Ambiguity Packing in Constraint-based Parsing Practical Results

Stephan Oepen, John CarrollNAACL 2000

TL;DR

This paper introduces a novel, efficient algorithm for "ambiguity packing" in constraint-based parsing, specifically for HPSG grammars. By packing equivalent or subsumed parse structures, they demonstrate a significant reduction in parsing complexity and time, making wide-coverage HPSG grammars more practical for real-world applications.

What Problem Does This Paper Address?

Natural language is inherently ambiguous, meaning a single sentence can have multiple valid interpretations. Parsing systems need to handle this ambiguity efficiently. "Ambiguity packing" is a technique where multiple, similar analyses of a linguistic segment are represented as a single entity, preventing redundant computation. Traditional ambiguity packing methods work well for context-free grammars by checking for identical "categories." However, for more powerful HPSG (Head-Driven Phrase Structure Grammar) grammars, which use complex, typed feature structures, checking for equivalence or subsumption is computationally expensive. This paper addresses the challenge of applying efficient ambiguity packing to large-scale HPSG grammars, which are increasingly used in practical systems like speech translation, and investigates whether the benefits seen in simpler grammars can be realized here.

Methods

The core contribution is a new, linear-time, bidirectional subsumption test for typed feature structures. This algorithm, detailed in Figure 1, efficiently checks if two feature structures are equivalent or if one subsumes the other. It uses temporary pointers and a generation counter to track intermediate results and detect reentrancies, achieving linear time complexity with respect to the size of the feature structures.

The paper then integrates this algorithm into a bottom-up chart parsing algorithm. This parser employs "proactive" and "retroactive" packing strategies.

  • Proactive packing: A new parse edge is packed into an existing one if it's equivalent or subsumed.
  • Retroactive packing: If a new edge subsumes an existing one, the existing edge and its derivatives are invalidated ("frosted" or "frozen") and the new edge takes over. This is more complex as it requires careful management of invalidated derivations.

The algorithm is designed to be integrated with arbitrary bottom-up chart parsing strategies with minimal overhead.

Datasets

The evaluation was performed using the LinGO grammar, a large, broad-coverage HPSG of English developed at CSLI Stanford. The test set consisted of 2,100 sentences extracted from VerbMobil corpora of transcribed speech, with input lengths ranging from 1 to 20 words. A subset of these sentences (around 1,000 each) was used for experiments with different grammar restrictors, divided into two groups based on sentence length (1-10 words and >10 words).

Key Insights and Ideas

  • Linear-time subsumption is achievable: The paper demonstrates that efficient, linear-time subsumption checking for complex typed feature structures is possible, overcoming a major hurdle for HPSG parsing.
  • Packing benefits HPSG: Ambiguity packing, including retroactive packing, is not only applicable but highly beneficial for large-scale HPSG grammars, significantly reducing chart size and parsing time.
  • Retroactive packing is complex but valuable: While managing invalidated derivations in retroactive packing is non-trivial, it leads to more compact parse forests.
  • Grammar restrictors matter: The choice of grammar restrictor (how much semantic information is included during parsing) significantly impacts packing efficiency and parsing performance. "Partial semantics" appears to offer the best trade-off.
  • Equivalence is common: A significant portion of packings involve equivalent feature structures, suggesting that unpacking could be simplified by leveraging this.

Key Results

  • Chart size reduction: Packing reduces the number of passive edges by a factor of more than three on average, and in some cases by a factor of 30 or more. The rate of increase of chart items with sentence length is greatly diminished.
  • Speedup: Compared to a non-packing parser, the packing scheme achieves a "very significant speedup," even when unpacking time is included. For example, with 6 PP modifiers, the number of packed nodes increased by a factor of 18.6, while parsing time was reduced by a factor of 1.460 compared to the unpack time.
  • Grammar restrictor impact: Using "partial semantics" resulted in minimal chart size and parsing time, outperforming "no semantics" (which led to overgeneralization) and "full semantics" (which was less effective due to increased subsumption testing costs).

Limitations and Future Work

  • Retroactive packing management: The paper acknowledges the complexity of managing invalidated derivations in retroactive packing and ensuring chart consistency.
  • Unpacking optimization: The authors plan to enhance the unpacking phase to leverage the observed high number of equivalence packings, which should reduce the work required.
  • Selective unpacking: For applications that don't need the full parse forest, a selective, incremental unpacking procedure needs to be defined.
  • Prioritized parsing: The authors aim to investigate how their packing approach can be integrated with prioritized best-first parsing strategies, which are favored by applications like VerbMobil.
  • Grammar development: Future work will also consider developments in grammar and semantic theory that might further simplify the packing and unpacking process.

Summary updated

BibTeX
@inproceedings{oepen2000ambiguity,
  author = {Stephan Oepen and John Carroll},
  title = {{Ambiguity Packing in Constraint-based Parsing Practical Results}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2000},
}
Figure