ConceptDBISAI-written · not yet proofread

Viterbi Algorithm

Also Viterbi

A dynamic-programming algorithm that computes the most likely hidden state sequence of a Hidden Markov Model for a given observation sequence in O(n·|H|²) time.

Know these firstHidden Markov Model

Definition

Given a Hidden Markov Model with hidden states $H$ and observations $o_1, \dots, o_n$ , let $\delta_i(h)$ be the maximal likelihood of any hidden sequence $h_1, \dots, h_i$ with $h_i = h$ for the first $i$ observations. The Viterbi algorithm computes

\delta_1(h) = \Pr(h)\,\Pr(o_1 \mid h), \qquad \delta_{i+1}(h') = \max_{h \in H} \big(\delta_i(h)\,\Pr(h' \mid h)\big) \cdot \Pr(o_{i+1} \mid h'),

stores the maximizing predecessor $\psi_{i+1}(h') = \arg\max_h \delta_i(h)\Pr(h' \mid h)$ as a back-pointer, chooses $h_n = \arg\max_h \delta_n(h)$ , and follows the back-pointers $h_{i} = \psi_{i+1}(h_{i+1})$ to recover the most likely sequence.

Formula#

With an END state (POS-Tagging): the final choice is $h_n = \arg\max_h \delta_n(h)\,\Pr(\text{END} \mid h)$ , and the probability of the best sequence is $\max_h \delta_n(h)\,\Pr(\text{END} \mid h)$ .
Running time: $n$ columns, each entry a maximum over $|H|$ predecessors: $O(n \cdot |H|^2)$ . Brute force over all sequences costs $O(|H|^n \cdot n)$ .
In practice computed with log-probabilities (sums instead of products) to avoid underflow.

Properties#

Why the recursion is correct. The likelihood is a product whose factors for positions $> i$ depend on $h_1, \dots, h_i$ only through $h_i$ . For a fixed $h_i = h$ the maximum over the prefix therefore factors out: $\max_{\text{prefix}} (\text{prefix part} \cdot c) = c \cdot \max_{\text{prefix}} (\text{prefix part})$ for a constant $c \ge 0$ . This is the optimal-substructure property of dynamic programming.
Max does not distribute over a product of two functions of the same variable: $\max_x f(x)g(x) \ne \max_x f(x) \cdot \max_x g(x)$ in general (exam WS 19/20, Task 5.3). Viterbi only pulls out factors that are constant for the maximized variables, which is why it keeps one $\delta_i(h)$ per state instead of one best state per position.
Greedy decoding is wrong. Choosing $h_1 = \arg\max_h \Pr(h)\Pr(o_1 \mid h)$ and then $h_{i+1} = \arg\max_{h'} \Pr(h' \mid h_i)\Pr(o_{i+1} \mid h')$ commits early and can end in a sequence with probability $0$ while a positive one exists (exam WS 18/19, Task 6.3, see POS-Tagging > Exercises & Exam Questions).

Example#

Example“good good good” in the sentiment HMM (exam WS 17/18, Task 6)

Parameters as in Hidden Markov Model > Example (initial $1/2$ each; transitions plus→plus $1/3$ , plus→minus $2/3$ , minus→plus $2/3$ , minus→minus $1/3$ ; $\Pr(\text{good} \mid \text{plus}) = 1/3$ , $\Pr(\text{good} \mid \text{minus}) = 2/3$ ).

$i$	$\delta_i(\text{plus})$	$\delta_i(\text{minus})$
1	$\frac12 \cdot \frac13 = \frac16$	$\frac12 \cdot \frac23 = \frac13$
2	$\max(\frac16 \cdot \frac13, \frac13 \cdot \frac23) \cdot \frac13 = \frac{2}{27}$ (from minus)	$\max(\frac16 \cdot \frac23, \frac13 \cdot \frac13) \cdot \frac23 = \frac{2}{27}$ (tie)
3	$\max(\frac{2}{27} \cdot \frac13, \frac{2}{27} \cdot \frac23) \cdot \frac13 = \frac{4}{243}$ (from minus)	$\max(\frac{2}{27} \cdot \frac23, \frac{2}{27} \cdot \frac13) \cdot \frac23 = \frac{8}{243}$ (from plus)

$h_3 = \text{minus}$ ( $8/243$ ), back-pointer $h_2 = \text{plus}$ , back-pointer $h_1 = \text{minus}$ . Most likely sequence: (minus, plus, minus) with likelihood $8/243$ , which a brute-force check over all 8 sequences confirms.

Sources#

Not covered by a WS 25/26 lecture. Source: the former Information Retrieval exams.
Exam WS 18/19, Task 6.3 (not published) (greedy vs. Viterbi)
Exam WS 19/20, Task 5.3–5.4 (not published) (max of a product, END tag)
Exam WS 17/18, Task 6 (not published) (decoding, brute force)

Connections

Mentioned in inline links2

Hidden Markov Model
which the Viterbi Algorithm computes in $O(n \cdot |H|^2)$ instead of trying all $|H|^n$ sequences. Maximizing the joint probability is the same as maximizing $\Pr(h_1, \dots, h_n \mid o_1, \dots, o_n)$ , because $\Pr(o_1, \dots, o_n)$ does… §
POS-Tagging
Viterbi Algorithm — dynamic programming for the most likely hidden sequence in $O(n|H|^2)$ §
Decoding problem: $\arg\max_{h_1..h_n} \Pr(h, o)$ over $|H|^n$ sequences. Brute force is correct but exponential; Viterbi keeps the best prefix per final state and needs $O(n|H|^2)$ . §

Search in these mentions →