Optimizing the Computational Lexicalization of Large Grammars

Christian JacqueminACL 1994 · DOI

Abstract

Large-scale natural language parsing often faces a computational bottleneck when linguistic rules are anchored to common words, leading to inefficient rule activation. This paper addresses the "Computational Lexicalization" problem by decoupling linguistic intuition from parser efficiency. By proving the problem is NP-complete and introducing an $O(n^3)$ approximation algorithm based on bin packing heuristics, the author achieves a 2.6x speedup in parsing real-world technical grammars.

Introduction

In Lexicalized Tree Adjoining Grammars (LTAGs), grammatical rules are associated with specific "lexical anchors." While linguists typically anchor rules to the head noun of a phrase (e.g., "alloy" in "metal alloy"), this often creates computational hotspots. In technical domains, a single head noun might be associated with thousands of rules, forcing the parser to evaluate numerous irrelevant paths. This research proposes a method to redistribute these rules across different words in a phrase to balance the parser's workload without altering the underlying grammar.

Methodology

The author frames grammar optimization as a mathematical challenge:

  1. Complexity Analysis: The "Lexicalization of a Grammar" (LG) problem is formally defined and proven to be NP-complete via reduction to the Bin Packing problem. Rules are treated as "items" with weights (complexity), and lexical items serve as "bins."
  2. Approximation Algorithm: To handle large grammars, a two-step $O(n^3)$ heuristic is employed:
  3. Step 1 (Easy Anchoring): Rules are immediately anchored to "rare" words (those appearing in few rules), filling the least-loaded bins first.
  4. Step 2 (Hard Anchoring): For rules containing only common words, a priority system assigns them to the word with the lowest current global weight, prioritizing rules with the fewest alternative anchors.
  5. Weighting Metrics: Rules are weighted based on structural complexity (e.g., node count), aiming for a uniform distribution across the vocabulary.

Key Results

The algorithm was tested on massive metallurgy grammars (up to 71,623 rules). The optimization significantly flattened the distribution of computational load.

Distribution of rule weights per lexical item using standard linguistic anchoring (max weight ~240).

As shown in the figure above, the standard linguistic approach resulted in a maximum weight of 241 for certain words. After applying the optimization algorithm, this maximum load dropped to just 34.

Distribution of rule weights after optimization (max weight ~34).

This load balancing led to a 2.6x increase in parsing speed, as the parser could filter out 57% more rules than the standard approach. Furthermore, the algorithm is highly scalable, processing the largest grammar in under 200 seconds on 1994-era hardware.

Conclusion

By treating lexicalization as a bin-packing problem, this work demonstrates that computational efficiency can be achieved without sacrificing linguistic integrity. Future improvements could involve using corpus frequency data to further refine rule weights and dynamic cost metrics based on actual parser performance.

Summary updated

BibTeX
@inproceedings{jacquemin1994optimizing,
  author = {Christian Jacquemin},
  title = {{Optimizing the Computational Lexicalization of Large Grammars}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1994},
  doi = {10.3115/981732.981759},
}
Figure