Abstract:
In automatic speech recognition, confusion easily arises between phonetically similar words (for example, the German words &#34;zwei&#34; and &#34;drei&#34;) in the case of previous recognition systems. Confusion of words which differ only in a single phoneme (for example, German phonemes &#34;dem&#34; and &#34;den&#34;) occurs particularly easily with these recognition systems. In order to solve this problem, a method for recognizing patterns in time-variant measurement signals is specified which permits an improved discrimination between such signals by reclassifying in pairs. This method combines the Viterbi decoding algorithm with the method of hidden Markov models, the discrimination-relevant features being examined separately in a second step after the main classification. In this case, different components of feature vectors are weighted differently, it being the case that by contrast with known approaches these weightings are performed in a theoretically based way. The method is suitable, inter alia, for improving speech-recognizing systems.

Description:
BACKGROUND OF THE INVENTION 
     The problem arises in various fields of pattern recognition of having to make use of multidimensional feature vectors whose individual components, the features, are relevant in different ways in the case of different patterns to be recognized. This situation occurs, in particular, in automatic speech recognition, in which when previous recognition systems are used it is easy for phonetically similar words, (for example, German words &#34;zwei&#34; and &#34;drei&#34;) to be confused. It is particularly easy when using known recognition systems to confuse words which differ only in a single phoneme (for example, German phonemes &#34;dem&#34; and &#34;den&#34;). This problem becomes still more acute in the case of speaker-independent recognition of speech which is carried over telephone lines, because due to the reduced transmission bandwidth of 3.4 kHz speech-relevant frequency ranges are lost (for example, The sounds /s/ and /f/ can no longer be distinguished over the telephone). 
     Some of these known recognition systems are based on a direct pattern comparison of stored reference words and the actually spoken word, with account being taken of temporal fluctuations in rate of speech. These fluctuations are taken into account with the aid of dynamic programming, for example. Moore has proposed an approach for such recognition systems (R. K. Moore, M. J. Russel, M. J. Tomlinson, &#34;The discriminative network: A mechanism for focusing recognition in whole word pattern matching&#34;, IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 1041-1044, Boston, 1983, ICASSP), which automatically finds the discrimination-relevant parts of words and weights these more strongly by comparison with the other parts. A disadvantage of this method is that the automatic search of discrimination-relevant parts can be affected by errors in the case of confusable word pairs. Discrimination-relevant word parts are not always found, or word parts are wrongly regarded as discrimination-relevant. This problem also cannot be solved in principle using the method of dynamic programming alone. 
     SUMMARY OF THE INVENTION 
     In other fields of signal processing and pattern recognition, very similar problems occur as in the field of speech recognition. It is therefore the object of the invention to specify a method for recognizing patterns in time-variant measurement signals, by means of which the frequency of the confusion of similar feature vectors can be substantially reduced. This object is achieved with the aid of a method for recognizing patterns in time-variant measurement signals by classifying a temporal sequence of pattern vectors and by reclassification in pairs. 
     In this method, the sequence of feature vectors which is to be classified is segmented with the aid of a Viterbi decoding algorithm by comparing this sequence to be classified with a set of hidden Markov models. For this purpose, there is calculated for each hidden Markov model a total emission probability for the generation of the sequence to be classified by this hidden Markov model. Subsequently, an optimum assignment path from feature vectors to states of the hidden Markov models is determined by backtracking. 
     A discriminating comparison of the assignments is carried out for selected or all pairs of hidden Markov models by calculating modified total emission probabilities for each hidden Markov model of a pair on the assumption that the respective other hidden Markov model of the same pair competes with the hidden Markov model under review, and by determining the respective more probable hidden Markov model of a pair. Thereafter, the hidden Markov model with the largest total emission probability is selected from among all the pairs under review. 
     The method has the advantage that a pattern to be classified is compared not with a reference pattern but with a statistical distribution function of many reference patterns. In this way, it is not a simple distance between two patterns to be recognized which is obtained, as is the case with dynamic programming, but a probability for the generation of a pattern by a hidden Markov model. The method of the hidden Markov models is comprehensively described in the article by L. R. Rabiner and W. H. Juang, &#34;An introduction to hidden Markov models&#34;, IEEE Transactions on Acoustics, Speech and Signal Processing, (1): 4-16, Jan. 1986. By contrast with the method of Moore, no use is made of heuristically calculated weightings in the method present here; rather, use is made of weightings based on information theory. These weightings represent recognition rate,.; which are estimated with the aid of the distribution density functions on which the hidden Markov models are based. In this case, a weighting of 1.0 signifies a one hundred percent estimated recognition rate, that is to say the recognition is absolutely certain at this instant of analysis, while a weighting of 0 signifies that no statement can be made on the pattern to be classified. 
     In the method present here, it is not the emission probabilities of feature vectors which are weighted, but emission probabilities of individual components of feature vectors. As a result, a different weighting of the relevance of individual feature vector components is possible, so that the influence of individual components on the recognition performance can be selectively influenced precisely in the case of the use of multi-dimensional feature spaces. 
     Advantageous developments of the invention are as follows. 
     The total emission probability for generating the sequence to be classified by a hidden Markov model is calculated by calculating for all feature vectors of the sequence to be classified and for all states of the hidden Markov model a local logarithmic emission probability for generating the respective feature vector by the respective state. An accumulated logarithmic emission probability is calculated for each state as a sum of its local logarithmic emission probability and the accumulated logarithmic emission probability of its best possible predecessor state, the best possible predecessor state being logged. 
     The discriminating comparison of the assignments of two hidden Markov models is carried out by calculating for all feature vectors of the temporal sequence a local logarithmic modified emission probability for generating the respective feature vector by the corresponding state of the respective hidden Markov model by adding these local logarithmic modified emission probabilities recursively along the already calculated assignment path to an accumulated logarithmic modified emission probability. The modified local emission probability for generating a feature vector by a state of a hidden Markov model is calculated by calculating a logarithmic emission probability for each component of this feature vector and multiplying it by a weighting. These weighted logarithmic emission probabilities are summed over all components of this feature vector. The weighting of a component of a feature vector is in this case a measure of the reliability of this component on the assumption that only two specific states of a hidden Markov model are to be compared with one another. The weightings are determined with the aid of a statistic quality measure for the reliability of a feature vector component or a training method. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The features of the present invention which are believed to be novel, are set forth with particularity in the appended claims. The invention, together with further objects and advantages, may best be understood by reference to the following description taken in conjunction with the accompanying drawings, in the several Figures of which like reference numerals identify like elements, and in which: 
     FIG. 1 shows state paths for models of the German words &#34;drei&#34; and &#34;zwei&#34;. 
     FIG. 2 shows a diagram for generating new set hypotheses in the case of connected speech. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The invention is described in more detail below with the aid of a preferred exemplary embodiment and of the figures. 
     Speech recognition is selected in this case as a special application area, in order to be able to explain the invention in more concrete and thus comprehensible form. However, in principle the invention can be applied beyond the field of speech recognition in the entire domain of pattern recognition in time-variant measurement signals. 
     The method is based on a main classification with the aid of a Viterbi decoding algorithm, which is followed by a discriminating reclassification by means of which the classification problem is reduced to the comparison of pairs of phonemes by weighting of feature vector components. In this case, different feature vector components are differently weighted in accordance with their capacity to discriminate phoneme pairs. It emerged in experiments that the speaker-independent recognition rate for the German language could be improved from 90 to 96%. In the case of the use a larger training data record and well trained word models, the recognition performance can be further increased. 
     The invention is based on the hidden Markov models, already presented, for phonemes and extends the recognition process by a reclassification in which the discrimination-relevant word parts or phonemes are examined separately in a second step after the main classification. The basic method is represented in a pseudo-code representation following the description. The total method consists of two parts, a main classification with the aid of the Viterbi decoding algorithm and a following reclassification by means of a comparison in pairs of hidden Markov models. In the course of the Viterbi decoding algorithm, total emission probabilities for hidden Markov models are calculated and the best assignment path from feature vectors to states of hidden Markov models is found with the aid of a backtracking method. In a variant of the method,, the hidden Markov models are subsequently sorted in accordance with their total emission probability. Suitably selected pairs, or all pairs of hidden Markov models are examined in the reclassification step by carrying out for each of these pairs a discriminating comparison of their assignments. The pairs of hidden Markov models are typically selected in accordance with values of their total emission probability. The discriminating comparison of the assignments of hidden Markov models to feature vectors is performed by calculating modified total emission probabilities for each hidden Markov model of a pair on the assumption that in each case the other hidden Markov model of the same pair competes with the hidden Markov model under review, and by determining the respectively more probable hidden Markov model of a pair. Of all pairs under review, the hidden Markov model with the highest total emission probability is selected. This selected hidden Markov model with the highest total emission probability corresponds to the recognized pattern, in the example of speech recognition to the word to be recognized. 
     The total emission probabilities for instance the generation of the sequence to be classified by means of a specific hidden Markov model are calculated by calculating for all feature vectors of the sequence to be classified and for all the states of the hidden Markov model a local logarithmized emission probability for the generation of the respective feature vector by the respective state, and by calculating an accumulated logarithmic emission probability for each state as sum of its local logarithmized emission probability and the accumulated logarithmic emission probability of its best possible predecessor state, the best possible predecessor state being logged. 
     The discriminating comparison of the assignments of two hidden Markov models is preferably carried out by calculating for all feature vectors of the temporal sequence a local logarithmic modified emission probability for the generation of the respective feature vector by the corresponding state of the respective hidden Markov model, and by adding these local logarithmic modified emission probabilities recursively along the already calculated assignment path to an accumulated logarithmic modified emission probability. 
     The modified logarithmic emission probability of generating a feature vector by a state of a hidden Markov model is calculated by calculating a logarithmic emission probability for each component of this feature vector and multiplying it by a weighting, and by adding these weighted logarithmic emission probabilities over all the components of this feature vector. In this process, the weighting of a component of a feature vector is a measure of the reliability of this component on the assumption that only two specific states of a hidden Markov model are to be compared with one another. 
     In a variant method, the weightings are determined with the aid of a statistical quality measure for the reliability of a feature vector component. In another variant method, the weightings are determined in a separate training method. 
     In the main classification step, use is made of methods known from the literature. In the reclassification step, the discrimination-relevant word parts are found and weighted in accordance with their discrimination capacity. In a simple transfer of the method of Moore to the hidden Markov models, the probabilities of the discrimination-relevant phonemes would be multiplied by a heuristically calculated weighting. In the present invention, by contrast, use is made of theoretically based weightings. These represent the recognition rates estimated with the aid of the distribution density functions on which the models are based: that is to say a weighting of 1 signifies a one hundred percent estimated recognition rate, while a weighting of 0 signifies a random recognition rate. 
     Moreover, it is not the emission probabilities of the feature vectors which are weighted, but the proportions of each individual feature vector component. This results in balancing the effect that the influence of individual components recedes too strongly into the background because of the growth in the number of components of newer recognition systems. If an /s/ is to be distinguished from a speech pause, it is immediately clear that the signal energy is a very important feature component, whereas it can contribute nothing to distinguishing between, for example, the sounds /o/ and /u/. 
     In order to estimate the recognition rate, use is made of the so-called Kolmogorov distance, which in the case of the distinction of only two competitors even represents the exact estimate. In the case of two classes, the error probability can be specified at once (K. Fukunaga, &#34;Introduction to statistical pattern recognition&#34;, Academic Press, New York, 1972; J. Kittler, &#34;Mathematical methods of feature selection in pattern recognition&#34;, Internat. J. Man-Machine Studies, 7:603-637, 1975): 
     
         E.sup.* =1/2[1-∫dx p (x) |p(k.sub.1 |x)-p(k.sub.2 |x) |]                                  (1) 
    
     Here, x signifies the feature vector and p (k/x) the conditional probability for an occurrence of the class k given the presence of the feature vector x. k 1  and k 2  denote two classes or phonemes to be distinguished. The integral on the right-hand side of the equation can be interpreted as a measure of distance, in this case, it is the Kolmogorov distance: 
     
         J.sub.k =∫dx p(x) |P (k.sub.1 |x) -p(k.sub.2 |x)|                                    (2) 
    
     By contrast with its actual definition for vectors, this distance is modified in such a way that the proportions of individual components are calculated separately: 
     
         j.sub.k (x.sub.i)=∫dx.sub.i p(x.sub.i) |p(k.sub.1 |x.sub.i)-p(k.sub.2 |x.sub.i)| (3) 
    
     An essential task of the reclassification is to return the problem of speech recognition to the distinction of in each case two speech sounds. The use of the Viterbi decoding method in conjunction with a subsequent backtracking in the main classification ensures that a list of best word candidates is specified in the main classification, including an assignment of symbolic speech sounds to the temporal speech signal characteristic (segmentation). 
     In the first step of the reclassification, the first word candidate is compared with the second word candidate taking account of the discrimination-relevant phonemes and feature vector components. At each instant of the comparison, each hidden Markov model is in precisely one state of a phoneme. This is rendered clear with the aid of the example shown in FIG. 1. In the recognition of numeral words, the words &#34;drei&#34; and &#34;zwei&#34; are frequently confused. In almost all cases, the correct word is among the two best words, and the total generation probabilities are similar. The discrimination-relevant parts of these two words are relatively short with reference to their total length. It is assumed in FIG. 1 that the word &#34;zwei&#34; was actually spoken. FIG. 1 represents the time distortion paths or state paths, found in the recognition process by the Viterbi decoding, of the two best word candidates. The reference models consist here of context-dependent phoneme models. 
     Plotted on the abscissa is the unknown spoken word, while the phoneme models for the words to be compared are plotted on the ordinate. In order to increase the separability of these words, use is made of the following method for the reclassification: at every instant t a corresponding pair of phoneme models is considered which occur at this instant on the optimum state path. At the instant t 1 , the model &#34;s v  &#34; (end segment of /s/ with right context /v/) occurs in the word &#34;zwei&#34;, whereas it is the model &#34;d&#34; (middle segment of /d/) which occurs at the same time in the word &#34;drei&#34;. It is therefore necessary to perform an evaluation of the probability of these co-models under the boundary condition that these two classes alone can occur too. It is then possible to evaluate the components of the feature vector so as to achieve a maximum separability between these two classes. Similarly, at the instant t 2  the classes &#34;ai&#34; of the word model &#34;zwei&#34; are compared with &#34;ai&#34; of &#34;drei&#34;. The separability disappears in this case, since the same phoneme models are used. The newly evaluated probabilities--which are now composed from the weighted probability proportions of the vector components--are multiplied up over the two paths. The decision is now taken in favor of that word model having the highest probability. 
     The better model is then compared with the next candidate from the word list. This method is continued until a suitable termination criterion is fulfilled. The latter can be either the termination after a specific number of candidates, or the undershooting of a minimum probability of generation of the word candidate. 
     The method can be further extended in the case of connected speech. By strict analogy with the recognition method for individual words, it is possible to select a best hypothesis only from set hypotheses already available, but not to generate a new hypothesis. New set hypotheses can also be generated from those available by means of the extension. For this purpose, a wordwise decision is taken as to which word from the two set hypotheses is better. Thus, the recognized utterance is a combination of the best words. FIG. 2 shows this with the aid of an example. 
     The essential improvements by comparison with known methods are thus: 
     The return of speech recognition to the comparison of only in each case two speech sounds (phonemes). 
     Weighting of the emission probabilities of the speech sounds using weightings which were adapted to a specific pair of speech sounds. 
     Using distance measures (here, Kolmogorov distance) from probability theory as weighting factors. 
     Generating new set hypotheses with the aid of reclassification in the case of connected speech. 
     It is assumed for the purpose of calculating the emission probabilities that these probabilities are weighted mixtures of Gaussian probability density functions with diagonal covariance matrix. On the assumption that the contribution of the best fitting mode is much larger for a given feature vector x than that of all the other modes of the mixture, the influence of the latter can be neglected. Since the Viterbi algorithm is used for training and for recognition, the logarithmic probability can be described as follows: ##EQU1## N signifying the number of the vector components and c k  the weighting of the best mode k. If the variances are assumed to be constant, this expression is essentially the euclidian distance between the feature vector and the main vector of the best fitting mode. 
     In the reclassification proposed here, this distance is modified in order to improve the class discrimination. This is performed by applying specific weightings to each vector component in accordance with a capacity of the vector components to distinguish between two classes: ##EQU2## 
     For the purpose of optimum discrimination, the weightings w n  depend on the two classes to be separated. The first problem of classification therefore consists in reducing the problem of k classes to two classes. Of course, this is not possible in a single step, since the number of classes to be compared is much too large for such a mode of procedure in typical applications such as, for example, in speech recognition. For this reason, use is made of a reprocessing step which selects the best hypothesis from a list of hypotheses with the aid of a Viterbi decoder on the basis of hid,den Markov models. The Viterbi decoder must perform backtracking in this case, since the best paths of each hypothesis are required in the reprocessing step. The reduction to two classes is accomplished by comparing two hypotheses in pairs. In the example of speech recognition, each temporal subsequence consists of a pair of competing phonemes which have been determined by the preceding backtracking step. The emission probabilities of these two phonemes are calculated anew taking account of the distinguishing power of each feature component in this special case. The weighted emission probabilities are multiplied along the corresponding Viterbi paths, a modified total emission probability for the sentence hypothesis being calculated. After the better hypothesis has been selected, it is compared with the following candidates of the list of hypotheses. This procedure is continued until a prescribed number of hypotheses is reached. 
     The main advantage of integrating a distinguishing procedure into the recognition process consists in the capacity for a very accurate and subtle distinction between phonemes without a high outlay on computation. The extra outlay bound up with the proposed method is relatively low by comparison with the total recognition time, since only the probabilities along the Viterbi path need to be calculated anew. 
     A further task consists in determining the weightings w n  for weighting the feature vector components. The weightings are calculated as statistical or information-theoretical separability measures for the use in the method proposed here. By contrast, heuristic weightings of the features are known from known approaches. One possibility consists in using a modified transinformation measure. The original definition for the transinformation is given by the expression ##EQU3## This is a very general measure for the quality of distributions of multidimensional random variables arid has all the necessary properties of a distance measure. It is monotonic: between two extreme values: the measure vanishes for the case of no separation between the classes and assumes the value 1 in the case of a complete, error-free separation. For a use in the discriminating reprocessing step proposed here, the definition advanced above must be modified, since it has to be split in accordance with feature vector components. Since only pairs of classes are compared with one another in the reprocessing step, it is also necessary in the method present here for the transinformation to be calculated only taking account of pairs of classes. This produces a three-dimensional matrix whose elements are given as follows: ##EQU4## k 1  and k 2  enumerating the classes to be compared, and x n  representing a component of a feature vector. In the proposed reclassification step, the eigenvalues of this matrix for the weighting represented in formula 5 are selected for each comparison in pairs, specifically w n  =j T  (k 1 , k 2 , n) for the comparison of classes k 1  and k 2 . 
     Since these values still remain quite difficult to calculate, a different distance measure was used as a trial in experiments. The Kolmogorov distance (2) is a measure of the expected recognition mark for given classes and feature distributions. By analogy with the transformation measure, this must be split into a three-dimensional matrix J K  having the elements: 
     
         j.sub.K (k.sub.1,k.sub.2,n)=∫dx.sub.n p(x.sub.n) |p(k.sub.1 |x.sub.n)-p (k.sub.2 |x.sub.n)|(8) 
    
     Application to Individual Word Recognition 
     The individual word recognition is based on context-dependent phoneme models. These phoneme models consist of three parts or segments which each consist of two states of which each has an emission probability. The first and the last part are context-dependent. Only the middle segment is not dependent on the context, since this segment is assumed to be stationary. The assumption is important as basis for a robust training using limited training data. The emission probabilities of the middle segments are linked via different words, thus rendering a good segmentation possible in training by means of the Viterbi method. Each word model consists of a sequence of suitable segment models in accordance with a transcription lexicon (K. Zunkler, &#34;An ISDN speech server based on speaker independent continuous hidden markov models&#34; in Proceedings of NATO-ASI, Springer-Verlag, July 1990). 
     The recognition process is now divided into two stages. In the first stage, use is made of a Viterbi decoding algorithm with backtracking. The result of this first step is an evaluated list of word candidates together with their Viterbi paths. In the second step, the best two candidates are enlisted and their corresponding paths are compared. This comparison can be represented with the aid of FIG. 1. FIG. 1 shows the Viterbi paths for the models of the words &#34;drei&#34; and &#34;zwei&#34; with the aim of determining the corresponding model states for each time interval, which are compared by the discriminating reclassification step. t 1  is a time interval having different model states by contrast with, for example, the time interval t 2 , which makes no contribution to the weighted word probabilities. 
     There is exactly one model state in each word candidate for each time interval. In this way, only this pair of model states is compared for this specific time interval. A weighted probability is calculated for each candidate and summed up over the Viterbi path for all time intervals having different model states. After this comparison of the two candidates, the better of the two is compared with the next candidate of the list until a prescribed number of candidates have been compared. It is not necessary in this case to compare all candidates with one another. Experiments have shown that the recognition rate remains the same if instead of a rapid selection method in terms of pairs use is made of, for example, the K.O. method. 
     The technical terms used in this patent application are customary in the field of pattern recognition and in the field of speech recognition; their significance can be gathered from the following publications: 
     Thomas W. Parsons, &#34;Voice and Speech Processing&#34;, McGraw Hill 1987 K. Fukunaga, &#34;Introduction to statistical pattern recognition&#34;, Academic Press, New York 1972 
     L. R. Rabiner and B. H. Juang, &#34;An introduction to hidden markov models&#34;, IEEE Transactions on Acoustics, Speech and Signal Processing, (1): 4-16, Jan. 1986 
     J. Kittler, &#34;Mathematical methods of feature selection in pattern recognition&#34;, Internat. Journ. Man-Machine Studies, 7:603-637, 1975. 
     The invention is not limited to the particular details of the method depicted and other modifications and applications are contemplated. Certain other changes may be made in the above described method without departing from the true spirit and scope of the invention herein involved. It is intended, therefore, that the subject matter in the above depiction shall be interpreted as illustrative and not in a limiting sense.