Patent Publication Number: US-6044344-A

Title: Constrained corrective training for continuous parameter system

Description:
BACKGROUND OF THE INVENTION 
     1. Field of the Invention 
     The present invention generally relates to improvements in decoder accuracy in pattern recognition and, more particularly, to a method for exposing a pattern recognition decoder to new training data without losing previously learned data. The method disclosed is applicable in areas of pattern recognition such as speech, handwriting and image recognition, machine translation, natural language processing and the like. 
     2. Background Description 
     Automated pattern recognition is a difficult task. For example, while there are many techniques for recognizing speech patterns being studied today, the so-called Hidden Markov Modeling (HMM) proves promising. &#34;Hidden&#34; refers to the probabilistic and not directly observable events which underlie a speech signal. There have been many variations of HMM proposed. HMM speech recognition systems typically use realizations of phonemes which are statistical models of phonetic segments, including allophones (phones) having parameters that are estimated from a set of training examples. Models of words are made by chaining or linking appropriate phone models. Recognition consists of finding the most likely path through the set of word models for the input speech signal. 
     HMM speech recognition decoding systems first need to be trained through an iterative process. That is, the system must be repeatedly exposed to training examples or words of a particular speaker&#39;s voice. A training word is analyzed to generate a framed sequence of acoustic parameter vectors or statistical models. A valid or &#34;good&#34; recognition occurs when the most likely path through the set of word models for the training word results in recognizing the correct word (i.e., the training word itself). 
     Unfortunately, when a decoding system is being trained and is exposed to training data at some iterative stage, it may lose several good properties that were acquired in previous training stages. The maximum likelihood (or mutual information) of the parameters may not lead to values which maximize recognition accuracy. Alternative error corrective estimation procedures are known which aim to minimize the number of recognition errors. Such procedures imitate error correction procedures for linear classifiers where adjustments are made unless the log probability for the correct word exceeds the log probability of all other words by some threshold. This procedure is lacking a rigorous foundation and, in particular, it does not provide hill-climbing algorithms. This procedure also does not guarantee that other recognition errors will not be introduced while some particular &#34;near miss&#34; errors are being corrected. 
     SUMMARY OF THE INVENTION 
     It is therefore an object of the present invention to provide a way to train a decoder on new data while preserving its accuracy on old data. 
     According to the invention, some good features or previously learned data are represented as constrained equations that define a constrained domain in a space of statistical parameters of the decoder. Some part of a previously learned data is represented as a feasible point on the constrained domain. 
     &#34;Good features&#34; are some factors in a decoding procedure that lead to successful decoding of some &#34;chunks&#34; of phrases. These &#34;chunks&#34; can be either words that were decoded correctly, or sentences that were decoded correctly, or even phonemes in words that are always or mostly decoded correctly. For example, the decoder received as input an acoustic utterance corresponding the phrase &#34;We obtained the bulk of the data from Broadcast News&#34;. Assume that the decoder decoded this utterance as &#34;We obtained the BAN of the data from . . . News&#34;. Hence, the decoder decoded the sentence with two errors, one substitution, and one deletion. In this example words that were decoded correctly can be used to define &#34;good features&#34;. These good features can be related to some factors in a space of statistical parameters of the decoder that may help to recognize correctly some words or phrases. The inequalities (1), below, provide a detailed example of factors related to &#34;good features&#34; (i.e., &#34;good&#34; sentences). The parameters in these inequalities depends on the training procedure. Different training procedures (e.g., different starting points) may lead to different parametric values in a decoder (e.g., different values of HMM in a decoder) after several iterations of forward-backward training steps. If inequalities (1) are satisfied for new values of training parameters then we are guaranteed that these &#34;good&#34; sentences will be decoded correctly by a decoder with these new parametric values (if other conditions, e.g. acoustic input utterance, remains the same). 
     A training procedure is reformulated as optimization of objective functions over the constrained domain. Finally, the constrained optimization problem is solved. This procedure incorporates a new error correcting strategy that, among other things, allows the use of hill-climbing algorithms and guarantees the error rate on old data is not increased. Hill-climbing algorithms guarantees that for each new iteration likelihood value is not decreasing (and typically increase until iterations started to converge to local maximum). 
     In a practical application, the invention is applied to training a continuous parameter speech recognition system. In this system, feature vectors resulting from the application of fast Fourier transform (FFT) analysis of a speech segment are input. These feature vectors are used to train the system whose output and probabilities are modeled by weighted sum of exponential functions with mean vectors and covariance matrices. Each path through the system gives rise to a likelihood score that is computed along this path. The best words (or candidate words) are chosen by a decoder as those that have highest likelihood scores along best paths (or as a sum of likelihood scores along all paths). 
     The fact that the best word is correct means that likelihood scores corresponding this word are higher than scores attached to other words. This property can be represented as a set of inequalities that involve means, covariances and weighted coefficients. This set of inequalities define a domain T in a parameter space K of means, covariances and weighted coefficients. Words are represented as points in this domain. This domain is not empty if the best word (corresponding to a point A) coincides with the correct word. 
     When an iterative step is made in the process of training, the means, covariances and weighted values are updated in accordance with a mathematical procedure that usually guarantees that the overall likelihood score for all words in a training script increases. The mathematical procedure is an algorithm for iterative finding of new points A1, A2, A3, . . . in a parameter space. For example Lalit R. Bahl et al. &#34;Speech Recognitions with continuous-parameter hidden Markov models&#34;, IEEE 1998, p. 40-430), section 2, describes such-algorithm to maximize some functions, and is herein incorporated by reference. 
     During such an update, it can happen that the new best word (corresponding a point B) will not coincide with the correct word; i.e., the point B .di-elect cons. K does not belong to the domain T that is defined by the constraints. If the point A (corresponding the best word in a previous iterative training step) is an inner point of the domain T, then there is a linear interval I belonging T (and lying on a line connecting the point A with the point B) such that any point on this interval I has a higher likelihood score than the likelihood score corresponding to A. Repeating this step iteratively builds a set of models with increased overall likelihood scores while preserving error rate on the fixed input set of feature acoustic vectors V. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The foregoing and other objects, aspects and advantages will be better understood from the following detailed description of a preferred embodiment of the invention with reference to the drawings, in which: 
     FIG. 1 is a block diagram illustrating the concept of constrained training that preserves the accuracy on a fixed input set of feature vectors according to the invention; 
     FIG. 2 is a flow diagram illustrating the decoding of data via the decoder shown in FIG. 1; 
     FIG. 3 is a flow diagram illustrating how the likelihood score for paths are computed in the practice of the invention; 
     FIG. 4 is a flow diagram showing how a gradient is computed in the practice of the invention; 
     FIG. 5 is a flow diagram showing how constrained equations are computed in the practice of the invention; 
     FIG. 6 is a flow diagram showing how parameters are updated in the practice of the invention; 
     FIG. 7 is a path diagram illustrating several iterative steps according to one example of the invention; and 
     FIG. 8 is a flow diagram showing the training procedure and incorporating the path diagram of FIG. 7. 
    
    
     DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT OF THE INVENTION 
     Referring now to the drawings, and more particularly to FIG. 1, there is shown by way of example how the method according to the invention is applied to a continuous speech recognizer. It is assumed that the speech training/decoder system comprises the following objects and modules. Referring to block 101, the training/decoding system uses mixtures of Gaussian densities in HMM output distributions. In the framework of maximum likelihood estimation (MLE) of HMM parameters, Gaussian mixture distributions are often seen as the best way of approximating as close as possible, the &#34;true&#34; underlying distributions. 
     This system requires consideration of the following data. First, some training data (e.g., one hundred sentences of spoken speech) is supplied by block 102. This data includes a training script (i.e., the one hundred sentences) and acoustic feature vectors corresponding these sentences. Within block 101, there is provided the best and general paths in HMM, represented by block 103. In addition, the parameter system (i.e., mean vectors, covariance matrices, weights, transition probabilities) is provided within block 101, as represented by block 104. 
     The training of the system according to the invention decodes data from HMM block 101 in decoder 105. A gradient is computed (training without constraints) in block 106. Computation of the equations that define the &#34;constrained&#34; domain over which the accuracy of the decoder 105 should be preserved in the next iterative steps is performed in block 107. Computation of a step of size a along a gradient for each Gaussian density is made in block 108. Finally, a parameter update is made by the loop 109. The fact that the decoder 105 performed well on some input data means that some inequalities for scores on input-output data are fulfilled. This set of inequalities forms constrained equations that we are trying to satisfy while we expose the decoder to a new training data. 
     FIG. 2 illustrates how the decoder 105 decodes the input data. In the block 201, the input data (acoustic feature vectors) are divided into one hundred segments A={a i  } (using, for example the Viterbi alignment). Viterbi alignment is explained, for example, in Lait R. Ball et al., &#34;A maximum likelihood approach to continuous speech recognition&#34;, IEEE Transaction on Pattern analysis and Machine Intelligence, vol. pami-5, no. 2, March 1983, Section V, and is herein incorporated by reference. 
     These segments correspond to the one hundred spoken sentences S={s i  } and are decoded using standard decoding methods. In block 202, for each sentence s .di-elect cons. S, the five best candidate sentences S i={S   i   j  }, (i=1, . . . , 100, j=1, . . . , 5) are found. 
     The best candidate sentences are obtained as follows. First, a set of candidate sentences are obtained by concatenating words from lists of candidate words. For each sentence s i  in this list, a likelihood score, over the corresponding acoustic segment {a i  }, is computed. Five sentences with highest likelihood scores then are chosen. 
     In the block 203, the best path ν s .sbsb.i in a HMM set and the likelihood score L (ν s .sbsb.i) along this path for each sentence S i  .di-elect cons. S are computed. In block 204, the best path ν s .sbsb.i and the likelihood score L (ν s .sbsb.i) along this path are computed for each sentence S i   j  .di-elect cons. S i . Then in block 205, the subset G of &#34;good&#34; sentences is identified, 
     
         G={s.di-elect cons.S|L(ν.sub.s.sbsb.i)-ε&gt;L(ν.sub.s.sbsb.j)}(1) 
    
     where i=1, . . . , 100, j=1, . . . , 5, .di-elect cons.&gt;0, ν s .sbsb.j ≠ν s .sbsb.j. &#34;Good&#34; sentences are those that were decoded correctly; i.e., their likelihood scores are higher than scores of candidate sentences. This situation is approximated by considering the inequalities (1) in which the likelihood of each correctly decoded sentence is larger than likelihoods of five &#34;best&#34; corresponding candidate sentences. In block 206, the list of candidate sentences is produced for each &#34;good&#34; sentence from (1): 
     
         S(G)={∪S.sup.i |s.sub.i νG}             (2) 
    
     FIG. 3 illustrates how the likelihood score for paths is computed. In block 301, the feature vector, y=y 1   T  =y 1  . . . y T , is input. Block 302 contains a total set of Gaussian distributions for HMM: N(Y; m k  ; W k ), where m k  and W k  are means and covariance of k th  Gaussian distribution, respectively. A general definition of Gaussian distribution is the following: 
     
         N(y;m;W)=w×.sub.e.sup.- (y-m)&#39;W(y-m)                 (3) 
    
     where ##EQU1## Block 303 contains best paths v s  for each s .di-elect cons. G∪S(G) that were described in blocks 201 and 205 of FIG. 2. Block 304 contains transition probabilities along a path v s  : a(v s )=a 1  a 2  a . . . a r , where a t  denote a transition probability for a t th  frame. Block 305 contains mean vectors (for most probable sub-mixtures along a path v s ): 
     m(v s )=(m s   1 , . . . , m 3   T ). 
     Block 306 contains covariance matrices (for most probable sub-mixtures along a path v s ): W(v s )=(W s   1 , . . . , W s   T ). Block 307 contains weighted factors (for most probable sub-mixtures along a path v s ): λ(v s )=(λ 1 , . . . , λ T ). Likelihood score for a path v and a feature string of vectors y T   1  is computed according the following formulae: ##EQU2## Likelihood scores for the whole HMM set are computed as a sum of scores for all paths in HMM. 
     FIG. 4 illustrates how a gradient is computed. Let θ=(m k ,W k ) be the total set of mean vectors and covariance matrices in block 401. Using standard methods, one can find in block 402 new θ: ##EQU3## Then in block 403, ##EQU4## where functions f() and g() are defined from standard training procedure for continuous parameters. 
     A standard training procedure is any (usually hill-climbing procedure) that finds new parameters by maximizing objective function (likelihood function) either without any constrains or using such typical constrains as probabilities which are non-negative and sum of probabilities=1. In the present invention, the likelihood function is maximized subject to non-typical constrains that come from requirement that some &#34;good&#34; properties were satisfied. 
     For continuous parameters, the standard training procedure involves maximizing, without constraints, the likelihood function that consists of sum of products of exponential expressions (equation (4)). The non-standard training procedure requires maximization of the same likelihood function subject non-standard constrains that are described, for example, in equation (7). Another example of standard procedure is described in &#34;Maximization technique occurring in the statistical analysis of probable functions of Markov Chains&#34;, L. E. Baum et al., The Annals of Mathematical statistics, 1970, vol 41, No. 1, pp. 164-171--section 3, and section 4 (for continuous parameters), which is herein incorporated by reference. 
     Referring again to FIG. 4, the gradient in this iteration step is defined as difference of vectors θ-θ in block 404. 
     The following mathematical statement is the basis for the computation of a step α along the gradient θ-θ such that α×(θ-θ)+θ belongs to a manifold defined by constraints. 
     The following is a statement relates to the procedure for training a likelihood function subject to constraints according to the present invention: 
     Let α=(α k ), α.di-elect cons. [0,1], where k are from the index set that parametrizes mean vectors and covariance matrices (one α for each Gaussian distribution). Let 
     θ=θ(α)={m(α k ), W(α&#39; k )} where m k  (α k )=m k  α k  +(1-α k ) m k  and W k  (α&#39; k )=g(y 1   T , m k  (α&#39; k )) for any α k , α&#39; k  such that 0≦α&#39; k  ≦α k  ≦1, 
     where y 1   T  is an input pattern vector, m k  denotes a mean vector indexed by k, m k  denotes another mean vector indexed by k, W k  (α&#39; k ) denotes a covariance matrix indexed by k and dependent on a real number α&#39; k , α=(α k ) is a set of real numbers α k , where 0≦α k  ≦1 and k are from the index set that parametrizes mean vectors and covariance matrices, m k  (α k ) denotes another mean vector that is obtained as weighted sum of mean vectors m k  and m k , a vector m(α k ) depends on a real number α k   
     Then L.sub.θ (y 1   T )&gt;L.sub.θ (y 1   T ). 
     The above statement allows to split computation of means and covariances. First, means are updated to satisfy the equations. Then covariances are updated to satisfy the equations. 
     The new feature of our theorem is the fact that it can be used in the domain that is restricted by constraints. The training of continuous parameters require finding of two sets of parameters, that is, means and covariance. Given a set of means and covariance and the value of likelihood function at this set, we want to find a new meaning and covariance such that at this new set of means and covariance the value of likelihood function is not less than its values at the initial set. The statement allows one to do this. It provides a whole set of values for means and covariance (belonging to some interval) such that at any point of this interval the value of the likelihood function is not less than at the initial set of means and covariance. Since the initial set of means and covariance is a feasible point (i.e. belongs to the domain of parameters with &#34;good&#34; properties) some part of this interval also belongs to this constrained subdomain. Therefore one can choose a new mean-covariance set on this part of interval, such that on one hand, it belongs to the constrained subdomain, on the other hand, it is guaranteed that the value of likelihood function at this point is not decreasing. 
     FIG. 5 describes how constrained equations are computed. In block 501 log of (4) is computed. ##EQU5## where ##EQU6## and summation is taken along a path ν. In block 502, for each corresponding pair of paths ν=ν s , s .di-elect cons.G and ν&#39;=ν&#39; s , s&#39;.di-elect cons.S(G) the following equation from 1 is constructed: ##EQU7## Substituting in the above equations formulas m k  (α k )=m k  α k  +(1-α) m k  and W k  (α&#39; k )=g(y 1   T , m k , (α&#39; k )) produces the following two series of equations of α and α&#39; generated in block 503: ##EQU8## and equations for covariances ##EQU9## These systems have solutions for α=0, α&#39;=0. The task is to find some non-zero α that satisfies these equations. This α would provide a step along a gradient that is mentioned in the above Statement. 
     This system can be solved using iterative linearization or splitting equations in subgroups of equations (one system for each parameter if the number of parameters more than number of equations). 
     In the FIG. 6, formula for parameter update is illustrated. Let m k  be a set of means obtained via one standard iterative step starting from a set of means m k  (see for example (7) ). This defines the gradient grad={m k  -m k  } as described in the FIG. 5 above. Using equations described in block 503 one can find non-zeroα that defines a step along this gradient and provide a parameters that satisfies equations in Block. 503. Let m=grad x α. 
     Then updated parameters can be computed as follows: 
     
         θ=θ(α)={m.sub.k (α.sub.k), W.sub.k (α&#39;.sub.k)}(10) 
    
     where 
     
         m.sub.k (α.sub.k)=m.sub.k α.sub.k +(1-α.sub.k) m.sub.k(11) 
    
     and 
     
         W.sub.k (α&#39;.sub.k)=g(y.sub.1.sup.T, m.sub.k (α&#39;.sub.k))(12) 
    
     for any α k , α&#39; k  such that 0≦α&#39; k  ≦1. 
     For any α&#39; k  in this interval an updated parameters are guaranteed not decrease an overall likelihood score in accordance with the Statement above. Because all updated parameters belong to the domain defined by equations in block 503 overall error rate over the data A={a i  } in block 201 will be not worsening. In other words, the present invention provides a method for updating decoding parameters in such a way that an overall likelihood increases and error rate on fixed set of input data does not increase. 
     Exact value of α k  can be chosen from several experiments on small data. Usually first iterations should take α&#39; close to the α and when a local maximum is approached should take α&#39; close to zero. 
     FIG. 7 illustrates several iterative steps. Block 701 denotes a total area defined by constrained equations. Block 702 denote the started point. Block 703 denote the updated parameter obtained via standard iteration (without constrains). The interval between points 702 and 703 denotes a set of points at which the likelihood value of L() is not less than likelihood value at the initial point 702 The part of this interval (AB) belongs to the subdomain with &#34;good&#34; properties, therefore any point inside of this interval (e.g. 704) provides a point that guarantees that some &#34;good&#34; properties are satisfied. The Statement provides the method for finding the interval between 702 and 703 and the system of equations (9) can be used to find the subinterval AB with &#34;good&#34; properties. This point 703 lies outside the domain 701. The point 705 is chosen in this interval 703 for next iterative steps that is repeated similar the first one. All iterative steps provides points that converge to the local maximum 706. 
     Local maximum of some function L(x) in some manifold M is a point x such that in some small area U that includes this point x the value of the function L(x) at the point x is the largest in comparison with all other values L(x) at points x in the area U. It is usually impossible to find the &#34;global&#34; maximum--i.e. the point at which the likelihood function L(x) has the largest value over all manifold M. Usually one can try to find the &#34;local&#34; maximum--when the function is largest in some small area. This is done by using iterative methods. 
     Referring now to FIG. 8, there is schematically illustrated &#34;good&#34; features, a constrained manifold, and a feasible point. Block 800 comprises a decoder that decodes speech input (block 805) that consists of sentences 1, 2, . . . from block 804. The decoder 800 was trained by a training block 802 that chose some point (e.g., A) in a space of parameters 801 (space K). This space of parameters K of the decoder can be a set of means and covariance of Gaussian distributions such as those described in FIG. 3 at block 302. 
     Block 806 denotes correctly decoded sentences. That is, sentences that were decoded correctly when the decoder 800 was controlled by a parameter A (point A in a domain K), and decoded sentences with acoustic input from 805. These correctly decoded sentences give rise to set of likelihood inequalities. These inequalities define sub-domain T on the 801. Since the point A satisfies these inequalities, it belongs to the domain T and therefore is a feasible point on the domain (the feasible point is a mathematical notion that denotes any point that satisfies a set of inequalities in question). It is desirable to preserve in further training &#34;good&#34; properties--namely that sentences in block 806 decoded correctly for given acoustic input 805. 
     Since training may choose a new point in a statistical parameter space K (block 801, point B), in order to preserve above &#34;good&#34; property, one can request that all new points in a statistical parameter space should belong to domain T. If the domain T, then we are guaranteed that the decoder with a new value of parameters (corresponding this point B) will decode correctly the sentences from block 806 given acoustic input 805. The example of iterative training procedure that requires that all new points belong some sub-domain are given in FIG. 7. This sub-domain A is an example of constrained manifold (that was obtained via constrains that correspond to likelihood inequalities in block 803. 
     While the invention has been described in terms of a single preferred embodiment, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the appended claims.