A Distance for HMMs Based on Aggregated Wasserstein Metric and State Registration

Yukun Chen, Jianbo Ye, Jia LiECCV 2016 · DOI · arXiv

Abstract

Comparing Hidden Markov Models (HMMs) is a fundamental challenge in time-series analysis due to state-labeling ambiguities and the lack of closed-form distance metrics. This paper introduces the Aggregated Wasserstein (AW) framework, which utilizes Optimal Transport to align or "register" the hidden states of two HMMs. By matching states based on their emission distributions, the authors propose two metrics: Minimized Aggregated Wasserstein (MAW) and Improved Aggregated Wasserstein (IAW). These metrics are computationally efficient, invariant to state relabeling, and demonstrate superior performance in motion capture retrieval and classification tasks compared to traditional Kullback-Leibler (KL) divergence.

Introduction

Measuring the similarity between two HMMs is difficult because their parameters—transition matrices and emission distributions—reside on non-linear manifolds where Euclidean distances are inappropriate. Two major hurdles complicate this task:

  1. The Identifiability Issue: HMM states are latent. A simple permutation of state labels results in different parameter matrices for mathematically identical models.
  2. Computational Complexity: Standard measures like KL-divergence typically require expensive Monte Carlo simulations, which scale poorly and lack closed-form solutions for HMMs.

This research seeks a parameter-based distance that is fast, robust to noise, and naturally handles state permutations.

Methodology: State Registration and Aggregated Wasserstein

The proposed framework introduces State Registration as a solution to the identifiability problem. Since the marginal distribution of a GMM-HMM at any time step is a Gaussian Mixture Model (GMM), the authors use Optimal Transport (OT) to find a coupling matrix ($W$) that matches the states of two HMMs based on the geometric similarity of their emission distributions.

The state registration process: using a coupling matrix to align states and transition matrices between two HMMs.

Two specific distances are derived from this registration:

  • Minimized Aggregated Wasserstein (MAW): A computationally efficient version that uses the closed-form Wasserstein distance between Gaussian emissions as the matching cost. Once states are aligned, the distance is computed as a weighted sum of differences in marginal distributions and re-aligned transition matrices.
  • Improved Aggregated Wasserstein (IAW): A more refined version using a specialized Monte Carlo approach. The authors prove that IAW converges significantly faster ($O(\sqrt{\log n / n})$) than traditional log-likelihood statistics in high-dimensional spaces.

Key Insights: Wasserstein vs. KL-Divergence

A critical finding of this work is the statistical robustness of the Wasserstein metric over KL-divergence. In scenarios where parameters are perturbed, the Wasserstein distance remains stable and exhibits lower variance.

Comparison of Wasserstein Distance and KL Divergence stability under varying deviation factors for mean and covariance.

Unlike KL-divergence, which can become undefined if a covariance matrix becomes singular, the Wasserstein metric provides a continuous and well-behaved measure of distance. This stability is crucial for practical applications where data may be noisy or models may be slightly misspecified.

Experimental Results

The framework was evaluated using synthetic data and the CMU Motion Capture (Mocap) dataset, which contains complex 62-dimensional sequences of human movement.

  • Retrieval Performance: MAW and IAW consistently outperformed KL-based methods in precision and recall across various joint groups (e.g., "root," "rleg," "lleg").
  • Classification Accuracy: In motion classification tasks using Adaboost, the proposed distances showed a significant lead. On a 6-joint group scheme, IAW achieved 88.17% accuracy, while KL-divergence reached only 73.37%.
  • Efficiency: MAW is highly optimized, requiring only 10–20ms per distance calculation in MATLAB, making it suitable for large-scale database searches.

Conclusion

The Aggregated Wasserstein framework provides a robust and efficient solution for HMM comparison. By framing state alignment as an Optimal Transport problem, the authors overcome the long-standing issue of state relabeling. Future work may extend this framework to more complex emission distributions beyond Gaussians and explore its application in HMM-based clustering for large time-series datasets.

Summary updated

BibTeX
@inproceedings{chen2016distance,
  author = {Yukun Chen and Jianbo Ye and Jia Li},
  title = {{A Distance for HMMs Based on Aggregated Wasserstein Metric and State Registration}},
  booktitle = {European Conference on Computer Vision},
  year = {2016},
  doi = {10.1007/978-3-319-46466-4\_27},
}
Figure