TL;DR
This paper introduces a new class of Hidden Markov Models (HMMs) called Dense-Mostly-Constant (DMC) HMMs. By approximating less important transition probabilities with a constant value, they achieve significant speedups in inference and learning for large state spaces, outperforming standard HMMs even when the DMC assumption is slightly violated.
What Problem Does This Paper Address?
Hidden Markov Models (HMMs) are powerful tools for modeling sequential data, widely used in fields like speech recognition and bioinformatics. However, standard HMM algorithms for fundamental tasks like calculating observation likelihood, inferring the most likely state sequence, and learning model parameters all have a time complexity that is quadratic in the number of states ($O(N^2)$). This quadratic scaling becomes a major bottleneck when dealing with HMMs that have a large number of states (hundreds or even thousands), which are increasingly necessary to capture complex real-world phenomena. The paper aims to overcome this limitation by developing faster algorithms for these core HMM operations without resorting to overly restrictive assumptions like sparse transition matrices.
Methods
The core innovation is the introduction of the Dense-Mostly-Constant (DMC) transition matrix. In a standard HMM, every transition probability between states is modeled individually. In a DMC HMM, for each state, we identify a small, fixed number ($K$) of "important" transitions whose exact probabilities are preserved. The remaining $N-K$ transition probabilities are then set to a constant value, ensuring that each row of the transition matrix still sums to one. This constraint allows for the development of sub-quadratic algorithms for the three main HMM problems:
- Forward Algorithm (Likelihood Calculation): Instead of an $O(N^2)$ summation per time step, the DMC condition allows for a split into an $O(1)$ amortized cost and an $O(K)$ cost, resulting in an overall $O(TNK)$ complexity.
- Viterbi Algorithm (State Sequence Inference): Similar to the forward algorithm, the maximization step can be split, leading to a more efficient computation.
- Baum-Welch Algorithm (Parameter Learning): The paper proposes a novel re-estimation procedure for the transition matrix that avoids computing all $N^2$ transition probabilities. It uses a "lazy dot-product evaluation" approach with an upper bound mechanism to efficiently identify and update the $K$ most important transitions, achieving a complexity of $O(TNK + RN^2)$ where $R$ is a parameter controlling the trade-off between computation and bound tightness.
Datasets
The paper uses the following datasets:
- Synthetic Datasets:
- DMC-friendly data: Generated from an HMM with a DMC transition matrix where the top 5 transitions capture 60% of the probability mass.
- Anti-DMC data: Generated from an HMM designed to violate the DMC assumption, where transition probabilities are proportional to $1, 2, 3, \dots, 20$ in each state.
- Real-world Dataset:
- Motionlogger dataset: 14,720 rows of two-dimensional time series data from accelerometers worn on a person's body, representing daily activity.
Key Insights and Ideas
- The "Constant Approximation" is Powerful: The core idea that approximating less important transitions with a constant value can drastically speed up computations is a key insight. It suggests that for many real-world problems, the exact values of all transition probabilities might not be critical for good performance.
- DMC as a Regularization Mechanism: The DMC assumption effectively reduces the number of parameters to be learned (from $N^2$ to $NK$), acting as a form of regularization. This can help prevent overfitting, especially in scenarios with large state spaces where standard HMMs might struggle to learn reliable transition probabilities from limited data.
- Bridging the Gap: DMC HMMs can be seen as bridging the gap between full HMMs (where $K=N-1$) and simpler models like Gaussian Mixture Models (which can be approximated by DMC HMMs with $K=0$). This flexibility allows them to adapt to different levels of complexity in the data.
- "Lazy" Computation for Efficiency: The "lazy dot-product evaluation" for computing the transition probabilities is a clever algorithmic technique that avoids unnecessary computations by focusing on potentially important terms first.
Key Results
- Dramatic Speedups: The DMC HMM algorithms demonstrate significant speedups for inference and learning, particularly as the number of states ($N$) increases. For example, the Viterbi algorithm's runtime scales linearly with $N$ for fixed $K$ in DMC HMMs, compared to quadratically for regular HMMs. Baum-Welch iterations also show substantial speed improvements.
- Competitive Accuracy: Despite the approximations, DMC HMMs achieve accuracy comparable to or even exceeding regular HMMs on the tested datasets. On the DMC-friendly dataset, a DMC HMM with $K=5$ achieved the same likelihood as a full regular HMM. Even on the Anti-DMC dataset, which is designed to break the DMC assumption, DMC HMMs still outperformed simpler baselines.
- Trade-offs Between N and K: The paper explores the trade-offs between the number of states ($N$) and the number of exact transitions ($K$). They show that for a fixed number of transition parameters, different pairs of $(N, K)$ can model data effectively, suggesting that the DMC framework allows for flexible model design.
Limitations and Future Work
- Heuristic Choice of R: The parameter $R$ in the Baum-Welch algorithm, which controls the extent of partial computation, is heuristically chosen ($T/20$ in experiments). Finding an optimal $R$ automatically could further improve performance.
- DMC Assumption Violation: While DMC HMMs perform well even when the assumption is slightly violated, extreme violations can lead to a larger accuracy gap compared to regular HMMs. The paper notes that the effectiveness depends on how well the data conforms to the DMC assumption.
- Future Work: The authors suggest that the DMC HMM framework could be extended for fast sparse structure discovery and as a regularization mechanism to prevent overfitting in large HMMs. They also mention exploring different ways to define the "constant" value and investigating its impact.
Summary updated