A Spectral Algorithm for Learning Hidden Markov Models
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Time SeriesTime Series AnalysisSimilar Papers 제목 키워드 기반
A Spectral Algorithm for Inference in Hidden Semi-Markov Models
Hidden semi-Markov models (HSMMs) are latent variable models which allow latent state persistence and can be viewed as a generalization of the popular hidden Markov models (HMMs). In this paper, we introduce a novel spec…
Reinforcement Learning in Rich-Observation MDPs using Spectral Methods
Reinforcement learning (RL) in Markov decision processes (MDPs) with large state spaces is a challenging problem. The performance of standard RL algorithms degrades drastically with the dimensionality of state space. How…
reinforcement-learningReinforcement LearningReinforcement Learning (RL)Short-Term Wind-Speed Forecasting Using Kernel Spectral Hidden Markov Models
In machine learning, a nonparametric forecasting algorithm for time series data has been proposed, called the kernel spectral hidden Markov model (KSHMM). In this paper, we propose a technique for short-term wind-speed p…
BIG-bench Machine LearningTime SeriesTime Series AnalysisImplementing spectral methods for hidden Markov models with real-valued emissions
Hidden Markov models (HMMs) are widely used statistical models for modeling sequential data. The parameter estimation for HMMs from time series data is an important learning problem. The predominant methods for parameter…
parameter estimationTime SeriesTime Series AnalysisGeographical Hidden Markov Tree for Flood Extent Mapping (With Proof Appendix)
Flood extent mapping plays a crucial role in disaster management and national water forecasting. Unfortunately, traditional classification methods are often hampered by the existence of noise, obstacles and heterogeneity…
General ClassificationManagement