Probabilistic Context-Free Grammar Induction Based on Structural Zeros

Mehryar Mohri, Brian RoarkNAACL 2006 · OpenReview

Abstract

We present a method for induction of concise and accurate probabilistic context-free grammars for efficient use in early stages of a multi-stage parsing technique. The method is based on the use of statistical tests to determine if a non-terminal combination is unobserved due to sparse data or hard syntactic constraints. Experimental results show that, using this method, high accuracies can be achieved with a non-terminal set that is orders of magnitude smaller than in typically induced probabilistic context-free grammars, leading to substantial speed-ups in parsing. The approach is further used in combination with an existing reranker to provide competitive WSJ parsing results.

Introduction: The Speed-Accuracy Tradeoff

In Natural Language Processing, parsing accuracy often comes at the cost of computational efficiency. To improve accuracy, researchers typically "split" grammar categories (non-terminals) into more specific sub-categories. While this captures linguistic nuance, it leads to a "state explosion." Since the standard CYK parsing algorithm has a complexity of $O(n^3 |P|)$, where $|P|$ is the number of grammar productions, adding rules makes parsers significantly slower and more memory-intensive. This paper addresses the challenge of inducing a concise grammar that remains accurate by focusing on what is linguistically impossible.

Methodology: Identifying Structural Zeros

The authors propose a method to build "skinny" Probabilistic Context-Free Grammars (PCFGs) by identifying structural zeros—combinations of grammar rules that never occur because they are forbidden by the language's syntax, rather than just being absent due to sparse data (sampling zeros).

To distinguish between the two, the authors use the Log Likelihood Ratio ($G^2$) to rank unobserved events. If an event is expected to occur frequently based on individual component counts but never appears in the corpus, it receives a high $G^2$ score, indicating a structural zero.

Top unobserved productions ranked by their Log Likelihood Ratio ($G^2$) score.

Instead of splitting every category, the authors perform selective state splitting only on non-terminals corresponding to these high-scoring structural zeros. This technique is applied within a simple "Markov order-0" framework, which is then "patched" with these selective splits to regain accuracy without the typical state explosion.

Key Results and Linguistic Validation

The top-ranked structural zeros identified by the algorithm align with linguistic intuition. For instance, the highest-scoring zero, PP → IN[that] NP, reflects that "that" rarely functions as a preposition in English.

Experimental results on the Penn Treebank (WSJ) demonstrate a significant breakthrough in efficiency. The proposed model, using selective splits, achieved an F-measure of 83.7% on the development set while parsing at 65.9 words per second. This is a substantial improvement over standard baselines of similar complexity, such as the Markov order-2 model which parses at only 24.9 words per second.

F-measure accuracy vs. parsing speed (words per second) for various models.

As shown in the figure above, the models with non-factored splits (represented by 'x') occupy a superior position in the speed-accuracy trade-off space compared to traditional Markov-order models. When combined with a state-of-the-art reranker, the system reached an F-measure of 88.0%, confirming that these concise grammars are highly effective for downstream processing.

Conclusion

By explicitly modeling syntactic constraints through structural zeros, this approach allows for the induction of highly efficient PCFGs. While currently limited by certain heuristic constraints on split types, the method demonstrates that a massive grammar isn't necessary for high accuracy—one simply needs to know which rules are impossible. Future work may explore broader non-terminal annotations and the application of structural zero detection to other learning tasks.

Summary updated

Abstract

We present a method for induction of concise and accurate probabilistic context-free grammars for efficient use in early stages of a multi-stage parsing technique. The method is based on the use of statistical tests to determine if a non-terminal combination is unobserved due to sparse data or hard syntactic constraints. Experimental results show that, using this method, high accuracies can be achieved with a non-terminal set that is orders of magnitude smaller than in typically induced probabilistic context-free grammars, leading to substantial speed-ups in parsing. The approach is further used in combination with an existing reranker to provide competitive WSJ parsing results.
BibTeX
@inproceedings{mohri2006probabilistic,
  author = {Mehryar Mohri and Brian Roark},
  title = {{Probabilistic Context-Free Grammar Induction Based on Structural Zeros}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2006},
  url = {https://openreview.net/forum?id=BJ-cM7ZOZr},
}
Figure