COMP5318 — Week 11 Supplement
Mathematical Foundations
Formal Markov property, HMM notation \(\lambda = (A, B, \pi)\), the Forward and Viterbi recurrences with backpointer, and a fully worked numerical example on a tiny two-state HMM.
Markov property and chain probability
Let \(\pi_1, \pi_2, \ldots, \pi_T\) be a sequence drawn from a finite state set \(S = \{s_1, \ldots, s_N\}\). The chain is first-order Markov if the conditional distribution of the next state depends only on the current state.
Markov property (first order)
\[ P(\pi_t = s_j \mid \pi_1, \ldots, \pi_{t-1}) \;=\; P(\pi_t = s_j \mid \pi_{t-1}) \]
Equivalently, the joint factorises as \(P(\pi_1, \ldots, \pi_T) = P(\pi_1) \prod_{t=2}^T P(\pi_t \mid \pi_{t-1})\).
Transition matrix \(A\) and initial vector \(\pi\)
\[ a_{ij} = P(\pi_t = s_j \mid \pi_{t-1} = s_i), \qquad \sum_{j=1}^N a_{ij} = 1 \text{ for all } i \]
\[ \pi_i = P(\pi_1 = s_i), \qquad \sum_{i=1}^N \pi_i = 1 \]
(Slides use \(A_0\) for the initial distribution; we follow the textbook convention and call it \(\pi\). Be careful: \(\pi\) is also used for the state variable in the slides — here we reserve \(\pi\) for the initial distribution and use \(q_t\) for the state at time \(t\) when disambiguation is needed.)
HMM specification \(\lambda = (A, B, \pi)\)
An HMM extends a Markov chain with an observation layer. At each time \(t\) the hidden state \(q_t\) emits an observation \(o_t\) according to an emission distribution.
Emission matrix \(B\)
\[ b_i(v_k) \;=\; P(o_t = v_k \mid q_t = s_i), \qquad \sum_{k=1}^K b_i(v_k) = 1 \]
\(K\) is the number of observation symbols. \(B\) is sometimes written \(E\) or \(X\).
Joint probability of a path and observations
\[ P(O, Q \mid \lambda) \;=\; \pi_{q_1}\, b_{q_1}(o_1)\, \prod_{t=2}^T a_{q_{t-1}\,q_t}\, b_{q_t}(o_t) \]
Direct evaluation of \(P(O \mid \lambda) = \sum_Q P(O, Q \mid \lambda)\) by enumerating all \(N^T\) paths costs \(\mathcal{O}(2T\,N^T)\) operations — intractable for realistic \(T\).
Forward algorithm
Define the forward variable \(\alpha_t(i) = P(o_1, \ldots, o_t,\ q_t = s_i \mid \lambda)\). It can be computed by a dynamic-programming recurrence in \(\mathcal{O}(N^2 T)\) time.
Forward recurrence
Initialisation \((t = 1)\): \[ \alpha_1(i) \;=\; \pi_i\, b_i(o_1), \qquad i = 1, \ldots, N \]
Induction \((t = 2, \ldots, T)\): \[ \alpha_t(i) \;=\; \left[\sum_{j=1}^N \alpha_{t-1}(j)\, a_{ji}\right] b_i(o_t) \]
Termination: \[ P(O \mid \lambda) \;=\; \sum_{i=1}^N \alpha_T(i) \]
The bracket \(\sum_j \alpha_{t-1}(j)\, a_{ji}\) is the total probability of arriving in state \(s_i\) at time \(t\) from any predecessor. Multiplying by \(b_i(o_t)\) accounts for emitting the observation at time \(t\) from state \(s_i\).
Viterbi algorithm
Define the Viterbi variable \(\delta_t(i)\) as the probability of the most likely path that ends in state \(s_i\) at time \(t\) and produces observations \(o_1, \ldots, o_t\). The companion backpointer \(\psi_t(i)\) stores the predecessor that achieves the maximum.
Viterbi recurrence
Initialisation \((t = 1)\): \[ \delta_1(i) \;=\; \pi_i\, b_i(o_1), \qquad \psi_1(i) = 0 \]
Induction \((t = 2, \ldots, T)\): \[ \delta_t(i) \;=\; \max_{1 \le j \le N}\, \bigl[\delta_{t-1}(j)\, a_{ji}\bigr]\, b_i(o_t) \]
\[ \psi_t(i) \;=\; \arg\max_{1 \le j \le N}\, \delta_{t-1}(j)\, a_{ji} \]
Termination and back-trace: \[ P^\star \;=\; \max_i \delta_T(i), \qquad q^\star_T = \arg\max_i \delta_T(i), \qquad q^\star_{t-1} = \psi_t(q^\star_t) \]
Replace the \(\sum\) in the Forward recurrence with \(\max\) and add a backpointer: that is essentially the entire algorithmic difference. Both run on the same \(N \times T\) trellis in \(\mathcal{O}(N^2 T)\) time.
Worked Example: Forward on a 2-state HMM
Consider an HMM with two hidden states \(\{H, L\}\) (High / Low activity) and two observation symbols \(\{A, B\}\). Parameters:
Model parameters
\(\pi = (0.6, 0.4)\) for \((H, L)\).
Transitions: \(a_{HH} = 0.7,\ a_{HL} = 0.3,\ a_{LH} = 0.4,\ a_{LL} = 0.6\).
Emissions: \(b_H(A) = 0.5,\ b_H(B) = 0.5,\ b_L(A) = 0.2,\ b_L(B) = 0.8\).
Observation sequence: \(O = (A, B)\), so \(T = 2\).
Goal
Compute \(P(O \mid \lambda) = P(A, B \mid \lambda)\) using the Forward algorithm and verify against direct enumeration of the four hidden paths \(HH, HL, LH, LL\).
Step 1 — initialisation
\(\alpha_1(H) = \pi_H\, b_H(A) = 0.6 \cdot 0.5 = 0.30\).
\(\alpha_1(L) = \pi_L\, b_L(A) = 0.4 \cdot 0.2 = 0.08\).
Step 2 — induction at \(t = 2\)
\(\alpha_2(H) = \bigl[\alpha_1(H)\, a_{HH} + \alpha_1(L)\, a_{LH}\bigr]\, b_H(B)\)
\(= (0.30 \cdot 0.7 + 0.08 \cdot 0.4) \cdot 0.5 = (0.21 + 0.032) \cdot 0.5 = 0.242 \cdot 0.5 = 0.121\).
\(\alpha_2(L) = \bigl[\alpha_1(H)\, a_{HL} + \alpha_1(L)\, a_{LL}\bigr]\, b_L(B)\)
\(= (0.30 \cdot 0.3 + 0.08 \cdot 0.6) \cdot 0.8 = (0.09 + 0.048) \cdot 0.8 = 0.138 \cdot 0.8 = 0.1104\).
Step 3 — termination
\(P(O \mid \lambda) = \alpha_2(H) + \alpha_2(L) = 0.121 + 0.1104 = 0.2314\).
Cross-check by enumeration: \(P(O, HH) = 0.6 \cdot 0.5 \cdot 0.7 \cdot 0.5 = 0.105\); \(P(O, HL) = 0.6 \cdot 0.5 \cdot 0.3 \cdot 0.8 = 0.072\); \(P(O, LH) = 0.4 \cdot 0.2 \cdot 0.4 \cdot 0.5 = 0.016\); \(P(O, LL) = 0.4 \cdot 0.2 \cdot 0.6 \cdot 0.8 = 0.0384\). Sum: \(0.105 + 0.072 + 0.016 + 0.0384 = 0.2314\). The two methods agree.