Improved Inference for Unlexicalized Parsing

Slav Petrov, Dan KleinNAACL 2007 · OpenReview

TL;DR

This paper introduces a novel coarse-to-fine parsing strategy for hierarchically state-split PCFGs that significantly speeds up parsing without sacrificing accuracy. They also compare different inference objectives for these grammars, demonstrating that certain methods optimize for exact match while others are better for overall accuracy (F1 score), and show that their approach generalizes well to multiple languages.

What Problem Does This Paper Address?

Parsing, the task of assigning a grammatical structure to a sentence, is a fundamental problem in Natural Language Processing. While unlexicalized PCFGs (Probabilistic Context-Free Grammars) can be learned to achieve high accuracy, the inference step – finding the best parse tree for a given sentence – can be computationally very expensive, especially with complex grammars. This paper tackles the challenge of making this inference process much faster while maintaining or even improving accuracy, particularly for hierarchically state-split PCFGs, which offer a way to capture richer linguistic structure than simpler PCFGs. They also explore how to best choose a parse tree when the grammar defines a distribution over possible trees, and how well these methods work across different languages.

Methods

The paper presents three main contributions:

  1. Hierarchical Coarse-to-Fine Parsing: This is the core innovation for speeding up inference. Instead of parsing directly with the final, complex grammar, they use a sequence of progressively simpler "projected" grammars. The key idea is that these simpler grammars can quickly prune away unlikely parse constituents, drastically reducing the search space for the subsequent, more complex grammars. A novel aspect is that these projected grammars are estimated from the final grammar itself, rather than requiring separate treebanks, making the process more flexible. This multi-stage pruning allows for significant speedups.
  2. Inference Objective Comparison: The authors investigate different ways to select the "best" parse tree from the distribution defined by the PCFG. They compare methods based on:
  3. Maximum Likelihood (Exact Match): Finding the single most probable parse tree.
  4. Risk Minimization: Selecting a tree that minimizes expected loss under various criteria (e.g., exact match, F1 score). This involves either sampling from the grammar or using dynamic programming approaches.
  5. Variational Approaches: Approximating the true posterior distribution over parses. They analyze the trade-offs, showing that some methods are better for exact matches, while others excel at maximizing overall F1 scores. They also highlight the importance of handling unary productions, which can complicate inference.

  6. Multilingual Experiments: They demonstrate the effectiveness of their approach by training models on English, German, and Chinese treebanks without any language-specific tuning. This shows the generalizability of their learned grammar structures and inference methods.

Datasets

The paper uses standard treebanks for training and evaluation:

  • English: Penn Treebank (used for learning grammars and evaluating performance).
  • German: Standard corpora (specific details provided in Table 3).
  • Chinese: Standard corpora (specific details provided in Table 3).

They also mention using a held-out set for tuning pruning thresholds in their coarse-to-fine method.

Key Insights and Ideas

  • Grammar Projections for Speed: Using simpler versions of the grammar (projections) to prune the search space is a highly effective way to accelerate parsing. The fact that these projections can be derived from the final grammar itself is a significant practical advantage.
  • No Free Lunch for Inference Objectives: There isn't a single "best" inference objective. The choice depends on whether the goal is to achieve perfect sentence matches (exact match) or to maximize overall accuracy (F1 score).
  • Generalizability of Learned Structure: Hierarchically state-splitting PCFGs, when learned automatically, capture linguistic generalizations that are robust across different languages, even without language-specific feature engineering.
  • Unary Productions Matter: The handling of unary productions is crucial for understanding the behavior of different inference algorithms.

Key Results

  • Speedup: The coarse-to-fine parsing scheme can make parsing up to 100 times faster than the baseline PCFG parser, with no loss in empirical accuracy. For example, on a development set, they achieve 91.2% F1 in 1200 seconds, or 91.1% F1 in 680 seconds with more aggressive pruning.
  • Accuracy: Their method achieves state-of-the-art parsing figures for German and Chinese, and competitive results for English, often outperforming previous unlexicalized methods.
  • Multilingual Performance: The approach generalizes well to German and Chinese, achieving high accuracies without language-specific tuning.
  • Inference Objective Performance: MAX-RULE-PRODUCT consistently outperformed MAX-RULE-SUM and VARIATIONAL approaches for overall accuracy (F1), while exact match objectives were superior for exact match accuracy.

Limitations and Future Work

  • English Performance: While competitive, their English parser is outperformed by reranking parsers that leverage non-generative features (like those from Charniak and Johnson, 2005). This suggests that for English, incorporating richer, non-generative features might be necessary to push accuracy further.
  • Overfitting: Figure 4 suggests that while the coarse-to-fine approach improves performance on the training domain (WSJ), there might be some overfitting occurring on other domains (Brown Corpus) after a certain number of training iterations.
  • Future Work: The paper implicitly suggests exploring more sophisticated feature integration for languages like English and further investigating the interplay between coarse-to-fine pruning and domain adaptation. The availability of the parser publicly is also a step towards broader adoption and further research.

Summary updated

Abstract

We present several improvements to unlexicalized parsing with hierarchically state-split PCFGs. First, we present a novel coarse-to-fine method in which a grammar’s own hierarchical projections are used for incremental pruning, including a method for efficiently computing projections of a grammar without a treebank. In our experiments, hierarchical pruning greatly accelerates parsing with no loss in empirical accuracy. Second, we compare various inference procedures for state-split PCFGs from the standpoint of risk minimization, paying particular attention to their practical tradeoffs. Finally, we present multilingual experiments which show that parsing with hierarchical state-splitting is fast and accurate in multiple languages and domains, even without any language-specific tuning.
BibTeX
@inproceedings{petrov2007improved,
  author = {Slav Petrov and Dan Klein},
  title = {{Improved Inference for Unlexicalized Parsing}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2007},
  url = {https://openreview.net/forum?id=BJWL9mWdWH},
}
Figure