Section 1 - Page 2
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
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