A Spectral Algorithm for Learning Hidden Markov Models

Abstract

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.

Published in JCSS Special Issue "Learning Theory 2009"

Cited by in corpus (38)

• A Spectral Algorithm for Latent Dirichlet Allocation
• A Survey on Latent Tree Models and Applications
• A Method of Moments for Mixture Models and Hidden Markov Models
• Spectral Experts for Estimating Mixtures of Linear Regressions
• Two Step CCA: A new spectral method for estimating vector models of words
• Spectral Methods for Learning Multivariate Latent Tree Structure
• Local Loss Optimization in Operator Models: A New Insight into Spectral Learning
• Supervised Learning for Dynamical System Learning
• Learning loopy graphical models with latent variables: Efficient methods and guarantees
• Better Agnostic Clustering Via Relaxed Tensor Norms
• Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learning
• Two-Manifold Problems with Applications to Nonlinear System Identification
• Identifiability and Unmixing of Latent Parse Trees
• Learning mixtures of spherical Gaussians: moment methods and spectral decompositions
• Spectral dimensionality reduction for HMMs
• Contrastive learning, multi-view redundancy, and linear models
• On learning parametric-output HMMs
• Learning to Filter with Predictive State Inference Machines
• Predictive-State Decoders: Encoding the Future into Recurrent Networks
• Learning Hidden Markov Models from Pairwise Co-occurrences with Application to Topic Modeling
• Nonparametric Estimation of Multi-View Latent Variable Models
• Dimension-free Concentration Bounds on Hankel Matrices for Spectral Learning
• A Spectral Algorithm for Latent Junction Trees
• Divide-and-Conquer Learning by Anchoring a Conical Hull
• Off-policy Evaluation in Infinite-Horizon Reinforcement Learning with Latent Confounders
• Prediction with a Short Memory
• Estimation from Indirect Supervision with Linear Moments
• Learning High-Dimensional Mixtures of Graphical Models
• Fourier PCA and Robust Tensor Decomposition
• A Canonical Form for Weighted Automata and Applications to Approximate Minimization
• Spectral Methods for Nonparametric Models
• Two-Manifold Problems
• Learning Parametric-Output HMMs with Two Aliased States
• Neural Network Based Nonlinear Weighted Finite Automata
• Learning HMMs with Nonparametric Emissions via Spectral Decompositions of Continuous Matrices
• Generalization Bounds for Weighted Automata
• Diversity in Spectral Learning for Natural Language Parsing
• Learning General Latent-Variable Graphical Models with Predictive Belief Propagation