Efficient Heuristic Natural Language Parsing

Christian R. Huyck, Steven L. LytinenAAAI 1993

Introduction

Computational linguistics faces a persistent challenge: the tradeoff between the expressiveness of a grammar and the efficiency of its parsing algorithm. While human language processing is remarkably efficient—operating in roughly linear time—standard algorithms for context-free grammars (CFGs) typically exhibit cubic time complexity ($O(n^3)$). This bottleneck hinders large-scale applications.

This paper proposes a heuristic-driven approach to bridge this gap. Rather than restricting the parser's lookahead or memory to force linearity—which often leads to failure on "garden path" sentences—the authors introduce a robust system that uses heuristics to guide a bottom-up parser. This approach aims for linear average-case performance while maintaining the ability to fall back on general search when heuristics prove insufficient.

The authors implemented their approach within the LINK system, a bottom-up, unification-based grammar parser. Instead of performing an exhaustive search, the parser employs a suite of heuristics to prioritize grammar rules:

  • Lexical Preference: Resolves ambiguity using semantic cues (e.g., verbs like "positioned" expecting specific prepositional phrases).
  • Phrase Creation: A syntactic rule favoring the attachment of new words to the most recent "elementary" constituents.
  • Particle Grabbing: Specifically handles phrasal verbs (e.g., "blow up") to distinguish particles from prepositions.
  • Search Control: A "last resort" mechanism that merges large adjacent phrases when standard heuristic parsing stalls.

Crucially, the system exhibits "graceful degradation." If heuristics lead to a dead end, the parser reverts to an undirected bottom-up chart search, ensuring a valid parse is eventually found, albeit at a higher computational cost.

Experimental Evaluation

The system was evaluated across two domains:

  1. Small Domain: A controlled set of sentences from Ford, Bresnan, and Kaplan (1982) to test psychological validity and baseline heuristic performance.
  2. Open Domain (MUC-4): A corpus of 1,600 news articles regarding terrorist events in Latin America. A random sample of 100 sentences was used to test scalability.

Results and Analysis

In the small domain, the parser demonstrated high efficiency, frequently applying the minimum number of rules necessary to reach a correct parse.

Figure 1: Comparison of the actual number of rules applied versus the theoretical minimum for sentences in a small, controlled domain.

In the more challenging MUC-4 open domain, the system successfully parsed 35% of sentences using heuristics alone. For these cases, the relationship between sentence length and rule applications was nearly linear ($Rules = 4.16 + 2.15 \times \text{length}$).

Even when a full heuristic parse was not achieved, the partial structures built by the heuristics significantly reduced the remaining search space. As shown in Figure 2, unrestricted searches often exceeded 500 rule applications, whereas heuristic-assisted partial parses remained significantly more efficient.

Figure 2: Parsing efficiency on the MUC-4 corpus, comparing heuristic success, partial parses, and unrestricted search.

Discussion and Conclusion

The results suggest that average-case performance, modeled after human linguistic biases, is a viable path toward efficient NLP. The transition from small to open domains highlighted that real-world language requires a vast library of nuanced heuristics, transforming parser design into a complex software engineering task.

Future work will focus on deeper integration of semantic knowledge to resolve noun phrase grouping ambiguities and managing the complex interactions between heuristics as the system's coverage expands.

Summary updated

BibTeX
@inproceedings{huyck1993efficient,
  author = {Christian R. Huyck and Steven L. Lytinen},
  title = {{Efficient Heuristic Natural Language Parsing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure