A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition

A Markov chain is a system that hops between a finite set of states, where the next state depends only on the current state — not on the history. This "memoryless" property is what makes the math tractable.

In a simple weather model, today's weather (sunny or rainy) determines tomorrow's. If it's sunny today, there's a 70% chance of sun tomorrow and 30% chance of rain. These numbers live in a transition matrix $A$, where $a_{ij}$ is the probability of moving from state $i$ to state $j$.

But what if we can't observe the weather directly — we can only see whether our colleague carries an umbrella? Now the weather is hidden, and the umbrella is the observation. This is the key insight behind HMMs: the states are invisible, and we must infer them from indirect, noisy signals.

An HMM is fully specified by five components, compactly written as $\lambda = (N, M, A, B, \pi)$:

• $N$ — the number of hidden states. In speech, each state might represent a phonetic segment. The states are $S = \{S_1, S_2, \ldots, S_N\}$.
• $M$ — the number of distinct observation symbols. If we vector-quantize a speech signal into a codebook of 256 entries, then $M = 256$.
• $A$ — the state transition probability matrix. Entry $a_{ij} = P(q_{t+1} = S_j \mid q_t = S_i)$ tells how likely the system is to move from state $i$ to state $j$.
• $B$ — the observation probability distribution. Entry $b_j(k) = P(O_t = v_k \mid q_t = S_j)$ gives the probability of emitting symbol $v_k$ when in state $S_j$. Think of it as each state having its own "fingerprint" of which observations it tends to produce.
• $\pi$ — the initial state distribution. $\pi_i = P(q_1 = S_i)$ is the probability that the system starts in state $i$.

Rabiner frames the entire HMM toolkit around three questions. Every application — from speech recognition to gene finding — maps onto one or more of them:

Problem 1 — Evaluation: Given a model $\lambda$ and an observation sequence $O$, what is $P(O \mid \lambda)$? In other words, how well does this model explain these observations? This is the scoring problem — used to select the best model among competitors.

Problem 2 — Decoding: Given $\lambda$ and $O$, what is the most likely hidden state sequence? What was probably happening behind the curtain? This is the inference problem — finding the hidden story.

Problem 3 — Learning: Given observation sequences, how do we adjust $\lambda = (A, B, \pi)$ to maximize $P(O \mid \lambda)$? How do we train the model from data? This is the optimization problem.

To compute $P(O \mid \lambda)$ by brute force, we'd sum over all possible state sequences — $N^T$ of them for $T$ time steps and $N$ states. For $N = 5$ and $T = 100$, that's $5^{100} \approx 10^{70}$ paths: impossible.

The Forward algorithm solves this in $O(N^2 T)$ time using dynamic programming. The idea is beautifully simple: define the forward variable $\alpha_t(i) = P(O_1, O_2, \ldots, O_t, q_t = S_i \mid \lambda)$ — the probability of seeing the first $t$ observations AND being in state $i$ at time $t$. Then build it up step by step:

1. Initialize: $\alpha_1(i) = \pi_i \cdot b_i(O_1)$ — start probability times emission probability.
2. Recurse: $\alpha_{t+1}(j) = \left[\sum_{i=1}^{N} \alpha_t(i) \cdot a_{ij}\right] \cdot b_j(O_{t+1})$ — sum all paths into state $j$, then multiply by the emission.
3. Terminate: $P(O \mid \lambda) = \sum_{i=1}^{N} \alpha_T(i)$.

Think of it as water flowing through a pipe network: at each time step, the flow arriving at state $j$ is the total from all incoming pipes, multiplied by how likely $j$ is to produce the observed sound.

The Backward algorithm is the mirror image: define $\beta_t(i) = P(O_{t+1}, \ldots, O_T \mid q_t = S_i, \lambda)$ — the probability of the future observations given that we're in state $i$ now. It recurses backward from time $T$ to time 1. On its own, the backward variable isn't useful for evaluation, but combined with $\alpha$ it unlocks the posterior probability of being in any state at any time: $\gamma_t(i) = P(q_t = S_i \mid O, \lambda) = \frac{\alpha_t(i) \beta_t(i)}{P(O \mid \lambda)}$. This posterior is the key ingredient for the learning algorithm (Problem 3).

The forward algorithm sums over all paths — good for scoring, but it doesn't tell us which path is most likely. The Viterbi algorithm is almost identical in structure, except it replaces the sum with a max:

$\delta_t(j) = \max_{i} \left[\delta_{t-1}(i) \cdot a_{ij}\right] \cdot b_j(O_t)$

Instead of summing all incoming paths, we keep only the best one — and store a backpointer $\psi_t(j) = \arg\max_i [\delta_{t-1}(i) \cdot a_{ij}]$ so we can trace back the winning path at the end.

The metaphor is a race: at each checkpoint, every runner (state) remembers only who handed them the baton fastest. At the finish line, we trace back through handoffs to reconstruct the fastest relay team.

How do we find the best parameters $(A, B, \pi)$ when we only have observation sequences and no labeled state sequences? This is a classic incomplete-data problem, and the Baum-Welch algorithm — a special case of the EM algorithm — solves it iteratively:

E-step (Expectation): Using the current model $\lambda$, compute the expected number of times each transition $i \to j$ is used, and the expected number of times each symbol $k$ is emitted from state $j$. These expectations come from the $\gamma$ and $\xi$ posteriors, which use both the forward ($\alpha$) and backward ($\beta$) variables.

M-step (Maximization): Re-estimate $A$, $B$, and $\pi$ by normalizing those expected counts into probabilities.

Repeat E and M until the likelihood $P(O \mid \lambda)$ converges. Baum et al. proved a remarkable guarantee: $P(O \mid \bar{\lambda}) \geq P(O \mid \lambda)$ — every iteration improves the likelihood or stays the same. The model climbs the likelihood surface monotonically until it reaches a local maximum.

Speech unfolds in time — you don't jump from the end of a word back to its beginning. This temporal constraint motivates left-right (or Bakis) HMMs, where the state index can only stay the same or increase: $a_{ij} = 0$ for $j < i$. The system can linger in a state (modeling duration) or advance, but never retreat.

For speech recognition, each word in the vocabulary gets its own left-right HMM, typically with 5–10 states. The states loosely correspond to phonetic segments: the initial consonant, the vowel, the final consonant. Each state's emission distribution captures the spectral characteristics of that segment.

Recognition works by running the evaluation problem (Problem 1) for every word model and choosing the word whose model gives the highest score: $W^* = \arg\max_w P(O \mid \lambda_w)$. The observation sequence $O$ comes from analyzing the speech signal — typically extracting features like LPC cepstral coefficients every 10 milliseconds, then vector-quantizing them.

Rabiner demonstrates HMMs on three progressively harder tasks:

Isolated word recognition — the simplest case. The speaker says one word at a time with pauses between words. Train one HMM per vocabulary word, score each model against the input, pick the winner. Error rates below 1% were achieved on digit recognition.

Connected word recognition — the speaker says a sequence of words without pauses, but from a known small vocabulary (like digit strings "one five seven"). The system concatenates word-level HMMs into a network and finds the best path through it using a modified Viterbi search.

Continuous speech recognition — unrestricted, natural speech with a large vocabulary and complex grammar. This requires sub-word units (phonemes or triphones), language models to constrain search, and sophisticated decoding strategies. The HMM framework scales to all three levels because the same algorithms (forward, Viterbi, Baum-Welch) apply regardless of granularity.

Two practical issues arise when implementing HMMs:

Numerical underflow. As $T$ grows, the forward variable $\alpha_t(i)$ becomes astronomically small — products of many probabilities. The standard fix is to scale (normalize) $\alpha$ at each time step, dividing by $c_t = \sum_i \alpha_t(i)$. The log-likelihood is then $\log P(O \mid \lambda) = -\sum_t \log c_t$. This keeps all numbers in a manageable range without changing the final answer.

Continuous observations. The discrete observation model ($M$ symbols from a codebook) limits resolution. For richer modeling, replace the discrete emission $B$ with Gaussian mixture models (GMMs): $b_j(\mathbf{x}) = \sum_{m=1}^{M_j} c_{jm} \, \mathcal{N}(\mathbf{x}; \boldsymbol{\mu}_{jm}, \boldsymbol{\Sigma}_{jm})$. Each state emits continuous feature vectors drawn from a mixture of Gaussians. The Baum-Welch re-estimation formulas generalize naturally to update the means, covariances, and mixture weights.

The mathematical DNA of HMMs lives on. The CRF is a discriminative cousin that removed HMMs' observation independence assumption. DeepSpeech 2 replaced the entire HMM pipeline with end-to-end neural networks. But the conceptual framework — latent states, transition dynamics, observation models, and the evaluate/decode/learn trichotomy — remains the vocabulary of sequential modeling.