A Context-Sensitive Model for Probabilistic LR Parsing of Spoken Language with Transformation-Based Postprocessing

Tobias RulandCOLING 2000

TL;DR

This paper introduces a probabilistic LR parser for spontaneous speech that incorporates richer context to improve parsing accuracy. To further boost performance, especially for tricky cases, they developed a transformation-based postprocessing step that learns to correct systematic parsing errors. This hybrid approach significantly enhances parsing precision and recall for spoken language translation systems.

What Problem Does This Paper Address?

Spontaneous speech, unlike carefully crafted written text, is messy. It's filled with hesitations, disfluencies, and variations in grammar and pronunciation. This makes it incredibly challenging for natural language processing (NLP) systems, particularly parsers, to accurately determine the grammatical structure of an utterance. Traditional parsers often struggle with the inherent ambiguity and noise in spoken language, leading to low accuracy. The Verbmobil project, a speech-to-speech translation system, highlights this problem: even with a 25% word error rate from speech recognition, the downstream parsing module needs to be robust. The authors aim to improve the accuracy of probabilistic LR parsers for spontaneous speech, specifically addressing the limitations of context-free grammars and the systematic errors that arise from them.

Methods

The core of the paper presents a context-sensitive probabilistic LR parser. Unlike standard probabilistic parsers that might only consider the immediate parser state and look-ahead symbol, this model expands the notion of "context" to include richer information. This can involve elements like the current parser state, look-ahead symbols, subsequent words, and even dialogue act information. The parser uses an A*-search algorithm to efficiently navigate the word graph (output from speech recognition) and find the best-scored parse tree according to acoustic and language model probabilities.

Crucially, the paper introduces a transformation-based postprocessing step. This is a symbolic routine that learns to correct systematic errors made by the probabilistic parser. The learning algorithm identifies pairs of incorrect parser outputs and their corresponding correct human-annotated analyses from a treebank. It then learns "transformations" – essentially Prolog rules – that map incorrect subtrees to correct ones. This process aims to improve the parser's output without retraining the entire probabilistic model, focusing on fixing recurring mistakes.

Datasets

The primary dataset used is the Verbmobil treebank. This treebank contains annotated transliterations of face-to-face dialogues from the "appointment scheduling" and "travel planning" domains. The paper mentions specific sizes for the treebanks used for training:

  • German: 25,881 trees
  • English: 23,140 trees
  • Japanese: 4,534 trees

The authors also mention using a training set of 19,750 German trees and testing on 1,000 unseen German utterances for experiments on context sensitivity.

Key Insights and Ideas

  • Richer Context is Key: Expanding the context considered by a probabilistic LR parser significantly improves its performance on spontaneous speech. This goes beyond simple look-ahead and state information.
  • Postprocessing for Systematic Errors: Probabilistic parsers, even with improved context, make predictable mistakes. A symbolic transformation-based postprocessing step is highly effective at correcting these systematic errors, leading to a substantial boost in accuracy.
  • Balancing Context and Generalization: While more context is beneficial, there's a point where excessive context can lead to overfitting and reduced generalization on unseen data. The authors demonstrate this through experiments with different context sizes.
  • Exact Match vs. Precision/Recall: The paper highlights that even with a relatively low "exact match" rate (where the entire parse tree must be identical to the gold standard), the parser can achieve high precision and recall on parsed utterances. This is attributed to the rich non-terminal symbols in their grammars, which allow for correct semantic interpretation even with minor syntactic variations.

Key Results

  • The context-sensitive parser (using the largest context, K5) consistently outperforms parsers with less context in terms of labeled precision.
  • Labeled recall is also superior with larger contexts, provided the context isn't "overweighted," which can harm generalization.
  • The probabilistic parser achieves high precision/recall on parsed utterances:
  • German: 90.2% Labeled Precision, 83.5% Labeled Recall (all utterances).
  • English: 90.6% Labeled Precision, 78.5% Labeled Recall (all utterances).
  • Japanese: 84.9% Labeled Precision, 63.1% Labeled Recall (all utterances).
  • The transformation-based postprocessing significantly improves the exact match rate:
  • German: Improved by 16% (from 46.3% to 53.8%).
  • English: Improved by 10% (from 55.4% to 61.2%).
  • The mean parsing time per utterance was around 400ms for German/English and 30ms for Japanese on a 166-Mhz Sun Ultra-1 workstation.

Limitations and Future Work

  • Data Sparsity: The authors acknowledge that a treebank of 20,000-30,000 trees is too small to reliably train grammars with millions of entries, leading them to filter infrequent rules.
  • Japanese Data: They note that there wasn't enough training data for Japanese to train the transformation-based postprocessing step, limiting its evaluation for that language.
  • Future Work: The authors suggest extending the transformation learning process to operate on smaller substructures (like single phrases) rather than entire trees. This could further improve generalization and the exact match rate on difficult spontaneous speech utterances.

Summary updated

BibTeX
@inproceedings{ruland2000context,
  author = {Tobias Ruland},
  title = {{A Context-Sensitive Model for Probabilistic LR Parsing of Spoken Language with Transformation-Based Postprocessing}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2000},
}
Figure