Hidden Markov model
A hidden Markov model can be pictured as a genie shut inside a room that nobody is allowed to see into. The room holds urns, X1, X2, X3 and so on, and each urn contains a known mix of balls. Every ball carries a unique label, y1, y2, y3 and so on. The genie chooses an urn, draws a ball at random, and sets it on a conveyor belt. An observer watches the belt. The observer sees the sequence of labeled balls and nothing else, because the urns stay out of sight.
Now suppose the observer knows exactly what each urn contains and has just watched balls y1, y2 and y3 roll past. Even then, the observer cannot be sure which urn the third ball came from. The observer is not helpless, though. It is possible to work out how likely it is that the third ball came from each of the urns.
That gap between what can be seen and what is really going on is the heart of this documentary. How do you reason about a process when all you ever get to watch is what it leaves behind? What numbers live inside such a model, and how are they found? And why does a puzzle about a genie keep turning up in so many fields?
Alice and Bob live far apart, and every day they talk on the telephone about what they did. Bob cares about only three activities: walking in the park, shopping, and cleaning his apartment. His choice depends exclusively on the weather where he lives. Alice has no definite information about that weather, but she knows the general trends. From what Bob tells her, she tries to guess whether the day was rainy or sunny.
Alice treats the weather as a discrete Markov chain with two states, Rainy and Sunny. She cannot observe those states directly, so they are hidden from her. What she can observe is what Bob reports: a walk, a shop, or a clean. Those reports are the observations, and the whole arrangement is a hidden Markov model.
In this version of the game, Alice knows every parameter. The numbers can be written as a few lines of Python code in three groups. The first group is the start probability, which captures Alice's belief about the weather when Bob first calls. She gives sixty percent to rainy and forty percent to sunny, because rain tends to be the more common state on average.
The second group is the transition probability, which describes how the weather changes from one day to the next. Rainy weather stays rainy with a probability of seventy percent. If today is rainy, there is only a thirty percent chance that tomorrow will be sunny. A sunny day is followed by another sunny day sixty percent of the time and by a rainy one forty percent of the time.
One quirk is worth noticing. Alice's starting belief is not the long-run balance implied by her transition probabilities. That balance works out to roughly fifty-seven percent rainy and forty-three percent sunny.
The whole model, then, comes down to a start belief, a table of changes between states, and a table linking states to what gets reported. The next question is how those tables are built and counted.
Ovals in a trellis diagram stand for random variables, and the arrows between them mark conditional dependencies. Each oval can take any of several values. One row of ovals holds the hidden state at each moment in time. The other row holds the observation at each moment. The states are called hidden states, and the chance of an observation given a state is called the emission probability, or output probability.
The arrows enforce two rules. First, the hidden variable at time t depends only on the hidden variable one step earlier. Everything before that step has no influence at all, and this is the Markov property. Second, the observation at time t depends only on the hidden variable at that same time t.
The usual version has a discrete set of hidden states, assumed to number N, and a categorical distribution governs the choice among them. Observations can be discrete, typically drawn from a categorical distribution, or continuous, typically drawn from a Gaussian distribution.
The transition probabilities control how the next hidden state is picked. Every one of the N states has a transition probability to each of the N states. The probabilities leaving any single state must sum to one, so the full grid forms a Markov matrix. Once all but one of a state's transitions are known, the last is fixed, which trims the number of free transition parameters.
Emission parameters depend on what is being observed. If the observation is discrete with M possible values, each state needs its own set of categorical parameters. If the observation is an M-dimensional vector following an arbitrary multivariate Gaussian distribution, there are parameters for the means and further parameters for the covariance matrix.
That Gaussian case can grow unwieldy. Unless M is small, it may be more practical to restrict the covariances. One option assumes the elements of the observation vector are independent of each other. A less restrictive option assumes each element is independent of all but a fixed number of its neighbors.
A model this tidy invites a set of precise questions, and there are several distinct ones to ask.
Summing over every possible sequence of hidden states is the brute-force route to the probability of an observed output sequence. Dynamic programming makes that sum manageable. The method that exploits it is the forward algorithm.
Filtering asks something different. Given the parameters and a run of observations, what is the distribution over the hidden state at the very end of the run? This suits processes that move through a sequence of states in time, with one observation at each point. Asking where the process stands now is natural there, and the forward algorithm answers it efficiently too.
Smoothing looks backward. It asks for the distribution of a hidden variable somewhere in the middle of the sequence, a point k in the past relative to the final time t. The forward-backward algorithm is a good way to compute these smoothed values for every hidden variable.
The most likely explanation is a different kind of question. It asks about the joint probability of the entire sequence of hidden states behind an observed sequence. Part-of-speech tagging shows why this matters. The words are observed, the underlying parts of speech are hidden, and what counts is the whole sequence of tags rather than the tag for one word. Answering this takes a maximum over all possible state sequences, which the Viterbi algorithm finds efficiently.
A final question concerns statistical significance. Suppose a sequence is drawn from a null distribution. What is the probability that it scores at least as high as the observed one, whether by forward probability or by best state sequence probability? When a model is used to weigh a hypothesis about an output sequence, this significance reflects the false positive rate that comes with failing to reject that hypothesis.
Every one of these questions assumes the parameters are already in hand. Finding them is a separate problem.
No tractable algorithm is known that finds the best parameters exactly. The aim is the maximum likelihood estimate of the transition and emission probabilities, given one output sequence or a whole set of them. What can be derived efficiently is a local maximum. Two algorithms do the job: Baum-Welch and Baldi-Chauvin. Baum-Welch is a special case of the expectation-maximization algorithm, and for linear chain models it is the standard estimation tool.
Predicting a time series changes the advice. Bayesian methods such as Markov chain Monte Carlo sampling have proven better than settling on a single maximum likelihood model, both in accuracy and in stability. The price is a significant computational burden.
When scalability also matters, variational approximations to Bayesian inference offer a middle path. They match expectation-maximization in efficiency. Their accuracy is only slightly worse than that of exact MCMC-type inference.
Variational methods come back later in the story, when a model is built from several independent chains at once.
Leonard E. Baum and other authors described hidden Markov models in a series of statistical papers in the second half of the 1960s. Speech recognition was among the first applications, starting in the mid-1970s. Seen from the linguistics side, a hidden Markov model is equivalent to a stochastic regular grammar.
The second half of the 1980s brought a new use. Researchers began applying the models to biological sequences, DNA above all. Since then they have become ubiquitous in bioinformatics.
The reach is far wider than genes and voices. The models are known in thermodynamics, statistical mechanics, physics, chemistry, economics and finance. They appear in signal processing and information theory. Pattern recognition covers handwriting recognition, gesture recognition, part-of-speech tagging and musical score following. Another use is the study of partial discharges.
The common thread is a hidden sequence that cannot be seen directly, paired with other data that depends on it. Speech recognition, including Siri, fits that mold, and so does speech synthesis. So do machine translation, activity recognition, cryptanalysis, neuroscience and single-molecule kinetic analysis.
Biology supplies a long list of its own: gene prediction, alignment of bio-sequences, protein folding, sequence motif discovery in DNA and proteins, chromatin state discovery, and DNA hybridization kinetics. Even scanning software uses the idea to separate documents. More unexpected entries include metamorphic virus detection, transportation forecasting and solar irradiance variability.
The Kalman filter handles one special case of a continuous hidden state exactly. There, the hidden Markov process is a linear dynamical system, with linear relationships among related variables and Gaussian distributions throughout. In general, exact inference with continuous latent variables is infeasible. Approximate methods such as the extended Kalman filter or the particle filter step in.
Priors on the transition probabilities offer another direction. The standard algorithms implicitly assume a uniform prior over them. A natural alternative is the Dirichlet distribution, the conjugate prior of the categorical distribution, usually chosen in symmetric form to reflect ignorance about which states are more likely. Its single concentration parameter sets the density of the transition matrix. A value of 1 gives a uniform distribution. Values above 1 give a dense matrix with nearly equal transitions. Values below 1 give a sparse one, where each state leads to only a few destinations.
A two-level prior stacks one Dirichlet distribution on top of another. Set both levels to produce sparse distributions and the model suits unsupervised part-of-speech tagging, where some parts of speech are far more common than others. Learning algorithms that assume a uniform prior generally perform poorly on that task. Models with such priors can be learned using Gibbs sampling or extended versions of expectation-maximization.
Replace the Dirichlet distribution with a Dirichlet process and the number of states becomes unknown and potentially infinite. The two-level version is the hierarchical Dirichlet process hidden Markov model, or HDP-HMM. It was first described under the name Infinite Hidden Markov Model and later formalized in a work titled Hierarchical Dirichlet Processes.
The maximum entropy Markov model, or MEMM, takes a discriminative approach instead of a generative one. It models the conditional distribution of the states given the observations, using logistic regression, which is also known as a maximum entropy model. Its strength is flexibility. Features of nearby observations, or of observations at any distance, can inform a hidden state, and those features need not be statistically independent. Its weaknesses are limits on the prior distributions that can be placed on hidden states and an inability to predict the probability of an arbitrary observation. Many common uses never need that prediction.
The linear-chain conditional random field is a variant that uses an undirected graphical model. It avoids the label bias problem of MEMMs and may predict more accurately. Training can be slower.
The factorial hidden Markov model conditions a single observation on the hidden variables of several independent Markov chains. It is equivalent to one HMM with a very large number of states, so learning is difficult. A junction tree algorithm can give an exact solution, though at a heavy cost. In practice, approximations such as variational approaches are used.
Allowing a state to depend on the previous two or three states is another extension. Dynamic-programming training time then grows with the number of adjacent states in the dependency. This approach has been widely used to model DNA sequences. The triplet Markov model adds an auxiliary underlying process to capture quirks of the data. A link between the theory of evidence and triplet models allows data fusion in a Markovian setting and the modeling of nonstationary data.
In 2012, a different route to nonstationary data was suggested. A small recurrent neural network, specifically a reservoir network, captures how the temporal dynamics of the observations evolve. Its output, a high-dimensional vector, conditions the state transition probabilities. The transition probabilities then change over time as the data dictates, instead of following an unrealistic hand-built schedule.
In 2023, two new algorithms were introduced, the Discriminative Forward-Backward and Discriminative Viterbi algorithms. They compute the posterior distribution of the HMM using only conditional distributions. Unlike the traditional Forward-Backward and Viterbi algorithms, they do not need the law of the observations, which allows the HMM to serve as a discriminative model.
For longitudinal data there is the latent Markov model. Its basic version has been extended to include individual covariates, random effects and more complex data structures such as multilevel data.
Given a Markov transition matrix and an invariant distribution on the states, a probability measure can be imposed on the set of subshifts. Now ignore the difference between certain states. The space of subshifts is projected onto a smaller space, and the probability measure is projected down with it.
The curious thing is what happens to the projected measure. It is not produced by a Markov chain on the smaller space, not even by a chain of higher order.
The intuition is simple. Watching a long unbroken run of one symbol makes an observer increasingly sure about the hidden state behind it. So the visible part of the system can be affected by something infinitely far in the past.
A more extreme case exists. In numbered example 2.6, a space of subshifts on 6 symbols projects onto a space of subshifts on 2 symbols, and every Markov measure on the smaller space has a preimage measure that is not Markov of any order. This is the pure mathematics behind the genie's room, where certainty about the urns grows with every ball on the belt but never fully arrives.
Up next
Updated
Common questions
What is a hidden Markov model?
It is a Markov model in which the observations depend on a hidden Markov process. The hidden process cannot be seen directly, but its outcomes affect an observable process in a known way, so watching the observations lets you learn about the hidden states.
What are the two kinds of parameters in a standard hidden Markov model?
Transition probabilities control how the hidden state at one time is chosen given the previous hidden state. Emission probabilities, also called output probabilities, govern the observed variable given the hidden state at the same time.
Which algorithm finds the most likely sequence of hidden states?
The Viterbi algorithm finds the maximum over all possible state sequences. It suits problems like part-of-speech tagging, where the whole sequence of hidden states matters rather than a single one.
How are the parameters of a hidden Markov model learned?
No tractable algorithm is known that solves it exactly. A local maximum likelihood estimate can be found efficiently with the Baum-Welch algorithm or the Baldi-Chauvin algorithm. Baum-Welch is a special case of expectation-maximization.
Who described hidden Markov models and when did speech recognition begin using them?
Leonard E. Baum and other authors described them in a series of statistical papers in the second half of the 1960s. Speech recognition was among the first applications, starting in the mid-1970s.
Where else are hidden Markov models used?
Uses include bioinformatics, gene prediction, handwriting recognition, machine translation, computational finance, neuroscience, cryptanalysis, speech synthesis and speech recognition, including Siri. Other uses are protein folding, transportation forecasting and solar irradiance variability.
All sources
60 references cited across the entry
- 3Modeling Form for On-line Following of Musical PerformancesB. Pardo et al. — July 2005
- 5JournalModeling linkage disequilibrium and identifying recombination hotspots using single-nucleotide polymorphism data.N Li et al. — December 2003
- 6JournalChromHMM: automating chromatin-state discovery and characterizationJason Ernst et al. — March 2012
- 7JournalA tutorial on Hidden Markov Models and selected applications in speech recognitionLawrence R. Rabiner — February 1989
- 8JournalError statistics of hidden Markov model and hidden Boltzmann model resultsLee A. Newberg — 2009
- 10JournalA variational Bayesian methodology for hidden Markov models utilizing Student's-t mixturesSotirios P. Chatzis et al. — 2011
- 11JournalParallel Optimization of Sparse Portfolios with AR-HMMsI. Róbert Sipos et al. — 2016
- 12JournalA novel corporate credit rating system based on Student's-t hidden Markov modelsAnastasios Petropoulos et al. — 2016
- 13JournalSolving Ion Channel Kinetics with the QuB SoftwareChristopher Nicolai — 2013
- 14JournalSpatiotemporally Resolved Multivariate Pattern Analysis for M/EEGCameron Higgins et al. — 2022
- 15JournalMotor-like neural dynamics in two parietal areas during arm reachingS. Diomedi et al. — 2021-10-01
- 16BookThe Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our WorldPedro Domingos — Basic Books — 2015
- 18JournalThe Complex Folding Network of Single Calmodulin MoleculesJ. Stigler et al. — 2011
- 19JournalA Hidden Markov Model Variant for Sequence ClassificationS. Blasiak et al. — 2011
- 20JournalHunting for metamorphic enginesW. Wong et al. — 2006
- 21JournalDNA motif elucidation using belief propagationK. -C. Wong et al. — 2013
- 22JournalImproved Optical Multiplexing with Temporal DNA BarcodesShalin Shah et al. — 2019-05-17
- 23JournalProgramming Temporal DNA Barcodes for Single-Molecule FingerprintingShalin Shah et al. — 2019-04-10
- 25Modeling and Forecasting the Evolution of Preferences over Time: A Hidden Markov Model of Travel BehaviorFeraz El Zarwi — May 2011
- 26JournalThe stochastic two-state solar irradiance model (STSIM)H. Morf — Feb 1998
- 27JournalA Markov-chain probability distribution mixture approach to the clear-sky indexJ. Munkhammar et al. — Aug 2018
- 28JournalAn N-state Markov-chain mixture distribution model of the clear-sky indexJ. Munkhammar et al. — Oct 2018
- 29JournalStatistical Inference for Probabilistic Functions of Finite State Markov ChainsL. E. Baum — 1966
- 30JournalAn inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecologyL. E. Baum et al. — 1967
- 31JournalGrowth transformations for functions on manifoldsL. E. Baum — 1968
- 32JournalA Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov ChainsL. E. Baum et al. — 1970
- 33JournalAn Inequality and Associated Maximization Technique in Statistical Estimation of Probabilistic Functions of a Markov ProcessL.E. Baum — 1972
- 34JournalThe DRAGON system—An overviewJ. Baker — 1975
- 35JournalDesign of a linguistic statistical decoder for the recognition of continuous speechF. Jelinek et al. — 1975
- 36BookHidden Markov Models for Speech RecognitionXuedong Huang et al. — Edinburgh University Press — 1990
- 37BookSpoken Language ProcessingXuedong Huang et al. — Prentice Hall — 2001
- 38BookGrammatical Inference and ApplicationsRafael C. Carrasco et al. — Springer — 1994
- 39JournalMaximum Likelihood Alignment of DNA SequencesM. Bishop and E. Thompson — 1986
- 40JournalInference in finite state space non parametric Hidden Markov Models and applicationsE. Gassiat et al. — 2016-01-01
- 41JournalFundamental Limits for Learning Hidden Markov Model ParametersKweku Abraham et al. — March 2023
- 42Beal, Matthew J., Zoubin Ghahramani, and Carl Edward Rasmussen. "The infinite hidden Markov model." Advances in neural information processing systems 14 (2002): 577-584.
- 43Teh, Yee Whye, et al. "Hierarchical dirichlet processes." Journal of the American Statistical Association 101.476 (2006).
- 44JournalFactorial Hidden Markov ModelsZoubin Ghahramani et al. — 1997
- 45JournalChaı̂nes de Markov TripletWojciech Pieczynski — 2002
- 46JournalMultisensor triplet Markov chains and theory of evidenceWojciech Pieczynski — 2007
- 47JournalDempster-Shafer fusion of multisensor signals in nonstationary Markovian contextM. Y. Boudaren et al. — 2012
- 49JournalUnsupervised segmentation of random discrete data hidden with switching noise distributionsM. Y. Boudaren et al. — October 2012
- 51JournalA Reservoir-Driven Non-Stationary Hidden Markov ModelSotirios P. Chatzis et al. — 2012
- 52M. Lukosevicius, H. Jaeger (2009) Reservoir computing approaches to recurrent neural network training, Computer Science Review 3: 127–149.
- 53Azeraf, E., Monfrini, E., & Pieczynski, W. (2023). Equivalence between LC-CRF and HMM, and Discriminative Computing of HMM-Based MPM and MAP. Algorithms, 16(3), 173.
- 54Azeraf, E., Monfrini, E., Vignon, E., & Pieczynski, W. (2020). Hidden markov chains, entropic forward-backward, and part-of-speech tagging. arXiv preprint arXiv:2005.10629.
- 55Azeraf, E., Monfrini, E., & Pieczynski, W. (2022). Deriving discriminative classifiers from generative models. arXiv preprint arXiv:2201.00844.
- 56Ng, A., & Jordan, M. (2001). On discriminative vs. generative classifiers: A comparison of logistic regression and naive bayes. Advances in neural information processing systems, 14.
- 57BookPanel Analysis: Latent Probability Models for Attitude and Behaviour ProcessesL. M. Wiggins — Elsevier — 1973
- 58BookLatent Markov models for longitudinal dataF. Bartolucci et al. — Chapman and Hall/CRC — 2013
- 60Hidden Markov processes in the context of symbolic dynamicsMike Boyle et al. — 2010-01-13