hidden Markov model
In plain wordsA model of a sequence, such as speech or DNA, in which hidden states — say, the words being spoken — change step by step at random, and each state gives off signals that can be observed, such as sounds.
A probabilistic graphical modelprobabilistic graphical model, n.: A way of describing how many uncertain quantities depend on one another by drawing them as a network, which makes it practical for a computer to reason about all of them together. of sequences in which an unobserved state evolves as a Markov chainMarkov chain, n.: A chance-driven process that moves between states without memory: the odds of its next move are set by where it is, never by the path that led there. Forecasting tomorrow's weather from today's alone is a simple example. — the next state depends only on the current one, through transition probabilities — and each state emits an observation according to an emission distribution. Three standard computations make it practical: the forward algorithm gives the probability of an observation sequence; the Viterbi algorithmViterbi algorithm, n.: A method that finds the likeliest hidden sequence behind some observations — such as each word's grammatical role in a sentence — by keeping only the best path to each point instead of trying every combination. finds the most likely sequence of hidden states; and the Baum–Welch algorithm, an instance of the expectation–maximization algorithmexpectation–maximization algorithm, n.: A method for fitting a model when some information is hidden: guess the hidden parts using the current model, refit the model as if those guesses were right, and repeat until nothing changes. built on forward–backward probabilities, learns the parameters from unlabeled sequences. All run in time linear in sequence length and quadratic in the number of states. HMMs, usually with Gaussian-mixture emissions, were the backbone of speech recognitionspeech recognition, n.: Technology that turns spoken words into written text, as when a phone transcribes a voice message or captions appear automatically under a video. from the 1980s until deep networks displaced them in the 2010s, and they remain standard in bioinformatics (gene finding, protein-family profiles) and in some taggingpart-of-speech tagging, n.: Labeling each word in a sentence with its grammatical role — noun, verb, adjective and so on — as in 'Time (noun) flies (verb) like (preposition) an arrow'. and handwriting systems.
The gene finder is a hidden Markov model whose hidden states are exon, intron and intergenic sequence.
Origin
Developed by Leonard E. Baum and colleagues at the Institute for Defense Analyses in papers from 1966 onward, which spoke of 'probabilistic functions of Markov chains'; the name 'hidden Markov model' was in use by 1980, though its coiner is not established. James Baker at Carnegie Mellon and Frederick Jelinek's group at IBM applied HMMs to speech recognition in the 1970s, and Lawrence Rabiner's 1989 tutorial spread them widely.
Related
- Markov chainMarkov chain, n.: A chance-driven process that moves between states without memory: the odds of its next move are set by where it is, never by the path that led there. Forecasting tomorrow's weather from today's alone is a simple example.
- Viterbi algorithmViterbi algorithm, n.: A method that finds the likeliest hidden sequence behind some observations — such as each word's grammatical role in a sentence — by keeping only the best path to each point instead of trying every combination.
- expectation–maximization algorithmexpectation–maximization algorithm, n.: A method for fitting a model when some information is hidden: guess the hidden parts using the current model, refit the model as if those guesses were right, and repeat until nothing changes.
- conditional random fieldconditional random field, n.: A statistical method for labeling every item in a sequence, such as marking each word in a sentence as a name, a place or an ordinary word, by choosing all the labels together rather than one at a time.
- speech recognitionspeech recognition, n.: Technology that turns spoken words into written text, as when a phone transcribes a voice message or captions appear automatically under a video.
- probabilistic graphical modelprobabilistic graphical model, n.: A way of describing how many uncertain quantities depend on one another by drawing them as a network, which makes it practical for a computer to reason about all of them together.
- Bayesian networkBayesian network, n.: A diagram of causes and effects with probabilities attached — say, how rain and a sprinkler can each make grass wet — that lets a computer update its beliefs about hidden causes when it sees evidence.
- conditional random fieldconditional random field, n.: A statistical method for labeling every item in a sequence, such as marking each word in a sentence as a name, a place or an ordinary word, by choosing all the labels together rather than one at a time.
- recurrent neural networkrecurrent neural network, n.: A neural network that reads a sequence, such as a sentence or an audio clip, one piece at a time, carrying a running summary forward so that what came earlier can shape how later pieces are understood.
Sources
- Baum, L. E. & Petrie, T. (1966). Statistical Inference for Probabilistic Functions of Finite State Markov Chains. Annals of Mathematical Statistics 37(6), 1554–1563.
- Rabiner, L. R. (1989). A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition. Proceedings of the IEEE 77(2), 257–286.
Mentioned in
speech recognitionspeech recognition, n.: Technology that turns spoken words into written text, as when a phone transcribes a voice message or captions appear automatically under a video., text-to-speechtext-to-speech, n.: Technology that reads written text aloud in a computer-generated voice, used in screen readers, voice assistants, audiobooks and navigation apps., Bayesian networkBayesian network, n.: A diagram of causes and effects with probabilities attached — say, how rain and a sprinkler can each make grass wet — that lets a computer update its beliefs about hidden causes when it sees evidence., conditional probabilityconditional probability, n.: The chance of something once you already know that something else is true — for example, the chance of rain given that the sky is cloudy., conditional random fieldconditional random field, n.: A statistical method for labeling every item in a sequence, such as marking each word in a sentence as a name, a place or an ordinary word, by choosing all the labels together rather than one at a time., dynamic programmingdynamic programming, n.: A problem-solving method that breaks a big problem into smaller overlapping pieces, solves each piece once and reuses the answers — the basis for computing the best long-term strategy step by step., expectation–maximization algorithmexpectation–maximization algorithm, n.: A method for fitting a model when some information is hidden: guess the hidden parts using the current model, refit the model as if those guesses were right, and repeat until nothing changes., Gaussian mixture modelGaussian mixture model, n.: A model that explains data as coming from several overlapping bell-shaped clouds, working out where each cloud sits, how spread out it is, and how likely each point is to belong to it., Kalman filterKalman filter, n.: A method that keeps a running best guess of something you cannot measure exactly, such as a vehicle's position, by blending predictions from a motion model with noisy sensor readings., Markov chainMarkov chain, n.: A chance-driven process that moves between states without memory: the odds of its next move are set by where it is, never by the path that led there. Forecasting tomorrow's weather from today's alone is a simple example., Markov propertyMarkov property, n.: The assumption that the future depends only on the present situation, not on how you got there — so knowing the current state is enough to predict what happens next., named-entity recognitionnamed-entity recognition, n.: Software that spots names and similar expressions in text and labels each by type: in 'Maria flew from Lagos to Paris on Monday', it marks a person, two cities and a date., n-gram modeln-gram model, n.: An early type of language model that predicts the next word from just the few words before it, using counts of how often each word followed those words in a large collection of text., probabilistic graphical modelprobabilistic graphical model, n.: A way of describing how many uncertain quantities depend on one another by drawing them as a network, which makes it practical for a computer to reason about all of them together., Viterbi algorithmViterbi algorithm, n.: A method that finds the likeliest hidden sequence behind some observations — such as each word's grammatical role in a sentence — by keeping only the best path to each point instead of trying every combination., Frederick JelinekFrederick Jelinek, prop. n.: A Czech-born American engineer who led IBM's speech-recognition research and made statistics learned from data, rather than hand-written grammar rules, the basis of language technology., MFCCMFCC, abbr.: A short list of numbers, usually about 13, that summarizes the shape of a brief slice of sound in a way that mimics human hearing; for decades the standard input to speech recognizers., partially observable Markov decision processpartially observable Markov decision process, n.: A version of the standard decision-making model in which the decision-maker cannot see the whole situation — like a poker player who cannot see other hands — and must act on clues and memory., part-of-speech taggingpart-of-speech tagging, n.: Labeling each word in a sentence with its grammatical role — noun, verb, adjective and so on — as in 'Time (noun) flies (verb) like (preposition) an arrow'.