where the maximization is only over different parameterizations (not over all pHTNs). Each task Z enjoys independent parameters, and from above the likelihood expression is a multinomial in those parameters (θZXY = P(Z → XY | H′)),
and so can be maximized simply by setting:

$$P(Z\to XY\mid{\mathcal{H}}_{\ell+1}):=\frac{M[Z\to XY]}{M[Z]}.\tag{8}$$

That is, the E-step completes the input data Φ by computing the parses of Φ
expected by Hℓ; subsequently the M-step treats those parses as ground truth, and sets the new reduction probabilities to the 'observed' frequency of such reductions in the completed data. This improves the likelihood of the model, and the process is repeated until convergence.

Discussion: Although the EM phase of learning does not introduce new reduction schemas, it does participate in structure learning in the sense that it effectively deletes reduction schemas by assigning zero probability to them. For this reason SH does not attempt to find a completely minimal grammar before running EM.

Nonetheless it is important that SH generates small grammars, as otherwise overfitting could become a serious problem. Worst choices of a hypothetical structure learner would include the trivial grammar that produces all and only the training plans; if this occurs the EM algorithm above would happily drive the probability of all other rules to 0 as the included trivial grammar would allow the perfect reproduction of training data.

## 3.3. Evaluation

To evaluate our pHTN learning approach, we designed and carried out experiments in both synthetic and benchmark domains. All the experiments were run on a 2.13 GHz Windows PC with 1.98GB of RAM. Although we focus on accuracy (rather than CPU time), we should clarify up-front that the runtime for learning is quite reasonable - between (almost) 0ms to 44ms per training plan. We take an oracle-based experimental strategy, that is, we generate an oracle pHTN H∗(to represent a possible user) and then subsequently use it to generate behavior Φ (a set of preferred plans). Our learner then induces a pHTN H from only Φ; so then we can assess the effectiveness of the learning in terms of the differences between the original and learned models. In some settings (e.g., knowledge discovery) it is very interesting to directly compare the syntax of learned models against ground truth, but for our purposes such comparisons are much less interesting: we can be certain that, syntactically, H will look nothing like a real user's preferences (as