Viterbi Algorithm
Section 1 - Page 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
2. Reducing complexity using recursion
We will consider recursively finding the most probable sequence
of hidden states given an observation sequence and a HMM. We
will first define the partial probability
 , which is the
probability of reaching a particular intermediate state in the
trellis. We then show how these partial probabilities are
calculated at t=1 and at t=n (> 1).
These partial probabilities differ from those calculated in the
forward algorithm since they represent the probability of the
most probable path to a state at time t, and not a total.
2a. Partial probabilities (
's)
and partial best paths
Consider the trellis below showing the states and first order
transitions for the observation sequence dry,damp,soggy;
|
