• The Viterbi Algorithm (VA) was first proposed by Andrew J.
Viterbi in 1967.
• TheViterbi algorithm is a dynamic programming algorithm.
• Use for finding the most likely sequence of hidden states-called
the Viterbi path- that results in a sequence of observed events,
especially in the context Hidden Markov Models.
• The algorithm has found its original application in communication
for decoding such as in dial-up modems, satellite, deep-space
communications and wireless LANs.
• It is now also commonly used in speech recognition, speech
synthesis, natural language processing, computational linguistics
and bioinformatics.
• Markov models are used to model sequences of events (or
observations) that occur one after another .
• In a Hidden Markov model, the state is not directly visible, but the
output/observations, dependent on the state, is visible.
• Each state has a probability distribution over the possible output .
• The sequence of observations generated by a HMM gives some
information about the sequence of states.
An example of Hidden Markov Model (State Diagram)
a12 a23
Hidden
a21 States
Observable
Events
aij -> Probability of transition from one state to another
bij -> Probability of an observation for a state
The Viterbi Algorithm
Input:
• The state space S={ s1 ,s2 ,…..sN } .
• The observation space O={ o1 , 02 ,…0K } .
• Transition matrix A of size N.N such that Aij stores the transition
probability of transiting from state si to sj state.
• Emission matrix B of size N.K such that Bij stores the probability of observing
oj from state si .
• An array of initial probabilities π of size N such that πi stores the probability of
state si at time t=1.
• Sequence of observations y1,y2…..yT.
Output :
The most likely hidden state sequence X= {x1 ,x2 ,……xT}.
Algorithm:
function VITERBI(O, S, π, A,T,B ) : X
for each state s from 1 to N do
Viterbi[ s,1 ] ← πs * B s,o1
Backpointer[ s,1 ] ← 0
for each time step t from 2 to T do
for each state s from 1 to N do
N
Viterbi[ s, t ] ← max
k=1
(Viterbi [ k , t-1] *A k ,s *B s, o )
N t
Backpointer[ s, t ] ← argmax (Viterbi [ k , t-1] * A k , s * B s, o )
k=1 t
End for
End for
Cont….
ZT ← argmax (Viterbi [s ,T ] )
XT←S ZT S=1
for i ←T,T-1….2 do
Zi-1 ← Backpointer[ Zi , i]
Xi-1 ← SZi-1
End for
Return X
End function
The complexity of the algorithm is O( T * N2)
• Consider a doctor diagnoses fever by asking patients how they
feel. The patients may only answer that they feel normal, dizzy, or
cold.
• There are two states, "Healthy" and "Fever", but the doctor cannot
observe them directly, they are hidden from him.
• On each day, there is a certain chance that the patient will tell the
doctor he/she is "normal", "cold", or "dizzy", depending on his/her
health condition.
Inputs:
States (S)=‘Healthy’ , ‘Fever’.
Observation (O)=‘Normal’ , ‘Cold’ , ‘Dizzy’.
Start_probability (π) = Healthy: 0.6, Fever: 0.4
Transition Probability(A)=
Healthy Fever
Healthy
0.7 0.3
Fever 0.4 0.6
Emission Probability(B)=
Normal Cold Dizzy
Healthy 0.5 0.4 0.1
Fever 0.1 0.3 0.6
Operations
Day 1
O bservation
Normal
H
0.30
Start
F
0.04
Calculate
P(start) * P( normal | state)
Day 1 Day 2
O bservation Observation
Normal P(H) . P( H->H) . P(cold | H) C o ld
0.3 . 0.7 .0.4
H = 0.084
0.30
Start
P(F) . P(F -> F) . P(cold | F )
F
0.04 0.04 . 0.6 . 0.3
= 0.0072
Calculate
P(old_state) * P(old_state -> new_state) * P( cold | new_state)
Day 1 Day 2
O bservation O b servation
Normal Cold
H
0.084 H
0.30 0.084
Start
F 0.0072 F
0.04 0.027
For each State H / F, Select the path with
the Highest probability
Day 1 Day 2 Day 3
O bservation Observation O bservation
Normal C o ld Dizzy
0.084 . 0.7 . 0.1
H H = 0.0058
0.30 0.084
Start
F F 0.027 . 0.6 . 0.6
0.04 0.027 = 0.00972
Calculate
P(old_state) * P(old_state -> new_state) *P(Dizzy | new_state)
Day 1 Day 2 Day 3
O bservation O b servation O bservation
Normal Cold Dizzy
H H
0.0058 H
0.30 0.084 0.0058
Start
F F 0.00972 F
0.04 0.027 0.0151
For each State H / F, Select the path with
the Highest probability
Day 1 Day 2 Day 3
O bservation O b servation O bservation
Normal Cold Dizzy
H H H
0.30 0.084 0.0058
Start
F F F
0.04 0.027 0.0151
For time step T, select the state that has the highest probability and backtrack
to the path that produced the highest probability using the backpointer and
return the states.
Day 1 Day 2 Day 3
O bservation O bservation O bservation
Normal Cold Dizzy
(0.30 ) (0.084 ) ( 0.0151 )
“HEALTHY” “HEALTHY” “FEVER”
Advantages
1. Ability to correct wrong bits transmitted by adding redundant
information.
2. The State diagram offers a complete description of the system.
3. It is possible to reconstruct lost data.
Disadvantages
1. Computation becomes complex for large number of states.
2. More bandwidth needed for redundant information.
• Viterbi algorithm is widely used in communication.
• Use to find the hidden states of finite states Hidden Markov Model.
• Also used extensively in recognition problems
