A Look at Parsing and Its Applications

Matthew Lease, Eugene Charniak, Mark Johnson, David McCloskyAAAI 2006

TL;DR

This paper provides a high-level overview of the state of statistical parsing in 2006, showcasing how moving beyond simple word-sequence models to structured syntactic models dramatically improves natural language understanding. By combining lexicalized grammars with discriminative reranking and semi-supervised learning, the authors demonstrate that parsers are essential engines for speech recognition, machine translation, and information extraction.

Introduction

At its core, the paper addresses the inherent ambiguity of human language. A sentence like "Jane saw the man with the binoculars" is a classic "garden path" for computers: did Jane use the binoculars to see, or did the man happen to be holding them?

To resolve this, we need parsing—the process of uncovering the recursive structure (syntax) of a sentence. While early NLP relied heavily on "n-grams" (predicting a word based only on the previous few words), these models are "blind" to long-distance relationships and hierarchical structure. The authors argue that for a system to truly "understand" language, it must be able to recover these syntactic relationships accurately and efficiently.

Methodology

The authors describe a sophisticated three-tiered approach to building a high-performance parser:

  1. Lexicalized PCFG (Probabilistic Context-Free Grammar): This is the "generative" foundation. Unlike basic grammars, this model is "lexicalized," meaning it learns the specific behavior of individual words. For example, it learns that the verb "give" usually takes two objects ("give a dog a bone"), whereas "donate" does not.
  2. The Reranker: Since the PCFG might produce several plausible-looking parses, a second-stage "Maximum Entropy" model acts as a critic. It looks at the top $k$ candidates from the PCFG and uses a wider array of complex features (which are too computationally expensive for the first stage) to pick the best one.
  3. Semi-Supervised Learning: To break the "data ceiling" of manually annotated text, the authors used their parser to label 24 million unannotated sentences from news archives. They then retrained the model on this massive "self-labeled" dataset, which significantly boosted performance.

Experimental Setup

  • Penn Treebank (PTB): The gold standard for the field, consisting of roughly two million words from the Wall Street Journal and telephone conversations, manually annotated by linguists.
  • North American News Corpus: A massive dataset of 24 million unannotated sentences used for the semi-supervised learning experiments.
  • HUB-1: A dataset of "read" Wall Street Journal text used to evaluate speech recognition performance.

Key Insights

  • Syntax as a "Prior" for Noisy Channels: The authors frame many NLP tasks (Speech Recognition, Machine Translation, Disfluency Modeling) as "noisy channel" problems. If you have a garbled or foreign input, a parser acts as a powerful "prior" ($P(S)$), telling the system which reconstructed sentences are syntactically "legal" and which are nonsense.
  • The Power of Reranking: Some linguistic features are global and hard to calculate while building a parse tree from the bottom up. By separating the process into "candidate generation" (PCFG) and "selection" (Reranker), the authors get the best of both worlds: efficiency and depth.
  • Self-Training Works: One of the most surprising findings was that a parser can "learn from its own mistakes." By parsing unannotated data and retraining on its own best guesses, the model became more robust and portable across different genres of text.

Key Results

  • Parsing Accuracy: The combined model achieved an f-measure of 92% on the Penn Treebank, a significant benchmark at the time.
  • Speech Recognition: Using a parsing-based language model instead of a standard trigram model reduced the Word Error Rate (WER) on the HUB-1 task from 13.7% to 11.9%. This improvement is reflected in the comparative performance metrics of various models.
Comparison of language models on speech recognition performance (Perplexity and WER).
  • Disfluency Modeling: In cleaning up conversational speech (removing "uhs" and "ums"), the parsing model achieved a 12.5% error reduction over n-gram models.
  • Sentence Compression: The syntactic model allowed for 10% more compression of sentences without losing grammaticality or information compared to non-syntactic methods.

Limitations and Future Work

The authors identify two primary hurdles:

  1. Scalability: While parsing models are smarter than n-gram models, they are also much slower and harder to scale. In 2006, n-grams could be trained on half a billion words, whereas syntactic models were still struggling to process that volume of data efficiently.
  2. The "Web" Challenge: Most parsers were trained on formal news text (WSJ). Moving these models to the messy, informal world of the web or different genres remains a challenge, though the authors suggest semi-supervised learning is a promising path forward.

Future work will focus on scaling these structured models to "very large corpora" to see if the benefits of syntax hold up when billions of words are available.

Summary updated

BibTeX
@inproceedings{lease2006look,
  author = {Matthew Lease and Eugene Charniak and Mark Johnson and David McClosky},
  title = {{A Look at Parsing and Its Applications}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure