Large Margin Hidden Markov Models for Automatic Speech Recognition

Fei Sha, Lawrence K. SaulNeurIPS 2006 · OpenReview

Introduction

In Automatic Speech Recognition (ASR), the standard approach to training Continuous Density Hidden Markov Models (CD-HMMs) relies on the Expectation-Maximization (EM) algorithm to maximize data likelihood. However, maximizing likelihood does not necessarily minimize the metrics we actually care about, such as word or phoneme error rates.

While discriminative training methods like Maximum Mutual Information (MMI) and Minimum Classification Error (MCE) were developed to address this disconnect, they are notoriously difficult to implement. Their objective functions are non-convex, meaning the training process often gets stuck in suboptimal local minima and requires careful initialization and heuristic tuning.

This paper introduces a novel framework for training CD-HMMs by maximizing the "margin" between correct and incorrect classifications, conceptually similar to Support Vector Machines (SVMs). By reparameterizing the model and using a "softmax" trick to handle the exponential number of possible sequences, the authors transform speech recognizer training into a convex optimization problem, effectively eliminating the issue of local minima.

Methodology

The authors build their large margin approach in two main steps, moving from single-frame classification to full sequence modeling.

Decision boundary and margin

1. Large Margin Gaussian Mixture Models (GMMs) First, they reparameterize GMMs using positive semidefinite matrices. This transformation makes the Mahalanobis distance—the core of GMM classification—linear with respect to the model parameters. This linearity allows them to frame the training as a Semidefinite Programming (SDP) problem, ensuring a convex objective for frame-level margin maximization.

2. Sequential Classification (HMMs) Moving from single frames to sequences introduces a combinatorial explosion: there are exponentially many incorrect label sequences for any given audio clip. To solve this, the authors introduce two key innovations:

  • Distance-Weighted Margins: They require the margin between the score of the correct sequence and an incorrect one to be proportional to the number of errors in the incorrect sequence (the Hamming distance). An incorrect sequence with many errors is forced further away from the correct sequence than one with only a single error.
  • The Softmax Trick: Instead of trying to satisfy every individual constraint for exponentially many sequences, they use a differentiable "softmax" (log-sum-exp) upper bound. This collapses the constraints into a single, manageable, and convex objective function that can be solved efficiently using dynamic programming (a variant of the forward-backward algorithm).

Datasets

  • TIMIT: The primary benchmark for the paper, a standard speech corpus used for phonetic recognition. The authors used roughly 1.2 million frames for training.
  • MNIST: Used as a preliminary evaluation for the "Large Margin GMM" component to demonstrate its effectiveness on multiway digit classification before tackling sequential data.

Key Results

By formulating the problem as a convex optimization, the authors ensure that the training converges to the global optimum, a significant advantage over traditional MMI and MCE methods.

The large margin approach significantly outperformed the standard EM baseline on the TIMIT phonetic recognition task. The authors evaluated both frame-based error and string-based (edit distance) error.

String-based error rates on TIMIT
  • String-based Error: As shown in the results, the error rate dropped from 32.7% (EM baseline) to 28.2% (Large Margin Utterance-based) for a model with 8 mixture components.
  • Frame-based Error: Similarly, frame-level error dropped from 41% to 27% under the same conditions.
  • Utterance vs. Frame Training: The "utterance-based" training (which considers the whole sequence) consistently beat "frame-based" training, proving that modeling temporal dependencies during margin maximization is crucial for ASR performance.

Limitations and Future Work

While convex, the optimization remains computationally demanding. The authors had to develop a custom solver using projected subgradients and conjugate gradients because off-the-shelf SDP solvers could not scale to ASR data sizes. Furthermore, the paper focuses strictly on phonetic recognition. Extending this framework to Large Vocabulary Continuous Speech Recognition (LVCSR)—which involves complex language models and vastly larger state spaces—remains a major future challenge. Finally, the current framework assumes a first-order HMM, leaving the exploration of higher-order dependencies within this convex framework as an open area for research.

Summary updated

Abstract

We study the problem of parameter estimation in continuous density hidden Markov models (CD-HMMs) for automatic speech recognition (ASR). As in support vector machines, we propose a learning algorithm based on the goal of margin maximization. Unlike earlier work on max-margin Markov networks, our approach is specifically geared to the modeling of real-valued observations (such as acoustic feature vectors) using Gaussian mixture models. Unlike previous discriminative frameworks for ASR, such as maximum mutual information and minimum classification error, our framework leads to a convex optimization, without any spurious local minima. The objective function for large margin training of CD-HMMs is defined over a parameter space of positive semidefinite matrices. Its optimization can be performed efficiently with simple gradient-based methods that scale well to large problems. We obtain competitive results for phonetic recognition on the TIMIT speech corpus.
BibTeX
@inproceedings{sha2006large,
  author = {Fei Sha and Lawrence K. Saul},
  title = {{Large Margin Hidden Markov Models for Automatic Speech Recognition}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2006},
  url = {https://openreview.net/forum?id=BkWKnPWdZB},
}
Figure