Scoring and re-scoring dynamic time warping of speech

• US 7,085,717 B2
• Filed: 05/21/2002
• Issued: 08/01/2006
• Est. Priority Date: 05/21/2002
• Status: Expired due to Fees

• Current Assignee: Nytell Software LLC (Intellectual Ventures LLC)
• Original Assignee: ThinkEngine Networks, Inc.
• Inventors: Reddy, Harinath K., Kepuska, Veton Z.
• Primary Examiner(s): Storm, Donald L.
• Application Number:
  US10/152,095
• Publication Number:
  US 20030220789A1
• Time in Patent Office: 1,533 Days
• Field of Search: 704/241, 704/242, 704/243, 704/236, 704/238, 704/239
• US Class Current: 704/241
• 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 and a first order of the template vectors, and

measuring second distances between (a) vectors belonging to the set of vectors that represent the utterance and (b) 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,

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

in which the measure of first distances is outside of a pre-specifled threshold, and the measure of second distances indicates that the template represents an out-of-vocabulary utterance.

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 also including 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 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.

8. 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 and a first order of the template vectors, and

measuring second distances between (a) vectors belonging to the set of vectors that represent the utterance and (b) 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,

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

in which the method also includes using the measured second distances to reject the template as a match for the utterance even though the first distances imply a match.

9. 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 and a first order of the template vectors, and

measuring second distances between (a) vectors belonging to the set of vectors that represent the utterance and (b) 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,

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

in which the measuring of the first distances is done in parallel with the measuring of the second distances.

10. 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 and a first order of the template vectors, and

measuring second distances between (a) vectors belonging to the set of vectors that represent the utterance and (b) 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,

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,

the method 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.

12. 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 and a first order of the template vectors, and

measuring second distances between (a) vectors belonging to the set of vectors that represent the utterance and (b) 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,

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,

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

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,

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

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

14. The method of claim 13 in which the matching decision is based on the spikiness of the distribution.

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

16. 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 and a first order of the template vectors, and

measuring second distances between (a) vectors belonging to the set of vectors that represent the utterance and (b) 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,

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,

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

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.

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

18. 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 and a first order of the template vectors, and

measuring second distances between (a) vectors belonging to the set of vectors that represent the utterance and (b) 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,

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,

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 a 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.

19. A method comprising receiving an utterance, forming a time-ordered series of vectors representing 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 additionally 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 utterance vectors, and

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

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.