Recap: filtering (from L10)

From past evidence \(o_{0:k}\), filtering gives the posterior over the current state:

\(f_{0:k} = P(S_k | o_{0:k}) = \alpha\, P(o_k | S_k) \sum_{s_{k-1}} P(S_k | s_{k-1})\, f_{0:(k-1)}\)

Today: a query about a past state, given all the evidence we have.

Smoothing: query a past state

\(P(S_k | o_{0:(t-1)}), \quad 0 \leq k \leq t-1\)

Deriving the smoothing formula

Four small steps from \(P(S_k | o_{0:(t-1)})\) to the forward-backward product:

Try to identify the rule before the label appears.

Smoothing  =  forward  ×  backward

Split the evidence around \(S_k\) into past and future:

\(P(S_k | o_{0:(t-1)}) \;=\; \alpha \, \underbrace{P(S_k | o_{0:k})}_{\textbf{forward } f_{0:k}} \, \underbrace{P(o_{(k+1):(t-1)} | S_k)}_{\textbf{backward } b_{(k+1):(t-1)}}\)

Two sweeps meet at \(S_k\); multiply pointwise and normalize.

Backward recursion

Compute \(b_{(k+1):(t-1)} \;\overset{\Delta}{=}\; P(o_{(k+1):(t-1)} | S_k)\) right-to-left.

Same factor sizes as forward recursion — total cost \(O(t)\) for the whole backward pass.

No normalization here: \(b\) is a likelihood, not a probability. Normalize after multiplying \(f \times b\).

A smoothing example: setup

Backward pass: compute \(b_{2:2}\), then \(b_{1:2}\)

\(b_{2:2} = P(o_2 | S_1) = \sum_{s_2} P(o_2 | s_2)\, b_{3:2}\, P(s_2 | S_1)\) with \(b_{3:2} = \langle 1, 1\rangle\):

\(b_{1:2} = P(o_{1:2} | S_0) = \sum_{s_1} P(o_1 | s_1)\, b_{2:2}\, P(s_1 | S_0)\):

Combine: \(P(S_k | o_{0:2}) = \alpha\, f_{0:k}\, b_{(k+1):2}\)

\(P(S_1 | o_{0:2}) = \alpha\, f_{0:1} \cdot b_{2:2}\):

\(P(S_0 | o_{0:2}) = \alpha\, f_{0:0} \cdot b_{1:2}\):

Deriving the backward recursion

Five steps from \(P(o_{(k+1):(t-1)} | S_k)\) to the recursive form:

The final factor is exactly \(P(o_{k+1} | s_{k+1})\, b_{(k+2):(t-1)}\, P(s_{k+1} | S_k)\) — the backward recursion.

The forward-backward algorithm

Compute the smoothed posterior at every time step \(k\) with one forward sweep + one backward sweep.

Forward gives every \(f_{0:k}\) (recap of L10), backward gives every \(b_{(k+1):(t-1)}\) — total cost \(O(t)\), one sweep each direction.

Try it: smoothing on a 4-step HMM

Compute \(P(S_2 \mid o_0 \wedge o_1 \wedge o_2 \wedge \neg o_3)\) — here \(k = 2,\; t = 4\).

The most-likely explanation

Find the single best sequence of hidden states that explains the observations:

\(\hat{s}_{0:t-1} = \arg\max_{s_{0:t-1}} P(s_{0:t-1} | o_{0:t-1})\)

• Generalize: \(S_t \in \{0, 1, \ldots, n-1\}\) — not just binary.
• Transition matrix \(A \in \mathbb{R}^{n \times n}\), emission matrix \(O \in \mathbb{R}^{n \times m}\).

Dynamic programming to the rescue: the Viterbi algorithm.

Dynamic programming: define \(\pi_k(j)\)

Why the recursion holds

The best path to state \(j\) at time \(k\) reuses the best path to some predecessor \(z\) at \(k-1\):

The inner max has no \(j\) in it — so one best path per node serves every successor (\(\phi_k(j)\) records the winning \(z\)). Constants don't change the argmax, so we work with the joint.

Viterbi recursion

\(\pi_k(j)\) = best probability of any path ending at state \(j\) at time \(k\). \(\phi_k(j)\) remembers which predecessor produced it — we'll use it to trace the best sequence back.

Viterbi: the algorithm

One sweep fills the trellis; one walk back along the backpointers extracts the MAP sequence.

Why Viterbi returns the true argmax

Recall \(\pi_k(j) = \displaystyle\max_{s_{0:(k-1)}} P(s_{0:(k-1)}, S_k{=}j, o_{0:k})\) and \(\phi_k(j) = \arg\max_{z}\bigl[\pi_{k-1}(z)\,P(j\mid z)\bigr]\). Goal: \(\hat s_{0:t-1} = \arg\max_{s_{0:t-1}} P(s_{0:t-1}, o_{0:t-1})\).

Splitting the argmax one state at a time turns the global search into \(t\) tiny argmaxes — and each one is exactly a backpointer \(\phi_k\).

Viterbi: trellis walk-through + complexity

Best path: \(\hat{s} = (1, 0, 1, 2, 1)\).

Complexity: \(O(t \cdot n^2)\) — one trellis edge per cell per step. Linear in time, quadratic in #states.