Viterbi Algorithm
Viterbi Algorithm
• The Viterbi Algorithm is used to find the most likely sequence of
hidden states that could have produced a given sequence of
observations.
• It is mainly used in:
• Speech recognition
• Part-of-Speech tagging
• DNA sequence analysis
• Hidden Markov Models (HMMs)
• In simple words:
• We know the observed output.
• We want to find which hidden states likely produced that output.
• Viterbi chooses the most probable path.
• In an HMM:
• Hidden states = we cannot see directly
• Observations = we can see
• Many possible hidden-state sequences can produce the same observation
sequence.
• Viterbi selects the most probable one using dynamic programming.
• Step 1 — Initialization (Day 1)
• For each hidden state 𝑗
• πj = initial probability
• bj(O1)=emission probability of first observation
• V1(j)=best probability of reaching state j on Day 1
• Step 2 — Recursion (Day 2 to Day T)
• For each time 𝑡=2......T
• and for each state j
For each day and each hidden state,
we look at:
(best probability so far) × transition × emission,and choose the
path with the maximum value.
• Step 3 - Backtracking:
Dataset (Observed Activities for 5 Days):
Day
Day Observation
1 W (Walk)
2 S (Shop)
3 S (Shop)
We need to find the most likely weather sequence behind these
observations.
HMM Parameters
Hidden states: S (Sunny), R (Rainy)
1. Initial Probability Observations: W (Walk), Sh (Shop)
• P(Sunny) = 0.6
• P(Rainy) = 0.4
2. Transition Probability
From/To Sunny Rainy
Sunny 0.7 0.3
Rainy 0.4 0.6
3. Emission Probability
State Walk (W) Shop (Sh)
S 0.6 0.4
R 0.1 0.9
Hidden states: S (Sunny), R (Rainy)
Observations: W (Walk), Sh (Shop)
Step 1: Initialization (Day 1)
• For the first observation (O₁ = W) compute for each state s:
• Calculate:
• v[1][S] = π(S) * b(S,W) = 0.6 * 0.6 = 0.36, backpointer[1][S] =
None
• v[1][R] = π(R) * b(R,W) = 0.4 * 0.1 = 0.04, backpointer[1][R] =
None
• At time 1 there is no prior state, so the best path to S (or R) is just starting
in that state and emitting the first observation.
• Starting Sunny and seeing Walk has probability 0.36; starting Rainy and
seeing Walk has probability 0.04. So if we only had day 1, Sunny would be
more likely.
Vt(j) = best (maximum) probability of reaching state j at time t.
Vt−1(i) = best probability of being in previous state i.
aij = transition probability from state i → j
bj(Ot) = emission probability of observing Ot from state j
max over i = choose the state i that gives the highest probability path to state j
At every step, for every hidden state, we check all possible previous states,
calculate the path probability,
pick the best one, and store it.
Step 2— Recursion (for each t = 2..T) t = 2 (Observation = Sh)
• Compute v[2][S] and v[2][R].
• For S at t=2:
• We consider both previous states S and R, compute two candidate probabilities,
and pick the larger.
• Candidate coming from previous S:
v[1][S] * a(S→S) * b(S,Sh)
= 0.36 * 0.7 * 0.4 = 0.36 * 0.28 = 0.1008
• Candidate coming from previous R:
• v[1][R] * a(R→S) * b(S,Sh)
= 0.04 * 0.4 * 0.4 = 0.04 * 0.16 = 0.0064
• Pick the max: 0.1008 (from previous S).So: v[1][S] = 0.1008
• backpointer[2][S] = S (meaning: best path to S at t=2 came from S at t=1)
• For R at t=2:
• From previous S:
v[1][S] * a(S→R) * b(R,Sh)
= 0.36 * 0.3 * 0.9 = 0.36 * 0.27 = 0.0972
• From previous R:
v[1][R] * a(R→R) * b(R,Sh)
= 0.04 * 0.6 * 0.9 = 0.04 * 0.54 = 0.0216
Pick the max: 0.0972 (from previous S).
• So:
v[2][R] = 0.0972
• backpointer[2][R] = S
t = 3 (Observation = Sh)
Again compute for each current state.
For S at t=3:
Candidates: From previous S:
v[2][S] * a(S→S) * b(S,Sh) = 0.1008 * 0.7 * 0.4
= 0.1008 * 0.28 = 0.028224
From previous R:
v[2][R] * a(R→S) * b(S,Sh) = 0.0972 * 0.4 * 0.4
= 0.0972 * 0.16 = 0.015552
Pick max: 0.028224 (from previous S).
So:
v[3][S] = 0.028224, backpointer[3][S] = S
For R at t=3:
From previous S:
v[2][S] * a(S→R) * b(R,Sh)
= 0.1008 * 0.3 * 0.9= 0.1008 * 0.27= 0.027216
From previous R:
v[2][R] * a(R→R) * b(R,Sh)
= 0.0972 * 0.6 * 0.9= 0.0972 * 0.54= 0.052488
Pick max: 0.052488 (from previous R).
So: v[3][Rb] = 0.052488
backpointer[3][R] =R
• At t=3 we got v[3][R] = 0.052488 which is larger than v[3][S] = 0.028224. That
means: if we only consider the full three-day observation sequence, the most
probable single path ending in R at t=3 has higher probability than the best path
ending in S. So the most likely final state is R.
• Pick the state with the highest v[T][s] at final time T (here T=3).
• v[3][S] = 0.028224
• v[3][R] = 0.052488 ← maximum
• So the best final state q3 = R (Rainy). The probability of the most likely complete
path = 0.052488.
Step3 — Backtracking to get the whole state sequence
• We follow backpointers from t = T down to 1:q3 = backpick: q3 = R.
• q2 = backpointer[3][R] = R (because we recorded that the best way to
get to R at t=3 came from R at t=2).
• q1 = backpointer[2][R] = S (best way to get to R at t=2 came from S at
t=1).
• backpointer[1][S] = None (start)
• So the most likely state sequence is:
• q1 = S, q2 = R, q3 = R → Sunny, Rainy, Rainy
• A patient’s health condition is hidden and can be:
Healthy (H)
Fever (F) Initial Probabilities
P(H) = 0.6
• The doctor observes symptoms each day: P(F) = 0.4
Normal (N)
cold (C) Observation Sequence
Normal → Cold → High Temperature
High Temperature (T)
Question:
Transition Probability Apply the Viterbi Algorithm to find the most probable hidden
From / To H F health states.
H 0.7 0.3
F 0.4 0.6
State → Emission Probability
Symptom N C T
Healthy (H) 0.5 0.4 0.1
Fever (F) 0.2 0.3 0.5