There has long been a desire to have machines capable of responding to human speech, such as machines capable of obeying human commands and machines capable of transcribing human dictation. Such machines would greatly increase the speed and ease with which people communicate with computers and with which they record and organize their words and thoughts.
Due to recent advances in computer technology and speech recognition algorithms, speech recognition machines have begun to appear in the past several decades, and have become increasingly more powerful and less expensive. For example, the assignee of the present application has publicly demonstrated speech recognition software which runs on popular personal computers and which requires little extra hardware. This system is capable of providing speaker dependent, discrete word recognition for vocabularies of up to two thousand words at any one time, and many of its features are described in U.S. patent application Ser. No. 797,249, entitled "Speech Recognition Apparatus and Method", which is assigned to the assignee of the present application, and which is incorporated herein by reference.
A major problem in speech recognition is that of reducing the tremendous amount of computation such recognition requires, so that recognition can be performed in a reasonable time by relatively inexpensive computer hardware. Since many speech recognition systems operate by comparing a given spoken utterance against each work in its vocabulary, and since each such comparison can require thousands of computer instructions, the amount of computation required to recognize an utterance tends to grow in proportion to the vocabularly size. Thus the problem of making speech recognition computationally efficient is more difficult in systems designed to recognize the large vocabularies necessary to make speech recognition useful for the trascription of normal speech.
The prior art has developed a variety of methods to reduce the computational demands required by large vocabularly recognition. One such prior art technique is that of "pruning". Generally speaking, pruning involves reducing the number of cases which a program considers, by eliminating from further consideration those cases which, for one reason or another, do not appear to warrant further computation.
For example, the system described in the above mentioned application Ser. No. 797,249 produces a score for each word in its active vocabulary after comparing that word against each successive frame of an utterance. This score corresponds to the liklihood that the frames received so far correspond to the given word. If the score for a given word is worse than a certain threshold, that word is removed, or pruned, from the active vocabulary and future frames are no longer compared against it. This technique greatly improves the computational efficiency, since it rapidly reduces the number of words against which successive frames of an utterance to be recognized have to be compared.
The above mentioned application Ser. No. 797,249 also uses another form of pruning, called prefiltering, to reduce computation. This prefiltering runs a superficial recognition against an entire vocabulary to quickly select those words which appear similar enough to the utterance to be recognized to warrant a more detailed comparison with that utterance.
In addition to pruning and prefiltering, the prior art has used lexical retrieval to reduce the number of vocabularly words against which an utterance has to be compared. In lexical retrieval information from the utterance to be recognized generates a group of words against which recognition is to be performed, and this is done without making a superficial comparison against each vocabulary word, as is disclosed in the above mentioned application Ser. No. 797,249. For example, the HEARSAY speech recognition program developed at Carnegie-Mellon University in the early 1970's has acoustic models of most syllables which occur in English. When an utterance to be recognized was received, it was compared against these syllable models, producing a list of syllables considered likely to occur in the word to be recognized. Then words containing those syllables were then chosen for comparison against the utterance to be recognized.
Speech recognition programs written at Bolt, Beranek, and Newman, have performed lexical retrieval by mapping all vocabulary words onto a common tree, in which branches correspond to phonemes. The root of the tree is the start of the word. Its first branches represent all the different initial phonemes contained in the vocabularly words. The second level branches connected to a given first level branch represent all the second phonemes in the vocabularly words which folow the first phoneme represented by the given first level branch. This is continued for multiple levels, so that words which start with a similar string of phonemes share a common initial path in the tree. When a word to be recognized is received, its successive parts are compared with a set of phoneme models, and the scores resulting from those comparisons are used to select those parts of the tree which probably correspond to the word to be recognized. The vocabularly words associated with those parts of the tree are then compared in greater detail against the word to be recognized.
Another method of reducing the computation required for speech recognition involves using common models to represent similar sounds occurring in different words. This saves computation, since it allows one comparison between a portion of an utterance to be recognized and a given common model to replace multiple comparisons between that utterance portion and the plurality of common sounds represented by the given common model. This general method is used in both the HEARSAY and Bolt, Beranek, and Newman's lexical retrieval methods described above. The HEARSAY program used syllable models, and the BB&N program used phonemes, to represent common sounds occurring in more than one word.
One way of developing common models to represent similar sounds occurring in more than one word is that of clustering. A preferred form of clustering involves grouping together, and creating a common probabilistic model to represent, similar sound models. A form of such clustering is described in detail in U.S. patent application Ser. No. 862,275, entitled "A Method for Representing Word Models for Use In Speech Recognition", filed by Gillick et al. on May 12th, 1986, which application is assigned to the assignee of the present application, and is incorporated herein by reference. This application Ser. No. 862,275 discloses the derivation of word models comprised of a sequence of nodes, each of which is a spectral probability distribution model representing the sound occurring in corresponding portions of multiple utterance of a given word. The nodes from many words are then clustered, or divided, into groups of nodes that have similar probability distributions. A common probability distribution model is calculated to represent all the nodes placed in a given cluster, and then that cluster model is used in place of its corresponding nodes in all word models. This greatly reduces the amount of memory required to represent a large vocabulary, since a relatively small number of cluster models can be used to spell a large number of words.
Another form of clustering has been described in a paper entitled "Modified K-Means Clustering Algorithm for Use in Isolated Word Recognition", by Wilpon et al., published in IEEE TRANSACTIONS ON ACOUSTICS, SPEECH, and SIGNAL PROCESSING, Volume ASSP-33, NO. 3, June 1985. The clustering disclosed in this paper clustered together utterances of the same word made by different speakers, to produce a relatively small number of cluster models to represent all the different ways that a given word can be said by different people. The cluster models each contained a succession of sub-models representing the sound of the word at successive points in time.
Although the above described methods do reduce the computation required for speech recognition, there still is a need for further computation reductions if present day personal computers are to recognize large vocabularies, such as twenty-thousand words or more, without the addition of expensive computational hardware.