Creating a hierarchical tree of language models for a dialog system based on prompt and dialog context

• US 6,754,626 B2
• Filed: 03/01/2001
• Issued: 06/22/2004
• Est. Priority Date: 03/01/2001
• Status: Expired due to Term

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Epstein, Mark E.
• Primary Examiner(s): Dorvil, Richemond
• Assistant Examiner(s): Nolan, Daniel A
• Application Number:
  US09/798,655
• Publication Number:
  US 20020123891A1
• Time in Patent Office: 1,209 Days
• Field of Search: 704/235, 704/238, 704/251, 704/257, 704/243, 704/219, 704/256, 704/9, 704/255
• US Class Current: 704/235
• CPC Class Codes: G10L 15/183 using context dependencies, e.g. language models
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams

Abstract

The invention disclosed herein concerns a method of converting speech to text using a hierarchy of contextual models. The hierarchy of contextual models can be statistically smoothed into a language model. The method can include processing text with a plurality of contextual models. Each one of the plurality of contextual models can correspond to a node in a hierarchy of the plurality of contextual models. Also included can be identifying at least one of the contextual models relating to the text and processing subsequent user spoken utterances with the identified at least one contextual model.

Claims

1. A method of creating a hierarchy of contextual models, said method comprising:

(a) measuring the distance between each of a plurality of contextual models using a distance metric, wherein at least one of said plurality of contextual models corresponds to at least a portion of a document or a user response within a dialog based system;

(b) identifying two of said plurality of contextual models, said identified contextual models being closer in distance than other ones of said plurality of contextual models;

(c) merging said identified contextual models into a parent contextual model;

(d) repeating said steps (a), (b), and (c) until a hierarchy of said plurality of contextual models is created, said hierarchy having a root node; and

(e) statistically smoothing said hierarchy of said plurality of contextual models resulting in a language model.

2. The method of claim 1, said merging step (c) further comprising:

interpolating between said identified contextual models, said interpolation resulting in a combination of said identified contextual models.

3. The method of claim 1, wherein at least one of said plurality of contextual models corresponds to a section of a document.

4. The method of claim 1, wherein at least one of said plurality of contextual models corresponds to at least one user response received in a particular dialog state in the dialog based system.

5. The method of claim 1, wherein at least one of said plurality of contextual models corresponds to at least one user response received at a particular location within a particular transaction within the dialog based system.

6. The method of claim 1, wherein at least one of said plurality of contextual models corresponds to a syntax of a prompt in the dialog based system.

7. The method of claim 1, wherein at least one of said plurality of contextual models corresponds to a particular and known dialog based system prompt.

8. The method of claim 1, wherein at least one of said plurality of contextual models corresponds to a received electronic mail message.

9. A method of creating a hierarchy of contextual models, said method comprising:

(a) measuring the distance between each of a plurality of contextual models using a distance metric, wherein at least one of said plurality of contextual models corresponds to at least a portion of a document or a user response within a dialog based system;

(b) identifying two of said plurality of contextual models, said identified contextual models being closer in distance than other ones of said plurality of contextual models;

merging said identified contextual models into a parent contextual model by building a parent contextual model using data corresponding to said identified contextual models;

(d) repeating said steps (a), (b), and (c) until a hierarchy of said plurality of contextual models is created, said hierarchy having a root node; and

(e) statistically smoothing said hierarchy of said plurality of contextual models resulting in a language model.

10. 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:

(a) measuring the distance between each of a plurality of contextual models using a distance metric, wherein at least one of said plurality of contextual models corresponds to at least a portion of a document or a user response within a dialog based system;

(b) identifying two of said plurality of contextual models, said identified contextual models being closer in distance than other ones of said plurality of contextual models;

(c) merging said identified contextual models into a parent contextual model;

(d) repeating said steps (a), (b), and (c) until a hierarchy of said plurality of contextual models is created, said hierarchy having a root node; and

(e) statistically smoothing said hierarchy of said plurality of contextual models resulting in a language model.

11. The machine readable storage of claim 10, said merging step (c) further comprising:

interpolating between said identified contextual models, said interpolation resulting in a combination of said identified contextual models.

12. The machine readable storage of claim 10, wherein at least one of said plurality of contextual models corresponds to a section of a document.

13. The machine readable storage of claim 10, wherein at least one of said plurality of contextual models corresponds to at least one user response received in a particular dialog state in the dialog based system.

14. The machine readable storage of claim 10, wherein at least one of said plurality of contextual models corresponds to at least one user response received at a particular location within a particular transaction within the dialog based system.

15. The machine readable storage of claim 10, wherein at least one of said plurality of contextual models corresponds to a syntax of a prompt in the dialog based system.

16. The machine readable storage of claim 10, wherein at least one of said plurality of contextual models corresponds to a particular and known dialog based system prompt.

17. The machine readable storage of claim 10, wherein at least one of said plurality of contextual models corresponds to a received electronic mail message.

18. 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:

(a) measuring the distance between each of a plurality of contextual models using a distance metric wherein at least one of said plurality of contextual models corresponds to at least a portion of a document or a user response within a dialog based system;

(b) identifying two of said plurality of contextual models, said identified contextual models being closer in distance than other ones of said plurality of contextual models;

(c) merging said identified contextual models into a parent contextual model by building a parent contextual model using data corresponding to said identified contextual models;

(d) repeating said steps (a), (b), and (c) until a hierarchy of said plurality of contextual models is created, said hierarchy having a root node; and

(e) statistically smoothing said hierarchy of said plurality of contextual models resulting in a language model.

19. A method of creating a hierarchical tree of language models comprising:

(a) creating a language model at the leaves of a tree, wherein each leaf corresponds to a different non-overlapping partition of user responses to prompts in a dialog system;

(b) identifying at least two closest child language models for leaves in the tree;

(c) merging said identified language models into a parent language model by using data corresponding to each child language mode; and

(d) repeating steps (b) and (c) until the hierarchical tree is formed, whereby a root of the hierarchical tree is built using all available training data.

20. The method of claim 19, wherein language models at the leaves of the tree are partitioned based upon dialog context.

21. The method of claim 20, wherein the dialog context is determined by a transaction the dialog system is in when a user response is collected.

22. The method of claim 20, wherein the dialog context is determined by a type of information for which the dialog system has asked when a user response is collected.

23. The method of claim 20, wherein the dialog context is determined by a type of question the dialog system has asked when a user response is collected.

24. The method of claim 23, wherein the dialog system has asked a yes or no question.

25. The method of claim 23, wherein the dialog system has asked a multiple choice question.

26. The method of claim 23, wherein the dialog system has asked a which question.

27. The method of claim 23, wherein the dialog context is determined by a number of consecutive prompts given to a user for a current dialog context.

28. The method of claim 19, wherein the hierarchical tree is constructed a priori from collected training data prior to the dialog system, within which the hierarchical tree is to be used, is deployed.

29. The method of claim 19, further comprising:

collecting data from users and adding the data to at least one of the non-overlapping partitions;

creating additional leaf language models using the collected data; and

rebuilding the hierarchical tree using the new leaves.

30. 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:

(a) creating a language model at the leaves of a tree, wherein each leaf corresponds to a different non-overlapping partition of user responses to prompts in a dialog system;

(b) identifying at least two closest child language models for leaves in the tree;

(c) merging said identified language models into a parent language model by using data corresponding to each child language model; and

(d) repeating steps (b) and (c) until the hierarchical tree is formed, whereby a root of the hierarchical tree is built using all available training data.

31. The machine readable storage of claim 30, wherein language models at the leaves of the tree are partitioned based upon dialog context.

32. The machine readable storage of claim 31, wherein the dialog context is determined by a transaction the dialog system is in when a user response is collected.

33. The machine readable storage of claim 31, wherein the dialog context is determined by a type of information for which the dialog system has asked when a user response is collected.

34. The machine readable storage of claim 31, wherein the dialog context is determined by a type of question the dialog system has asked when a user response is collected.

35. The machine readable storage of claim 34, wherein the dialog system has asked a yes or no question.

36. The machine readable storage of claim 34, wherein the dialog system has asked a multiple choice question.

37. The machine readable storage of claim 34, wherein the dialog system has asked a which question.

38. The machine readable storage of claim 34, wherein the dialog context is determined by a number of consecutive prompts given to a user for a current dialog context.

39. The machine readable storage of claim 30, wherein the hierarchical tree is constructed a priori from collected training data prior to the dialog system, within which the hierarchical tree is to be used, is deployed.

40. The machine readable storage of claim 30, further comprising:

collecting data from users and adding the data to at least one of the non-overlapping partitions;

creating additional leaf language models using the collected data; and

rebuilding the hierarchical tree using the new leaves.