Method and apparatus for finding the best splits in a decision tree for a language model for a speech recognizer

Claim 3

An automatic speech recognition system comprising: means for converting an utterance into an utterance signal representing the utterance, said utterance comprising a series of at least a predictor word and a predicted word, said utterance signal comprising at least one predictor word signal representing the predictor word; means for storing a set of M predictor feature signals, each predictor feature signal having a predictor feature value X m , where M is an integer greater than or equal to three and m is an integer greater than zero and less than or equal to M, each predictor feature signal in the set representing a different word; means for generating a decision set which contains a subset of the M predictor feature signals representing the words; means for comparing the predictor word signal with the predictor feature signals in the decision set; means for outputting a first category feature signal representing a first predicted word if the predictor word signal is a member of the decision set, said first category feature signal being one of N category feature signals, each category feature signal representing a different word and having a category feature value Y n , where N is an integer greater than or equal to three, and n is an integer greater than zero and less than or equal to N; and means for outputting a second category feature signal, different from the first category feature signal and representing a second predicted word different from the first predicted word if the predictor word signal is not a member of the decision set; characterized in that the means for generating the decision set comprises: means for storing a training text comprising a set of observed events, each event having a predictor feature X representing a predictor word and a category feature Y representing a predicted word, said predictor feature having one of M different possible values X m , each X m representing a different predictor word, said category feature having one of N possible values Y n , each Y n representing a different predicted word; (a) means for measuring the predictor feature value X m and the category feature value Y n of each event in the set of events; (b) means for estimating, from the measured predictor feature values and the measured category feature values, the probability P(X m , Y n ) of occurrence of an event having a category feature value Y n and a predictor feature value X m , for each Y n and each X m ; (c) means for selecting a starting set SX opt (t) of predictor feature values X m , where t has an initial value; (d) means for calculating, from the estimated probabilities P(X m , Y n ), the conditional probability P(SX opt (t)|Y n ) that the predictor feature has a value in the set SX opt (t) when the category feature has a value Y n , for each Y n ; (e) means for defining a number of pairs of sets SY j (t) and SY j (t) of category feature values Y n , where j is an integer greater than zero and less than or equal to (N-1), each set SY j (t) containing only those category feature values Y n having the j lowest values of P(SX opt (t)|Y n ), each set SY j (t) containing only those category feature values Y n having the (N-j) highest values of P(SX opt (t)|Y n ); (f) means for finding a pair of sets SY opt (t) and SY opt (t) from among the pairs of sets SY j (t) and SY j (t) such that the pair of sets SY opt (t) and SY opt (t) have the lowest uncertainty in the value of the predictor feature; (g) means for calculating, from the estimated probabilities P(X m , Y n ), the conditional probability P(SY opt (t)|X m ) that the category feature has a value in the set SY opt (t) when the predictor feature has a value X m , for each X m ; (h) means for defining a number of pairs of sets SX i (t+1) and SX i (t+1) of predictor feature values X m , where i is an integer greater than zero and less than or equal to (M-1), each set SX i (t+1) containing only those predictor feature values X m having the i lowest values of P(SY opt (t)|X m ), each set SX i (t+1) containing only those predictor feature values X m having the (M-i) highest values of P(SY opt (t)|X m ); (i) means for finding a pair of sets SX opt (t+1) and SX opt (t+1) from among the pairs of sets SX i (t+1) and SX i (t+1) such that the pair of sets SX opt (t+1) and SX opt (t+1) have the lowest uncertainty in the value of the category feature; and (l) means for outputting the set SX opt (t+1) as the decision set.

Claim 4

An automatic speech recognition system comprising: means for converting an utterance into an utterance signal representing the utterance, said utterance comprising a series of at least a predictor word and a predicted word, said utterance signal comprising at least one predictor word signal representing the predictor word; means for storing a set of M predictor feature signals, each predictor feature signal having a predictor feature value X m , where M is an integer greater than or equal to three and m is an integer greater than zero and less than or equal to M, each predictor feature signal in the set representing a different word; means for generating a decision set which contains a subset of the M predictor feature signals representing the words; means for comparing the predictor word signal with the predictor feature signals in the decision set; means for outputting a first category feature signal representing a first predicted word if the predictor word signal is a member of the decision set, said first category feature signal being one of N category feature signals, each category feature signal representing a different word and having a category feature value Y n , where N is an integer greater than or equal to three, and n is an integer greater than zero and less than or equal to N; and means for outputting a second category feature signal, different from the first category feature signal and representing a second predicted word different from the first predicted word if the predictor word signal is not a member of the decision set; characterized in that the means for generating the decision set comprises: means for storing a training text comprising a set of observed events, each event having a predictor feature X representing a predictor word and a category feature Y representing a predicted word, said predictor feature having one of M different possible values X m , each X m representing a different predictor word, said category feature having one of N possible values Y n , each Y n representing a different predicted word; (a) means for measuring the predictor feature value X m and the category feature value Y n of each event in the set of events; (b) means for estimating, from the measured predictor feature values and the measured category feature values, the probability P(X m , Y n ) of occurrence of an event having a category feature value Y n and a predictor feature value X m , for each Y n and each X m ; (c) means for selecting a starting set SX opt (t) of predictor feature values X m , where t has an initial value; (d) means for calculating, from the estimated probabilities P(X m , Y n ), the conditional probability P(SX opt (t)|Y n ) that the predictor feature has a value in the set SX opt (t) when the category feature has a value Y n , for each Y n ; (e) means for defining a number of pairs of sets SY j (t) and SY j (t) of category feature values Y n , where j is an integer greater than zero and less than or equal to (N-1), each set SY j (t) containing only those category feature values Y n having the j lowest values of P(SX opt (t)|Y n ), each set SY j (t) containing only those category feature values Y n having the (N-j) highest values of P(SX opt (t)|Y n ); (f) means for finding a pair of sets SY opt (t) and SY opt (t) from among the pairs of sets SY j (t) and SY j (t) such that the pair of sets SY opt (t) and SY opt (t) have the lowest uncertainty in the value of the predictor feature; (g) means for calculating, from the estimated probabilities P(X m , Y n ), the conditional probability P(SY opt (t)|X m ) that the category feature has a value in the set SY opt (t) when the predictor feature has a value X m , for each X m ; (h) means for defining a number of pairs of sets SX i (t+1) and SX i (t+1) of predictor feature values X m , where i is an integer greater than zero and less than or equal to (M-1), each set SX i (t+1) containing only those predictor feature values X m having the i lowest values of P(SY opt (t)|X m ), each set SX i (t+1) containing only those predictor feature values X m having the (M-i) highest values of P(SY opt (t)|X m ); (i) means for finding a pair of sets SX opt (t+1) and SX opt (t+1) from among the pairs of sets SX i (t+1) and SX i (t+1) such that the pair of sets SX opt (t+1) and SX opt (t+1) have the lowest uncertainty in the value of the category feature; and (l) means for outputting the set SX opt (t+1) as the decision set.