Abstract:
The discriminative clustering technique tests a provided set of Gaussian distributions corresponding to an acoustic vector space. A distance metric, such as the Bhattacharyya distance, is used to assess which distributions are sufficiently proximal to be merged into a new distribution. Merging is accomplished by computing the centroid of the new distribution by minimizing the Bhattacharyya distance between the parameters of the Gaussian distributions being merged.

Description:
BACKGROUND AND SUMMARY OF THE INVENTION 
     The present invention relates generally to statistical model-based speech recognition systems. More particularly, the invention relates to a system and method for improving the accuracy of acoustic models used by the recognition system while at the same time controlling the number of parameters. The discriminative clustering technique allows robust recognizers of small size to be constructed for resource-limited applications such as in embedded systems and consumer products. 
     Much of the automatic speech recognition technology today relies upon Hidden Markov Model (HMM) representation of features extracted from digitally recorded speech. A Hidden Markov Model is represented by a set of states, a set of vectors defining transitions between certain pairs of states, probabilities that apply to state-to-state transitions and further sets of probabilities characterizing observed output symbols and initial conditions. Frequently the probabilities associated with the Hidden Markov Model are represented as Gaussians expressed by representing the mean and variance as floating point numbers. 
     Hidden Markov Models can become quite complex, particularly as the number of states representing each speech unit is increased and as more complex Gaussian mixture density components are used. Complexity is further compounded by the need to have additional sets of models to support context-dependent recognition. For example, to support context-dependent recognition in a recognizer that models phonemes, different sets of Gaussians are typically required to represent the different allophones of each phoneme. 
     The above complexity carries a price. Recognizers with more sophisticated, and hence more robust, models typically require a large amount of memory and processing power. This places a heavy burden on embedded systems and speech-enabled consumer products, because these typically do not have much memory or processing power to spare. What is needed, therefore, is a technique for reducing the number of Gaussians needed to represent speech, while retaining as much accuracy as possible. For the design of memory-restricted embedded systems and computer products, the most useful solution would give the system designer control over the total number of parameters used. 
     The present invention provides a technique for improving modeling power while reducing the number of parameters. In its preferred embodiment, the technique takes a bottom-up approach for defining clusters of Gaussians that are sufficiently close to one another to warrant being merged. In its preferred form, the technique begins with as many clusters as Gaussians used to represent the states of the Hidden Markov Models. Clusters are then agglomerated, in tree fashion, to minimize the dispersion inside the cluster and to maximize the separation between clusters. The agglomerative process proceeds until the desired number of clusters is reached. The system designer may specify the desired number based on memory footprint and processing architecture. A Lloyd-Max clustering algorithm is then performed to move Gaussians from one cluster to another in order to further decrease the dispersion within clusters. 
     Unlike conventional systems that tend to merely average Gaussian mean and variance values together, the method of the present invention employs a powerful set of equations that provides the parameters representative of each cluster (e.g. centroid), so that the Bhattacharyya distance is minimized inside the cluster. This provides a far better way of estimating the parameters representative of the cluster, because it is consistent with the metric used to associate the Gaussians to the cluster itself. In the preferred implementation, the Bhattacharyya distance is minimized through an iterative procedure that we call the minimum mean Bhattacharyya center algorithm. 
     For a more complete understanding of the invention, its objects and advantages, refer to the following specification and to the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 is a block diagram presenting an overview of the bottomup clustering method of the preferred embodiment; 
     FIG. 2 is a flowchart illustrating the presently preferred agglomerative clustering technique in greater detail; 
     FIG. 3 is a block diagram giving an overview of how the Bhattacharyya distance is used in both the clustering step and the center step; 
     FIG. 4 is a flowchart illustrating the presently preferred iterative technique for performing the center step. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The presently preferred embodiment of the discriminative clustering technique is designed to work with an initial set of Gaussian distributions shown at  10  in FIG.  1 . By operation of the discriminative clustering method, this initial set is compressed as illustrated at  30 . In essence, the method minimizes redundancy in the speech models while preserving as much relevant information as possible. As noted above, typically the Hidden Markov Model is used to represent sound units in the language, such as words, subwords, phonemes or the like, by quantizing sequences of acoustic vectors. This acoustic vector space is commonly represented using Gaussian distributions. Thus, conceptually, the sound units of a language may be represented by a dictionary of Gaussian distributions. The invention is designed to compress this Gaussian dictionary while preserving the information needed to properly model the different acoustic vectors needed to perform accurate speech recognition. The presently preferred embodiment employs an agglomerative clustering algorithm  20  to form the compressed set of gaussians  30 . A Lloyd-Max process  40  may then be performed on the compressed set of gaussians, if desired. 
     FIG. 2 shows the agglomerative clustering algorithm. An objective of the algorithm is to merge distributions which return similar likelihoods and hence do not help much in the recognition process. The basic principle of agglomerative clustering is to start from an initial set of vectors which are treated as leaves of a tree structure. The procedure than proceeds to merge vectors with the objective of increasing overall distortion as little as possible. The procedure is repeated iteratively until the desired number of clusters remains. Overall distortion is assessed by a distance measurement. The presently preferred embodiment uses a Bhaftacharyya distance measurement. Thus the overall distortion may be represented as follows: 
     
       
           d   overall =Σ i=1   N Σ j−1   M     i     d ( x   i   , td   ij ) 
       
     
     where td ij  is the jth sample of data associated with the cluster x i . 
       1 (gaussian distribution) 
     Referring to FIG. 2, the clustering algorithm begins with an initial set of Gaussians  50 . Then, for each couple of vectors x n , x m , the procedure considers at step  58  a new dictionary by temporarily merging the vector couple x n  and x m . Then, at step  60 , a new overall distortion is computed. The new overall distortion is then tested at  62  and the merging of vectors x n  and x m  is committed if doing so will result in the lowest overall distortion. The results may be organized as a tree structure  63 . The procedure is then repeated as at  64  for the remainder of the resulting dictionary. 
     The algorithm of FIG. 2 can be made less complex by computing the increase in distortion rather than the overall distortion at step  60 . This is done by comparing the distortion due to a couple of vectors with the distortion resulting when they are merged. This increase in distortion may be calculated as set forth in the equation below. 
      Δ d=Σ   j=1   M     n     d ( x′, td   nj )− d ( x   n   , td   nj )+Σ j=1   Mm   d ( x′, td   mj )− d ( x   m   , td   mj ) 
     After computing the increase in distortion the proposed merging of two vectors is committed if it results in the lowest distortion increase. 
     One advantage of the agglomerative clustering procedure is that it does a good job of identifying small and concentrated populations. However, if allowed to proceed unchecked, it can grow clusters that become too large and hence no longer are able to discriminate effectively between different sound units. 
     To avoid oversized clusters, the distance measure can be weighted with the number of gaussians belonging to a cluster to penalize overused clusters. Cluster with a smaller number of belonging gaussians will show a smaller distortion. 
     The preferred embodiment uses the Bhattacharyya distance as a metric for both cluster formation and subsequent computation of the new cluster&#39;s centroid. FIG. 3 illustrates this. In FIG. 3 the cluster formation step  70  uses the Bhattacharyya distance to find the gaussians that are close enough together to warrant being merged, as indicated at step  72 . 
     The preferred technique is based on a computation of the Bhattacharyya distance  14 , which may be computed for two Gaussian distributions g 1  and g 2  as follows:            D   bhat          (       g   1     ,     g   2       )       =         1   8     *       (       μ   2     -     μ   1       )     T     *       [         ∑   1          +     ∑   2         2     ]       -   1       *     (       μ   2     -     μ   1       )       +       1   2        ln                   ∑   1          +     ∑   2              2                  ∑   1          *          ∑   2                                                        
     where μ 1  and μ 2  are the mean vectors associated with distributions g 1  and g 2  and Σ 1  and Σ 2  are the respective covariance matrices. 
     After determining which Gaussian distributions to merge, the procedure next computes the centroid resulting from the merging of two or more Gaussian distributions as indicated at step  74 . The center step  74  involves finding the centroid that minimizes the Bhattacharyya distance between the center and the vectors (gaussians) in the cluster, as indicated at  76 . 
     FIG. 3 illustrates a representative cluster at  75  having a centroid  76  and containing a plurality of gaussian distributions  77 - 80 . The Bhattacharyya distances between the centroid  76  and the respective distributions. The center step  74 , in effect, minimizes the sum of the Bhattacharyya distances (shown in dotted lines). 
     The Bhattacharyya centroid is computed iteratively, after first being initialized as the maximum likelihood centroid. The maximum likelihood centroid corresponds to maximum likelihood estimation on the training data associated with the distributions in the cluster. For Cluster which contains the Gaussian distribution&#39;s g i  with a weight of w i , i=1, . . . , N, the Bhattacharyya centroid (mean and standard deviation) may be computed as shown in Equations 1 and 2 below. 
     For diagonal covariance matrices our procedure can be based on the following equations, where σ 2  is the variance and μ is the mean associated with a specific component of the feature vector.                μ   c     =         ∑   i            w   i     *       (       σ   c   2     +     σ   i   2       )       -   1       *     μ   i             ∑   i            w   i     *       (       σ   c   2     +     σ   i   2       )       -   1                     Equation  1                 σ   c   2     =         ∑   i          w   i           ∑   i            w   i     *     [       2       σ   c   2     +     σ   i   2         -       (         μ   c     -     μ   i           σ   c   2     +     σ   i   2         )     2       ]                   Equation  2                                
     Use of the above Equations 1 and 2 results in a significant improvement over conventional clustering techniques. Unlike conventional techniques that merely seek average value of the means of Gaussians belonging to a cluster, the above equations actually provide the parameters of the cluster so that the Bhattacharyya distance is minimized inside the cluster. Note that the parameters representative of the cluster are consistent with the metric used to associate the Gaussians to the cluster itself. Equations 1 and 2 comprise a coherent set of equations that represent a uniform criteria for computing the cluster centers. These equations may be solved iteratively as will now be described. 
     The above equations 1 and 2 are computed iteratively using the algorithm illustrated in FIG.  4 . Beginning at step  100 , the algorithm initializes the centers of each centroid using a maximum likelihood calculation. The means and variances are then fed to respective re-estimation calculation blocks  101  and  102 . The re-estimation calculation block  101  implements above equation 1 and calculation block  102  implements above equation 2. 
     Note that the output of calculation block  101  represents a re-estimated mean, which is fed back as an input to calculation block  102 . The output of block  102  represents a re-estimated variance. The output of block  102  is fed into block  101  as an input, as illustrated. Thus each calculation block  101  and  102  provides its output as an input to the other block. The calculations performed at blocks  101  and  102  are designed to operate iteratively until a stop condition is met. The stop condition can be either: (1) a predetermined number of iterations or (2) upon achieving a convergence in the distortion. After iteration has ceased, the final means and variance values are output as at  104  to be used as the new centroids for the cluster, now optimized with respect to the Bhattacharyya distance. 
     From the foregoing, it will be understood that the presently preferred discriminative clustering technique exploits the Bhattacharyya distance to find the gaussians that are close enough to warrant being assigned to the same cluster. The technique further exploits the Bhattacharyya distance in recomputing a new centroid for the cluster in terms of optimized mean and variance values based on equations 1 and 2 recited above. These equations are efficiently solved through an iterative technique in which the re-estimation of the mean is used in calculating the re-estimation of the variance, and vice versa. 
     While the invention has been described in its presently preferred form, it will be understood that the invention is capable of modification without departing from the spirit of the invention as set forth in the appended claims.