Abstract:
A system and method for applying a linear transformation to classify and input event. In one aspect, a method for classification comprises the steps of capturing an input event; extracting an n-dimensional feature vector from the input event; applying a linear transformation to the feature vector to generate a pool of projections; utilizing different subsets from the pool of projections to classify the feature vector; and outputting a class identity of the classified feature vector. In another aspect, the step of utilizing different subsets from the pool of projections to classify the feature vector comprises the steps of, for each predefined class, selecting a subset from the pool of projections associated with the class; computing a score for the class based on the associated subset; and assigning, to the feature vector, the class having the highest computed score.

Description:
BACKGROUND 
     1. Technical Field 
     This application relates generally to speech and pattern recognition and, more specifically, to multi-category (or class) classification of an observed multi-dimensional predictor feature, for use in pattern recognition systems. 
     2. Description of Related Art 
     In one conventional method for pattern classification and classifier design, each class is modeled as a gaussian, or a mixture of gaussian, and the associated parameters are estimated from training data. As is understood, each class may represent different data depending on the application. For instance, with speech recognition, the classes may represent different phonemes or triphones. Further, with handwriting recognition, each class may represent a different handwriting stroke. Due to computational issues, the gaussian models are assumed to have a diagonal co-variance matrix. When classification is desired, a new observation is applied to the models within each category, and the category, whose model generates the largest likelihood is selected. 
     In another conventional design, the performance of a classifier that is designed using gaussian models is enhanced by applying a linear transformation of the input data, and possibly, by simultaneously reducing the feature dimension. More specifically, conventional methods such as Principal Component Analysis, and Linear Discriminant Analysis may be employed to obtain the linear transformation of the input data. Recent improvements to the linear transform techniques include Heteroscedastic Discriminant Analysis and Maximum Likelihood Linear Transforms (see, e.g., Kumar, et al., “Heteroscedastic Discriminant Analysis and Reduced Rank HMMs For Improved Speech Recognition,”  Speech Communication , 26:283-297, 1998). 
     More specifically, FIG. 1 a  depicts one method for applying a linear transform to an observed event x. With this method, a precomputed n×n linear transformation, θ T , is multiplied by an observed event x (an n×1 feature vector), to yield and n×1 dimensional vector, y. The vector y is modeled as a gaussian vector with a mean u j  and variances Σ j  for each different class. The same y is used and a different mean and variance is assigned for each different class to model that same y. The variances for each class are assumed to be diagonal covariance matrices. 
     In another conventional method depicted in FIG. 1 b , instead of a single linear transformation θ T  (as in FIG. 1 a ), a plurality of linear transformation matrices θ 1   T , θ 2   T  are implemented, as long as the value of the determinant is constrained to be “1” (unity). Then one transformation is applied for one set of classes, and other to another set of classes. With this method, each class may have its own linear transformation θ, or two or more classes may share the same linear transformation θ. 
     SUMMARY OF THE INVENTION 
     The present invention is directed to a system and method for applying a linear transformation to classify and input event. In one aspect, a method for classification comprises the steps of: 
     capturing an input event; 
     extracting an n-dimensional feature vector from the input event; 
     applying a linear transformation to the feature vector to generate a pool of projections; 
     utilizing different subsets from the pool of projections to classify the feature vector; and 
     outputting a class identity associated with the feature vector. 
     In another aspect, the step of utilizing different subsets from the pool of projections to classify the feature vector comprises the steps of: 
     for each predefined class, selecting a subset from the pool of projections associated with the class; 
     computing a score for the class based on the associated subset; and 
     assigning, to the feature vector, the class having the highest computed score. 
     In yet another aspect, each of the associated subsets comprise a unique predefined set of n indices computed during training, which are used to select the associated components from the computed pool of projections. 
     In another aspect, a preferred classification method is implemented in Gaussian and/or maximum-likelihood framework. 
     The novel concept of applying projections is different from the conventional method of applying different transformations because the sharing is at the level of the projections. Therefore, in principle, each class (or large number of classes) may use different “linear transforms”, although the difference between such transformations may arise from selecting a different combination of linear projections from a relatively small pool of projections. This concept of applying projections can advantageously be applied in the presence of any underlying classifier. 
     These and other aspects, features and advantage of the present invention will be described and become apparent from the following detailed description of preferred embodiments, which is to be read in connection with the accompanying drawings. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIGS. 1 a  and  b  illustrate conventional methods for applying linear transforms in a classification process; 
     FIG. 2 illustrates a method for applying linear transform in a classification process according to one aspect of the present invention; 
     FIG. 3 comprise a block diagram of a classification system according to one embodiment of the present invention; 
     FIG. 4 comprises a flow diagram of a classification method according to one aspect of the present invention; 
     FIG. 5 comprises a flow diagram of a method for estimating parameters that are used for a classification process according to one aspect of the present invention; and 
     FIG. 6 comprises a flow diagram of a method for computing a optimizing a linear transformation according to one aspect of the present invention. 
    
    
     DESCRIPTION OF PREFERRED EMBODIMENTS 
     In general, the present invention is an extension of conventional techniques that implement a linear transformation, to provide a system and method for enhancing, e.g., speech and pattern recognition. It has been determined that it is not necessary to apply the same linear transformation to the predictor feature x (such as described above with reference to FIG. 1 a ). Instead, as depicted in FIG. 2, it is possible to compute a linear transform of K×n dimensions, where K&gt;n, which is multiplied by a feature x (of n×1 dimensions) to create a pool of projections (e.g., a y vector of dimension K×1) wherein the pool is preferably larger in size than the feature dimension. 
     Then for each class, a n subset of K transformed features in the pool y is used to compute the likelihood of the class. For instance, the first n values in y would be chosen for class  1 , and a different subset of n values in y would be used for class  2  and so on. The n values for each of the class are predetermined at training. The nature of the training data and how accurately you want the training data to be modeled determines the size of y. In addition, the size of y may also depend on the amount of computational resources available at the time of training and recognition. This concept is different from the conventional method of using different linear transformations as described above, because the sharing is at the level of projections (in the pool y). Therefore, in principle, each class, or a large number of classes may use different “linear transformations”, although the difference between those transformations may arise only from choosing a different combination of linear projections from the relatively small pool of projections y. 
     The unique concept of applying projections can be applied in the presence of any underlying classifier. However, since it is popular to use Gaussian or Mixture of Gaussian, a preferred embodiment described below relates to methods to determine (1) the optimal directions, and (2) projection subsets for each class, under a Gaussian model assumption. In addition, although several paradigms of parameter estimation exist, such as maximum-likelihood, minimum-classification-error, maximum-entropy, etc., a preferred embodiment described below presents equations only for maximum-likelihood framework, since that is most popular. 
     The systems and methods described herein may be implemented in various forms of hardware, software, firmware, special purpose processors, or a combination thereof. The present invention is preferably implemented as an application comprising program instructions that are tangibly embodied on a program storage device (e.g., magnetic floppy disk, RAM, ROM, CD ROM and/or Flash memory) and executable by any device or machine comprising suitable architecture. Because some of the system components and process steps depicted in the accompanying Figures are preferably implemented in software, the actual connections in the Figures may differ depending upon the manner in which the present invention is programmed. Given the teachings herein, one of ordinary skill in the related art will be able to contemplate these and similar implementations or configurations of the present invention. 
     Referring now to FIG. 3, a block diagram illustrates a classification system  30  according to an exemplary embodiment of the present invention. The system  30  comprises an input device  31  (e.g., a microphone, an electronic notepad) for collecting input signals (e.g., speech or handwriting data) and converting the input data into electronic/digitized form. A feature extraction module  32  extracts feature vectors from the electronic data using any known technique that is suitable for the desired application. A training module  33  is provided to store and process training data that is input to the system  30 . The training module  33  utilizes techniques known in the art for generating suitable prototypes (either independent, dependent or both) that are used during a recognition process. The prototypes are stored in a prototype database  34 . The training module  33  further generates precomputed parameters, which are stored in database  35 , using methods according the present invention. Preferred embodiments of the precomputed parameters and corresponding methods are described in detail below. The system  30  further comprises a recognition system  36  (also known as a Viterbi Decoder, Classifier, etc.) which utilizes the prototypes  34  and precomputed parameters  35  during a real-time recognition process, for example, to identify/classify input data, which is either stored in system memory or output to a user via the output device  37  (e.g., a computer monitor, text-to-speech, etc.) A recognition/classification technique according to one aspect of the present invention (which may be implemented in the system  30 ) will now be described in detail with reference to FIG.  4 . 
     FIG. 4 is a flow diagram that illustrates a method for classifying an observed event according to one aspect of the invention. The following method is preferably implemented in the system of FIG.  3 . During run-time of the system (step  100 ), an event is received (e.g., uttered sound, handwritten character, etc.) and converted to an n-dimensional real-valued predictor feature x (step  101 ). Then, x is multiplied by a transposed n×k linear transformation matrix 
     
       
         θ T:y=θ   T χ  Equ. 1 
       
     
     to compute a pool of projections y, where θ is a linear transform that is precomputed during training (as explained below), y comprises a k dimensional vector, and k is an integer that is larger than or equal to n (step  102 ). 
     Next, a predefined class j is selected and the n indices defined by the corresponding subset Sj are retrieved (step  103 ). More specifically, during training, a plurality of classes j (j=1 . . . J) are defined. In addition, for each class j, there is a pre-defined subset S j  containing n different indices from the range 1 . . . k. In other words, each of the predefined subsets Sj comprise a unique set of n indices (from a y vector computed during training using the training data) corresponding to a particular class j. For instance, the first n values in y (computed during training) would be chosen for class  1 , and a different subset of n values in y would be used for class  2  and so on. 
     Then, the n indices of the current Sj, are used to select the associated values from the current y vector (computed in step  102 ) to generate a y j  vector (step  104 ). The term y j  is defined herein as the n dimensional vector that is generated by selecting the subset S j  from y (i.e., by selecting n values from y). In other words, this step allows for the selection of the indices in the current y vector that are associated with the given class j. Moreover, the value y j,k  is the k&#39;th component of y j  (k=1 . . . n). 
     Another component that is defined during training is θ j , which is dependent on θ (which is computed during training). The term θ j  is defined as a n×n submatrix of θ, which is concatenation of the columns of θ, corresponding to indices in S j . In other words, θ j  corresponds to those columns of θ that correspond to the subsets Sj. 
     Another component that is computed during training is σ j,k  which is defined as a positive real number denoting the variance of k&#39;th component of the j&#39;th class, as well as μ j,k , which is defined as a mean of the k&#39;th component of the j&#39;th class. 
     The next step is to retrieve the precomputed values for σ j,k , μ j,k , and θ j  for the current class j (step  105 ), and compute the score for the current class j, preferably using the following formula step  106 )(step  105 ):                P   j     =       2      log             θ   j            -       ∑     k   =   1     n          log                   σ     j   ,   k           -       ∑     k   =   1     n              (       y     j   ,   k       -     μ     j   ,   k         )     2       σ     j   ,   k                     Equn   .              2                                
     This process (steps  103 - 106 ) is repeated for each of the classes j=(1 . . . J), until there are no classes remaining (negative determination in step  108 ). Then, the observation x assigned to that class for which the corresponding value of P j  is maximum (step  403 ) and the feature x is output with the associated category feature value g. 
     Referring now to FIG. 5, a flow diagram illustrates a method for estimating the training parameters according to one aspect of the present invention. In particular, the method of FIG. 5 is a clustering approach that is preferably used to compute the parameters θ, S j , σ j,k , and μ j,k  in a Gaussian system. The parameter estimation process is commenced during training of the system (step  200 ). Assume that initially, some labeled training data x i  is available, for which, the class assignments g i  have been assigned (step  201 ). 
     Using the training data assigned to a particular class j, the class mean for the class j is computed as follows:                    χ   _     j     =         ∑     gi   =   j            χ   j           ∑     gi   =   j          1         ,           Equn   .              3                                
     where {overscore (x)} j  comprises an n×1 vector (step  202 ). The class mean for each class is computed similarly. In addition, using the training data assigned to a particular class j, a covariance matrix for the class j is computed as follows:                Σ   j     =         ∑     gi   =   j              (       χ   j     -       χ   _     j       )            (       χ   j     -       χ   _     j       )     T             ∑     gi   =   j          1               Equn   .              4                                
     where Σ j  is an n×n matrix. The covariance is similarly computed for each class. 
     Next, using an eigenvalue analysis, all of the eigenvalues of each of the Σ j  are computed (step  204 ). An n×n matrix Σ j  is generated comprising all the eigenvectors of a given Σ j , wherein the term Σ j,i  represents the i&#39;th eigenvector of a given Σ j . 
     An initial estimate of θ is then computed as an nx(nJ) matrix by concatenating all of the eigenvector matrices as follows (step  206 ): 
     
       
         θ=[E 1  . . . E J ]  Equn.5. 
       
     
     Further, an initial estimate of S j  for each class j is computed as follows (step  207 ): 
     
       
           S   j   ={n ( j −1)+1 , . . . nj}   Equn.6, 
       
     
     such that θ j =E j . In other words, what this steps does is initialize the representation of each subset Sj as a set of indices. For instance, if subset S 1  corresponding to class  1  comprises the first n components of θ, then S 1  is listed as {1 . . . n}. Similarly, S 2  would be represented as {n+1 . . . 2n}, and S 3  would be represented as {2n+1 . . . 3n}, etc. 
     After θ and S j  are known, the means μ j  and variances σ j  for each class j are computed as follows (step  208 ):                    μ   j     =         ∑     gi   =   j              θ   j   T          x   i             ∑     gi   =   j          1         ,   and                        Equn   .              7                 σ   j     =           ∑     gi   =   j              (         θ   j   T          χ   i       -     μ   j       )     2           ∑     gi   =   j          1       .             Equn   .              8                                
     After all the above parameters are computed, the next step in the exemplary parameter estimation process is to reduce the size of the initially computed θ to compute a new θ that is ultimately used in a classification process (such as described in FIG. 2) (step  209 ). Preferably, this process is performed using what is referred to herein as a “merging of two vectors” process, which will now be described in detail with reference to FIG.  6 . This process is preferably commenced to reduce/optimize the initially computed θ. 
     Referring to FIG. 6, this process begins by computing what is referred to herein as the “likelihood” L(θ,{S j }) as follows (step  300 ):                  L        (     θ   ,     {     S   j     }       )       =       ∑     j   =   1     J            N   j     *     (       2      log             θ   j            -       ∑     i   =   1     n          log        (     σ     j   ,   i       )           )           ,           Equn   .              9                                
     where N j  refers to the number of data points in the training data that belong to the class j. 
     After the initial value of the likelihood in Equn. 9 is computed, the process proceeds with the selection (random or ordered) of any two indices o and p that belong to the set of subsets {Sj} (step  301 ). If there is an index j such that o and p belong to the same Sj (affirmative determination in step  301 ), another set of indices (or a single alternate index) will be selected (return to step  301 ). In other words, the numbers should be selected such that replacing the first number by the second number would not create an Sj that would have two numbers that are exactly the same. Otherwise, a deficient classifier would be generated. On the other hand, if there is not an index j such that o and p belong to the same Sj (affirmative determination in step  301 ), then the process may continue using the selected indices. 
     Next, each entry in {Sj} that is equal to o is iteratively replaced with p (step  303 ). For each iteration, the o&#39;th column is removed from θ and θ is reindexed (step  304 ). More specifically, by replacing the number o with p, o does not occur in Sj, which means that that particular column of θ does not occur. Consequently, an adjustment to Sj is required so that the indices point to the proper location in θ. This is preferably preformed by subtracting 1 from all the entries in Sj that are greater than o. 
     After each iteration (or merge), the likelihood is computed using Equn. 9 above and stored temporarily. It is to be understood that for each iteration (steps  303 - 305 ) for a given o and p, θ is returned to its initial state. When all the iterations (merges) for a particular o and p are performed (affirmative decision in step  306 ), a new estimate of θ and {Sj} are generated by applying the “best merge.” The best merge is defined herein as that choice of permissible o and p that results in the minimum reduction in the value of L(θ,{S j }) (i.e., the iteration that results in the smallest decrease in the initial value of the Likelihood) (step  307 ). In other words, steps  303 - 305  are performed for all combination of possibilities in Sj and the combination that provides the smallest decrease in the initial value of the Likelihood (as computed using the initial values of Equn. 7 and 8 above) is selected. 
     After the best merge is performed, the resulting θ is deemed the new θ (step  308 ). A determination is then made as to whether the new θ has met predefined criteria (e.g., a minimum size limitation, or the overall net decrease in the Likelihood has met a threshold, etc.) (step  309 ). If the predefined criteria has not been met (negative determination in step  309 ), an optional step of optimizing θ may be performed (step  310 ). Numerical algorithms such as conjugate-gradients may be used to maximize L(θ,{S j }) with respect to θ. 
     This merging process (steps  301 - 308 ) is then repeated for other indices (nj) until the predefined criteria has been met (affirmative determination in step  309 ), at which time an optional step of optimizing θ may be performed (step  311 ), and the process flow returns to step  210 , FIG.  5 . 
     Returning back to FIG. 5, once all the parameters are computed, the parameters are stored for subsequent use during a classification process (step  210 ). The parameter estimation process is then complete (step  211 ). 
     It is to be appreciated that the techniques described above may be readily adapted for use with mixture models, and HMMs (hidden markov models). Speech Recognition systems typically employ HMMS in which each node, or state, is modeled as a mixture of Gaussians. The well-known expectation maximization (EM) algorithm is preferably used for parameter estimation in this case. The techniques described above readily easily generalize to this class of models as follows. 
     The class index j is assumed to span over all the mixture components of all the states. For example, if there are two states, one with two mixture components, and the other with three, then J is set to five. In any iteration of the EM algorithm, α i,j  is defined as the probability that the i&#39;th data point belongs to the j&#39;th component. Then the above Equations 7 and 8 are replaced with                μ   j     =         ∑     i   =   1     N            α     i   ,   j            θ   j   T          χ   i             ∑     i   =   1     N          α     i   ,   j                   Equn   .              10                 σ   j     =         ∑     i   =   1     N              a     i   ,   j            (         θ   j   T          χ   i       -     μ   j       )       2           ∑     i   =   1     N          α     i   ,   j                   Equn   .              11                                
     Similarly, the above Equations 3 and 4 are replaced with                  χ   _     j     =           ∑     i   =   1     N            α     i   ,   j            χ   j             ∑     i   =   1     N          α     i   ,   j                         and             Equn   .              12                 Σ   j     =           ∑     i   =   1     N              α     i   ,   j            (       χ   j     -       χ   _     j       )              (       χ   j     -       χ   _     j       )     T             ∑     i   =   1     N          α     i   ,   j           .             Equn   .              13                                
     The optimization is then performed as usual, at each step of the EM algorithm. 
     It is to be understood that FIGS. 5 and 6 illustrate one method to compute θ and corresponding S j , and that there are other techniques according to the present invention to compute such values. For instance, the parameter estimation techniques described in the previous section, can be modified in various ways, for instance, by delaying some optimization, in the clustering process, or by optimizing for θ not on every step of the EM algorithm, but only after a few steps, or maybe only once. 
     Given k−1 columns of θ, the last column and the (possibly soft) assignments of training samples to the classes the remaining column of θ can be obtained as the unique solution to a strictly convex optimization problem. This suggest an iterative EM update for estimating θ. The so-called Q function in EM for this problem is given by:                    Q   =            const   +       ∑     t   ,   j                γ   j          (   t   )          log                     p   j          (     χ   t     )                         =            const   -       1   2            ∑     t   ,   j                γ   j          (   t   )            {         -   2        log                        A   j            +     log             D   j            +                                      Tr        {       A   j   ′          D   j     -   1              A   j          (       χ   t     -     μ   j       )              (       χ   t     -     μ   j       )     ′       }       }     ,                 Equn   .              14                                
     where γ j (t) is the state occupation probability at time t. Let P be a pool of directions and let P s  be the subset associated with j. For any direction a, let S(a) be states that include direction a. Let |A j |=|c j,a a′| where c j,a  is the row vector of cofactors associated with complementary (other than a) rows of A j . Let d j (a) be the variance of the direction a for state j (i.e., that component of D j ). For a εP j  differentiating with respect to a (leaving all other parameters fixed):              0   =       ∑       j   ∈     S        (   a   )         ,   t                γ   j          (   t   )              {         -   2            c     j   ,   a           c     j   ,   a            a   ′           +     2        a       d   j          (   a   )              (       χ   t     -     μ   j       )            (       χ   t     -     μ   j       )     ′         }     .                 Equn   .              15                                
     That is,                  ∑       j   ∈     S        (   a   )         ,   t                γ   j          (   t   )              c     j   ,   a           c     k   ,   a            a   ′             =     a          ∑       j   ∈     S        (   a   )         ,   t                γ   j          (   t   )                  (       χ   t     -     μ   j       )            (       χ   t     -     μ   j       )     ′           d   j          (   a   )         .                   Equn   .              16                                
     Let        G   =       ∑       j   ∈     S        (   a   )         ,   t                γ   j          (   t   )                  (       χ   t     -     μ   j       )            (       χ   t     -     μ   j       )     ′           d   j          (   a   )         .                                
     Then we have the fixed point equation for a:          a   =       ∑     j   ∈     S        (   a   )                  γ   j              c     j   ,   a            G     -   1             c     j   ,   a            a   ′               ,                          
     where          γ   j     =       ∑   t              γ   j          (   t   )       .                              
     We suggest a “relaxation-scheme” for updating a:            a   new     =       λ                   a   old       +       (     1   -   λ     )          (       ∑     j   ∈     S        (     a   old     )                  γ   j              c     j   ,     a   old              G     -   1             c     j   ,     a   old              a   old   ′             )           ,                          
     for some λε[0,2]. Once a direction is picked, γ j (t) can be computed again and find improve some other direction a in the pool P. 
     Another approach that may be implemented is one that allows assignment of directions to classes. The embodiment addresses how many directions to select and how to assign these directions to classes. Earlier, a “bottom-up” clustering scheme was described that starts with the PCA directions of Σ j  and clusters them into groups based on an ML criterion. Here, an alternate scheme could be implemented that would be particularly useful when the pool of directions is small relative to the number of classes. Essentially, this is a top-down procedure, wherein we start with a pool of precisely n directions (recall n is the dimension of the feature space) and estimate the parameters (which is equivalent to estimating the MLLT (Maximum Likelihood Linear Transform) (see, R. A. Gopinath, “Maximum Likelihood modeling With Gaussian Distributions or Classification,”  Proceedings of ICASSP ′98, Denver, 1998). Then, small set of directions are found which, when added to the pool, gives the maximal gain in likelihood. Then, the directions from the pool are reassigned to each class and re-estimate the parameters. This procedure is iterated to gradually increase the number of projections in the pool. A specific configuration could be the following. For each class find the single best direction that, when replaced, would give the maximal gain in likelihood. Then, by comparing the likelihood gains of these directions for every class, choose the best one and add it to the pool. This precisely increases the pool size by 1. Then, a likelihood criterion (K-means type) may be used to reassign directions to the classes and repeat the process. 
     Although illustrative embodiments have been described herein with reference to the accompanying drawings, it is to be understood that the present system and method is not limited to those precise embodiments, and that various other changes and modifications may be affected therein by one skilled in the art without departing from the scope or spirit of the invention. All such changes and modifications are intended to be included within the scope of the invention as defined by the appended claims.