📄 Probabilistic CFG with Latent Annotations

Summary

Treebank PCFGs make strong independence assumptions. Strong parsers usually weaken these by enriching non-terminals with hand-picked features such as head words, parent labels or subcategorization frames, which requires much trial and error. Matsuzaki, Miyao and Tsujii propose PCFG-LA, a generative model in which every non-terminal carries a hidden annotation drawn from a fixed set. The observed treebank tree is treated as incomplete data. A fine-grained grammar is learned automatically with EM, using an inside-outside-style procedure that runs over the given trees after binarization. Finding the single most probable parse under this model is NP-hard, so the authors compare three approximate decoders:

• reranking N-best PCFG parses,
• choosing the best fully annotated (Viterbi complete) tree,
• an approximate-distribution method.

On the Penn WSJ corpus, the best setup reaches 86.6% F1 on sentences of up to 40 words. This matches an unlexicalized parser built with extensive manual feature engineering (Klein and Manning, 2003). The result shows that useful symbol refinements can be learned rather than hand-designed.

Key points

• Model and training. Each node label becomes a pair of observed category and latent symbol. The tree probability sums over all latent assignments. This sum is computed with backward/forward recursions that are linear in the number of tree nodes once trees are binarized.
• Complexity. Exact best-parse search is NP-hard. The proof represents a stochastic tree substitution grammar (STSG) as a PCFG-LA and relies on the known hardness of STSG parsing.
• WSJ results. On sentences of 40 words or fewer, LR/LP is 86.7/86.6. On sentences of 100 words or fewer, it is 86.0/86.1. Klein and Manning (2003) reach 85.7/86.9, while Collins (1999) and Charniak (1999) remain ahead.
• Binarization and model size. Four binarization schemes were tested: CENTER-PARENT, CENTER-HEAD, LEFT and RIGHT. Accuracy grows with the number of parameters, and models of similar size perform alike regardless of scheme. The exception is small LEFT models.
• Costs and robustness. The largest models took roughly 15–20 hours to train. Different random initializations noticeably changed both log-likelihood and parsing accuracy.

Interesting ideas

• I1. Latent refinement instead of hand-crafted features. Hidden subcategories are learned by EM directly on annotated trees. The same idea could refine POS tags, UD relation labels or morphological categories wherever manual splitting is costly.
• I2. Cheap model as candidate generator. A simple markovised PCFG proposes candidates through N-best lists or a pruned chart, and the richer model only rescores them. This two-stage design suits any expensive scorer that is intractable to search exactly.
• I3. Choosing an approximation by testing. The authors analyse why the best annotated tree usually approximates the best observed tree, then compare decoders by plotting accuracy against parse time. The approximate-distribution method wins unless time is very tight, which is a useful way to evaluate any approximate inference.
• I4. Transform, train, then restore. Trees are binarized to keep computation tractable and converted back after parsing. The authors also check that the binarization choice matters little once models are large enough.
• I5. Initialization from a simpler model. Parameters start from the plain PCFG maximum-likelihood probabilities multiplied by random noise. Training several seeds gives an honest estimate of variance before claiming one configuration beats another.