Method and apparatus for an improved language recognition system

• US 5,870,706 A
• Filed: 04/10/1996
• Issued: 02/09/1999
• Est. Priority Date: 04/10/1996
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Alshawi, Hiyan
• Primary Examiner(s): Hudspeth, David R.
• Assistant Examiner(s): Opsasnick, Michael N.
• Application Number:
  US08/631,874
• Time in Patent Office: 1,035 Days
• Field of Search: 395/2.6-2.65, 395/2.2
• US Class Current: 704/255
• CPC Class Codes: G10L 15/1815 Semantic context, e.g. disambiguation of the recognition hypotheses based on word meaning
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams

Abstract

Methods and apparatus for a language model and language recognition systems are disclosed. The method utilizes a plurality of probabilistic finite state machines having the ability to recognize a pair of sequences, one sequence scanned leftwards, the other scanned rightwards. Each word in the lexicon of the language model is associated with one or more such machines which model the semantic relations between the word and other words. Machine transitions create phrases from a set of word string hypotheses, and incrementally calculate costs related to the probability that such phrases represent the language to be recognized. The cascading lexical head machines utilized in the methods and apparatus capture the structural associations implicit in the hierachical organization of a sentence, resulting in a language model and language recognition systems that combine the lexical sensitivity of N-gram models with the structural properties of dependency grammar.

Claims

1. A method for language recognition, wherein a signal indicative of the language to be recognized is generated, comprising the steps of:

generating candidate word strings for the signal;

selecting among the candidates using a language model utilizing a plurality of finite state machines, each machine having the ability to recognize a pair of sequences, one sequence scanned leftwards, the other scanned rightwards, and each machine corresponding to a word in a vocabulary of the language model.

2. The method of claim 1 wherein the step of selecting further comprises utilizing only finite state machines corresponding to the words contained in the candidate word strings.

3. The method of claim 1 wherein the step of generating candidate word strings further comprises generating such word strings in the form of a word lattice.

4. The method of claim 1 wherein the step of selecting further comprises utilizing the finite state machines to derive phrases from the words contained in the candidate word strings and compute a cost for the derived phrases, wherein the cost relates to the degree of correspondence betweeen the derived phrase and the language represented by the signal.

5. The method of claim 4 wherein a lower cost indicates a greater degree of correspondence.

6. The method of claim 5 wherein the step of selecting further comprises determining the lowest cost phrase.

7. The method of claim 4 wherein the cost of a phrase is based on probabilities, wherein less probable word associations result in higher costs.

8. The method of claim 4 wherein costs are applied incrementally as phrases are derived.

9. The method of claim 1 wherein the language to be recognized is spoken and the step of generating candidate word strings further comprises applying an acoustic model.

10. A computer-readable storage medium comprising encoded computer-readable program instructions for use in conjunction with a programmable computer, which instructions cause the computer to select a language string from a plurality of language string hypotheses, the selected string providing the best correspondence to a signal representative of language, wherein such selection results from the action of a plurality of finite state machines capable of recognizing a pair of sequences, one sequence scanned leftwards, the other scanned rightwards through a data structure based on the plurality of language string hypotheses.

11. The computer-readable storage medium of claim 10 wherein the data structure is a phrase lattice comprised of phrases formed by the plurality of finite state machines.

12. The computer-readable storage medium of claim 10 wherein the language recognition system is a speech recognition system, the language string hypotheses are presented in the form of a word lattice and wherein the finite state machines that are acting correspond to the words in the word lattice.

13. A method for selecting a word string from a plurality of word string hypotheses, wherein the word string hypotheses are derived from an input signal representative of language and the selected word string best represents the language, comprising the steps of:

(a) activating state machines that correspond to the words in the word string hypotheses, wherein the activated state machines are selected from a plurality of such state machines defining a lexicon, wherein each of the activated state machines are capable of recognizing a pair of sequences, one sequence scanned leftwards, the other scanned rightwards, and further wherein each state machine is characterized by an initial state;

(b) generating a first plurality of phrase records, wherein, a phrase record is generated for each word in the word string hypotheses and each phrase record is characterized by a word, a state machine, the initial state, and a cost;

(c) generating a phrase lattice by forming a data structure comprised of the phrase records of step (b);

(d) generating a plurality of extended phrase records, wherein an extended phrase record is formed when a phrase record within the phrase lattice consumes an adjacent phrase record in the phrase lattice by a state machine transition, wherein, the extended phrase record;

contains the words of both the phrase record and the adjacent phrase record, and is characterized by the state machine of the consuming phrase record,

a new state corresponding to the transition of the state machine, and

a new cost, wherein,

the new cost is the sum of the costs of the consumed phrase and the consuming phrase, a cost associated with the state machine transition of the consuming phrase and a cost associated with a stop undertaken by the consumed state machine, and a cost pertaining to an association between the words in the consumed and consuming phrase records;

(e) adding the extended phrase record to the phrase lattice if the new cost of the extended phrase record is lower than a reference phrase record cost;

(f) repeating steps (d) and (e) wherein a phrase record can consume an adjacent phrase record until all phrase records have been fully extended and wherein the reference phrase record cost is updated by the extended phrase records added to the phrase lattice; and

(g) selecting the lowest cost phrase record spanning the entire input signal.