Phase transition for parameter learning of Hidden Markov Models
arXiv:2003.11680 · doi:10.1103/PhysRevE.104.044105
Abstract
We study a phase transition in parameter learning of Hidden Markov Models (HMMs). We do this by generating sequences of observed symbols from given discrete HMMs with uniformly distributed transition probabilities and a noise level encoded in the output probabilities. By using the Baum-Welch (BW) algorithm, an Expectation-Maximization algorithm from the field of Machine Learning, we then try to estimate the parameters of each investigated realization of an HMM. We study HMMs with n=4, 8 and 16 states. By changing the amount of accessible learning data and the noise level, we observe a phase-transition-like change in the performance of the learning algorithm. For bigger HMMs and more learning data, the learning behavior improves tremendously below a certain threshold in the noise strength. For a noise level above the threshold, learning is not possible. Furthermore, we use an overlap parameter applied to the results of a maximum-a-posteriori (Viterbi) algorithm to investigate the accuracy of the hidden state estimation around the phase transition.
arXiv comment9 pages, 9 figures
References in corpus (18)
- Finding and evaluating community structure in networks
- The spread of epidemic disease on networks
- Machine learning phases of matter
- Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
- Unsupervised learning of phase transitions: from principal component analysis to variational autoencoders
- Local resolution-limit-free Potts model for community detection
- Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
- -means as a variational EM approximation of Gaussian mixture models
- Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
- The Entropy of a Binary Hidden Markov Process
- Hidden Markov models for stochastic thermodynamics
- Clustering analysis of the ground-state structure of the vertex-cover problem
- Phase transition encoded in neural network
- Numerical Solution-Space Analysis of Satisfiability Problems
- Information theoretic approach to ground-state phase transitions for two and three-dimensional frustrated spin systems
- When memory pays: Discord in hidden Markov models
- Utilizing hidden Markov processes as a new tool for experimental physics
- Active Inference for Binary Symmetric Hidden Markov Models