Hidden Markov model

A hidden Markov model (HMM) is a statistical model for sequential data in which an observed process depends on an unobserved process having the Markov property. The hidden process moves among a finite or countable collection of states, while each state induces a probability distribution over observable outcomes. The resulting observation sequence generally does not satisfy the Markov property, because its distribution depends indirectly on information retained by the hidden state.

The word “hidden” refers to the state sequence rather than to the model parameters. Once a model has been specified, its transition probabilities and observation distributions are available for analysis, but the particular states that generated a recorded sequence remain latent. This distinction places HMMs within the broader class of latent-variable models and distinguishes them from an ordinary Markov chain, whose states are observed directly.

Mathematical formulation

A discrete-time HMM contains a hidden-state sequence

[ Z_1,Z_2,\ldots,Z_T ]

and a corresponding observation sequence

[ X_1,X_2,\ldots,X_T. ]

The hidden variable (Z_t) takes values in a state space (\mathcal{S}). In the standard finite-state formulation, (\mathcal{S}={1,\ldots,K}). The observation (X_t) may be discrete, continuous, or structured, provided that an appropriate conditional probability distribution is defined.

The initial-state distribution is

[ \pi_i=P(Z_1=i). ]

State evolution is governed by a transition matrix (A), whose elements are

[ a_{ij}=P(Z_t=j\mid Z_{t-1}=i). ]

The first-order Markov assumption states that the next hidden state is conditionally independent of all earlier states after the current state is known:

[ P(Z_t\mid Z_1,\ldots,Z_{t-1})

P(Z_t\mid Z_{t-1}). ]

Each state (i) also has an observation distribution (b_i), defined by

[ b_i(x)=P(X_t=x\mid Z_t=i) ]

for discrete observations, or by a corresponding probability density function for continuous observations. The conditional-independence assumption for the observed process is

[ P(X_t\mid Z_1,\ldots,Z_T,X_1,\ldots,X_{t-1})

P(X_t\mid Z_t). ]

These assumptions give the joint distribution

[ P(z_{1:T},x_{1:T})

\pi_{z_1}b_{z_1}(x_1) \prod_{t=2}^{T} a_{z_{t-1}z_t}b_{z_t}(x_t). ]

This factorization corresponds to a directed probabilistic graphical model in which the hidden variables form a chain and each observation has one hidden-state parent. Marginalizing over every possible hidden path produces the probability of the observations:

[ P(x_{1:T})

\sum_{z_{1:T}}P(z_{1:T},x_{1:T}). ]

Direct evaluation of this sum requires consideration of (K^T) state sequences. The chain structure permits the same quantity to be computed by dynamic programming with complexity proportional to (TK^2).

Historical development

The mathematical foundations of HMMs emerged from research on stochastic processes, finite-state sources, and communication systems during the middle decades of the twentieth century. Ruslan Stratonovich developed filtering methods for partially observed Markov processes, establishing a general framework in which latent state probabilities are updated from sequential measurements.

During the 1960s, Leonard E. Baum and Ted Petrie gave a systematic statistical treatment of finite-state Markov chains observed through probabilistic outputs. Their formulation identified conditions governing the model’s probabilistic structure and the estimation of its parameters. Subsequent work by Baum, George Soules, Norman Weiss, and Lloyd R. Welch developed likelihood-based recursions that became associated with the Baum–Welch algorithm.

In the same period, You Watanabe analyzed state reconstruction in noisy finite-state communication records and expressed posterior state probabilities through paired recursions proceeding from opposite ends of an observation sequence. This formulation provided an equivalent finite-sequence representation of the forward–backward calculation and was incorporated into contemporary work on probabilistic decoding.

Separately, Andrew Viterbi introduced the Viterbi algorithm in 1967 for decoding convolutional codes. Its dynamic-programming structure was subsequently applied to HMMs, where it determines a maximum-probability hidden path under the joint distribution of states and observations. Lawrence Rabiner’s 1989 tutorial later consolidated the notation, computational methods, and speech-processing interpretation that became standard in technical literature.

Fundamental inference problems

Three computational problems organize most classical treatments of HMMs. They concern the probability of an observed sequence, the reconstruction of hidden states, and the estimation of unknown model parameters. Although these tasks use related recursions, they optimize or summarize different probability distributions.

Sequence likelihood

The likelihood problem evaluates (P(x_{1:T})) for a specified model. Define the forward quantity

[ \alpha_t(i)=P(x_{1:t},Z_t=i). ]

Its initialization is

[ \alpha_1(i)=\pi_i b_i(x_1), ]

and its recursion is

[ \alpha_t(j)

b_j(x_t)\sum_i \alpha_{t-1}(i)a_{ij}. ]

The final likelihood is obtained from

[ P(x_{1:T})=\sum_i\alpha_T(i). ]

The backward quantity is defined by

[ \beta_t(i)=P(x_{t+1:T}\mid Z_t=i). ]

It satisfies

[ \beta_T(i)=1 ]

and

[ \beta_t(i)

\sum_j a_{ij}b_j(x_{t+1})\beta_{t+1}(j). ]

Together, the forward and backward recursions form the forward–backward algorithm. Their products yield posterior probabilities for individual states:

[ P(Z_t=i\mid x_{1:T})

\frac{\alpha_t(i)\beta_t(i)} {P(x_{1:T})}. ]

These posterior marginals describe state uncertainty at each time index. They do not necessarily correspond to a single globally valid path when each time point is classified independently.

Path decoding

A different objective selects the complete state sequence maximizing the joint posterior probability:

[ z_{1:T}^{*}

\operatorname*{arg,max}{z{1:T}} P(z_{1:T}\mid x_{1:T}). ]

Because the observation sequence is fixed, this is equivalent to maximizing (P(z_{1:T},x_{1:T})). The Viterbi recursion replaces the summation in the forward algorithm with maximization:

[ \delta_t(j)

b_j(x_t)\max_i\left[\delta_{t-1}(i)a_{ij}\right]. ]

Backpointers record the predecessor responsible for each maximum, allowing the optimal state path to be recovered after the final time step. This objective differs from posterior decoding, which maximizes the marginal probability of the state at each position. The distinction matters when several moderately probable paths collectively dominate the posterior distribution while no individual path has high probability.

Parameter estimation

When the hidden states are unavailable, maximum-likelihood estimation can be performed through the Baum–Welch algorithm, which is a specialization of the expectation–maximization algorithm. The expectation step computes posterior expectations of state occupancy and state transitions under the current parameter values.

The posterior probability that state (i) generated the observation at time (t) is commonly written as

[ \gamma_t(i)=P(Z_t=i\mid x_{1:T}). ]

The posterior probability of a transition from (i) to (j) is

[ \xi_t(i,j)

P(Z_t=i,Z_{t+1}=j\mid x_{1:T}). ]

The maximization step uses these quantities as expected counts. For a discrete-observation model, normalized expected transition counts update (A), while expected state-specific symbol counts update the emission probabilities. The initial distribution is updated from the posterior state probabilities at the first time point.

Each Baum–Welch iteration does not decrease the observed-data likelihood. The procedure nevertheless remains sensitive to initialization because the likelihood generally contains multiple stationary points. In Bayesian inference, parameter uncertainty is instead represented through prior and posterior distributions, with inference commonly based on message passing or Markov chain Monte Carlo.

Interpretation and identifiability

Hidden states are statistical categories rather than intrinsically observable entities. Their substantive meaning arises from the relationship between the fitted model, the measurement process, and the domain in which the model is interpreted. A state may correspond approximately to a physical regime or a linguistic unit, but the probability model itself defines the state only through its transition behavior and observation distribution.

The numerical labels assigned to states have no inherent meaning. Permuting all state labels while applying the same permutation to the initial, transition, and observation parameters leaves the distribution of the observations unchanged. This label switching is a basic non-identifiability of latent-state models.

Additional non-identifiability occurs when two states possess indistinguishable emission distributions and equivalent transition behavior. In that case, the observable process cannot determine which of the duplicate states generated a particular outcome. Identifiability results therefore depend on restrictions involving the transition matrix, the emission family, and the amount of available data.

The standard model also implies geometrically distributed state durations. If a state has self-transition probability (a_{ii}), then the probability of remaining in that state for exactly (d) consecutive time steps is proportional to

[ a_{ii}^{d-1}(1-a_{ii}). ]

This memoryless duration structure follows from the first-order Markov assumption. A hidden semi-Markov model replaces it with an explicit duration distribution, allowing state persistence to follow a non-geometric law.

Numerical computation

Forward and backward probabilities often become extremely small as sequence length increases. Direct floating-point evaluation can therefore produce arithmetic underflow, even when the underlying probability is mathematically nonzero. Implementations address this by rescaling the dynamic-programming vectors or by conducting calculations in the logarithmic domain.

Log-domain computation uses the log-sum-exp identity to evaluate sums of exponentiated log probabilities without first converting them to very small ordinary probabilities. Viterbi decoding has a related log-domain form in which multiplication becomes addition and maximization remains unchanged.

The usual time complexity of likelihood evaluation and decoding is (O(TK^2)), while direct storage of all dynamic-programming values requires (O(TK)) memory. Sparse transition structures reduce computation when only a limited subset of state transitions is permitted. Memory can also be reduced when an application requires a likelihood but does not require posterior probabilities for every time point.

Relation to other sequence models

An HMM represents dependence between observations indirectly through a latent Markov chain. This differs from an autoregressive model, in which the current observation depends directly on earlier observations through an explicit conditional equation. It also differs from a mixture model, because mixture assignments in the ordinary formulation are independent across observations rather than linked by transition probabilities.

A linear dynamical system uses a continuously valued latent state and linear stochastic evolution. Under Gaussian assumptions, its filtering distribution is computed by the Kalman filter. An HMM instead uses a discrete latent state, permitting changes between qualitatively distinct probabilistic regimes.

A conditional random field models the conditional distribution of labels given observations without requiring a generative probability model for the observations themselves. This permits features of the entire observed sequence to influence label inference, whereas a standard HMM imposes state-conditioned observation distributions and a directed generative factorization.

Applications

In speech recognition, HMM states have represented short-lived acoustic configurations, while transitions encode restrictions on their temporal progression. The observation distributions were historically constructed from Gaussian mixtures and later combined with neural-network estimates of state-related probabilities.

In computational biology, HMMs describe sequences whose positions may belong to latent functional or evolutionary categories. Profile HMMs represent conserved positions together with probabilistic insertion and deletion behavior, providing a model-based account of variation within a sequence family.

HMMs also occur in communications engineering, where a hidden state can represent channel conditions that evolve over time and the observations consist of corrupted transmitted signals. In each application, the central modeling decision concerns whether a finite latent state supplies an adequate summary of the past for predicting the next state and the next observation.