Reduction of search space in speech recognition using phone boundaries and phone ranking

• US 5,729,656 A
• Filed: 11/30/1994
• Issued: 03/17/1998
• Est. Priority Date: 11/30/1994
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Nahamoo, David, Padmanabhan, Mukund
• Primary Examiner(s): MacDonald, Allen R.
• Assistant Examiner(s): Mattson, Robert
• Application Number:
  US08/347,013
• Time in Patent Office: 1,203 Days
• Field of Search: 381/41, 381/42, 381/43, 395/2.6, 395/2.62-2.66, 395/2.4
• US Class Current: 704/254
• CPC Class Codes: G10L 15/04 Segmentation; Word boundary detection
• CPC Class Codes: G10L 15/142 Hidden Markov Models [HMMs]
• CPC Class Codes: G10L 2015/025 Phonemes, fenemes or fenones being the recognition units
• CPC Class Codes: G10L 2015/085 Methods for reducing search complexity, pruning

Abstract

A method for estimating the probability of phone boundaries and the accuracy of the acoustic modelling in reducing a search-space in a speech recognition system. The accuracy of the acoustic modelling is quantified by the rank of the correct phone. The system includes a microphone for converting an utterance into an electrical signal, which is processed by an acoustic processor and label match which finds the best-matched acoustic label prototype. A probability distribution on phone boundaries is produced for every time frame using a first decision tree. These probabilities are compared to a threshold and some time frames are identified as boundaries between phones. An acoustic score is computed for all phones between every given pair of hypothesized boundaries, and the phones are ranked on the basis of this score. A second decision tree is traversed for every time frame to obtain the worst case rank of the correct phone at that time, and a short list of allowed phones is made for every time frame. A fast acoustic word match processor matches the label string from the acoustic processor to produce an utterance signal which includes at least one word. From recognition candidates produced by the fast acoustic match and the language model, the detailed acoustic match matches the label string from the acoustic processor against acoustic word models and outputs a word string corresponding to an utterance.

Claims

1. A method of recognizing speech, comprising the steps of:

a) inputting a plurality of words of training data;

b) training a plurality of first binary decision trees to ask a maximally informative question at each node based upon contextual information in the training data, wherein each first binary decision tree corresponds to a different time in a sequence of the training data;

c) traversing one of the first binary decision trees for every time frame of an input sequence of speech to determine a probability distribution for every time frame, the probability distribution being the probability that a node is a phone boundary;

d) comparing the probabilities associated with the time frames with a threshold for identifying some time frames as boundaries between phones;

e) providing an acoustic score for all phones between every given pair of boundaries to generate a second binary decision tree of such acoustic scores;

f) traversing the second binary decision tree of such acoustic scores for all phones to rank the phones from best to worst on the basis of this score; and

g) outputting a recognition result in response to the score.

2. A method of recognizing speech, comprising the steps of:

inputting a plurality of words of training data;

b) training a plurality of binary first decision trees to ask a maximally informative question at each node based upon contextual information in the training data, wherein each binary first decision tree corresponds to a different time in a sequence of the training data;

c) traversing one of the decision trees for every time frame of an input sequence of speech to determine a probability distribution for every time frame, the probability distribution being the probability that a node is a phone boundary;

d) comparing the probabilities associated with the time frames with a threshold for identifying some time frames as boundaries between phones;

e) providing an acoustic score for all phones between every given pair of boundaries;

f) ranking the phones on the basis of this score;

outputting a recognition result in response to the score;

h) traversing one or more of a second set of decision trees for every time frame on an input sequence of speech to determine a second probability distribution, the probability distribution being a distribution over all possible ranks that the correct phone can take for obtaining a worst case rank of a correctly recognized phone by choosing the worst case rank as the class value at which the cumulative probability distribution of the classes exceeds a specified threshold;

i) assigning as the absolute worst case rank of the worst case ranks between any two adjacent phone boundaries the worst case rank of the correctly recognized phone between the phone boundaries;

j) discarding all phones whose rank is worse than this absolute worst case rank in the current segment;

k) making a short list of phones for the segment; and

l) outputting a recognition result in response to the short list of the recognition result being a short list of words.

3. A method of recognizing speech, comprising the steps of:

a) inputting a plurality of words of training data;

b) training a plurality of binary first decision trees to ask a maximally informative question at each node based upon contextual information in the training data, wherein each binary first decision tree corresponds to a different time in a sequence of the training data;

c) traversing one of the decision trees for every time frame of an input sequence of speech to determine a probability distribution for every time frame, the probability distribution being the probability that a node is a phone boundary;

d) comparing the probabilities associated with the time frames with a threshold for identifying some time frames as boundaries between phones;

e) providing an acoustic score for all phones between every given pair of boundaries;

f) ranking the phones on the basis of this score;

outputting a recognition result in response to the score;

h) traversing one or more of a second set of decision trees for every time frame on an input sequence of speech to determine a second probability distribution, the probability distribution being a distribution over all possible ranks that a phone can take for obtaining a worst case rank of a correctly recognized phone by choosing the worst case rank as the class value at which the cumulative probability distribution of the classes exceeds a specified threshold;

i) assigning as the absolute worst case rank of the worst case ranks between any two adjacent phone boundaries the worst case rank of the correctly recognized phone between the phone boundaries;

j) discarding all phone boundaries whose rank is worse than this absolute worst case rank in the current segment;

k) making a short list of phones for the segment;

l) comparing constituent phones of a word in a vocabulary to see if the word lies in the short list and making up a short list of words; and

m) outputting a recognition result by comparing the words of the short list with a language model to determine the most probable word match for the input sequence of speech.

4. A method for recognizing speech, comprising the steps of:

a) entering a string of utterances constituting training data;

b) converting the utterances of the training data to electrical signals;

c) representing the electrical signal of the training data as prototype quantized feature vectors, one feature vector representing a given time frame;

d) assigning to each prototype feature vector a class label associated with the prototype quantized feature vector;

e) forming a plurality of binary decision trees for different times in the training data, each tree having a root node and a plurality of child nodes, comprising the steps of;

i. creating a set of training records comprising 2K+1 predictors, l^k, and one predicted class, p, where the 2K+1 predictors are feature vector labels at 2K+1 consecutive times t-K, . . . , t, . . . , t+K, and the predicted class is a binary record indicator whether time t is associated with a phone boundary in the case of the first decision tree or is associated with the correct phone in the case of the second decision tree;

ii. computing the estimated joint distribution of predictors l^k and phone p for 2K+1 predictors using the training data, wherein the predictors are feature vector labels at times t-K, . . . , t, . . . , t+K and p is the phone at time t;

iii. storing the estimated joint distribution of l^k and p and a corresponding distribution for each predictor l^k at the root node;

iv. computing the best partitioning of the values that predictor l^k can take for each l^k to minimize phone uncertainty at each node; and

v. choosing the predictor l^k whose partitioning results in the lowest uncertainty and partitioning the training data into two child nodes based on the computed-based partitioning l^k, each child node being assigned a class distribution based on the training data at the child node;

f) repeating for each child node if the amount of training data at the child node is greater than a threshold;

g) inputting an utterance to be recognized;

h) converting the utterance into an electrical signal;

i) representing the electrical signal as a series of quantized feature vectors;

j) matching the series of quantized feature vectors against the stored prototype feature vectors to determine a closest match and assigning an input label to each of the series of feature vectors corresponding to the label of the closest matching prototype feature vector;

k) traversing one of the decision trees for every time frame of an input sequence of speech to determine a probability distribution for every time frame, the probability distribution being the probability that a node is a phone boundary;

l) comparing the probabilities associated with the time frames with a threshold for identifying some time frames as boundaries between phones;

m) providing an acoustic score for all phones between every given pair of boundaries;

n) ranking the phones on the basis of this score; and

o) outputting a recognition result in response to the score.

5. The method of claim 4 further including the steps of:

traversing one or more of a second set of decision trees for every time frame on an input sequence of speech to determine a second probability distribution, the probability distribution being a distribution over all possible ranks that a phone can take for obtaining a worst case rank of a correctly recognized phone by choosing the worst case rank as the class value at which the cumulative probability distribution of the classes exceeds a specified threshold;

assigning as the absolute worst case rank of the worst case ranks between any two adjacent phone boundaries the worst case rank of the correctly recognized phone between the phone boundaries;

discarding all phone boundaries whose rank is worse than this absolute worst case rank in the current segment;

making a short list for the segment; and

outputting a recognition result in response to the short list.

6. An apparatus for recognizing speech, comprising:

a) means for inputting a plurality of words of training data;

b) means for training a plurality of first binary decision trees to ask a maximally informative question at each node based upon contextual information in the training data, wherein each first binary decision tree corresponds to a different time in a sequence of the training data;

c) means for traversing one of the first binary decision trees for every time frame of an input sequence of speech to determine a probability distribution for every time frame, the probability distribution being the probability that a node is a phone boundary;

d) means for comparing the probabilities associated with the time frames with a threshold for identifying some time frames as boundaries between phones;

e) means for providing an acoustic score for all phones between every given pair of boundaries to generate a second binary decision tree of such acoustic scores;

f) means for traversing the second binary decision tree of such acoustic scores for all phones to rank the phones from best to worst on the basis of this score; and

g) means for outputting a recognition result in response to the score.

7. An apparatus for recognizing speech, comprising:

a) means for inputting a plurality of words of training data;

b) means for training a plurality of binary first decision trees to ask a maximally informative question at each node based upon contextual information in the training data, wherein each binary first decision tree corresponds to a different time in a sequence of the training data;

c) means for traversing one of the decision trees for every time frame of an input sequence of speech to determine a probability distribution for every time frame, the probability distribution being the probability that a node is a phone boundary;

d) means for comparing the probabilities associated with the time frames with a threshold for identifying some time frames as boundaries between phones;

e) means for providing an acoustic score for all phones between every given pair of boundaries;

means for ranking the phones on the basis of this score; and

means for outputting a recognition result in response to the score;

h) means for traversing one or more of a second set of decision trees for every time frame on an input sequence of speech to determine a second probability distribution, the probability distribution being a distribution over all possible ranks that the correct phone can take for obtaining a worst case rank of a correctly recognized phone by choosing the worst case rank as the class value at which the cumulative probability distribution of the classes exceeds a specified threshold;

i) means for assigning as the absolute worst case rank of the worst case ranks between any two adjacent phone boundaries the worst case rank of the correctly recognized phone between the phone boundaries;

j) means for discarding all phones whose rank is worse than this absolute worst case rank in the current segment;

k) means for making a short list of phones for the segment; and

l) means for outputting a recognition result in response to the short list of the recognition result being a short list of words.

8. An apparatus for recognizing speech, comprising:

a) means for inputting a plurality of words of training data;

b) means for training a plurality of binary first decision trees to ask a maximally informative question at each node based upon contextual information in the training data, wherein each binary first decision tree corresponds to a different time in a sequence of the training data;

c) means for traversing one of the decision trees for every time frame of an input sequence of speech to determine a probability distribution for every time frame, the probability distribution being the probability that a node is a phone boundary;

d) means for comparing the probabilities associated with the time frames with a threshold for identifying some time frames as boundaries between phones;

e) means for providing an acoustic score for all phones between every given pair of boundaries;

f) means for ranking the phones on the basis of this score; and

g) means for outputting a recognition result in response to the score;

h) means for traversing one or more of a second set of decision trees for every time frame on an input sequence of speech to determine a second probability distribution, the probability distribution being a distribution over all possible ranks that a phone can take for obtaining a worst case rank of a correctly recognized phone by choosing the worst case rank as the class value at which the cumulative probability distribution of the classes exceeds a specified threshold;

i) means for assigning as the absolute worst case rank of the worst case ranks between any two adjacent phone boundaries the worst case rank of the correctly recognized phone between the phone boundaries;

j) means for discarding all phone boundaries whose rank is worse than this absolute worst case rank in the current segment;

k) means for making a short list of phones for the segment;

l) means for comparing constituent phones of a word in a vocabulary to see if the word lies in the short list and making up a short list of words; and

m) means for outputting a recognition result by comparing the words of the short list with a language model to determine the most probable word match for the input sequence of speech.

9. An apparatus for recognizing speech, comprising:

a) means for entering a string of utterances constituting training data;

b) means for converting the utterances of the training data to electrical signals;

c) means for representing the electrical signal of the training data as prototype quantized feature vectors, one feature vector representing a given time frame;

d) means for assigning to each prototype feature vector a class label associated with the prototype quantized feature vector;

e) means for forming a plurality of binary decision trees for different times in the training data, each tree having a root node and a plurality of child nodes, comprising the steps of;

i. means for creating a set of training records comprising 2K+1 predictors, l^k, and one predicted class, p, where the 2K+1 predictors are feature vector labels at 2K+1 consecutive times t-K, . . . , t, . . . , t+K, and the predicted class is a binary record indicator whether time t associated with a phone boundary in the case of the first decision tree or is associated with the correct phone in the case of the second decision tree;

ii. means for computing the estimated joint distribution of predictors l^k and phone p for 2K+1 predictors using the training data, wherein the predictors are feature vector labels at times t-K, . . . , t, . . . , t+K and p is the phone at time t;

iii. means for storing the estimated joint distribution of l^k and p and a corresponding distribution for each predictor l^k at the root node;

iv. means for computing the best partitioning of the values that predictor l^k can take for each l^k to minimize phone uncertainty at each node; and

v. means for choosing the predictor l^k whose partitioning results in the lowest uncertainty and partitioning the training data into two child nodes based on the computed-based partitioning l^k, each child node being assigned a class distribution based on the training data at the child node;

f) means for repeating for each child node if the amount of training data at the child node is greater than a threshold;

g) means for inputting an utterance to be recognized;

h) means for converting the utterance into an electrical signal;

i) means for representing the electrical signal as a series of quantized feature vectors;

j) means for matching the series of quantized feature vectors against the stored prototype feature vectors to determine a closest match and assigning an input label to each of the series of feature vectors corresponding to the label of the closest matching prototype feature vector;

k) means for traversing one of the decision trees for every time frame of an input sequence of speech to determine a probability distribution for every time frame, the probability distribution being the probability that a node is a phone boundary;

l) means for comparing the probabilities associated with the time frames with a threshold for identifying some time frames as boundaries between phones;

m) means for providing an acoustic score for all phones between every given pair of boundaries;

n) means for ranking the phones on the basis of this score; and

o) means for outputting a recognition result in response to the score.

10. The apparatus of claim 9 further including:

means for traversing one or more of a second set of decision trees for every time frame on an input sequence of speech to determine a second probability distribution, the probability distribution being a distribution over all possible ranks that a phone can take for obtaining a worst case rank of a correctly recognized phone by choosing the worst case rank as the class value at which the cumulative probability distribution of the classes exceeds a specified threshold;

means for assigning as the absolute worst case rank of the worst case ranks between any two adjacent phone boundaries the worst case rank of the correctly recognized phone between the phone boundaries;

means for discarding all phone boundaries whose rank is worse than this absolute worst case rank in the current segment;

means for making a short list for the segment; and

means for outputting a recognition result in response to the short list.