hints concerning non-primitives; for language learning it is reasonable to assume that such annotations are available, because the non-primitives involved are agreed upon by multiple users (or there is no communication). In particular information sources such as dictionaries and informal grammars can be mined relatively cheaply. In the case of preference learning for plans, the non-primitives of interest are user-specific mental constructs (preferences), and so it is far less reasonable to assume that appropriate annotations could be obtained cheaply. So, unlike learning pCFGs, our system must invent all of its own non-primitive symbols without any hints.

Our learner operates in two phases. First a structure hypothesizer (SH) invents non-primitive symbols and associated reduction schemas (tasks and methods), as needed, in a greedy fashion, to cover all the training examples. In the second phase, the probabilities of the reduction schemas are iteratively improved by an Expectation-Maximization (EM) approach. The result is a local optima in the space of pHTN domains (instead of H∗ = argmaxH P(H | Φ, T), the global maximum).

## 3.1. Structure Hypothesizer (Sh)

We develop a (greedy) structure hypothesizer (SH) in order to generate a set of methods that can, at least, parse all plan examples, but more than that, parse all the plan examples without resorting to various kinds of trivial grammars (for example, parsing each plan example with a disjoint set of methods). The basic idea is to iteratively factor out frequent common subsequences, in particular frequent common pairs since we work in Chomsky normal form. We describe the details in the following; Algorithm 1 summarizes in pseudocode.

SH learns reduction schemas in a bottom-up fashion. It starts by initializing H
with a separate reduction for each primitive (from distinct non-primitives); this is a minor technical requirement of Chomsky normal form.4 Then all plan examples are rewritten using this initial set of rules: so far not much of import has occurred.

Next the algorithm enters its main loop: hypothesizing additional schemas until all plan examples can be parsed to an instance of the top level task, T.

5 In short, SH hypothesizes a schema, rewrites the plan examples using the new