

![0_image_0.png](0_image_0.png)

istence of a recursive schema (of the form z → zs); if such a recursive schema is added, then eventually the sequence gets rewritten to just z.

Example. Consider a variant of the Travel domain (Figure 1) allowing the traveler to purchase a day pass (instead of a single-trip ticket) for the train. Two training plans are shown in Figure 2. First SH builds the primitive action schemas: A1 → Buyticket, A2 → Getin, and A3 → Getout; the updated plan examples are shown as level 2 in the Figure. Next, since A2A3 is the most frequent pair in the plans
(and there is insufficiently obvious evidence of recursion), SH constructs a rule S1 → A2A3. After updating the plans with the new rule, the plans become A1S1 and A1S1S1S1, depicted as level 3 in the Figure. At this point SH realizes the recursive structure (the simple repetition A1S1S1S1), and so adds the rule A1 →
A1S1. After rewriting all plans are parsable to the symbol A1 (let T = A1), so SH
is done: the final set of schemas is at the bottom left of Figure 2.

## 3.2. Refining Schema Probabilities: Em Phase

We take an Expectation-Maximization (EM) approach in order to learn appropriate parameters for the set of schemas returned by SH. EM is a gradient-ascent method with two phases to each iteration: first the current model is used to compute expected values for the hidden variables (E-step: induces a well-behaved lower bound on the true gradient), and then the model is updated to maximize the likelihood of those particular values (M-step: ascends to the maximum of the lower bound). Doing so will normally change the expected values of the hidden variables, so the process is repeated until convergence, and convergence does in fact occur [9]. For our problem, standard (soft-assignment) EM would compute an entire distribution over all possible parses (of each plan, at each iteration); as the grammars are automatically generated, there may very well be a huge number of such parses. So instead we focus on computing just the parse considered most