Viterbi Algorithm
Section 1  Page 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
We can find the most probable sequence of hidden states by
listing all possible sequences of hidden states and finding the
probability of the observed sequence for each of the
combinations. The most probable sequence of hidden states is
that combination that maximises
Pr(observed sequence  hidden state combination).
For example, for the observation sequence in the trellis shown,
the most probable sequence of hidden states is the sequence that
maximises :
Pr(dry,damp,soggy  sunny,sunny,sunny), Pr(dry,damp,soggy 
sunny,sunny,cloudy), Pr(dry,damp,soggy  sunny,sunny,rainy), . .
. . Pr(dry,damp,soggy  rainy,rainy,rainy)
This approach is viable, but to find the most probable sequence
by exhaustively calculating each combination is computationally
expensive. As with the forward algorithm, we can use the time
invariance of the probabilities to reduce the complexity of the
calculation.
