Leveraging back-off grammars for authoring context-free grammars

• US 8,862,468 B2
• Filed: 12/22/2011
• Issued: 10/14/2014
• Est. Priority Date: 12/01/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Paek, Timothy, Chickering, Max, Badger, Eric
• Primary Examiner(s): WOZNIAK, JAMES S
• Application Number:
  US13/334,580
• Publication Number:
  US 20120095752A1
• Time in Patent Office: 1,027 Days
• Field of Search: 704/1, 704/9, 704/44, 704243-244, 704/257
• US Class Current: 704/244
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars

Abstract

A system and method of refining context-free grammars (CFGs). The method includes deriving back-off grammar (BOG) rules from an initially developed CFG and utilizing the initial CFG and the derived BOG rules to recognize user utterances. Based on a response of the initial CFG and the derived BOG rules to the user utterances, at least a portion of the derived BOG rules are utilized to modify the initial CFG and thereby produce a refined CFG. The above method can carried out iterativey, with each new iteration utilizing a refined CFG from preceding iterations.

Claims

1. A method of refining a context-free grammar, the method comprising:

generating backoff grammar rules from rules of an initial context-free grammar, each backoff grammar rule being generated based on at least one keyword identified from the initial context-free grammar; and

recursively modifying the initial context-free grammar using a computer processing unit, wherein recursively modifying comprises;

obtaining a relined context-free grammar by modifying the initial context-free grammar,during a first iteration, based at least in part on recognition of utterances using the backoff grammar rules;

determining a recognition efficiency of the refined context-free grammar and the hackoff grammar rules to the utterances; and

during each of at least one additional iteration, further modifying the refined context-free grammar based at least in part on recognition of utterances using the refined context free grammar and backoff grammar rules until the refined context-free grammar and the backoff grammar rules meet a threshold level of recognition efficiency.

2. The method of claim 1, wherein modifying the initial context-free grammar comprises selecting, based at least in part on a statistic derived from application of the backoff grammar rules, a sub-set of a collection of utterances for transcription, the sub-set being fewer than all of the utterances in the collection.

3. The method of claim 2, wherein the statistic is indicative of a frequency with which one of the backoff grammar rules has been identified as a top recognition.

4. The method of claim 2, wherein the statistic is indicative of a frequency of selection of a particular one of the backoff grammar rules.

5. The method of claim 2, wherein the statistic is indicative of how successful or unsuccessful a particular one of the backoff grammar rules was in terms of handling a particular out of grammar utterance in the collection.

6. The method of claim 2, wherein the statistic is indicative of a relative effectiveness of a particular one of the backoff grammar rules.

7. The method of claim 2, further comprising utilizing a dictation grammar to automatically transcribe the utterances that are selected for transcription.

8. The method of claim 1, wherein recursively modifying the initial context free grammar comprises manually adjusting the initial context free grammar based on transcriptions of the utterances selected for transcription.

9. The method of claim 1, wherein reclusively modifying the initial context free grammar comprises automatically adjusting the initial context free grammar based on transcriptions of the utterances selected for transcription.

10. The method of claim 9, wherein automatically adjusting comprises automatically adjusting based at least in part on a determined minimal edit distance.

11. An adaptive speech recognition system comprising:

one or more computer processors;

a language model component comprising a language model that includes a context-free grammar (CFG) and a plurality of back-off grammar (BOG) rules, the BOG rules each comprising a rule for producing a recognition result from a user utterance and being derived from one or more grammar rules of the CFG that specify words and patterns of words, wherein the language model component obtains recognition results, using at least one of the computer processors, for user utterances by processing the user utterances with the CFG during a first pass and then processing a portion of the use utterances that comprise out of grammar utterances with the BOG rules during a second pass; and

a grammar refining component that iteratively modifies the language model, using at least one of the computer processors, based on a data indicator that identifies the most frequently occurring out of grammar utterances handled by the BOG rules, wherein modifying the language model comprises incorporating the most frequently occurring out of grammar utterances into the CFG.

12. The system of claim 11, wherein iteratively modifying the language model comprises manually adjusting the CFG based on a selected set of transcriptions of the out of grammar utterances.

13. The system of claim 11, wherein iteratively modifying the language model comprises automatically adjusting the CFG based on a selected set of transcriptions of the out of grammar utterances.

14. The system of claim 13,wherein the selected set of transcription is selected based in part on the data indicator.

15. The system of claim 11, wherein iteratively modifying the language model comprises automatically adjusting the CFG used on a determination of minimal edit distance.

16. The system of claim 11, wherein the CFG includes keywords, slots, and carrier phrases.