Copying human interactions through learning and discovery

• US 8,990,126 B1
• Filed: 08/03/2006
• Issued: 03/24/2015
• Est. Priority Date: 08/03/2006
• Status: Expired due to Fees

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Bangalore, Srinivas, Conkie, Alistair, Di Fabbrizio, Giuseppe, Gupta, Narendra Kumar, Stent, Amanda Joy
• Primary Examiner(s): RIFKIN, BEN M
• Application Number:
  US11/462,068
• Time in Patent Office: 3,155 Days
• Field of Search: 706/12
• US Class Current: 706/12
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 40/103 Formatting, i.e. changing of presentation of documents automatic justification G06F40/189; automatic line break hyphenation G06F40/191
• CPC Class Codes: G06F 40/20 Natural language analysis semantic analysis of natural language G06F40/30

Abstract

A method, system and computer readable medium that generates a dialog model for use in automated dialog is disclosed. The method may include collecting a plurality of task-oriented dialog interactions between users and human agents for a given domain, identifying one or more task in each dialog interaction, identifying one or more subtasks in each identified task and associating relations between the subtasks, identifying a dialog act and a set of predicate-argument relations for each subtask, generating one or more clauses from the set of predicate-argument relations, storing the tasks, subtasks, dialog acts predicate-argument relations, and clauses from each dialog interaction as a dialog interaction set, generating a dialog management model using the stored dialog interaction sets.

Claims

1. A method comprising:

collecting a plurality of task-oriented, human-human dialog interactions between users and human agents for a given domain;

after collecting the plurality of task-oriented, human-human dialog interactions, extracting, via a processor, a respective dialog structure associated with each of the plurality of task-oriented, human-human dialog interactions, wherein extracting the respective dialog structure comprises;

identifying a respective task in each of the plurality of task-oriented, human-human dialog interactions;

identifying subtasks in the respective task and associating relations between the subtasks, wherein the identifying of the subtask is done using a chunk model equation PT*=argmax Σ

_ST P(ST|U)P(PT|ST), where PT* is the most likely plan tree, ST is each subtask in a sequence of utterances U, PT represents likelihood of each plan tree, and P represents the individual probabilities within the chunk model equation, where the chunk model equation uses the respective dialog structures U and ST as a weighted lattice; and

identifying a dialog act and a set of predicate-argument relations for the subtasks by annotating user utterances in the plurality of task-oriented, human-human dialog interactions with tags;

generating a clause from the set of predicate-argument relations;

removing speech repairs and dysfluencies from a respective user utterance in each of the plurality of task-oriented, human-human dialog interactions; and

storing the respective task, the subtasks, the dialog act, the set of predicate-argument relations, the clause, inter-clausal relations within the clause, and a set of dominance and precedence relations associated with the respective task as a dialog interaction set represented as a single tree.

2. The method of claim 1, further comprising:

identifying named entities for each subtask;

identifying labels for the named entities; and

storing the labels in the dialog interaction set.

3. The method of claim 1, wherein the predicate-argument relations are identified using supertags.

4. The method of claim 1, wherein the subtasks are identified using a chunk-based model.

5. The method of claim 1, wherein the subtasks are identified using a parse-based model.

6. The method of claim 1, wherein the subtasks are segmented into beginning, middle and end utterances.

7. The method of claim 1, further comprising generating a dialog management model using the dialog interaction set.

8. A computer-readable storage device having instructions stored which, when executed by a computing device, cause the computing device to perform operations comprising:

collecting a plurality of task-oriented, human-human dialog interactions between users and human agents for a given domain;

after collecting the plurality of task-oriented, human-human dialog interactions, extracting a respective dialog structure associated with each of the plurality of task-oriented, human-human dialog interactions, wherein extracting the respective dialog structure comprises;

identifying a respective task in each of the plurality of task-oriented, human-human dialog interactions;

identifying subtasks in the respective task and associating relations between the subtasks, wherein the identifying of the subtask is done using a chunk model equation PT*=argmax Σ

_ST P(ST|U)P(PT|ST), where PT* is the most likely plan tree, ST is each subtask in a sequence of utterances U, PT represents likelihood of each plan tree, and P represents the individual probabilities within the chunk model equation where the chunk model equation uses the respective dialog structures U and ST as a weighted lattice; and

identifying a dialog act and a set of predicate-argument relations for the subtasks by annotating user utterances in the plurality of task-oriented, human-human dialog interactions with tags;

generating a clause from the set of predicate-argument relations;

removing speech repairs and dysfluencies from a respective user utterance in each of the plurality of task-oriented, human-human dialog interactions;

storing the respective task, the subtasks, the dialog act, the set of predicate-argument relations, the clause, inter-clausal relations within the clause, and a set of dominance and precedence relations associated with the respective task as a dialog interaction set represented as a single tree.

9. The computer-readable storage device of claim 8 the computer-readable storage device having additional instructions stored which result in the operations further comprising:

identifying named entities for the subtasks;

identifying labels for the named entities; and

storing the labels in the dialog interaction set.

10. The computer-readable storage device of claim 8, wherein the predicate-argument relations are identified using supertags.

11. The computer-readable storage device of claim 8, wherein the subtasks are identified using a chunk-based model.

12. The computer-readable storage device of claim 8, wherein the subtasks are identified using a parse-based model.

13. The computer-readable storage device of claim 8, wherein the subtasks are segmented into beginning, middle and end utterances.

14. The computer-readable storage device of claim 8, the computer-readable storage device having additional instructions stored which result in the operations further comprising generating a dialog management model using the dialog interaction set.

15. A system comprising:

a processor; and

a computer readable storage medium having stored therein instructions which, when executed by the processor, cause the processor to perform operations comprising;

collecting a plurality of task-oriented, human-human dialog interactions between users and human agents for a given domain;

after collecting the plurality of task-oriented, human-human dialog interactions, extracting, via a processor, a respective dialog structure associated with each of the plurality of task-oriented, human-human dialog interactions, wherein extracting the respective dialog structure comprises;

identifying a respective task in each of the plurality of task-oriented, human-human dialog interactions;

identifying subtasks in the respective task and associating relations between the subtasks, wherein the identifying of the subtask is done using a chunk model equation PT*=argmax Σ

_ST P(ST|U)P(PT|ST), where PT* is the most likely plan tree, ST is each subtask in a sequence of utterances U, PT represents likelihood of each plan tree, and P represents the individual probabilities within the chunk model equation, where the chunk model equation uses the respective dialog structures U and ST as a weighted lattice; and

identifying a dialog act and a set of predicate-argument relations for the subtasks by annotating user utterances in the plurality of task-oriented, human-human dialog interactions with tags;

generating a clause from the set of predicate-argument relations;

removing speech repairs and dysfluencies from a respective user utterance in each of the plurality of task-oriented, human-human dialog interactions; and

storing the respective task, the subtasks, the dialog act, the set of predicate-argument relations, the clause, inter-clausal relations within the clause, and a set of dominance and precedence relations associated with the respective task as a dialog interaction dataset represented as a single tree.

16. The system of claim 15, the computer-readable storage medium having additional instructions stored which result in the operations further comprising:

identifying named entities for the subtasks;

identifying labels for the named entities; and

storing the labels in a Child training database.

17. The system of claim 15, wherein the predicate-argument relations are identified using supertags.

18. The system of claim 15, wherein the subtasks are identified using one of a chunk-based model and a parse-based model.

19. The system of claim 15, the computer readable storage medium having additional instructions stored which result in the operations further comprising segmenting the subtasks into beginning, middle and end utterances.

20. The system of claim 15, the computer readable storage medium having additional instructions stored which result in the operations further comprising generating a dialog management model using the dialog interaction set.