Positive Results for Parsing with a Bounded Stack using a Model-Based Right-Corner Transform

William SchulerNAACL 2009

TL;DR

This paper introduces a novel "model-based" right-corner transform that maps probabilistic grammars to a bounded-stack parsing framework (HHMMs). This approach allows for a fair comparison between bounded and unbounded parsers, demonstrating that a bounded-stack parser using the transformed grammar significantly outperforms an unbounded-stack CKY parser on the same underlying model.

What Problem Does This Paper Address?

Statistical parsing, a core task in Natural Language Processing (NLP), aims to determine the syntactic structure of sentences. Traditional methods like CKY parsing often assume an "unbounded stack," meaning they can theoretically handle any level of syntactic complexity. However, human language processing is known to be constrained by working memory limitations. This paper questions whether the unbounded assumption in standard parsers is computationally wasteful and if it might be hindering performance by attempting to model syntactic structures beyond human cognitive capacity. The authors propose that by explicitly modeling these memory constraints, parsing accuracy can be improved.

Methods

The core innovation is a "model-based" right-corner transform. Unlike previous tree-based transforms, this method transforms the probabilistic grammar itself, rather than individual parse trees. This ensures a fair comparison between bounded and unbounded parsers derived from the same underlying probabilistic model.

The paper leverages Hierarchic Hidden Markov Models (HHMMs), which are designed to mimic bounded-memory pushdown automata. The right-corner transform is applied to the grammar rules to create direction-specific rules (distinguishing left and right children) and then depth limits are enforced. This process effectively maps an unbounded PCFG to a bounded-stack HHMM. The probabilities are then calculated by marginalizing out irrelevant information from the original grammar.

Datasets

The Wall Street Journal (WSJ) Treebank was used for evaluation. Specifically, sections 2-21 were used for training the PCFG model, and sections 22-24 (with sentences longer than 40 words) were used for evaluation.

Key Insights and Ideas

  • Human Memory as a Constraint: The paper strongly suggests that standard parsing models might be "wasting probability mass" by assuming unbounded memory, which doesn't reflect human cognitive limits.
  • Model-Based Transformation: Transforming the grammar itself, rather than just trees, is crucial for a fair comparison between bounded and unbounded parsing models. This ensures that differences in performance are due to the stack bound, not other model variations.
  • Right-Corner Transform's Role: The right-corner transform, when applied to grammars and then bounded, effectively reconfigures the parsing problem to be more amenable to limited memory.
  • Long Sentences Benefit Most: The performance gains from bounded-stack parsing are most pronounced on longer sentences, where the complexity of unbounded parsing becomes a more significant issue.

Key Results

The paper reports that a bounded-stack HHMM parser, derived from a right-corner transformed grammar, significantly outperforms an unbounded-stack CKY parser using the original grammar. Specifically, on sentences longer than 40 words from the WSJ Treebank, the bounded PCFG model achieved approximately a 0.15% reduction in error compared to the original PCFG (p < 0.1 via a one-tailed pairwise t-test). This suggests that the probability mass wasted by unbounded parsing on long sentences has a tangible impact on accuracy.

Limitations and Future Work

The authors acknowledge that the correctness of their probability distributions relies on terms canceling out, which is guaranteed for parsing with an infinite beam. For practical parsing with finite beams, this might not hold.

Future work could explore applying this model-based transform to other types of grammars or parsing frameworks. The paper also hints at the potential for this approach to better model incremental parsing phenomena like coreference or disfluency, which are naturally handled by bounded-stack models. The authors suggest that further investigation into the "richer dependencies" of HHMMs compared to standard PCFGs could also yield insights.

Summary updated

BibTeX
@inproceedings{schuler2009positive,
  author = {William Schuler},
  title = {{Positive Results for Parsing with a Bounded Stack using a Model-Based Right-Corner Transform}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
}
Figure