Probability of the sequences.

The joint probability of the state sequence q being generated by the HMM and the observation sequence $\mbox{\boldmath$O$}$ being generated by that state sequence is  

$$\Pr(\mbox{\boldmath$O$},q\vert\lambda) = \pi_{q_0} \prod_{t=1}^T a_{q_{t-1} q_t} b_{q_t}(\mbox{\boldmath$O$}_t) \:.$$ (16)

Since the generating state sequence is unknown the actual probability of the observation sequence for the model $\lambda$ is  

$$\Pr(\mbox{\boldmath$O$}\vert\lambda) = \sum_q \pi_{q_0} \prod_{t=1}^T a_{q_{t-1} q_t} b_{q_t}(\mbox{\boldmath$O$}_t) \:.$$ (17)

The probability (18) can be computed using the forward-backward procedure [Baum, 1972].

The dynamic programming by Viterbi algorithm [Forney, 1973] is commonly used to decode the most likely state sequence behind the observations by maximizing recursively the probability $\Pr(\mbox{\boldmath$O$},q\vert\lambda)$ (17). The estimation of the HMM parameters using the maximum likelihood (ML) criterion, i.e. maximization of $\Pr(\mbox{\boldmath$O$}\vert\lambda)$ over $\lambda$,is done using the Baum-Welch algorithm [Baum and Petrie, 1966]. Anyhow, a simpler ML training can be obtained by replacing the maximization of $\Pr(\mbox{\boldmath$O$}\vert\lambda)$ by the maximization of the likelihood of the most probable state sequence obtained by the Viterbi search. The optimal model is then

$$\bar \lambda = \arg \max_\lambda \: \max_q \: \Pr(\mbox{\boldmath$O$},q\vert\lambda) \:.$$ (18)

This latter method is called the segmental K-means or the Viterbi training and it can be shown [Rabiner et al., 1986] to have the same asymptotic behavior as the Baum-Welch training, but with less numerical difficulties.