Extremely Lexicalized Models for Accurate and Fast HPSG Parsing

Takashi Ninomiya, Takuya Matsuzaki, Yoshimasa Tsuruoka, Yusuke Miyao, Jun'ichi TsujiiEMNLP 2006 · OpenReview

Abstract

Parsing real-world text using deep linguistic formalisms like Head-driven Phrase Structure Grammar (HPSG) has historically been computationally expensive. This paper demonstrates that for complex grammars, significant gains in both speed and accuracy can be achieved by shifting the probabilistic weight from phrase structures to the words themselves. By utilizing an "extremely lexicalized" model that prioritizes the selection of rich lexical entries (supertags), the authors achieved a 4x speedup and a 2-point improvement in precision and recall over traditional phrase-structure-based models.

Introduction: The Challenge of HPSG Parsing

In HPSG, most syntactic information—such as subcategorization frames—is stored within individual lexical entries rather than general hierarchical rules. Despite this inherent lexicalization, traditional probabilistic models for HPSG parsers are often defined over phrase structures. This approach is slow because the parser must explore a vast search space of hierarchical rules to find the most probable tree.

The authors hypothesize that if the words already contain the majority of the syntactic information, a complex probabilistic model for phrase structures may be redundant. They propose reducing parsing overhead by focusing on supertagging: the process of assigning complex lexical entries to words before the parser begins building a tree.

Methodology: Three Lexicalized Models

The researchers compared three new probabilistic models against a baseline phrase-structure-based model:

  1. Model 1 (Lexical Only): The probability of a parse tree is defined solely as the product of the probabilities of its lexical entries, ignoring phrase-structure rule probabilities entirely.
  2. Model 2 (Lexical + Root): Adds a probability for the "root" node to ensure the final structure represents a complete sentence.
  3. Model 3 (The Hybrid): Combines lexical entry probabilities with traditional phrase-structure probabilities.

To calculate lexical probabilities, the authors employed a Maximum Entropy discriminative model using features such as word trigrams and Part-of-Speech (POS) 5-grams. The parser utilizes an iterative algorithm that starts with a narrow search beam and gradually widens it if no valid parse is found, ensuring maximum efficiency.

Experimental Results

The models were evaluated using the Penn Treebank (PTB) and the Enju 2.1 HPSG grammar. The results confirmed that lexical information is the primary driver of parsing accuracy in HPSG.

F-score vs. Parsing time (ms/sentence) for the previous model and the three proposed lexicalized models.

As shown in the performance graph, Models 1 and 2 were approximately 4 times faster than the previous state-of-the-art model while maintaining comparable accuracy. This suggests that HPSG's strict unification constraints act as a natural filter; even without a complex phrase-structure model, the grammar prevents the construction of nonsensical trees.

Detailed comparison of precision, recall, and average parsing time on Section 23 of the Penn Treebank.

The Hybrid Model (Model 3) achieved the best overall performance, improving both labeled precision and recall by approximately 2.0 percentage points (reaching ~89% F-score). This improvement indicates that while lexical information is dominant, phrase-structure models still provide valuable global context, such as the distance between head words, which local features might miss.

Conclusion

This research proves that for highly lexicalized grammars like HPSG, the lexical entries are so informative that syntactic parsing becomes almost trivial once the correct tags are assigned. By treating supertagging as the primary engine of the probabilistic model rather than just a pre-filter, the authors developed a parser that is both significantly faster and more accurate than previous phrase-structure-centric approaches. Future work may explore how these results generalize to morphologically richer languages or less lexicalized formalisms.

Summary updated

BibTeX
@inproceedings{ninomiya2006extremely,
  author = {Takashi Ninomiya and Takuya Matsuzaki and Yoshimasa Tsuruoka and Yusuke Miyao and Jun'ichi Tsujii},
  title = {{Extremely Lexicalized Models for Accurate and Fast HPSG Parsing}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2006},
  url = {https://openreview.net/forum?id=Z4TwmbsFTvU},
}
Figure