📄 Towards History-based Grammars: Using Richer Models for Probabilistic Parsing

Summary

The paper addresses structural ambiguity in parsing. Earlier probabilistic models, such as the standard P-CFG, condition each rule choice on very little context. The authors propose History-based Grammars (HBG), a generative model in which the probability of expanding each node may depend on anything already built in the leftmost derivation. This includes words, syntactic and semantic categories, lexical heads and tree structure. Decision trees group derivation histories into equivalence classes, which makes such rich conditioning estimable. In this implementation, only the path from the current node to the root and the child index are examined.

The experiments use a broad-coverage feature-based unification grammar, IBM computer-manual text and the Lancaster Treebank as the gold standard. On 760 test sentences of 7–17 words, HBG raises the Viterbi rate from 60% (P-CFG) to 75%, cutting errors by 37%. The result suggests that statistical models learned from treebanks can take over much of the disambiguation burden. Traditionally, grammarians handled that burden through manual tuning.

Key points

• Data and domain:
  • The vocabulary is the 3,000 most frequent words from a 600,000-word corpus of 10 computer manuals.
  • The authors kept a few million words of fully covered sentences, drawn from 40M words of manuals.
  • Gold parses come from the Lancaster Treebank, which uses 17 non-terminal labels and 240 tags.
• Grammar:
  • It is a unification grammar with 21 features and 672 rule templates, of which 400 were used on 15,000 sentences.
  • Its more than 10,000 non-terminal labels are mapped onto Treebank labels for evaluation. Tags are ignored in that evaluation.
• Evaluation metrics:
  • The any-consistent rate is the share of sentences where the grammar proposes the correct parse anywhere among its candidates. It reaches 90%.
  • The Viterbi rate is the share of sentences where the model's top parse is correct. It is 60% for P-CFG and 75% for HBG.
  • A simpler head-annotated model scores 66%.
• Baseline training: The P-CFG baseline was trained with a Treebank-constrained version of the Inside-Outside algorithm.
• HBG estimation:
  • A decision tree models only the rule-template component of HBG. The other four factors use n-gram models with deleted interpolation.
  • Training used about 9,000 sentence-tree pairs, yielding about 240,000 tuples and a tree of roughly 40,000 nodes.
  • Building the tree took 18 hours and produced a model of nearly 100 MB.

Interesting ideas

• I1. Two separate metrics. The paper measures grammar coverage (any-consistent rate) apart from model selection (Viterbi rate). This shows whether errors come from a missing parse or a wrong choice, and it is a useful diagnostic for any parse-and-rank system.
• I2. Division of labour. The grammarian works only on coverage, while statistics learned from a treebank pick the best parse. This clean split could organise rule-based pipelines for low-resource languages.
• I3. Decision trees over histories. Asking questions about the derivation history lets a model use rich context without an explosion of parameters. The same trick could be applied to any sequential prediction task with structured context.
• I4. Bit-string encoding of categories and words. Similar items share prefixes in their codes. Categories and rules were coded by hand, and words via mutual-information clustering. This lets the decision tree ask questions at varying levels of granularity, which helps generalise from sparse data.
• I5. Functional parent versus immediate parent. The functional parent skips over unit productions such as NP2 → NP1, so that informative context is not hidden behind uninformative chain nodes. This is relevant to any tree-based feature extraction.