10.4.1 Maximum Mutual Information Estimation

Recall that in Maximum Likelihood Estimation (MLE), we train our acoustic model parameters (A and B) so as to maximize the likelihood of the training data. Consider a particular observation sequence $ O $, and a particular HMM model $ M_k $ corresponding to word sequence $ W_k $, out of all the possible sentences $ W' \in \mathcal{L} $. The MLE criterion thus maximizes

$$ \mathcal{F}_{\mathrm{M L E}}(\lambda)=P_{\lambda}(O|M_{k}) $$

Since our goal in speech recognition is to have the correct transcription for the largest number of sentences, we'd like on average for the probability of the correct word string $ W_k $ to be high; certainly higher than the probability of all the wrong word strings $ W_{j,s,t,j} \neq k $. But the MLE criterion above does not guarantee this. Thus we'd like to pick some other criterion which will let us chose the model $ \lambda $ which assigns the highest probability to the correct model, i.e. maximizes $ P_\lambda(M_k|O) $. Maximizing the probability of the word string rather than the probability of the observation sequence is called conditional maximum likelihood estimation or CMLE:

$$ \mathcal{F}_{\mathrm{C M L E}}(\lambda)=P_{\lambda}(M_{k}|O) $$

Using Bayes Law, we can express this as

$$ \mathcal{F}_{\mathrm{C M L E}}(\lambda)=P_{\lambda}(M_{k}|O)=\frac{P_{\lambda}(O|M_{k})P(M_{k})}{P_{\lambda}(O)} $$

Let's now expand $ P_{\lambda}(O) $ by marginalizing (summing over all sequences which could have produced it). The total probability of the observation sequence is the weighted sum over all word strings of the observation likelihood given that word string:

$$ P(O)=\sum_{W\in\mathcal{L}}P(O|W)P(W) $$

So a complete expansion of Eq. 10.6 is:

$$ \mathcal{F}_{\mathrm{C M L E}}(\lambda)=P_{\lambda}(M_{k}|O)=\frac{P_{\lambda}(O|M_{k})P(M_{k})}{\sum_{M\in\mathcal{L}}P_{\lambda}(O|M)P(M)} $$

In a slightly confusing bit of standard nomenclature, CMLE is generally referred to instead as Maximum Mutual Information Estimation (MMIE). This is because it turns out that maximizing the posterior $ P(W|O) $ and maximizing the mutual information $ I(W,O) $ are equivalent if we assume that the language model probability of each sentence W is constant (fixed) during acoustic training, an assumption we usually make. Thus from here on we will refer to this criterion as the MMIE criterion rather than the CMLE criterion, and so here is Eq. 10.8 restated:

$$ \mathcal{F}_{\mathrm{M M I E}}(\lambda)=P_{\lambda}(M_{k}|O)=\frac{P_{\lambda}(O|M_{k})P(M_{k})}{\sum_{M\in\mathcal{L}}P_{\lambda}(O|M)P(M)} $$

In a nutshell, then, the goal of MMIE estimation is to maximize (10.9) rather than (10.4). Now if our goal is to maximize $ P_{\lambda}(M_k|O) $, we not only need to maximize the numerator of (10.9), but also minimize the denominator. Notice that we can rewrite the denominator to make it clear that it includes a term equal to the model we are trying to maximize and a term for all other models:

$$ P_{\lambda}(M_{k}|O)=\frac{P_{\lambda}(O|M_{k})P(M_{k})}{P_{\lambda}(O|M_{k})P(M_{k})+\sum_{i\neq k}P_{\lambda}(O|M_{i})P(M_{i})} $$

Thus in order to maximize $ P_\lambda(M_k|O) $, we will need to incrementally change $ \lambda $ so that it increases the probability of the correct model, while simultaneously decreasing the probability of each of the incorrect models. Thus training with MMIE clearly fulfills the important goal of discriminating between the correct sequence and all other sequences.

The implementation of MMIE is quite complex, and we don't discuss it here except to mention that it relies on a variant of Baum-Welch training called Extended Baum-Welch that maximizes (10.9) instead of (10.4). Briefly, we can view this as a two step algorithm; we first use standard MLE Baum-Welch to compute the forward-backward counts for the training utterances. Then we compute another forward-backward pass using all other possible utterances and subtract these from the counts. Of course it turns out that computing this full denominator is computationally extremely expensive, because it requires running a full recognition pass on all the training data. Recall that in normal EM, we don't need to run decoding on the training data, since we are only trying to maximize the likelihood of the correct word sequence; in MMIE, we need to compute the probabilities of all possible word sequences. Decoding is very time-consuming because of complex language models. Thus in practice MMIE algorithms estimate the denominator by summing over only the paths that occur in a word lattice, as an approximation to the full set of possible paths.

CMLE was first proposed by Nadas (1983) and MMIE by Bahl et al. (1986), but practical implementations that actually reduced word error rate came much later; see Woodland and Povey (2002) or Normandin (1996) for details.