Content deleted Content added
m →Weather guessing game: format code |
Finnusertop (talk | contribs) m ce refs |
||
Line 4:
A '''hidden Markov model''' ('''HMM''') is a [[Statistical model|statistical]] [[Markov model]] in which the system being [[mathematical model|model]]ed is assumed to be a [[Markov process]] — call it <math> X </math> — with unobservable ("''hidden''") states. As part of the definition, HMM requires that there be an observable process <math> Y </math> whose outcomes are "influenced" by the outcomes of <math>X</math> in a known way. Since <math> X </math> cannot be observed directly, the goal is to learn about <math>X</math> by observing <math> Y. </math> 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 not affect the outcome of <math> Y </math> at <math> t=t_0. </math>
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]]
== Definition ==
Line 157:
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 |url=https://www.scribd.com/doc/6369908/Growth-Functions-for-Transformations-on-Manifolds |access-date=28 November 2011 |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 |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>
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>
== Extensions ==
Line 164:
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"
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.
Line 174:
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).
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}}</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.], 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">[http://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">[http://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 alternative 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.
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 obtain a nonstationary HMM the transition probabilities of which evolve over time in a manner that is inferred from the data itself, as opposed to some unrealistic ad-hoc model of temporal evolution.
| |||