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

Claim 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.

Claim 2

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.

Claim 3

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.

Claim 4

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.

Claim 5

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.

Claim 6

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.

Claim 7

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.

Claim 8

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.

Claim 10

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.

Claim 11

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.

Claim 12

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.

Claim 13

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.

Claim 14

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.

Claim 15

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.

Claim 16

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.

Claim 17

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.