Non-leaf node penalty score assignment system and method for improving acoustic fast match speed in large vocabulary systems

• US 6,275,801 B1
• Filed: 11/03/1998
• Issued: 08/14/2001
• Est. Priority Date: 11/03/1998
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Novak, Miroslav, Picheny, Michael
• Primary Examiner(s): SMITS, TALIVALDIS IVARS
• Application Number:
  US09/184,870
• Time in Patent Office: 1,015 Days
• Field of Search: 704/252, 704/255
• US Class Current: 704/252
• CPC Class Codes: G10L 15/08 Speech classification or search

Abstract

A method for fast match processing, comprising two stages, a pre-processing stage and an on-line stage. The pre-processing stage comprises the steps of computing an a-priori probability of occurrence for each word from an acoustic vocabulary; deriving a penalty score for each word from said acoustic vocabulary based on each words a-priori probability of occurrence in an input text. The on-line stage operates on an input text stream, comprising the steps of, computing a path score for each word from said input text; combining the computed path score with the derived penalty score to form a combined score and testing the combined score against a threshold to determine top ranking candidate words.

Claims

1. In a speech recognition system a method for fast match processing comprising the steps of:

(a) computing an a-priori probability of occurrence for each word from an acoustic vocabulary;

(b) deriving a penalty score for each word from said acoustic vocabulary based on each word'"'"'s a-priori probability of occurrence in an input spoken text;

 

analyzing said input spoken text for;

(c) computing a path score for each word from said input spoken text, wherein step (c) further comprises the step of constructing an asynchronous tree structure comprising a plurality of branches, leaf nodes, and non-leaf nodes, each leaf node representing one of said words from the input spoken text and each non-leaf node representing a single phone of one or more said words from the input spoken text, wherein each of said leaf nodes is assigned a penalty score in accordance with the word associated with the leaf node and non-leaf nodes are assigned penalty scores derived from leaf node penalty scores, the step of assigning penalty scores for non-leaf nodes from leaf node penalty scores further comprising;

identifying a non-leaf node in the tree that is a parent node to at least one leaf node;

determining whether there is more than one identified child leaf node;

based on the determination step, whenever there is more than one identified child leaf node, choosing the penalty score associated with the child leaf node whose penalty score is most positive, otherwise, whenever there is only one child leaf node, selecting that child leaf node'"'"'s penalty score; and

(d) combining the computed path score with the derived penalty score to form a combined score and testing the combined score against a threshold to determine top ranking candidate words.

2. The method of claim 1, wherein step (a) further comprises sorting the acoustic vocabulary into a sorted list in accordance with each vocabulary word'"'"'s a-priori probability.

3. The method of claim 2, wherein step (b) further comprises deriving said penalty scores as a function of each words position in the sorted list.

4. The method of claim 3, wherein said function is a non-decreasing function.

5. The method of claim 1, wherein step (c) further comprises performing a depth first traversal on said asynchronous tree structure.

6. A computer program device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for fast match processing, comprising the steps of:

(a) computing an a-priori probability of occurrence for each word from an acoustic vocabulary;

(b) deriving a penalty score for each word from said acoustic vocabulary based on each word'"'"'s a-priori probability of occurrence in an input spoken text;

 

analyzing said input spoken text for;

(c) computing a path score for each word from said input spoken text, wherein step (c) further comprises the step of constructing an asynchronous tree structure comprising a plurality of branches, leaf nodes, and non-leaf nodes, each leaf node representing one of said words from the input spoken text and each non-leaf node representing a single phone of one or more said words from the input spoken text, wherein each of said leaf nodes is assigned a penalty score in accordance with the word associated with the leaf node and non-leaf nodes are assigned penalty scores derived from leaf node penalty scores, the step of assigning penalty scores for non-leaf nodes from leaf node penalty scores further comprising;

identifying a non-leaf node in the tree that is a parent node to at least one leaf node;

determining whether there is more than one identified child leaf node;

based on the determination step, whenever there is more than one identified child leaf node, choosing the penalty score associated with the child leaf node whose penalty score is most positive, otherwise, whenever there is only one child leaf node, selecting that child leaf node'"'"'s penalty score; and

(d) combining the computed path score with the derived penalty score to form a combined score and testing the combined score against a threshold to determine top ranking candidate words.

7. The computer program device of claim 6, wherein step (a) further comprises sorting the acoustic vocabulary into a sorted list in accordance with each vocabulary word'"'"'s a-priori probability.

8. The computer program device of claim 7, wherein step (b) further comprises deriving said penalty scores as a function of each words position in the sorted list.

9. The computer program device of claim 8, wherein said function is a non-decreasing function.

10. The method of claim 6, wherein step (c) further comprises performing a depth first traversal on said asynchronous tree structure.