System and Method for Detecting Repeated Patterns in Dialog Systems

• US 20090313016A1
• Filed: 06/13/2008
• Published: 12/17/2009
• Est. Priority Date: 06/13/2008
• Status: Active Grant

• Current Assignee: Robert Bosch GmbH
• Original Assignee: Robert Bosch GmbH
• Inventors: Cevik, Mert, Weng, Fuliang
• Granted Patent: US 8,140,330 B2
• Time in Patent Office: Days
• US Class Current: 704/241
• CPC Class Codes: G10L 15/12 using dynamic programming techniques, e.g. dynamic time warping [DTW]
• CPC Class Codes: G10L 15/22 Procedures used during a speech recognition process, e.g. man-machine dialogue

Abstract

Embodiments of a method and system for detecting repeated patterns in dialog systems are described. The system includes a dynamic time warping (DTW) based pattern comparison algorithm that is used to find the best matching parts between a correction utterance and an original utterance. Reference patterns are generated from the correction utterance by an unsupervised segmentation scheme. No significant information about the position of the repeated parts in the correction utterance is assumed, as each reference pattern is compared with the original utterance from the beginning of the utterance to the end. A pattern comparison process with DTW is executed without knowledge of fixed end-points. A recursive DTW computation is executed to find the best matching parts that are considered as the repeated parts as well as the end-points of the utterance.

Claims

1. A method of detecting repeated patterns in a dialog system, comprising:

receiving an initial utterance from a user in the dialog sequence as a set of test patterns;

receiving a correction utterance from the user;

segmenting the correction utterance into a set of reference patterns;

extracting feature vectors from the test patterns and the reference patterns;

comparing each test pattern with each reference pattern using a dynamic time warping process;

computing distance scores between each reference pattern and each test pattern; and

identifying test patterns with a distance score that is less than a defined distance threshold as a repeated pattern.

2. The method of claim 1 wherein the correction utterance is provided by the user in response to an output from the dialog system, and further wherein both the correction utterance and the initial utterance comprise spoken user input and the repeated patterns that are selected from the group consisting of:

words, syllables, and phrases.

3. The method of claim 2 wherein the segmenting step comprises:

identifying silence regions separating speech segments within the initial utterance;

extracting statistical characteristics of the silence regions using an endpoint detection process;

computing a zero-crossing rate threshold for the silence regions

computing an energy threshold for the speech segments;

determining if the length of a speech segment is less than a defined length threshold; and

saving a speech segment as a reference pattern if its length is less than the defined length threshold, or dividing the speech segment into two or more sub-segments if its length is greater than the defined length threshold.

4. The method of claim 3 wherein the defined length threshold is determined by a process comprising one of experimental determination, or theoretical calculation.

5. The method of claim 4 wherein the initial utterance and correction utterance are each defined by a set of feature parameters.

6. The method of claim 5 wherein the feature parameters comprise Mel frequency cepstral coefficients.

7. The method of claim 6 wherein the feature parameters comprise 13-dimension feature vectors generated at a defined frame rate.

8. The method of claim 7 wherein the frame rate comprises 100 frames per second.

9. The method of claim 6 further comprising applying a raised sine liftering function to control non-information bearing components of the cepstral coefficients.

10. The method of claim 1 further comprising:

defining reference and test pattern pairs for each possible combination of test and reference patterns;

recursively applying a dynamic time warping process on each reference and test pattern pairs;

defining a maximum reference pattern length; and

identifying matching patterns as reference patterns of a reference and test pattern pair with a distance score that is less than the defined maximum reference pattern length.

11. A method of repetition detection in a dialog system comprising:

receiving an initial user utterance as a first sequence of segments;

providing an interpretive output to the user based on the initial user utterance;

receiving a correction utterance in response to the interpretive output;

segmenting the correction utterance into a second sequence of segments;

aligning each segment from the second sequence with each segment from the first sequence;

determining a distance score for each segment from the first sequence with each segment from the second sequence;

comparing each distance score with a defined score threshold; and

identifying segments with a distance score below the defined score threshold as a repeated segment.

12. The method of claim 11 wherein each of the initial user utterance and the correction utterance comprises spoken user input and the segments are selected from the group consisting of:

words, syllables, and phrases.

13. The method of claim 12 wherein the step of segmenting the correction utterance comprises finding a word boundary for each segment, wherein a word boundary comprises an intersection of a silent section and a spoken section within the utterance.

14. The method of claim 13 further comprising defining a set of feature parameters for each of the first sequence of segments and the second sequence of segments.

15. The method of claim 13 wherein the feature parameters comprise Mel frequency cepstral coefficients.

16. A system for detecting repeated patterns in a dialog system, comprising:

a speech recognizer stage receiving an initial utterance from a user in the dialog sequence as a set of test patterns, and receiving a correction utterance from the user in response to an output from a response generator of the dialog system;

an event detector detecting the occurrence of repeated segments between the initial utterance and the correction utterance;

a segmentation component segmenting the correction utterance into a set of reference patterns;

a feature extraction component extracting feature vectors from the test patterns and the reference patterns; and

a pattern comparison component comparing each test pattern with each reference pattern using a dynamic time warping process, and computing distance scores between each reference pattern and each test pattern to identify test patterns with a distance score of less than a defined distance threshold as a repeated pattern.

17. The system of claim 16 further comprising a decision rule component defining the distance threshold.

18. The system of claim 17 wherein the initial utterance comprises spoken user input and the repeated patterns are selected from the group consisting of:

words, syllables, and phrases.

19. The method of claim 18 wherein the segmentation component step comprises:

means for identifying silence regions separating speech segments within the initial utterance;

means for extracting statistical characteristics of the silence regions using an endpoint detection process;

means for computing a zero-crossing rate threshold for the silence regions

means for computing an energy threshold for the speech segments;

means for determining if the length of a speech segment is less than a defined length threshold; and

means for saving a speech segment as a reference pattern if its length is less than the defined length threshold, or dividing the speech segment into two or more sub-segments if its length is greater than the defined length threshold.

20. The system of claim 19 wherein the initial utterance and correction utterance are each defined by a set of feature parameters.

21. The method of claim 20 wherein the feature parameters comprise Mel frequency cepstral coefficients.

22. The method of claim 21 wherein the pattern comparison component further comprises:

means for defining reference and test pattern pairs for each possible combination of test and reference patterns;

means for recursively applying a dynamic time warping process on each reference and test pattern pairs;

means for defining a maximum reference pattern length; and

means for identifying matching patterns as reference patterns of a reference and test pattern pair with a distance score that is less than the defined maximum reference pattern length.