A Tool for Automated Revision of Grammars for NLP Systems

Nanda Kambhatla, Wlodek ZadroznyNAACL 2000

TL;DR

This paper introduces a novel algorithm and tool for automatically revising natural language processing (NLP) grammars to exclude specific unwanted sentences (counter-examples). This significantly reduces the tedious manual effort required to create tightly constrained grammars, leading to improved accuracy in speech understanding systems.

What Problem Does This Paper Address?

Natural language processing (NLP) systems, particularly those dealing with spoken language, rely on grammars to define the set of acceptable utterances and their associated meanings. A key challenge is developing grammars that are general enough to capture a wide range of user inputs but also constrained enough to prevent misinterpretations and errors. Overly general grammars can lead to increased recognition errors and unintended actions, while overly restrictive grammars limit usability. Manually refining these grammars to exclude specific "counter-examples" (sentences that are accepted but shouldn't be) is a time-consuming and difficult process. This paper addresses this challenge by proposing an automated approach to grammar revision.

Methods

The core of the paper presents an algorithm for automatically revising grammars to disallow counter-examples. The process involves:

  • Parse Tree Generation: For each identified counter-example, a parse tree is generated using the current grammar. This tree represents the specific grammar rules used to generate that sentence.
  • Grammar Modification: The algorithm then modifies the production rules of the grammar to invalidate the counter-example. This is achieved by introducing new non-terminals that either exclude the problematic phrase or generate only the problematic phrase, effectively "splitting" the original non-terminal's functionality. This process is iterative, with the revised grammar used for subsequent counter-examples.
  • Handling Recursion: An extension to the algorithm is described to handle grammars with recursive rules. This involves "unrolling" the recursion in the grammar to create an equivalent, non-recursive representation of the parse tree for the counter-example, allowing the modification algorithm to be applied.
  • Grammar Compaction: To mitigate the potential increase in grammar size due to rule modification, the paper also discusses an algorithm for grammar compaction based on the Minimum Description Length (MDL) principle. This algorithm merges and concatenates non-terminals to create a more compact grammar that accepts the same language.
  • Attribute-Value Grammars: The authors also outline an approach to adapt their method for attribute-value grammars by first converting them into equivalent non-attributed grammars, where attributes are encoded in non-terminal names.

Datasets

Not discussed in the paper. The authors mention using grammars from speech understanding systems for telephony banking, stock trading, and directory assistance, and that these grammars initially accepted "around fifty million sentences each." However, specific datasets for training or evaluation are not detailed.

Key Insights and Ideas

  • Automating Tedious Work: The primary insight is that the laborious task of manually refining grammars can be significantly automated, freeing up developers.
  • Counter-Examples as Drivers: Using specific "counter-examples" is a powerful and intuitive way to guide grammar revision, making the process more targeted.
  • Grammar Splitting: The core modification technique of splitting non-terminals to exclude specific phrases is a clever way to precisely constrain grammar rules.
  • MDL for Practicality: The integration of MDL-based grammar compaction is crucial for making the automated revision practical, as naive rule modification can lead to overly complex grammars.

Key Results

The authors report successful application of their tool to constrain overgeneralizing grammars for speech understanding systems. This resulted in:

  • Improved Recognition Accuracy: A 20-30% improvement in sentence recognition accuracy was achieved.
  • Reduced Transaction Errors: In a telephony banking system, the "successful transaction in first try" rate improved from 43% to 71% (a 65% improvement). The average number of wrong tries to achieve a successful answer was reduced from 2.1 to 0.5.
  • Significant Effort Reduction: The main benefit highlighted is the tremendous simplification of the grammar revision process for developers, who interact with an intuitive tool instead of manually editing rules.

Limitations and Future Work

  • Manual Identification of Counter-Examples: While the revision process is automated, the identification of counter-examples still relies on the grammar developer, often drawing from speech recognition error logs or randomly generated sentences.
  • Grammar Size: Without grammar compaction, the automated revision process can lead to an increase in grammar size. The MDL-based compaction addresses this, but the paper acknowledges the need for efficient compaction.
  • Future Work: The authors mention implementing an extension to handle attribute-value grammars, which they have outlined in Section 3. They also suggest that the algorithms are applicable to any domain where grammars are used, implying potential for broader application.

Summary updated

BibTeX
@inproceedings{kambhatla2000tool,
  author = {Nanda Kambhatla and Wlodek Zadrozny},
  title = {{A Tool for Automated Revision of Grammars for NLP Systems}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2000},
}
Figure