Hidden Markov Models — Mathematics Knowledge System

Overview

A Hidden Markov Model (HMM) is a doubly stochastic process: an unobserved (hidden) Markov chain X_1, X_2, ... drives an observed emission sequence Y_1, Y_2, ..., where Y_t depends only on X_t. HMMs are used in speech recognition, NLP (POS tagging), bioinformatics (gene finding), and financial modeling. Key algorithms: the forward-backward algorithm (E-step inference), the Viterbi algorithm (most likely hidden path), and Baum-Welch (EM for parameter learning).

Intuition

Imagine an absent-minded professor who is secretly in one of several moods (states), but you can only observe what they say (observations). The mood evolves as a Markov chain (each mood depends only on the current mood), and what the professor says depends only on their current mood. You see only the words, not the mood. An HMM lets you infer the hidden mood sequence from the observations.

Formal Definition

Definition

An HMM is defined by (S, O, A, B, pi0) where S = {1,...,N} is the hidden state space, O is the observation alphabet, A = (a_{ij}) is the transition matrix with a_{ij} = P(X_{t+1}=j | X_t=i), B = (b_i(o)) is the emission matrix with b_i(o) = P(Y_t=o | X_t=i), and pi0 is the initial distribution.

a_{ij} = P(X_{t+1} = j \mid X_t = i), \quad \sum_j a_{ij} = 1

Transition probabilities

b_i(o) = P(Y_t = o \mid X_t = i), \quad \sum_o b_i(o) = 1

Emission probabilities

\alpha_t(i) = P(Y_1 = y_1, \ldots, Y_t = y_t, X_t = i)

Forward variable

\alpha_t(i) = b_i(y_t) \sum_j \alpha_{t-1}(j)\, a_{ji}

Forward recursion

P(Y_1 = y_1, \ldots, Y_T = y_T) = \sum_i \alpha_T(i)

Likelihood via forward algorithm

Notation

Notation	Meaning
$\alpha_t(i)$	Forward variable: joint probability of observations y_1..y_t and hidden state i at time t
$\beta_t(i)$	Backward variable: conditional probability of future observations y_{t+1}..y_T given state i at time t
$\gamma_t(i)$	Posterior: P(X_t = i \| Y_1=y_1,...,Y_T=y_T)

Theorems

Theorem 1: Theorem 1 (Forward-Backward Algorithm)

\text{The posterior } P(X_t = i \mid Y_{1:T} = y_{1:T}) = \gamma_t(i) = \frac{\alpha_t(i)\beta_t(i)}{\sum_j \alpha_t(j)\beta_t(j)}, \text{ where } \alpha \text{ (forward) and } \beta \text{ (backward) are computed in } O(N^2 T) \text{ time.}

Theorem 2: Theorem 2 (Viterbi Algorithm)

\text{The most probable hidden state sequence } x^* = \arg\max_{x_{1:T}} P(X_{1:T} = x_{1:T} \mid Y_{1:T} = y_{1:T}) \text{ is found by Viterbi dynamic programming in } O(N^2 T) \text{ time.}

Worked Examples

1
Initialize forward variables at t=1 for observation y_1=1.
$\alpha_1(H) = \pi(H) b_H(1) = 0.5 \times 0.2 = 0.1$
2
alpha_1(C) = pi(C) * b_C(1) = 0.5 * 0.5 = 0.25.
$\alpha_1(C) = 0.5 \times 0.5 = 0.25$
3
At t=2, observation y_2=2. Forward recursion: alpha_2(H) = b_H(2) * [alpha_1(H)*a_{HH} + alpha_1(C)*a_{CH}] = 0.8 * [0.1*0.7 + 0.25*0.4] = 0.8*(0.07+0.10) = 0.8*0.17 = 0.136.
$\alpha_2(H) = 0.8 \times (0.1 \times 0.7 + 0.25 \times 0.4) = 0.8 \times 0.17 = 0.136$
4
alpha_2(C) = b_C(2) * [alpha_1(H)*a_{HC} + alpha_1(C)*a_{CC}] = 0.5 * [0.1*0.3 + 0.25*0.6] = 0.5*(0.03+0.15) = 0.5*0.18 = 0.09.
$\alpha_2(C) = 0.5 \times (0.1 \times 0.3 + 0.25 \times 0.6) = 0.5 \times 0.18 = 0.09$
5
Total likelihood: P(Y_1=1, Y_2=2) = alpha_2(H) + alpha_2(C) = 0.136 + 0.09 = 0.226.
$P(Y_1=1, Y_2=2) = 0.136 + 0.09 = 0.226$

✓ Answer

P(Y_1=1, Y_2=2) = 0.226.

Practice Problems

Mediumfree response

What are the three fundamental problems of HMMs? Briefly describe the algorithm used to solve each.

Mediumfree response

Write the backward variable beta_t(i) = P(Y_{t+1},...,Y_T | X_t = i) and the recursion for computing it.

Common Mistakes

Common Mistake

Confusing the forward algorithm with Viterbi

The forward algorithm computes the total likelihood P(Y|model) by summing over all paths. Viterbi finds the single most probable path using max instead of sum.

Common Mistake

Using Viterbi posteriors for the most likely sequence

Viterbi finds the most likely joint hidden sequence. Choosing the state with maximum marginal posterior P(X_t | Y) at each t separately may not give the most likely sequence.

Quiz

Summary

An HMM has a hidden Markov chain X_t and observed emissions Y_t | X_t ~ B(X_t).
Three problems: evaluation (forward), decoding (Viterbi), learning (Baum-Welch/EM).
Forward algorithm: alpha_t(i) = b_i(y_t) sum_j alpha_{t-1}(j) a_{ji} in O(N^2 T).
Viterbi: replace sum by max + back-pointer to find the MAP hidden sequence.
Applications: speech recognition, gene finding, POS tagging, anomaly detection.

References

BookRabiner, L. R. -- A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition (1989)
BookBishop, C. M. -- Pattern Recognition and Machine Learning, Chapter 13
WebsiteWikipedia -- Hidden Markov model