9.4.3 Probabilities, log probabilities and distance functions

Up to now, all the equations we have given for acoustic modeling have used probabilities. It turns out, however, that a log probability (or logprob) is much easier to work with than a probability. Thus in practice throughout speech recognition (and related fields) we compute log-probabilities rather than probabilities.

One major reason that we can’t use probabilities is numeric underflow. To compute a likelihood for a whole sentence, say, we are multiplying many small probability values, one for each 10ms frame. Multiplying many probabilities results in smaller and smaller numbers, leading to underflow. The log of a small number like .00000001 = 10^{-8}, on the other hand, is a nice easy-to-work-with-number like -8. A second reason to use log probabilities is computational speed. Instead of multiplying probabilities, we add log-probabilities, and adding is faster than multiplying. Log-probabilities are particularly efficient when we are using Gaussian models, since we can avoid exponentiating.

Thus for example for a single multivariate diagonal-covariance Gaussian model, instead of computing:

$$ b_{j}(o_{t})=\prod_{d=1}^{D}\frac{1}{\sqrt{2\pi\sigma_{jd}^{2}}}exp\left(-\frac{1}{2}\frac{(o_{td}-\mu_{jd})^{2}}{\sigma_{jd}^{2}}\right) $$

we would compute

$$ \log b_{j}(o_{t})=-\frac{1}{2}\sum_{d=1}^{D}\left[log(2\pi)+\sigma_{jd}^{2}+\frac{(o_{td}-\mu_{jd})^{2}}{\sigma_{jd}^{2}}\right] $$

With some rearrangement of terms, we can rewrite this equation to pull out a constant C:

$$ \log b_{j}(o_{t})=C-\frac{1}{2}\sum_{d=1}^{D}\frac{(o_{td}-\mu_{jd})^{2}}{\sigma_{jd}^{2}} $$

where C can be precomputed:

$$ C=-\frac{1}{2}\sum_{d=1}^{D}\left(\log(2\pi)+\sigma_{j d}^{2}\right) $$

In summary, computing acoustic models in log domain means a much simpler computation, much of which can be precomputed for speed.

The perceptive reader may have noticed that equation (9.45) looks very much like the equation for Mahalanobis distance (9.20). Indeed, one way to think about Gaussian logprobs is as just a weighted distance metric.

A further point about Gaussian pdfs, for those readers with calculus. Although the equations for observation likelihood such as (9.26) are motivated by the use of Gaussian probability density functions, the values they return for the observation likelihood,

$ b_j(o_t) $, are not technically probabilities; they may in fact be greater than one. This is because we are computing the value of $ b_j(o_t) $ at a single point, rather than integrating over a region. While the total area under the Gaussian PDF curve is constrained to one, the actual value at any point could be greater than one. (Imagine a very tall skinny Gaussian; the value could be greater than one at the center, although the area under the curve is still 1.0). If we were integrating over a region, we would be multiplying each point by its width $ dx $, which would bring the value down below one. The fact that the Gaussian estimate is not a true probability doesn't matter for choosing the most likely HMM state, since we are comparing different Gaussians, each of which is missing this dx factor.

In summary, the last few subsections introduced Gaussian models for acoustic training in speech recognition. Beginning with simple univariate Gaussian, we extended first to multivariate Gaussians to deal with the multidimensional acoustic feature vectors. We then introduced the diagonal covariance simplification of Gaussians, and then introduced Gaussians mixtures (GMMs).

9.5 THE LEXICON AND LANGUAGE MODEL

Since previous chapters had extensive discussions of the N-gram language model (Ch. 4) and the pronunciation lexicon (Ch. 7), in this section we just briefly recall them to the reader.

Language models for LVCSR tend to be trigrams or even fourgrams; good toolkits are available to build and manipulate them (Stolcke, 2002; Young et al., 2005). Bigrams and unigram grammars are rarely used for large-vocabulary applications. Since trigrams require huge amounts of space, however, language models for memory-constrained applications like cell phones tend to use smaller contexts (or use compression techniques). As we will discuss in Ch. 24, some simple dialogue applications take advantage of their limited domain to use very simple finite state or weighted-finite state grammars.

Lexicons are simply lists of words, with a pronunciation for each word expressed as a phone sequence. Publicly available lexicons like the CMU dictionary (CMU, 1993) can be used to extract the 64,000 word vocabularies commonly used for LVCSR. Most words have a single pronunciation, although some words such as homonyms and frequent function words may have more; the average number of pronunciations per word in most LVCSR systems seems to range from 1 to 2.5. Sec. ?? in Ch. 10 discusses the issue of pronunciation modeling.

9.6 SEARCH AND DECODING

We are now very close to having described all the parts of a complete speech recognizer. We have shown how to extract cepstral features for a frame, and how to compute the acoustic likelihood $ b_{j}(o_{t}) $ for that frame. We also know how to represent lexical knowledge, that each word HMM is composed of a sequence of phone models, and

each phone model of a set of subphone states. Finally, in Ch. 4 we showed how to use N-grams to build a model of word predictability.

In this section we show how to combine all of this knowledge to solve the problem of decoding: combining all these probability estimators to produce the most probable string of words. We can phrase the decoding question as: ‘Given a string of acoustic observations, how should we choose the string of words which has the highest posterior probability?’

Recall from the beginning of the chapter the noisy channel model for speech recognition. In this model, we use Bayes rule, with the result that the best sequence of words is the one that maximizes the product of two factors, a language model prior and an acoustic likelihood:

$$ \hat{W}=\underset{W\in\mathcal{L}}{\mathrm{a r g m a x}}\overbrace{P(O|W)}^{likelihood\ prior}\overbrace{P(W)}^{} $$

Now that we have defined both the acoustic model and language model we are ready to see how to find this maximum probability sequence of words. First, though, it turns out that we’ll need to make a modification to Equation (9.47), because it relies on some incorrect independence assumptions. Recall that we trained a multivariate Gaussian mixture classifier to compute the likelihood of a particular acoustic observation (a frame) given a particular state (subphone). By computing separate classifiers for each acoustic frame and multiplying these probabilities to get the probability of the whole word, we are severely underestimating the probability of each subphone. This is because there is a lot of continuity across frames; if we were to take into account the acoustic context, we would have a greater expectation for a given frame and hence could assign it a higher probability. We must therefore reweight the two probabilities. We do this by adding in a language model scaling factor or LMSF, also called the language weight. This factor is an exponent on the language model probability $ P(W) $. Because $ P(W) $ is less than one and the LMSF is greater than one (between 5 and 15, in many systems), this has the effect of decreasing the value of the LM probability:

$$ \hat{W}=\underset{W\in\mathcal{L}}{\mathrm{a r g m a x}}P(O|W)P(W)^{L M S F} $$

Reweighting the language model probability $P(W)$ in this way requires us to make one more change. This is because $P(W)$ has a side-effect as a penalty for inserting words. It's simplest to see this in the case of a uniform language model, where every word in a vocabulary of size $|V|$ has an equal probability $\frac{1}{|V|}$. In this case, a sentence with $N$ words will have a language model probability of $\frac{1}{|V|}$ for each of the $N$ words, for a total penalty of of $\frac{N}{|V|}$. The larger $N$ is (the more words in the sentence), the more times this $\frac{1}{V}$ penalty multiplier is taken, and the less probable the sentence will be. Thus if (on average) the language model probability decreases (causing a larger penalty), the decoder will prefer fewer, longer words. If the language model probability increases (larger penalty), the decoder will prefer more shorter words. Thus our use of a LMSF to balance the acoustic model has the side-effect of decreasing the word insertion penalty. To offset this, we need to add back in a separate word insertion penalty:

$$ \hat{W}=\underset{W\in\mathcal{L}}{\operatorname{a r g m a x}}P(O|W)P(W)^{{L M S F}}W I P^{N} $$

Since in practice we use logprobs, the goal of our decoder is:

$$ \hat{W}=\underset{W\in\mathcal{L}}{\operatorname{argmax}}\log P(O|W)+LMSF\times\log P(W)+N\times\log WIP $$

Now that we have an equation to maximize, let's look at how to decode. It's the job of a decoder to simultaneously segment the utterance into words and identify each of these words. This task is made difficult by variation, both in terms of how words are pronounced in terms of phones, and how phones are articulated in acoustic features. Just to give an intuition of the difficulty of the problem imagine a massively simplified version of the speech recognition task, in which the decoder is given a series of discrete phones. In such a case, we would know what each phone was with perfect accuracy, and yet decoding is still difficult. For example, try to decode the following sentence from the (hand-labeled) sequence of phones from the Switchboard corpus (don't peek ahead!):

[ay d ih s hh er d s ah m th ih ng ax b aw m uh v ih ng r ih s en l ih]

The answer is in the footnote.² The task is hard partly because of coarticulation and fast speech (e.g., [d] for the first phone of just!). But it’s also hard because speech, unlike English writing, has no spaces indicating word boundaries. The true decoding task, in which we have to identify the phones at the same time as we identify and segment the words, is of course much harder.

For decoding, we will start with the Viterbi algorithm that we introduced in Ch. 6, in the domain of digit recognition, a simple task with which a vocabulary size of 11 (the numbers one through nine plus zero and oh).

Recall the basic components of an HMM model for speech recognition:

$$ Q=q_{1}q_{2}\ldots q_{N} $$

a set of states corresponding to subphones

$$ A=a_{01}a_{02}\ldots a_{n1}\ldots a_{nn} $$

a transition probability matrix $A$, each $a_{ij}$ representing the probability for each subphone of taking a self-loop or going to the next subphone. Together, $Q$ and $A$ implement a pronunciation lexicon, an HMM state graph structure for each word that the system is capable of recognizing.

$$ \boldsymbol{B}=\boldsymbol{b}_{i}(o_{t}) $$

A set of observation likelihoods: also called emission probabilities, each expressing the probability of a cepstral feature vector (observation $ o_{t} $) being generated from subphone state i.

The HMM structure for each word comes from a lexicon of word pronunciations. Generally we use an off-the-shelf pronunciation dictionary such as the free CMUdict dictionary described in Ch. 7. Recall from page 9 that the HMM structure for words in

speech recognition is a simple concatenation of phone HMMs, each phone consisting of 3 subphone states, where every state has exactly two transitions: a self-loop and a loop to the next phones. Thus the HMM structure for each digit word in our digit recognizer is computed simply by taking the phone string from the dictionary, expanding each phone into 3 subphones, and concatenating together. In addition, we generally add an optional silence phone at the end of each word, allowing the possibility of pausing between words. We usually define the set of states Q from some version of the ARPAbet, augmented with silence phones, and expanded to create three subphones for each phone.

The A and B matrices for the HMM are trained by the Baum-Welch algorithm in the embedded training procedure that we will describe in Sec. 9.7. For now we'll assume that these probabilities have been trained.

Fig. 9.22 shows the resulting HMM for digit recognition. Note that we've added non-emitting start and end states, with transitions from the end of each word to the end state, and a transition from the end state back to the start state to allow for sequences of digits. Note also the optional silence phones at the end of each word.

Digit recognizers often don't use word probabilities, since in many digit situations (phone numbers or credit card numbers) each digit may have an equal probability of appearing. But we've included transition probabilities into each word in Fig. 9.22, mainly to show where such probabilities would be for other kinds of recognition tasks. As it happens, there are cases where digit probabilities do matter, such as in addresses (which are often likely to end in 0 or 00) or in cultures where some numbers are lucky and hence more frequent, such as the lucky number '8' in Chinese.

Now that we have an HMM, we can use the same forward and Viterbi algorithms that we introduced in Ch. 6. Let's see how to use the forward algorithm to generate $ P(O|W) $, the likelihood of an observation sequence $ O $ given a sequence of words $ W $; we'll use the single word "five". In order to compute this likelihood, we need to sum over all possible sequences of states; assuming five has the states [f], [ay], and [v], a 10-observation sequence includes many sequences such as the following:

The forward algorithm efficiently sums over this large number of sequences in $ O(N^{2}T) $ time.

Let's quickly review the forward algorithm. It is a dynamic programming algorithm, i.e. an algorithm that uses a table to store intermediate values as it builds up the probability of the observation sequence. The forward algorithm computes the observation probability by summing over the probabilities of all possible paths that could generate the observation sequence.

Each cell of the forward algorithm trellis $ \alpha_t(j) $ or forward $ [t,j] $ represents the probability of being in state $ j $ after seeing the first $ t $ observations, given the automaton $ \lambda $. The

value of each cell $ \alpha_{t}(j) $ is computed by summing over the probabilities of every path that could lead us to this cell. Formally, each cell expresses the following probability:

$$ \alpha_{t}(j)=P(o_{1},o_{2}\ldots o_{t},q_{t}=j|\lambda) $$

Here $q_{t}=j$ means “the probability that the $t$th state in the sequence of states is state $j$”. We compute this probability by summing over the extensions of all the paths that lead to the current cell. For a given state $q_{j}$ at time $t$, the value $\alpha_{t}(j)$ is computed as:

$$ \alpha_{t}(j)=\sum_{i=1}^{N}\alpha_{t-1}(i)a_{ij}b_{j}(o_{t}) $$

The three factors that are multiplied in Eq' 9.52 in extending the previous paths to compute the forward probability at time t are:

$ \alpha_{t-1}(i) $ the previous forward path probability from the previous time step

$ a_{ij} $ the transition probability from previous state $ q_{i} $ to current state $ q_{j} $

$ b_{j}(o_{t}) $ the state observation likelihood of the observation symbol $ o_{t} $ given the current state j

The algorithm is described in Fig. 9.23.

function FORWARD(observations of len T, state-graph of len N) returns forward-prob

create a probability matrix forward[N+2,T]

for each state s from 1 to N do

forward[s,1] ← $ a_{0,s} * b_s(o_1) $

for each time step t from 2 to T do

for each state s from 1 to N do

forward[s,t] ← $ \sum_{t'=1}^{N} forward[s',t-1] * a_{s',s} * b_s(o_t) $

forward[qF,T] ← $ \sum_{s'=1}^{N} forward[s,T] * a_{s,qF} $

return forward[qF,T]

;initialization step

;recursion step

Let's see a trace of the forward algorithm running on a simplified HMM for the single word five given 10 observations; assuming a frame shift of 10ms, this comes to 100ms. The HMM structure is shown vertically along the left of Fig. 9.24, followed by the first 3 time-steps of the forward trellis. The complete trellis is shown in Fig. 9.25, together with B values giving a vector of observation likelihoods for each frame. These likelihoods could be computed by any acoustic model (GMMs or other); in this example we've hand-created simple values for pedagogical purposes.

Let's now turn to the question of decoding. Recall the Viterbi decoding algorithm from our description of HMMs in Ch. 6. The Viterbi algorithm returns the most likely state sequence (which is not the same as the most likely word sequence, but is often a good enough approximation) in time $ O(N^2T) $.

Each cell of the Viterbi trellis, $ v_t(j) $ represents the probability that the HMM is in state $ j $ after seeing the first $ t $ observations and passing through the most likely state sequence $ q_{1\cdots q_{t-1}} $, given the automaton $ \lambda $. The value of each cell $ v_t(j) $ is computed by recursively taking the most probable path that could lead us to this cell. Formally, each cell expresses the following probability:

$$ v_{t}(j)=P(q_{0},q_{1}...q_{t-1},o_{1},o_{2}...o_{t},q_{t}=j|\lambda) $$

Like other dynamic programming algorithms, Viterbi fills each cell recursively. Given that we had already computed the probability of being in every state at time

$t-1$, We compute the Viterbi probability by taking the most probable of the extensions of the paths that lead to the current cell. For a given state $q_j$ at time $t$, the value $v_t(j)$ is computed as:

$$ v_{t}(j)=\max_{i=1}^{N}v_{t-1}(i)a_{ij}b_{j}(o_{t}) $$

The three factors that are multiplied in Eq. 9.54 for extending the previous paths to compute the Viterbi probability at time t are:

$ v_{t-1}(i) $ the previous Viterbi path probability from the previous time step

$ a_{ij} $ the transition probability from previous state $ q_{i} $ to current state $ q_{j} $

$ b_j(o_t) $ the state observation likelihood of the observation symbol $ o_t $ given the current state j

Fig. 9.26 shows the Viterbi algorithm, repeated from Ch. 6.

function VITERBI(observations of len T,state-graph of len N) returns best-path

create a path probability matrix viterbi[N+2,T]

for each state s from 1 to N do

;initialization step

viterbi[s,1]←a_{0,s} * b_{s}(o_{1})

backpointer[s,1]←0

for each time step t from 2 to T do

;recursion step

for each state s from 1 to N do

viterbi[s,t]←max_{s=1}^{N} viterbi[s',t-1] * a_{s',s} * b_{s}(o_{t})

backpointer[s,t]←argmax_{s=1}^{N} viterbi[s',t-1] * a_{s',s}

viterbi[q_{F},T]←max_{s=1}^{N} viterbi[s,T] * a_{s,q_{F}} ; termination step

backpointer[q_{F},T]←argmax_{s=1}^{N} viterbi[s,T] * a_{s,q_{F}} ; termination step

return the backtrace path by following backpointers to states back in time from backpointer[q_{F},T]

Figure 9.26 Viterbi algorithm for finding optimal sequence of hidden states. Given an observation sequence of words and an HMM (as defined by the A and B matrices), the algorithm returns the state-path through the HMM which assigns maximum likelihood to the observation sequence. $ a[s',s] $ is the transition probability from previous state $ s' $ to current state s, and $ b_{s}(o_{t}) $ is the observation likelihood of s given $ o_{t} $. Note that states 0 and 1 are non-emitting start and end states.

Recall that the goal of the Viterbi algorithm is to find the best state sequence $ q = (q_1 q_2 q_3 \ldots q_T) $ given the set of observations $ o = (o_1 o_2 o_3 \ldots o_T) $. It needs to also find the probability of this state sequence. Note that the Viterbi algorithm is identical to the forward algorithm except that it takes the MAX over the previous path probabilities where forward takes the SUM.

Fig. 9.27 shows the computation of the first three time-steps in the Viterbi trellis corresponding to the forward trellis in Fig. 9.24. We have again used the made-up probabilities for the cepstral observations; here we also follow common convention in not showing the zero cells in the upper left corner. Note that only the middle cell in the third column differs from Viterbi to forward. Fig. 9.25 shows the complete trellis.

Note the difference between the final values from the Viterbi and forward algorithms for this (made-up) example. The forward algorithm gives the probability of the observation sequence as .00128, which we get by summing the final column. The Viterbi algorithm gives the probability of the observation sequence given the best path, which we get from the Viterbi matrix as .000493. The Viterbi probability is much smaller than the forward probability, as we should expect since Viterbi comes from a single path, where the forward probability is the sum over all paths.

The real usefulness of the Viterbi decoder, of course, lies in its ability to decode a string of words. In order to do cross-word decoding, we need to augment the A matrix, which only has intra-word state transitions, with the inter-word probability of

transitioning from the end of one word to the beginning of another word. The digit HMM model in Fig. 9.22 showed that we could just treat each word as independent, and use only the unigram probability. Higher-order N-grams are much more common. Fig. 9.29, for example, shows an augmentation of the digit HMM with bigram probabilities.

A schematic of the HMM trellis for such a multi-word decoding task is shown in Fig. 9.30. The intraword transitions are exactly as shown in Fig. 9.27. But now between words we've added a transition. The transition probability on this arc, rather than coming from the A matrix inside each word, comes from the language model $ P(W) $.

Once the entire Viterbi trellis has been computed for the utterance, we can start from the most-probable state at the final time step and follow the backtrace pointers

backwards to get the most probable string of states, and hence the most probable string of words. Fig. 9.31 shows the backtrace pointers being followed back from the best

state, which happens to be at $ w_2 $, eventually through $ w_N $ and $ w_1 $, resulting in the final word string $ w_1 w_N \cdots w_2 $.

The Viterbi algorithm is much more efficient than exponentially running the forward algorithm for each possible word string. Nonetheless, it is still slow, and much modern research in speech recognition has focused on speeding up the decoding process. For example in practice in large-vocabulary recognition we do not consider all possible words when the algorithm is extending paths from one state-column to the next. Instead, low-probability paths are pruned at each time step and not extended to the next state column.

This pruning is usually implemented via beam search (Lowerre, 1968). In beam search, at each time $ t $, we first compute the probability of the best (most-probable) state/path $ D $. We then prune away any state which is worse than $ D $ by some fixed threshold (beam width) $ \theta $. We can talk about beam-search in both the probability and negative log probability domain. In the probability domain any path/state whose probability is less than $ \theta*D $ is pruned away; in the negative log domain, any path whose cost is greater than $ \theta+D $ is pruned. Beam search is implemented by keeping for each time step an active list of states. Only transitions from these words are extended when moving to the next time step.

Making this beam search approximation allows a significant speed-up at the cost of a degradation to the decoding performance. Huang et al. (2001) suggest that empirically a beam size of 5-10% of the search space is sufficient; 90-95% of the states are thus not considered. Because in practice most implementations of Viterbi use beam search, some of the literature uses the term beam search or time-synchronous beam search instead of Viterbi.

9.7 EMBEDDED TRAINING

We turn now to see how an HMM-based speech recognition system is trained. We've already seen some aspects of training. In Ch. 4 we showed how to train a language model. In Sec. 9.4, we saw how GMM acoustic models are trained by augmenting the EM algorithm to deal with training the means, variances, and weights. We also saw how posterior AM classifiers like SVMs or neural nets could be trained, although for neural nets we haven't yet seen how we get training data in which each frame is labeled with a phone identity.

In this section we complete the picture of HMM training by showing how this augmented EM training algorithm fits into the whole process of training acoustic models. For review, here are the three components of the acoustic model:

$$ Q=q_{1}q_{2}\ldots q_{N} $$

the subphones represented as a set of states

$$ A=a_{01}a_{02}\ldots a_{n1}\ldots a_{nn} $$

a subphone transition probability matrix $A$, each $a_{ij}$ representing the probability for each subphone of taking a self-loop or going to the next subphone. Together, $Q$ and $A$ implement a pronunciation lexicon, an HMM state graph structure for each word that the system is capable of recognizing.

$$ \boldsymbol{B}=\boldsymbol{b}_{i}(o_{t}) $$

A set of observation likelihoods:, also called emission probabilities, each expressing the probability of a cepstral feature vector (observation $ o_{t} $) being generated from subphone state i.

We will assume that the pronunciation lexicon, and thus the basic HMM state graph structure for each word, is pre-specified as the simple linear HMM structures with loopbacks on each state that we saw in Fig. 9.7 and Fig. 9.22. In general, speech recognition systems do not attempt to learn the structure of the individual word HMMs. Thus we only need to train the $B$ matrix, and we need to train the probabilities of the non-zero (self-loop and next-subphone) transitions in the $A$ matrix. All the other probabilities in the $A$ matrix are set to zero and never change.

The simplest possible training method, is hand-labeled isolated word training, in which we train separate the $B$ and $A$ matrices for the HMMs for each word based on hand-aligned training data. We are given a training corpus of digits, where each instance of a spoken digit is stored in a wavefile, and with the start and end of each word and phone hand-segmented. Given such a hand-labeled database, we can compute the $B$ Gaussians observation likelihoods and the $A$ transition probabilities by merely counting in the training data! The $A$ transition probability are specific to each word, but the $B$ Gaussians would be shared across words if the same phone occurred in multiple words.

Unfortunately, hand-segmented training data is rarely used in training systems for continuous speech. One reason is that it is very expensive to use humans to hand-label phonetic boundaries; it can take up to 400 times real time (i.e. 400 labeling hours to label each 1 hour of speech). Another reason is that humans don't do phonetic

labeling very well for units smaller than the phone; people are bad at consistently finding the boundaries of subphones. ASR systems aren't better than humans at finding boundaries, but their errors are at least consistent between the training and test sets.

For this reason, speech recognition systems train each phone HMM embedded in an entire sentence, and the segmentation and phone alignment are done automatically as part of the training procedure. This entire acoustic model training process is therefore called \textit{embedded training}. Hand phone segmentation do still play some role, however, for example for bootstrapping initial systems for discriminative (SVM; non-Gaussian) likelihood estimators, or for tasks like phone recognition.

In order to train a simple digits system, we'll need a training corpus of spoken digit sequences. For simplicity assume that the training corpus is separated into separate wavefiles, each containing a sequence of spoken digits. For each wavefile, we'll need to know the correct sequence of digit words. We'll thus associate with each wavefile a transcription (a string of words). We'll also need a pronunciation lexicon and a phone-set, defining a set of (untrained) phone HMMs. From the transcription, lexicon, and phone HMMs, we can build a "whole sentence" HMM for each sentence, as shown in Fig. 9.32.

We are now ready to train the transition matrix A and output likelihood estimator B for the HMMs. The beauty of the Baum-Welch-based paradigm for embedded training of HMMs is that this is all the training data we need. In particular, we don't need phonetically transcribed data. We don't even need to know where each word starts and ends. The Baum-Welch algorithm will sum over all possible segmentations of words.

and phones, using $ \xi_{j}(t) $, the probability of being in state j at time t and generating the observation sequence O.

We will, however, need an initial estimate for the transition and observation probabilities $ a_{ij} $ and $ b_j(o_t) $. The simplest way to do this is with a flat start. In flat start, we first set to zero any HMM transitions that we want to be ‘structurally zero’, such as transitions from later phones back to earlier phones. The $ \gamma $ probability computation in Baum-Welch includes the previous value of $ a_{ij} $, so those zero values will never change. Then we make all the rest of the (non-zero) HMM transitions equiprobable. Thus the two transitions out of each state (the self-loop and the transition to the following sub-phone) each would have a probability of 0.5. For the Gaussians, a flat start initializes the mean and variance for each Gaussian identically, to the global mean and variance for the entire training data.

Now we have initial estimates for the A and B probabilities. For a standard Gaussian HMM system, we now run multiple iterations of the Baum-Welch algorithm on the entire training set. Each iteration modifies the HMM parameters, and we stop when the system converges. During each iteration, as discussed in Ch. 6, we compute the forward and backward probabilities for each sentence given the initial A and B probabilities, and use them to re-estimate the A and B probabilities. We also apply the various modifications to EM discussed in the previous section to correctly update the Gaussian means and variances for multivariate Gaussians. We will discuss in Sec. ?? in Ch. 10 how to modify the embedded training algorithm to handle mixture Gaussians.

In summary, the basic embedded training procedure is as follows:

Given: phoneset, pronunciation lexicon, and the transcribed wavefiles

1. Build a “whole sentence” HMM for each sentence, as shown in Fig. 9.32.

2. Initialize A probabilities to 0.5 (for loop-backs or for the correct next subphone) or to zero (for all other transitions).

3. Initialize B probabilities by setting the mean and variance for each Gaussian to the global mean and variance for the entire training set.

4. Run multiple iterations of the Baum-Welch algorithm.

The Baum-Welch algorithm is used repeatedly as a component of the embedded training process. Baum-Welch computes $ \xi_t(i) $, the probability of being in state $ i $ at time $ t $, by using forward-backward to sum over all possible paths that were in state $ i $ emitting symbol $ o_t $ at time $ t $. This lets us accumulate counts for re-estimating the emission probability $ b_j(o_t) $ from all the paths that pass through state $ j $ at time $ t $. But Baum-Welch itself can be time-consuming.

There is an efficient approximation to Baum-Welch training that makes use of the Viterbi algorithm. In Viterbi training, instead of accumulating counts by a sum over all paths that pass through a state j at time t, we approximate this by only choosing the Viterbi (most-probable) path. Thus instead of running EM at every step of the embedded training, we repeatedly run Viterbi.

Running the Viterbi algorithm over the training data in this way is called forced Viterbi alignment or just forced alignment. In Viterbi training (unlike in Viterbi decoding on the test set) we know which word string to assign to each observation

sequence, So we can ‘force’ the Viterbi algorithm to pass through certain words, by setting the $ a_{ij} $s appropriately. A forced Viterbi is thus a simplification of the regular Viterbi decoding algorithm, since it only has to figure out the correct state (subphone) sequence, but doesn’t have to discover the word sequence. The result is a forced alignment: the single best state path corresponding to the training observation sequence. We can now use this alignment of HMM states to observations to accumulate counts for reestimating the HMM parameters. We saw earlier that forced alignment can also be used in other speech applications like text-to-speech, whenever we have a word transcript and a wavefile in which we want to find boundaries.

The equations for retraining a (non-mixture) Gaussian from a Viterbi alignment are as follows:

$$ \hat{\mu}_{i}=\frac{1}{T}\sum_{t=1}^{T}o_{t}s.t.q_{t}is state i $$

$$ \hat{\sigma}_{j}^{2}~=~\frac{1}{T}\sum_{t=1}^{T}(o_{t}-\mu_{i})^{2}~\mathrm{s.t.}~q_{t}\mathrm{~i s~s t a t e~}i $$

We saw these equations already, as (9.27) and (9.28) on page 25, when we were ‘imagining the simpler situation of a completely labeled training set’.

It turns out that this forced Viterbi algorithm is also used in the embedded training of hybrid models like HMM/MLP or HMM/SVM systems. We begin with an untrained MLP, and using its noisy outputs as the $B$ values for the HMM, perform a forced Viterbi alignment of the training data. This alignment will be quite errorful, since the MLP was random. Now this (quite errorful) Viterbi alignment gives us a labeling of feature vectors with phone labels. We use this labeling to retrain the MLP. The counts of the transitions which are taken in the forced alignments can be used to estimate the HMM transition probabilities. We continue this hill-climbing process of neural-net training and Viterbi alignment until the HMM parameters begin to converge.

9.8 EVALUATION: WORD ERROR RATE

WORD ERROR

The standard evaluation metric for speech recognition systems is the word error rate. The word error rate is based on how much the word string returned by the recognizer (often called the hypothesized word string) differs from a correct or reference transcription. Given such a correct transcription, the first step in computing word error is to compute the minimum edit distance in words between the hypothesized and correct strings, as described in Ch. 3. The result of this computation will be the minimum number of word substitutions, word insertions, and word deletions necessary to map between the correct and hypothesized strings. The word error rate (WER) is then defined as follows (note that because the equation includes insertions, the error rate can be greater than 100%):

$$ \text{Word Error Rate}=100\times\frac{Insertions+Substitutions+Deletions}{Total~Words~in~Correct~Transcript} $$

We sometimes also talk about the SER (Sentence Error Rate), which tells us how many sentences had at least one error:

$$ \begin{array}{c} Sentence~Error~Rate~=~100\times\frac{\#of~sentences~with~at~least~one~word~error}{total~\#of~sentences}\end{array} $$

ALIGNMENTS

Here is an example of the alignments between a reference and a hypothesized utterance from the CALLHOME corpus, showing the counts used to compute the word error rate:

This utterance has six substitutions, three insertions, and one deletion:

$$ Word~Error~Rate~=~100\frac{6+3+1}{13}=76.9\% $$

The standard method for implementing minimum edit distance and computing word error rates is a free script called sclite, available from the National Institute of Standards and Technologies (NIST) (NIST, 2005). sclite is given a series of reference (hand-transcribed, gold-standard) sentences and a matching set of hypothesis sentences. Besides performing alignments, and computing word error rate, sclite performs a number of other useful tasks. For example, it gives useful information for error analysis, such as confusion matrices showing which words are often misrecognized for others, and gives summary statistics of words which are often inserted or deleted. sclite also gives error rates by speaker (if sentences are labeled for speaker id), as well as useful statistics like the sentence error rate, the percentage of sentences with at least one word error.

Finally, sclite can be used to compute significance tests. Suppose we make some changes to our ASR system and find that our word error rate has decreased by 1%. In order to know if our changes really improved things, we need a statistical test to make sure that the 1% difference is not just due to chance. The standard statistical test for determining if two word error rates are different is the Matched-Pair Sentence Segment Word Error (MAPSSWE) test, which is also available in sclite (although the McNemar test is sometimes used as well).

The MAPSSWE test is a parametric test that looks at the difference between the number of word errors the two systems produce, averaged across a number of segments. The segments may be quite short or as long as an entire utterance; in general we want to have the largest number of (short) segments in order to justify the normality assumption and for maximum power. The test requires that the errors in one segment be statistically independent of the errors in another segment. Since ASR systems tend to use trigram LMs, this can be approximated by defining a segment as a region bounded on both sides by words that both recognizers get correct (or turn/utterance boundaries).

Here's an example from NIST (2007) with four segments, labeled in roman numerals:

In region I, system A has 2 errors (a deletion and an insertion) and system B has 0; in region III system A has 1 (substitution) error and system B has 2. Let's define a sequence of variables Z representing the difference between the errors in the two systems as follows:

$ N_{A}^{i} $ the number of errors made on segment i by system A

$ N_{B}^{i} $ the number of errors made on segment i by system B

$$ Z\qquad N_{A}^{i}-N_{B}^{i},i=1,2,\cdots,n\text{where}n\text{is the number of segments} $$

For example in the example above the sequence of $Z$ values is $\{2, -1, -1, 1\}$. Intuitively, if the two systems are identical, we would expect the average difference, i.e. the average of the $Z$ values, to be zero. If we call the true average of the differences $mu_z$, we would thus like to know whether $mu_z = 0$. Following closely the original proposal and notation of Gillick and Cox (1989), we can estimate the true average from our limited sample as $\hat{\mu}_z = \sum_{i=1}^{n} Z_i/n$.

The estimate of the variance of the $ Z_{i} $'s is:

$$ \sigma_{z}^{2}=\frac{1}{n-1}\sum_{i=1}^{n}\left(Z_{i}-\mu_{z}\right)^{2} $$

Let

$$ W=\frac{\hat{\mu}_{z}}{\sigma_{z}/\sqrt{n}} $$

For a large enough $n$ (>50) W will approximately have a normal distribution with unit variance. The null hypothesis is $H_0: \mu_z = 0$, and it can thus be rejected if $2 * P(Z \geq |w|) \leq 0.05$ (two-tailed) or $P(Z \geq |w|) \leq 0.05$ (one-tailed). where $Z$ is standard normal and $w$ is the realized value $W$; these probabilities can be looked up in the standard tables of the normal distribution.

Could we improve on word error rate as a metric? It would be nice, for example, to have something which didn't give equal weight to every word, perhaps valuing content words like Tuesday more than function words like a or of. While researchers generally agree that this would be a good idea, it has proved difficult to agree on a metric that works in every application of ASR. For dialogue systems, however, where the desired semantic output is more clear, a metric called concept error rate has proved extremely useful, and will be discussed in Ch. 24 on page ??.

9.9 SUMMARY

Together with Ch. 4 and Ch. 6, this chapter introduced the fundamental algorithms for addressing the problem of Large Vocabulary Continuous Speech Recognition.

• The input to a speech recognizer is a series of acoustic waves. The waveform, spectrogram and spectrum are among the visualization tools used to understand the information in the signal.

• In the first step in speech recognition, sound waves are sampled, quantized, and converted to some sort of spectral representation; A commonly used spectral representation is the mel cepstrum or MFCC which provides a vector of features for each frame of the input.

GMM acoustic models are used to estimate the phonetic likelihoods (also called observation likelihoods) of these feature vectors for each frame.

• Decoding or search or inference is the process of finding the optimal sequence of model states which matches a sequence of input observations. (The fact that there are three terms for this process is a hint that speech recognition is inherently inter-disciplinary, and draws its metaphors from more than one field; decoding comes from information theory, and search and inference from artificial intelligence).

• We introduced two decoding algorithms: time-synchronous Viterbi decoding (which is usually implemented with pruning and can then be called beam search) and stack or A $ ^{*} $ decoding. Both algorithms take as input a sequence of cepstral feature vectors, a GMM acoustic model, and an N-gram language model, and produce a string of words.

• The embedded training paradigm is the normal method for training speech recognizers. Given an initial lexicon with hand-built pronunciation structures, it will train the HMM transition probabilities and the HMM observation probabilities.

BIBLIOGRAPHICAL AND HISTORICAL NOTES

The first machine which recognized speech was probably a commercial toy named "Radio Rex" which was sold in the 1920s. Rex was a celluloid dog that moved (via a spring) when the spring was released by 500 Hz acoustic energy. Since 500 Hz is roughly the first formant of the vowel [eh] in "Rex", the dog seemed to come when he was called (David and Selfridge, 1962).

By the late 1940s and early 1950s, a number of machine speech recognition systems had been built. An early Bell Labs system could recognize any of the 10 digits from a single speaker (Davis et al., 1952). This system had 10 speaker-dependent stored patterns, one for each digit, each of which roughly represented the first two vowel formants in the digit. They achieved 97–99% accuracy by choosing the pattern which had the highest relative correlation coefficient with the input. Fry (1959) and Denes (1959) built a phoneme recognizer at University College, London, which recognized four vowels and nine consonants based on a similar pattern-recognition principle. Fry and Denes's system was the first to use phoneme transition probabilities to constrain the recognizer.

The late 1960s and early 1970s produced a number of important paradigm shifts. First were a number of feature-extraction algorithms, include the efficient Fast Fourier

Transform (FFT) (Cooley and Tukey, 1965), the application of cepstral processing to speech (Oppenheim et al., 1968), and the development of LPC for speech coding (Atal and Hanauer, 1971). Second were a number of ways of handling warping; stretching or shrinking the input signal to handle differences in speaking rate and segment length when matching against stored patterns. The natural algorithm for solving this problem was dynamic programming, and, as we saw in Ch. 6, the algorithm was reinvented multiple times to address this problem. The first application to speech processing was by Vintsyuk (1968), although his result was not picked up by other researchers, and was reinvented by Velichko and Zagoruyko (1970) and Sakoe and Chiba (1971) (and (1984)). Soon afterward, Itakura (1975) combined this dynamic programming idea with the LPC coefficients that had previously been used only for speech coding. The resulting system extracted LPC features for incoming words and used dynamic programming to match them against stored LPC templates. The non-probabilistic use of dynamic programming to match a template against incoming speech is called dynamic time warping.

The third innovation of this period was the rise of the HMM. Hidden Markov Models seem to have been applied to speech independently at two laboratories around 1972. One application arose from the work of statisticians, in particular Baum and colleagues at the Institute for Defense Analyses in Princeton on HMMs and their application to various prediction problems (Baum and Petrie, 1966; Baum and Eagon, 1967). James Baker learned of this work and applied the algorithm to speech processing (Baker, 1975) during his graduate work at CMU. Independently, Frederick Jelinek, Robert Mercer, and Lalit Bahl (drawing from their research in information-theoretical models influenced by the work of Shannon (1948)) applied HMMs to speech at the IBM Thomas J. Watson Research Center (Jelinek et al., 1975). IBM's and Baker's systems were very similar, particularly in their use of the Bayesian framework described in this chapter. One early difference was the decoding algorithm; Baker's DRAGON system used Viterbi (dynamic programming) decoding, while the IBM system applied Jelinek's stack decoding algorithm (Jelinek, 1969). Baker then joined the IBM group for a brief time before founding the speech-recognition company Dragon Systems. The HMM approach to speech recognition would turn out to completely dominate the field by the end of the century; indeed the IBM lab was the driving force in extending statistical models to natural language processing as well, including the development of class-based N-grams, HMM-based part-of-speech tagging, statistical machine translation, and the use of entropy/perplexity as an evaluation metric.

The use of the HMM slowly spread through the speech community. One cause was a number of research and development programs sponsored by the Advanced Research Projects Agency of the U.S. Department of Defense (ARPA). The first five-year program starting in 1971, and is reviewed in Klatt (1977). The goal of this first program was to build speech understanding systems based on a few speakers, a constrained grammar and lexicon (1000 words), and less than 10% semantic error rate. Four systems were funded and compared against each other: the System Development Corporation (SDC) system, Bolt, Beranek & Newman (BBN)'s HWIM system, Carnegie-Mellon University's Hearsay-II system, and Carnegie-Mellon's Harpy system (Lowerre, 1968). The Harpy system used a simplified version of Baker's HMM-based DRAGON system and was the best of the tested systems, and according to Klatt

the only one to meet the original goals of the ARPA project (with a semantic accuracy rate of 94% on a simple task).

Beginning in the mid-1980s, ARPA funded a number of new speech research programs. The first was the “Resource Management” (RM) task (Price et al., 1988), which like the earlier ARPA task involved transcription (recognition) of read-speech (speakers reading sentences constructed from a 1000-word vocabulary) but which now included a component that involved speaker-independent recognition. Later tasks included recognition of sentences read from the Wall Street Journal (WSJ) beginning with limited systems of 5,000 words, and finally with systems of unlimited vocabulary (in practice most systems use approximately 60,000 words). Later speech-recognition tasks moved away from read-speech to more natural domains; the Broadcast News domain (LDC, 1998; Graff, 1997) (transcription of actual news broadcasts, including quite difficult passages such as on-the-street interviews) and the Switchboard, CALLHOME, CALLFRIEND, and Fisher domains (Godfrey et al., 1992; Cieri et al., 2004) (natural telephone conversations between friends or strangers). The Air Traffic Information System (ATIS) task (Hemphill et al., 1990) was an earlier speech understanding task whose goal was to simulate helping a user book a flight, by answering questions about potential airlines, times, dates, and so forth.

Each of the ARPA tasks involved an approximately annual bake-off at which all ARPA-funded systems, and many other ‘volunteer’ systems from North American and Europe, were evaluated against each other in terms of word error rate or semantic error rate. In the early evaluations, for-profit corporations did not generally compete, but eventually many (especially IBM and ATT) competed regularly. The ARPA competitions resulted in widescale borrowing of techniques among labs, since it was easy to see which ideas had provided an error-reduction the previous year, and were probably an important factor in the eventual spread of the HMM paradigm to virtual every major speech recognition lab. The ARPA program also resulted in a number of useful databases, originally designed for training and testing systems for each evaluation (TIMIT, RM, WSJ, ATIS, BN, CALLHOME, Switchboard, Fisher) but then made available for general research use.

Speech research includes a number of areas besides speech recognition; we already saw computational phonology in Ch. 7, speech synthesis in Ch. 8, and we will discuss spoken dialogue systems in Ch. 24. Another important area is speaker identification and speaker verification, in which we identify a speaker (for example for security when accessing personal information over the telephone) (Reynolds and Rose, 1995; Shriberg et al., 2005; Doddington, 2001). This task is related to language identification, in which we are given a wavefile and have to identify which language is being spoken; this is useful for automatically directing callers to human operators that speak appropriate languages.

There are a number of textbooks and reference books on speech recognition that are good choices for readers who seek a more in-depth understanding of the material in this chapter: Huang et al. (2001) is by far the most comprehensive and up-to-date reference volume and is highly recommended. Jelinek (1997), Gold and Morgan (1999), and Raibiner and Juang (1993) are good comprehensive textbooks. The last two textbooks also have discussions of the history of the field, and together with the survey paper of Levinson (1995) have influenced our short history discussion in this chapter. Our description

of the forward-backward algorithm was modeled after Rabiner (1989), and we were also influenced by another useful tutorial paper, Knill and Young (1997). Research in the speech recognition field often appears in the proceedings of the annual INTER-SPEECH conference, (which is called ICSLP and EUROSPEECH in alternate years) as well as the annual IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP). Journals include Speech Communication, Computer Speech and Language, the IEEE Transactions on Audio, Speech, and Language Processing, and the ACM Transactions on Speech and Language Processing.

EXERCISES

9.1 Analyze each of the errors in the incorrectly recognized transcription of “um the phone is I left the...” on page 46. For each one, give your best guess as to whether you think it is caused by a problem in signal processing, pronunciation modeling, lexicon size, language model, or pruning in the decoding search.

9.2 In practice, speech recognizers do all their probability computation using the log probability (or logprob) rather than actual probabilities. This helps avoid underflow for very small probabilities, but also makes the Viterbi algorithm very efficient, since all probability multiplications can be implemented by adding log probabilities. Rewrite the pseudocode for the Viterbi algorithm in Fig. 9.26 on page 38 to make use of logprobs instead of probabilities.

9.3 Now modify the Viterbi algorithm in Fig. 9.26 on page 38 to implement the beam search described on page 41. Hint: You will probably need to add in code to check whether a given state is at the end of a word or not.

9.4 Finally, modify the Viterbi algorithm in Fig. 9.26 on page 38 with more detailed pseudocode implementing the array of backtrace pointers.

9.5 Using the tutorials available as part of a publicly available recognizer like HTK or Sonic, build a digit recognizer.

9.6 Take the digit recognizer above and dump the phone likelihoods for a sentence. Now take your implementation of the Viterbi algorithm and show that you can successfully decode these likelihoods.

Atal, B. S. and Hanauer, S. (1971). Speech analysis and synthesis by prediction of the speech wave. Journal of the Acoustical Society of America, 50, 637–655.

Baker, J. K. (1975). The DRAGON system – An overview. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-23(1), 24–29.

Baum, L. E. and Eagon, J. A. (1967). An inequality with applications to statistical estimation for probabilistic functions of Markov processes and to a model for ecology. Bulletin of the American Mathematical Society, 73(3), 360–363.

Baum, L. E. and Petrie, T. (1966). Statistical inference for probabilistic functions of finite-state Markov chains. Annals of Mathematical Statistics, 37(6), 1554–1563.

Bayes, T. (1763). An Essay Toward Solving a Problem in the Doctrine of Chances, Vol. 53. Reprinted in Facsimiles of two papers by Bayes, Hafner Publishing Company, New York, 1963.

Bledsoe, W. W. and Browning, I. (1959). Pattern recognition and reading by machine. In 1959 Proceedings of the Eastern Joint Computer Conference, pp. 225–232. Academic.

Cieri, C., Miller, D., and Walker, K. (2004). The Fisher Corpus: a Resource for the Next Generations of Speech-to-Text. In LREC-04.

CMU (1993). The Carnegie Mellon Pronouncing Dictionary v0.1. Carnegie Mellon University.

Cohen, P. R., Johnston, M., McGee, D., Oviatt, S. L., Clow, J., and Smith, I. (1998). The efficiency of multimodal interaction: a case study. In ICSLP-98, Sydney, Vol. 2, pp. 249–252.

Cooley, J. W. and Tukey, J. W. (1965). An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19(90), 297–301.

David, Jr., E. E. and Selfridge, O. G. (1962). Eyes and ears for computers. Proceedings of the IRE (Institute of Radio Engineers), 50, 1093–1101.

Davis, K. H., Biddulph, R., and Balashek, S. (1952). Automatic recognition of spoken digits. Journal of the Acoustical Society of America, 24(6), 637–642.

Davis, S. and Mermelstein, P. (1980). Comparison of parametric representations for monosyllabic word recognition in continuously spoken sentences. IEEE Transactions on Acoustics, Speech, and Signal Processing, 28(4), 357–366.

Denes, P. (1959). The design and operation of the mechanical speech recognizer at University College London. Journal of the British Institution of Radio Engineers, 19(4), 219–234. Appears together with companion paper (Fry 1959).

Deng, L. and Huang, X. (2004). Challenges in adopting speech recognition. Communications of the ACM, 47(1), 69–75.

Doddington, G. (2001). Speaker recognition based on idiolectal differences between speakers. In EUROSPEECH-01, Budapest, pp. 2521–2524.

Duda, R. O., Hart, P. E., and Stork, D. G. (2000). Pattern Classification. Wiley-Interscience Publication.

Fry, D. B. (1959). Theoretical aspects of mechanical speech recognition. Journal of the British Institution of Radio Engineers, 19(4), 211–218. Appears together with companion paper (Denes 1959).

Gillick, L. and Cox, S. (1989). Some statistical issues in the comparison of speech recognition algorithms. In IEEE ICASSP-89, pp. 532–535.

Godfrey, J., Holliman, E., and McDaniel, J. (1992). SWITCHBOARD: Telephone speech corpus for research and development. In IEEE ICASSP-92, San Francisco, pp. 517–520. IEEE.

Gold, B. and Morgan, N. (1999). Speech and Audio Signal Processing. Wiley Press.

Graff, D. (1997). The 1996 Broadcast News speech and language-model corpus. In Proceedings DARPA Speech Recognition Workshop, Chantilly, VA, pp. 11–14. Morgan Kaufmann.

Gray, R. M. (1984). Vector quantization. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-1(2), 4–29.

Hemphill, C. T., Godfrey, J., and Doddington, G. (1990). The ATIS spoken language systems pilot corpus. In Proceedings DARPA Speech and Natural Language Workshop, Hidden Valley, PA, pp. 96–101. Morgan Kaufmann.

Huang, X., Acero, A., and Hon, H.-W. (2001). Spoken Language Processing: A Guide to Theory, Algorithm, and System Development. Prentice Hall, Upper Saddle River, NJ.

Itakura, F. (1975). Minimum prediction residual principle applied to speech recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-32, 67–72.

Jelinek, F. (1969). A fast sequential decoding algorithm using a stack. IBM Journal of Research and Development, 13, 675–685.

Jelinek, F. (1997). Statistical Methods for Speech Recognition. MIT Press.

Jelinek, F., Mercer, R. L., and Bahl, L. R. (1975). Design of a linguistic statistical decoder for the recognition of continuous speech. IEEE Transactions on Information Theory, IT-21(3), 250–256.

Klatt, D. H. (1977). Review of the ARPA speech understanding project. Journal of the Acoustical Society of America, 62(6), 1345–1366.

Knill, K. and Young, S. J. (1997). Hidden Markov Models in speech and language processing. In Young, S. J. and Bloothooft, G. (Eds.), Corpus-based Methods in Language and Speech Processing, pp. 27–68. Kluwer, Dordrecht.

LDC (1998). LDC Catalog: Hub4 project. University of Pennsylvania. www.ldc.upenn.edu/Catalog/LDC98S71.html or www.ldc.upenn.edu/Catalog/Hub4.html.

Levinson, S. E. (1995). Structural methods in automatic speech recognition. Proceedings of the IEEE, 73(11), 1625–1650.

Lowerre, B. T. (1968). The Harpy Speech Recognition System. Ph.D. thesis, Carnegie Mellon University, Pittsburgh, PA.

Mosteller, F. and Wallace, D. L. (1964). Inference and Disputed Authorship: The Federalist. Springer-Verlag. A second edition appeared in 1984 as Applied Bayesian and Classical Inference.

NIST (2005). Speech recognition scoring toolkit (sctk) version 2.1. Available at http://www.nist.gov/speech/tools/.

NIST (2007). Matched Pairs Sentence-Segment Word Error (MAPSSWE) Test. http://www.nist.gov/speech/tests/sigtests/mapsswe.htm.

Oppenheim, A. V., Schafer, R. W., and Stockham, T. G. J. (1968). Nonlinear filtering of multiplied and convolved signals. Proceedings of the IEEE, 56(8), 1264–1291.

Price, P. J., Fisher, W., Bernstein, J., and Pallet, D. (1988). The DARPA 1000-word resource management database for continuous speech recognition. In IEEE ICASSP-88, New York, Vol. 1, pp. 651–654.

Rabiner, L. R. (1989). A tutorial on Hidden Markov Models and selected applications in speech recognition. Proceedings of the IEEE, 77(2), 257–286.

Rabiner, L. R. and Juang, B. H. (1993). Fundamentals of Speech Recognition. Prentice Hall.

Reynolds, D. A. and Rose, R. C. (1995). Robust text-independent speaker identification using gaussian mixture speaker models. IEEE Transactions on Speech and Audio Processing, 3(1), 72–83.

Sakoe, H. and Chiba, S. (1971). A dynamic programming approach to continuous speech recognition. In Proceedings of the Seventh International Congress on Acoustics, Budapest, Budapest, Vol. 3, pp. 65–69. Akadémiai Kiadó.

Sakoe, H. and Chiba, S. (1984). Dynamic programming algorithm optimization for spoken word recognition. IEEE Transactions on Acoustics, Speech, and Signal Processing, ASSP-26(1), 43–49.

Shannon, C. E. (1948). A mathematical theory of communication. Bell System Technical Journal, 27(3), 379–423. Continued in the following volume.

Shriberg, E., Ferrer, L., Kajarekar, S., Venkataraman, A., and Stolcke, A. (2005). Modeling prosodic feature sequences for speaker recognition. Speech Communication, 46(3-4), 455–472.

Stevens, S. S. and Volkmann, J. (1940). The relation of pitch to frequency: A revised scale. The American Journal of Psychology, 53(3), 329–353.

Stevens, S. S., Volkmann, J., and Newman, E. B. (1937). A scale for the measurement of the psychological magnitude pitch. Journal of the Acoustical Society of America, 8, 185–190.

Stolcke, A. (2002). Srilm - an extensible language modeling toolkit. In ICSLP-02, Denver, CO.

Taylor, P. (2008). Text-to-speech synthesis. Manuscript.

Tomokiyo, L. M. (2001). Recognizing non-native speech: Characterizing and adapting to non-native usage in speech recognition. Ph.D. thesis, Carnegie Mellon University.

Velichko, V. M. and Zagoruyko, N. G. (1970). Automatic recognition of 200 words. International Journal of Man-Machine Studies, 2, 223–234.

Vintsyuk, T. K. (1968). Speech discrimination by dynamic programming. Cybernetics, 4(1), 52–57. Russian Kibernetika 4(1):81-88 (1968).

Young, S. J., Evermann, G., Gales, M., Hain, T., Kershaw, D., Moore, G., Odell, J. J., Ollason, D., Povey, D., Valtchev, V., and Woodland, P. C. (2005). The HTK Book. Cambridge University Engineering Department.

10

SPEECH RECOGNITION: ADVANCED TOPICS

True, their voice-print machine was unfortunately a crude one. It could discriminate among only a few frequencies, and it indicated amplitude by indecipherable blots. But it had never been intended for such vitally important work.

Aleksandr I. Solzhenitsyn, The First Circle, p. 505

The keju civil service examinations of Imperial China lasted almost 1300 years, from the year 606 until it was abolished in 1905. In its peak, millions of would-be officials from all over China competed for high-ranking government positions by participating in a uniform examination. For the final ‘metropolitan’ part of this exam in the capital city, the candidates would be locked into an examination compound for a grueling 9 days and nights answering questions about history, poetry, the Confucian classics, and policy.

Naturally all these millions of candidates didn't all show up in the capital. Instead, the exam had progressive levels; candidates who passed a one-day local exam in their local prefecture could then sit for the biannual provincial exam, and only upon passing that exam in the provincial capital was a candidate eligible for the metropolitan and palace examinations.

This algorithm for selecting capable officials is an instance of multi-stage search. The final 9-day process requires far too many resources (in both space and time) to examine every candidate. Instead, the algorithm uses an easier, less intensive 1-day process to come up with a preliminary list of potential candidates, and applies the final test only to this list.

The keju algorithm can also be applied to speech recognition. We'd like to be able to apply very expensive algorithms in the speech recognition process, such as 4-gram, 5-gram, or even parser-based language models, or context-dependent phone models that can see two or three phones into the future or past. But there are a huge number of potential transcriptions sentences for any given waveform, and it's too expensive (in time, space, or both) to apply these powerful algorithms to every single candidate. Instead, we'll introduce \textit{multipass decoding} algorithms in which efficient but dumber decoding algorithms produce shortlists of potential candidates to be rescored by slow but smarter algorithms. We'll also introduce the \textit{context-dependent acoustic model}.

which is one of these smarter knowledge sources that turns out to be essential in large-vocabulary speech recognition. We'll also briefly introduce the important topics of discriminative training and the modeling of variation.

10.1 MULTIPASS DECODING: N-BEST LISTS AND LATTICES

The previous chapter applied the Viterbi algorithm for HMM decoding. There are two main limitations of the Viterbi decoder, however. First, the Viterbi decoder does not actually compute the sequence of words which is most probable given the input acoustics. Instead, it computes an approximation to this: the sequence of states (i.e., phones or subphones) which is most probable given the input. More formally, recall that the true likelihood of an observation sequence O is computed by the forward algorithm by summing over all possible paths:

VITERBI APPROXIMATION

$$ P(O|W)=\sum_{S\in S_{1}^{T}}P(O,S|W) $$

The Viterbi algorithm only approximates this sum by using the probability of the best path:

$$ P(O|W)\approx\max_{S\in S_{1}^{T}}P(O,S|W) $$

It turns out that this Viterbi approximation is not too bad, since the most probable sequence of phones usually turns out to correspond to the most probable sequence of words. But not always. Consider a speech recognition system whose lexicon has multiple pronunciations for each word. Suppose the correct word sequence includes a word with very many pronunciations. Since the probabilities leaving the start arc of each word must sum to 1.0, each of these pronunciation-paths through this multiple-pronunciation HMM word model will have a smaller probability than the path through a word with only a single pronunciation path. Thus because the Viterbi decoder can only follow one of these pronunciation paths, it may ignore this many-pronunciation word in favor of an incorrect word with only one pronunciation path. In essence, the Viterbi approximation penalizes words with many pronunciations.

A second problem with the Viterbi decoder is that it is impossible or expensive for it to take advantage of many useful knowledge sources. For example the Viterbi algorithm as we have defined it cannot take complete advantage of any language model more complex than a bigram grammar. This is because of the fact mentioned earlier that a trigram grammar, for example, violates the dynamic programming invariant. Recall that this invariant is the simplifying (but incorrect) assumption that if the ultimate best path for the entire observation sequence happens to go through a state $ q_i $, that this best path must include the best path up to and including state $ q_i $. Since a trigram grammar allows the probability of a word to be based on the two previous words, it is possible that the best trigram-probability path for the sentence may go through a word but not include the best path to that word. Such a situation could occur if a particular word $ w_x $ has a high trigram probability given $ w_y, w_z $, but that conversely the best path

to $ w_y $ didn't include $ w_z $ (i.e., $ P(w_y|w_q,w_z) $ was low for all $ q $). Advanced probabilistic LMs like SCFGs also violate the same dynamic programming assumptions.

There are two solutions to these problems with Viterbi decoding. The most common is to modify the Viterbi decoder to return multiple potential utterances, instead of just the single best, and then use other high-level language model or pronunciation-modeling algorithms to re-rank these multiple outputs (Schwartz and Austin, 1991; Soong and Huang, 1990; Murveit et al., 1993).

The second solution is to employ a completely different decoding algorithm, such as the stack decoder, or A* decoder (Jelinek, 1969; Jelinek et al., 1975). We begin in this section with multiple-pass decoding, and return to stack decoding in the next section.

In multiple-pass decoding we break up the decoding process into two stages. In the first stage we use fast, efficient knowledge sources or algorithms to perform a non-optimal search. So for example we might use an unsophisticated but time-and-space efficient language model like a bigram, or use simplified acoustic models. In the second decoding pass we can apply more sophisticated but slower decoding algorithms on a reduced search space. The interface between these passes is an N-best list or word lattice.

The simplest algorithm for multipass decoding is to modify the Viterbi algorithm to return the N-best sentences (word sequences) for a given speech input. Suppose for example a bigram grammar is used with such an N-best-Viterbi algorithm to return the 1000 most highly-probable sentences, each with their AM likelihood and LM prior score. This 1000-best list can now be passed to a more sophisticated language model like a trigram grammar. This new LM is used to replace the bigram LM score of each hypothesized sentence with a new trigram LM probability. These priors can be combined with the acoustic likelihood of each sentence to generate a new posterior probability for each sentence. Sentences are thus rescored and re-ranked using this more sophisticated probability. Fig. 10.1 shows an intuition for this algorithm.

There are a number of algorithms for augmenting the Viterbi algorithm to generate N-best hypotheses. It turns out that there is no polynomial-time admissible algorithm for finding the N most likely hypotheses (Young, 1984). There are however, a number of approximate (non-admissible) algorithms; we will introduce just one of them, the

“Exact N-best” algorithm of Schwartz and Chow (1990). In Exact N-best, instead of each state maintaining a single path/backtrace, we maintain up to N different paths for each state. But we’d like to ensure that these paths correspond to different word paths; we don’t want to waste our N paths on different state sequences that map to the same words. To do this, we keep for each path the word history, the entire sequence of words up to the current word/state. If two paths with the same word history come to a state at the same time, we merge the paths and sum the path probabilities. To keep the N best word sequences, the resulting algorithm requires $ O(N) $ times the normal Viterbi time. We’ll see this merging of paths again when we introducing decoding for statistical machine translation, where it is called hypothesis recombination.

The result of any of these algorithms is an N-best list like the one shown in Fig. 10.2. In Fig. 10.2 the correct hypothesis happens to be the first one, but of course the reason to use N-best lists is that isn't always the case. Each sentence in an N-best list is also annotated with an acoustic model probability and a language model probability. This allows a second-stage knowledge source to replace one of those two probabilities with an improved estimate.

One problem with an N-best list is that when N is large, listing all the sentences is extremely inefficient. Another problem is that N-best lists don't give quite as much information as we might want for a second-pass decoder. For example, we might want distinct acoustic model information for each word hypothesis so that we can reapply a new acoustic model for the word. Or we might want to have available different start and end times of each word so that we can apply a new duration model.

For this reason, the output of a first-pass decoder is usually a more sophisticated representation called a word lattice (Murveit et al., 1993; Aubert and Ney, 1995). A word lattice is a directed graph that efficiently represents much more information about possible word sequences. $ ^{1} $ In some systems, nodes in the graph are words and arcs are

transitions between words. In others, arcs represent word hypotheses and nodes are points in time. Let's use this latter model, and so each arc represents lots of information about the word hypothesis, including the start and end time, the acoustic model and language model probabilities, the sequence of phones (the pronunciation of the word), or even the phone durations. Fig. 10.3 shows a sample lattice corresponding to the N-best list in Fig. 10.2. Note that the lattice contains many distinct links (records) for the same word, each with a slightly different starting or ending time. Such lattices are not produced from N-best lists; instead, a lattice is produced during first-pass decoding by including some of the word hypotheses which were active (in the beam) at each timestep. Since the acoustic and language models are context-dependent, distinct links need to be created for each relevant context, resulting in a large number of links with the same word but different times and contexts. N-best lists like Fig. 10.2 can also be produced by first building a lattice like Fig. 10.3 and then tracing through the paths to produce N word strings.

The fact that each word hypothesis in a lattice is augmented separately with its acoustic model likelihood and language model probability allows us to rescue any path through the lattice, using either a more sophisticated language model or a more sophisticated acoustic model. As with N-best lists, the goal of this rescoring is to replace the 1-best utterance with a different utterance that perhaps had a lower score on the first decoding pass. For this second-pass knowledge source to get perfect word error rate, the actual correct sentence would have to be in the lattice or N-best list. If the correct sentence isn't there, the rescoring knowledge source can't find it. Thus it

is important when working with a lattice or N-best list to consider the baseline lattice error rate (Woodland et al., 1995; Ortmanns et al., 1997): the lower bound word error rate from the lattice. The lattice error rate is the word error rate we get if we chose the lattice path (the sentence) that has the lowest word error rate. Because it relies on perfect knowledge of which path to pick, we call this an oracle error rate, since we need some oracle to tell us which sentence/path to pick.

Another important lattice concept is the lattice density, which is the number of edges in a lattice divided by the number of words in the reference transcript. As we saw schematically in Fig. 10.3, real lattices are often extremely dense, with many copies of individual word hypotheses at slightly different start and end times. Because of this density, lattices are often pruned.

Besides pruning, lattices are often simplified into a different, more schematic kind of lattice that is sometimes called a word graph or finite state machine, although often it's still just referred to as a word lattice. In these word graphs, the timing information is removed and multiple overlapping copies of the same word are merged. The timing of the words is left implicit in the structure of the graph. In addition, the acoustic model likelihood information is removed, leaving only the language model probabilities. The resulting graph is a weighted FSA, which is a natural extension of an N-gram language model; the word graph corresponding to Fig. 10.3 is shown in Fig. 10.4. This word graph can in fact be used as the language model for another decoding pass. Since such a wordgraph language model vastly restricts the search space, it can make it possible to use a complicated acoustic model which is too slow to use in first-pass decoding.

A final type of lattice is used when we need to represent the posterior probability of individual words in a lattice. It turns out that in speech recognition, we almost never see the true posterior probability of anything, despite the fact that the goal of speech recognition is to compute the sentence with the maximum a posteriori probability. This is because in the fundamental equation of speech recognition we ignore the denominator in our maximization:

$$ \hat{W}=\underset{W\in\mathcal{L}}{\operatorname{a r g m a x}}\frac{P(O|W)P(W)}{P(O)}=\underset{W\in\mathcal{L}}{\operatorname{a r g m a x}}P(O|W)P(W) $$

The product of the likelihood and the prior is not the posterior probability of the

utterance. It is not even a probability, since it doesn't necessarily lie between 0 and 1. It's just a score. Why does it matter that we don't have a true probability? The reason is that without having true probability, we can choose the best hypothesis, but we can't know how good it is. Perhaps the best hypothesis is still really bad, and we need to ask the user to repeat themselves. If we had the posterior probability of a word it could be used as a confidence metric, since the posterior is an absolute rather than relative measure. A confidence metric is a metric that the speech recognizer can give to a higher-level process (like dialogue) to indicate how confident the recognizer is that the word string that it returns is a good one. We'll return to the use of confidence in Ch.24.

In order to compute the posterior probability of a word, we'll need to normalize over all the different word hypotheses available at a particular point in the utterances. At each point we'll need to know which words are competing or confusable. The lattices that show these sequences of word confusions are called confusion networks, meshes, sausages, or pinched lattices. A confusion network consists of a sequence of word positions. At each position is a set of mutually exclusive word hypotheses. The network represents the set of sentences that can be created by choosing one word from each position.

Note that unlike lattices or word graphs, the process of constructing a confusion network actually adds paths that were not in the original lattice. Confusion networks have other uses besides computing confidence. They were originally proposed for use in minimizing word error rate, by focusing on maximizing improving the word posterior probability rather than the sentence likelihood. Recently confusion networks have been used to train discriminative classifiers that distinguish between words.

Roughly speaking, confusion networks are built by taking the different hypothesis paths in the lattice and aligning them with each other. The posterior probability for each word is computing by first summing over all paths passing through a word, and then normalizing by the sum of the probabilities of all competing words. For further details see Mangu et al. (2000), Evermann and Woodland (2000), Kumar and Byrne (2002), Doumpiotis et al. (2003b).

Standard publicly available language modeling toolkits like SRI-LM (Stolcke, 2002) (http://www.speech.sri.com/projects/srilm/) and the HTK language

modeling toolkit (Young et al., 2005) (http://htk.eng.cam.ac.uk/) can be used to generate and manipulate lattices, N-best lists, and confusion networks.

FORWARD-BACKWARD

There are many other kinds of multiple-stage search, such as the forward-backward search algorithm (not to be confused with the forward-backward algorithm for HMM parameter setting) (Austin et al., 1991) which performs a simple forward search followed by a detailed backward (i.e., time-reversed) search.

10.2 A $ ^{*} $ ('STACK') DECODING

Recall that the Viterbi algorithm approximated the forward computation, computing the likelihood of the single best (MAX) path through the HMM, while the forward algorithm computes the likelihood of the total (SUM) of all the paths through the HMM. The $ A^{*} $ decoding algorithm allows us to use the complete forward probability, avoiding the Viterbi approximation. $ A^{*} $ decoding also allows us to use any arbitrary language model. Thus $ A^{*} $ is a one-pass alternative to multi-pass decoding.

The A* decoding algorithm is a best-first search of the tree that implicitly defines the sequence of allowable words in a language. Consider the tree in Fig. 10.6, rooted in the START node on the left. Each leaf of this tree defines one sentence of the language; the one formed by concatenating all the words along the path from START to the leaf. We don't represent this tree explicitly, but the stack decoding algorithm uses the tree implicitly as a way to structure the decoding search.

The algorithm performs a search from the root of the tree toward the leaves, looking for the highest probability path, and hence the highest probability sentence. As we proceed from root toward the leaves, each branch leaving a given word node represents a word which may follow the current word. Each of these branches has a probability, which expresses the conditional probability of this next word given the part of the sentence we've seen so far. In addition, we will use the forward algorithm to assign each word a likelihood of producing some part of the observed acoustic data. The A* decoder must thus find the path (word sequence) from the root to a leaf which

has the highest probability, where a path probability is defined as the product of its language model probability (prior) and its acoustic match to the data (likelihood). It does this by keeping a priority queue of partial paths (i.e., prefixes of sentences, each annotated with a score). In a priority queue each element has a score, and the pop operation returns the element with the highest score. The $ A^{*} $ decoding algorithm iteratively chooses the best prefix-so-far, computes all the possible next words for that prefix, and adds these extended sentences to the queue. Fig. 10.7 shows the complete algorithm.

function STACK-DECODING() returns min-distance

Initialize the priority queue with a null sentence.

Pop the best (highest score) sentence s off the queue.

If (s is marked end-of-sentence (EOS)) output s and terminate.

Get list of candidate next words by doing fast matches.

For each candidate next word w:

Create a new candidate sentence $ s + w $.

Use forward algorithm to compute acoustic likelihood $ L $ of $ s + w $

Compute language model probability P of extended sentence $ s + w $

Compute “score” for $ s + w $ (a function of L, P, and ???)

if (end-of-sentence) set EOS flag for $ s + w $.

Insert $ s + w $ into the queue together with its score and EOS flag

Figure 10.7 The A* decoding algorithm (modified from Paul (1991) and Jelinek (1997)). The evaluation function that is used to compute the score for a sentence is not completely defined here possible evaluation functions are discussed below.

Let's consider a stylized example of an A* decoder working on a waveform for which the correct transcription is if music be the food of love. Fig. 10.8 shows the search space after the decoder has examined paths of length one from the root. A fast match is used to select the likely next words. A fast match is one of a class of heuristics designed to efficiently winnow down the number of possible following words, often by computing some approximation to the forward probability (see below for further discussion of fast matching).

At this point in our example, we've done the fast match, selected a subset of the possible next words, and assigned each of them a score. The word Alice has the highest score. We haven't yet said exactly how the scoring works.

Fig. 10.9a shows the next stage in the search. We have expanded the Alice node. This means that the Alice node is no longer on the queue, but its children are. Note that now the node labeled if actually has a higher score than any of the children of Alice. Fig. 10.9b shows the state of the search after expanding the if node, removing it, and adding if music, if muscle, and if messy on to the queue.

We clearly want the scoring criterion for a hypothesis to be related to its probability. Indeed it might seem that the score for a string of words $ w_1^i $ given an acoustic string $ y_1^j $ should be the product of the prior and the likelihood:

$$ P(y_{1}^{j}|w_{1}^{i})P(w_{1}^{i}) $$

Alas, the score cannot be this probability because the probability will be much smaller for a longer path than a shorter one. This is due to a simple fact about probabilities and substrings; any prefix of a string must have a higher probability than the string itself (e.g., P(START the ...) will be greater than P(START the book)). Thus if we used probability as the score, the A* decoding algorithm would get stuck on the

single-word hypotheses.

Instead, we use the $ A^{*} $ evaluation function (Nilsson, 1980; Pearl, 1984) $ f^{*}(p) $ given a partial path p:

$$ f^{*}(p)=g(p)+h^{*}(p) $$

$ f^{*}(p) $ is the estimated score of the best complete path (complete sentence) which starts with the partial path p. In other words, it is an estimate of how well this path would do if we let it continue through the sentence. The $ A^{*} $ algorithm builds this estimate from two components:

• $ g(p) $ is the score from the beginning of utterance to the end of the partial path p. This g function can be nicely estimated by the probability of p given the acoustics so far (i.e., as $ P(O|W)P(W) $ for the word string W constituting p).

• $ h^{*}(p) $ is an estimate of the best scoring extension of the partial path to the end of the utterance.

Coming up with a good estimate of $ h^{*} $ is an unsolved and interesting problem. A very simple approach is to chose an $ h^{*} $ estimate which correlates with the number of words remaining in the sentence (Paul, 1991). Slightly smarter is to estimate the expected likelihood per frame for the remaining frames, and multiple this by the estimate of the remaining time. This expected likelihood can be computed by averaging the likelihood per frame in the training set. See Jelinek (1997) for further discussion.

Tree Structured Lexicons

We mentioned above that both the A $ ^{*} $ and various other two-stage decoding algorithms require the use of a fast match for quickly finding which words in the lexicon are likely candidates for matching some portion of the acoustic input. Many fast match algorithms are based on the use of a tree-structured lexicon, which stores the pronunciations of all the words in such a way that the computation of the forward probability can be shared for words which start with the same sequence of phones. The tree-structured lexicon was first suggested by Klovstad and Mondshein (1975); fast match algorithms which make use of it include Gupta et al. (1988), Bahl et al. (1992) in the context of A $ ^{*} $ decoding, and Ney et al. (1992) and Nguyen and Schwartz (1999) in the context of Viterbi decoding. Fig. 10.10 shows an example of a tree-structured lexicon from the Sphinx-II recognizer (Ravishankar, 1996). Each tree root represents the first phone of all words beginning with that context dependent phone (phone context may or may not be preserved across word boundaries), and each leaf is associated with a word.

10.3 CONTEXT-DEPENDENT ACOUSTIC MODELS: TRIPHONES

In our discussion in Sec. ?? of how the HMM architecture is applied to ASR, we showed how an HMM could be created for each phone, with its three emitting states corresponding to subphones at the beginning, middle, and end of the phone. We thus

represent each subphone ("beginning of [eh]", "beginning of [t]", "middle of [ae]") with its own GMM.

There is a problem with using a fixed GMM for a subphone like "beginning of [eh]". The problem is that phones vary enormously based on the phones on either side. This is because the movement of the articulators (tongue, lips, velum) during speech production is continuous and is subject to physical constraints like momentum. Thus an articulator may start moving during one phone to get into place in time for the next phone. In Ch. 7 we defined the word coarticulation as the movement of articulators to anticipate the next sound, or perseverating movement from the last sound. Fig. 10.11 shows coarticulation due to neighboring phone contexts for the vowel [eh].

In order to model the marked variation that a phone exhibits in different contexts, most LVCSR systems replace the idea of a context-independent (CI phone) HMM with a context-dependent or CD phones. The most common kind of context-dependent model is a triphone HMM (Schwartz et al., 1985; Deng et al., 1990). A triphone model represents a phone in a particular left and right context. For example the triphone [y-eh+l] means "[eh] preceded by [y] and followed by [l]". In general, [a-b+c] will mean "[b] preceded by [a] and followed by [c]". In situations where we don't have a full triphone context, we'll use [a-b] to mean "[b] preceded by [a]" and [b+c] to mean "[b] followed by [c]".

Context-dependent phones capture an important source of variation, and are a key part of modern ASR systems. But unbridled context-dependency also introduces the same problem we saw in language modeling: training data sparsity. The more complex the model we try to train, the less likely we are to have seen enough observations of each phone-type to train on. For a phoneset with 50 phones, in principle we would need $ 50^{3} $ or 125,000 triphones. In practice not every sequence of three phones is possible (English doesn't seem to allow triphone sequences like [ae-eh+ow] or [m-j+t]). Young et al. (1994) found that 55,000 triphones are needed in the 20K Wall Street Journal task. But they found that only 18,500 of these triphones, i.e. less than half, actually

occurred in the SI84 section of the WSJ training data.

Because of the problem of data sparsity, we must reduce the number of triphone parameters that we need to train. The most common way to do this is by clustering some of the contexts together and tying subphones whose contexts fall into the same cluster (Young and Woodland, 1994). For example, the beginning of a phone with an [n] on its left may look much like the beginning of a phone with an [m] on its left. We can therefore tie together the first (beginning) subphone of, say, the [m-eh+d] and [n-eh+d] triphones. Tying two states together means that they share the same Gaussians. So we only train a single Gaussian model for the first subphone of the [m-eh+d] and [n-eh+d] triphones. Likewise, it turns out that the left context phones [r] and [w] produce a similar effect on the initial subphone of following phones.

Fig. 10.12 shows, for example the vowel [iy] preceded by the consonants [w], [r], [m], and [n]. Notice that the beginning of [iy] has a similar rise in F2 after [w] and [r]. And notice the similarity of the beginning of [m] and [n]; as Ch. 7 noted, the position of nasal formants varies strongly across speakers, but this speaker (the first author) has a nasal formant (N2) around 1000 Hz.

Fig. 10.13 shows an example of the kind of triphone tying learned by the clustering algorithm. Each mixture Gaussian model is shared by the subphone states of various triphone HMMs.

How do we decide what contexts to cluster together? The most common method is to use a decision tree. For each state (subphone) of each phone, a separate tree is built. Fig. 10.14 shows a sample tree from the first (beginning) state of the phone /ih/, modified from Odell (1995). We begin at the root node of the tree with a single large cluster containing (the beginning state of) all triphones centered on /ih/. At each node in the tree, we split the current cluster into two smaller clusters by asking questions.

about the context. For example the tree in Fig. 10.14 first splits the initial cluster into two clusters, one with nasal phone on the left, and one without. As we descend the tree from the root, each of these clusters is progressively split. The tree in Fig. 10.14 would split all beginning-state /ih/ triphones into 5 clusters, labeled A-E in the figure.

The questions used in the decision tree ask whether the phone to the left or right has a certain phonetic feature, of the type introduced in Ch. 7. Fig. 10.15 shows a few decision tree questions; note that there are separate questions for vowels and consonants. Real trees would have many more questions.

How are decision trees like the one in Fig. 10.14 trained? The trees are grown top down from the root. At each iteration, the algorithm considers each possible question q and each node n in the tree. For each such question, it considers how the new split would impact the acoustic likelihood of the training data. The algorithm computes the difference between the current acoustic likelihood of the training data, and the new likelihood if the models were tied based on splitting via question q. The algorithm picks the node n and question q which gives the maximum likelihood. The procedure then iterates, stopping when each leaf node has some minimum threshold number of examples.

We also need to modify the embedded training algorithm we saw in Sec. ?? to deal with context-dependent phones and also to handle mixture Gaussians. In both cases we

use a more complex process that involves cloning and using extra iterations of EM, as described in Young et al. (1994).

To train context-dependent models, for example, we first use the standard embedded training procedure to train context-independent models, using multiple passes of EM and resulting in separate single-Gaussians models for each subphone of each monophone /aa/, /ae/, etc. We then clone each monophone model, i.e. make identical

copies of the model with its 3 substates of Gaussians, one clone for each potential triphone. The A transition matrices are not cloned, but tied together for all the triphone clones of a monophone. We then run an iteration of EM again and retrain the triphone Gaussians. Now for each monophone we cluster all the context-dependent triphones using the clustering algorithm described on page 15 to get a set of tied state clusters. One tvnical state is chosen as the exemplar for this cluster and the rest are tied to it.

We use this same cloning procedure to learn Gaussian mixtures. We first use embedded training with multiple iterations of EM to learn single-mixture Gaussian models for each tied triphone state as described above. We then clone (split) each state into 2 identical Gaussians, perturb the values of each by some epsilon, and run EM again to retrain these values. We then split each of the two mixtures, resulting in four, perturb them, retrain. We continue until we have an appropriate number of mixtures for the amount of observations in each state.

A full context-depending GMM triphone model is thus created by applying these two cloning-and-retraining procedures in series, as shown schematically in Fig. 10.16.

10.4 DISCRIMINATIVE TRAINING

The Baum-Welch and embedded training models we have presented for training the HMM parameters (the A and B matrices) are based on maximizing the likelihood of the training data. An alternative to this maximum likelihood estimation (MLE) is to focus not on fitting the best model to the data, but rather on discriminating the best model from all the other models. Such training procedures include Maximum Mutual Information Estimation (MMIE) (Woodland and Povey, 2002) the use of neural net/SVM classifiers (Bourlard and Morgan, 1994) as well as other techniques like Minimum Classification Error training (Chou et al., 1993; McDermott and Hazen, 2004) or Minimum Bayes Risk estimation (Doumpiotis et al., 2003a). We summarize the first two of these in the next two subsections.