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.
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.
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