likely by the current parameters, that is, we are employing the hard-assignment variation of EM. One beneficial side-effect is that this introduces bias in favor of less ambiguous grammars - for in-depth analysis of the tradeoffs involved in choosing between hard and soft assignment see [10, 11]. In the following we describe the details of our specialization of (hard-assignment) EM.

In the E-step, the current model Hℓis used to compute the most probable parse tree, X
∗
ℓ
(φ), of each example φ (from the fixed start symbol T): X
∗
ℓ
(φ) =
argmaxparse X P(X | **φ, T,** Hℓ). This computation can be implemented reasonably efficiently in a bottom-up fashion since any subtree of a most probable parse is also a most probable parse (of the subsequence it covers, given its root, etc.). The first level is particularly simple since we associated every primitive, a, with a distinct non-primitive, Za (so its most probable, indeed only, parse is just Za → a). The remainder of the parsing computes:

$$P(a_{i},\ldots,a_{j}\mid Z,{\cal H}_{\ell})=$$ $$\max_{k;Z\to X,Y,\theta\in{\cal H}_{\ell}}\theta\cdot P(a_{i},\ldots,a_{k}\mid X,{\cal H}_{\ell})\cdot P(a_{k+1},\ldots,a_{j}\mid Y,{\cal H}_{\ell}),\tag{6}$$  for all indices $i<j\in[n]$ and tasks (non-terminals) $Z$ (so the parsing com
for all indices **i < j** ∈ [n] and tasks (non-terminals) Z (so the parsing computes O(n 2m) maximizations, each in O(**nr/m**) steps, for a worst-case runtime of O(n 3r) on a plan of length n with m tasks and r rules in the pHTN). Conceviably one of the reduction schemas might exist with 0 probability: the implementation prunes such schemas rather than waste computation. By recording the rule and midpoint (k) winning each maximization, the most probable parse of φ, X
∗
ℓ
(φ),
can be easily extracted (beginning at P(a1**, . . . , a**n | T, Hℓ)).

After getting the most probable parse trees for all plan examples, the learner moves on to the M-step. In this step, the probabilities associated with each reduction schema are updated by maximizing the likelihood of generating those particular parse trees; let X = {X ∗
ℓ
(φ) | φ ∈ Φ} and let M[event] count how many times the specified event happens in X (for example, M[Z], for some task Z, is the total number of times Z appears in the parses X). Then:

$$\mathcal{H}_{\ell+1}=\operatorname{argmax}_{\mathcal{H}^{\prime}}\prod_{\mathcal{X}^{*}\in\mathbf{X}}P(\mathcal{X}^{*}\mid T,\mathcal{H}^{\prime}),$$ $$=\operatorname{argmax}_{\mathcal{H}^{\prime}}\prod_{\mathcal{X}^{*}\in\mathbf{X}}\prod_{Z\to XY\in\mathcal{X}^{*}}P(Z\to XY\mid\mathcal{H}^{\prime}),$$ $$=\operatorname{argmax}_{\mathcal{H}}\prod_{Z}\prod_{Z\to XY,\theta_{ZXY}\in\mathcal{H}^{\prime}}\theta_{ZXY}^{M[Z\to XY]},\tag{7}$$

10