Method and apparatus for generating deterministic approximate weighted finite-state automata

• US 6,073,098 A
• Filed: 11/21/1997
• Issued: 06/06/2000
• Est. Priority Date: 11/21/1997
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Buchsbaum, Adam Louis, Giancarlo, Raffaele, Westbrook, Jeffery Rex
• Primary Examiner(s): Hudspeth, David R.
• Assistant Examiner(s): Lerner, Martin
• Application Number:
  US08/975,648
• Time in Patent Office: 928 Days
• Field of Search: 704/231, 704/232, 704/236, 704/242, 704/255, 704/256, 706/5, 706/17, 706/20, 706/39, 706/55
• US Class Current: 704/255
• CPC Class Codes: G10L 15/08 Speech classification or search
• CPC Class Codes: G10L 15/19 Grammatical context, e.g. disambiguation of the recognition hypotheses based on word sequence rules

Abstract

An approximate weighted finite-state automaton can be constructed in place of a weighted finite-state automaton so long as the approximate weighted finite-state automaton maintains a sufficient portion of the original best strings in the weighted finite-state automaton and sufficiently few spurious strings are introduced into the approximate weighted finite-state automaton compared to the weighted finite-state automaton. An approximate weighted finite-state automaton can be created from a non-deterministic weighted finite-state automaton during determinization by discarding the requirement that old states be used in place of new states only when an old state is identical to a new state. Instead, in an approximate weighted finite-state automaton, old states will be used in place of new states when each of the remainders of the new state is sufficiently close to the corresponding remainder of the old state. An error tolerance parameter τ defines whether the remainders of the new state are sufficiently close to the corresponding remainders of the old state. If the remainders of the new state are sufficiently close to the remainders of the old state, a new transition is created from a current state to the old state rather than the new state. Such approximate weighted finite-state automata allow the size of the resulting deterministic finite-state automata to be reduced and can prevent the expansion that would otherwise occur in some deterministic finite-state automata.

Claims

1. A method for automatically recognizing speech, comprising:

inputting an electric signal representing an uttered speech;

converting the electric signal to a feature vector lattice; and

converting the feature vector lattice to a recognized text string representing the uttered speech using at least one approximate weighted finite-state lattice;

wherein each at least one approximate weighted finite-state lattice is generated from a corresponding non-deterministic weighted finite-state lattice by;

determining the corresponding non-deterministic weighted finite-state lattice to form the approximate weighted finite-state lattice on a state-by-state basis;

determining, as each set of states of the corresponding non-deterministic weighted finite-state lattice reachable from a current state of the approximate weighted finite-state lattice is determinized to form at least one proposed new state of the approximate weighted finite-state lattice, for each proposed new state, if that proposed new state is sufficiently similar to a previous state of the approximate weighted finite-state lattice;

creating a transition from the current state of the approximate weighted finite-state lattice to the previous state of the approximate weighted finite-state lattice if that proposed new state is sufficiently similar to the previous state; and

creating a transition from the current state of the approximate weighted finite-state lattice to the proposed new state of the approximate weighted finite-state lattice if that proposed new state is not sufficiently similar to any previous state of the approximate weighted finite-state lattice.

2. The method of claim 1, wherein converting the feature vector lattice to a recognized text string comprises:

converting the feature vector lattice to a phone lattice using an acoustic model lattice;

converting the phone lattice to a word lattice using a lexicon lattice; and

converting the word lattice to the recognized text string using a grammar lattice;

wherein at least one of the acoustic model lattice, the lexicon lattice and the grammar lattice is an approximate weighted finite-state lattice.

3. The method of claim 1, wherein converting the feature vector lattice to a recognized text string comprises:

converting the feature vector lattice to a phone lattice using an acoustic model lattice; and

converting the phone lattice to the recognized text string using a composed lexicon and grammar lattice;

wherein at least one of the acoustic model lattice, and the composed lexicon and grammar lattice is an approximate weighted finite-state lattice.

4. The method of claim 1, wherein converting the feature vector lattice to a recognized text string comprises:

converting the feature vector lattice to a word lattice using a composed acoustic model and lexicon lattice; and

converting the word lattice to the recognized text string using a grammar lattice;

wherein at least one of the composed acoustic model and lexicon lattice and the grammar lattice is an approximate weighted finite-state lattice.

5. The method of claim 1, wherein converting the feature vector lattice to a recognized text string comprises converting the feature vector lattice to the recognized text string using a composed acoustic model, lexicon and grammar lattice, wherein the composed acoustic model, lexicon and grammar lattice is an approximate weighted finite-state lattice.

6. The method of claim 1, wherein each at least one approximate weighted finite-state lattice corresponds to a non-deterministic weighted finite-state lattice and is an approximation of a deterministic weighted finite-state lattice generated from the corresponding non-deterministic weighted finite-state lattice.

7. An automatic speech recognition system, comprising:

a speech processing subsystem that inputs an electrical signal representing an uttered speech and outputs a feature vector lattice; and

a speech recognizer that inputs the feature vector lattice and outputs a text string representing the uttered speech;

wherein the speech recognizer converts the feature vector lattice to the text string using at least one approximate weighted finite-state lattice;

means for determinizing, for each approximate weighted finite-state lattice, a corresponding non-deterministic weighted finite-state lattice on a state-by-state basis to form that approximate weighted finite-state lattice;

means for determining, as each set of states of the corresponding non-deterministic weighted finite-state lattice reachable from a current state of that approximate weighted finite-state lattice is determinized to form at least one proposed new state of that approximate weighted finite-state lattice, for each proposed new state, if that proposed new state is sufficiently similar to a previous state of that approximate weighted finite-state lattice;

means for creating a transition from the current state of that approximate weighted finite-state lattice to the previous state of that approximate weighted finite-state lattice if that proposed new state is sufficiently similar to the previous state; and

means for creating a transition from the current state of that approximate weighted finite-state lattice to the proposed new state of that approximate weighted finite-state lattice if that proposed new state is not sufficiently similar to any previous state of that approximate weighted finite-state lattice.

8. The automatic speech recognition system of claim 7, wherein the speech recognizer comprises:

a phonetic recognition subsystem than converts the feature vector lattice to a phone lattice using an acoustic model lattice;

a word recognition subsystem that converts the phone lattice to a word lattice using a lexicon lattice; and

a text recognition subsystem that converts the word lattice to the recognized text string using a grammar lattice;

wherein at least one of the acoustic model lattice, the lexicon lattice and the grammar lattice is an approximate weighted finite-state lattice.

9. The automatic speech recognition system of claim 7, wherein the speech recognizer comprises:

a phonetic recognition subsystem than converts the feature vector lattice to a phone lattice using an acoustic model lattice; and

a word and text recognition subsystem that converts the phone lattice to the recognized text string using a composed lexicon and grammar lattice;

wherein at least one of the acoustic model lattice, and the composed lexicon and grammar lattice is an approximate weighted finite-state lattice.

10. The automatic speech recognition system of claim 7, wherein the speech recognizer comprises:

a phonetic and word recognition subsystem than converts the feature vector lattice to a word lattice using a composed acoustic model and lexicon lattice; and

a text recognition subsystem that converts the word lattice to the recognized text string using a grammar lattice;

wherein at least one of the composed acoustic model and lexicon lattice and the grammar lattice is an approximate weighted finite-state lattice.

11. The automatic speech recognition system of claim 7, wherein the speech recognizer comprises a phonetic, word and task recognition subsystem that converts the feature vector lattice to a recognized text string using a composed acoustic model, lexicon and grammar lattice, wherein the composed acoustic model, lexicon and grammar lattice is an approximate weighted finite-state lattice.

12. The automatic speech recognition system of claim 7, wherein each at least one approximate weighted finite-state lattice corresponds to a non-deterministic weighted finite-state lattice and is an approximation of a deterministic weighted finite-state lattice generated from the corresponding non-deterministic weighted finite-state lattice.