Method and apparatus for performing plan-based dialog

• US 6,785,651 B1
• Filed: 09/14/2000
• Issued: 08/31/2004
• Est. Priority Date: 09/14/2000
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wang, Kuansan
• Primary Examiner(s): ABEBE, DANIEL DEMELASH
• Application Number:
  US09/662,242
• Time in Patent Office: 1,447 Days
• Field of Search: 704/235, 704/246, 704/257, 704/270, 704/275, 379/88.01
• US Class Current: 704/246
• CPC Class Codes: G06F 40/143 Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
• CPC Class Codes: G06F 40/154 Tree transformation for tree-structured or markup documents, e.g. XSLT, XSL-FO or stylesheets
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation
• CPC Class Codes: G06F 9/453 Help systems
• CPC Class Codes: G10L 15/18 using natural language modelling
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding
• CPC Class Codes: H04M 3/4938 comprising a voice browser which renders and interprets, e.g. VoiceXML

Abstract

The present invention provides a dialog system in which the subsystems are integrated under a single technology model. In particular, each of the sub-systems uses stochastic modeling to identify a probability for its respective output. The combined probabilities identify a most probable action to be taken by the dialog system given the latest input from the user and the past dialog states. An additional aspect of the present invention is an embodiment in which the sub-systems communicate with one another through XML pages, thus allowing the sub-systems to be distributed across a distributed network.

Claims

1. A method of providing a dialog interface in a computer system, the method comprising:

receiving user input;

applying the user input to a language model to determine a score for at least one surface semantic that describes the content of the user input;

applying a surface semantic to a discourse model to determine a score for at least one discourse semantic that describes the current state of a dialog with the user;

applying a discourse semantic to a behavior model to determine a score for at least one action to be taken by the computer system; and

taking an action based in part on the score provided by the discourse model and based in part on the score provided by the behavior model.

2. The method of claim 1 further comprising:

receiving multiple modes of user input;

applying each mode of user input to a language model provided for that mode of user input; and

determining a score for at least one surface semantic for each mode of user input that is received.

3. The method of claim 1 wherein applying a surface semantic to a discourse model comprises expanding a discourse semantic structure by placing values in slots of the discourse semantic structure based on the surface semantic.

4. The method of claim 3 wherein expanding the discourse semantic structure further comprises:

accessing a discourse memory to retrieve an explicit value for an implicit reference in the surface semantic; and

placing the explicit value in a slot in the discourse semantic structure.

5. The method of claim 4 wherein accessing a discourse memory comprises accessing a discourse memory comprising:

a long-term memory having values resolved from previous user input;

an explicit memory having explicit values found in a current user input; and

an implicit memory having values resolved from an implicit reference in the current user input.

6. The method of claim 5 wherein accessing a discourse memory comprises accessing the explicit memory first, the long-term memory second and the implicit memory last.

7. The method of claim 3 wherein applying a surface semantic to a discourse model further comprises after expanding a discourse semantic structure determining if a semantic token in the discourse semantic structure can be replaced by an entity.

8. The method of claim 7 wherein determining if a semantic token in the discourse semantic structure can be replaced by an entity comprise s searching for an entity in a database based on attributes found in the discourse structure for the semantic token.

9. The method of claim 8 wherein determining if a semantic token in the discourse semantic structure can be replaced by an entity further comprises determining that the semantic token can be replaced by an entity if only one entity is found during the search of the database.

10. The method of claim 8 wherein determining if a semantic token in the discourse semantic structure can be replaced by an entity further comprises determining that the semantic token cannot be replaced by an entity if multiple entities are found during the search of the database.

11. The method of claim 10 wherein applying a surface semantic to a discourse model further comprises:

retrieving multiple entities from a database as possible replacements for a discourse semantic token;

adding the multiple entities as children of the discourse semantic token to form separate discourse semantic structures for each entity; and

determining a score for each discourse semantic structure associated with each entity.

12. The method of claim 1 wherein determining a score for at least one action comprises determining a score for an action of:

selecting one of multiple entities in a discourse semantic structure for a discourse semantic token; and

executing a command without asking the user to clarify which entity is correct for the semantic token.

13. The method of claim 12 wherein taking an action based in part on a score provided by the behavior model comprises taking the action of executing the command without asking the user to clarify which entity is correct for the semantic token.

14. The method of claim 1 wherein determining a score for at least one action further comprises applying an identity of an available user interface to the behavior model such that actions that are compatible with the available user interface receive generally higher scores than actions that are not compatible with the user interface.

15. The method of claim 1 wherein applying the user input to a language model further comprises describing the surface semantic using a markup language.

16. The method of claim 15 wherein applying a surface semantic to a discourse model further comprises describing a discourse semantic using a markup language.

17. The method of claim 16 further comprising applying a discourse semantic to a behavior model by converting the discourse semantic into an action described using a markup language.

18. The method of claim 17 wherein converting the discourse semantic comprises selecting a markup language for the action based on an available user interface.

19. The method of claim 18 wherein describing a discourse semantic using a markup language comprises describing the discourse semantic using an extensible markup language and wherein converting the discourse semantic comprises applying the discourse semantic to an extensible stylesheet language transformation.

20. The method of claim 19 further comprising:

receiving an instruction from a user to change the available user interface; and

applying the discourse semantic to a second extensible stylesheet language transformation to convert the discourse semantic into an action described using a second markup language.

21. A system for providing a computer-based dialog interface to a user, the system comprising:

a dialog state engine that receives input from the user and that uses at least one model to generate at least one score for a current dialog state that is represented by a discourse semantic structure comprising semantic tokens that provide a general representation of specific entities, the score being based on the user'"'"'s input and a previous dialog state, the dialog state engine comprising;

a recognition engine that uses a model to determine a score for at least one surface semantic based on the user input;

a discourse engine that uses a model to determine a score for at least one current dialog state based on the surface semantic from the recognition engine and a previous dialog state, the discourse engine expanding the discourse semantic structure based on the surface semantic and attempting to collapse a portion of the discourse semantic structure before using the model to determine a score for the discourse semantic structure; and

a database containing specific entities that are represented by the semantic tokens; and

a rendering engine that uses a model to identify a score for at least one action based on a current dialog state.

22. The system of claim 21 wherein the discourse engine attempts to collapse a portion of the discourse semantic structure by looking for entities in the database that have the same attributes associated with one of the semantic tokens.

23. The system of claim 22 wherein if more than one entity has the same attributes associated with one of the semantic tokens, the discourse engine adds the entities to the discourse semantic structure below the semantic token, identifies a separate discourse semantic structure for each entity and generates a separate score for the separate discourse semantic structure associate with each entity.

24. A system for providing a computer-based dialog interface to a user, the system comprising:

a dialog state engine that receives input from the user and that uses at least one model to generate at least one score for a current dialog state based on the user'"'"'s input and a previous dialog state, wherein the dialog state engine describes the current dialog state using a markup language; and

a rendering engine that uses a model to identify a score for at least one action based on a current dialog state and that converts the markup language describing the current dialog state into a second markup language that describes an action.

25. The system of claim 24 wherein the current dialog state is described using an extensible markup language and wherein the rendering engine utilizes extensible stylesheet language transformations to transform the extensible markup language into the second markup language.

26. The system of claim 25 wherein the dialog state engine further receives an indication from the user that they wish to change the output interface, and wherein the rendering engine changes the extensible stylesheet language transformation based on the change of the output interface so that the same extensible markup language description of the current dialog state is converted into a third markup language different from the second markup language.

27. A method of providing a dialog interface, the method comprising:

receiving input generated by a user;

determining a current dialog state based on the received input and a past dialog state;

formatting the current dialog state into an extensible markup language page;

converting the markup language page into an output markup language page based on the current dialog state and an available output user interface by applying the extensible markup language page to an extensible stylesheet language transformation; and

passing the output markup language page to the available output user interface.

28. The method of claim 27 wherein converting the markup language page further comprises selecting an extensible stylesheet language transformation that forms a proper output markup language page for the output user interface.

29. The method of claim 28 further comprising:

receiving an instruction from the user to change the output user interface to a new output user interface; and

selecting a different extensible stylesheet language transformation so that the output markup language page is appropriate for the new output user interface.

30. A system for providing a computer-based dialog interface to a user, the system comprising:

a dialog state engine that receives input from the user and that generates a markup language page representing a current dialog state; and

a rendering engine that converts the markup language page representing the current dialog state into a markup language page representing an action, wherein the rendering engine comprises extensible stylesheet language transformations that convert the markup language page representing the current dialog state into the markup language page representing an action.

31. A system for providing a computer-based dialog interface to a user, the system comprising:

a dialog state engine that receives input from the user and that generates a markup language page representing a current dialog state; and

a rendering engine that converts the markup language page representing the current dialog state into a markup language page representing an action, wherein the rendering engine utilizes a document matching portion of extensible stylesheet language transformations to convert the markup language page representing the current dialog state into machine instructions representing actions that are not described in a markup languages.

32. A system for providing a computer-based dialog interface to a user, the system comprising:

a dialog state engine that receives input from the user and that generates a markup language page representing a current dialog state, wherein the dialog state engine comprises;

a recognition engine that receives user input and generates a markup language page representing the surface semantics of the user input, wherein the recognition engine applies a document generating portion of extensible stylesheet language transformations to produce the markup language page representing the surface semantics; and

a discourse engine that converts the markup language page representing the surface semantics into the markup language page representing the dialog state; and

a rendering engine that converts the markup language page representing the current dialog state into a markup language page representing an action.