TL;DR
This paper tackles the computational inefficiency of unification-based parsing, a powerful framework for natural language processing. The authors propose and empirically validate two key strategies: using "medium-grained" phrase structure rules and employing "late unification." Together, these methods significantly speed up parsing without sacrificing linguistic expressiveness or maintainability.
What Problem Does This Paper Address?
Unification-based frameworks, like HPSG, offer a theoretically rich way to combine linguistic information (syntax, semantics, pragmatics). However, the core operation, unification, can be computationally expensive, hindering the development of large-scale practical NLP systems. Existing research has focused on optimizing CFG parsing algorithms or graph unification algorithms. This paper, however, zeroes in on two less-explored but crucial aspects: the granularity of phrase structure rules and the interleaving of CFG parsing with unification. The challenge is to find a sweet spot that balances computational cost, linguistic coverage, and ease of maintenance.
Methods
The paper introduces and evaluates two main strategies:
- Medium-Grained Phrase Structure Rules: Instead of extremely coarse rules that push most linguistic constraints into feature descriptions (like in HPSG), or very fine-grained rules that lead to an unmanageable number of rules, the authors advocate for "medium-grained" rules. These rules incorporate more morpho-syntactic information directly into the phrase structure rules themselves. This means fewer, but more informative, rules, aiming to reduce the burden on unification while keeping the grammar manageable.
- Late Unification: This strategy delays the computationally intensive unification process until a complete CFG parse is generated. In contrast, "early unification" (or step-by-step) evaluates feature descriptions at each rule invocation. Late unification aims to avoid unnecessary unification operations on irrelevant sub-parses, saving computational resources.
The authors implemented these strategies within an active chart parser using a Typed Feature Structure Propagation (TFSP) parser.
Datasets
The experiments were conducted using 85 sample sentences selected from ATR's dialogue corpus, specifically from the "secretarial service of an international conference" task domain. The average sentence length was 11.0 characters, with a maximum of 28 characters. The grammars used were developed for Japanese.
Key Insights and Ideas
- The Granularity-Unification Trade-off: The paper highlights a critical trade-off: extremely coarse rules reduce the number of CFG rules but increase unification complexity (due to extensive disjunctions in feature descriptions). Conversely, very fine-grained rules lead to an explosion in CFG rules. Medium-grained rules offer a balanced solution.
- Late Unification Pays Off: Delaying unification until the end of CFG parsing significantly reduces redundant computations. This is particularly effective when combined with more informative phrase structure rules.
- Grammar Maintainability vs. Efficiency: The authors demonstrate that it's possible to achieve both efficiency and maintainability. Medium-grained rules, while increasing the number of rules compared to extremely coarse ones, are still manageable and lead to a more efficient system.
- Japanese Specifics: The work leverages the structure of Japanese, particularly verb phrases, to illustrate how morpho-syntactic information can be effectively encoded in medium-grained rules.
Key Results
The experimental results are compelling:
- Medium-grained rules with early unification were 1.7 times faster than coarse-grained rules with early unification.
- Late unification with medium-grained rules was 2.0 times more efficient than early unification with medium-grained rules.
- The combination of medium-grained rules and late unification resulted in a parser that was 3.5 times faster on average than the previous system using coarse-grained rules and early unification.
The paper also shows that the parsing time for late unification appears to be polynomial in sentence length, whereas early unification's time can vary much more irregularly.
Limitations and Future Work
The authors acknowledge that while late unification avoids unnecessary copies of DAGs for irrelevant subparses, it might still encounter infinite loops if feature descriptions are ignored. To mitigate this, they force evaluation of rules that could cause loops.
Future work suggested includes:
- Automatic Transformation of Rules: Developing techniques to automatically convert disjunctions in feature descriptions into atomic phrase structure rules, further enhancing efficiency without sacrificing maintainability.
- Feature-Sensitive Lazy Unification: Separating features for constraint-checking (e.g., syntactic) from those for information propagation (e.g., semantic) to prune irrelevant subparses more efficiently.
- Parallel Implementation: Leveraging the separation of CFG parsing and unification in the late unification strategy for parallel processing, which could lead to further speedups.
Summary updated