Introduction
Natural language processing systems often struggle with the inherent messiness of spontaneous speech. Human utterances frequently include stutters, false starts, and filler words that deviate from formal grammar. Traditional parsers are brittle; a single unrecognized word or a slight grammatical deviation can cause the entire parsing process to fail.
The GLR* parser, an evolution of the Generalized LR parser, addresses this by allowing the system to skip over unrecognizable words to find the largest possible subset of the input that conforms to the grammar. While this "robustness" prevents total failure, it introduces significant ambiguity. By allowing word skipping, a single sentence can yield dozens of "maximal" partial parses. The challenge lies in determining which of these interpretations most accurately captures the speaker's intent.
The Integrated Heuristic Scheme
To resolve this ambiguity, this paper introduces an integrated heuristic scheme that assigns a penalty score to every potential parse. The system selects the parse with the lowest total penalty. This scheme integrates four primary features:
- Skipped Words: Each skipped word incurs a penalty (ranging from 0.95 to 1.05). Notably, the system applies higher penalties to words skipped later in a sentence. This heuristic accounts for the fact that "noise" like false starts usually occurs at the beginning of an utterance.
- Substituted Words: To mitigate speech recognition errors, the parser can substitute an input word with a candidate from a pre-defined list, incurring a small penalty.
- Fragmentation: The scheme favors cohesive parse trees. Every additional fragment required to cover the input increases the total penalty score.
- Statistical Disambiguation: A probabilistic module based on the Briscoe and Carroll framework assigns probabilities to "shift" and "reduce" actions. These are converted into penalties using the formula: $penalty = 0.1 \times (-\log_{10}(pscore))$.
Additionally, a Parse Quality Heuristic acts as a final filter, classifying the chosen parse as "good" or "bad" based on its total penalty relative to the sentence length.
Evaluation and Results
The system was evaluated using the ATIS (Air Travel Information System) dataset, consisting of spontaneous speech queries. The performance of the standard GLR parser was compared against two versions of the robust GLR parser: one using a simple heuristic (GLR (1)) and one using the new integrated heuristic scheme (GLR* (2)).
The results, summarized in the table above, demonstrate a significant improvement in robustness. The GLR* system successfully parsed 58 sentences that the standard GLR parser found completely unparsable, increasing the parsable rate from 51.7% to 95.8%.
More importantly, the integrated heuristic (GLR* (2)) improved the quality of the selected parses. It correctly identified "good" parses in 75% of cases, compared to 70% for the simple heuristic. The integrated approach also reduced the rate of "bad" parses from 25.8% to 20.8%.
Conclusion
The findings suggest that simply maximizing word coverage is insufficient for robust parsing. A multi-dimensional heuristic approach—combining word skipping patterns, fragmentation, and statistical probabilities—is essential for navigating the ambiguity of partial parses. While the current weights for these heuristics were manually tuned, future work could involve automated optimization and the integration of domain-specific semantic analysis to further refine parse selection.
Summary updated