Melodis crystal decoder method and device for searching an utterance by accessing a dictionary divided among multiple parallel processors
View Patent ↗The technology disclosed relates to a system and method for fast, accurate and parallelizable speech search, called Crystal Decoder. It is particularly useful for search applications, as opposed to dictation. It can achieve both speed and accuracy, without sacrificing one for the other. It can search different variations of records in a reference database without a significant increase in elapsed processing time. This is accomplished by first accessing the database, and for each word representation in the database, searching an utterance for likely instances of the word representation utilizing multiple parallel processors. Even the main decoding part can be parallelized as the number of words increase to maintain a fast response time.
1. A method of electronically processing an utterance to locate candidate words at arbitrary positions within the utterance, including:
accessing a dictionary of word sets each comprising multiple word representations;
for each word representation, searching the utterance for likely instances of the word representation and scoring each likely word instance for a probability of a match to the word representation;
wherein, the utterance is searched by multiple processors operating on the multiple word sets; and
reporting at least a subset of likely word instances and respective probability scores for further electronic processing.
2. The method of claim 1 , further including applying dynamic programming to phoneme representations of the utterance and the word representation during the searching and/or scoring.
3. The method of claim 2 , further including analyzing the utterance against one or more phoneme graphs that represent allowable transitions between successive phonemes, wherein the allowable transitions are constrained by a language model based on the word representations in the dictionary.
4. The method of claim 3 , further including training the phoneme graphs against audio data.
5. The method of claim 4 , wherein the trained phoneme graphs represent alternative pronunciations by more than 100 speakers.
6. The method of claim 2 , further including constructing the phoneme representations for the word representations as one or more phoneme graphs.
7. The method of claim 6 , wherein the scoring uses probabilities derived from training the phoneme graphs against audio data and not probabilities derived from a language model.
8. The method of claim 2 , wherein the scoring further includes normalizing partial scores accumulated while applying the dynamic programming, whereby the scores for the likely word instances can be meaningfully compared between the likely word instances that match shorter and longer parts of the utterance.
9. The method of claim 1 , applied to matching the likely word instances to catalog entries, the method further including:
accessing a catalog of phrases sets each comprising multiple phrase representations;
for each phrase representation, searching the reported subset of likely word instances for likely occurrences of each phrase and
scoring each likely phrase occurrence for a probability of a match between the phrase and the utterance;
wherein the subset of likely word instances is searched by multiple processors operating on the multiple phrase sets; and
reporting at least a subset of likely phrase occurrences and respective probability scores for further processing.
10. The method of claim 9 , wherein the phrases include ordered words organized into one or more phrase graphs.
11. The method of claim 10 , wherein at least some of the items in the catalog are represented by multiple phrases with different word orderings.
12. The method of claim 11 , wherein the phrase graphs represent all phrases for which items from the catalog will be selected.
13. The method of claim 11 , wherein the phrase graphs include edges that indicate deleted words and penalties associated with deleting words from phrases.
14. The method of claim 9 , further including applying dynamic programming to scoring the phrases against ordered, non-overlapping sequences of the likely word instances.
15. The method of claim 14 , further including splitting a sound in the utterance shared by successive likely word instances, thereby eliminating overlap.
16. The method of claim 14 , further including eliminating from consideration phrases that start with one or more words not found in the subset of likely word instances.
17. The method of claim 16 , further including splitting a sound in the utterance shared by successive likely word instances, thereby eliminating overlap.
18. The method of claim 9 , wherein each likely word instance is represented by at least a start frame, a first end frame, a last end frame and multiple probability scores when the first end frame and the last end frame are different, further including using overlap between likely word instances when searching for the phrase to eliminate from consideration some of the likely word instances.
19. The method of claim 1 , further including applying dynamic programming to hidden Markov models of the utterance and of the word representation during the searching and/or scoring.
20. The method of claim 19 , wherein the hidden Markov models represent phonemes.
21. The method of claim 19 , wherein the hidden Markov models for the word representations model words without intermediate phoneme representations.
22. The method of claim 9 , wherein the scoring further includes normalizing partial scores accumulated while applying the dynamic programming, whereby the scores for the likely word instances can be meaningfully compared between the likely word instances that match shorter and longer parts of the utterance.
23. The method of claim 1 , wherein each likely word instance is represented by at least a start frame, a first end frame, a last end frame and multiple probability scores when the first end frame and the last end frame are different.
24. The method of claim 1 , further including reporting for further processing at least three times as many likely word instances as there are distinct words in the dictionary.
25. A method of matching candidate words in an utterance to catalog entries, the method including:
searching the utterance for likely instances of word representations and scoring each likely word instance for a probability of a match to the word representations;
accessing a catalog of phrases sets each comprising multiple phrase representations;
for each phrase representation, searching a set of likely word instances for likely phrase occurrences and
scoring each likely phrase occurrence for a probability of a match between the phrase and the utterance;
wherein the set of likely word instances is searched by multiple processors operating on the multiple phrase sets; and
reporting at least a subset of likely phrase occurrences and respective probability scores for further processing.
26. A device that of electronically processes an utterance to locate candidate words at arbitrary positions within the utterance, including:
first multiple processors;
memory coupled to the processors;
a dictionary of word representations stored a first memory, the dictionary of word sets each comprising multiple word respresentations;
a word searching-scoring module that processes a particular word set, the word searching-scoring module adapted to, for each word representations
search the utterance stored in a second memory for likely instances of the word representation and
score each likely word instance for a probability of a match to the word representation;
further including a first coordination module adapted to assign multiple instances of the word searching-scoring modules to run on the first multiple processors; and
a first reporting module coupled in communication with the first coordination module and/or the word searching-scoring modules that reports at least a subset of likely word instances and respective probability scores for further electronic processing.
27. The device of claim 26 , extended to process the likely word instances against catalog entries, including:
second multiple processors coupled to the memory;
a catalog of phrases that represent items, stored a third memory, the catalog divided into multiple phrase sets each comprising multiple phase representations;
a phrase searching-scoring module that, for each phrase resprentation
searches the reported subset of likely word instances for likely phrase occurrences and
scores each likely phrase occurrence for a probability of a match between the phrase and the utterance;
further including a second coordination module adapted to assign multiple instances of the phrase searching-scoring module to run on the second multiple processors; and
a second reporting module coupled in communication with the second coordination module and/or the phrase searching-scoring modules that reports at least a subset of likely phrase occurrences and respective probability scores for further processing.
28. An article of manufacture including a computer readable non-transitory storage media containing at least instructions to carry out a method of electronically processing an utterance to locate candidate words at arbitrary positions within the utterance, including:
accessing a dictionary of word sets each comprising multiple word representations;
for each word representation,searching the utterance for likely instances of the word representation and scoring each likely word instance for a probability of a match to the word representation;
wherein, the utterance is searched by multiple processors operating on the multiple word sets; and
reporting at least a subset of likely word instances and respective probability scores for further electronic processing.
29. An article of manufacture including a computer readable non-transitory storage media containing at least instructions to carry out a method of matching candidate words in an utterance to catalog entries, the method including:
searching the utterance for likely instances of word representations and scoring each likely word instance for a probability of a match to the word representations;
accessing a catalog of phrases sets each comprising multiple phrase representations;
for each phrase representation, searching a set of likely word instances for likely occurrences of each phrase and
scoring each likely phrase occurrence for a probability of a match between the phrase and the utterance;
wherein the set of likely word instances is searched by multiple processors operating on the multiple phrase sets; and
reporting at least a subset of likely phrase occurrences and respective probability scores for further processing.
30. A method of matching candidate words in an utterance to items in catalog entries, the method including:
accessing a phrase dictionary representing catalog entries for the items, wherein all of the phrases used to select the items are represented in the phrase dictionary;
receiving candidate phoneme sequences tentatively recognized from the utterance, with confidence scores;
traversing parts of the phrase dictionary, in parallel using multiple processors, locating candidate phrases that match sequences within the utterance of non-overlapping candidate phonemes;
calculating phrase confidence scores for the candidate phrases; and
reporting at least a subset of the candidate phrase and respective candidate phrase scores for further processing.
31. The method of claim 30 , further including using the candidate phrase confidence scores to select one or more items based on their catalog entries.
32. The method of claim 30 , wherein the phrase dictionary is represented by phase graphs with optional edges that indicate words subject to deletion.
33. The method of claim 30 , wherein the candidate words are constrained by words and phrases in the catalog entries.