Method and system for hierarchical natural language understanding

• US 6,311,150 B1
• Filed: 09/03/1999
• Issued: 10/30/2001
• Est. Priority Date: 09/03/1999
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Ramaswamy, Ganesh N., Kleindienst, Jan
• Primary Examiner(s): EDOUARD, PATRICK NESTOR
• Application Number:
  US09/389,789
• Time in Patent Office: 788 Days
• Field of Search: 704/1, 704/2, 704/9, 704/255, 704/257
• US Class Current: 704/1
• CPC Class Codes: G06F 40/279 Recognition of textual entities
• CPC Class Codes: G06F 40/30 Semantic analysis

Abstract

A method for hierarchical translation of input to a formal command in natural language understanding systems includes presenting an input command to be translated to a natural language understanding engine. At least two translator levels are provided in the natural language understanding engine. A first translator level of the at least two translator levels translates the input command into at least one category by associating the input command with the at least one category for the next level of translators. A formal language command is output for the input command from a last of the at least two translator levels based on the input command and the at least one category.

Claims

1. A method for hierarchical translation of input to a formal command in a natural language understanding system comprising the steps of:

presenting an input command to be translated to a natural language understanding engine;

providing at least two translator levels in the natural language understanding engine;

translating the input command into at least one category by a first translator level of the at least two translator levels by associating the input command with the at least one category for a next level of translators; and

outputting a formal language command for the input command from a last of the at least two translator levels based on the input command and the at least one category.

2. The method as recited in claim 1, wherein the step of providing at least two translator levels includes providing N translator levels where N is defined as a system parameter.

3. The method as recited in claim 1, wherein the step of translating the command into at least one category includes the step of providing a plurality of models, each model being associated with a category, each category including a subset of formal language commands to narrow a search space for determining the formal language command corresponding to the input command.

4. The method as recited in claim 1, further comprising the step of applying the formal language command to at least one application.

5. The method as recited in claim 1, wherein the at least one category includes formal language command entries relevant to at least one application and further comprising the step of applying the formal language command entries to the at least one application in accordance with the input command.

6. The method as recited in claim 1, wherein the at least one category includes all entries for the input command and further comprising the step of associating a first portion of the entries with the at least one category by providing a formal command for each of the entries relevant for the at least one category.

7. The method as recited in claim 6, further comprising the step of mapping a second portion of the entries to an error command.

8. The method as recited in claim 1, wherein the at least one category includes a do nothing category and the step of outputting a formal language command includes the step of outputting a do nothing command associated with incomplete and improper input commands.

9. The method as recited in claim 1, wherein the at least one category includes a general category for addressing ambiguous commands, commands relevant to multiple categories and system related commands.

10. The method as recited in claim 1, wherein the at least two translator levels search for a category selection for a next translator level or search for the formal language command for the last level, the category selection being limited to a given category from a previous level translator thereby narrowing a search space for each translator level to improve speed and accuracy.

11. A method for hierarchical translation of input to a formal command in a natural language understanding system comprising the steps of:

presenting an input command to be translated to a natural language understanding engine;

providing a plurality of translator levels in the natural language understanding engine;

providing a plurality of categories for each translator level, each category including a group of formal language commands stored in at least one model;

associating the input command with the categories for a given translator level;

scoring a probability of correct translation for each of the at least two categories;

selecting a category of the at least two categories yielding a highest score;

associating the input command with the selected category for a next level of translators; and

outputting a formal language command for the input command from a last of the translator levels based on the input command and the selected category.

12. The method as recited in claim 11, wherein the step of providing a plurality of translator levels includes providing N translator levels where N is defined as a system parameter.

13. The method as recited in claim 11, wherein each category includes a subset of formal language commands to narrow a search space for determining the formal language command corresponding to the input command.

14. The method as recited in claim 11, further comprising the step of applying the formal language command to at least one application.

15. The method as recited in claim 11, wherein the categories include formal language command entries relevant to at least one application and further comprising the step of applying the formal language command entries to the at least one application in accordance with the input command.

16. The method as recited in claim 11, wherein the at least two categories include all entries for the input command and further comprising the step of associating a first portion of the entries with a given category by providing a formal command for each of the entries relevant for the given category.

17. The method as recited in claim 16, further comprising the step of mapping a second portion of the entries to an error command.

18. The method as recited in claim 11, wherein the step of selecting a category of the at least two categories yielding a highest score includes the step of selecting a category with a lower score if a translation error is encountered for a category or categories yielding a higher score.

19. The method as recited in claim 18, further comprising the step of, if a translation error is encountered for all scored categories, selecting a do nothing category.

20. The method as recited in claim 11, wherein at least one category includes a do nothing category and the step of outputting a formal language command includes the step of outputting a do nothing command associated with incomplete and improper input commands.

21. The method as recited in claim 11, further comprising the step of assigning formal language commands to multiple categories to protect against translation errors in intermediate levels of the plurality of translator levels.

22. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps of claim 11.

23. A method for building hierarchical models for translating an input command to a formal command in a natural language understanding system comprising the steps of:

collecting training data from a domain of inputs;

separating the training data into translation levels, the translation levels arranged to provide a given output at each level for associating the inputs to a category, the training data including the inputs and an associated formal language command for each input;

for each translation level, indicating categories for searching for a formal language command by dividing up a formal language command search space and associating the categories with each input; and

associating each input with the formal language command in a last translation level.

24. The method as recited in claim 23, wherein the step of indicating categories for searching for a formal language command includes the step of constructing the categories based on applications supported by the natural language understanding systems.

25. The method as recited in claim 24, wherein the step of constructing the categories based on applications supported by the natural language understanding systems includes the step of constructing subcategories based on a task intended by user input.

26. The method as recited in claim 23, wherein the step of indicating categories for searching for a formal language command includes the step of constructing the categories based on a nature of a user'"'"'s input.

27. The method as recited in claim 23, further comprising the step of packaging models for each category such that models of categories are capable of being added or removed without affecting models of other categories.

28. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for hierarchical translation of input to a formal command in a natural language understanding system, the method steps comprising:

presenting an input command to be translated to a natural language understanding engine;

providing at least two translator levels in the natural language understanding engine;

translating the input command into at least one category by a first translator of the at least two translators by associating the input command with the at least one category for the next level of translators; and

outputting a formal language command for the input command from a last of the at least two translator levels based on the input command and the at least one category.

29. The program storage device as recited in claim 28, wherein the step of providing at least two translator levels includes providing N translator levels where N is defined as a system parameter.

30. The program storage device as recited in claim 28, wherein the step of translating the command into at least one category includes the step of providing a plurality of models, each model being associated with a category, each category including a subset of formal language commands to narrow a search space for determining the formal language command corresponding to the input command.

31. The program storage device as recited in claim 28, further comprising the step of applying the formal language command to at least one application.

32. The program storage device as recited in claim 28, wherein the at least one category includes formal language command entries relevant to at least one application and further comprising the step of applying the formal language command entries to the at least one application in accordance with the input command.

33. The program storage device as recited in claim 28, wherein the at least one category includes all entries for the input command and further comprising the step of associating a first portion of the entries with the at least one category by providing a formal command for each of the entries relevant for the at least one category.

34. The program storage device as recited in claim 33, further comprising the step of mapping a second portion of the entries to an error command.

35. The program storage device as recited in claim 28, wherein the at least one category includes a do nothing category and the step of outputting a formal language command includes the step of outputting a do nothing command associated with incomplete and improper input commands.

36. The program storage device as recited in claim 28, wherein the at least one category includes a general category for addressing ambiguous commands, commands relevant to multiple categories and system related commands.

37. The program storage device as recited in claim 28, wherein the at least two translator levels search for a category selection for a next translator level or the formal language command for the last level, the category selection being limited to a top choice category from a previous level translator thereby narrowing a search space for each translator level to improve speed and accuracy.