📄 A Maximum-Entropy-Inspired Parser

Summary

The paper addresses how to make a generative statistical parser for Penn treebank-style trees more accurate, given sparse training data. Charniak's model builds a parse top-down. For each constituent it predicts three things in order: the head's pre-terminal (tag), the lexical head, and the expansion. Expansions come from a lexicalized Markov grammar rather than fixed treebank rules. The main contribution is a way to condition and smooth these probabilities that borrows from log-linear modelling. Each probability is a product of ratios, and each ratio adjusts the estimate as more context is added. This lets the author test and combine many conditioning events without heavy re-engineering. Trained and tested on the standard Wall Street Journal treebank sections, the parser reaches 90.1% average precision/recall on sentences of up to 40 words and 89.5% on sentences of up to 100 words. That is a 13% error reduction over the best earlier single parser (Collins). The result also refutes the idea that treebank-trained parsers had hit a performance ceiling.

Key points

• Results on the standard WSJ Penn treebank sections: precision/recall reaches 90.1% when sentences are capped at ≤40 words, and 89.5% when the cap is ≤100 words. This is about 13% less error than Collins's parser [9]. The conclusion prints 91.1% for the ≤40 setting, which conflicts with the abstract and introduction.
• Predicting the head's pre-terminal before the head word itself raised labeled precision/recall by nearly 2%, an effect the author did not anticipate.
• The conditioning context for the head tag includes:
  • the parent's label, head tag and head word;
  • the label of the left sibling;
  • the grandparent's label.
• Comparison of expansion models:
  • a first-order Markov grammar was slightly worse than a treebank grammar;
  • a second-order one was slightly better;
  • a third-order one was clearly better.
• The maximum-entropy-inspired smoothing gave a small but real gain over deleted interpolation. The non-terminal set was extended with the symbols aux and auxg for certain auxiliary verbs.

Interesting ideas

• I1. Smoothing as a product of ratios. Start from a coarse estimate, then multiply by factors of the form "estimate with more context divided by estimate with less context." This gives much of the flexibility of log-linear models without iterative training, and suits any sparse conditional estimation task, such as tagging or language modelling.
• I2. Context chains that skip unrelated features. Each added factor can condition only on the features that matter for it, instead of on everything added before. This reduces fragmentation of the data when the features come from unrelated sources.
• I3. Predicting a coarse category first. Guessing the tag before the word gives a cheap intermediate variable that sharpens the later prediction. The same decomposition could help other generative models with large vocabularies.
• I4. Markov-generated rule right-hand sides. Generating the head child first and then its left and right siblings outward, with tunable order, means unseen rules can still get probability. Treating the order as a parameter to sweep made for a clean ablation.
• I5. Choosing a model for flexibility. The author favored a model in which changing features needs no new code. This made fast experimentation possible across conditioning events and grammar types, a useful principle for research codebases.