Hidden Markov Models

Suppose you see the word sequence "time flies like an arrow." You must tag each word with its part of speech. The word "flies" could be a noun (insects) or a verb (moving quickly). The correct choice depends on invisible grammatical structure you cannot observe directly. You can only observe the words themselves. This is the central problem a Hidden Markov Model (HMM) solves. It recovers a hidden sequence of states from a visible sequence of observations. It uses probability to arbitrate ambiguity. HMMs formalize an idea that is everywhere in real systems. The data we observe is a noisy or indirect signal. It reflects some underlying process we actually care about. Speech recognizers observe acoustic frames but want phonemes. Part-of-speech taggers observe words but want syntactic categories. Bioinformatics pipelines observe DNA base pairs but want gene/intergenic boundaries. Before neural sequence models dominated, HMMs were the workhorse of statistical Part-of-Speech Tagging, speech recognition, and gene finding. They remain the cleanest illustration of generative sequence modeling with latent structure. This is a template that reappears in conditional random fields, structured perceptrons, and even the attention patterns of modern sequence-to-sequence models. The big picture is this: an HMM assumes a hidden Markov chain wanders through states over time. At each time step it emits a visible symbol. That symbol's distribution depends only on the current hidden state. Two probability tables define this process: transitions between states and emissions from states. Together with an initial-state distribution, they define a complete generative story for how observed sequences arise. Once you have that story, three classic questions become well-posed and computable. How likely is this observed sequence? What is the single best hidden path that explains it? How do we learn the transition and emission probabilities from data? This article builds the HMM from its independence assumptions upward. It gives exact pseudocode for the forward algorithm (probability of an observation sequence). It lays the groundwork for the decoding and learning algorithms that build directly on it. It ends with the historical context that connects Markov's original chains to modern statistical NLP. It previews how The Viterbi Algorithm and applications like Named-Entity Recognition extend these ideas.

Key takeaways

An HMM is a generative model: a hidden Markov chain of states emits observable symbols at each time step.
Two independence assumptions make it tractable: the Markov assumption (states) and the output-independence assumption (emissions).
Three parameter tables define it: initial state probabilities, transition probabilities, and emission probabilities.
The forward algorithm computes the likelihood of an observation sequence in $O(N^2T)$ time via dynamic programming, not brute-force $O(N^T)$ .
Decoding (finding the best hidden path) and learning (estimating parameters from data) reuse the same trellis structure, previewing the Viterbi algorithm and Baum-Welch/EM.
HMMs power classical part-of-speech tagging, speech recognition, and named-entity recognition, and remain a conceptual scaffold for later sequence models.

The core insight

An HMM models an observed sequence as generated by a hidden Markov chain whose current state alone determines both the next state and the current emission, and dynamic programming exploits this locality to make otherwise exponential computations run in polynomial time.

The idea

A Hidden Markov Model is a probabilistic generative model for sequences in which an unobserved (hidden) sequence of discrete states $q_1, q_2, \dots, q_T$ evolves over time, and each state $q_t$ produces a visible observation $o_t$ . The model is specified by three components: a set of states $S = \{s_1, \dots, s_N\}$ with an initial distribution $\pi$ over which state starts the chain; a transition matrix $A$ where $a_{ij} = P(q_{t+1}=s_j \mid q_t = s_i)$ gives the probability of moving from state $i$ to state $j$ ; and an emission matrix $B$ where $b_j(o_t) = P(o_t \mid q_t = s_j)$ gives the probability that state $j$ emits observation $o_t$ . Together $\lambda = (A, B, \pi)$ fully specifies the model. Two independence assumptions make the model tractable and give it its name. The Markov assumption says the probability of the next state depends only on the current state, not the entire history: $P(q_{t+1} \mid q_1, \dots, q_t) = P(q_{t+1} \mid q_t)$ . This is the same first-order Markov property used in N-gram Language Models, just applied to a hidden chain rather than an observed one. The output independence assumption says the current observation depends only on the current hidden state, not on neighboring observations or states: $P(o_t \mid q_1,\dots,q_T,o_1,\dots,o_T) = P(o_t \mid q_t)$ . These two assumptions factor an otherwise intractable joint distribution over long sequences into a product of small local terms, which is exactly what makes exact dynamic-programming algorithms possible. It helps to contrast an HMM with the tools you already know. A n-gram model treats the observed words themselves as a Markov chain — there's no hidden layer. Naive Bayes treats a document's words as conditionally independent given a single global class label, with no notion of a sequence of latent states evolving over time. The HMM generalizes both: it keeps a Naive-Bayes-style emission model (observations depend only on a hidden category) but replaces the single static label with a whole sequence of labels linked by a Markov chain — precisely the structure needed for tagging problems like Part-of-Speech Tagging, where the hidden "class" of a word (its tag) depends on the tag before it.

How it works

An HMM answers three canonical questions, traditionally called the "three problems" of HMMs (Rabiner's formulation): 1. Likelihood (evaluation). Given a model $\lambda = (A,B,\pi)$ and an observation sequence $O = o_1 \dots o_T$ , compute $P(O \mid \lambda)$ . Solved by the forward algorithm. 2. Decoding. Given $\lambda$ and $O$ , find the most probable hidden state sequence $Q^* = \arg\max_Q P(Q \mid O, \lambda)$ . Solved by the Viterbi algorithm (the subject of its own dedicated treatment). 3. Learning. Given only observation sequences (and a fixed state set), estimate $\lambda$ . Solved by Baum-Welch, an instance of Expectation-Maximization, which itself leans on the forward and a companion backward algorithm. This article works through the first problem in full detail, since it introduces the trellis structure and the recurrence that both later algorithms reuse almost verbatim.

Why brute force fails. The literal definition of likelihood is a sum over every possible hidden path:

P(O\mid\lambda) = \sum_{Q} P(O, Q \mid \lambda) = \sum_{Q} P(O\mid Q,\lambda)\,P(Q\mid\lambda)

There are $N^T$ possible hidden sequences of length $T$ over $N$ states, so naively evaluating every term costs $O(N^T \cdot T)$ time — exponential in the sequence length. For a part-of-speech tagger with 45 tags and a 20-word sentence, that is $45^{20}$ terms: computationally impossible.

The forward algorithm's key insight. Define the forward variable

\alpha_t(j) = P(o_1, o_2, \dots, o_t, \, q_t = s_j \mid \lambda)

the probability of seeing the observations up to time $t$ and being in state $j$ at time $t$ , summed over all the ways of getting there. Because of the Markov and output-independence assumptions, $\alpha_t(j)$ can be computed recursively from $\alpha_{t-1}(\cdot)$ alone — you never need to remember the full path, only the total probability mass funneling into each state at each time step. This is the dynamic-programming insight: overlapping subproblems (many paths share a common prefix) are computed once and reused, collapsing $N^T$ paths into a table of size $N \times T$ . The recurrence:

\alpha_1(j) = \pi_j \, b_j(o_1)

\alpha_t(j) = \left[\sum_{i=1}^{N} \alpha_{t-1}(i)\, a_{ij}\right] b_j(o_t), \qquad 2 \le t \le T

P(O\mid\lambda) = \sum_{j=1}^{N} \alpha_T(j)

``` ALGORITHM Forward(observations O[1..T], states S[1..N], A, B, pi) // A[i][j] = P(state j | state i); B[j][o] = P(observation o | state j) // alpha[t][j] = P(o_1..o_t, q_t = s_j | lambda) alpha <- array of size (T x N), initialized to 0 // --- Initialization step (t = 1) --- for j <- 1 to N: alpha[1][j] <- pi[j] B[j][ O[1] ] // --- Recursion step (t = 2 .. T) --- for t <- 2 to T: for j <- 1 to N: sum <- 0 for i <- 1 to N: sum <- sum + alpha[t-1][i] A[i][j] alpha[t][j] <- sum B[j][ O[t] ] // --- Termination step --- total <- 0 for j <- 1 to N: total <- total + alpha[T][j] return total, alpha // total = P(O | lambda) ``` Each cell `alpha[t][j]` is filled using only the previous column `alpha[t-1][]`, so the table can be built left to right, column by column — the same "fill a table using only already-filled entries" discipline used in edit distance and matrix chain multiplication. A companion backward algorithm defines $\beta_t(i) = P(o_{t+1},\dots,o_T \mid q_t = s_i, \lambda)$ via an analogous recursion run right-to-left; $\alpha$ and $\beta$ together are what Baum-Welch needs to estimate transition and emission counts during learning.

Figure

The HMM trellis: forward-algorithm dynamic programming over states × time

Complexity & correctness

Time complexity. The forward algorithm fills a table of $T$ columns and $N$ rows. Computing each cell `alpha[t][j]` requires summing over $N$ predecessor states, so each cell costs $O(N)$ work. Total cost:

O(N) \text{ per cell} \times N \text{ rows} \times T \text{ columns} = O(N^2 T)

This replaces the brute-force $O(N^T \cdot T)$ with a polynomial-time algorithm — for $N=45$ tags and $T=20$ words, roughly $45^2 \times 20 \approx 40{,}500$ operations instead of $45^{20}$ . This exponential-to-polynomial reduction is the entire reason HMMs were usable at scale for real corpora.

Space complexity. Storing the full table is $O(NT)$ . If only the final probability $P(O\mid\lambda)$ is needed (not the full table, e.g. for decoding), a rolling pair of columns suffices, reducing space to $O(N)$ — though the full table is normally kept because Viterbi and Baum-Welch need it.

Correctness argument. The proof is an induction on $t$ that formalizes the DP invariant. Claim: `alpha[t][j]` as computed by the recurrence equals $\alpha_t(j) = P(o_1,\dots,o_t, q_t=s_j \mid \lambda)$ . Base case ( $t=1$ ): $\alpha_1(j) = P(o_1, q_1 = s_j) = P(q_1=s_j)\,P(o_1 \mid q_1=s_j) = \pi_j b_j(o_1)$ by the chain rule and the output-independence assumption. This matches the initialization step exactly. Inductive step: assume `alpha[t-1][i]` correctly equals $\alpha_{t-1}(i)$ for every state $i$ . Partition the event $\{o_1,\dots,o_t, q_t=s_j\}$ by which state $q_{t-1}$ occupied at the previous step (the law of total probability over a partition of the sample space):

\alpha_t(j) = \sum_{i=1}^N P(o_1,\dots,o_{t-1}, q_{t-1}=s_i)\, P(q_t=s_j \mid q_{t-1}=s_i)\, P(o_t \mid q_t = s_j)

The middle factor uses the Markov assumption (the transition to $s_j$ depends only on $q_{t-1}$ , not the earlier observations or states), and the last factor uses the output-independence assumption (the emission depends only on $q_t$ ). Substituting $a_{ij}$ and $b_j(o_t)$ for these factors, and $\alpha_{t-1}(i)$ for the first factor (true by the inductive hypothesis), yields exactly the recurrence used by the algorithm:

\alpha_t(j) = \left[\sum_i \alpha_{t-1}(i)\, a_{ij}\right] b_j(o_t)

Termination: $P(O\mid\lambda) = \sum_j P(o_1,\dots,o_T, q_T = s_j) = \sum_j \alpha_T(j)$ , again by total probability over the final hidden state — exactly what the termination step computes. This completes the induction: every cell of the table is provably the quantity it claims to be, and no probability mass from any hidden path is double-counted or omitted, because the partition at each step is over a mutually exclusive, exhaustive set of predecessor states.

Honest tradeoffs. The polynomial-time gain is bought entirely by the Markov and output-independence assumptions; if a domain genuinely needs longer-range dependencies (a word's tag depending on a tag three positions back, or an emission depending on the surrounding words as in log-linear taggers), the plain HMM is a biased model — it will assign probability incorrectly, no matter how much data it sees. Discriminative alternatives (CRFs, neural taggers) relax these independence assumptions at the cost of losing the simple closed-form generative story and the exact EM-style unsupervised learning HMMs support.

Worked example

Consider a toy weather-inference HMM (the classic ice-cream illustration), reused here for tagging-flavored intuition: hidden states are `{HOT, COLD}`, and the observation each day is the number of ice creams eaten: `{1, 2, 3}`. Parameters:

	HOT	COLD
$\pi$ (initial)	0.8	0.2

$A$	→ HOT	→ COLD
HOT	0.7	0.3
COLD	0.4	0.6

$B$	1	2	3
HOT	0.2	0.4	0.4
COLD	0.5	0.4	0.1

Observation sequence: $O = (3, 1)$ — three ice creams, then one.

Step $t=1$ , $o_1 = 3$ :

\alpha_1(\text{HOT}) = \pi_{\text{HOT}} \cdot b_{\text{HOT}}(3) = 0.8 \times 0.4 = 0.32

\alpha_1(\text{COLD}) = \pi_{\text{COLD}} \cdot b_{\text{COLD}}(3) = 0.2 \times 0.1 = 0.02

Step $t=2$ , $o_2 = 1$ :

\alpha_2(\text{HOT}) = \big[\alpha_1(\text{HOT})a_{\text{HOT,HOT}} + \alpha_1(\text{COLD})a_{\text{COLD,HOT}}\big] \cdot b_{\text{HOT}}(1)

= [0.32 \times 0.7 + 0.02 \times 0.4] \times 0.2 = [0.224 + 0.008]\times 0.2 = 0.232 \times 0.2 = 0.0464

\alpha_2(\text{COLD}) = \big[\alpha_1(\text{HOT})a_{\text{HOT,COLD}} + \alpha_1(\text{COLD})a_{\text{COLD,COLD}}\big]\cdot b_{\text{COLD}}(1)

= [0.32\times 0.3 + 0.02\times 0.6]\times 0.5 = [0.096+0.012]\times 0.5 = 0.108\times 0.5 = 0.054

Termination:

P(O = (3,1) \mid \lambda) = \alpha_2(\text{HOT}) + \alpha_2(\text{COLD}) = 0.0464 + 0.054 = 0.1004

A trace table makes the DP structure explicit:

$t$	$o_t$	$\alpha_t(\text{HOT})$	$\alpha_t(\text{COLD})$
1	3	0.3200	0.0200
2	1	0.0464	0.0540

Notice that although observing "3 ice creams" makes day 1 look overwhelmingly HOT ( $0.32 \gg 0.02$ ), by day 2 — after observing only "1 ice cream" — the COLD path has caught up and overtaken the HOT path ( $0.054 > 0.0464$ ). This is exactly the ambiguity-resolving behavior an HMM is built for: no single day's observation determines the hidden state; the whole sequence, weighted through transition probabilities, does. Decoding (finding the single best hidden path, rather than summing over all of them) is precisely what the forthcoming The Viterbi Algorithm computes, by replacing each sum in the recurrence above with a max.

Common pitfalls & traps

Pitfall	Why it happens	Fix
Confusing forward probability with the best-path probability	$\alpha_t(j)$ sums over all paths reaching $s_j$ ; it is not the probability of the single best path	Use Viterbi's max-based recurrence when you need the single best hidden sequence, not the forward algorithm
Zero-probability emissions from unseen words/symbols	Maximum-likelihood emission estimates assign probability 0 to unseen observation symbols, collapsing the whole sequence probability to 0	Apply smoothing (e.g., add-one, Good-Turing, or unknown-word models) to $B$ , exactly as in n-gram smoothing
Underflow from multiplying many small probabilities	$\alpha_t(j)$ shrinks geometrically with $t$ ; for long sequences it underflows floating point	Work in log-space (log-sum-exp for the summation step) or rescale $\alpha$ columns at each step
Treating $A$ / $B$ rows as unnormalized counts	Forgetting to normalize transition/emission counts into probabilities during parameter estimation	Always divide raw counts by the correct denominator (row sums) before use
Assuming a first-order HMM captures all context needed	Real tag dependencies (e.g. "to VB" vs "to NN") sometimes span more than one previous state	Consider a higher-order (trigram) HMM or a richer feature-based model such as a CRF

Pioneers & history

Origins · 1 minAndrey Markov and how this was discovered

Andrey Markov

1856–1922 · Russian mathematician who introduced Markov chains

Markov developed the theory of chains of dependent random variables in the early 1900s, originally to model letter sequences in Pushkin's poetry — an early, informal ancestor of statistical language modeling. His name now labels the "memoryless" independence assumption at the heart of every HMM: the future depends on the present, not the full past.

History

1906

— Andrey Markov formalizes chains of dependent trials, later named Markov chains.

1966

— Leonard Baum and colleagues develop the mathematical machinery (forward-backward algorithm) for hidden Markov processes at the Institute for Defense Analyses.

1970

— Baum, Petrie, Soules, and Weiss publish the convergence proof underlying what becomes the Baum-Welch algorithm.

1980

s — HMMs become the dominant technique for speech recognition (IBM, Bell Labs) and are adapted to part-of-speech tagging and computational biology.

1990

s — HMM-based taggers (e.g., using the Penn Treebank) become standard baselines in statistical NLP, later joined and partly supplanted by discriminative models like maximum-entropy Markov models and CRFs.

Rabiner's 1989 tutorial on HMMs for speech recognition became the standard reference that popularized the "three problems" framing (evaluation, decoding, learning) used throughout this article, cementing forward-backward and Viterbi as the canonical algorithmic pair for any hidden Markov process.

Where this matters

HMMs were the backbone of statistical Part-of-Speech Tagging for decades: tag sequences form the hidden Markov chain, and words are the emissions, with the forward and Viterbi algorithms giving both sequence probabilities and best-tag-sequence decoding. In speech recognition, HMMs (often combined with Gaussian mixture models or, later, neural acoustic models) modeled phoneme sequences as hidden states emitting acoustic feature vectors, forming the core of systems from the 1980s through the early 2010s before end-to-end neural architectures took over. In bioinformatics, profile HMMs detect gene structures and protein family membership by treating coding/non-coding regions as hidden states emitting nucleotide or amino-acid sequences. HMMs are also the direct conceptual predecessor of conditional random fields, which drop the generative/independence assumptions but keep the same trellis-and-dynamic-programming machinery, and they remain the standard first example taught alongside Named-Entity Recognition pipelines, where hidden states correspond to entity tags (e.g., `B-PER`, `I-ORG`, `O`) emitting the observed tokens. Even in the era of large neural sequence models, the HMM's clean separation of transition dynamics and emission likelihoods, and its exact polynomial-time inference algorithms, remain the clearest teaching example of how structured probabilistic assumptions convert an exponential search problem into a tractable one.

Ask the tutor: How does the Viterbi algorithm's max-based recurrence differ in its correctness proof from the forward algorithm's sum-based one?

What's the difference between a Markov chain and a Hidden Markov Model?

A plain Markov chain models a sequence of observed states directly — the states themselves are what you see, as in an n-gram model over word sequences. An HMM adds a layer of indirection: the Markov chain governs hidden states you never observe directly, and each hidden state stochastically emits a visible observation via the emission matrix $B$ . This extra layer is exactly what lets HMMs model problems like part-of-speech tagging, where you observe words but want to infer unobserved grammatical tags, or speech recognition, where you observe acoustic signals but want unobserved phonemes.

Why can't we just use Naive Bayes instead of an HMM for tagging?

Naive Bayes assigns a single class label to an entire document based on conditionally independent features, with no notion of a sequence of labels influencing one another. An HMM generalizes this by chaining together many "Naive-Bayes-like" emission decisions, one per time step, and linking the hidden labels themselves with a Markov chain. This lets an HMM capture the fact that adjacent tags are correlated (a determiner is almost always followed by a noun or adjective), which plain Naive Bayes has no mechanism to represent at all.

What exactly does the forward algorithm compute, and why do we need it?

It computes $P(O\mid\lambda)$ , the total probability that the model assigns to an observed sequence, summed over every possible hidden path consistent with it. This quantity is needed to compare or evaluate models (e.g., picking the HMM parameters, among several candidates, that best explain training data) and as a computational building block inside the Baum-Welch learning algorithm, which needs both forward and backward probabilities to re-estimate transition and emission counts.

Is the forward algorithm the same as the Viterbi algorithm?

No, though they share almost identical recurrence structure. The forward algorithm sums over all incoming paths at each trellis cell to compute a total probability; the Viterbi algorithm replaces that sum with a max and keeps backpointers, so it finds the single most probable hidden state sequence rather than the total probability mass over all sequences. Both run in $O(N^2T)$ time using the same dynamic-programming trellis, but they answer different questions (evaluation vs. decoding).

How are the transition and emission probabilities actually learned?

If labeled training data is available (e.g., a corpus where every word already has its correct part-of-speech tag), $A$ and $B$ can be estimated directly by counting: $a_{ij}$ is the relative frequency of tag $j$ following tag $i$ , and $b_j(o)$ is the relative frequency of word $o$ given tag $j$ , both typically smoothed to avoid zero probabilities. When no labeled tags are available, the Baum-Welch algorithm (a special case of Expectation-Maximization) iteratively re-estimates $A$ and $B$ using forward and backward probabilities computed under the current parameter guess, provably increasing the data likelihood at every iteration until convergence to a local optimum.

What are the main limitations of HMMs compared to modern neural sequence models?

HMMs assume a rigid first-order Markov dependency among hidden states and that each observation depends only on its own hidden state, ignoring surrounding context and arbitrary overlapping features. Neural sequence models and conditional random fields relax these assumptions, allowing rich, overlapping, and long-range features to influence predictions, generally yielding higher accuracy on complex tagging and recognition tasks. HMMs remain valuable, however, for their transparency, small parameter count, exact and efficient inference, and ability to learn from unlabeled data via EM, which neural models often cannot do as cleanly.

Why is the Markov assumption called an "assumption" rather than a fact — does it hurt accuracy?

It is an assumption because real language and real hidden processes often violate strict first-order dependence — a word's correct tag can depend on context several tokens away, not just the immediately preceding tag. This is a genuine source of model bias: no amount of data fixes an HMM's blindness to dependencies its structure cannot express. In practice this cost is often acceptable given the enormous efficiency gain from polynomial-time inference, and richer variants (higher-order HMMs, or discriminative models like CRFs) exist precisely to relax this assumption when accuracy demands it.