Using Integer Linear Programming for Detecting Speech Disfluencies

Kallirroi GeorgilaNAACL 2009

TL;DR

This paper introduces a novel two-stage approach for detecting speech disfluencies, like repetitions and revisions, by combining state-of-the-art classifiers with Integer Linear Programming (ILP). Their method significantly improves disfluency detection accuracy, especially when training data is scarce, with minimal computational overhead.

What Problem Does This Paper Address?

Spontaneous speech is rife with disfluencies – hesitations, repetitions, and self-corrections – which pose a significant challenge for natural language processing (NLP) systems. These disfluencies disrupt the flow of information, making it harder for tools like parsers or information extractors, which are typically trained on clean, written text, to function effectively. While various methods exist for detecting these speech anomalies, this paper aims to improve their accuracy and robustness, particularly in low-data scenarios, by leveraging the constraint-satisfaction power of Integer Linear Programming.

Methods

The proposed technique employs a two-stage process.

Stage 1: Initial Classification: The first stage involves using existing, state-of-the-art speech disfluency detection models. The authors experimented with three types:

  • Hidden-Event Language Models (HELMs): Statistical models that capture sequential patterns in speech.
  • Maximum Entropy (ME) models: Probabilistic models that assign probabilities to different tags based on features.
  • Conditional Random Fields (CRFs): Discriminative models that consider the entire sequence of tags.

These classifiers are trained on lexical features and, during testing, each word in an utterance is assigned a set of possible disfluency labels (e.g., "outside disfluency," "beginning of edit," "interruption point").

Stage 2: Integer Linear Programming (ILP) Refinement: The core novelty lies in the second stage, where ILP is used to refine the initial classifications. ILP is a mathematical optimization technique that finds the best solution to a problem by maximizing or minimizing a linear objective function subject to a set of linear constraints. In this context:

  • The objective function aims to maximize the overall probability of the utterance's tag sequence, based on the probabilities assigned by the initial classifiers.
  • The constraints encode linguistic knowledge about how disfluencies typically occur. These include:
  • Local constraints: Each word can only have one tag.
  • Global constraints: Rules about allowed tag transitions between consecutive words (e.g., an "interruption point" must be followed by a "beginning of edit" or an "outside disfluency" tag).
  • Pattern-based rules: The authors also incorporated specific rules to capture common disfluency patterns, such as repeated words or sequences involving pronouns and discourse markers.

By formulating these rules as ILP constraints, the system can enforce linguistic consistency and improve the accuracy of the final tag assignments.

Datasets

The primary dataset used is the Switchboard corpus, a widely used resource for speech disfluency research. The authors transformed its annotations into a format suitable for their task, defining tags like "BE" (beginning of edit), "IP" (interruption point), and "IE" (inside edit). They used portions of this corpus for training, development, and testing, and also explored the impact of varying training set sizes (25%, 50%, 75%, 100%).

Key Insights and Ideas

  • ILP as a powerful constraint enforcer: The paper demonstrates that ILP can effectively enforce linguistic rules and patterns that are difficult to capture solely with individual classifiers. This leads to more coherent and accurate disfluency tagging.
  • Significant gains in low-data regimes: The most striking finding is that ILP provides substantial performance improvements, particularly when training data is limited. This is crucial for real-world applications where obtaining large, annotated datasets can be prohibitively expensive.
  • Negligible computational cost: Applying ILP during testing adds minimal processing time, making it a highly efficient way to boost performance.
  • Novel ILP formulation: While the two-stage approach isn't entirely new, the specific formulation of the ILP objective function and constraints for disfluency detection is presented as novel.

Key Results

The ILP-enhanced models (referred to as "ILP" and "ILP-") consistently outperformed their baseline counterparts across all tested classifiers (HELMs, ME, and CRFs).

  • Error Rate Reduction: For example, with the ME model, the error rate for detecting the "BE" tag dropped from 52.6% (plain ME) to 36.3% (ME ILP) and 33.7% (ME ILP-). Similar improvements were observed for the "IP" tag.
  • Low-Data Performance: When trained on only 25% of the data, the ILP-enhanced HELM and ME models performed better than the plain HELM and ME models trained on 100% of the data.
  • CRF Performance: While CRFs generally performed better than HELMs and ME, the ILP enhancement still yielded improvements, though sometimes smaller. The "ILP-" variant (using only general ILP constraints and short-context rules) showed a slight edge over the full "ILP" model for CRFs.

Limitations and Future Work

  • Limitations: The paper primarily focuses on lexical features. The authors acknowledge that incorporating acoustic and prosodic features could further enhance performance. The current ILP formulation also doesn't explicitly handle all types of disfluencies, such as filled pauses or discourse markers, as "editing terms."
  • Future Work: The authors plan to:
  • Experiment with acoustic and prosodic features.
  • Detect disfluencies directly from speech recognition output, rather than relying on transcribed text.
  • Explore more complex disfluency patterns and editing terms.

Summary updated

BibTeX
@inproceedings{georgila2009using,
  author = {Kallirroi Georgila},
  title = {{Using Integer Linear Programming for Detecting Speech Disfluencies}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
}
Figure