An HPSG-to-CFG Approximation of Japanese

Bernd Kiefer, Hans-Ulrich Krieger, Melanie SiegelCOLING 2000

TL;DR

This paper introduces a method to convert complex Head-Driven Phrase Structure Grammars (HPSGs) into simpler Context-Free Grammars (CFGs). This approximation allows for faster initial filtering of sentences, significantly reducing the computational load for parsing, especially for languages like Japanese with rich ambiguity.

What Problem Does This Paper Address?

Parsing natural language with highly expressive grammars like HPSGs can be computationally very expensive. HPSGs, while powerful for capturing linguistic nuances, often lead to complex feature structures and a large search space. This makes real-time applications, such as machine translation of spoken dialogues, challenging. The authors aim to bridge this gap by creating a computationally cheaper CFG that closely approximates the behavior of an HPSG, enabling a two-stage parsing approach: a fast CFG filter followed by a more detailed HPSG analysis.

Methods

The core of the paper is an approximation algorithm that iteratively refines feature structures to reach a "fixpoint." This process involves:

  • Lexicon Abstraction: Generalizing lexicon entries by removing word-specific information using a "lexicon restrictor."
  • Rule Instantiation and Restriction: Applying HPSG rules to these abstracted entries to create initial derivation structures. A "rule restrictor" then removes information that is solely present in the daughters of a rule, ensuring that the set of derivable structures remains the same (due to HPSG's Locality Principle).
  • Iterative Fixpoint Construction: Repeating the instantiation and restriction process. In each iteration, the newly generated feature structures are added to the set. The process stops when no new structures are generated or removed, indicating a fixpoint.
  • CFG Generation: Once the fixpoint is reached, the resulting complex feature structures are treated as non-terminal symbols in a CFG. The HPSG rules are then instantiated one last time with these fixpoint structures to generate the final CFG productions.

The authors also highlight several optimizations for practical implementation:

  • Reduced Unifications: Splitting the set of feature structures to avoid redundant computations.
  • Rule Filter and Quick-Check: Pre-computing rule applicability and using "quick-check vectors" to efficiently identify likely unification failures.
  • Subsumption-Based Set Union: Adding new structures only if they are not subsumed by existing ones, and removing subsumed structures to keep the set of feature structures manageable.

Datasets

The paper uses a Japanese HPSG grammar developed for the Verbmobil project. This grammar consists of 43 rule schemata, 1,208 types, and a test lexicon of 2,781 entries. The lexicon restrictor maps these entries to 849 lexical abstractions. No new benchmarks are introduced; the focus is on approximating an existing grammar.

Key Insights and Ideas

  • The Power of Approximation: The core idea is that a CFG can serve as a highly effective "cheap filter" for more complex grammars. This is crucial for real-time systems.
  • Fixpoint Iteration as a Generalization Strategy: The iterative process of abstraction and restriction naturally leads to a generalized set of structures that capture the essence of the HPSG without infinite recursion.
  • The Role of Restrictors: Both lexicon and rule restrictors are vital for managing complexity. Removing semantic information (like the CONTENT feature) is particularly effective in preventing infinite growth and collapsing redundant rules.
  • Optimizations are Crucial: The described optimizations (quick-check, subsumption) are not just theoretical niceties but are essential for making the approximation algorithm computationally feasible for large grammars.

Key Results

  • The approximation process for the Japanese HPSG reached a fixpoint in 5 iteration steps, resulting in 10,058 feature structures.
  • The generated CFG produced 19,198,592 productions, which is only 1.26% of the theoretical maximum possible productions (over 1.5 billion). This demonstrates a significant reduction in grammar size.
  • The optimization techniques (quick-check, subsumption) were highly effective, detecting over 98% of failing subsumptions early and nearly 100% of failing unifications.
  • The authors suggest that this approach can drastically reduce the workload on the HPSG side in a parsing pipeline.

Limitations and Future Work

  • Restrictor Choice: The authors acknowledge that the choice of restrictor is critical and can significantly impact the size of the fixpoint and the resulting CFG. They are unsure if their chosen restrictor is optimal.
  • Computational Cost: While optimized, the fixpoint computation still took approximately 27.3 CPU hours for the Japanese grammar.
  • Future Work: The authors are implementing a CF parser capable of handling the generated large set of CF rules. They also express hope that these results can be carried over to other languages, citing experiments with an English Verbmobil grammar.

Summary updated

BibTeX
@inproceedings{kiefer2000hpsg,
  author = {Bernd Kiefer and Hans-Ulrich Krieger and Melanie Siegel},
  title = {{An HPSG-to-CFG Approximation of Japanese}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2000},
}
Figure