Hidden Markov model: Difference between revisions

Revision as of 15:08, 26 August 2024

Latest revision as of 09:02, 26 August 2025

(14 intermediate revisions by 11 users not shown)

Line 1:

{{shortShort description|Statistical Markov model}}

{{goodGood article}}

A '''hidden Markov model''' ('''HMM''') is a [[Markov model]] in which the observations are dependent on a latent (or "''hidden"'') [[Markov process]] (referred to as <math> X </math>). An HMM requires that there be an observable process <math> Y </math> whose outcomes depend on the outcomes of <math>X</math> in a known way. Since <math> X </math> cannot be observed directly, the goal is to learn about state of <math>X</math> by observing <math> Y. </math>. By definition of being a Markov model, an HMM has an additional requirement that the outcome of <math> Y </math> at time <math> t = t_0 </math> must be "influenced" exclusively by the outcome of <math> X </math> at <math> t = t_0 </math> and that the outcomes of <math> X </math> and <math> Y </math> at <math> t < t_0 </math> must be conditionally independent of <math> Y </math> at <math> t=t_0 </math> given <math> X </math> at time <math> t = t_0. </math>. Estimation of the parameters in an HMM can be performed using [[Maximummaximum likelihood estimation|maximum likelihood]]. For linear chain HMMs, the [[Baum–Welch algorithm]] can be used to estimate the parameters.

Hidden Markov models are known for their applications to [[thermodynamics]], [[statistical mechanics]], [[physics]], [[chemistry]], [[economics]], [[finance]], [[signal processing]], [[information theory]], [[pattern recognition]]—such as [[speech recognition|speech]],<ref>{{cite web | url=https://scholar.google.com/scholar?q=levinson+hidden+markov+model+tutorial&hl=en&as_sdt=0&as_vis=1&oi=scholart | title=Google Scholar }}</ref> [[handwriting recognition|handwriting]], [[gesture recognition]],<ref>Thad Starner, Alex Pentland. [http://www.cc.gatech.edu/~thad/p/031_10_SL/real-time-asl-recognition-from%20video-using-hmm-ISCV95.pdf Real-Time American Sign Language Visual Recognition From Video Using Hidden Markov Models]. Master's Thesis, MIT, Feb 1995, Program in Media Arts</ref> [[part-of-speech tagging]], musical score following,<ref>B. Pardo and W. Birmingham. [http://www.cs.northwestern.edu/~pardo/publications/pardo-birmingham-aaai-05.pdf Modeling Form for On-line Following of Musical Performances] {{Webarchive|url=https://web.archive.org/web/20120206123155/http://www.cs.northwestern.edu/~pardo/publications/pardo-birmingham-aaai-05.pdf |date=2012-02-06 }}. AAAI-05 Proc., July 2005.</ref> [[partial discharge]]s<ref>Satish L, Gururaj BI (April 2003). "[https://ieeexplore.ieee.org/document/212242/;jsessionid=F905BAE29AD4A7BD5B228B4734549DA2?arnumber=212242 Use of hidden Markov models for partial discharge pattern classification]". ''[[IEEE Transactions on Dielectrics and Electrical Insulation]]''.</ref> and [[bioinformatics]].<ref>{{cite journal|last1=Li|first1=N|last2=Stephens|first2=M|title=Modeling linkage disequilibrium and identifying recombination hotspots using single-nucleotide polymorphism data.|journal=Genetics|date=December 2003|volume=165|issue=4|pages=2213–33|doi=10.1093/genetics/165.4.2213|pmid=14704198|pmc=1462870}}</ref><ref>{{cite journal |last1=Ernst |first1=Jason |last2=Kellis |first2=Manolis |title=ChromHMM: automating chromatin-state discovery and characterization |journal=Nature Methods |date=March 2012 |volume=9 |issue=3 |pages=215–216 |doi=10.1038/nmeth.1906 |pmid=22373907 |url= |pmc=3577932 }}</ref>

== Definition ==

Line 10:

* <math>X_n</math> is a [[Markov process]] whose behavior is not directly observable ("hidden");

* <math>\operatorname{\mathbf{P}}\bigl(Y_n \in A\ \bigl|\ X_1=x_1,\ldots,X_n=x_n\bigr)=\operatorname{\mathbf{P}}\bigl(Y_n \in A\ \bigl|\ X_n=x_n\bigr),</math>,

:for every <math>n\geq 1,</math>, <math>x_1,\ldots, x_n,</math>, and every [[Borel set]] <math>A</math>.

Let <math>X_t</math> and <math>Y_t</math> be continuous-time stochastic processes. The pair <math>(X_t,Y_t)</math> is a ''hidden Markov model'' if

Line 18:

*<math>\operatorname{\mathbf{P}}(Y_{t_0} \in A \mid \{X_t \in B_t\}_{ t\leq t_0}) = \operatorname{\mathbf{P}}(Y_{t_0} \in A \mid X_{t_0} \in B_{t_0})</math>,

:for every <math> t_0, </math>, every Borel set <math> A, </math>, and every family of Borel sets <math> \{B_t\}_{t \leq t_0}. </math>.

=== Terminology ===

Line 27:

[[File:HiddenMarkovModel.svg|right|thumb|300px|

Figure 1. Probabilistic parameters of a hidden Markov model (example)<br />

''X'' — states<br />

''y'' — possible observations<br />

''a'' — state transition probabilities<br />

''b'' — output probabilities]]

In its discrete form, a hidden Markov process can be visualized as a generalization of the [[urn problem]] with replacement (where each item from the urn is returned to the original urn before the next step).<ref>{{cite journal |author=Lawrence R. Rabiner |author-link=Lawrence Rabiner |date=February 1989 |title=A tutorial on Hidden Markov Models and selected applications in speech recognition |url=http://www.ece.ucsb.edu/Faculty/Rabiner/ece259/Reprints/tutorial%20on%20hmm%20and%20applications.pdf |journal=Proceedings of the IEEE |volume=77 |issue=2 |pages=257–286 |citeseerx=10.1.1.381.3454 |doi=10.1109/5.18626 |s2cid=13618539}} [httphttps://www.cs.cornell.edu/courses/cs481/2004fa/rabiner.pdf]</ref> Consider this example: in a room that is not visible to an observer there is a genie. The room contains urns X1, X2, X3, ... each of which contains a known mix of balls, with each ball having a unique label y1, y2, y3, ... . The genie chooses an urn in that room and randomly draws a ball from that urn. It then puts the ball onto a conveyor belt, where the observer can observe the sequence of the balls but not the sequence of urns from which they were drawn. The genie has some procedure to choose urns; the choice of the urn for the ''n''-th ball depends only upon a random number and the choice of the urn for the {{nowrap|(''n''&nbsp; −&nbsp; 1)-th}} ball. The choice of urn does not directly depend on the urns chosen before this single previous urn; therefore, this is called a [[Markov process]]. It can be described by the upper part of Figure 1.

The Markov process itself cannot be observed, only the sequence of labeled balls, thus this arrangement is called a "''hidden Markov process"''. This is illustrated by the lower part of the diagram shown in Figure 1, where one can see that balls y1, y2, y3, y4 can be drawn at each state. Even if the observer knows the composition of the urns and has just observed a sequence of three balls, ''e.g.'' y1, y2 and y3 on the conveyor belt, the observer still cannot be ''sure'' which urn (''i.e.'', at which state) the genie has drawn the third ball from. However, the observer can work out other information, such as the likelihood that the third ball came from each of the urns.

=== Weather guessing game ===

Line 66:

== Structural architecture ==

The diagram below shows the general architecture of an instantiated HMM. Each oval shape represents a random variable that can adopt any of a number of values. The random variable ''x''(''t'') is the hidden state at time {{mvar|t}} (with the model from the above diagram, {{nowrap|''x''(''t'')&nbsp; ∈&nbsp; {&nbsp; ''x''₁,&nbsp; ''x''₂,&nbsp; ''x''₃&nbsp; })}}. The random variable ''y''(''t'') is the observation at time {{mvar|t}} (with {{nowrap|''y''(''t'')&nbsp; ∈&nbsp; {&nbsp; ''y''₁,&nbsp; ''y''₂,&nbsp; ''y''₃,&nbsp; ''y''₄&nbsp; })}}. The arrows in the diagram (often called a [[Trellis (graph)|trellis diagram]]) denote conditional dependencies.

From the diagram, it is clear that the [[conditional probability distribution]] of the hidden variable ''x''(''t'') at time {{mvar|t}}, given the values of the hidden variable {{mvar|x}} at all times, depends ''only'' on the value of the hidden variable {{nowrap|''x''(''t''&nbsp; −&nbsp; 1)}}; the values at time {{nowrap|''t''&nbsp; −&nbsp; 2}} and before have no influence. This is called the [[Markov property]]. Similarly, the value of the observed variable ''y''(''t'') only depends on only the value of the hidden variable ''x''(''t'') (both at time {{mvar|t}}).

In the standard type of hidden Markov model considered here, the state space of the hidden variables is discrete, while the observations themselves can either be discrete (typically generated from a [[categorical distribution]]) or continuous (typically from a [[Gaussian distribution]]). The parameters of a hidden Markov model are of two types, ''transition probabilities'' and ''emission probabilities'' (also known as ''output probabilities''). The transition probabilities control the way the hidden state at time {{mvar|t}} is chosen given the hidden state at time <math>t-1</math>.

The hidden state space is assumed to consist of one of {{mvar|N}} possible values, modelled as a categorical distribution. (See the section below on extensions for other possibilities.) This means that for each of the {{mvar|N}} possible states that a hidden variable at time {{mvar|t}} can be in, there is a transition probability from this state to each of the {{mvar|N}} possible states of the hidden variable at time <math>t+1</math>, for a total of <math>N^2</math> transition probabilities. Note that theThe set of transition probabilities for transitions from any given state must sum to 1. Thus, the <math>N \times N</math> matrix of transition probabilities is a [[Stochastic matrix|Markov matrix]]. Because any transition probability can be determined once the others are known, there are a total of <math>N(N-1)</math> transition parameters.

In addition, for each of the {{mvar|N}} possible states, there is a set of emission probabilities governing the distribution of the observed variable at a particular time given the state of the hidden variable at that time. The size of this set depends on the nature of the observed variable. For example, if the observed variable is discrete with {{mvar|M}} possible values, governed by a [[categorical distribution]], there will be <math>M-1</math> separate parameters, for a total of <math>N(M-1)</math> emission parameters over all hidden states. On the other hand, if the observed variable is an {{mvar|M}}-dimensional vector distributed according to an arbitrary [[multivariate Gaussian distribution]], there will be {{mvar|M}} parameters controlling the [[mean]]s and <math>\frac {M(M+1)} 2</math> parameters controlling the [[covariance matrix]], for a total of <math>N \left(M + \frac{M(M+1)}{2}\right) = \frac {NM(M+3)} 2 = O(NM^2)</math> emission parameters. (In such a case, unless the value of {{mvar|M}} is small, it may be more practical to restrict the nature of the covariances between individual elements of the observation vector, e.g. by assuming that the elements are independent of each other, or less restrictively, are independent of all but a fixed number of adjacent elements.)

[[File:hmm temporal bayesian net.svg|500px|center|Temporal evolution of a hidden Markov model]]

== Inference ==

[[File:HMMsequence.svg|thumb|400px|The state transition and output probabilities of an HMM are indicated by the line opacity in the upper part of the diagram. Given that we have observed the output sequence is observed in the lower part of the diagram, weinterest may be interestedoccurs in the most likely sequence of states that could have produced it. Based on the arrows that are present in the diagram, the following state sequences are candidates:<br />

5 3 2 5 3 2<br />

4 3 2 5 3 2<br />

3 1 2 5 3 2<br />

WeThe canmost findlikely thesequence mostcan likelybe sequencefound by evaluating the joint probability of both the state sequence and the observations for each case (simply by multiplying the probability values, which here correspond to the opacities of the arrows involved). In general, this type of problem (i.e., finding the most likely explanation for an observation sequence) can be solved efficiently using the [[Viterbi algorithm]].]]

Several [[inference]] problems are associated with hidden Markov models, as outlined below.

=== Probability of an observed sequence ===

The task is to compute in a best way, given the parameters of the model, the probability of a particular output sequence. This requires summation over all possible state sequences:

The probability of observing a sequence

: <math>Y=y(0), y(1),\dots,y(L-1)\, </math>

of length ''L'' is given by

:<math>P(Y)=\sum_{X}P(Y\mid X)P(X),\,</math>

where the sum runs over all possible hidden-node sequences

: <math>X=x(0), x(1), \dots, x(L-1).\, </math>

Applying the principle of [[dynamic programming]], this problem, too, can be handled efficiently using the [[forward algorithm]].

=== Probability of the latent variables ===

A number of related tasks ask about the probability of one or more of the latent variables, given the model's parameters and a sequence of observations <math>y(1),\dots,y(t).</math>.

==== Filtering ====

The task is to compute, given the model's parameters and a sequence of observations, the distribution over hidden states of the last latent variable at the end of the sequence, i.e. to compute <math>P(x(t)\ |\mid y(1),\dots,y(t))</math>. This task is used when the sequence of latent variables is thought of as the underlying states that a process moves through at a sequence of points in time, with corresponding observations at each point. Then, it is natural to ask about the state of the process at the end.

This problem can be handled efficiently using the [[forward algorithm]]. An example is when the algorithm is applied to a Hidden Markov Network to determine <math>\mathrm{P}\big( h_t \ |mid v_{1:t} \big)</math>.

==== Smoothing ====

This is similar to filtering but asks about the distribution of a latent variable somewhere in the middle of a sequence, i.e. to compute <math>P(x(k)\ |\mid y(1), \dots, y(t))</math> for some <math>k < t</math>. From the perspective described above, this can be thought of as the probability distribution over hidden states for a point in time ''k'' in the past, relative to time ''t''.

The [[forward-backward algorithm]] is a good method for computing the smoothed values for all hidden state variables.

==== Most likely explanation ====

The task, unlike the previous two, asks about the [[joint probability]] of the ''entire'' sequence of hidden states that generated a particular sequence of observations (see illustration on the right). This task is generally applicable when HMM's are applied to different sorts of problems from those for which the tasks of filtering and smoothing are applicable. An example is [[part-of-speech tagging]], where the hidden states represent the underlying [[Part-of-speech tagging|parts of speech]] corresponding to an observed sequence of words. In this case, what is of interest is the entire sequence of parts of speech, rather than simply the part of speech for a single word, as filtering or smoothing would compute.

This task requires finding a maximum over all possible state sequences, and can be solved efficiently by the [[Viterbi algorithm]].

=== Statistical significance ===

For some of the above problems, it may also be interesting to ask about [[statistical significance]]. What is the probability that a sequence drawn from some [[null distribution]] will have an HMM probability (in the case of the forward algorithm) or a maximum state sequence probability (in the case of the Viterbi algorithm) at least as large as that of a particular output sequence?<ref>{{Cite journal |last1=Newberg |first1=L. |doi=10.1186/1471-2105-10-212 |title=Error statistics of hidden Markov model and hidden Boltzmann model results |journal=BMC Bioinformatics |volume=10 |pagesarticle-number=212 |year=2009 |pmid=19589158 |pmc=2722652 |doi-access=free }} {{open access}}</ref> When an HMM is used to evaluate the relevance of a hypothesis for a particular output sequence, the statistical significance indicates the [[false positive rate]] associated with failing to reject the hypothesis for the output sequence.

== Learning ==

The parameter learning task in HMMs is to find, given an output sequence or a set of such sequences, the best set of state transition and emission probabilities. The task is usually to derive the [[maximum likelihood]] estimate of the parameters of the HMM given the set of output sequences. No tractable algorithm is known for solving this problem exactly, but a local maximum likelihood can be derived efficiently using the [[Baum–Welch algorithm]] or the Baldi–Chauvin algorithm. The [[Baum–Welch algorithm]] is a special case of the [[expectation-maximization algorithm]].

If the HMMs are used for time series prediction, more sophisticated Bayesian inference methods, like [[Markov chain Monte Carlo]] (MCMC) sampling are proven to be favorable over finding a single maximum likelihood model both in terms of accuracy and stability.<ref>Sipos, I. Róbert. ''Parallel stratified MCMC sampling of AR-HMMs for stochastic time series prediction''. In: Proceedings, 4th Stochastic Modeling Techniques and Data Analysis International Conference with Demographics Workshop (SMTDA2016), pp. 295-306. Valletta, 2016. [http://1drv.ms/b/s!ApL_0Av0YGDLglwEOv1aYAGbmQeL PDF]</ref> Since MCMC imposes significant computational burden, in cases where computational scalability is also of interest, one may alternatively resort to variational approximations to Bayesian inference, e.g.<ref>{{cite journal |url=http://users.iit.demokritos.gr/~dkosmo/downloads/patrec10/vbb10.pdf |doi=10.1016/j.patcog.2010.09.001 |volume=44 |issue=2 |title=A variational Bayesian methodology for hidden Markov models utilizing Student's-t mixtures |year=2011 |journal=Pattern Recognition |pages=295–306 |last1=Chatzis |first1=Sotirios P. |last2=Kosmopoulos |first2=Dimitrios I. |bibcode=2011PatRe..44..295C |citeseerx=10.1.1.629.6275 |access-date=2018-03-11 |archive-date=2011-04-01 |archive-url=https://web.archive.org/web/20110401184517/http://users.iit.demokritos.gr/~dkosmo/downloads/patrec10/vbb10.pdf |url-status=dead }}</ref> Indeed, approximate variational inference offers computational efficiency comparable to expectation-maximization, while yielding an accuracy profile only slightly inferior to exact MCMC-type Bayesian inference.

== Applications ==

Line 130:

HMMs can be applied in many fields where the goal is to recover a data sequence that is not immediately observable (but other data that depend on the sequence are). Applications include:

* [[Computational finance]]<ref>{{cite journal |doi=10.1007/s10614-016-9579-y |volume=49 |issue=4 |title=Parallel Optimization of Sparse Portfolios with AR-HMMs |year=2016 |journal=Computational Economics |pages=563–578 |last1=Sipos |first1=I. Róbert |last2=Ceffer |first2=Attila |last3=Levendovszky |first3=János|s2cid=61882456 }}</ref><ref>{{cite journal |doi=10.1016/j.eswa.2016.01.015 |volume=53 |title=A novel corporate credit rating system based on Student's-t hidden Markov models |year=2016 |journal=Expert Systems with Applications |pages=87–105 |last1=Petropoulos |first1=Anastasios |last2=Chatzis |first2=Sotirios P. |last3=Xanthopoulos |first3=Stylianos}}</ref>

* [[Single-molecule experiment|Single-molecule kinetic analysis]]<ref>{{cite journal |last1=Nicolai |first1=Christopher |date=2013 |doi=10.1142/S1793048013300053 |title=SOLVINGSolving IONIon CHANNELChannel KINETICSKinetics WITHwith THEthe QuB SOFTWARESoftware |journal=Biophysical Reviews and Letters |date=2013 |volume=8 |issue=3n04 |pages=191–211 |first=CHRISTOPHER |last=NICOLAI}}</ref>

* [[Neuroscience]]<ref>{{cite journal |doi=10.1002/hbm.25835 |title=Spatiotemporally Resolved Multivariate Pattern Analysis for M/EEG |journal=Human Brain Mapping |date=2022 |last1=Higgins |first1=Cameron |last2=Vidaurre |first2=Diego |last3=Kolling |first3=Nils |last4=Liu |first4=Yunzhe |last5=Behrens | first5=Tim | last6=Woolrich | first6=Mark |volume=43 |issue=10 |pages=3062–3085 |pmid=35302683 |pmc=9188977 }}</ref><ref>{{Cite journal |last1=Diomedi |first1=S. |last2=Vaccari |first2=F. E. |last3=Galletti |first3=C. |last4=Hadjidimitrakis |first4=K. |last5=Fattori |first5=P. |date=2021-10-01 |title=Motor-like neural dynamics in two parietal areas during arm reaching |url=https://www.sciencedirect.com/science/article/pii/S0301008221001301 |journal=Progress in Neurobiology |language=en |volume=205 |pagesarticle-number=102116 |doi=10.1016/j.pneurobio.2021.102116 |pmid=34217822 |issn=0301-0082|hdl=11585/834094 |s2cid=235703641 |hdl-access=free }}</ref>

* [[Cryptanalysis]]

* [[Speech recognition]], including [[Siri]]<ref>{{cite book|last1=Domingos|first1=Pedro|title=The Master Algorithm: How the Quest for the Ultimate Learning Machine Will Remake Our World|url=https://archive.org/details/masteralgorithmh0000domi|url-access=registration|date=2015|publisher=Basic Books|isbn=9780465061921|page=[https://archive.org/details/masteralgorithmh0000domi/page/37 37]|language=en}}</ref>

Line 145:

* [[Time series|Time series analysis]]

* [[Activity recognition]]

* [[Protein folding]]<ref>{{Cite journal |last1=Stigler |first1=J. |last2=Ziegler |first2=F. |last3=Gieseke |first3=A. |last4=Gebhardt |first4=J. C. M. |last5=Rief |first5=M. |title=The Complex Folding Network of Single Calmodulin Molecules |doi=10.1126/science.1207598 |journal=[[Science (journal)|Science]] |volume=334 |issue=6055 |pages=512–516 |year=2011 |pmid=22034433 |bibcode=2011Sci...334..512S |s2cid=5502662 }}</ref>

* Sequence classification<ref>{{Cite journal |last1=Blasiak |first1=S. |last2=Rangwala |first2=H. |title=A Hidden Markov Model Variant for Sequence Classification |journal=IJCAI Proceedings-International Joint Conference on Artificial Intelligence |volume=22 |pages=1192 |year=2011 }}</ref>

* [[Metamorphic virus detection]]<ref>{{Cite journal |last1=Wong |first1=W. |last2=Stamp |first2=M. |doi=10.1007/s11416-006-0028-7 |title=Hunting for metamorphic engines |journal=Journal in Computer Virology |volume=2 |issue=3 |pages=211–229 |year=2006 |s2cid=8116065 }}</ref>

* [[Sequence motif]] discovery (DNA and proteins)<ref>{{Cite journal |last1=Wong |first1=K. -C. |last2=Chan |first2=T. -M. |last3=Peng |first3=C. |last4=Li |first4=Y. |last5=Zhang |first5=Z. |title=DNA motif elucidation using belief propagation |doi=10.1093/nar/gkt574 |journal=Nucleic Acids Research |volume=41 |issue=16 |pages=e153 |year=2013 |pmid=23814189 |pmc=3763557}}</ref>

* DNA hybridization kinetics<ref>{{Cite journal|last1=Shah|first1=Shalin|last2=Dubey|first2=Abhishek K.|last3=Reif|first3=John|date=2019-05-17|title=Improved Optical Multiplexing with Temporal DNA Barcodes|journal=ACS Synthetic Biology|volume=8|issue=5|pages=1100–1111|doi=10.1021/acssynbio.9b00010|pmid=30951289|s2cid=96448257}}</ref><ref>{{Cite journal|last1=Shah|first1=Shalin|last2=Dubey|first2=Abhishek K.|last3=Reif|first3=John|date=2019-04-10|title=Programming Temporal DNA Barcodes for Single-Molecule Fingerprinting|journal=Nano Letters|volume=19|issue=4|pages=2668–2673|doi=10.1021/acs.nanolett.9b00590|pmid=30896178|bibcode=2019NanoL..19.2668S|s2cid=84841635|issn=1530-6984}}</ref>

*[[Chromatin]] state discovery<ref>{{Cite web|url=http://compbio.mit.edu/ChromHMM/|title=ChromHMM: Chromatin state discovery and characterization|website=compbio.mit.edu|access-date=2018-08-01}}</ref>

*[[Transportation forecasting]]<ref>{{Cite arXiv|title=Modeling and Forecasting the Evolution of Preferences over Time: A Hidden Markov Model of Travel Behavior|last=El Zarwi|first=Feraz|date=May 2011|eprint = 1707.09133|class = stat.AP}}</ref>

*[[Solar irradiance]] variability <ref>{{Cite journal|title=The stochastic two-state solar irradiance model (STSIM)|last1=Morf|first1=H.|journal=Solar Energy|volume=62|issue=2|pages=101–112|date=Feb 1998|bibcode=1998SoEn...62..101M|doi=10.1016/S0038-092X(98)00004-8}}</ref><ref>{{Cite journal|title=A Markov-chain probability distribution mixture approach to the clear-sky index|last1=Munkhammar|first1=J.|last2=Widén|first2=J.|journal = Solar Energy|date=Aug 2018|volume=170|pages=174–183|bibcode=2018SoEn..170..174M|doi=10.1016/j.solener.2018.05.055|s2cid=125867684}}</ref><ref>{{Cite journal|title=An N-state Markov-chain mixture distribution model of the clear-sky index|last1=Munkhammar|first1=J.|last2=Widén|first2=J.|journal=Solar Energy|volume=173|pages=487–495|date=Oct 2018|bibcode=2018SoEn..173..487M|doi=10.1016/j.solener.2018.07.056|s2cid=125538244}}</ref>

== History ==

Hidden Markov models were described in a series of statistical papers by [[Leonard E. Baum]] and other authors in the second half of the 1960s.<ref>{{cite journal |last=Baum |first=L. E. |author2=Petrie, T. |title=Statistical Inference for Probabilistic Functions of Finite State Markov Chains |journal=The Annals of Mathematical Statistics |year=1966 |volume=37 |issue=6 |pages=1554–1563 |doi=10.1214/aoms/1177699147|doi-access=free }}</ref><ref>{{Cite journal |last1=Baum |first1=L. E. |last2=Eagon |first2=J. A. |doi=10.1090/S0002-9904-1967-11751-8 |title=An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology |journal=[[Bulletin of the American Mathematical Society]] |volume=73 |issue=3 |pages=360 |year=1967 |zbl=0157.11101 |url=http://projecteuclid.org/euclid.bams/1183528841 |doi-access=free }}</ref><ref>{{cite journal |last=Baum |first=L. E. |author2=Sell, G. R. |title=Growth transformations for functions on manifolds |journal=Pacific Journal of Mathematics |year=1968 |volume=27 |issue=2 |pages=211–227 |doi=10.2140/pjm.1968.27.211 |doi-access=free }}</ref><ref>{{Cite journal |last1=Baum |first1=L. E. |author-link1=Leonard E. Baum |last2=Petrie |first2=T. |last3=Soules |first3=G. |last4=Weiss |first4=N. |title=A Maximization Technique Occurring in the Statistical Analysis of Probabilistic Functions of Markov Chains |doi=10.1214/aoms/1177697196 |journal=[[The Annals of Mathematical Statistics]] |volume=41 |issue=1 |pages=164–171 |year=1970 |jstor=2239727 |zbl=0188.49603 |mr=287613 |doi-access=free }}</ref><ref>{{cite journal |last=Baum |first=L.E. |title=An Inequality and Associated Maximization Technique in Statistical Estimation of Probabilistic Functions of a Markov Process |journal=Inequalities |year=1972 |volume=3 |pages=1–8}}</ref> One of the first applications of HMMs was [[speech recognition]], starting in the mid-1970s.<ref>{{Cite journal |last1=Baker |first1=J. |author-link1=James K. Baker |doi=10.1109/TASSP.1975.1162650 |title=The DRAGON system—An overview |journal=IEEE Transactions on Acoustics, Speech, and Signal Processing |volume=23 |pages=24–29 |year=1975 }}</ref><ref>{{Cite journal |last1=Jelinek |first1=F. |last2=Bahl |first2=L. |last3=Mercer |first3=R. |doi=10.1109/TIT.1975.1055384 |title=Design of a linguistic statistical decoder for the recognition of continuous speech |journal=[[IEEE Transactions on Information Theory]] |volume=21 |issue=3 |pages=250 |year=1975 }}</ref><ref>{{cite book |title=Hidden Markov Models for Speech Recognition |url=https://archive.org/details/hiddenmarkovmode0000huan |publisher=Edinburgh University Press |year=1990 |isbn=978-0-7486-0162-2 |author1=Xuedong Huang |author2=M. Jack |author3=Y. Ariki |author-link1=Xuedong Huang}}</ref><ref>{{cite book |title=Spoken Language Processing |publisher=Prentice Hall |year=2001 |isbn=978-0-13-022616-7 |author1=Xuedong Huang |author2=Alex Acero |author3=Hsiao-Wuen Hon |author-link1=Xuedong Huang}}</ref> From the linguistics point of view, hidden Markov models are equivalent to stochastic regular grammar.<ref>{{Cite book |last1=Carrasco |first1=Rafael C. |last2=Oncina |first2=Jose |date=1994 |editor-last=Carrasco |editor-first=Rafael C. |editor2-last=Oncina |editor2-first=Jose |chapter=Learning stochastic regular grammars by means of a state merging method |chapter-url=https://link.springer.com/chapter/10.1007/3-540-58473-0_144 |title=Grammatical Inference and Applications |series=Lecture Notes in Computer Science |volume=862 |language=en |___location=Berlin, Heidelberg |publisher=Springer |pages=139–152 |doi=10.1007/3-540-58473-0_144 |isbn=978-3-540-48985-6}}</ref>

In the second half of the 1980s, HMMs began to be applied to the analysis of biological sequences,<ref>{{cite journal |doi=10.1016/0022-2836(86)90289-5 |author=M. Bishop and E. Thompson |title=Maximum Likelihood Alignment of DNA Sequences |journal=[[Journal of Molecular Biology]] |volume=190 |issue=2 |pages=159–165 |year=1986 |pmid=3641921}} {{subscription required}} {{closed access}}</ref> in particular [[DNA]]. Since then, they have become ubiquitous in the field of [[bioinformatics]].<ref name=durbin>{{Durbin 1998|mode=cs1}}</ref>

Line 163:

In the hidden Markov models considered above, the state space of the hidden variables is discrete, while the observations themselves can either be discrete (typically generated from a [[categorical distribution]]) or continuous (typically from a [[Gaussian distribution]]). Hidden Markov models can also be generalized to allow continuous state spaces. Examples of such models are those where the Markov process over hidden variables is a [[linear dynamical system]], with a linear relationship among related variables and where all hidden and observed variables follow a [[Gaussian distribution]]. In simple cases, such as the linear dynamical system just mentioned, exact inference is tractable (in this case, using the [[Kalman filter]]); however, in general, exact inference in HMMs with continuous latent variables is infeasible, and approximate methods must be used, such as the [[extended Kalman filter]] or the [[particle filter]].

Nowadays, inference in hidden Markov models is performed in [[Nonparametric statistics|nonparametric]] settings, where the dependency structure enables [[identifiability]] of the model<ref>{{Cite journal |last1=Gassiat |first1=E. |last2=Cleynen |first2=A. |last3=Robin |first3=S. |date=2016-01-01 |title=Inference in finite state space non parametric Hidden Markov Models and applications |url=https://doi.org/10.1007/s11222-014-9523-8 |journal=Statistics and Computing |language=en |volume=26 |issue=1 |pages=61–71 |doi=10.1007/s11222-014-9523-8 |issn=1573-1375|url-access=subscription }}</ref> and the learnability limits are still under exploration.<ref>{{Cite journal |last1=Abraham |first1=Kweku |last2=Gassiat |first2=Elisabeth |last3=Naulet |first3=Zacharie |date=March 2023 |title=Fundamental Limits for Learning Hidden Markov Model Parameters |url=https://ieeexplore.ieee.org/document/9917566 |journal=IEEE Transactions on Information Theory |volume=69 |issue=3 |pages=1777–1794 |doi=10.1109/TIT.2022.3213429 |arxiv=2106.12936 |bibcode=2023ITIT...69.1777A |issn=0018-9448}}</ref>

=== Bayesian modeling of the transitions probabilities ===

Hidden Markov models are [[generative model]]s, in which the [[joint distribution]] of observations and hidden states, or equivalently both the [[prior distribution]] of hidden states (the ''transition probabilities'') and [[conditional distribution]] of observations given states (the ''emission probabilities''), is modeled. The above algorithms implicitly assume a [[Uniform distribution (continuous)|uniform]] prior distribution over the transition probabilities. However, it is also possible to create hidden Markov models with other types of prior distributions. An obvious candidate, given the categorical distribution of the transition probabilities, is the [[Dirichlet distribution]], which is the [[conjugate prior]] distribution of the categorical distribution. Typically, a symmetric Dirichlet distribution is chosen, reflecting ignorance about which states are inherently more likely than others. The single parameter of this distribution (termed the ''concentration parameter'') controls the relative density or sparseness of the resulting transition matrix. A choice of 1 yields a uniform distribution. Values greater than 1 produce a dense matrix, in which the transition probabilities between pairs of states are likely to be nearly equal. Values less than 1 result in a sparse matrix in which, for each given source state, only a small number of destination states have non-negligible transition probabilities. It is also possible to use a two-level prior Dirichlet distribution, in which one Dirichlet distribution (the upper distribution) governs the parameters of another Dirichlet distribution (the lower distribution), which in turn governs the transition probabilities. The upper distribution governs the overall distribution of states, determining how likely each state is to occur; its concentration parameter determines the density or sparseness of states. Such a two-level prior distribution, where both concentration parameters are set to produce sparse distributions, might be useful for example in [[unsupervised learning|unsupervised]] [[part-of-speech tagging]], where some parts of speech occur much more commonly than others; learning algorithms that assume a uniform prior distribution generally perform poorly on this task. The parameters of models of this sort, with non-uniform prior distributions, can be learned using [[Gibbs sampling]] or extended versions of the [[expectation-maximization algorithm]].

An extension of the previously described hidden Markov models with [[Dirichlet distribution|Dirichlet]] priors uses a [[Dirichlet process]] in place of a Dirichlet distribution. This type of model allows for an unknown and potentially infinite number of states. It is common to use a two-level Dirichlet process, similar to the previously described model with two levels of Dirichlet distributions. Such a model is called a ''hierarchical Dirichlet process hidden Markov model'', or ''HDP-HMM'' for short. It was originally described under the name "Infinite Hidden Markov Model"<ref>Beal, Matthew J., Zoubin Ghahramani, and Carl Edward Rasmussen. "The infinite hidden Markov model." Advances in neural information processing systems 14 (2002): 577-584.</ref> and was further formalized in "Hierarchical Dirichlet Processes".<ref>Teh, Yee Whye, et al. "Hierarchical dirichlet processes." Journal of the American Statistical Association 101.476 (2006).</ref>

=== Discriminative approach ===

A different type of extension uses a [[discriminative model]] in place of the [[generative model]] of standard HMMs. This type of model directly models the conditional distribution of the hidden states given the observations, rather than modeling the joint distribution. An example of this model is the so-called ''[[maximum entropy Markov model]]'' (MEMM), which models the conditional distribution of the states using [[logistic regression]] (also known as a "[[Maximum entropy probability distribution|maximum entropy]] model"). The advantage of this type of model is that arbitrary features (i.e. functions) of the observations can be modeled, allowing ___domain-specific knowledge of the problem at hand to be injected into the model. Models of this sort are not limited to modeling direct dependencies between a hidden state and its associated observation; rather, features of nearby observations, of combinations of the associated observation and nearby observations, or in fact of arbitrary observations at any distance from a given hidden state can be included in the process used to determine the value of a hidden state. Furthermore, there is no need for these features to be [[statistically independent]] of each other, as would be the case if such features were used in a generative model. Finally, arbitrary features over pairs of adjacent hidden states can be used rather than simple transition probabilities. The disadvantages of such models are: (1) The types of prior distributions that can be placed on hidden states are severely limited; (2) It is not possible to predict the probability of seeing an arbitrary observation. This second limitation is often not an issue in practice, since many common usages of HMM's do not require such predictive probabilities.

A variant of the previously described discriminative model is the linear-chain [[conditional random field]]. This uses an undirected graphical model (aka [[Markov random field]]) rather than the directed graphical models of MEMM's and similar models. The advantage of this type of model is that it does not suffer from the so-called ''label bias'' problem of MEMM's, and thus may make more accurate predictions. The disadvantage is that training can be slower than for MEMM's.

=== Other extensions ===

Yet another variant is the ''factorial hidden Markov model'', which allows for a single observation to be conditioned on the corresponding hidden variables of a set of <math>K</math> independent Markov chains, rather than a single Markov chain. It is equivalent to a single HMM, with <math>N^K</math> states (assuming there are <math>N</math> states for each chain), and therefore, learning in such a model is difficult: for a sequence of length <math>T</math>, a straightforward Viterbi algorithm has complexity <math>O(N^{2K} \, T)</math>. To find an exact solution, a junction tree algorithm could be used, but it results in an <math>O(N^{K+1} \, K \, T)</math> complexity. In practice, approximate techniques, such as variational approaches, could be used.<ref>{{cite journal |last1=Ghahramani |first1=Zoubin |author-link1=Zoubin Ghahramani |last2=Jordan |first2=Michael I. |author-link2=Michael I. Jordan |title=Factorial Hidden Markov Models |journal=[[Machine Learning (journal)|Machine Learning]] |year=1997 |volume=29 |issue=2/3 |pages=245–273 |doi=10.1023/A:1007425814087|doi-access=free }}</ref>

All of the above models can be extended to allow for more distant dependencies among hidden states, e.g. allowing for a given state to be dependent on the previous two or three states rather than a single previous state; i.e. the transition probabilities are extended to encompass sets of three or four adjacent states (or in general <math>K</math> adjacent states). The disadvantage of such models is that dynamic-programming algorithms for training them have an <math>O(N^K \, T)</math> running time, for <math>K</math> adjacent states and <math>T</math> total observations (i.e. a length-<math>T</math> Markov chain). This extension has been widely used in [[bioinformatics]], in the modeling of [[Nucleic acid sequence|DNA sequences]].

Another recent extension is the ''triplet Markov model'',<ref name="TMM">{{cite journal |doi=10.1016/S1631-073X(02)02462-7 |volume=335 |issue=3 |title=Chaı̂nes de Markov Triplet |year=2002 |journal=Comptes Rendus Mathématique |pages=275–278 |last1=Pieczynski |first1=Wojciech|url=http://www.numdam.org/item/10.1016/S1631-073X(02)02462-7.pdf }}</ref> in which an auxiliary underlying process is added to model some data specificities. Many variants of this model have been proposed. One should also mention the interesting link that has been established between the ''theory of evidence'' and the ''triplet Markov models''<ref name="TMMEV">{{cite journal |doi=10.1016/j.ijar.2006.05.001 |volume=45 |title=Multisensor triplet Markov chains and theory of evidence |year=2007 |journal=International Journal of Approximate Reasoning |pages=1–16 |last1=Pieczynski |first1=Wojciech|doi-access=free }}</ref> and which allows to fuse data in Markovian context<ref name="JASP">[http://asp.eurasipjournals.com/content/pdf/1687-6180-2012-134.pdf Boudaren et al.] {{Webarchive|url=https://web.archive.org/web/20140311164443/http://asp.eurasipjournals.com/content/pdf/1687-6180-2012-134.pdf |date=2014-03-11 }}, M. Y. Boudaren, E. Monfrini, W. Pieczynski, and A. Aissani, Dempster-Shafer fusion of multisensor signals in nonstationary Markovian context, EURASIP Journal on Advances in Signal Processing, No. 134, 2012.</ref> and to model nonstationary data.<ref name="TSP">[https://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=1468502&contentType=Journals+%26+Magazines&searchField%3DSearch_All%26queryText%3Dlanchantin+pieczynski Lanchantin et al.], P. Lanchantin and W. Pieczynski, Unsupervised restoration of hidden non stationary Markov chain using evidential priors, IEEE Transactions on Signal Processing, Vol. 53, No. 8, pp. 3091-3098, 2005.</ref><ref name="SPL">[https://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6244854&contentType=Journals+%26+Magazines&searchField%3DSearch_All%26queryText%3Dboudaren Boudaren et al.], M. Y. Boudaren, E. Monfrini, and W. Pieczynski, Unsupervised segmentation of random discrete data hidden with switching noise distributions, IEEE Signal Processing Letters, Vol. 19, No. 10, pp. 619-622, October 2012.</ref> Note that alternativeAlternative multi-stream data fusion strategies have also been proposed in the recent literature, e.g.,<ref>Sotirios P. Chatzis, Dimitrios Kosmopoulos, [https://ieeexplore.ieee.org/document/6164251/ "Visual Workflow Recognition Using a Variational Bayesian Treatment of Multistream Fused Hidden Markov Models,"] IEEE Transactions on Circuits and Systems for Video Technology, vol. 22, no. 7, pp. 1076-1086, July 2012.</ref>

Finally, a different rationale towards addressing the problem of modeling nonstationary data by means of hidden Markov models was suggested in 2012.<ref name="Reservoir-HMM">{{cite journal |last1=Chatzis |first1=Sotirios P. |last2=Demiris |first2=Yiannis |year=2012 |title=A Reservoir-Driven Non-Stationary Hidden Markov Model |journal=Pattern Recognition |volume=45 |issue=11 |pages=3985–3996 |doi=10.1016/j.patcog.2012.04.018|bibcode=2012PatRe..45.3985C |hdl=10044/1/12611 |hdl-access=free }}</ref> It consists in employing a small recurrent neural network (RNN), specifically a reservoir network,<ref>M. Lukosevicius, H. Jaeger (2009) Reservoir computing approaches to recurrent neural network training, Computer Science Review '''3''': 127–149.</ref> to capture the evolution of the temporal dynamics in the observed data. This information, encoded in the form of a high-dimensional vector, is used as a conditioning variable of the HMM state transition probabilities. Under such a setup, we eventually obtainis obtained a nonstationary HMM, the transition probabilities of which evolve over time in a manner that is inferred from the data itself, asin opposedcontrast to some unrealistic ad-hoc model of temporal evolution.

In 2023, two innovative algorithms were introduced for the Hidden Markov Model. These algorithms enable the computation of the posterior distribution of the HMM without the necessity of explicitly modeling the joint distribution, utilizing only the conditional distributions.<ref>Azeraf, 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.</ref><ref>Azeraf, E., Monfrini, E., Vignon, E., & Pieczynski, W. (2020). Hidden markov chains, entropic forward-backward, and part-of-speech tagging. arXiv preprint arXiv:2005.10629.</ref> Unlike traditional methods such as the Forward-Backward and Viterbi algorithms, which require knowledge of the joint law of the HMM and can be computationally intensive to learn, the Discriminative Forward-Backward and Discriminative Viterbi algorithms circumvent the need for the observation's law.<ref>Azeraf, E., Monfrini, E., & Pieczynski, W. (2022). Deriving discriminative classifiers from generative models. arXiv preprint arXiv:2201.00844.</ref><ref>Ng, A., & Jordan, M. (2001). On discriminative vs. generative classifiers: A comparison of logistic regression and naive bayes. Advances in neural information processing systems, 14.</ref> This breakthrough allows the HMM to be applied as a discriminative model, offering a more efficient and versatile approach to leveraging Hidden Markov Models in various applications.

Line 190:

== Measure theory ==

{{See also|Subshift of finite type}}

[[File:Blackwell_HMM_example.png|thumb|193x193px|The hidden part of a hidden Markov model, whose observable states is non-Markovian.]]

Given a Markov transition matrix and an invariant distribution on the states, we can impose a probability measure can be imposed on the set of subshifts. For example, consider the Markov chain given on the left on the states <math>A, B_1, B_2 </math>, with invariant distribution <math>\pi = (2/7, 4/7, 1/7) </math>. If weBy "forget"ignoring the distinction between <math>B_1, B_2</math>, we project this space of subshifts is projected on <math>A, B_1, B_2 </math> into another space of subshifts on <math>A, B </math>, and this projection also projects the probability measure down to a probability measure on the subshifts on <math>A, B </math>.

The curious thing is that the probability measure on the subshifts on <math>A, B </math> is not created by a Markov chain on <math>A, B </math>, not even multiple orders. Intuitively, this is because if one observes a long sequence of <math>B^n</math>, then one would become increasingly sure that the <math>\Pr(A |\mid B^n) \to \frac 23 </math>, meaning that the observable part of the system can be affected by something infinitely in the past.<ref name=":0">''[https://web.archive.org/web/20221005013617/https://petersen.web.unc.edu/wp-content/uploads/sites/17054/2018/04/Main.pdf Sofic Measures: Characterizations of Hidden Markov Chains by Linear Algebra, Formal Languages, and Symbolic Dynamics]'' - Karl Petersen, Mathematics 210, Spring 2006, University of North Carolina at Chapel Hill</ref><ref name=":1">{{Citation |last1=Boyle |first1=Mike |title=Hidden Markov processes in the context of symbolic dynamics |date=2010-01-13 |last2=Petersen |first2=Karl|arxiv=0907.1858 }}</ref>

Conversely, there exists a space of subshifts on 6 symbols, projected to subshifts on 2 symbols, such that any Markov measure on the smaller subshift has a preimage measure that is not Markov of any order (Exampleexample 2.6 <ref name=":1" />).

== See also ==

Line 206:

* [[Conditional random field]]

* [[Estimation theory]]

* [[HH-suite]] (HHpred /, HHsearch]]) free server and software for protein sequence searching

* [[HMMER]], a free hidden Markov model program for protein sequence analysis

* [[Hidden Bernoulli model]]

Line 214:

* [[Sequential dynamical system]]

* [[Stochastic context-free grammar]]

* [[Time Seriesseries]] Analysisanalysis

* [[Variable-order Markov model]]

* [[Viterbi algorithm]]

Line 226:

=== Concepts ===

* {{cite journal |last1=Teif |first1=V. B. |last2=Rippe |first2=K. |year=2010 |title=Statistical–mechanical lattice models for protein–DNA binding in chromatin |journal=J. Phys.: Condens. Matter |volume=22 |issue=41 |page=414105 |doi=10.1088/0953-8984/22/41/414105 |pmid=21386588 |arxiv=1004.5514|bibcode=2010JPCM...22O4105T |s2cid=103345 }}

* [http://www.cs.sjsu.edu/~stamp/RUA/HMM.pdf A Revealing Introduction to Hidden Markov Models] by Mark Stamp, San Jose State University.

* [https://web.archive.org/web/20120415032315/http://www.ee.washington.edu/research/guptalab/publications/EMbookChenGupta2010.pdf Fitting HMM's with expectation-maximization – complete derivation]

* [http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html A step-by-step tutorial on HMMs] {{Webarchive|url=https://web.archive.org/web/20170813231824/http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html |date=2017-08-13 }} ''(University of Leeds)''

* [httphttps://www.cs.brown.edu/research/ai/dynamics/tutorial/Documents/HiddenMarkovModels.html Hidden Markov Models] ''(an exposition using basic mathematics)''

* [http://jedlik.phy.bme.hu/~gerjanos/HMM/node2.html Hidden Markov Models] ''(by Narada Warakagoda)''

* Hidden Markov Models: Fundamentals and Applications [http://www.eecis.udel.edu/~lliao/cis841s06/hmmtutorialpart1.pdf Part 1], [http://www.eecis.udel.edu/~lliao/cis841s06/hmmtutorialpart2.pdf Part 2] ''(by V. Petrushin)''