Author: Yusuke Miyao Conference: Proceedings of the 37th Annual Meeting of the Association for Computational Linguistics (1999)
Abstract
This paper addresses the computational bottleneck in high-coverage grammars like Head-Driven Phrase Structure Grammar (HPSG) caused by massive lexical ambiguity. The author proposes an automatic method to "pack" equivalent parts of multiple feature structures into a single representation. By utilizing a specialized unification algorithm with memoization, the system avoids redundant computations, achieving a 6x to 8x speedup in parsing efficiency.
The Problem of Redundancy in Lexical Ambiguity
In linguistic frameworks such as HPSG, words and phrases are represented as complex feature structures, essentially nested attribute-value matrices. Natural language ambiguity often results in a single word having dozens of potential feature structures depending on its context. Traditionally, parsers either process these structures individually—which is highly redundant—or rely on manually defined disjunctions, which are difficult for grammar writers to maintain.
As shown in the lexical entries for "credited" above, while the structures differ in their subcategorization (COMPS) or extraction (SLASH) properties, they share large, identical sub-components. Standard unification algorithms fail to recognize this redundancy, re-calculating the same results for identical parts across different entries.
The Packing and Unification Method
Miyao introduces two primary components to solve this: an Automatic Packing Algorithm and a Packed Unification Algorithm.
1. Automatic Packing
The packing algorithm identifies equivalent sub-parts across a set of feature structures and collapses them into "segments" ($S_i$). Where structures diverge, "disjunctive nodes" ($\Delta_i$) are introduced. A "dependency function" ($D_i$) serves as a map, specifying which segment to select for a particular original structure.
To maintain sound logic, the author introduces a constraint: segments cannot have "inter-segment shared nodes." Reentrancy (structure sharing) is instead managed via the dependency function, ensuring modularity and facilitating efficient caching.
2. Packed Unification with Memoization
When unifying two packed structures, the algorithm uses a segment_stack to manage disjunctions. The core efficiency gain comes from memoization. By storing the results of segment unifications in a table, the algorithm can skip thousands of low-level operations if it encounters segments it has already processed elsewhere.
Experimental Evaluation
The method was evaluated using the XHPSG system, focusing on highly ambiguous lexical entries for two words:
- "credited": 37 distinct entries.
- "walked": 79 distinct entries.
Performance was measured by unifying these entries with grammar rules representing a "left daughter" (e.g., the word "Mary"). The results demonstrated a dramatic reduction in computational overhead. For "credited," the number of low-level node unification calls dropped from 30,929 to just 256. Overall, the packed method was 6.4 times faster for "credited" and 8.4 times faster for "walked."
Conclusion and Future Work
Miyao's approach demonstrates that automatic packing and memoized unification can significantly mitigate the costs of lexical ambiguity in HPSG. While the reduction in node unification is substantial, future work remains in optimizing the management of dependency functions and integrating the algorithm into full-sentence processing. The author notes that further gains are possible, as approximately 25% of segment unification operations remain redundant in the current implementation.
Summary updated