Sparse Multi-Scale Grammars for Discriminative Latent Variable Parsing

Slav Petrov, Dan KleinEMNLP 2008 · OpenReview

Abstract

We present a discriminative, latent variable approach to syntactic parsing in which rules exist at multiple scales of refinement. The model is formally a latent variable CRF grammar over trees, learned by iteratively splitting grammar productions (not categories). Different regions of the grammar are refined to different degrees, yielding grammars which are three orders of magnitude smaller than the single-scale baseline and 20 times smaller than the split-and-merge grammars of Petrov et al. (2006). In addition, our discriminative approach integrally admits features beyond local tree configurations. We present a multiscale training method along with an efficient CKY-style dynamic program. On a variety of domains and languages, this method produces the best published parsing accuracies with the smallest reported grammars.

Introduction

Syntactic parsing—the process of determining the grammatical structure of a sentence—often relies on "latent variables." Because standard labels like "Noun Phrase" (NP) are too coarse to capture all linguistic nuances, researchers typically split them into subcategories (e.g., $NP_{subject}$ vs. $NP_{object}$).

However, this leads to a "curse of dimensionality." If you double the number of categories, the number of possible binary grammar rules increases eightfold. Previous "split-and-merge" approaches tried to mitigate this by merging useless categories back together, but the resulting grammars remained dense and computationally expensive. Furthermore, most of these models were generative; they struggled to incorporate "overlapping" features (like capitalization or punctuation patterns) that don't fit neatly into a standard context-free grammar.

Methodology

The authors propose a discriminative, multi-scale approach that refines grammar rules only where necessary.

Production Splitting and Hierarchical Refinement

Instead of splitting categories (like NP), the model splits productions (the rules themselves). This allows a category to be complex in one part of the grammar (e.g., when it's a subject) but remain simple elsewhere. Starting with a simple X-bar grammar, each rule is iteratively refined into eight sub-rules.

Sparsity via $L_1$ Regularization

To prevent rule explosion, $L_1$ regularization is used during training. This pressure forces the weights of redundant or useless rules to zero. If all refinements of a rule have zero weight, they are collapsed back into their parent, creating a "multi-scale" effect where some rules are fine-grained and others are coarse.

The transition from dense single-scale productions to sparse multi-scale productions via regularization.

Discriminative Framework and Inference

The grammar is treated as a Hidden Variable Conditional Random Field (CRF), allowing for non-local features like unknown word suffixes and span-based patterns (punctuation, capitalization). For inference, a modified CKY algorithm handles a chart where nodes exist at different scales, avoiding the need to expand the full dense grammar.

Results and Evaluation

The model was evaluated on English (Penn Treebank, Brown Corpus), French (French Treebank), and German (NEGRA corpus).

  • Grammar Size: The final multi-scale grammars used fewer than 50,000 active productions—20x smaller than previous state-of-the-art split-and-merge grammars and 1,000x smaller than single-scale baselines.
  • Accuracy: On the WSJ English task, the model achieved an F1 score of 89.4% (90.0% with span features), matching or exceeding contemporary generative models.
  • Speed: Due to the smaller grammar and efficient CKY implementation, the parser was 36% faster than previous latent variable parsers, averaging 0.36 seconds per sentence.
  • Multilingual Success: The model achieved state-of-the-art results for French and German without language-specific tuning.

Discussion

A key insight is that language complexity is non-uniform. A multi-scale grammar recognizes that certain categories (like Verb Phrases) may require many sub-types, while others (like Prepositional Phrases) remain simple. By using $L_1$ regularization, the model automatically performs feature selection on the grammar itself.

An example parse tree demonstrating labels at different scales of refinement (e.g., $NP_0$ vs $NP_1$ vs $NP_*$).

Furthermore, the discriminative approach outperformed generative models on out-of-domain data (Brown corpus), suggesting that highly regularized, sparse grammars are less prone to overfitting training set quirks.

Conclusion

While the model offers fast inference and high accuracy, training remains computationally intensive, taking approximately three days on an 8-CPU cluster. The non-convex objective function also makes the model sensitive to initialization. Future work could explore more sophisticated global features and optimization techniques to further enhance performance.

Summary updated

Abstract

We present a discriminative, latent variable approach to syntactic parsing in which rules exist at multiple scales of refinement. The model is formally a latent variable CRF grammar over trees, learned by iteratively splitting grammar productions (not categories). Different regions of the grammar are refined to different degrees, yielding grammars which are three orders of magnitude smaller than the single-scale baseline and 20 times smaller than the split-and-merge grammars of Petrov et al. (2006). In addition, our discriminative approach integrally admits features beyond local tree configurations. We present a multiscale training method along with an efficient CKY-style dynamic program. On a variety of domains and languages, this method produces the best published parsing accuracies with the smallest reported grammars.
BibTeX
@inproceedings{petrov2008sparse,
  author = {Slav Petrov and Dan Klein},
  title = {{Sparse Multi-Scale Grammars for Discriminative Latent Variable Parsing}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
  url = {https://openreview.net/forum?id=Hk-sTWzOWH},
}
Figure