Minimum bayesian risk methods for automatic speech recognition

• US 9,123,333 B2
• Filed: 02/20/2013
• Issued: 09/01/2015
• Est. Priority Date: 09/12/2012
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Amarilli, Antoine, Mohri, Mehryar, Allauzen, Cyril
• Primary Examiner(s): SINGH, SATWANT K
• Application Number:
  US13/771,934
• Publication Number:
  US 20140303973A1
• Time in Patent Office: 923 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G10L 15/08 Speech classification or search

Abstract

A hypothesis space of a search graph may be determined. The hypothesis space may include n hypothesis-space transcriptions of an utterance, each selected from a search graph that includes t>n transcriptions of the utterance. An evidence space of the search graph may also be determined. The evidence space may include m evidence-space transcriptions of the utterance that are randomly selected from the search graph, where t>m. For each particular hypothesis-space transcription in the hypothesis space, an expected word error rate may be calculated by comparing the particular hypothesis-space transcription to each of the evidence-space transcriptions. Based on the expected word error rates, a lowest expected word error rate may be obtained, and the particular hypothesis-space transcription that is associated with the lowest expected word error rate may be provided.

Claims

1. A method comprising:

selecting, by a computing device, n hypothesis-space transcriptions of an utterance from a search graph that includes t>

n transcriptions of the utterance, wherein selecting the n hypothesis-space transcriptions comprises determining n best transcriptions of the utterance according to a maximum a posteriori (MAP) technique;

randomly selecting m evidence-space transcriptions of the utterance from the search graph, wherein t>

m;

for each particular hypothesis-space transcription of the n hypothesis-space transcriptions, calculating an expected word error rate by comparing the particular hypothesis-space transcription to the randomly selected m evidence-space transcriptions;

based on the expected word error rates, determining a lowest expected word error rate; and

providing the particular hypothesis-space transcription that is associated with the lowest expected word error rate.

2. The method of claim 1, wherein comparing the particular hypothesis-space transcription to the randomly selected m evidence-space transcriptions comprises, for each particular evidence-space transcription of the selected m evidence-space transcriptions:

based on the utterance, determining a probability that the particular evidence space transcription is a correct transcription of the utterance;

determining an edit distance between the particular hypothesis-space transcription and the particular evidence space transcription; and

calculating a product of the probability and the edit distance.

3. The method of claim 2, wherein the edit distance is a Levenshtein edit distance.

4. The method of claim 2, wherein determining the edit distance comprises:

factoring an edit transducer in the tropical semiring into a left-half transducer and a right-half transducer, wherein the edit transducer includes a finite-state transducer that maps edit operations to associated costs;

composing, into a first composed transducer, at least one of the n hypothesis space transcriptions with the left-half transducer;

composing, into a second composed transducer, the right-half transducer with an evidence space transducer, wherein the evidence space transducer represents the m evidence-space transcriptions; and

composing the first composed transducer and the second composed transducer.

5. The method of claim 2, wherein determining the edit distance comprises:

factoring an edit transducer in the log semiring into a left-half transducer and a right-half transducer, wherein the edit transducer includes a finite-state transducer that maps edit operations to associated costs;

composing, into a first composed transducer, a hypothesis space transducer with the left-half transducer, wherein the hypothesis space transducer represents the n hypothesis space transcriptions;

composing, into a second composed transducer, the right-half transducer with an evidence space transducer, wherein the evidence space transducer represents the m evidence-space transcriptions; and

composing the first composed transducer and the second composed transducer.

6. The method of claim 2, wherein the expected word error rate is the sum of each of the products associated with the particular evidence-space transcriptions.

7. The method of claim 1, wherein the search graph comprises a directed acyclic graph, each edge of the directed acyclic graph associated with a probability, and wherein randomly selecting the m evidence-space transcriptions from the search graph comprises traversing the directed acyclic graph from a source node to a terminal node by repeatedly selecting edges according to the probability associated with each edge.

8. The method of claim 1 further comprising:

receiving a representation of the utterance from a client device, wherein providing the particular hypothesis-space transcription that is associated with the lowest expected word error rate comprises providing the particular hypothesis-space transcription that is associated with the lowest expected word error rate to the client device.

9. The method of claim 1, wherein providing the particular hypothesis-space transcription that is associated with the lowest expected word error rate comprises providing the particular hypothesis-space transcription that is associated with the lowest expected word error rate on an output display of the computing device.

10. The method of claim 1, wherein the search graph comprises a search graph finite state transducer (FST), and wherein the search graph FST comprises a composition of a language model FST and a dictionary FST.

11. An article of manufacture including a non-transitory computer-readable medium, having stored thereon program instructions that, upon execution by a computing device, cause the computing device to perform operations comprising:

selecting n hypothesis-space transcriptions of an utterance from a search graph that includes t>

n transcriptions of the utterance, wherein selecting the n hypothesis-space transcriptions comprises determining n best transcriptions of the utterance according to a maximum a posteriori (MAP) technique;

randomly selecting m evidence-space transcriptions of the utterance from the search graph, wherein t>

m;

for each particular hypothesis-space transcription of the selected n hypothesis-space transcriptions, calculating an expected word error rate by comparing the particular hypothesis-space transcription to the randomly selected m evidence-space transcriptions;

based on the expected word error rates, determining a lowest expected word error rate; and

providing the particular hypothesis-space transcription that is associated with the lowest expected word error rate.

12. The article of manufacture of claim 11, wherein comparing the particular hypothesis-space transcription to the evidence-space transcriptions comprises, for each particular evidence-space transcription of the selected m evidence-space transcriptions:

based on the utterance, determining a probability that the particular evidence space transcription is a correct transcription of the utterance;

determining an edit distance between the particular hypothesis-space transcription and the particular evidence space transcription; and

calculating a product of the probability and the edit distance.

13. The article of manufacture of claim 12, wherein the edit distance is a Levenshtein edit distance.

14. The article of manufacture of claim 12, wherein the expected word error rate is the sum of each of the products associated with the particular evidence-space transcriptions.

15. The article of manufacture of claim 11, wherein the search graph comprises a directed acyclic graph, each edge of the directed acyclic graph associated with a probability, and wherein randomly selecting the evidence-space transcriptions from the search graph comprises traversing the directed acyclic graph from a source node to a terminal node by repeatedly selecting edges according to the probability associated with each edge.

16. A computing device comprising:

at least one processor;

data storage; and

program instructions stored in the data storage that, when executed by the processor, cause the computing device to perform operations comprising;

selecting n hypothesis-space transcriptions of an utterance from a search graph that includes t>

n transcriptions of the utterance, wherein selecting the n hypothesis-space transcriptions comprises determining n best transcriptions of the utterance according to a maximum a posteriori (MAP) technique;

randomly selecting m evidence-space transcriptions of the utterance from the search graph, wherein t>

m;

for each particular hypothesis-space transcription of the selected n hypothesis-space transcriptions, calculating an expected word error rate by comparing the particular hypothesis-space transcription to the randomly selected m evidence-space transcriptions;

based on the expected word error rates, determining a lowest expected word error rate; and

providing the particular hypothesis-space transcription that is associated with the lowest expected word error rate.

17. The computing device of claim 16, wherein comparing the particular hypothesis-space transcription to each of the evidence-space transcriptions comprises, for each particular evidence-space transcription of the selected m evidence-space transcriptions:

based on the utterance, determining a probability that the particular evidence space transcription is a correct transcription of the utterance;

determining an edit distance between the particular hypothesis-space transcription and the particular evidence space transcription; and

calculating a product of the probability and the edit distance.

18. The computing device of claim 16, wherein the search graph comprises a directed acyclic graph, each edge of the directed acyclic graph associated with a probability, and wherein randomly selecting the evidence-space transcriptions from the search graph comprises traversing the directed acyclic graph from a source node to a terminal node by repeatedly selecting edges according to the probability associated with each edge.