A New Predictive Analyzer of English

Hiroyuki MushaCOLING 1986

TL;DR

This paper introduces a novel predictive analyzer for English that enhances Kuno's original model by incorporating five new prediction types. By leveraging a grammar-based approach with extended stack mechanisms, the system aims to mimic human sentence recognition more closely, achieving over 70% success on analyzed articles with just two words of lookahead.

What Problem Does This Paper Address?

Understanding how humans process language, particularly sentence structure, is a fundamental challenge in Natural Language Processing (NLP). When humans read or listen, they don't just passively receive words; they actively predict what's coming next, which helps them resolve ambiguities and build a coherent understanding. Traditional parsers often struggle with this predictive aspect, sometimes requiring extensive backtracking or complex mechanisms. This paper addresses the need for a more human-like predictive parsing system for English that can efficiently resolve syntactic ambiguities by anticipating upcoming words and structures.

Methods

The authors build upon Kuno's predictive analyzer by introducing five new types of predictions:

  • Essential Predictions: These are fundamental predictions necessary for forming a valid sentence structure, directly mapped from Greibach normal form grammar rules.
  • Optional Predictions: These handle postpositional modifiers (like adjectival clauses) that aren't strictly required for a sentence's core structure. A "shifting flag" is introduced to allow for multiple state changes while processing a single word.
  • Bunch Predictions: This allows predicting a set of possible syntactic categories simultaneously, useful for situations where multiple structures could follow, such as after the verb "be."
  • And Stack: A dedicated stack is used to manage coordinate conjunctions (like "and"). Instead of treating "and" as a simple connector, this mechanism allows the parser to predict multiple possible structures (e.g., NP, VP, S) that might follow the conjunction, resolving them based on subsequent words.
  • Insertive Structures: This handles elements that temporarily interrupt the main sentence structure, such as adverbs or prepositional phrases, by suspending the current prediction and pushing new ones onto the stack.

The system utilizes three stacks: the prediction stack, the "and" stack, and an "NP" stack (for handling relative clauses where a noun phrase is temporarily missing). The grammar rules are described using an extended Greibach normal form.

Datasets

Not discussed in the paper. The authors mention analyzing "two kinds of articles," specifically "a manual of a computer software and an abstract article on world economics," but these are not presented as formal datasets with specific characteristics or benchmarks.

Key Insights and Ideas

  • Mimicking Human Prediction is Key: The core idea is that human language understanding relies heavily on prediction, and a successful NLP system should emulate this.
  • Beyond Simple Predictions: The paper demonstrates that a richer set of prediction types (optional, bunch, insertive) is crucial for handling the complexities of natural language syntax, going beyond basic phrase structure rules.
  • The Power of Contextual Stacks: The introduction of specialized stacks (and stack, NP stack) provides elegant solutions for challenging linguistic phenomena like coordination and relative clauses.
  • Minimal Lookahead Suffices: Surprisingly, the research suggests that a relatively small lookahead (two words) is often sufficient for effective predictive parsing, aligning with human cognitive limitations.
  • Grammar as a Predictive Engine: The paper shows how Greibach normal form, with extensions, can serve as a powerful and executable specification for predictive parsing mechanisms.

Key Results

  • High Recognition Rate: The analyzer successfully recognized over 70% of sentences from the analyzed articles.
  • Optimal Lookahead: Two words of lookahead proved to be the critical length for achieving this success rate. Looking one additional word ahead yielded only marginal improvement.
  • Qualitative Success: The system was able to generate appropriate tree structures for sentences involving pending structures (optional predictions, and stack, insertive rules), demonstrating its ability to handle complex syntactic constructions.

Limitations and Future Work

  • Subjectivity in Design: The authors acknowledge that the design is based on the author's "subjective retrospect" of English recognition, suggesting potential for further refinement based on broader linguistic data.
  • Limited Dataset: The analysis was performed on only two articles, which may not be representative of the full diversity of English language.
  • Preference Handling: While preference factors are mentioned, the current treatment is described as "linear ordering" and "trying usual rules before unusual ones," which might be a simplification of human preference mechanisms.
  • Future Work: The paper implicitly suggests further experimentation with larger and more diverse datasets, as well as refining the preference mechanisms. The authors also note that their approach offers a simpler alternative to frameworks like ATNs.

Summary updated

BibTeX
@inproceedings{musha1986new,
  author = {Hiroyuki Musha},
  title = {{A New Predictive Analyzer of English}},
  booktitle = {International Conference on Computational Linguistics},
  year = {1986},
}
Figure