A DTW-based dissimilarity measure for left-to-right hidden Markov models and its application to word confusability analysis

Qiang Huo, Wei LiInterspeech 2006

TL;DR

This paper introduces a novel Dynamic Time Warping (DTW) based dissimilarity measure for Hidden Markov Models (HMMs) used in speech recognition. By approximating the Kullback-Leibler divergence between Gaussian Mixture Models (GMMs) representing HMM states, they create a computationally efficient way to compare HMMs, which they then apply to effectively identify confusable syllables in Mandarin Chinese.

What Problem Does This Paper Address?

Measuring the dissimilarity between Hidden Markov Models (HMMs) without running costly recognition experiments is a long-standing challenge in speech recognition. This is crucial for applications like identifying confusable words or syllables, which helps in vocabulary selection and improving system robustness. Traditional methods for calculating HMM dissimilarity, like using Monte Carlo simulations to approximate Kullback-Leibler Divergence (KLD), are computationally expensive and impractical for real-time applications. The paper aims to bridge this gap by proposing an efficient and theoretically grounded dissimilarity measure for left-to-right HMMs, specifically for continuous density GMM-based HMMs (CDHMMs).

Methods

The core of the paper is a DTW-based dissimilarity measure for left-to-right CDHMMs. The process involves:

  1. Representing HMM States as GMMs: Each state in an HMM is modeled by a Gaussian Mixture Model (GMM), where the GMM parameters (weights, means, and covariance matrices) capture the observation densities.
  2. Local Distortion Score: The key innovation lies in defining the local distortion score between two GMMs (representing states from two different HMMs). Instead of exact KLD, which is intractable for GMMs, the authors explore and compare several approximate KLD methods. They settle on a "matching-based approximation" method from prior work [5] as it offers a good balance between accuracy and computational efficiency.
  3. DTW for HMM Dissimilarity: Dynamic Time Warping (DTW) is then applied to the sequences of GMMs representing two HMMs. DTW finds the optimal alignment between the two sequences, allowing for variations in their lengths, and uses the GMM dissimilarity scores as the local costs. The final DTW path cost serves as the overall HMM dissimilarity measure.
  4. Application to Syllable Confusability: The proposed HMM dissimilarity measure is then used to build a syllable dissimilarity matrix. This matrix is used in an agglomerative hierarchical clustering procedure to identify groups of confusable syllables.

Datasets

The paper does not explicitly mention specific datasets for training the HMMs used in the confusability analysis. However, it states that the HMMs were trained using the HTK3.0 toolkit on a large corpus of Putonghua speech data from multiple sources (HKU96, HKU99, 863, and MSRA), totaling approximately 180 hours from 330 speakers. For evaluation, they used 33021 utterances from 20 speakers from the isolated syllable part of the HKU96 Putonghua corpus.

Key Insights and Ideas

  • DTW as a Natural Fit for Sequential GMM Dissimilarity: The paper elegantly frames the problem of comparing HMMs (which are sequences of states, each represented by a GMM) as a sequence alignment problem, making DTW a suitable and intuitive tool.
  • The Importance of Efficient GMM Dissimilarity: The authors highlight that the practicality of HMM dissimilarity measures hinges on efficient and accurate approximations of KLD between GMMs. Their comparative study of approximation methods is crucial for selecting the right tool.
  • Matching-Based KLD Approximation is Effective: The chosen matching-based KLD approximation proves to be computationally efficient and provides results consistent with more expensive methods, making it suitable for their application.
  • Model-Based Confusability Aligns with Recognition-Based Confusability: A significant finding is that the syllable confusability identified using their proposed HMM dissimilarity measure shows high consistency with confusability derived from actual syllable recognition confusion matrices. This validates the effectiveness of their model-based approach.

Key Results

  • The proposed DTW-based HMM dissimilarity measure is shown to be effective in identifying confusable syllables.
  • When applied to 410 Putonghua base syllables, the method, using a threshold of 10 for clustering, resulted in 90 clusters of confusable syllables.
  • The agreement between clusters identified by their method and those derived from recognition confusion matrices was high, with 27 pairs of clusters showing perfect agreement (CP=1) and 48 pairs having a CP greater than 0.5.
  • The matching-based KLD approximation was found to be the most computationally efficient among the methods studied, while still providing good results.

Limitations and Future Work

  • Limitations of GMM Approximation: While the matching-based KLD approximation is efficient, it is still an approximation. The paper acknowledges that the UT-based method might offer better accuracy in certain scenarios (e.g., when mixture weights are close to 0 or 1).
  • Computational Complexity: Although more efficient than MC simulation, the DTW-based HMM dissimilarity measure might still be computationally intensive for very large vocabularies or real-time applications requiring extremely fast responses.
  • Future Work: The authors mention that they are using this new measure in other ASR applications and will report those studies elsewhere, suggesting potential for broader application and further validation. They also implicitly suggest exploring other GMM dissimilarity measures or further optimizing the DTW process.

Summary updated

BibTeX
@inproceedings{huo2006dtw,
  author = {Qiang Huo and Wei Li},
  title = {{A DTW-based dissimilarity measure for left-to-right hidden Markov models and its application to word confusability analysis}},
  booktitle = {Interspeech},
  year = {2006},
}
Figure