A Spectral Algorithm for Learning Hidden Markov Models

By Daniel J. Hsu, Sham M. Kakade, Tong Zhang. 2009

246 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

Kernel Mean Embedding of Distributions: A Review and Beyonds (2016, background): “24) by the loss which is less sensitive to outliers such as Huber loss (Huber 1964) and k is assumed to be non-negative and to integrate to one, e.g., Gaussian kernel and Student’s-t kernel. Later, Muandet et al. (2014b) provides a non-linear extension of the estimator in (3.”
Closing the learning-planning loop with predictive state representations (2009, background): “However, the problem of learning HMMs and POMDPs in general is hard under cryptographic assumptions (Kearns and Valiant 1994; Terwijn 2002).”
Predictive-State Decoders: Encoding the Future into Recurrent Networks (2017, background): “In the controls literature, these approaches were developed as subspace identification [51], and in the ML literature as spectral approaches for partially-observed systems [9, 8, 26, 56].”
A Latent Variable Model Approach to PMI-based Word Embeddings (2015, background): “The novelty here over such past works is a theoretical analysis in the method-of-moments tradition (Hsu et al., 2012; Cohen et al., 2012).”
Learning nonlinear dynamic models (2009, methodology): “The agnostic setting, where the SPR-DM model is only approximately correct, can be analyzed using perturbation techniques (e.g., for linear systems, this is done in (Hsu et al., 2008)).”
Variance Reduction for Faster Non-Convex Optimization (2016, methodology): “For some models, probabilistic and other assumptions on the input can be used to give specially designed polynomial-time algorithms (Arora et al., 2014; 2013; Hsu et al., 2012).”
Spectral Inference Networks: Unifying Spectral Methods With Deep 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 [17, 1].”
Two Manifold Problems with Applications to Nonlinear System Identification (2012, methodology): “Subspace identification approaches to learning nonlinear dynamical systems depend critically on instrumental variables and the spectral decomposition of (potentially infinite-dimensional) covariance operators (Hsu et al., 2009; Boots et al., 2010; Song et al., 2010).”
A Method of Moments for Mixture Models and Hidden Markov Models (2012, methodology): “…present work is based on a notable exception to the above situation, namely Chang’s spectral decomposition technique for discrete Markov models of evolution (Chang, 1996) (see also Mossel and Roch (2006) and Hsu et al. (2009) for adaptations to other discrete mixture models such as discrete HMMs).”
A Provably Correct Learning Algorithm for Latent-Variable PCFGs (2014, background): “First, a guarantee of correct parameter values in the limit of infinite data is typically the starting point for a sample complexity result (see for example (Hsu et al., 2009; Anandkumar et al., 2012)).”
RAND-WALK: A Latent Variable Model Approach to Word Embeddings (2015, background): “However, we can assume equation (2.2), that is, the partition function typically don’t vary much for most of context vectors c .”
Better Agnostic Clustering Via Relaxed Tensor Norms (2017, background): “( If the cluster means are in general position, other lines of work yields results for Gaussians [ KMV10, MV10, BS10, HK13, BCV14, GVX14, BCMV14, ABG + 14, GHK15] or for distributions satisfying independence assumptions [HKZ09, AGH + 13].”
Nonparametric Estimation of Multi-View Latent Variable Models (2013, background): “Recently, there is a surge of interest in designing spectral algorithms for estimating the parameters of latent variable models (Hsu et al., 2009; Parikh et al., 2011; Song et al., 2011; Foster et al., 2012; Anandkumar et al., 2012a,b; Kir´aly, 2013).”
A spectral algorithm for learning Hidden Markov Models (2008, background): “This makes the algorithm particularly applicable to settings with a large number of observations, such as those in natural language proc ssing where the space of observation is sometimes the words in a language.”
Inference in finite state space non parametric Hidden Markov Models and applications (2015, methodology): “An alternative proof of Theorem 1 could be given using the parametric identiﬁcation result in Hsu et al. (2012) combined with an adequate discretization argument.”
Sample-Efficient Reinforcement Learning for POMDPs with Linear Function Approximations (2022, methodology): “…is based on a new variant of the Bellman operator designed for such POMDPs, inspired by the observable representation of hidden Markov models (Hsu et al., 2012), which avoids the computation of conditional expectation with respect to the entire history and thus implies computation eﬃciency.”