Hidden Markov model

A hidden Markov model (HMM) is a statistical model for sequential data in which an unobserved sequence of states generates observable outputs. The hidden states follow a Markov chain, while each observation is drawn from a distribution associated with its current state. An HMM therefore describes both how an underlying system changes and how those changes produce measurements. It is used in statistics, machine learning, and time-series analysis when the underlying states cannot be observed directly. (cs.ubc.ca)

Mathematical structure

In the standard finite-state, discrete-time HMM, the hidden random variable $Z_t$ takes one of $K$ possible values, and $X_t$ denotes the observation at position $t$. The hidden sequence is a stochastic process satisfying the first-order Markov assumption:

The observation assumption is conditional independence: given the complete hidden sequence, observations are independent, and the distribution of $X_t$ depends only on $Z_t$. These assumptions concern the hidden process and conditional observations; the observed sequence itself need not be a first-order Markov chain. (web.stanford.edu)

A time-homogeneous model has three principal components:

• Initial distribution: $\pi_i=P(Z_1=i)$.
• Transition matrix: $a_{ij}=P(Z_{t+1}=j\mid Z_t=i)$.
• Emission distributions: $b_i(x)=p(X_t=x\mid Z_t=i)$.

Each transition row sums to one. Emissions may describe discrete symbols, continuous measurements, or vectors. Continuous emissions can use a normal distribution or a Gaussian mixture model; in that case, $b_i(x)$ denotes a density rather than a point probability. (cs.ubc.ca)

For parameters $\theta$, the joint distribution factors as

This makes an HMM a generative model: it specifies how to generate both states and observations. Its dependency structure can also be represented as a chain-structured Bayesian network. (web.stanford.edu)

Inference and decoding

Three classical computational problems are distinguished: evaluating an observation sequence, estimating its hidden states, and learning model parameters. Directly enumerating all $K^T$ state sequences is generally impractical. The chain structure instead permits efficient dynamic programming. (cs.ubc.ca)

The forward algorithm computes the observation likelihood by summing over hidden paths. Define $\alpha_t(j)=p(x_{1:t},Z_t=j\mid\theta)$. Then

The likelihood is $\sum_j\alpha_T(j)$. For a dense transition matrix, the recursion requires $O(TK^2)$ time, excluding emission-evaluation costs. Scaling intermediate quantities or using logarithmic arithmetic prevents numerical underflow in long sequences. (cs.ubc.ca)

The forward–backward algorithm combines forward quantities with backward quantities describing subsequent observations. It yields posterior state probabilities $P(Z_t=j\mid x_{1:T})$. Filtering conditions on observations available up to the current position; smoothing also incorporates later observations. Both quantify uncertainty rather than selecting only one state path. (cs.ubc.ca)

The Viterbi algorithm instead finds the single most probable complete hidden-state sequence. It replaces summation with maximization and stores predecessor choices for traceback. This global decoding differs from independently selecting the most probable state at each position: marginal choices need not form the most probable path and can even violate transition constraints. (web.stanford.edu)

Parameter estimation

When hidden-state labels accompany the training data, supervised learning can estimate discrete transition and emission probabilities from normalized counts. When only observations are available, unsupervised learning commonly uses the Baum–Welch algorithm, an HMM-specific form of the expectation–maximization algorithm. (web.stanford.edu)

In its expectation step, forward–backward inference computes expected state occupancies and transition counts. Its maximization step updates parameters using these expectations. Under exact updates, the observed-data likelihood does not decrease, but maximum likelihood estimation can reach a local rather than global optimum. Initialization consequently affects the fitted result. For continuous emissions, updates also estimate the parameters of the chosen density family. (cs.ubc.ca)

Applications

In speech recognition, HMM states can represent stages of speech sounds, with acoustic feature vectors serving as observations. Left-to-right transition structures encode progression through a sound while allowing variable duration through self-transitions. This separates sequential organization from the statistical description of acoustic measurements. (cs.ubc.ca)

In natural language processing, an HMM can treat grammatical categories as hidden states and words as observations. In biological sequence analysis, profile HMMs describe position-specific sequence patterns, using match, insertion, and deletion states to represent conserved positions and gaps. They support searches for related protein and DNA sequences. Here, the sequence index represents position rather than elapsed time. (web.stanford.edu)

Assumptions and extensions

A standard HMM summarizes the relevant hidden history through its current state and assumes conditionally independent emissions. These restrictions can be inadequate when observations retain dependencies not explained by that state. State-space design and emission distributions therefore determine which structure the model can represent. (cs.ubc.ca)

For a nonabsorbing state $i$, a constant self-transition probability implies a geometrically distributed uninterrupted residence time:

The hidden semi-Markov model replaces this implicit duration mechanism with explicit duration distributions. It can represent residence times whose probability of ending depends on how long the system has already occupied the state, while retaining a hidden-state description of sequential observations. (cs.ubc.ca)