Minimum bayesian risk methods for automatic speech recognition

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.