📄 A Linear Observed Time Statistical Parser Based on Maximum Entropy Models

Summary

The paper tackles full syntactic parsing of English. It aims for parse quality above earlier statistical parsers while keeping feature engineering light and decoding fast. Ratnaparkhi recasts parsing as a sequence of small decisions made in three left-to-right passes: POS tagging, flat-chunk detection, and then an alternation of constituent-building and completeness-checking steps. A separate maximum entropy model scores each kind of decision. Its features are generated automatically from short templates over the local context, such as neighbouring words, tags, constituent labels and head words. A simple breadth-first search keeps only the top-scoring partial derivations. Trained and tested on the Penn Treebank (Wall St. Journal), the parser reaches about 87% precision and 86% recall. This beats the best results previously reported, from Collins (1996) and Magerman's SPATTER (1995). Its running time grows linearly with sentence length in practice. The parser also outputs several ranked parses, and an oracle choosing the best of the top 20 would score about 93%. That gap points to reranking as a valuable research direction.

Key points

• Accuracy on section 23 of the WSJ part of the Penn Treebank is roughly 87% precision and 86% recall, measured with PARSEVAL and with the looser measures used by Collins (1996) and Magerman (1995).
• Four procedures (TAG, CHUNK, BUILD, CHECK) run in three passes. Their actions are designed so that every complete parse tree corresponds to exactly one derivation.
• BUILD labels each tree as Start X or Join X. CHECK answers Yes or No on whether the newest proposed constituent is finished, which plays the role of reduce versus shift in a shift-reduce parser.
• Feature templates cover head words, which are found with Magerman's head-finding rules. Each lexical predicate also gets backed-off variants that drop one or more words, which helps with rare words.
• An oracle that picks the best of the top 20 parses would reach about 93% precision and recall.

Interesting ideas

• I1. Splitting a reduce into incremental decisions. Instead of committing to a whole CFG rule at once, the parser attaches trees one by one and then asks a yes/no completeness question. Small, local classification steps like these are easier to model and could suit other structured-prediction tasks, such as transition-based parsers for UD treebanks.
• I2. Back-off expressed as features. Sparse lexical predicates are paired with less specific versions that omit words, and the maximum entropy model learns how much to trust each one. This avoids hand-tuned smoothing schemes like the one in Collins's bigram parser.
• I3. Oracle upper bound for reranking. Measuring how good the best parse in the top N could be gives a ceiling for any reranker. This tells you whether building a second-stage model is worth the effort, and the check works for any system that produces n-best output.
• I4. Chunking as a reusable intermediate layer. Flat phrases are found first with the same Start/Join tagging scheme, and later passes then work on a shorter forest. A staged pipeline like this can simplify parsers for languages or domains with limited resources.
• I5. Plain words instead of word clusters. Unlike SPATTER, the model uses raw words in its predicates, which removes a costly clustering step. Adding new kinds of information, such as punctuation cues, only requires writing another template.