Beyond Gaussian Mixtures

Standard mixture models treat observations as independently and identically distributed (i.i.d.)—each data point is generated by first selecting a component, then sampling from that component's distribution. This assumption is fundamental to tractable inference but profoundly limiting for sequential data.

Consider speech recognition: an audio signal consists of a sequence of acoustic frames corresponding to phonemes. Crucially, phonemes don't appear randomly—the phoneme at time $t$ strongly depends on previous phonemes. A 'k' sound is likely followed by a vowel, not by silence. This temporal structure carries essential information that i.i.d. models discard.

Hidden Markov Models (HMMs) extend mixture models by introducing Markov dependencies between the latent component indicators. Instead of independent component selection, the sequence of latent states $z_1, z_2, \ldots, z_T$ forms a Markov chain: the current state depends only on the previous state. This seemingly simple modification enables HMMs to capture rich temporal structure while remaining computationally tractable.

HMMs are foundational in machine learning, having driven breakthroughs in speech recognition, computational biology, handwriting recognition, and financial modeling. Understanding HMMs provides the conceptual foundation for more advanced sequential models like conditional random fields and recurrent neural networks.

An HMM jointly models a sequence of observations $\mathbf{x} = (x_1, x_2, \ldots, x_T)$ and a corresponding sequence of hidden states $\mathbf{z} = (z_1, z_2, \ldots, z_T)$.

Model Components

1. State space: Discrete states $z_t \in {1, 2, \ldots, K}$

2. Initial state distribution $\boldsymbol{\pi}$: $$\pi_k = p(z_1 = k)$$ Vector of length $K$ summing to 1.

3. Transition matrix $\mathbf{A}$: $$A_{jk} = p(z_t = k | z_{t-1} = j)$$ $K \times K$ matrix where each row sums to 1. Entry $A_{jk}$ is the probability of transitioning from state $j$ to state $k$.

4. Emission distributions ${p(x | z = k)}_{k=1}^K$: The probability of observing $x$ given state $k$. Common choices:

• Discrete: Categorical distribution over observation symbols
• Continuous: Gaussian $\mathcal{N}(x | \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)$
• Mixture: GMM per state (HMM-GMM)

Generative Process

An HMM generates a sequence as follows:

1. Sample initial state: $z_1 \sim \text{Categorical}(\boldsymbol{\pi})$
2. Sample first observation: $x_1 \sim p(x | z_1)$
3. For $t = 2, \ldots, T$:
   • Sample next state: $z_t \sim \text{Categorical}(\mathbf{A}{z{t-1}, \cdot})$
   • Sample observation: $x_t \sim p(x | z_t)$

Factorization

The joint probability factorizes as:

$$p(\mathbf{x}, \mathbf{z}) = p(z_1) \prod_{t=2}^T p(z_t | z_{t-1}) \prod_{t=1}^T p(x_t | z_t)$$

$$= \pi_{z_1} \prod_{t=2}^T A_{z_{t-1}, z_t} \prod_{t=1}^T p(x_t | z_t)$$

Key Conditional Independence Properties

1. Markov property on states: $z_t \perp z_{1:t-2} | z_{t-1}$ (future is independent of past given present)

2. Conditional independence of observations: $x_t \perp x_{-t}, z_{-t} | z_t$ (observation depends only on its corresponding state)

3. D-separation: Given the hidden states, all observations are independent. Given observations, states are generally not independent—there's "explaining away."

Working with HMMs requires solving three fundamental computational problems:

Problem 1: Evaluation (Likelihood)

Question: Given model parameters $\boldsymbol{\theta} = (\boldsymbol{\pi}, \mathbf{A}, {\text{emission params}})$ and observation sequence $\mathbf{x} = (x_1, \ldots, x_T)$, compute $p(\mathbf{x} | \boldsymbol{\theta})$.

Challenge: Naive computation requires summing over all $K^T$ possible state sequences: $$p(\mathbf{x}) = \sum_{z_1, \ldots, z_T} p(\mathbf{x}, \mathbf{z})$$

For $T = 100$ and $K = 50$, this is $50^{100} \approx 10^{170}$ terms—utterly intractable.

Solution: The forward algorithm computes this in $O(TK^2)$ time using dynamic programming.

Applications: Model selection, anomaly detection, speech recognition confidence.

Problem 2: Decoding (Most Likely State Sequence)

Question: Given $\boldsymbol{\theta}$ and $\mathbf{x}$, find the most probable state sequence: $$\mathbf{z}^* = \arg\max_{\mathbf{z}} p(\mathbf{z} | \mathbf{x}, \boldsymbol{\theta})$$

Challenge: Same combinatorial explosion—$K^T$ candidate sequences.

Solution: The Viterbi algorithm finds the global optimum in $O(TK^2)$ using dynamic programming.

Applications: Speech-to-text transcription, part-of-speech tagging, gene finding.

Problem 3: Learning (Parameter Estimation)

Question: Given observation sequences (potentially multiple), find parameters that maximize likelihood: $$\boldsymbol{\theta}^* = \arg\max_{\boldsymbol{\theta}} p(\mathbf{x} | \boldsymbol{\theta})$$

Challenge: Hidden states make the likelihood non-convex. Direct optimization is difficult.

Solution: The Baum-Welch algorithm (EM for HMMs) iteratively improves parameters.

Applications: Training speech recognizers, building biological sequence models.

The forward-backward algorithm efficiently computes the likelihood $p(\mathbf{x})$ and the posterior marginals $p(z_t | \mathbf{x})$. It consists of two passes: a forward pass that accumulates evidence from the past, and a backward pass that accumulates evidence from the future.

Forward Variables

Define the forward variable $\alpha_t(k)$ as the joint probability of observing the first $t$ observations and ending in state $k$:

$$\alpha_t(k) = p(x_1, \ldots, x_t, z_t = k)$$

Base case ($t = 1$): $$\alpha_1(k) = \pi_k \cdot p(x_1 | z_1 = k)$$

Recursion ($t > 1$): $$\alpha_t(k) = p(x_t | z_t = k) \sum_{j=1}^K \alpha_{t-1}(j) \cdot A_{jk}$$

The sum accumulates all ways to reach state $k$ at time $t$: for each previous state $j$, multiply the probability of being in $j$ at $t-1$ by the transition probability to $k$.

Termination: The total likelihood is: $$p(\mathbf{x}) = \sum_{k=1}^K \alpha_T(k)$$

Backward Variables

Define the backward variable $\beta_t(k)$ as the probability of observing the remaining sequence given that we're in state $k$ at time $t$:

$$\beta_t(k) = p(x_{t+1}, \ldots, x_T | z_t = k)$$

Base case ($t = T$): $$\beta_T(k) = 1$$

Recursion ($t < T$): $$\beta_t(k) = \sum_{j=1}^K A_{kj} \cdot p(x_{t+1} | z_{t+1} = j) \cdot \beta_{t+1}(j)$$

Posterior Marginals

Combining forward and backward variables yields the posterior:

$$\gamma_t(k) = p(z_t = k | \mathbf{x}) = \frac{\alpha_t(k) \cdot \beta_t(k)}{p(\mathbf{x})} = \frac{\alpha_t(k) \cdot \beta_t(k)}{\sum_j \alpha_t(j) \cdot \beta_t(j)}$$

Pairwise posterior (needed for learning): $$\xi_t(j, k) = p(z_t = j, z_{t+1} = k | \mathbf{x}) = \frac{\alpha_t(j) \cdot A_{jk} \cdot p(x_{t+1} | k) \cdot \beta_{t+1}(k)}{p(\mathbf{x})}$$

The Viterbi algorithm finds the most likely state sequence—the global maximum a posteriori (MAP) path—using dynamic programming. It exploits the same Markov structure as forward-backward but uses max instead of sum.

Key Insight

The optimal principle: the best path to state $k$ at time $t$ must pass through some state $j$ at time $t-1$, and that prefix must itself be optimal for reaching $j$.

Viterbi Variables

Define $\delta_t(k)$ as the probability of the best path ending in state $k$ at time $t$:

$$\delta_t(k) = \max_{z_1, \ldots, z_{t-1}} p(z_1, \ldots, z_{t-1}, z_t = k, x_1, \ldots, x_t)$$

Base case: $$\delta_1(k) = \pi_k \cdot p(x_1 | k)$$

Recursion: $$\delta_t(k) = p(x_t | k) \cdot \max_j \left[ \delta_{t-1}(j) \cdot A_{jk} \right]$$

Backpointers: Store the $\arg\max$ at each step: $$\psi_t(k) = \arg\max_j \left[ \delta_{t-1}(j) \cdot A_{jk} \right]$$

Backtracking

After completing the forward pass:

1. Best final state: $z_T^* = \arg\max_k \delta_T(k)$
2. Best path probability: $p^* = \delta_T(z_T^*)$
3. Backtrack: For $t = T-1, \ldots, 1$: $z_t^* = \psi_{t+1}(z_{t+1}^*)$

Comparison to Forward

When to Use Each

Forward/Posterior: When you need uncertainty—"what's the probability of state $k$ at time $t$?"

Viterbi/MAP: When you need a single best explanation—"what sequence of states best explains the observations?"

The Baum-Welch algorithm is EM specialized to HMMs. It iteratively updates parameters using expected sufficient statistics computed via forward-backward.

E-Step

Run forward-backward to compute:

1. State posteriors: $\gamma_t(k) = p(z_t = k | \mathbf{x})$
2. Transition posteriors: $\xi_t(j, k) = p(z_t = j, z_{t+1} = k | \mathbf{x})$

M-Step

Initial distribution: $$\hat{\pi}_k = \gamma_1(k)$$

The expected count of starting in state $k$.

Transition matrix: $$\hat{A}{jk} = \frac{\sum{t=1}^{T-1} \xi_t(j, k)}{\sum_{t=1}^{T-1} \gamma_t(j)}$$

Numerator: expected count of $j \to k$ transitions. Denominator: expected count of being in state $j$ (when a transition is possible).

Emission parameters (discrete case): $$\hat{B}{kv} = p(x = v | z = k) = \frac{\sum{t: x_t = v} \gamma_t(k)}{\sum_{t=1}^T \gamma_t(k)}$$

Expected count of emitting $v$ from state $k$, divided by expected time in state $k$.

Gaussian Emissions

For Gaussian emission $p(x | z = k) = \mathcal{N}(x | \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)$:

$$\hat{\boldsymbol{\mu}}k = \frac{\sum{t=1}^T \gamma_t(k) \mathbf{x}t}{\sum{t=1}^T \gamma_t(k)}$$

$$\hat{\boldsymbol{\Sigma}}k = \frac{\sum{t=1}^T \gamma_t(k) (\mathbf{x}_t - \hat{\boldsymbol{\mu}}_k)(\mathbf{x}_t - \hat{\boldsymbol{\mu}}k)^T}{\sum{t=1}^T \gamma_t(k)}$$

Weighted mean and covariance, weighted by the posterior probability of being in state $k$ at each time.

Multiple Observation Sequences

Given multiple independent sequences ${\mathbf{x}^{(1)}, \ldots, \mathbf{x}^{(M)}}$:

1. Run forward-backward on each sequence separately
2. Aggregate sufficient statistics across sequences
3. M-step uses pooled statistics

For example: $$\hat{A}{jk} = \frac{\sum{m=1}^M \sum_{t=1}^{T_m-1} \xi_t^{(m)}(j, k)}{\sum_{m=1}^M \sum_{t=1}^{T_m-1} \gamma_t^{(m)}(j)}$$

The basic HMM can be extended in many directions to handle different application requirements.

Left-to-Right (Bakis) HMM

For sequential processes (speech, handwriting), states represent progression through a pattern. Constrain transitions to only allow forward movement:

$$A_{jk} = 0 \text{ for } k < j$$

The model can only stay in the current state or advance. This is standard in speech recognition phoneme models.

Continuous Density HMM

Replace discrete emissions with continuous distributions:

• Single Gaussian: $p(x|k) = \mathcal{N}(x | \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k)$
• GMM per state: $p(x|k) = \sum_m w_{km} \mathcal{N}(x | \boldsymbol{\mu}{km}, \boldsymbol{\Sigma}{km})$

GMM-HMMs were the dominant approach in speech recognition before deep learning.

Semi-Continuous (Tied-Mixture) HMM

Share Gaussian components across states, with state-specific mixture weights: $$p(x|k) = \sum_m w_{km} \mathcal{N}(x | \boldsymbol{\mu}_m, \boldsymbol{\Sigma}_m)$$

Reduces parameters while allowing state-specific distributions.

Factorial HMM

Multiple independent Markov chains $\mathbf{z}^{(1)}, \ldots, \mathbf{z}^{(F)}$, with observations depending on all chains:

$$p(x_t | z_t^{(1)}, \ldots, z_t^{(F)})$$

This models multiple independent "causes" contributing to observations (e.g., different speakers in audio).

Input-Output HMM (IOHMM)

Condition transitions and/or emissions on external inputs: $$p(z_t | z_{t-1}, \mathbf{u}_t)$$ $$p(x_t | z_t, \mathbf{u}_t)$$

This bridges HMMs with supervised learning and connects to recurrent neural networks.

HMMs have driven major advances across diverse application domains.

Speech Recognition (Historical Foundation)

The application that defined HMM research for decades:

• States: Phonemes or sub-phonemic units
• Observations: Acoustic features (MFCCs)
• Structure: Left-to-right within phonemes, phoneme concatenation via grammar

GMM-HMMs achieved commercially viable speech recognition, later enhanced by deep neural networks replacing GMMs.

Computational Biology

Gene finding: Identify protein-coding regions in DNA

• States: Coding, non-coding, intron, exon boundaries
• Observations: Nucleotide sequences
• Key models: GENSCAN, Glimmer

Protein structure: Profile HMMs for sequence alignment

• States: Match, insert, delete for each profile position
• Applications: HMMER, Pfam database

Part-of-Speech Tagging

Assign grammatical categories to words:

• States: Noun, verb, adjective, etc.
• Observations: Words or word features
• Transitions: Capture grammatical constraints (articles precede nouns)

This page has provided a comprehensive treatment of Hidden Markov Models, from fundamental concepts through practical algorithms.

What's Next: Infinite Mixtures (Dirichlet Process Mixture Models)

Both standard mixture models and HMMs require specifying the number of components $K$ in advance. But often we don't know how many components exist—we want the model complexity to grow with the data. The next page introduces Dirichlet Process Mixture Models (DPMMs), which extend mixture models with a nonparametric Bayesian prior that allows for a potentially infinite number of components, automatically inferring appropriate complexity from data.