9.4.1 Vector Quantization

One way to make MFCC vectors look like symbols that we could count is to build a mapping function that maps each input vector into one of a small number of symbols. Then we could just compute probabilities on these symbols by counting, just as we did for words in part-of-speech tagging. This idea of mapping input vectors to discrete quantized symbols is called vector quantization or VQ (Gray, 1984). Although vector quantization is too simple to act as the acoustic model in modern LVCSR systems, it is a useful pedagogical step, and plays an important role in various areas of ASR, so we use it to begin our discussion of acoustic modeling.

In vector quantization, we create the small symbol set by mapping each training feature vector into a small number of classes, and then we represent each class by a discrete symbol. More formally, a vector quantization system is characterized by a codebook, a clustering algorithm, and a distance metric.

A codebook is a list of possible classes, a set of symbols constituting a vocabulary $V = \{\nu_1, \nu_2, ..., \nu_n\}$. For each symbol $\nu_k$ in the codebook we list a prototype vector, also known as a codeword, which is a specific feature vector. For example if we choose to use 256 codewords we could represent each vector by a value from 0 to 255; (this is referred to as 8-bit VQ, since we can represent each vector by a single 8-bit value). Each of these 256 values would be associated with a prototype feature vector.

The codebook is created by using a clustering algorithm to cluster all the feature vectors in the training set into the 256 classes. Then we chose a representative feature vector from the cluster, and make it the prototype vector or codeword for that cluster.

K-means clustering is often used, but we won't define clustering here; see Huang et al. (2001) or Duda et al. (2000) for detailed descriptions.

Once we’ve built the codebook, for each incoming feature vector, we compare it to each of the 256 prototype vectors, select the one which is closest (by some distance metric), and replace the input vector by the index of this prototype vector. A schematic of this process is shown in Fig. 9.15.

The advantage of VQ is that since there are a finite number of classes, for each class $ v_k $, we can compute the probability that it is generated by a given HMM state/sub-phone by simply counting the number of times it occurs in some training set when labeled by that state, and normalizing.

Both the clustering process and the decoding process require a distance metric or distortion metric, that specifies how similar two acoustic feature vectors are. The distance metric is used to build clusters, to find a prototype vector for each cluster, and to compare incoming vectors to the prototypes.

The simplest distance metric for acoustic feature vectors is Euclidean distance. Euclidean distance is the distance in N-dimensional space between the two points defined by the two vectors. In practice we use the phrase ‘Euclidean distance’ even though we actually often use the square of the Euclidean distance. Thus given a vector x and a vector y of length D, the (square of the) Euclidean distance between them is defined as:

$$ d_{euclidean}(x,y)=\sum_{i=1}^{D}(x_{i}-y_{i})^{2} $$

The (squared) Euclidean distance described in (9.18) (and shown for two dimensions in Fig. 9.16) is also referred to as the sum-squared error, and can also be expressed using the vector transpose operator as:

$$ d_{e u c l i d e a n}(x,y)=(x-y)^{T}(x-y) $$

The Euclidean distance metric assumes that each of the dimensions of a feature vector are equally important. But actually each of the dimensions has very different variances. If a dimension tends to have a lot of variance, then we'd like it to count less in the distance metric; a large difference in a dimension with low variance should count more than a large difference in a dimension with high variance. A slightly more complex distance metric, the Mahalanobis distance, takes into account the different variances of each of the dimensions.

If we assume that each dimension i of the acoustic feature vectors has a variance $ \sigma_{i}^{2} $, then the Mahalanobis distance is:

$$ d_{mahalanobis}(x,y)=\sum_{i=1}^{D}\frac{(x_{i}-y_{i})^{2}}{\sigma_{i}^{2}} $$

For those readers with more background in linear algebra here's the general form of Mahalanobis distance, which includes a full covariance matrix (covariance matrices will be defined below):

$$ d_{\mathrm{m a h a l a n o b i s}}(x,y)=(x-y)^{T}\Sigma^{-1}(x-y) $$

In summary, when decoding a speech signal, to compute an acoustic likelihood of a feature vector $ o_{t} $ given an HMM state $ q_{j} $ using VQ, we compute the Euclidean or Mahalanobis distance between the feature vector and each of the N codewords, choose the closest codeword, getting the codeword index $ \nu_{k} $. We then look up the likelihood of the codeword index $ \nu_{k} $ given the HMM state j in the pre-computed B likelihood matrix defined by the HMM:

$ \hat{b}_j(o_t) = b_j(v_k) $ s.t. $ v_k $ is codeword of closest vector to $ o_t $

Since VQ is so rarely used, we don't use up space here giving the equations for modifying the EM algorithm to deal with VQ data; instead, we defer discussion of EM training of continuous input parameters to the next section, when we introduce Gaussians.