Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars

Jason Eisner, Giorgio SattaACL 1999 · OpenReview

Abstract: Several recent stochastic parsers use bilexical grammars, where each word type idiosyncratically prefers particular complements with particular head words. We present $O(n^4)$ parsing algorithms for two bilexical formalisms, improving the prior upper bounds of $O(n^5)$. For a common special case that was known to allow $O(n^3)$ parsing (Eisner, 1997), we present an $O(n^3)$ algorithm with an improved grammar constant.

Introduction: The Efficiency Tax of Lexicalization

In traditional Context-Free Grammars (CFGs), rules are generic—for instance, a Verb Phrase (VP) consists of a Verb (V) and a Noun Phrase (NP). However, natural language is inherently "bilexical": specific words exhibit strong preferences for specific partners. A verb like convened expects an object like meeting or assembly, rather than apple or cloud.

To capture these nuances, researchers utilize bilexical grammars, where every grammatical category is lexicalized (tagged with a specific head word). While this significantly improves parsing accuracy, it introduces a "state space explosion." Because the number of possible rules scales with the vocabulary size, standard parsing algorithms like CKY become prohibitively slow, often running in $O(n^5)$ or $O(n^6)$ time. Historically, researchers bypassed this complexity through "pruning" (discarding low-probability paths), which risks search errors and suboptimal parses.

Algorithmic Innovation: Decoupling and Two-Step Attachment

Jason Eisner and Giorgio Satta address this complexity by restructuring the dynamic programming "chart" used in parsing. Their primary innovation involves a clever decoupling of constituent boundaries.

1. Sub-constituent Derivations

Standard CKY parsing combines two completed constituents into a larger one. This requires tracking four indices: the start, the end, and the split point of the two children. This four-index requirement, combined with the head-word indices, leads to high complexity. The authors propose using "incomplete" items—sub-derivations that represent partially formed constituents.

2. Two-Step Attachment

Instead of attaching a dependent word to a head word in a single $O(n^5)$ step, the process is broken into two $O(n^4)$ steps. First, an intermediate item is created where the head has "accepted" a dependent but has not yet finalized its own phrase. By creating an intermediate state that "forgets" the far boundary of a dependent phrase at the moment of attachment, the algorithm saves a factor of $n$ in its nested loops.

3. The "Split" Optimization

For the common case where a word's left-side dependents do not interact with its right-side dependents (the "split" property), the authors demonstrate an $O(n^3)$ complexity. This matches the speed of standard, non-lexicalized CFG parsing, proving that lexicalization does not inherently necessitate a performance penalty.

Inference rules for the $O(n^3)$ split grammar parsing algorithm, showing the START, ATTACH-LEFT, and ATTACH-RIGHT operations.

Key Results and Insights

  • General Bilexical CFGs: The upper bound for parsing was improved from $O(n^5)$ to $O(n^4)$.
  • Head Automaton Grammars (HAGs): The authors proved that HAGs can be translated into bilexical CFGs, allowing them to be parsed in $O(n^4)$, an improvement over previous $O(n^5)$ implementations.
  • Optimized Split HAGs: A new $O(n^3)$ algorithm was introduced with a significantly smaller "grammar constant" (the number of non-terminals), making it faster in practical applications.
  • Memory Efficiency: The algorithms maintain a space complexity of $O(n^3)$, which remains manageable for modern computational hardware.

Conclusion and Future Directions

While $O(n^4)$ is a substantial improvement, it remains slower than the $O(n^3)$ required for basic CFGs, suggesting that for extremely long sentences, further optimizations or heuristic pruning may still be required. The authors also suggest that these techniques could be extended to Lexicalized Tree Adjoining Grammars (LTAGs), potentially reducing their complexity from $O(n^8)$ to $O(n^7)$.

Ultimately, this work demonstrates that by carefully managing how head-dependent relationships are tracked in dynamic programming, high-accuracy lexicalized parsing can be made significantly more practical for real-world natural language processing tasks.

Summary updated

Abstract

Several recent stochastic parsers use bilexical grammars, where each word type idiosyncratically prefers particular complements with particular head words. We present O(n 4 ) parsing algorithms for two bilexical formalisms, improving the prior upper bounds of O(n 5 ). For a common special case that was known to allow O(n 3 ) parsing (Eisner, 1997), we present an O(n 3 ) algorithm with an improved grammar constant.
BibTeX
@inproceedings{eisner1999efficient,
  author = {Jason Eisner and Giorgio Satta},
  title = {{Efficient Parsing for Bilexical Context-Free Grammars and Head Automaton Grammars}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1999},
  url = {https://openreview.net/forum?id=rJ4J6heu-B},
}
Figure