Method and apparatus for constructing Markov model word baseforms

Claim 3

The method of Claim 1 comprising the further steps of: (j) concatenating the respective constructed sequences of Markov models for the successive common segments of the subject word to form a word baseform; and (k) repeating steps (a) though (j) for each word in the vocabulary.

Claim 4

The method of Claim 2 wherein step (h) includes the steps of: (l) for each i-th common segment, locating a consistent point in each i-th substring corresponding thereto and dividing each substring at the consistent point thereof into a left portion and a right portion.

Claim 5

The method of Claim 3 wherein step (l) includes the steps of: (m) determining, from the stored probabilities, the Markov model having the highest joint probability of producing the i-th label of the prototype string and the i-th substrings of all the other strings; (n) appending a Markov model in front of the determined Markov model to form an ordered pair of Markov models and computing, based on the stored probabilities, the probability of the ordered pair of Markov models producing the i-th label of the prototype string and the each of the i-th substrings of the other strings; (o) repeating step (n) for each Markov model in the set as the appended Markov model; (p) appending a Markov model at the end of the selected Markov model to form an ordered pair of Markov models and computing, based on the stored probabilities, the probability of the ordered pair of Markov models producing the i-th label of the prototype string and the each of the i-th substrings of the other strings; (q) repeating step (p) for each Markov model in the set as the appended Markov model; (r) selecting the ordered pair of the appended Markov model and the selected Markov model that has the highest joint probability of producing the i-th label of the prototype string and the each of the i-th substrings of the other strings; and (s) performing an alignment process between the selected ordered pair of Markov models and each i-th substring, the point in each substring where the two Markov models meet being the consistent point.

Claim 6

The method of Claim 3 comprising the further steps of: (t) splitting the left portion from the right portion of each i-th substring at the respective consistent point thereof; (u) finding the single Markov model P L having the highest joint probability for the left portions of the i-th substrings; (v) finding the two-model sequence, from among all two-model sequences that include the Markov model P L , which has the highest joint probability of producing the left portions; (w) if the highest probability two-model sequence of step (v) is higher than the probability associated with the single phone P L , aligning each i-th substring against the found two-model sequence and splitting the found two-model sequence apart at the point of meeting into a resultant left portion and a resultant right portion; and (x) performing steps (t) through (w) with the resultant left portion and the resultant right portion being substituted for the left portion and the right portion respectively.

Claim 7

The method of claim 5 comprising the further steps of: (y) discontinuing the splitting when a highest probability single Markov model has a higher probability than any two-model sequence that includes the highest probability single Markov model and an appended Markov model; and (z) concatenating the unsplit single Markov models, the concatenated unsplit Markov models representing a basic baseform for the i-th segment of the subject word.

Claim 8

The method of Claim 6 comprising the further steps of: (aa) aligning each i-th substring against the baseform of the concatenated unsplit single Markov models; and (bb) for a Markov model in the concatenated baseform, determining the labels which are aligned thereagainst and either, if there are no aligned labels, deleting the Markov model from the concatenated baseform, or if there are aligned labels, finding the Markov model which maximizes the probability of producing the determined labels; and (cc) replacing the Markov model in the concatenated baseform by the found phone if they differ; and (dd) repeating step (cc) for each Markov model in the concatenated basic baseform of the i-th segment of the subject word.

Claim 9

The method of Claim 7 comprising the further step of: (dd) repeating steps (aa), (bb), and (cc) until each Markov model in the concatenated baseform has the maximum probability of producing the labels aligned therewith; the baseform resulting from step (dd) being a refined baseform for the word segment.

Claim 10

In a speech recognition system, a method of determining Markov model sequences for words in a vocabulary, based on multiple utterances of each word, the method comprising the steps of: (a) generating, from an acoustic processor which assigns one of an alphabet of speech-type labels to each successive interval of speech, a respective string of labels for each utterance of a subject word; (b) storing the respective strings in computer memory; and (c) partitioning the generated string for each utterance of the subject word into successive word segments; wherein step (c) includes the steps of: (d) computing and storing arc probabilities and label output probabilities for each of a set of Markov models, wherein each Markov model in the set corresponds to a respective label; (e) retrieving from storage the generated string corresponding to a prototype utterance for a subject word; (f) selecting one Markov model after another in sequence, each corresponding to one respective label after another generated by the acoustic processor for the prototype utterance; (g) aligning each Markov model for the prototype utterance against labels generated for another utterance of the subject word, wherein the successive Markov models for the prototype utterance are aligned against successive substrings for said other utterance based on the stored probabilities; and (h) repeating step (g) for each utterance other than the prototype utterance; the i-th label of the prototype string and the i-th substring of each other string representing the i-th segment of each respective utterance.

Claim 11

In a speech recognition system, a method of determining Markov model sequences for words in a vocabulary, based on multiple utterances of each word, the method comprising the steps of: (a) generating, from an acoustic processor which assigns one of an alphabet of speech-type labels to each successive interval of speech, a respective string of labels for each utterance of a subject word; (b) storing the respective strings in computer memory; and (c) partitioning the generated string for each utterance of the subject word into successive word segments; wherein step (c) includes the steps of: (d) computing and storing arc probabilities and label output probabilities for each of a set of Markov models, wherein each Markov model in the set corresponds to a respective label; (e) retrieving from storage the generated string corresponding to a prototype utterance for a subject word; (f) selecting one Markov model after another in sequence, each corresponding to one respective label after another generated by the acoustic processor for the prototype utterance; (g) aligning each Markov model for the prototype utterance against labels generated for another utterance of the subject word, wherein the successive Markov models for the prototype utterance are aligned against successive substrings for said other utterance based on the stored probabilities; and (h) repeating step (g) for each utterance other than the prototype utterance; the i-th label of the prototype string and the i-th substring of each other string representing the i-th segment of each respective utterance.

Claim 12

The method of Claim 9 further comprising the step of: (j) constructing a single sequence of Markov models applicable to each i-th segment corresponding to each utterance, where 1≦i≦N, and N is the total number of segments into which the subject word is partitioned; which includes the steps of: (k) where phonelength corresponds to the number of Markov models in sequence, finding a one-model best first baseform P L of phonelength 1 which maximizes the joint probability of producing the substrings resulting from multiple utterances of a given word in a vocabulary of words; (l) finding a two-model best second baseform of phonelength 2 and of the form either P L P₂ or P₂P L which has a higher joint probability than any other baseform of length 2; (m) iteratively comparing the joint probability of the found best first baseform with the joint probability of the found best second baseform and, if the found best second baseform joint probability is higher than the joint probability of the found best first baseform, splitting each label string into a left portion and a right portion at the point which maximizes the probability that the left portion is produced by the left model and the right portion is produced by the right model; (n) repeating steps (k) through (m) until all baseforms are of single phonelength and no found best second baseform has a higher probability than its respective found best first baseform; (o) after step (n), concatenating the baseforms of phonelength 1 to form a basic baseform of the i-th word segment.

Claim 13

the method of Claim 10 comprising the further steps of: (p) aligning the concatenated baseform against the i-th substrings using the Viterbi algorithm and identifying a group of labels in each i-th substring which corresponds to each Markov model in the concatenated baseform for the i-th word segment; and (q) replacing, in memory containing the baseform, any Markov model in the concatenated baseform by any other Markov model in the set having a higher joint probability of producing the label groups in the multiple i-th substrings.

Claim 14

The method of Claim 11 comprising the further steps of: (r) concatenating the respective single sequences for successive segments in order to form a sequence of Markov models for the subject word; and (s) repeating steps (a) through (r) for one word after another in a vocabulary of words.

Claim 15

The method of Claim 12 wherein step (d) includes the steps of: (t) selecting one of the strings for a given word and constructing a preliminary baseform of the given word formed of the sequence of fenemic Markov models corresponding to the labels in the selected string; and (u) computing arc probabilities and label output probabilities for the fenemic Markov models.

Claim 16

The method of Claim 9 wherein step (d) includes the steps of: (v) selecting one of the strings for a given word and constructing a preliminary baseform of the given word formed of the sequence of fenemic Markov models corresponding to the labels in the selected string; (w) computing arc probabilities and label output probabilities for fenemic Markov models based on the labels generated for all strings other than the selected one string of step (v).

Claim 17

The method of Claim 9 wherein step (c) includes the steps of: (x) grouping substrings corresponding to one Markov model in the singleton baseform after another, each group corresponding to a common segment of the subject word; (y) determining the best single Markov model P₁ for producing the substrings in an i-th group; (z) determining the best two model baseform of the form P₁P₂ or P₂P₁ for producing the substrings in the i-th group; (aa) aligning the best two model baseform against each substring in the i-th group; (bb) splitting each substring of the i-th group into a left portion and a right portion with the left portion corresponding to the first Markov model of the two phone baseform and the right portion corresponding to the second Markov model of the two phone baseform; (cc) identifying each left portion as a left substring and each right portion as a right substring; (dd) processing the set of left substrings in the same manner as the set of substrings in the i-th group including the further step of inhibiting further splitting of a substring when the single model baseform thereof has a higher probability of producing the substring than does the best two model baseform; (ee) processing the set of right substrings in the same manner as the set of substrings in the i-th group including the further step of inhibiting further splitting of a substring when the single model baseform thereof has a higher probability of producing the substring than does the best two model baseform; (ff) concatenating the unsplit single models in an order corresponding the order of the groups to which they correspond; (gg) aligning the concatenated baseform against each of the substrings for the i-th group and identifying, for each model in the concatenated baseform, the substring in each substring of the i-th group which corresponds thereto, the substrings corresponding to a given model being a set of common substrings; (hh) for each set of common substrings, determining the Markov model having the highest joint probability of producing the common substrings; (jj) for each common substring, replacing the model therefor in the concatenated baseform by the determined model of highest joint probability; and repeating steps (gg) through (jj) until no models are replaced.

Claim 18

Apparatus for constructing a Markov model word baseform for a word in a vocabulary from multiple utterances thereof, the apparatus comprising: acoustic processor means (202) for generating a string of labels in response to an uttered speech input; storage means (206), coupled to receive label string outputs from the acoustic processor means, for storing labels for multiple strings of labels generated by the acoustic processor in response to multiple utterances of a subject word; selector means (208) for retrieving a prototype string from among the stored strings for the subject word; forming means (210), coupled to receive as input a retrieved prototype string, for forming a singleton word baseform for the retrieved prototype string; aligning means (212), coupled to retrieve label strings from the label string storing means and coupled to the singleton baseform means, for aligning the labels in strings other than the selected prototype string against the singleton baseform, each string being divided into successive substrings respectively aligned against successive fenemic Markov models in the singleton baseform; and correlator means (214), coupled to receive input alignment data from the aligning means, for grouping the i-th substrings of the multiple strings, each group of i-th substrings corresponding to a common word segment.

Claim 19

Apparatus for constructing a Markov model word baseform for a word in a vocabulary from multiple utterances thereof, the apparatus comprising: acoustic processor means (202) for generating a string of labels in response to an uttered speech input; storage means (206), coupled to receive label string outputs from the acoustic processor means, for storing labels for multiple strings of labels generated by the acoustic processor in response to multiple utterances of a subject word; selector means (208) for retrieving a prototype string from among the stored strings for the subject word; forming means (210), coupled to receive as input a retrieved prototype string, for forming a singleton word baseform for the retrieved prototype string; aligning means (212), coupled to retrieve label strings from the label string storing means and coupled to the singleton baseform means, for aligning the labels in strings other than the selected prototype string against the singleton baseform, each string being divided into successive substrings respectively aligned against successive fenemic Markov models in the singleton baseform; and correlator means (214), coupled to receive input alignment data from the aligning means, for grouping the i-th substrings of the multiple strings, each group of i-th substrings corresponding to a common word segment.

Claim 20

Apparatus as in Claim 16 further comprising: model constructor means (216) for determining the fenemic Markov model or fenemic Markov model sequence having the highest joint probability of producing the labels in a group of substrings formed by the correlator means.

Claim 21

Apparatus as in Claim 17 further comprising: training means (206) for computing arc probabilities and label output probabilities for each fenemic Markov model including: means for choosing any string of labels generated for the subject word; means, coupled to the string choosing means, for forming a preliminary sample baseform from said any chosen string; and means, coupled to the sample baseform forming means and the storing means, for computing arc probabilities and label output probabilities.