Hidden Markov model

A Hidden Markov model combines an unobserved Markov chain $Z_1,\dots ,Z_T$ with observations $O_1,\dots ,O_T$. Given the whole hidden-state path, the observations have conditional independence, and the conditional distribution of $O_t$ depends only on $Z_t$. The state-transition assumption and this emission assumption are separate parts of the model.^[ref]

For a time-homogeneous model with a finite hidden state space and discrete observations, write ${\pi }_i=P(Z_1=i)$, $a_{ij}=P(Z_{t+1}=j\mid Z_t=i)$ and $b_i(o)=P(O_t=o\mid Z_t=i)$ for the emission probabilities. The joint probability mass function factors asFor continuous observations, appropriate probability density functions replace the emission probability mass functions.

For example, a hidden state can describe whether a machine is working normally or has a fault, while a noisy sensor emits a positive or negative signal. Both states may emit a positive signal, with different probabilities; one observation therefore need not identify the state. Summing the factorization over hidden paths gives the observation likelihood. The forward algorithm reuses partial sums to compute it, and the backward algorithm helps infer hidden-state posterior probabilities. The observations alone need not satisfy the Markov property.

An emission probability in a Hidden Markov model is the probability of an observation conditional on its hidden state. For a finite observation alphabet, each state's emission probabilities sum to one. A match state can therefore emit several different characters, each with its own probability.

The backward algorithm computes suffix likelihoods in a Hidden Markov model. With ${\beta }_t(i)=P(o_{t+1},\dots ,o_T\mid Z_t=i)$, its recurrence is ${\beta }_t(i)={\sum }_j{a}_{ij}{b}_j(o_{t+1}){\beta }_{t+1}(j)$. Together with the forward algorithm, it gives posterior state probabilities proportional to ${\alpha }_t(i){\beta }_t(i)$. The terminal condition must include any explicit End-state transition.

The forward algorithm computes sequence likelihoods by summing over all hidden paths through a Hidden Markov model. For emitting states, ${\alpha }_t(i)=P(o_1,\dots ,o_t,Z_t=i)$ obeys ${\alpha }_{t+1}(j)=b_j(o_{t+1}){\sum }_i{\alpha }_t(i)a_{ij}$. It reuses partial sums rather than enumerating exponentially many state sequences. Silent states require additional transitions without consuming an observation. Scaling or log-sum-exp prevents floating-point underflow.

An insertion state in a profile hidden Markov model emits characters between successive match states. A bypass allows zero inserted characters and a self-transition allows several. Under a fixed loop probability $r<1$, the length of an insertion run conditional on entering has a geometric distribution on positive integers with exit probability $1-r$.

A match state in a profile hidden Markov model emits one aligned character at a particular profile position whenever it is visited. “Match” names its alignment role, not a requirement to emit one deterministic character or to match another sequence exactly.

A profile hidden Markov model represents the position-dependent structure of a sequence alignment using an ordered series of match states and optional insertion states, commonly with silent deletion states as well. An emitting state chooses one character from its probability mass function; transitions describe which profile position comes next. If deletion states are forbidden, an alignment column containing gaps cannot be a compulsory match state.

In a screening misclassification model, true disease states are latent and screen results are emissions. A cancer-free state may emit a positive result with a false positive rate, while a perfectly sensitive pre-clinical state always emits a positive result. Conditional independence of emissions given latent states is an additional model assumption, not a consequence of a marginal false-positive rate.