Abstract:
A method for fast speech recognition of Mandarin words is accomplished by obtaining a first database which is a vocabulary of N Mandarin phrases. The vocabulary is described by an acoustic model which is formed by concatenating together word models. Each of the so concatenated word models is a concatenation of an initial model and a final model, wherein the initial model may be a null element, and both the initial and final model are represented by a probability model. A second database which contains initial models is determined. A preliminary logarithmic probability is subsequently calculated. A sub-set of vocabulary comprising acoustic models having the highest probability of occupance are established using the preliminary logarithmic probabilities. This facilitates recognizing phrases of Mandarin phrases which are then outputted to a user.

Description:
FIELD OF THE INVENTION 
     The present invention relates to a fast speech recognition method for Mandarin words. More specifically, the present invention relates to an improved speech recognition method for Mandarin/Chinese words which is based on hidden Markov models. 
     BACKGROUND OF THE INVENTION 
     With the advancement and increased popularity of computer technology, many speech recognition strategies have been proposed and tested. With all the development efforts, however, speech recognition is still considered as being one of the more difficult problems in artificial intelligence and computer science. 
     Voice input to computers presents a number of distinct advantages, most notably the provision of a natural, fast, hands-free, eyes-free, location-free input medium. However, there still exist many problems that prevent routine use of speech as an input device; these include relatively high cost, lack of real time response, speaker dependence, lack of robustness to variations such as noise, speech rate and loudness, lack of ability to handle non-grammatical speech, etc. Voice input via speech recognition provides a more attractive option for the Mandarin language (which is the official dialect of the Chinese language), because Mandarin is not an alphabet-based language (nor are other Chinese dialects), and it is substantially more cumbersome to enter the Mandarin characters than an alphabet-based language such as the English language. However, the problems mentioned above become more pronounced for Mandarin words because many of the &#34;initial sounds&#34; (equivalent to the consonants in the English language) often are either omitted by the speakers or are habitually rendered unintelligible by many Mandarin speakers. 
     SUMMARY OF THE INVENTION 
     The primary object of the present invention is to develop an improved speech recognition method for Mandarin words. More specifically, the primary object of the present invention is to develop a fast, preferably with real-time speed, speech recognition method for Mandarin/Chinese words which is based on hidden Markov models. 
     Several speech recognitions have been proposed which have exhibited impressive accuracy. These include the method of dynamic time warp of non-linear alignment by Itakura of NTT; the DRAGON system of Carnegie-Mellon University (stochastic modeling for all knowledge sources); the HEARSAY system of Carnegie-Mellon University (utilizing a blackboard structure through which all knowledge sources communicate); the HAPPY system of Carnegie-Mellon University (combining the advantages of DRAGON and HEARSAY and using network representation and beam search to improve the efficiency of the search); the Wilpon system of Bell Labs (using clustering techniques to create robust templates for speaker-independent isolated-word recognition); the FEATURE system of Carnegie-Mellon University (using a feature-based approach which led to a speaker-indepent system capable of recognizing isolated English letters with an accuracy over 90%, without grammar); the Tangora of IBM (using a natural very-large-vocabulary task); the BYBLOS system of BBN (applying context-dependent modeling of phonemes); and the Rabiner system of Bell Labs (using continuous hidden Markov model technology with multiple models and mixtures). Some of the advantages and constrains of these technologies have been discussed by Kai-Fu Lee. See &#34;Automatic Speech Recognition: The Development of the SHPHINX System,&#34; Kluwer Academic Publishers (1989). The content thereof is incorporated herein by reference. Lee also discussed in detail the method of using the hidden Markov model for speech recognition. 
     The hidden Markov model has been successfully utilized for speech recognition of Mandarin words. However, most of the prior art studies have been conducted on relatively powerful computers, particularly mainframe computers. Direct use of the hidden Markov model for recognizing Mandarin words with a relatively large vocabulary on lower end computers, such as personal computers, has met difficulties because of the low computing speed. In the present invention, it was discovered that, when the hidden Markov model is utilized in a novel two-stage approach, excellent results, including high accuracy and fast speed, could be obtained. 
     The basic sound unit of the Mandarin language (typically described as a syllable) comprises an initial unit (equivalent to consonant) and a final unit (equivalent to vowel). A Mandarin words comprises a sequence of basic sound units. During speech recognition, the speech signal A is first represented by a sequence of characteristic vectors. For example, The speech signal &#34;A&#34; can be represented as A=X 1  X 2  . . . X t  . . . X T , wherein X t  is a characteristic vector (&#34;frame&#34;) and T is the signal length or the &#34;total frame number&#34; of the sound. 
     The hidden Markov model utilizes statistical expressions to describe speech signals. In the hidden Markov model, speech signals are described as being generated according a certain probability distribution. The probability distribution itself can be gradually changed as a function of time. In other words, a speech signal is represented as one probability distribution at one time (or stage), but can be changed to another probability distribution at another time. This stage is described as &#34;state&#34; in the hidden Markov model. Each state &#34;i&#34; corresponds to a signal generating probability distribution b i  (X t ), this is designated as the output observation probability. The transition from state &#34;i&#34; to state &#34;j&#34; is described by a state transition probability a ij . Thus a hidden Markov model is, in essence, a collection of states connected by transitions. Each transition carries two sets of probabilities: a state transition probability, which provides the probability of taking this transition, and an output observation probability, which defines the probability of emitting each output symbol from a finite alphabet given that a transition is taken. The details of the hidden Markov model are described in the treatise by L. R. Rabiner and B. H. Juang: &#34;An Introduction to Hidden Markov Models,&#34; IEEE ASSP Magazine (January 1986). The content thereof is incorporated herein by reference. Thus it will not be repeated here. 
     In the method disclosed in the present invention, a vocabulary consisting of N phrases is first established. This vocabulary is described as W={W 1 , W 2 , . . . W N ). The length of phrase W i  (i.e., the number of words constituting the phrase W i ) is described as |W i  |=l i . In the present invention W i  is described by an acoustic model M i , which is formed by concatenating word models of {C 1 , C 2 , C 3  . . . }. That is, M i  =C i1  C i2  . . . C i |W|i. Each word model C i  is a concatenation of an initial model m I   j  and a final model m F   k , i.e., C i  = m I   j  !m F   k . The model is bracketed, indicating that it may be omitted or rendered unintelligible by the speaker. In the present invention, both the initial and final models are presented by a hidden Markov model. The procedure for representing a sound model using hidden Markov model has been described in the same treatise by L. R. Rabiner et al as discussed above, and it will not be repeated here. 
     During the speech recognition, the input speech signal is designated as A, assuming A is the correct pronunciation of phrase W j , the task of speech recognition is to find W j  in the vocabulary W. In the present invention, a full search procedure is developed by which the probability of each acoustic model M i  (i=1, 2, . . . , N) in the vocabulary W to be the sound of A, i.e., Prob (A|M i ), i=1,2 . . . , N, is calculated. From these calculated probability values, the phrase W k  corresponding to maximum probability is found: 
     
         k=arg.sub.i Max(Prob)(A|M.sub.i)) 
    
     The input speech signal &#34;A&#34; is then recognized as W k . In these calculations, M i  (i=1, 2, . . . , N) is a from-left-to-right hidden Markov model with s states and A=X 1  X 2  . . . X t  . . . X T . The maximum probability of a signal via an optimum state (i.e., the maximum likelihood of a speech signal being represented by an hidden Markov accoustic model) can be calculated from the well-known Viterbi algorithm. The details of implementing Viterbi algorithm is described in the same treatise by L. R. Rabiner and B. H. Juang: &#34;An Introduction to Hidden Markov Models,&#34; IEEE ASSP Magazine (January 1986). Thus it will not be repeated. 
     The procedure described above is designated as a &#34;full search&#34; procedure. In this procedure, all the acoustic models will be compared with the input speech signal. This procedure becomes very time consuming when the size of the vocabulary becomes large. 
     In the present invention, a novel preliminary screening procedure based on two unique sets of models is developed which will be performed preceeding the full search procedure, and the full search procedure is performed based on a substantially reduced sub-set of the entire vocabulary. (In the present invention, the two sets of models collectively constitute a reference database associated with the preliminary screening procedure; this type of database, which contains mathematical models, should be distinguished from the more conventionally accepted definition of &#34;database&#34;, which typically stores standard sound signals and constitutes the &#34;vocabulary&#34; used in the present invention.) In this procedure, which is summarized as a flowchart in FIG. 1, the input speech signal is first segmented into l syllable segments, each segment contains an initial and a final sub-segment; however the initial sub-segment may be absent. This step can be summarized by the following equation: 
     
         A=( s.sup.1.sub.1 !s.sup.F.sub.I)( s.sup.I.sub.2 !s.sup.F.sub.2) . . . ( s.sup.I.sub.1 !s.sup.F.sub.1) 
    
     wherein A is the input speech signal, s I   i  (i=1, 2, . . . , l) is the ith initial syllable sub-segment, and s F   1  (i=1,2, . . . , l) is the ith final syllable sub-segment. The brackets enclosing the initial syllable sub-segment indicating that the initial syllable sub-segment may be missing. 
     As described earlier, in the present invention, each word model C i  is a concatenation of an initial model m I   j  and a final model m F   k , i.e., C i  = m I   j  !m F   k . Thus the preliminary screening procedure disclosed in the present invention involves a reference database, which comprises J initial models, m I   j  (j=1,2 . . . , J), and K final models m F   k  (k=1,2, . . , K). The next step is to compute log Prob (s I   i  |m I   j ) and log Prob (s F   i  |m F   k ), for all the sub-segments (i.e., i=1,2, . . . , l), and for all the initial and final models m I   j , m F   k  (i.e., j=1,2, . . . , J, and k=1,2, . . . , K, respectively). 
     In the present invention, each word W n  in W with length l is represented by an acoustic model M n  (= m I   j1  !m F   k1   m I   j2  !m F   k2  . . .  m I   jl  !m F   k1 ). The next step is to calculate a preliminary logarithmic probability log Prob (W n ) according to the following formula: ##EQU1## 
     For Mandarin words, it is possible that the input speech signal A may be segmented into other l&#39;s (i.e., other number of syllable segments). If this is the case, then a different l is selected and the above preliminary screening procedure is repeated until all the possible l&#39;s are exhausted. After all the log Prob(W n )&#39;s are calculated, the words with the top X values of log Prob(W n )&#39;s are selected and designated as W&#39; i , i=1,2, . . . X, which are represented by acoustic models M&#39; i , i=1,2, . . . X, respectively. These X words with the largest log Prob(W n ) are then subject to full search procedure as described above. However, a substantially reduced sub-set of the original vocabulary W&#39; (now with K phrases) will be searched, instead of the original vocabulary W (with N phrases). 
     During the full search procedure, the probabilities of A|M&#39; i  (i=1, 2, . . . X) are calculated. The input speech signal is then recognized as the word with the maximum probability. That is, during the full search step, A is recognized as W&#39; x , wherein 
     
         x=arg.sub.i Max(Prob(A|M&#39;.sub.i), i=1,2, . . . X 
    
    
    
     BRIEF DESCRIPTION OF THE DRAWING 
     The present invention will be described in detail with reference to the drawing showing the preferred embodiment of the present invention, wherein: 
     FIG. 1 is a schematic flowchart diagram illustrating the two-stage fast speech recognition process for Mandarin words disclosed in the present invention which utilizes hidden Markov models. 
     FIG. 2 illustrates the segmentations of the Chinese phrase  into 2, 3, and 4 frames. 
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
     The present invention discloses an improve speech recognition method for Mandarin words based on probability models. The method discloses in the present invention involves two different reference databases, both of which are based on hidden Markov models. The present invention also discloses a novel two-stage procedure, each stage utilizing one of the two reference databases, respectively, to provide a fast, with real-time or near-real-time performance, speech recognition method for Mandarin/Chinese words. 
     In the method disclosed in the present invention, prior to the execution of the speech recognition procedure, a vocabulary W consisting of N phrases is first established. This vocabulary is described as 
     
         W={W.sub.1,W.sub.2, . . . W.sub.N) 
    
     The length of a constituent phrase W i  (i can be 1 from N) in the vocabulary W is described as |W i  |=l i . In the Mandarin language, a phrase consists of one or more words, which constitute the basic unit. In the present invention, W i  is described by an acoustic model M i  which is formed by concatenating word models of {C 1 ,C 2 ,C 3  . . . }. That is, 
     
         M.sub.i =C.sub.i1 C.sub.i2 . . . C.sub.i|Wi| 
    
     Wherein |W i  | is the number of word models constituting the acoustic model M i . 
     In the present invention, each word model C i  is a concatenation of an initial model m I   j  and a final model m F   k , i.e., 
     
         C.sub.i = m.sup.I.sub.j !m.sup.F.sub.k 
    
     The initial model is bracketed, indicating that it may be missing (i.e., mathematically inaudible). In the present invention, both the initial and final models are presented by a hidden Markov model. The above procedure establishes the reference database which will be utilized in the speech recognition step of the present invention. 
     During the speech recognition, the input speech signal is designated as A. The task of speech recognition is to find W j  in the vocabulary W such that A is the correct pronunciation of phrase W j . 
     In the present invention, a novel two-step process is developed which utilizes the hidden Markov model for speech recognition of Mandarin words. Two reference databases are developed, one comprises the accoustic models of all the phrases contained in a vocabulary and other comprises only initial and final sound models. The two-step process disclosed in the present invention includes a preliminary screening procedure utilizing the database of initial and final sound models, and a subsequent fill search procedure utilizing a substantially reduced subset of the vocabulary database. FIG. 1 is a flowchart showing the steps involved in the preliminary screening procedure. In this procedure, the input speech signal is first segmented into l syllable segments, each segment containing an initial and a final sub-segment; however the initial sub-segment may be absent. This step can be summarized by the following equation: 
     
         A=( s.sup.I.sub.1 !s.sup.F.sub.1)( s.sup.I.sub.2 !s.sup.F.sub.2) . . . ( s.sup.I.sub.l !s.sup.F.sub.l) 
    
     wherein A is the input speech signal, s I   i  (i=1, 2, . . . , l) is the ith initial syllable sub-segment, and s F   1  (i=1, 2, . . . , l) is the ith final syllable sub-segment. The brackets enclosing the initial syllable sub-segment indicating that the initial syllable sub-segment may be missing. In this procedure, the segmentation into the initial and final sub-segments is again carried out using the Viterbi algorithm. However, the models used in the above described embodiment of the present invention involve two general initial and final models which have the same structure as the specific initial and final models, except that the distribution of output probability for each state is calculated by combing all the distributions of the corresponding states of the specific models. 
     As described earlier, in the present invention, each word model C i  is a concatenation of an initial model m I   j  and a final model m F   l  i.e., C i  = m I   j  !m F   k . Thus the first step of the present invention includes a reference database, which comprises J initial models, m I   j  (j=1,2, . . . , J), and K final models, m F   k  (k=1,2, . . . , K). The next step is to compute log Prob (s I   i  |m I   j ) and log Prob (s F   i  |m F   k ), for all the sub-segments (i.e., i=1, 2,. . . , l), and for all the initial and final models m I   j , m F   k  (i.e., j=1,2, . . . , J, and k=1, 2, . . . , K, respectively). 
     In the present invention, each word W n  in W with length l is represented by an acoustic model M n  (= m I   j1  !m F   k1   m I   j2  !m F   k2  . . .  m I   jl  !m F   kl ). The next step is to calculate a preliminary logarithmic probability log Prob (W n ) for the accoustic model M n , according to the following formula: ##EQU2## 
     For Mandarin language, it is possible that the input speech signal A may be segmented into other l&#39;s. If this is the case, then a different l is selected and the above preliminary screening procedure is repeated, as shown in FIG. 1, until all the possible l&#39;s are exhausted. FIG. 2 illustrates the segmentations of the Chinese phrase  into 2, 3, and 4 syllable segments, or frames. 
     After all the logProb(W n )&#39;s are calculated, the words within the top Xth log Prob(W n )&#39;s are selected and designated as W&#39; i , i=1,2, . . . X, which are represented by acoustic models M&#39; i , i=1,2, . . . X, respectively. These X words with the largest values of log Prob(W n ) are then subject to second step full search procedure of the two-step process of the present invention. 
     During the full search procedure, the probabilities of A|M&#39; i  (i=1,2, . . . K) are calculated. The input speech signal is then recognized as the word with the maximum probability. That is, during the full search step, A is recognized as W&#39; x , wherein 
     
         x=arg.sub.i Max(Prob(A|M&#39;.sub.i), i=1,2, . . . X 
    
     A full search procedure may be conducted without the preliminary screening step described above. In this approach, which can be considered as a conventional approach, the probability of each acoustic model M i  (i=1, 2, . . . , N) in the vocabulary W to be the sound of A, i.e., Prob (A|M i ), i=1,2, . . . , N, is calculated. From these calculated probability values, the phrase W k  corresponding to maximum probability is found: 
     
         k=arg.sub.i Max(Prob(A|M.sub.i)),i=1,2, . . . N 
    
     A is then recognized as W k . 
     The present invention will now be described more specifically with reference to the following examples. It is to be noted that the following descriptions of examples, including the preferred embodiment of this invention, are presented herein for purposes of illustration and description, and are not intended to be exhaustive or to limit the invention to the precise form disclosed. 
     Reference Databases: 
     A reference database containing 21 initial units and 36 final units of Mandarin language was established, each unit was characterized by a 3-state hidden Markov model with left-to-right structure where each state was described by continuous probabilities of 4-mixture Gaussian distributions. The parameters in all the initial and final units were estimated using the well-known Baum-Welch procedure. Details of the Baum-Welch procedure have been described in the same treatise by L. R. Rabiner and B. H. Juang: &#34;An Introduction to Hidden Markov Models,&#34; IEEE ASSP Magazine (January 1986). Thus it will not be repeated. 
     The general initial model I and final model F used for segmenting the input speech signal is respectively combined by the 21 specific initial models and 36 specific final models as described above. The general models have the same structure (3-state, left-to-right) as the specific models. During the calculations, the output probability for each state i of the general initial model was designated as B I   i  (O i ), and that of the specific initial model was designated as b i   j  (O i ), where j (=1,2, . . . , or 21) is the index of the specific initial model. Likewise, the output probability for each state i of the general final model was designated as B F   i  (O i ), and that of the specific final model was designated as b -k   i  (O i ), where k (=1, 2, . . . , or 36) is the index of the specific final model. The values of B I   k  (O i ) and B F   i  (O i ) are calculated by combining the specific initial and final models, respectively according to the following formula: 
     
         B.sup.I.sub.i (O.sub.i)=Max.sub.j b.sub.i.sup.j (O.sub.i), j=1,2, . . . 21 
    
     
         B.sup.F.sub.i (O.sub.i)=Max.sub.k b.sup.-k.sub.i (O.sub.i), k=1,2, . . . 36 
    
     Since the transition probabilities was tested to exhibit little influence on the segmentation results, they were simply chosen from the transition probabilities of any one of the specific models. Source codes describing the calculational procedure are enclosed in the appendix. 
     Three Mandarin vocabularies containing 100, 480, and 945 Mandarin phrases, respectively, were also established. Each Mandarin phrase is a concatenation of one or more Mandarin words, and each Mandarin word is represented by a model C i , which is a concatenation of an initial model m I   j  and a final model m F   k , as described above. 
     Computation Times 
     A SUN workstation SPARC 10 was used in the speech recognition experiments. Table 1 compares the CPU times calculated using a full search (convention approach), and the two-stage process disclosed in the present invention. 
     
                       TABLE 1______________________________________          This InventionVocabulary Size (N)      Full Search                K = 10   K = 20 K = 30______________________________________945        0.096750  0.043752 0.045630                                0.046557480        0.072973  0.043605 0.044246                                0.045242100        0.051507  0.043605 0.043999                                0.045533______________________________________ 
    
     Table 1 shows that the CPU required for the present invention is substantially shorter than that required for the full search process, and is almost independent of the size of the vocabulary. Thus the method disclosed in the present invention is particularly useful for large Mandarin vocabularies. 
     Recognition Accuracy 
     In one study, 479 Mandrain phrases spoken by three male voices (M1, M2, and M3) were input and recognized using a 480-phrase reference database. Results are analyzed based on each individual male voice and are summarized in Tables 2-4 below. 
     
                       TABLE 2______________________________________M1        Number of Incorrect Recognitions                        Error Rate (%)______________________________________Full Search     52                 10.86This InventionX = 10    64                 13.36X = 20    63                 13.15X = 30    62                 12.94X = 40    60                 12.53X = 50    58                 12.11______________________________________ 
    
     
                       TABLE 3______________________________________M2        Number of Incorrect Recognitions                        Error Rate (%)______________________________________Full Search     11                 2.30This InventionX = 10    16                 3.34X = 20    15                 3.13X = 30    15                 3.13X = 40    14                 2.92X = 50    14                 2.92______________________________________ 
    
     
                       TABLE 4______________________________________M3        Number of Incorrect Recognitions                        Error Rate (%)______________________________________Full Search     50                 10.44This InventionX = 10    49                 10.23X = 20    47                 9.81X = 30    47                 9.81X = 40    48                 10.02X = 50    49                 10.23______________________________________ 
    
     In another study, 100 Mandrain phrases spoken by the same male voice were input and recognized using a 100-Mandrain phrase reference database. Results are analyzed and summarized in Table 5 below. 
     
                       TABLE 5______________________________________   Number of Incorrect Recognitions                    Error Rate (%)______________________________________Full Search     5                  5This InventionX = 10    6                  6X = 20    6                  6X = 30    6                  6______________________________________ 
    
     Tables 2-5 illustrate that the two-stage process disclosed in the present invention provides essentially the same accuracy as that obtained from full search. However, the present invention allows speech recongntion to be conducted at a much faster speed. It should be noted that, as it was discussed above, direct use of the hidden Markov model for Mandrain speech recognition would result in an unacceptably low speed on a PC when a large vocabulary was utilized. The present invention, which utilizes a novel two-step approach, greatly extended the applicability of the hidden Markov model for fast and accurate speech recognition of Mandrain words using commodity computers. 
     The foregoing description of the preferred embodiments of this invention has been presented for purposes of illustration and description. Obvious modifications or variations are possible in light of the above teaching. The embodiments were chosen and described to provide the best illustration of the principles of this invention and its practical application to thereby enable those skilled in the art to utilize the invention in various embodiments and with various modifications as are suited to the particular use contemplated. All such modifications and variations are within the scope of the present invention as determined by the appended claims when interpreted in accordance with the breadth to which they are fairly, legally, and equitably entitled. ##SPC1##