Method and apparatus for a time-synchronous tree-based search strategy

Claim 2

A speech recognition method for recognizing an entire utterance, for a system including an asynchronous detailed match procedure, said method comprising the step of performing a synchronous fast match process for said entire utterance prior to executing said detailed match procedure.

Claim 3

A method as recited in claim 1, wherein said fast match process is performed in an iterative manner with an iteration performed for each of a plurality of frame triplets.

Claim 4

A method as recited in claim 2, wherein each phoneme in a fast match graph is represented as a single state with a self loop.

Claim 5

A method as recited in claim 1 wherein said fast match process proceeds backward from an end of said entire utterance towards a beginning of said entire utterance.

Claim 6

A method as recited in claim 1, further comprising: providing a fast match graph for a speech language vocabulary, wherein said fast match graph corresponds to a backward search, and wherein said graph has arcs having destinations exiting a given node and are stored as the successors to that node, while the sources of the incoming arcs are stored as its predecessors; storing the phoneme identity of each node in said fast match graph for use in a Viterbi search; storing an identity of each word formed by a group of phonemes; and invoking dynamic programming of said Viterbi search to enable construction of lists of potential words at each of said plurality of frame triplets.

Claim 7

A speech recognition system for recognizing an entire utterance and having means for receiving and executing a detailed match procedure, said system comprising: means for performing a synchronous fast match on said entire utterance prior to asynchronously executing said detailed match procedure.

Claim 8

A speech recognition system for recognizing an entire utterance and having means for receiving and executing a detailed match procedure, said system comprising: means for performing a synchronous fast match on said entire utterance prior to asynchronously executing said detailed match procedure.

Claim 9

A system as recited in claim 6, wherein said fast match process is performed in an iterative manner with an iteration performed for each of a plurality of frame triplets.

Claim 10

A system as recited in claim 7, wherein each phoneme in a fast match graph is represented as a single state with a self loop.

Claim 11

A system as recited in claim 6, wherein said fast match process proceeds backward from an end of said entire utterance towards a beginning of said entire utterance.

Claim 12

A speech recognition method for recognizing an entire utterance segmented into a plurality of frames and based upon a speech language vocabulary, said method comprising: receiving an utterance; forming an acoustic signal of a plurality of phoneme constituents making up said utterance; combining three of said frames to form a frame triplet; initiating a fast match for said utterance by forming a phoneme probability matrix table giving probabilities of each phoneme versus an acoustic observation time, wherein said phoneme matrix table has each column corresponding to a single frame; multiplying together a group of three individual probabilities of the three frames that make up each said triplet to produce a joint probability of the triplet for each particular said phoneme and triplet; forming a triplet probability matrix representing a complete observation time of said utterance and having a row for each phoneme of said utterance and a column for each said triplet; and invoking a synchronous iterative process to perform the fast match for the entire utterance in steps of frame triplets.

Claim 13

A speech recognition method for recognizing an entire utterance segmented into a plurality of frames and based upon a speech language vocabulary, said method comprising: receiving an utterance; forming an acoustic signal of a plurality of phoneme constituents making up said utterance; combining three of said frames to form a frame triplet; initiating a fast match for said utterance by forming a phoneme probability matrix table giving probabilities of each phoneme versus an acoustic observation time, wherein said phoneme matrix table has each column corresponding to a single frame; multiplying together a group of three individual probabilities of the three frames that make up each said triplet to produce a joint probability of the triplet for each particular said phoneme and triplet; forming a triplet probability matrix representing a complete observation time of said utterance and having a row for each phoneme of said utterance and a column for each said triplet; and invoking a synchronous iterative process to perform the fast match for the entire utterance in steps of frame triplets.

Claim 14

A speech recognition method for recognizing an entire utterance segmented into a plurality of frames and based upon a speech language vocabulary, said method comprising: receiving an utterance; forming an acoustic signal of a plurality of phoneme constituents making up said utterance; combining three of said frames to form a frame triplet; initiating a fast match for said utterance by forming a phoneme probability matrix table giving probabilities of each phoneme versus an acoustic observation time, wherein said phoneme matrix table has each column corresponding to a single frame; multiplying together a group of three individual probabilities of the three frames that make up each said triplet to produce a joint probability of the triplet for each particular said phoneme and triplet; forming a triplet probability matrix representing a complete observation time of said utterance and having a row for each phoneme of said utterance and a column for each said triplet; invoking a synchronous iterative process to perform the fast match for the entire utterance in steps of frame triplets; initializing to the root node and to the end of the utterance; determining for each potentially active node `n` at a next time τ, a maximum of a node at time τ+3 which maximizes the product of a score of said node with the transition probability from said node into a potentially active node; computing the score s(τ,n) of the potentially active node given by a product of said maximum and an observation probability at a current time of the phoneme identified with state `n`; determining a maximum score of the node scores at the current time; comparing the score for each potentially active node to said maximum score; including in a next active list, only active nodes for which the difference between the log of said active node score and the log of the maximum score is less than a user-specified range constant; and adding to a matrix of contender words at an appropriate time, a new node placed in said next active list which corresponds to a beginning of a whole word, and a new node score of said new node.

Claim 15

A speech recognition method for recognizing an entire utterance segmented into a plurality of frames and based upon a speech language vocabulary, said method comprising: receiving an utterance; forming an acoustic signal of a plurality of phoneme constituents making up said utterance; combining three of said frames to form a frame triplet; initiating a fast match for said utterance by forming a phoneme probability matrix table giving probabilities of each phoneme versus an acoustic observation time, wherein said phoneme matrix table has each column corresponding to a single frame; multiplying together a group of three individual probabilities of the three frames that make up each said triplet to produce a joint probability of the triplet for each particular said phoneme and triplet; forming a triplet probability matrix representing a complete observation time of said utterance and having a row for each phoneme of said utterance and a column for each said triplet; invoking a synchronous iterative process to perform the fast match for the entire utterance in steps of frame triplets; initializing to the root node and to the end of the utterance; determining for each potentially active node `n` at a next time τ, a maximum of a node at time τ+3 which maximizes the product of a score of said node with the transition probability from said node into a potentially active node; computing the score s(τ,n) of the potentially active node given by a product of said maximum and an observation probability at a current time of the phoneme identified with state `n`; determining a maximum score of the node scores at the current time; comparing the score for each potentially active node to said maximum score; including in a next active list, only active nodes for which the difference between the log of said active node score and the log of the maximum score is less than a user-specified range constant; and adding to a matrix of contender words at an appropriate time, a new node placed in said next active list which corresponds to a beginning of a whole word, and a new node score of said new node.

Claim 16

A method as recited in claim 11, further comprising the step of making available said matrix of contender words to a detailed match process.

Claim 17

A method as recited in claim 11, wherein said new node score is obtained by multiplying an unnormalized backward score of said new node by an unnormalized forward score of a root node.

Claim 18

A method as recited in claim 13, wherein said unnormalized forward score of said root node is obtained from a detailed match procedure.

Claim 19

A speech recognition method for recognizing an entire utterance segmented into a plurality of frames and based upon a speech language vocabulary, said method comprising: receiving an utterance; forming an acoustic signal of a plurality of phoneme constituents making up said utterance; combining three of said frames to form a frame triplet; initiating a fast match for said utterance by forming a phoneme Probability matrix table giving probabilities of each phoneme versus an acoustic observation time, wherein said phoneme matrix table has each column corresponding to a single frame; multiplying together a group of three individual probabilities of the three frames that make up each said triplet to produce a joint probability of the triplet for each particular said phoneme and triplet; forming a triplet probability matrix representing a complete observation time of said utterance and having a row for each phoneme of said utterance and a column for each said triplet; invoking a synchronous iterative process to Perform the fast match for the entire utterance in steps of frame triplets; forming a `next potentials list` from the `current active list` if an utterance beginning has not been reached; computing and storing a score for each node in the `potentials list`; finding and storing a current highest node score; choosing and using an inclusion range parameter to form the `next active list`; entering and storing active list entries for each triplet in a `matrix of contender words`; decrementing to a next backward frame triplet; modifying the `current active list` to correspond with the next active list; and stopping the fast match process if the utterance beginning has been reached.

Claim 20

A speech recognition method for recognizing an entire utterance segmented into a plurality of frames and based upon a speech language vocabulary, said method comprising: receiving an utterance; forming an acoustic signal of a plurality of phoneme constituents making up said utterance; combining three of said frames to form a frame triplet; initiating a fast match for said utterance by forming a phoneme Probability matrix table giving probabilities of each phoneme versus an acoustic observation time, wherein said phoneme matrix table has each column corresponding to a single frame; multiplying together a group of three individual probabilities of the three frames that make up each said triplet to produce a joint probability of the triplet for each particular said phoneme and triplet; forming a triplet probability matrix representing a complete observation time of said utterance and having a row for each phoneme of said utterance and a column for each said triplet; invoking a synchronous iterative process to Perform the fast match for the entire utterance in steps of frame triplets; forming a `next potentials list` from the `current active list` if an utterance beginning has not been reached; computing and storing a score for each node in the `potentials list`; finding and storing a current highest node score; choosing and using an inclusion range parameter to form the `next active list`; entering and storing active list entries for each triplet in a `matrix of contender words`; decrementing to a next backward frame triplet; modifying the `current active list` to correspond with the next active list; and stopping the fast match process if the utterance beginning has been reached.

Claim 21

A speech recognition method for recognizing an entire utterance, for a system including a fast match process and a detailed match procedure, wherein said fast match process proceeds backward from an end of said entire utterance towards a beginning of said entire utterance.

Claim 22

A speech recognition method for recognizing an entire utterance, for a system including a fast match process and a detailed match procedure, wherein said fast match process proceeds backward from an end of said entire utterance towards a beginning of said entire utterance.

Claim 23

A speech recognition method comprising: recognizing an utterance by performing an asynchronous detailed match and a synchronous fast match, wherein said fast match is performed in an iterative manner with an iteration performed for each of a plurality of frames.

Claim 24

A speech recognition method comprising: recognizing an utterance by performing an asynchronous detailed match and a synchronous fast match, wherein said fast match is performed in an iterative manner with an iteration performed for each of a plurality of frames.

Claim 25

A method as recited in claim 17, further comprising representing each phoneme in a fast match graph as a single state with a self loop.

Claim 26

A method as recited in claim 17, further comprising forming said plurality of frames comprised of a frame triplet.

Claim 27

A speech recognition system for recognizing an utterance, said system comprising a fast match process which proceeds backward from an end of said utterance towards a beginning of said utterance.

Claim 28

A speech recognition system for recognizing an utterance, said system comprising a fast match process which proceeds backward from an end of said utterance towards a beginning of said utterance.

Claim 29

A speech recognition system as recited in claim 20, including a fast match process, wherein said fast match process is performed in an iterative manner with an iteration performed for each of a plurality of frames.

Claim 30

A system as recited in claim 21, wherein each phoneme in a fast match graph is represented as a single state with a self loop.

Claim 31

A system as recited in claim 21, wherein said plurality of frames comprises a frame triplet.

Claim 32

A speech recognition apparatus comprising: means for synchronously performing a fast match on an entire utterance; and means for executing a detailed match procedure asynchronously on said entire utterance so as to recognize said entire utterance.

Claim 33

A speech recognition apparatus comprising: means for synchronously performing a fast match on an entire utterance; and means for executing a detailed match procedure asynchronously on said entire utterance so as to recognize said entire utterance.

Claim 34

A speech recognition apparatus as recited in claim 24, further comprising means for receiving said entire utterance.

Claim 35

A speech recognition method comprising: multiplying phoneme probabilities together in groups of three frames, each group forming a triplet, and employing each triplet in a fast match process using a non-replicated one state model.

Claim 36

A speech recognition method comprising: multiplying phoneme probabilities together in groups of three frames, each group forming a triplet, and employing each triplet in a fast match process using a non-replicated one state model.

Claim 37

A speech recognition method as recited in claim 26, further comprising constructing a matrix of phoneme probabilities versus time triplets.