Abstract:
A two-pass classification system and method that post-processes HMM scores with additional confidence scores to derive a value that may be applied to a threshold on which a keyword verses non-keyword determination may be based. The first stage comprises Generalized Probabilistic Descent (GPD) analysis which uses feature vectors of the spoken words and the HMM segmentation information (developed by the HMM detector during processing) as inputs to develop a first set of confidence scores through a linear combination (a weighted sum) of the feature vectors of the speech. The second stage comprises a linear discrimination method that combines the HMM scores and the confidence scores from the GPD stage with a weighted sum to derive a second confidence score. The output of the second stage may then be compared to a predetermined threshold to determine whether the spoken word or words include a keyword.

Description:
TECHNICAL FIELD 
     This invention relates to the field of automated speech recognition, and, more specifically, to the field of post-processing Hidden Markov Model keyword detection to establish whether a keyword has been detected. 
     BACKGROUND OF THE INVENTION 
     One of the better detectors for determining which keyword is present in a given utterance is the Hidden Markov Model (HMM) detector. In the HMM detector, digitized speech is analyzed against statistical models of the set of desired keywords (i.e., &#34;one&#34;, &#34;two&#34;, &#34;three&#34;, etc.) and a score is determined for each of the keywords. The keyword with the highest score is considered to be the &#34;best fit&#34;. There is, however, no reliable method for detecting whether a valid keyword has actually been spoken. One method of detecting keywords is to compare the HMM scores to a predetermined threshold. This method represents an initial approach to incorporating rejection in a speech recognizer. 
     In order to acheive more reliable results, the HMM scores have to be further analyzed (using linear discrimination analysis, for example) to determine whether any of the scores is above a threshold of &#34;goodness&#34; before a determination can be made that a specific utterance was in fact the keyword. However, HMM scores vary widely according to length of the verbal utterance, the speaker, and the speaking environment (i.e., the voice path, the microphone, etc.), which is not correctable even by post-processing with linear discrimination analysis and, thus, a simple comparison with a threshold may not be accurate. Therefore, a problem in the art is that HMM alone or with a linear discrimination analysis threshold determination is not well suited to establish a good test for acceptance of the highest-scoring keyword model. 
     SUMMARY OF THE INVENTION 
     This problem is solved and a technical advance is achieved in the art by a two-pass classification system and method that post-processes HMM scores with additional confidence scores to derive a value that may be applied to a threshold on which a keyword verses non-keyword determination may be based. The first pass (stage) comprises Generalized Probabilistic Descent (GPD) analysis which uses feature vectors of the spoken words and HMM segmentation information (developed by the HMM detector during processing) as inputs to develop confidence scores. The GPD confidence scores are obtained through a linear combination (a weighted sum) of the feature vectors of the speech (which are independent of the length of the verbal utterance and the speaking environment). The confidence scores are then delivered to the second pass (stage). 
     The second stage comprises a linear discrimination method similar to the prior art but, in addition to using the HMM scores as inputs, it also uses the confidence scores from the GPD stage. The linear discrimination method combines the two input values using a weighted sum. The output of the second stage may then be compared to a predetermined threshold. In this manner, the best fit keyword as determined by HMM analysis may be tested to determine whether the spoken word or words include a keyword. 
    
    
     BRIEF DESCRIPTION OF THE DRAWING 
     A more complete understanding of the invention may be obtained from a consideration of the following description in conjunction with the drawings, in which 
     FIG. 1 is a block diagram of the telephone network showing a toll switch equipped with an adjunct processor that includes an exemplary embodiment of this invention; 
     FIG. 2 is a more detailed block diagram of an adjunct processor showing an exemplary embodiment of this invention; 
     FIG. 3 is a functional block diagram of the processing performed in FIG. 2; and 
     FIG. 4 is a block diagram of a genetic HMM grammar used in the exemplary embodiment of this invention. 
    
    
     DETAILED DESCRIPTION 
     FIG. 1 is a block diagram of the telephone network 100 incorporating an exemplary embodiment of this invention. A customer at a calling telephone, for example, pay phone 102, wishes to reach a called telephone 103. The customer at pay phone 102 wishes to use a credit card to make a call to telephone 102. The customer dials the telephone number of telephone 103, which is determined by a local switch in local network 104 as a long distance or network call. Local network 104 sends the call into the toll network 106 by seizing an access trunk or channel 108, as is known in the art, to toll switch 110. The call is received at toll switch 110 at switching network 112. 
     As part of call setup, toll switch 110 records billing information. In this case, a pay phone does not have billing information associated with it; therefore, central control 114 of toll switch 110 connects an adjunct processor to the call. Adjunct processor collects credit card billing information from pay phone 102. For purposes of describing this invention, adjunct processor includes an exemplary embodiment of this invention which collects verbal credit card information, or alternatively verbal collect calling or third party billing information. This invention is not limited to this embodiment, as it may be used to determine the utterance of any keyword. 
     Adjunct switch 116 comprises a plurality of service circuits, such as speech recognizer 122, a processor 118, and memory 120. Processor 118 connects the call through to voice processor 122, which then audibly prompts the customer at pay phone 102 to speak his/her credit card number. This invention then processes the verbal responses received from the customer at pay phone 102 and determines what, if any, keywords were spoken by the customer at pay phone 102. These keywords are then recorded as the billing number or credit card number (or other appropriate action is taken, as necessary) and call processing proceeds. Toll switch 110 connects to a second toll switch 130, which completes the call to local network 132 and to telephone 103. 
     Turning now to FIG. 2, a speech processing unit 122 including an exemplary embodiment of this invention is shown. Incoming speech is delivered by processor 118 of adjunct 116 (FIG. 1) to CODEC or digital interface 202. CODEC 202, as is known in the art, is used in situations where the incoming speech is analog, and a digital interface is used in cases where incoming speech is in digital form. The incoming speech is delivered to a processor 204, which performs analysis of the speech. Memory 206, connected to processor 204, is used to store the digitized speech being processed and to store a program according to an exemplary embodiment of this invention. Processor 204 is responsive to the instructions of the program in memory 206 to process incoming speech and make a determination of a &#34;best&#34; keyword and whether or not that keyword is good enough to be treated as valid. Other implementations of this invention may be readily apparent to one skilled in the art, including hardware circuits that perform the software functions of the described exemplary embodiment. It is therefore intended that all such embodiments be covered by the claims of this application. 
     Turning now to FIG. 3, a block diagram of the basic functionality of the exemplary embodiment of this invention is shown. Digitized speech in 8Hz frames is used as input 302 to a linear predictive coding analysis system 304. Linear predictive coding analysis and feature vector generation represent each frame with 24 parameters, as shown in Table 1. For purposes of describing this embodiment of this invention, a 10th order linear predictive coding analysis system is used having a 45 ms window length and 15 ms update rate. A total of 38 parameters are computed, consisting of the first 12 cepstral coefficients, their first derivatives (called the Delta Cepstral Coefficients), the second derivatives (called Delta-Delta Cepstral Coefficients), Delta energy, and Delta-Delta energy. To reduce the computational load, a subset of 24 of the 38 parameters is used to form a recognizer feature vector. This 24 parameter subset is optimally selected using discriminative analysis for feature reduction, as described in E. L. Boccchieri, and J. G. Wilpon, &#34;Discriminative Analysis for Feature Reduction in Automatic Speech Recognition,&#34; in Proceeding IEEE International Conference on Acoustics, Speech, Signal Processing, page 501-504, March, 1992. The linear predictive (LP) coding analysis delivers the first 10 autocorrelation coefficients to feature vector generator 306. Feature vector generation uses the memory and produces Table 1 on a frame by frame basis. 
     
                       TABLE 1______________________________________Recognizer Feature Vector ParametersParameter            ParameterIndex      Parameter Index        Parameter______________________________________1          cep(1)    13           Δcep(4)2          cep(2)    14           Δcep(5)3          cep(3)    15           Δcep(6)4          cep(4)    16           Δcep(7)5          cep(5)    17           Δcep(9)6          cep(6)    18           Δ.sup.2 cep(1)7          cep(7)    19           Δ.sup.2 cep(2)8          cep(8)    20           Δ.sup.2 cep(3)9          cep(9)    21           Δ.sup.2 cep(4)10         Δcep(1)                22           Δ.sup.2 cep(6)11         Δcep(2)                23           Δenergy12         Δcep(3)                24           Δ.sup.2 energy______________________________________ 
    
     Feature vector generator 306 delivers parameters of Table 1 to a Hidden Markov Model recognizer 308, and to the Generalized Probabilistic Descent (GPD) analysis 310 according to this invention. Each keyword is modeled as a continuous density HMM which uses 8 to 10 states, depending on the specific word, left to right model, with 15 Gaussian mixture components per state. The segment K-means algorithm as described in L. R. Rabiner, J. G. Wilpon, and B. H-Juang, &#34;A Segment K-Means Training Procedure for Connected Word Recognition,&#34; AT&amp;T Technical Journal, Volume 65, No. 3, pages 21-31, May-June, 1986, is used to estimate the HMM parameters and the well-known Viterbi decoding algorithm is employed to obtain the optimal HMM path. 
     FIG. 4 shows a block diagram of a generic HMM grammar that is used for purposes of describing the exemplary embodiment. Every grammar node in FIG. 4 is a terminal node, implying that a separate utterance segmentation is obtained for each node. The silence model in this grammar allows for the recognition of keywords with silence before and after the keyword, while the garbage (filler) model facilitates recognition of keywords imbeded in other speech material. The garbage model parameters are estimated using a database of speech that does not include any of the valid keywords. Including a garbage model significantly increases recognition accuracy when the goal is to word spot a keyword imbeded in extraneous speech. The garbage model can also be used in the keyword/non-keyword classification as discussed below. The garbage database used here comes from three sources: phonetically balanced sentences, speakers speaking their name, and extraneous speech on either side of the keyword collected from an actual recognition trial. 
     The goal in any classification system is to maximally separate the classes, as seen in FIG. 4. In this case, there are two classes: keywords and non-keywords. The prior art method of making this decision is to use the HMM output itself as a determination for keyword/non-keyword classifier. This can be done by comparing the HMM likelihood score of the garbage node, node 0 in FIG. 4, to the largest likelihood score among the keyword nodes, nodes 1 through N. If the garbage score is larger, then a non-keyword decision can be made. Another option is to set a threshold on the likelihood scores or some combination thereof. Although the HMM classifier has been shown to be very reliable in classifying a closed set of keywords (i.e., predefined set of keywords), its performance on an open set, such as detection of any utterance not containing a keyword, is not very reliable. 
     Returning to FIG. 3, a two-pass classifier according to the exemplary embodiment of the invention uses the information supplied by the HMM keyword classifier in a two-stage discriminant analysis. The first stage is Generalized Probabilistic Descent (GPD) analysis 310 and a second stage provides linear discrimination analysis 312. 
     Information supplied by the HMM is employed in a two stage discriminant analysis. The first stage is trained using the Generalized Probabilistic Descent (GPD) discriminant training as described in W. Chou, B. H-Juang, and C-H. Lee, &#34;Segmental GPD Training of HMM Based Speech Recognizer,&#34; Proc. IEEE Int. Conf. Acoust., Speech, Signal Processing, pages 473-476, Mar., 1992. The second is trained using Fisher&#39;s linear discriminant training method, as described in K. V. Mardia, J. T. Kent, J. M. Bibby, &#34;Multivariant Analysis,&#34; London, Academic Press, 1979. The output of the second stage is a classification parameter that can be compared to a threshold to make the final keyword/non-keyword decision. In the case of a keyword decision, the recognition answer is the candidate with the largest HMM likelihood score. Therefore, formally stated, the keyword/non-keyword classification is the classification of two classes. The first class includes all instances where the utterance does not contain any keyword, and the second class includes all cases where the utterance contains a keyword and the largest terminal node likelihood score corresponds to the correct keyword model (i.e., correct HMM recognition). 
     In operation, incoming speech 302 is, in box 304, segmented into frames and 10 autocorrelation coefficients are computed per frame. The 10 autocorrelation coefficients are passed to box 306, where feature vectors are generated. The feature vectors are passed to Hidden Markov Model recognizer 308, which performs statistical pattern matching between the incoming feature vectors and prestored models. 
     To perform keyword/nonkeyword classification, boxes 310 and 312 are included. Box 310 receives word and state segmentation information from HMM recognizer 308, and receives the same feature vectors from box 306 as the HMM recognizer 308. Box 310 uses the segmentation information to linearly combine the feature vectors in order to deliver scores that indicate whether a keyword is present or not. Box 312 combines the outputs of GPD 310 with the HMM likelihood scores to produce a single value that is then compared to a threshold. If a determination is made that a keyword is present, then the keyword with the highest HMM likelihood score is designated as a recognized keyword. 
     THE GPD DISCRIMINATION STAGE 
     In its original formulation, GPD discriminative training was developed to minimize recognition errors by optimizing with respect to the HMM model parameters. As a framework for discriminative training, the GPD is used to train the first stage of the two-pass classifier. The GPD framework first defines a distance function, and rather than minimize this function directly, a loss function that is itself a function of the distance function is minimized. The purpose of the loss function, which is a monotonic smooth function, is to emphasize the separation of cases that are highly confusable while deemphasizing the less confusable cases. 
     For this keyword/non-keyword classification problem, the distance function is defined in terms of the HMM segmentation information. The HMM can be thought of as a &#34;time-warper,&#34; time-warping a given utterance into a fixed number of states, thereby, allowing the representation of the utterance by a fixed length vector. Similar to the method used in P. Ramesh, S. Katagiri, and C. -H. Lee, &#34;A new connected word recognition algorithm based on HMM/LVQ segmentation and LVQ classification,&#34; in &#34;Proc. IEEE Int. Conf. Acoust., Speech, Signal Processing, pp. 113-116, May, 1991, the fixed length vector transformation is accomplished by taking the means of the feature vectors of all the frames in a given state, and then concatenating the slates&#39; mean vectors to form a fixed length vector, called the discriminating vector, for the utterance. In addition to the advantages (from a classification point-of-view) gained by transforming variable length utterances into fixed length vectors, the discriminating vectors enables exploitation of the correlation that exists among states of a keyword model. The HMM grammar of FIG. 4 assumes one model per keyword, and provides a terminal node for every model including garbage. Therefore, for a given utterance, a set of discriminating vectors can be generated, one for each model. 
     The definition of the distance function starts by first defining a discriminant function as 
     
         R.sub.j (x.sub.j, a.sub.i,j)=x.sub.j.sup.t a.sub.i,j, j=1,2,. . . , N,g,[1] 
    
     where x j  is the discriminating vector for keyword model j, N is the number of keywords, &#34;g&#34; denotes the garbage model, &#34;i&#34; is the index of the keyword HMM model with the largest terminal node likelihood score, and a i ,j is a vector of weights obtained using the GPD training described below. 
     Given the above two classes, the goal is to determine a i ,j, for j=1,2, . . . ,N,g, such that if the utterance contains no keyword, then ##EQU1## Similarly, if the utterance contains a keyword and the HMM recognizes it correctly, the goal is ##EQU2## Essentially, equations [2] and [3] convey the fact that to achieve good classification performance, the discriminating function corresponding to the correct class must be the largest. 
     The discriminating functions are used to define an overall distance function. For implementational convenience, the distance function is defined separately for each of the two classes. Consistent with the GPD framework, the distance function for the non-keyword class is ##EQU3## where 
     
         X=[x.sub.1 x.sub.2. . . x.sub.N x.sub.g ],                 [5] 
    
     
         A.sub.i =[a.sub.i,1 a.sub.i,2. . . a.sub.i,N a.sub.i,g ],  [6] 
    
     ηis a positive number, and &#34;i&#34; is the index of the keyword model with the largest terminal node likelihood score. For the keyword class, ##EQU4## 
     The distance function of equations [4] and [7] is then incorporated in a sigmoid shaped loss function defined as ##EQU5## where γ is a constant used to control the smoothness of the monotonically increasing L i  (X,A i ). 
     Ideally, the goal is to minimize the expected value, E[L i  (X,A i )], with respect to A i . However, since the probability density function of X cannot be explicitly determined, a gradient-based iterative procedure is used to minimize the loss function. The gradient procedure iteratively adjusts the elements of A i  according to 
     
         (A.sub.i).sub.n+1 =(A.sub.i).sub.n -εVL.sub.i (X.sub.n,(A.sub.i).sub.n)                                 [9] 
    
     where VL i  (X n ,(A i ) n ) is the gradient of the loss function with respect to A i  evaluated at the n th  training sample (utterance) X n . Here ε is the update step size. 
     Two points are worth mentioning here. First, the expected value of the loss function is minimized without explicitly defining the probability density function of X. Instead, the GPD adaptively adjusts the elements of A i  according to the set of observable vectors {X n  }. Second, a classification error rate function that is not continuous is mapped into a continuous smooth loss function that can be readily minimized. 
     According to the definition of the distance function given in equations [4] and [7], and the adaptation formula [9], every element in the matrix A i  is adapted every iteration. This can be overwhelming. A simple example illustrates this. Consider the example of recognizing the 11 digits, where, each word is modeled as a 10 state left-to-right HMM. A 10-state left-to-fight garbage model is also included. Each frame is converted to a 24-dimensional feature vector, as described above. Therefore, the discriminating vector x j  is of dimension 240, and each matrix A i  is 240×12, where i=1,2, . . . , 11. Adapting 2880 parameters each iteration requires a large number of computations, as well as a long time to converge. Moreover, the larger the keyword set, the larger the number of adapted parameters per iteration. It is therefore desirable to have the number of parameters adapted per iteration manageable and independent of the size of the keyword set. 
     To achieve this, a modification to the distance function of equations [4] and [7] is needed. The distance function as it is defined incorporates information concerning all the keyword and garbage models. This is useful if the goal is to classify an utterance among N different classes. In the keyword/non-keyword classification case, we are only concerned about two classes. The modified distance function is, therefore, defined as follows. For the non-keyword class, the distance function is 
     
         d.sub.i (X,Z.sub.i)=-R.sub.g (x.sub.g,a.sub.i,g)+log[[.sub.e ηR.sub.i (x.sub.i,a.sub.i,i).sub.+e ηR.sub.k (x.sub.k,a.sub.i,k)].sup.1/η,[10] 
    
     where &#34;k&#34; is the index of the keyword model with the second largest terminal node keyword likelihood score. For the correct classification class, 
     
         d.sub.i (X,A.sub.i)=-R.sub.i (x.sub.i,a.sub.i,i)+log [.sub.e ηR.sub.g (x.sub.g,a.sub.i,g).sub.+e ηR.sub.k (x.sub.k,a.sub.i,k ].sup.1/η[ 11] 
    
     The modified distance function is defined in terms of the discriminating functions for three HMM models, namely, the word model with the largest node likelihood, the word model with the second largest node likelihood, and the garbage model. As will be seen below, incorporating the second largest node likelihood with the other two, provides an added degree of freedom that is used in the second stage discrimination. 
     THE LINEAR DISCRIMINANT STAGE 
     The second stage discrimination of the two-pass classifier employs linear discriminant analysis to combine the classification power of the GPD stage with that of the HMM itself. The GPD scores, defined as the numerical values of the discriminating functions of equation [1], are combined with the HMM likelihood scores using linear discrimination. The output of this stage is a classification score that can be compared to a threshold to perform the final keyword/non-keyword decision. Specifically, the parameters used in this discrimination stage form a four dimensional classification vector, y, where 
     
         y.sub.1 =log P.sub.i (O)-log P.sub.g (O),                  [12] 
    
     
         y.sub.2 =log P.sub.i (O)-log P.sub.k (O),                  [13] 
    
     
         y.sub.3 =R.sub.i (x.sub.i,a.sub.i,i)-R.sub.g (x.sub.g,a.sub.i,g),[14] 
    
     
         y.sub.4 =R.sub.i (x.sub.i,a.sub.i,i)-R.sub.k (x.sub.k,a.sub.i,k).[15] 
    
     Here P i  (O) is the terminal node likelihood corresponding to keyword &#34;i&#34;. Again, the indices &#34;i&#34;, &#34;k&#34;, &#34;g&#34; refer to the keyword model with the largest terminal node likelihood., the keyword model with the second largest terminal node likelihood, and the garbage model, respectively. To obtain a single classification score, the vector y is projected onto a single dimension. The classification score is therefore written as 
     
         C=y.sup.t b.sub.i, i=1,2 . . . , N                         [16 
    
     where b i  is the projection vector, given that HMM model &#34;i&#34; results in the largest keyword terminal node likelihood. The projection vectors are determined using the Fisher discriminant role as discussed in K. V. Maddia, J. T. Kent, and J. M. Bibby, &#34;multivariant Analysis,&#34; London Academic Press, 1979, to maximize the separation between the keyword and the non-keyword class. 
     Y nokey ,i is the classification vector given that the input speech does not contain a keyword and the largest keyword terminal node likelihood corresponds to keyword &#34;i&#34;. Further, Y key ,i is the classification vector given that the input speech contains the keyword &#34;i&#34; and the largest keyword terminal node likelihood corresponds to word &#34;i&#34;. The Fisher discriminant rule determines b i  by maximizing the ratio of the between-classes sum of squares to the within classes sum of squares, as follows, ##EQU6## where 
     
         G.sub.i =(y.sub.key,i -y.sub.nokey,i) (y.sub.key,i -y.sub.nokey,i).sup.t,[18] 
    
     
         W.sub.i =E[v.sub.i v.sub.i.sup.t ]+E[u.sub.i u.sub.i.sup.t ],[19] 
    
     
         v.sub.i =y.sub.key,i -y.sub.key,i,                         [20] 
    
     and 
     
         u.sub.i =Y.sub.nokey,i -y.sub.nokey,i                      [21] 
    
     y key ,i is the mean classification vector over all utterances containing keyword &#34;i&#34; that the HMM recognizer recognized correctly, and y nokey ,i is the mean classification vector for utterances not containing a keyword where the largest keyword likelihood corresponds to word &#34;i&#34;. Maximizing F i  and solving for b i  gives 22 
     
         b.sub.i =W.sub.i.sup.1 (y.sub.key,i -y.sub.nokey,i), i=1,2,. . . N.[22] 
    
     During recognition, the classification score given in equation [16] is computed using b i  of equation [22]. It is then compared to a threshold to determine if the utterance should be rejected. The value of the threshold depends on the desired operating point of the recognizer. 
     It is to be understood that the above-described embodiments are merely illustrative principles of the invention, and that many variations may be devised by those skilled in the art without departing from the scope of the invention. It is, therefore, intended that such variations be included within the scope of the appended claims.