Semantic graphs and conversational agents

• US 9,196,245 B2
• Filed: 01/21/2014
• Issued: 11/24/2015
• Est. Priority Date: 03/26/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: VirtuOz SA (Microsoft Corporation)
• Inventors: Larcheveque, Jean-Marie Henri Daniel, Powers, Elizabeth Ireland, Recksiek, Freya Kate, Teodosiu, Dan
• Primary Examiner(s): PULLIAS, JESSE SCOTT
• Application Number:
  US14/160,074
• Publication Number:
  US 20140200891A1
• Time in Patent Office: 672 Days
• Field of Search: 704/1, 704/9, 704/10, 704/257
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/355 Class or cluster creation or modification
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G10L 15/1815 Semantic context, e.g. disambiguation of the recognition hypotheses based on word meaning

Abstract

Semantic clustering techniques are described. In various implementations, a conversational agent is configured to perform semantic clustering of a corpus of user utterances. Semantic clustering may be used to provide a variety of functionality, such as to group a corpus of utterances into semantic clusters in which each cluster pertains to a similar topic. These clusters may then be leveraged to identify topics and assess their relative importance, as for example to prioritize topics whose handling by the conversation agent should be improved. A variety of utterances may be processed using these techniques, such as spoken words, textual descriptions entered via live chat, instant messaging, a website interface, email, SMS, a social network, a blogging or micro-blogging interface, and so on.

Claims

1. A method implemented by one or more computer processors, the method comprising:

forming at least one intent graph pattern by using a plurality of user utterance;

comparing the at least one intent graph pattern of the plurality of user utterances with a plurality of semantic graph patterns; and

determining a matching semantic graph pattern based on the comparing if a subgraph of the matching graph pattern subsumes the at least one intent graph pattern of the plurality of user utterances.

2. The method as described in claim 1, further comprising obtaining the plurality of user utterances from one or more users as part of an interactive natural language dialog with a conversation agent.

3. The method as described in claim 2, further comprising using the matching semantic graph pattern by the conversation agent to engage in a subsequent interactive natural language dialog with the one or more users.

4. The method as described in claim 1, wherein comparing the at least one intent graph pattern of the plurality of user utterances with a plurality of semantic graph patterns further includes parsing semantic graph patterns of user utterances that are part of semantic clusters that are formed for like topics.

5. The method as described in claim 1, wherein forming an intent graph pattern of the plurality of user utterances further includes parsing conversation logs of a conversation agent.

6. The method as described in claim 1, wherein forming an intent graph pattern of the plurality of user utterances further includes identifying an intersection of pairs of semantic graphs representing one or more of the plurality of user utterances.

7. The method as described in claim 1, wherein the subgraph of the matching semantic graph subsumes the pattern if the matching semantic graph pattern is transformable into the intent graph pattern of the plurality of user utterances.

8. The method as described in claim 7, wherein the matching semantic graph pattern includes inter-connected nodes and edges and has traits defined therein, and wherein the method further comprises transforming the matching semantic graph by at least one of the following:

deleting at least one node and at least one incoming edge from the matching semantic graph pattern;

deleting a trait from the matching semantic graph pattern; and

replacing a value of a trait in the matching semantic graph pattern with another value that subsumes the replaced trait value.

9. The method as described in claim 1, further comprising:

outputting the intent graph pattern of the plurality of user utterances in a user interface; and

configuring the user interface to receive one or more inputs to modify the intent graph pattern of the plurality of user utterances, wherein the one or more inputs include a subset of the plurality of user utterances to be used in the modifying of the intent graph pattern of the plurality of user utterances.

10. A computer program product comprising computer readable instructions, stored on a non-transitory computer readable medium, the computer readable instructions, when executed by one or more computer processors, cause the one or more processors to:

form at least one intent graph pattern from a plurality of user utterances received in a natural language dialog with an executing conversation agent;

parse a plurality of semantic graph patterns to identify a semantic graph pattern that matches the at least one intent graph pattern of the plurality of user utterances; and

determine, from the plurality of semantic graph patterns, a matching semantic graph pattern if a subgraph of the matching graph pattern subsumes the at least one intent graph pattern of the plurality of user utterances.

11. The computer program product as described in claim 10, further comprising computer readable instructions to obtain the plurality of user utterances from one or more users as part of an interactive natural language dialog with the conversation agent.

12. The computer program product as described in claim 11, further comprising using the matching semantic graph pattern by the conversation agent to engage in a subsequent interactive natural language dialog with the one or more users.

13. The computer program product as described in claim 10, wherein the computer readable instructions to parse further include computer readable instructions to compare the at least one intent graph pattern of the plurality of user utterances with a plurality of semantic graph patterns by parsing semantic graph patterns of user utterances that are part of semantic clusters that are formed for like topics.

14. The computer program product as described in claim 10, wherein the computer readable instructions to form an intent graph pattern of the plurality of user utterances further include computer readable instructions to parse conversation logs of the conversation agent.

15. The computer program product as described in claim 10, wherein the computer readable instructions to form an intent graph pattern of the plurality of user utterances further includes identifying an intersection of pairs of semantic graphs representing one or more of the plurality of user utterances.

16. The computer program product as described in claim 10, wherein the subgraph of the matching semantic graph subsumes the pattern if the matching semantic graph pattern is transformable into the intent graph pattern of the plurality of user utterances.

17. The computer program product as described in claim 16, wherein the matching semantic graph pattern includes inter-connected nodes and edges and has traits defined therein, and wherein the method further comprises computer readable instructions to transform the matching semantic graph by at least one of the following:

deleting at least one node and at least one incoming edge from the matching semantic graph pattern;

deleting a trait from the matching semantic graph pattern; and

replacing a value of a trait in the matching semantic graph pattern with another value that subsumes the replaced trait value.

18. The computer program product as described in claim 10, further comprising computer readable instructions to:

output the intent graph pattern of the plurality of user utterances in a user interface; and

configure the user interface to receive one or more inputs to modify the intent graph pattern of the plurality of user utterances, wherein the one or more inputs include a subset of the plurality of user utterances to be used in the modifying of the intent graph pattern of the plurality of user utterances.

19. A data processing system, the system comprising:

a conversation agent, executing on one or more computer processors, the conversation agent configured to facilitate forming at least one intent graph pattern from a plurality of user utterances received in a natural language dialog with one or more users; and

a parser configured to parse a plurality of semantic graph patterns to determine a semantic graph pattern that matches the at least one intent graph pattern of the plurality of user utterances, a matching semantic graph pattern being determined if a subgraph of the matching graph pattern subsumes the at least one intent graph pattern of the plurality of user utterances.

20. The data processing system as described in claim 19, wherein the subgraph of the matching semantic graph subsumes the pattern if the matching semantic graph pattern is transformed into the intent graph pattern of the plurality of user utterances.