A spectral algorithm for learning Hidden Markov Models

By Daniel J. Hsu, Sham M. Kakade, Tong Zhang. Journal of computer and system sciences (Print), 2008

312 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Signal Processing

View Paper: https://www.semanticscholar.org/paper/16611312448f5897c7a84e2f590617f4fa3847c4

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Signal Processing

Citations in the corpus

Provable Bounds for Learning Some Deep Representations (2013, background): “, for which learning algorithms with provable guarantees were given (Hsu et al., 2012; Moitra & Valiant, 2010; Hsu & Kakade, 2013; Arora et al., 2012; Anandkumar et al., 2012).”
Predictive State Recurrent Neural Networks (2017, methodology): “In particular, method-of-moments algorithms provide consistent parameter estimates for a range of BFs including PSRs [5, 7, 9, 10, 11].”
Spectral Inference Networks: Unifying Deep and Spectral Learning (2018, methodology): “Spectral algorithms can also be used for asymptotically exact estimation of parametric models like hidden Markov models and latent Dirichlet allocation by computing the SVD of moment statistics (Hsu et al., 2012; Anandkumar et al., 2012).”
Methods of Moments for Learning Stochastic Languages: Unified Presentation and Empirical Comparison (2014, methodology): “We now proceed to give the details of the algorithm, which is based on (Hsu et al., 2009; Bailly et al., 2009).”
Learning to Filter with Predictive State Inference Machines (2015, methodology): “This assumption allows us to avoid the cryptographic hardness of the general problem (Hsu et al., 2009).”
Spectral Learning of Mixture of Hidden Markov Models (2014, background): “Method of Moments (MoM) based algorithms [1, 2, 3] for learning latent variable models have recently become popular in the machine learning community.”
Kernel Embeddings of Latent Tree Graphical Models (2011, background): “One advantage of our spectral algorithm is that it is local-minimum-free and hence amenable for further statistical analysis (see [11, 25, 16] for previous work on spectral algorithms).”
A Spectral Algorithm for Latent Dirichlet Allocation (2012, methodology): “The idea has been extended to other discrete mixture models such as discrete hidden Markov models (HMMs) and mixture models with single active topics (see Mossel and Roch (2006); Hsu et al. (2009); Anandkumar et al. (2012)).”
Spectral Methods for Indian Buffet Process Inference (2014, background): “In particular, the work of [6, 5, 11, 21, 29] demonstrates that it is possible to infer latent variable structure accurately, despite the problem being nonconvex, thus exhibiting many local minima.”
Tensor decompositions for learning latent variable models (2012, methodology): “While finite sample bounds can be given to establish the learnability of these models [HKZ12], the algorithms do not actually give parameter estimates (e.g., of the emission or transition matrices in the case of HMMs).”
Learning mixtures of spherical gaussians: moment methods and spectral decompositions (2012, methodology): “The non-degeneracy condition in this work is similar to one used for bypassing computational (cryptographic) barriers to estimation for hidden Markov models [9, 23, 17, 3].”
An Online Spectral Learning Algorithm for Partially Observable Nonlinear Dynamical Systems (2011, methodology): “Recently, spectral algorithms have been increasingly used to learn models of partially observable nonlinear dynamical systems such as HMMs (Hsu, Kakade, and Zhang 2009; Siddiqi, Boots, and Gordon 2010) and TPSRs (Rosencrantz, Gordon, and Thrun 2004; Boots, Siddiqi, and Gordon 2010; Boots and Gordon…”