Method and apparatus for disambiguating lists of elements for speech interfaces

• US 6,523,004 B1
• Filed: 07/19/1999
• Issued: 02/18/2003
• Est. Priority Date: 07/19/1999
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Loring, Keith P., Wang, Huifang, Vanbuskirk, Ronald E.
• Primary Examiner(s): CHAWAN, VIJAY B
• Application Number:
  US09/356,144
• Time in Patent Office: 1,310 Days
• Field of Search: 704/231, 704/251, 704/270, 704/272, 704/273, 704/275, 704/235, 704/260
• US Class Current: 704/251
• CPC Class Codes: G10L 15/04 Segmentation; Word boundary detection
• CPC Class Codes: G10L 2015/085 Methods for reducing search complexity, pruning

Abstract

In a computer system having a list based natural discourse application adapted for speech recognition. In response to a first user element request, the system searches a list of elements to generate a list of matches which contain elements which satisfy the element request. The system calculates the time required to read out the match list common levels, the time required to read out all matches, and the time required to iteratively query the user as to which matches of one of said common levels to read out. The system then reads out the match list using the method having the lowest calculated time.

Claims

1. In a computer system having a list based natural discourse application adapted for speech recognition, a method of selecting a speech menu element from a list of elements comprising the steps of:

in response to a first user element request, searching a list of speech menu elements to generate a list of matches which contain elements which satisfy said element request;

determining a time required to play said matches for each of a plurality of audible playback methods; and

choosing a preferred one of said plurality of audible playback methods for audibly presenting said matches to a user according to said determining step.

2. In a method of selecting an element from a list as claimed in claim 1, further comprising the steps of:

determining one or more most probable matches in said match list;

reading out said most probable matches.

3. In a method of selecting an element from a list as claimed in claim 2, wherein said most probable matches are read out if the number of matches selected for read out is less than a predetermined number.

4. In a method of selecting an element from a list as claimed in claim 2, wherein said most probable matches are matches having the least missing information.

5. In a method of selecting an element from a list as claimed in claim 1, said method further comprising:

parsing the matches in said list of matches into common levels based upon a predetermined criteria;

wherein said determining step comprises calculating the time required to read out the match list common levels, calculating the time required to read out all matches, calculating the time required to iteratively query the user as to which matches of one of said common levels to read out; and

wherein said choosing step comprises reading out the match list using the method having the lowest calculated time.

6. In a method of selecting an element from a list as claimed in claim 5, further comprising the step:

If the read out method selected reads out a level in which the matches are to be read out, repeating the steps of the natural discourse application method beginning with the parsing step using a revised list of matches containing only match list elements within the selected level until a match list element is selected by the user.

7. In a method of selecting an element from a list as claimed in claim 5, wherein the calculated times are greater than a predetermined number, then after the times are calculated,

querying the user to select one of said read out methods if all of the calculated times are greater than a predetermined time;

reading out the matches using the read out method selected by the user if the user selected one of said methods.

8. In a method of selecting an element from a list as claimed in claim 7, wherein the user fails to select a read out method, then after the user has affirmatively declined to select a read out method, or fails to respond within a predetermined time, selecting one of said read out methods based upon the number of match list common levels and the calculated read out times.

9. In a method of selecting an element from a list as claimed in claim 7, wherein the user fails to select a read out method, then after the user has affirmatively declined to select a read out method, or fails to respond within a predetermined time,

reading out the matches using the read out method determined by the following criteria;

(1) if there is one common level, then read out all of the matches;

(2) if there are two or more common levels, then if two or more read out methods do not have the same calculated time, t, then read out the matches using the method having the lowest calculated time. If two or more of the methods of reading out the matches is equal to the lowest calculated time, and reading out all of the matches has one of the lowest calculated times, then read out all of the matches, otherwise iteratively query the user as to which level all of the matches in the level to read out.

10. In a method of selecting an element from a list as claimed in claim 5, wherein said predetermined criteria is length of a substring within said element.

11. In a method of selecting an element from a list as claimed in claim 5, wherein if one or more of the calculated times are equal, reading out all of the match list elements, if the time for reading out all of the match list elements is equal to the lowest time, otherwise reading out the match list common levels.

12. In a computer system having a list based natural discourse application adapted for speech recognition for selecting an element from a list comprising:

means responsive to a first user element request, searching a list of speech menu elements to generate a list of matches which contain speech menu elements which satisfy said element request;

means for determining a time required to play said matches for each of a plurality of audible playback methods; and

means for choosing a preferred one of said plurality of audible playback methods for audibly presenting said matches to a user according to said time determination.

13. In a system as claimed in claim 12, further comprising:

means for determining one or more most probable matches in said list of matches;

means for reading out said most probable matches.

14. In a system as claimed in claim 13, wherein said most probable matches are read out if the number of matches selected for read out is less than a predetermined number.

15. In a system as claimed in claim 12, said system further comprising:

means for parsing the matches in said list of matches into common levels based upon a predetermined criteria;

wherein said means for determining a time comprise means for calculating the time required to read out the match list common levels, means for calculating the time required to read out all matches, means for calculating the time required to iteratively query the user as to which matches of one of said common levels to read out; and

wherein said means for choosing comprise means for reading out the match list using the method having the lowest calculated time.

16. In a system as claimed in claim 15, further comprising:

means for querying the user to select one of said read out methods if all of the calculated times are greater than a predetermined time; and

means for reading out the matches using the read out method selected by the user if the user selected one of said methods.

17. In a system as claimed in claim 16, further comprising:

means for selecting one of said read out methods based upon the number of match list common levels and the calculated read out times if the user fails to select a read out method, and the user has affirmatively declined to select a read out method, or fails to respond within a predetermined time.

18. In a system as claimed in claim 16, wherein the user fails to select a read out method, then after the user has affirmatively declined to select a read out method, or fails to respond within a predetermined time,

means for reading out the matches using the read out method determined by the following criteria;

(1) if there is one common level, then read out all of the matches;

(2) if there are two or more common levels, then if two or more read out methods do not have the same calculated time, t, then read out the matches using the method having the lowest calculated time. If two or more of the methods of reading out the matches is equal to the lowest calculated time, and reading out all of the matches has one of the lowest calculated times, then read out all of the matches, otherwise iteratively query the user as to which level all of the matches in the level to read out.

19. In a system as claimed in claim 15, wherein said predetermined criteria is length of a substring within said element.

20. In a system as claimed in claim 15, wherein in said means for reading out the match list using the method having the lowest calculated time, if one or more of the calculated times are equal, read out all of the match list elements, if the time for reading out all of the match list elements is equal to the lowest time, otherwise reading out the match list common levels.

21. In a system as claimed in claim 12, wherein said most probable matches are matches having the least missing information.

22. A machine readable storage, having stored thereon a computer program having a plurality of code sections executable by a machine for causing the machine to perform the steps of:

in response to a first user element request, searching a list of speech menu elements to generate a list of matches which contain elements which satisfy said element request;

determining a time required to play said matches for each of a plurality of audible playback methods; and

choosing a preferred one of said plurality of audible playback methods for audibly presenting said matches to a user according to said determining step.

23. The machine readable storage as claimed in claim 22, further including a plurality of code sections executable by a machine for causing the machine to perform the step of:

determining one or more most probable matches in said match list;

reading out said most probable matches.

24. The machine readable storage as claimed in claim 23, wherein said most probable matches are read out if the number of matches selected for read out is less than a predetermined number.

25. The machine readable storage as claimed in claim 23, wherein choosing said preferred method includes the steps of:

parsing the matches in said list of matches into common levels based upon a predetermined criteria;

calculating the time required to read out the match list common levels;

calculating the time required to read out all matches;

calculating the time required to iteratively query the user as to which matches of one of said common levels to read out; and

reading out the match list using the method having the lowest calculated time.

26. The machine readable storage as claimed in claim 25, further including a plurality of code sections executable by a machine for causing the machine to perform the step of:

If the read out method selected reads out a level in which the matches are to be read out, repeating the steps of the natural discourse application method beginning with the parsing step using a revised list of matches containing only match list elements within the selected level until a match list element is selected by the user.

27. The machine readable storage as claimed in claim 25, further including a plurality of code sections executable by a machine for causing the machine to perform said steps, wherein the calculated times are greater than a predetermined number, then after the times are calculated,

querying the user to select one of said read out methods if all of the calculated times are greater than a predetermined time;

reading out the matches using the read out method selected by the user if the user selected one of said methods.

28. The machine readable storage as claimed in claim 27, further including a plurality of code sections executable by a machine for causing the machine to perform said steps, wherein the user fails to select a read out method, then after the user has affirmatively declined to select a read out method, or fails to respond within a predetermined time, selecting one of said read out methods based upon the number of match list common levels and the calculated read out times.

29. The machine readable storage as claimed in claim 27, further including a plurality of code sections executable by a machine for causing the machine to perform said steps, wherein the user fails to select a read out method, then after the user has affirmatively declined to select a read out method, or fails to respond within a predetermined time,

reading out the matches using the read out method determined by the following criteria;

(1) if there is one common level, then read out all of the matches;

(2) if there are two or more common levels, then if two or more read out methods do not have the same calculated time, t, then read out the matches using the method having the lowest calculated time. If two or more of the methods of reading out the matches is equal to the lowest calculated time, and reading out all of the matches has one of the lowest calculated times, then read out all of the matches, otherwise iteratively query the user as to which level all of the matches in the level to read out.

30. The machine readable storage as claimed in claim 25, wherein said predetermined criteria is length of a substring within said element.

31. In the machine readable storage as claimed in claim 25, wherein, if one or more of the calculated times are equal, reading out all of the match list elements, if the time for reading out all of the match list elements is equal to the lowest time, otherwise reading out the match list common levels.

32. In the machine readable storage as claimed in claim 23, wherein said most probable matches are matches having the least missing information.