Hidden Markov Models: Parameter Estimation and Smoothing

Maximum Likelihood Estimation (MLE, no smoothing)

From fully labelled training data (dual-tape), count and divide:

Transitions:

$a_{ij} = \frac{\text{count}(s_i \to s_j)}{\text{count}(s_i)}$

Emissions:

$b_i(v_k) = \frac{\text{count}(s_i \text{ emits } v_k)}{\text{count}(s_i)}$

Problem: any count of zero gives probability zero. In Viterbi decoding, a zero anywhere kills that path entirely. With small training sets, many transitions and emissions will be unseen.

Laplace (Add-One) Smoothing

Transitions:

$a_{ij} = \frac{\text{count}(s_i \to s_j) + 1}{\text{count}(s_i) + |S|}$

Emissions:

$b_i(v_k) = \frac{\text{count}(s_i \text{ emits } v_k) + 1}{\text{count}(s_i) + |V|}$

CRITICAL: Denominators Are Different

This is the most common exam error. Transitions add $|S|$ (number of hidden states) to the denominator. Emissions add $|V|$ (number of observation symbols) to the denominator. They are different quantities and students who mix them up lose marks.

Why they differ: a transition goes to one of $|S|$ possible next states, so we smooth across $|S|$ outcomes. An emission goes to one of $|V|$ possible observation symbols, so we smooth across $|V|$ outcomes.

Full Worked Example: COVID HMM (2022 Q9)

Training Data (timesteps 1–7)

States: L, M, H, H, H, M, M Observations: +, ++, ++, +++, ++, ++, +

Counting Transitions

From / To	L	M	H
L	0	1	0
M	0	2	1
H	0	1	2

$\text{count}(L) = 1$, $\text{count}(M) = 3$, $\text{count}(H) = 3$

Without smoothing:

$a_{L \to M} = \frac{1}{1} = 1.0 \quad a_{M \to H} = \frac{1}{3} \quad a_{M \to M} = \frac{2}{3}$ $a_{H \to H} = \frac{2}{3} \quad a_{H \to M} = \frac{1}{3} \quad a_{L \to L} = \frac{0}{1} = 0$

$a_{L \to L} = 0$ is problematic: if we ever reach state L, we cannot stay there.

With smoothing ($|S| = 3$):

$a_{L \to M} = \frac{1+1}{1+3} = \frac{2}{4} \quad a_{M \to H} = \frac{1+1}{3+3} = \frac{2}{6}$ $a_{M \to M} = \frac{2+1}{3+3} = \frac{3}{6} \quad a_{H \to H} = \frac{2+1}{3+3} = \frac{3}{6}$ $a_{H \to M} = \frac{1+1}{3+3} = \frac{2}{6} \quad a_{L \to L} = \frac{0+1}{1+3} = \frac{1}{4}$

Counting Emissions

State / Obs	+	++	+++
L	1	0	0
M	0	3	0
H	0	1	2

$\text{count}(L) = 1$, $\text{count}(M) = 3$, $\text{count}(H) = 3$

Without smoothing:

$b_L(+) = \frac{1}{1} = 1.0 \quad b_M(\text{++}) = \frac{3}{3} = 1.0 \quad b_H(\text{++}) = \frac{1}{3} \quad b_H(\text{+++}) = \frac{2}{3}$

Zeros everywhere: $b_L(\text{++}) = 0$, $b_L(\text{+++}) = 0$, $b_M(+) = 0$, $b_M(\text{+++}) = 0$, $b_H(+) = 0$.

With smoothing ($|V| = 3$):

$b_L(+) = \frac{1+1}{1+3} = \frac{2}{4} \quad b_M(\text{++}) = \frac{3+1}{3+3} = \frac{4}{6} \quad b_H(\text{+++}) = \frac{2+1}{3+3} = \frac{3}{6}$

General Smoothing Parameter $\omega$

$a_{ij} = \frac{\text{count}(s_i \to s_j) + \omega}{\text{count}(s_i) + \omega \cdot |S|}$

$b_i(v_k) = \frac{\text{count}(s_i \text{ emits } v_k) + \omega}{\text{count}(s_i) + \omega \cdot |V|}$

Laplace smoothing is the special case $\omega = 1$. $\omega$ can be tuned on a development set (cross-validation).

Summary

Quantity	MLE (no smoothing)	Laplace (add-one)
$a_{ij}$	$\frac{\text{count}(s_i \to s_j)}{\text{count}(s_i)}$	$\frac{\text{count}(s_i \to s_j) + 1}{\text{count}(s_i) + \|S\|}$
$b_i(v_k)$	$\frac{\text{count}(s_i \text{ emits } v_k)}{\text{count}(s_i)}$	$\frac{\text{count}(s_i \text{ emits } v_k) + 1}{\text{count}(s_i) + \|V\|}$
Smoothing amount	None	Shift mass from seen to unseen
Most common error	—	Adding $\|V\|$ to transition denominator

Past paper questions: y2022p3q9, y2024p3q8, y2025p3q9