Dynamic time warping of speech

• US 20030220789A1
• Filed: 05/21/2002
• Published: 11/27/2003
• Est. Priority Date: 05/21/2002
• Status: Active Grant

• Current Assignee: Nytell Software LLC (Intellectual Ventures LLC)
• Original Assignee: ThinkEngine Networks, Inc.
• Inventors: Kepuska, Veton K.
• Granted Patent: US 7,085,717 B2
• Time in Patent Office: Days
• US Class Current: 704/238
• CPC Class Codes: G10L 15/12 using dynamic programming techniques, e.g. dynamic time warping [DTW]

Abstract

A method includes (i) measuring first distances between (a) vectors belonging to a set of vectors that represent an utterance and (b) vectors belonging to a set of vectors that represent a template, the measuring being done in accordance with a first order of the utterance vectors a first order of the template vectors, and (ii) measuring second distances between (a) individual vectors belonging to the set of vectors that represent the utterance and (b) individual vectors belonging to the set of vectors that represent the template, the measuring being done in accordance with a second order of the utterance vectors and a second order of the template vectors, and (iii) in which the first template vector order and the second template vector order are different and/or the first utterance vector order and the second utterance vector order are different. In another aspect, a method includes measuring distances between vectors that represent an utterance and vectors that represent a template, generating information indicative of how well the vectors of the utterance match the vectors of the template, and making a matching decision based on the measured distances and on the generated information.

Claims

1. A method comprising

measuring first distances between (a) vectors belonging to a set of vectors that represent an utterance and (b) vectors belonging to a set of vectors that represent a template, the measuring being done in accordance with a first order of the utterance vectors a first order of the template vectors, and

measuring second distances between (a) individual vectors belonging to the set of vectors that represent the utterance and (b) individual vectors belonging to the set of vectors that represent the template, the measuring being done in accordance with a second order of the utterance vectors and a second order of the template vectors,

and in which the first template vector order and the second template vector order are different and/or the first utterance vector order and the second utterance vector order are different.

2. The method of claim 1 also including using the first distances and the second distances in connection with a speech processing operation.

3. The method of claim 1 in which the first template order is the reverse of the second template order or the first utterance vector order is the reverse of the second utterance vector order.

4. The method of claim 1 in which the matching comprises

relative scoring of the utterance with respect to the template and with respect to other templates.

5. The method of claim 1 in which the first utterance order and the first template order are based on original orders of the utterance vectors and the template vectors.

6. The method of claim 1 in which the measuring of first distances and the measuring of second distances are performed with respect to multiple templates.

7. The method of claim 1 in which the measure of first distances is outside of a pre-specified threshold, and the measure of second distances indicates that the template represents an out-of-vocabulary utterance.

8. The method of claim 1 also including using the measured second distances to reject the template as a match for the utterance even though the first distances imply a match.

9. The method of claim 1 in which the measuring of the first distances is done in parallel with the measuring of the second distances.

10. The method of claim 1 also including measuring third distances between (a) individual vectors belonging to the set of vectors that represent the utterance and (b) individual vectors belonging to the set of vectors that represent the template, the measuring being done in accordance with a third order of the utterance vectors and a third order of the template vectors.

11. The method of claim 10 in which the second distances are measured with the template vectors in an original order and the utterance vectors in a reversed order, and the third distances are measured with the utterance vectors in an original order and the template vectors in a reversed order.

18. The method of claim 1 also including

generating information indicative of how well the vectors of the utterance match the vectors of the template, and

making a matching decision based on the measured distances and on the generated information.

19. The method of claim 18 in which the generating of information includes producing a distribution of values associated with the vectors of the template, the values indicating the frequency with which reference template vectors produce a minimum local distance in matching with vectors of the utterance.

20. The method of claim 19 in which the matching decision is based on the extent to which the distribution is non-uniform.

21. The method of claim 20 in which the matching decision is based on the spikiness of the distribution.

22. The method of claim 20 in which the matching decision is based on how well the entire set of vectors representing the template are used in the matching.

23. The method of claim 18 in which the measuring of distances includes generating a raw dynamic time warping score and rescoring the score based on the information indicative of how well the vectors of the utterance match the vectors of the template.

24. The method of claim 23 in which the rescoring is based on both the spikiness of the distribution and the on how well the entire set of vectors representing the template are used in the matching.

25. A method of claim 1 also including

producing a distribution of values associated with the vectors of the template, the values indicating the frequency with which reference template vectors produce a minimum local distance in matching with vectors of the utterance, and

rescoring the score based on a spikiness of the distribution and on how well the entire set of vectors representing the template are used in the matching.

12. A method comprising

receiving an utterance,

forming a time-ordered series of vectors repesenting the utterance,

using dynamic time warping to score the utterance vectors against time-ordered series of vectors representing templates of possible utterances, the scoring being done using the template vectors and utterance vectors in their time order,

using dynamic time warping to also score the utterance vectors against the vectors representing templates, the additional scoring being done using a different time-order of vectors of one or both of the template vectors, and

selecting one of the templates as a match for the utterance based on both the scoring and the additional scoring.

13. The method of claim 12 in which the different time ordering comprises the reverse of time ordering.

14. The method of claim 12 in which the selecting includes removing from consideration templates for which the scoring indicates a match and the additional scoring indicates that the matching template is out of vocabulary.

15. Apparatus comprising

an input port connected to receive digitized speech, and

a speech recognizer configured to

measuring first distances between (a) vectors belonging to a set of vectors that represent an utterance and (b) vectors belonging to a set of vectors that represent a template, the measuring being done in accordance with a first order of the utterance vectors a first order of the template vectors, and

measuring second distances between (a) individual vectors belonging to the set of vectors that represent the utterance and (b) individual vectors belonging to the set of vectors that represent the template, the measuring being done in accordance with a second order of the utterance vectors and a second order of the template vectors,

and in which the first template vector order and the second template vector order are different and/or the first utterance vector order and the second utterance vector order are different.

26. The apparatus of claim 15 in which the speech recognizer is also configured to

generate information indicative of how well the vectors of the utterance match the vectors of the template, and

make a matching decision based on the measured distances and on the generated information.

16. Apparatus comprising

means for receiving digitized speech,

means for recognizing speech including

means for measuring first distances between (a) vectors belonging to a set of vectors that represent an utterance and (b) vectors belonging to a set of vectors that represent a template, the measuring being done in accordance with a first order of the utterance vectors a first order of the template vectors, and

means for measuring second distances between (a) individual vectors belonging to the set of vectors that represent the utterance and (b) individual vectors belonging to the set of vectors that represent the template, the measuring being done in accordance with a second order of the utterance vectors and a second order of the template vectors,

and in which the first template vector order and the second template vector order are different and/or the first utterance vector order and the second utterance vector order are different, and

means for providing an output matching utterance.

27. The apparatus of claim 16 also including

means for generating information indicative of how well the vectors of the utterance match the vectors of the template, and

means for making a matching decision based on the measured distances and on the generated information.

17. A medium carrying instructions adapted to cause a machine to

measuring first distances between (a) vectors belonging to a set of vectors that represent an utterance and (b) vectors belonging to a set of vectors that represent a template, the measuring being done in accordance with a first order of the utterance vectors a first order of the template vectors, and

measuring second distances between (a) individual vectors belonging to the set of vectors that represent the utterance and (b) individual vectors belonging to the set of vectors that represent the template, the measuring being done in accordance with a second order of the utterance vectors and a second order of the template vectors,

and in which the first template vector order and the second template vector order are different and/or the first utterance vector order and the second utterance vector order are different.

28. The medium of claim 17 also including causing the machine to

generate information indicative of how well the vectors of the utterance match the vectors of the template, and

make a matching decision based on the measured distances and on the generated information.