Source-linked AI summary
A Spectral Algorithm for Learning Hidden Markov Models
Daniel Hsu, Sham M. Kakade, Tong Zhang
TL;DR
Learning HMMs is generally hard and often relies on heuristics that can suffer from local optima. This paper presents an efficient spectral algorithm under rank-based separation conditions, with guarantees for joint and conditional observation distributions and applicability to large observation spaces.
Problem
General HMM learning is hard under cryptographic assumptions, while heuristic approaches can suffer from local optima and require careful initialization.
Method
The paper learns an observable HMM representation from observable quantities using an SVD of a past–future correlation matrix, under spectral conditions on O and T.
Results
The algorithm efficiently approximates joint observation-sequence distributions and conditionals for future observations, with joint error degrading polynomially in t and conditional error asymptotically bounded.
Takeaways & Limitations
The method’s sample complexity depends on the number of observations only through spectral properties, making it applicable to large observation spaces such as NLP vocabularies.
Takeaways & Limitations
The guarantees assume spectral rank or separation conditions, and the algorithm does not explicitly ensure predicted probabilities lie in [0, 1].
Abstract
from arXiv · showhide
Hidden Markov Models (HMMs) are one of the most fundamental and widely used statistical tools for modeling discrete time series. In general, learning HMMs from data is computationally hard (under cryptographic assumptions), and practitioners typically resort to search heuristics which suffer from the usual local optima issues. We prove that under a natural separation condition (bounds on the smallest singular value of the HMM parameters), there is an efficient and provably correct algorithm for learning HMMs. The sample complexity of the algorithm does not explicitly depend on the number of distinct (discrete) observations---it implicitly depends on this quantity through spectral properties of the underlying HMM. This makes the algorithm particularly applicable to settings with a large number of observations, such as those in natural language processing where the space of observation is sometimes the words in a language. The algorithm is also simple, employing only a singular value decomposition and matrix multiplications.
1 Introduction
The paper introduces an efficient spectral algorithm for learning HMMs under a natural separation condition, avoiding heuristic hidden-state search. It uses observable relationships between past and future observations and supports large observation spaces.
- Motivation: HMM learning is generally hard under cryptographic assumptions, motivating heuristic methods for practical applications.HMMs are widely used in speech recognition, NLP, and genomic sequence modeling.
- Contribution: The algorithm learns HMMs under spectral separation conditions on the observation and transition matrices.The observation distributions may overlap substantially, so a single observation need not identify its hidden state.
- Guarantees: The method estimates joint sequence distributions with error degrading polynomially in sequence length and conditional future-observation distributions with asymptotically bounded error.These guarantees apply to sequence prediction without explicitly recovering the transition and observation models.
- Method: The algorithm uses an SVD of a past–future correlation matrix, interpretable as canonical correlation analysis, to uncover hidden-state information.This connects the approach to spectral subspace identification while adapting it to HMMs rather than additive-noise dynamical systems.
- Implications: Its sample complexity depends on observation-space size only implicitly through HMM spectral properties, supporting settings with many observations such as language vocabularies.The approach instead learns an alternative representation related linearly to the HMM’s hidden state.
- Related Work: Compared with prior efficient work, the algorithm avoids explicitly recovering observation and transition matrices and is designed for unequal, potentially large state and observation spaces.Prior work assumed state and observation spaces had the same dimension and introduced noise when explicitly learning the matrices.
2 Preliminaries
The preliminaries define HMM parameters, observable operator representations, rank assumptions, and the sampling model used for the paper’s guarantees. The analysis targets joint and conditional observation-distribution estimation.
- 2.1 Hidden Markov Models: An HMM has m hidden states and n observations, with transition matrix T, observation matrix O, and initial distribution π determining sequence probabilities.Conditional independence makes T and O sufficient to characterize state and observation sequences.
- 2.1 Hidden Markov Models: Observation operators encode each observation symbol as Ax = T diag(Ox,1, . . . , Ox,m), enabling sequence probabilities to be expressed through matrix products.This is the observable-operator formulation used by the learning representation.
- 2.1 Hidden Markov Models: The algorithm learns an observable-operator representation rather than necessarily recovering the original HMM transition and observation matrices.The representation is closely related to the hidden-state model and can support hidden-state interpretation.
- 2.3 Assumptions: The HMM rank condition requires π to be positive element-wise and both O and T to have rank m.It excludes cases where one state’s output distribution is a mixture of other states’ output distributions.
- 2.3 Assumptions: The observation-rank requirement can be relaxed by forming probability tables from multiple consecutive observation symbols.For example, different transition probabilities can distinguish states with identical single-observation probabilities.
- 2.4 Learning Model: The learning model assumes independent observation sequences generated from a common initial state distribution, while the analysis uses only each sequence’s initial few observations.Using full long sequences in practice can provide sufficient data with effective sample size discounted by the Markov chain’s mixing rate.
- 2.4 Learning Model: The goals are accurate estimation of Pr[x1:t] and Pr[xt|x1:t−1] for arbitrary sequence length t.Conditional-distribution approximation does not depend on t, whereas joint-distribution quality degrades gracefully with t.
3 Observable Representations of Hidden Markov Models
The paper replaces direct hidden-state estimation with an observable HMM parameterization built from marginal observation probabilities and a spectral subspace. Under rank and invertibility conditions, this representation supports computing joint and conditional observation probabilities from empirical statistics.
- Heuristic HMM learning can suffer from local optima and require careful initialization because hidden states are unobserved.
- Under Condition 1, HMMs admit an efficiently learnable parameterization based only on observable quantities, avoiding guesses about hidden states.
- 3.1 Definition: The representation uses marginal probabilities of observation singletons, pairs, and triples, together with an m-dimensional matrix U satisfying invertibility of U^⊤O.
- 3.1 Definition: If the initial distribution is positive and O and T have column rank m, P2,1 has rank m and the left singular vectors associated with its non-zero singular values span the same space as O.
- 3.2 Basic Properties: The observable representation computes sequence probabilities as products of matrix operators and also supports conditional probabilities through normalized internal states linked linearly to hidden-state beliefs.
- 3.3 Proofs: The algorithm estimates the observable statistics from independent observation triples, computes an SVD of empirical P2,1, and returns an HMM model parameterized by observable operators.
4 Spectral Learning of Hidden Markov Models
The section presents a spectral learning algorithm for HMMs with guarantees for joint and conditional observation probabilities. Its analysis depends on spectral separation, and extends to distributions approximately modeled by HMMs.
- Algorithm: The algorithm estimates HMM parameters from random samples using a representation based on observable probability operators.The method uses an empirical estimate of P2,1 and an SVD to construct U, while random samples estimate the model parameters.
- Learning Approximately HMM Distributions: The joint-probability guarantee degrades gracefully when the data distribution is only approximately generated by an HMM.The approximation error includes a term determined by the distance between the true distribution and a structurally valid HMM distribution.
- Joint Probability Accuracy: For observation distributions with Zipf-like frequencies and s > 1, the relevant sample-complexity term can become independent of the number of observation symbols.The effective support size satisfies n0(ε) = O(ε1/(1−s)), which is independent of n in this setting.
- Joint Probability Accuracy: The learned model approximates joint observation-sequence probabilities with total-variation error that degrades polynomially as sequence length increases.Theorem 6 gives a high-probability guarantee for any sequence length t, with the bound controlled by the HMM spectral parameters.
- Conditional Probability Accuracy: Conditional prediction error remains asymptotically bounded under additional stochasticity conditions, using KL divergence to measure relative accuracy.The analysis uses the positivity condition [Ax]ij ≥ α > 0 and explains that KL divergence is appropriate when conditioning on low-probability histories.
5 Proofs
The proofs establish that sampling and perturbation errors yield accurate observable parameters and controlled sequence and conditional prediction errors under the stated HMM conditions.
- Error estimation: Independent observation triples provide high-probability bounds on the sampling errors used to estimate the observable representation.The analysis then propagates these sampling bounds to parameter errors.
- Observable representation: A sufficiently accurate estimate of the past–future correlation matrix makes the estimated singular subspace well-conditioned and keeps the observable representation valid.Invertibility of bU^T O is central to defining the estimated parameters.
- Error propagation: Errors in products of estimated observation operators accumulate roughly additively rather than exponentially over sequence length.This controls the growth of sequence-probability errors despite multiplying t matrices.
- Theorem conclusion: Choosing the sample size and accuracy parameters to satisfy the intermediate bounds yields the theorem’s desired L1 error of ε.The stated parameter bounds are δ∞ ≤ 0.05ε, δ1 ≤ 0.05ε, and Δ ≤ 0.4ε/t.
- Conditional prediction: Under Condition 3, sufficiently accurate state updates avoid assigning very small probabilities to hidden states and support contraction-based conditional prediction analysis.The corollary guarantees [bgt]i ≥ α/2 under explicit parameter-error conditions.
A Sample Complexity Bound
The sample-complexity analysis estimates empirical probability vectors using concentration bounds and exploits the fact that infrequent observation symbols contribute little total probability mass.
- Empirical estimation: The empirical estimate of a discrete probability vector is formed from N independently sampled one-hot observations.The analysis applies a concentration result based on McDiarmid’s inequality.
- Concentration bound: McDiarmid’s inequality provides a high-probability bound for the Euclidean error of the empirical probability estimate.The bound is stated in Proposition 19.
- Large observation spaces: When observation dimensionality n is large, restricting attention to the k most frequent symbols can improve the error bound through the tail mass ε(k).ε(k) is the total probability of the smallest n−k observation probabilities.
B Matrix Perturbation Theory
The perturbation results quantify how singular-value and singular-subspace errors respond to matrix perturbations, supporting stability of the estimated observable representation.
- Singular-value stability: Singular values of a perturbed matrix are controlled by the perturbation norm through standard matrix perturbation bounds.These bounds are cited from Stewart and Sun.
- Subspace stability: Canonical-angle bounds control how far the leading left and right singular subspaces move after perturbation.The result assumes a separation gap between singular values of the relevant subspaces.
- Subspace stability: For a full-rank matrix, sufficiently small spectral perturbation preserves the leading singular subspace and bounds its deviation from the true subspace.The condition is ∥E∥2 ≤ εσn with ε < 1.
- Parameter stability: Pseudoinverse perturbation bounds translate matrix errors into errors in the estimated observable parameters.The analysis uses these bounds alongside singular-subspace control.
C Recovering the Observation and Transition Matrices
An optional spectral post-processing step recovers the observation and transition matrices explicitly by exploiting eigenvalues and eigenvectors of observable matrix products.
- Matrix construction: The recovery procedure uses joint-probability matrices whose factorizations involve the observation and transition matrices.It defines P3,1 from observations at times 3 and 1 and relates P3,x,1 to O, Ax, T, and the initial distribution.
- Observation recovery: The eigenvalues of (U^T P3,x,1)(U^T P3,1)+ equal the observation probabilities associated with the diagonal operator Ox.This identifies observation probabilities from observable statistics.
- Eigen-decomposition: Random linear combinations separate the relevant eigenvalues with high probability, allowing eigenvectors to recover U^T O T up to diagonal scaling.The separation is stated to be roughly on the same order as the failure probability.
- Transition recovery: Once O is formed from the diagonal operators, the initial distribution π and transition matrix T can be recovered from P1 and P2,1.This uses the full-column-rank property of O.
- Stability limitation: The explicit recovery step has sample complexity polynomial in 1/η because eigenvector stability depends heavily on eigenvalue spacing.This contrasts with the logarithmic dependence targeted by the main spectral approach’s failure-probability analysis.