![](https://csdnimg.cn/release/download_crawler_static/10922364/bg13.jpg)
1.5 Recognition and Viterbi Decoding 9
2. Calculate the forward and backward probabilities for all states j and times t.
3. For each state j and time t, use the probability L
j
(t) and the current observation vector o
t
to update the accumulators for that state.
4. Use the final accumulator values to calculate new parameter values.
5. If the value of P = P (O|M) for this iteration is not higher than the value at the previous
iteration then stop, otherwise repeat the above steps using the new re-estimated parameter
values.
All of the above assumes that the parameters for a HMM are re-estimated from a single ob-
servation sequence, that is a single example of the spoken word. In practice, many examples are
needed to get good parameter estimates. However, the use of multiple observation sequences adds
no additional complexity to the algorithm. Steps 2 and 3 above are simply repeated for each distinct
training sequence.
One final point that should be mentioned is that the computation of the forward and backward
probabilities involves taking the product of a large number of probabilities. In practice, this means
that the actual numbers involved become very small. Hence, to avoid numerical problems, the
forward-backward computation is computed in HTK using log arithmetic.
The HTK program which implements the above algorithm is called HRest. In combination
with the tool HInit for estimating initial values mentioned earlier, HRest allows isolated word
HMMs to be constructed from a set of training examples using Baum-Welch re-estimation.
1.5 Recognition and Viterbi Decoding
The previous section has described the basic ideas underlying HMM parameter re-estimation using
the Baum-Welch algorithm. In passing, it was noted that the efficient recursive algorithm for
computing the forward probability also yielded as a by-product the total likelihood P (O|M). Thus,
this algorithm could also be used to find the model which yields the maximum value of P (O|M
i
),
and hence, it could be used for recognition.
In practice, however, it is preferable to base recognition on the maximum likelihood state se-
quence since this generalises easily to the continuous speech case whereas the use of the total
probability does not. This likelihood is computed using essentially the same algorithm as the for-
ward probability calculation except that the summation is replaced by a maximum operation. For
a given model M, let φ
j
(t) represent the maximum likelihood of observing speech vectors o
1
to
o
t
and being in state j at time t. This partial likelihood can be computed efficiently using the
following recursion (cf. equation 1.16)
φ
j
(t) = max
i
{φ
i
(t − 1)a
ij
}b
j
(o
t
). (1.27)
where
φ
1
(1) = 1 (1.28)
φ
j
(1) = a
1j
b
j
(o
1
) (1.29)
for 1 < j < N. The maximum likelihood
ˆ
P (O|M ) is then given by
φ
N
(T ) = max
i
{φ
i
(T )a
iN
} (1.30)
As for the re-estimation case, the direct computation of likelihoods leads to underflow, hence,
log likelihoods are used instead. The recursion of equation 1.27 then becomes
ψ
j
(t) = max
i
{ψ
i
(t − 1) + log(a
ij
)} + log(b
j
(o
t
)). (1.31)
This recursion forms the basis of the so-called Viterbi algorithm. As shown in Fig. 1.6, this algorithm
can be visualised as finding the best path through a matrix where the vertical dimension represents
the states of the HMM and the horizontal dimension represents the frames of speech (i.e. time).
Each large dot in the picture represents the log probability of observing that frame at that time and
each arc between dots corresponds to a log transition probability. The log probability of any path