Vocabulary-independent search of spontaneous speech

• US 20060116997A1
• Filed: 11/29/2004
• Published: 06/01/2006
• Est. Priority Date: 11/29/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Seide, Frank Torsten, Yu, Roger Peng
• Granted Patent: US 7,584,098 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G10L 15/04 Segmentation; Word boundary detection

Abstract

A method of identifying a location of a query string in an audio signal is provided. Under the method, a segment of the audio signal is selected. A score for a query string in the segment of the audio signal is determined by determining the product of probabilities of overlapping sequences of tokens. The score is then used to decide if the segment of the audio signal is likely to contain the query string.

Claims

1. A method of identifying a location of a query string in an audio signal, the method comprising:

selecting a segment of the audio signal;

determining a score for the query string in the segment of the audio signal by determining the product of probabilities of overlapping sequences of tokens; and

using the score to decide if the segment of the audio signal is likely to contain the query string.

2. The method of claim 1 further comprising selecting a plurality of segments of the audio signal, determining a score for the query string in each segment, and using the scores to rank the segments.

3. The method of claim 2 further comprising selecting at least one segment that ranks higher than another segment and searching the selected segment to identify at least one possible location of the query in the selected segment.

4. The method of claim 2 further comprising dividing an audio signal into segments of substantially similar durations.

5. The method of claim 4 wherein dividing the audio signal comprises identifying points of silence in the audio signal and dividing the audio signal at the points of silence.

6. The method of claim 4 wherein the step of dividing the audio signal is performed by a speech recognizer.

7. The method of claim 1 wherein the probabilities of overlapping sequences of tokens are determined from values stored in an index for the segment of the audio signal.

8. The method of claim 7 further comprising forming the index by first identifying a set of sequences of tokens found in a chosen set.

9. The method of claim 8 further comprising forming the chosen set using a background dictionary.

10. The method of claim 8 further comprising determining a set of backoff weights for sequences of tokens that are not found in the chosen set.

11. The method of claim 8 wherein at least one probability of an overlapping sequence of tokens is determined using a backoff weight.

12. The method of claim 7 further comprising constructing a lattice of possible token sequences that can represent the audio signal and using the lattice as the basis to form the index.

13. The method of claim 12 wherein forming the index further comprises determining a probability of a path through the lattice and using the probability to set the probability of a sequence of tokens.

14. The method of claim 1 wherein the probability of at least one overlapping sequence of tokens is estimated using the probability of a shorter sequence of tokens.

22. The method of claim 1 wherein the tokens comprise sub-word units.

23. The method of claim 22 wherein the tokens comprise phonemes.

24. The method of claim 1 wherein determining a score for the query string comprises determining a first score component for overlapping sequences of sub-word units and a second score component for overlapping sequences of words and combining the first score component and the second score component to form the score for the query string.

15. The method of 14 wherein the shorter sequence of tokens comprises a single token.

16. The method of claim 15 wherein the query string comprises multiple words and determining a score for the query string comprises multiplying a product of probabilities of overlapping sequences of tokens associated with a first word by a product of probabilities of overlapping sequences of tokens associated with a second word in the query string, and further by a probability for a unigram of silence.

17. The method of claim 16 further comprising determining a second score for the query string by determining a product of overlapping sequences of tokens associated with the first and second word while assuming no silence between the first and second word.

18. The method of claim 17 further comprising selecting one of the score and the second score as a final score for the query string in the segment.

19. The method of claim 17 further comprising combining the score and the second score to form a final score for the query string in the segment.

20. The method of claim 19 wherein combining the score and the second score comprises summing the score and the second score to form the final score.

21. The method of claim 20 wherein combining the score and the second score comprises forming a weighted sum of the score and the second score to form the final score.

25. A computer-readable medium having computer-executable instructions for performing steps comprising:

dividing a user query into a sequence of tokens;

using an index of token sub-sequences to identify probabilities for at least two sub-sequences of tokens in the sequence of tokens of the user query;

combining the identified probabilities together to form a score that indicates the likelihood of the user query appearing in a segment of an audio signal.

26. The computer-readable medium of claim 25 wherein using an index to identify probabilities for at least two sub-sequences comprises using the index to identify the probabilities of the at least two sub-sequences appearing in a segment of the audio signal.

27. The computer-readable medium of claim 26 wherein the probability of at least one sub-sequence is determined using a backoff weight and a probability of a portion of the sub-sequence.

28. The computer-readable medium of claim 25 wherein the user query comprises at least two words.

29. The computer-readable medium of claim 28 wherein dividing the user query into a sequence of tokens comprises dividing the user query into a separate sequence of tokens for each word in the query.

30. The computer-readable medium of claim 29 wherein using an index of token sub-sequences comprises identifying probabilities for sub-sequences of tokens in a sequence of tokens associated with a first word of the query, identifying probabilities for sub-sequences of tokens in a sequence of tokens associated with a second word of a query, and identifying a probability of a silence token between the first word and the second word.

31. The computer-readable medium of claim 29 wherein using an index of token sub-sequences further comprises identifying probabilities for sub-sequences of tokens that include tokens from the first word and the second word.

32. The computer-readable medium of claim 31 further comprising determining a first score and a second score that indicate the likelihood of the user query, the first score being based in part on a probability for a silence token between the first word and the second word and the second score being based on a probability for a sub-sequence of tokens that includes tokens from the first word and the second word.

33. The computer-readable medium of claim 28 wherein combining the identified probabilities together to form a score comprises combining identified probabilities for sub-sequences of sub-word tokens to form a first component of the score, combining identified probabilities for sub-sequences of word tokens to form a second component of the score and combining the first component of the score and the second component of the score to form the score.