📄 Generative Models for Statistical Parsing with Combinatory Categorial Grammar

Summary

The paper asks whether a wide-coverage parser built on Combinatory Categorial Grammar (CCG) can be trained with generative probability models and still reach accuracy close to standard Penn Treebank parsers. CCG uses a much more constrained grammar that directly encodes extraction and coordination. The authors train on CCGbank, an automatic conversion of Penn Treebank trees into CCG normal-form derivations (WSJ sections 02-21 for training, section 23 for testing).

They start from a simple top-down model. At each node it chooses an expansion type, then generates the head daughter category and then the non-head daughter category. They then add several features:

• a coordination flag,
• a grandparent transformation,
• three distance measures,
• lexical word-word dependencies.

Because CCG trees and labels differ from Treebank ones, Parseval scores cannot be compared directly, so the authors also use a dependency-based evaluation. The best model recovers 89.9% of unlabeled word-word dependencies on section 23, close to Collins (1999). Unlike Gildea (2001), they find that word-word dependencies help substantially. This suggests that a linguistically richer grammar can be parsed statistically without a large accuracy penalty.

Key points

• The CCGbank lexicon extracted from training data has 1207 lexical categories, versus 48 Penn Treebank POS tags. The instantiated grammar has only about 3,000 rules, against more than 12,400 in the original Treebank representation.
• The translation to CCGbank handles 98.3% of training sentences and 98.5% of test sentences. Gapping and UCP constructions are not covered.
• The best model scores 89.9% unlabeled dependency recovery on section 23 and 89.7% on section 00. Collins (1999) reports 90.9% on section 00.
• For the most frequent subject-extraction dependency, the parser reaches 94.3% precision and 96.5% recall. Recall rises to 97.3% when bare-infinitival extraction analyses are also counted.
• Missing lexical entries are the main cause of errors and parse failures. The baseline fails on 6 of 2379 test sentences. The model labelled HWDep in Table 4 scores 86.6 on sentences with full lexical coverage but only 75.1 on sentences with missing entries.

Interesting ideas

• I1. Grammar-neutral evaluation. Score parsers on unlabeled head-dependent word pairs instead of bracket overlap. This allows fair comparison between systems with different tree shapes and label sets, for example across formalisms or annotation schemes.
• I2. Replace rare words with POS tags. Map rare training words and unknown test words to their POS tag rather than one generic unknown token. With a large, fine-grained lexicon, this keeps useful category information for unseen words.
• I3. Smooth lexical probabilities through POS tags. Interpolate P(w|c) with an estimate that passes through POS tags. This makes the parser robust to unseen words with little implementation cost. The authors also show that the rare-word cutoff interacts strongly with whether smoothing helps.
• I4. Separate two kinds of lexical gaps. Distinguish entirely unknown words from known words that lack the needed category, and report scores separately for sentences with and without missing entries. This diagnostic would reveal lexicon gaps in any lexicalized grammar or tagger.
• I5. Re-test feature gains under a new representation. Re-check techniques that helped in another representation, such as grandparent annotation. In CCG its gain was much smaller, because rich categories already encode context and further splitting increases data sparsity.