Reranking the Berkeley and Brown Parsers

Mark Johnson, Ahmet Engin UralNAACL 2010

TL;DR

This paper explores how to improve syntactic parsing accuracy by reranking the outputs of two leading parsers, the Berkeley and Brown parsers. They found that while a standard set of reranking features worked well for the Brown parser, a more extensive, "extended" feature set was necessary to significantly improve the Berkeley parser and combined outputs. This highlights the importance of parser-specific features for effective reranking.

What Problem Does This Paper Address?

Syntactic parsing, the task of identifying the grammatical structure of sentences, is a fundamental step in natural language processing (NLP). While many sophisticated parsing algorithms exist, achieving perfect accuracy remains a challenge. Two prominent "generative" statistical parsers are the Charniak's "Maximum Entropy Inspired" parser (referred to as the "Brown" parser) and Petrov's "split-merge" parser (the "Berkeley" parser). Both of these parsers can produce a list of the top-N most likely parse trees (an "n-best list") for a given sentence.

The problem this paper addresses is how to best leverage these n-best lists, especially when combining the outputs of different parsers, to achieve even higher parsing accuracy. Specifically, they investigate whether a generic set of "reranking" features, designed to re-evaluate and re-order the candidate parses, works equally well for both parsers, or if parser-specific features are crucial for optimal performance.

Methods

The core technique employed is reranking. This involves taking the n-best list of parse trees produced by a parser and using a separate model (a reranker) to re-score these trees. The reranker then selects the tree with the highest score as the final prediction.

The authors compare two sets of reranking features:

  • Standard Feature Set: This is the set of features originally developed for the Brown parser.
  • Extended Feature Set: This is a significantly larger set of features, incorporating a wider range of linguistic and structural information, designed to be more comprehensive and potentially capture nuances missed by the standard set. This set includes features related to:
  • Parser identity
    • Log probabilities from the parsers
    • Conditional probabilities
    • Right-branching structures
    • "Heavy" phrases
    • Left and right branching lengths
    • Grammatical rules and n-grams of categories
    • Head words and dependencies
    • Syntactic and semantic heads
    • Right-branching context
    • Subject-verb agreement
    • Parallelism and length of conjoined phrases
    • Words and their POS tags at phrase boundaries
    • Tree fragments and auxiliary trees

They train rerankers using both feature sets on n-best lists generated by:

  1. The Berkeley parser alone.
  2. The Brown parser alone.
  3. A combined n-best list containing the union of parses from both parsers.

They also conduct an ablation study where they systematically remove individual feature "super-classes" from the extended set to understand the contribution of each type of feature. For training, they primarily use the L-BFGS algorithm, but for the ablation study, they switch to the averaged perceptron algorithm for speed, noting a slight drop in accuracy.

Datasets

The primary dataset used is the Wall Street Journal (WSJ) section of the Penn Treebank corpus. This is a standard benchmark for syntactic parsing. The experiments are set up using a 20-fold cross-validation approach, where sections 2-21 are used for training and testing across folds, and sections 22, 23, and 24 are used for final evaluation. Specifically, sections 1-18 are used for training rerankers, sections 19-20 for development, and section 22 for testing.

Key Insights and Ideas

  • Parser-Specific Features Matter: The most striking insight is that the standard reranker features, optimized for the Brown parser, do not yield significant improvements when applied to the Berkeley parser or a combined list. This strongly suggests that different parsers capture different types of information, and reranking features need to be tailored to the specific parser's strengths and weaknesses.
  • Extended Features Unlock Potential: The "extended" feature set, with its vast number of features and diverse linguistic information, proves much more effective, especially for the Berkeley parser and the combined n-best lists. This indicates that the Berkeley parser, which is often considered less lexicalized than the Brown parser, benefits greatly from explicit linguistic features that capture global tree properties.
  • Combined Parsers Benefit from Recalibration: Linguistically-informed features (like Heads, SynSemHeads, HeadTree) become more important when reranking the combined n-best lists. This suggests that while individual parsers might produce internally consistent probabilities, combining their outputs requires a recalibration mechanism that can better reconcile their different perspectives.
  • Log Probability is Still Key: Features related to the parsers' own log probabilities (RelLogP, InterpLogCondP) are crucial, even with the extended feature set. This highlights that the parsers' initial scoring is still a valuable signal, but it needs to be augmented and potentially adjusted by other features.
  • WEdges is Surprisingly Useful: The WEdges feature, which captures information about words and POS tags at the boundaries of non-terminals, proves particularly effective for reranking the Berkeley parser.

Key Results

  • Standard Features: Reranking the Berkeley parser's n-best lists with the standard features yielded no overall improvement in f-score. Combining Berkeley and Brown parses with standard features also showed no improvement.
  • Extended Features: With the full extended feature set, rerankers trained with the averaged perceptron algorithm achieved f-scores of 91.2% on the Berkeley and Brown parses individually, and 91.6% on the combined parses.
  • Overall Improvement: When testing on section 23 (a standard evaluation scenario), a reranker with the extended features trained on the combined output achieved an f-score of 91.49%. This is approximately 0.1% higher than a reranker using only the standard features trained on the Brown parser's output. While seemingly small, this is a statistically significant improvement in this highly competitive field.
  • Ablation Study: The ablation study (Figure 1) shows that removing certain feature super-classes can lead to noticeable drops in performance, confirming the importance of various feature types. Linguistically-informed features were found to be more critical for the combined reranker than for individual parsers.

Limitations and Future Work

  • Marginal Improvement: The authors acknowledge that while the extended feature set offers improvement, the overall gains are not dramatic. They suggest that current reranker features might still be implicitly designed with parsers like the Brown parser in mind, and a truly revolutionary improvement might require further innovation.
  • Feature Set Size: The extended feature set is massive (over 4 million features). While effective, managing and training with such large feature sets can be computationally intensive.
  • Averaged Perceptron vs. L-BFGS: The averaged perceptron algorithm, used for the ablation study, is faster but results in a slightly lower f-score (approximately 0.1% lower) compared to L-BFGS. This suggests that the choice of optimization algorithm can impact final performance.
  • Future Work: The paper implicitly suggests exploring even more sophisticated feature engineering, potentially focusing on features that better bridge the gap between different parsers or capture more complex linguistic phenomena. Further investigation into the interaction between parser characteristics and reranking features would also be valuable.

Summary updated

BibTeX
@inproceedings{johnson2010reranking,
  author = {Mark Johnson and Ahmet Engin Ural},
  title = {{Reranking the Berkeley and Brown Parsers}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2010},
}
Figure