Semantic clustering and conversational agents

• US 8,676,565 B2
• Filed: 03/26/2010
• Issued: 03/18/2014
• 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:
  US12/748,133
• Publication Number:
  US 20110238409A1
• Time in Patent Office: 1,453 Days
• Field of Search: 704/1, 704/9, 704/10, 704/257
• US Class Current: 704/9
• 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:

computationally matching one or more of a plurality of utterances into a respective one of a plurality of predefined topics through comparison with one or more corresponding semantic graph patterns; and

for at least one said utterance that was not matched to the semantic graph patterns, computationally generating a semantic graph pattern that described information common to the at least one said utterance.

2. A method as described in claim 1, wherein the plurality of utterances were provided by one or more users as part of an interactive natural language dialog.

3. A method as described in claim 2, wherein the generating of the semantic graph pattern is used by a conversational agent to engage in a subsequent interactive natural language dialog for subsequent said matching.

4. A method as described in claim 1, wherein the matching and the generating are performed automatically and without user intervention by the one or more modules.

5. A method as described in claim 1, wherein the generating is based at least in part on conversation logs.

6. A method as described in claim 1, wherein the generating includes an intersection of pairs of semantic graphs representing said utterances.

7. A method as described in claim 6, wherein the generating is performed for the intersection of pairs of semantic graphs considered in an order of decreasing specificity.

8. A method as described in claim 1, further comprising outputting the generated semantic graph pattern in a user interface.

9. A method as described in claim 8, wherein the user interface is configured to receive one or more inputs to modify the generated semantic graph pattern.

10. A method as described in claim 9, wherein the one or more inputs include specifying the set of utterances to be used in generating the semantic graph pattern.

11. A method as described in claim 8, wherein the user interface is configured to receive one or more inputs to associate the generated semantic graph pattern with a new topic that is not one of the predefined topics.

12. A method as described in claim 8, wherein the user interface is configured to output data that describes one or more likely consequences of adding the generated semantic graph pattern to the conversational agent based on a historical log.

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

clustering a plurality of semantic graphs of user utterances that were produced based on computational linguistic analysis into respective ones of a plurality of semantic clusters based at least in part on a proximity metric; and

exposing a conversational agent that is configured to engage in an interactive natural language dialog using one or more capabilities that leverage the clustering of the plurality of semantic graphs of user utterances, the conversation agent executing on one or more computer processors.

14. A method as described in claim 13, wherein the one or more capabilities include linguistic capabilities.

15. A method as described in claim 13, wherein the clustering adds one or more capabilities to the conversational agent regarding topics.

16. A method as described in claim 13, wherein the proximity metric is a concept-set proximity metric, which for two said semantic graphs is defined as a ratio of aggregate specificity of semantic objects that are common to two said semantic graphs to an aggregate specificity of at least two said semantic objects found in both of the two said semantic graphs.

17. A method as described in claim 13, wherein the clustering further comprises clustering that is performed at least in part through the use of a graph intersection proximity metric.

18. A method as described in claim 17, wherein the graph-intersection proximity metric of two said semantic graphs g1 and g2 includes:

Finding, using an intersection heuristic, an informative graph, called gl *g2, that subsumes both a sub graph of gl and a subgraph of g2, wherein the informative graph'"'"'s informativeness is directly related to the precision of the semantic objects it contains; and

dividing an aggregate specificity of the informative graph gl *g2 by an aggregate specificity of gl and g2.

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

receiving an input that specifies a particular semantic graph of user utterances that is based on a linguistic analysis;

processing a corpus that is a historical log of user utterances, the processing performed using the specified semantic graph of user utterances and one or more other semantic graphs of user utterances that are part of semantic clusters that are formed for like topics; and

outputting a result of the processing in a user interface.

20. A method as described in claim 19, wherein the processing is performed using a concept-set proximity metric.

21. A method as described in claim 19, wherein the processing is performed using a graph-intersection proximity metric.

22. A method as described in claim 19, wherein the processing is performed using by taking a ratio of aggregate specificity of semantic objects that are common to two semantic graphs that are compared to an aggregate specificity of at least two semantic objects found in both of the two semantic graphs.

23. A method as described in claim 19, wherein the user interface is configured to allow an agent to respond to the input.

24. A method as described in claim 19, wherein the user interface is configured to associate the particular semantic graph to at least one said topic of a corresponding said semantic cluster.

25. A method as described in claim 19, wherein the user interface is configured to identify a match of the particular semantic graph to a wrong intent.

26. A computer program product stored on a non-transitory computer readable medium, the computer program product comprising instructions that, responsive to execution by a computing device having one or more processors, causes the computing device to perform operations comprising:

determining that a plurality of utterances do not correspond to one or more predefined semantic clusters, each said semantic cluster corresponding to a topic and including one or more semantic graphs that were generated as part of a linguistic analysis;

forming a plurality of semantic clusters from the plurality of utterances based on linguistic analysis such that each said utterance included in a corresponding said formed semantic cluster corresponds to a similar topic;

automatically generating semantic graph patterns that describe the utterances in the formed semantic clusters;

arranging the generated semantic graph patterns in order of specificity; and

outputting the arranged semantic graph patterns for display in a user interface.

27. The computer program product as described in claim 26, wherein the user interface is configured to receive one or more inputs to modify one or more of the output semantic graph patterns.

28. The computer program product as described in claim 26, wherein the user interface is configured to receive one or more inputs to associate one or more of the output semantic graph patterns with at least one topic of the predefined semantic clusters.

29. The computer program product as described in claim 26, wherein the user interface is configured to receive one or more inputs to associate one or more of the output semantic graph patterns with a new topic of a new semantic cluster that is not one of the predefined semantic clusters.

30. The computer program product as described in claim 26, wherein the user interface is configured to output data that describes one or more likely consequences of adding one or more of the output semantic graph patterns to a conversational agent based on a historical log.

31. The computer program product as described in claim 26, wherein the instructions are further configured to automatically add the generated semantic graph pattern to a conversational agent to engage in an interactive natural language dialog.

32. A computer program product stored on a non-transitory computer readable medium, the computer program product comprising:

executable instructions that, responsive to execution by a computing device, causes the computing device to suggest a semantic graph pattern, which describes at least one utterance that was not matched to a direct pattern during natural language processing but was matched to an indirect pattern that corresponds to a plurality of intents for use by a conversational agent that is configured to engage in an interactive natural language dialog.

33. The computer program product as described in claim 32, wherein the semantic graph pattern is configured to act as a direct pattern to elicit a question from a user that provided the at least one utterance to determine which of the plurality of intents is likely to be of interest to the user.

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

clustering a plurality of semantic graphs that were formed based on a linguistic analysis of a corpus of user utterances into a plurality of semantic clusters through use of one or more proximity metrics;

identifying which of the plurality of semantic clusters include divergent sub-clusters; and

offering the identified semantic clusters for review in a user interface.

35. A method as described in claim 34, wherein the offering is performed for both divergent and convergent sub-clusters in the identified semantic clusters.

36. A method as described III claim 34, wherein the clustering is performed hierarchically at two levels.

37. A method as described in claim 34, wherein the clustering is performed to form sub-clusters that are obtained using clustering criteria that are tuned to a level of specificity of the semantic graphs.

38. A method as described in claim 34, wherein the user interface is configured to accept one or more corrective actions that include fixing a particular semantic graph pattern that is mismatched or adding a semantic graph pattern with increased specificity to a correct intent associated with at least one said semantic cluster.

39. A method as described in claim 34, wherein the divergent subclusters correspond to different intents, respectively.