📄 Three Generative, Lexicalised Models for Statistical Parsing

Summary

Collins addresses statistical parsing of English Wall Street Journal text from the Penn treebank. Earlier strong lexicalised parsers (Magerman 95; Jelinek et al. 94; Collins 96) estimated P(T|S) directly and produced trees with no information on subcategorisation or wh-movement, which are needed to recover predicate-argument structure. The paper proposes three generative models of lexicalised context-free grammar that estimate the joint P(T, S) through a head-driven, top-down derivation:

• Model 1 generates the head child first, then left and right modifiers using separate zero-order Markov processes conditioned on a surface distance measure.
• Model 2 marks complements with a "-C" suffix and adds probabilistic left and right subcategorisation frames.
• Model 3 adds a probabilistic treatment of traces from relative-clause extraction.

The final system reaches 88.1% constituent precision and 87.5% recall, an average gain of 2.3% over Collins 96. Beyond the accuracy gain, the output is richer, with complements and traces that downstream applications can use for argument extraction.

Key points

• The data is the Penn treebank WSJ corpus, with lexical heads assigned by rules similar to those of Magerman 95 and Jelinek et al. 94.
• The distance feature is a three-part vector:
  • whether the intervening string is empty,
  • whether it contains a verb,
  • whether it contains 0, 1, 2 or more than 2 commas (counting tokens tagged "," or ":").
• Complements are identified heuristically by parent/child label configurations. Nodes are excluded if they carry semantic tags such as ADV, TMP, LOC or PRP. The first child after the head of a PP is marked as a complement.
• Trace recovery was evaluated on 436 cases:
  • 342 string-vacuous subject extractions reached 97.1% precision and 98.2% recall.
  • 94 longer-distance cases reached 76% precision and 60.6% recall.
  • Infinitival relatives were much harder, at 41% precision and 18% recall on 60 cases in section 23.
• The final scores are 88.1/87.5% constituent precision/recall.

Interesting ideas

• I1. Head-first factorisation of rules. Generating the head child first and then each modifier independently (with a STOP symbol ending each side) replaces one sparse rule probability with many small, well-estimated ones. This also lets the model handle rules never seen in training, which suits any treebank with flat, highly varied rules.
• I2. Subcat frames as hard constraints inside a soft model. A multiset of required complements is drawn first, and each complement is removed from it as it is generated. STOP has zero probability while the frame is non-empty, and complements outside the frame are forbidden. This neatly fixes errors such as two subjects that independence assumptions would otherwise permit, and the same constraint trick could carry over to dependency or argument-structure models.
• I3. Cheap surface-distance features. Simple binary or bucketed features, such as adjacency, an intervening verb, or comma counts, capture attachment preferences like right-branching and modification of the most recent verb. They are easy to reproduce for other languages.
• I4. Deriving richer labels from existing annotation. Function tags and configurational rules convert a plain treebank into complement/adjunct training data, so richer output does not require new annotation.
• I5. Reusing the parser as a language model. Because the model is generative, summing over trees (or taking the best tree) gives P(S), which the author suggests could be useful for syntax-aware language modelling, for example in speech recognition.