📄 Statistical Decision-Tree Models for Parsing

Summary

Magerman presents SPATTER, a statistical parser that learns every parsing choice from a treebank instead of relying on a hand-built grammar. These choices include part-of-speech tags, constituent structure and constituent labels. Each choice is scored by a decision-tree model that selects which context features to use, such as words, relations between words, and already-built constituents. The probability of a full tree is the product of its decision probabilities. Search combines a stack decoder with breadth-first expansion and probabilistic pruning. The paper also shows formally that decision trees match interpolated n-gram models in expressive power. Their real advantage is that they can be learned automatically when the context space is huge. SPATTER beat IBM's long-developed grammar-based parser on a computer-manuals task. On Penn Treebank WSJ sentences of up to 40 words, it reached about 86% precision and 86% recall, with 1.3 crossing brackets per sentence. The work matters because it showed that a richly lexicalized statistical model, trained only on annotated data, can outperform expert-written grammars on broad-coverage parsing.

Key points

• Data: Penn Treebank v2, WSJ portion, with 46 POS tags and 27 non-terminal labels. Training used sections 02–21 (about 40,000 sentences) and testing used section 00 (1,920 sentences). Only sentences of 40 words or fewer were evaluated.
• PARSEVAL results for sentences of up to 40 words were roughly 86% precision, 86% recall and 1.3 crossings per sentence. For sentences of 10–20 words, the figures were about 91% precision, 90% recall and 0.5 crossings.
• Against the IBM computer-manuals parser, which had over ten years of grammar development, SPATTER produced zero-crossing parses for 76% of sentences versus IBM's 69%.
• The parser takes raw words and weighs all tag sequences probabilistically rather than committing to one pre-tagged sequence. On an SGI R4400 machine equipped with 160 MB of RAM, the average parsing time was roughly 12 seconds for each sentence.
• Sections 00 and 01 were kept out of training because they carry coreference annotation for a separate project. Using them could have biased later coreference experiments.

Interesting ideas

• I1. Parsing as a sequence of scored decisions. Treating a tree as a chain of probabilistic choices lets one model family handle tagging, bracketing and labeling. The same framing works for any structured-prediction task.
• I2. Decision trees as learned smoothing. The author shows a tree is an interpolated n-gram model in which only the leaf's history gets weight. This is a useful way to explain why feature-selecting models can scale to very large contexts where full deleted interpolation becomes impractical.
• I3. Binary encoding of words. Words are represented by about 30 yes/no questions that together identify each word. This lets a tree split on partial lexical information, which could help low-resource or morphologically rich vocabularies such as Ukrainian.
• I4. No hard commitment to upstream predictions. Keeping all tag hypotheses alive, weighted by probability, avoids the cascading errors of a pipeline. The same approach applies to tokenization or NER feeding into later stages.
• I5. Careful split hygiene. Reserving annotated sections needed by a downstream study, and reporting results by sentence length, are good evaluation habits for any shared corpus.