Clustering user utterance intents with semantic parsing

• US 10,134,389 B2
• Filed: 09/04/2015
• Issued: 11/20/2018
• Est. Priority Date: 09/04/2015
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Hakkani-Tur, Dilek, Ju, Yun-Cheng, Zweig, Geoffrey G., Tur, Gokhan
• Primary Examiner(s): Opsasnick, Michael N
• Application Number:
  US14/846,486
• Publication Number:
  US 20170069310A1
• Time in Patent Office: 1,173 Days
• Field of Search: 704 4, 704 9
• CPC Class Codes: G06F 40/205 Parsing
• CPC Class Codes: G06F 40/30 Semantic analysis
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation
• CPC Class Codes: G10L 15/063 Training
• CPC Class Codes: G10L 15/1815 Semantic context, e.g. disambiguation of the recognition hypotheses based on word meaning
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding
• CPC Class Codes: G10L 15/22 Procedures used during a speech recognition process, e.g. man-machine dialogue
• CPC Class Codes: G10L 2015/0631 Creating reference templates; Clustering
• CPC Class Codes: G10L 2015/223 Execution procedure of a spoken command

Abstract

A system is provided that trains a spoken language understanding (SLU) classifier. A corpus of user utterances is received. For each of the user utterances in the corpus, the user utterance is semantically parsed, and the result of this semantic parsing is represented as a rooted semantic parse graph. The parse graphs representing all of the user utterances in the corpus are then combined into a single corpus graph that represents the semantic parses of the entire corpus. The user utterances in the corpus are then clustered into intent-wise homogeneous groups of user utterances, where this clustering includes finding subgraphs in the corpus graph that represent different groups of user utterances, and each of these different groups has a similar user intent. The intent-wise homogeneous groups of user utterances are then used to train the SLU classifier, and the trained SLU classifier is output.

Claims

1. A system for training a spoken language understanding (SLU) classifier, comprising:

one or more computing devices, said computing devices being in communication with each other via a computer network whenever there is a plurality of computing devices; and

a computer program having program modules executable by the one or more computing devices, the one or more computing devices being directed by the program modules of the computer program to,

receive a corpus of user utterances,

for each of the user utterances in the corpus,

semantically parse the user utterance, and

represent the result of said semantic parsing as a rooted semantic parse graph,

combine the parse graphs representing all of the user utterances in the corpus into a single corpus graph that represents the semantic parses of the entire corpus and comprises a root node that is common to the parse graph representing each of the user utterances in the corpus,

cluster the user utterances in the corpus into intent-wise homogeneous groups of user utterances, said clustering comprising finding subgraphs in the corpus graph that represent different groups of user utterances, each of said different groups having a similar user intent, each of the subgraphs being more specific than the root node alone and more general than the full semantic parses of the individual user utterances,

use the intent-wise homogeneous groups of user utterances to train the SLU classifier, and

output the trained SLU classifier.

2. The system of claim 1, wherein the semantic parsing of each of the user utterances in the corpus is performed using an Abstract Meaning Representation semantic parser that considers the lexical semantic structure of each of the user utterances.

3. The system of claim 1, wherein the semantic parsing of each of the user utterances in the corpus is performed using a Proposition Bank semantic parser.

4. The system of claim 1, wherein the semantic parsing of each of the user utterances in the corpus is performed using one of:

a dependency parser;

or

a FrameNet semantic parser;

or

the dependency parser combined with the FrameNet semantic parser.

5. The system of claim 1, wherein the corpus graph further comprises a plurality of child nodes and a plurality of edges each of which either connects the root node to one of the child nodes or connects one of the child nodes to another one of the child nodes, and the program module for clustering the user utterances in the corpus into intent-wise homogeneous groups of user utterances comprises program modules for:

computing the frequency of occurrence of each of the child nodes in the corpus graph,

identifying the child nodes in the corpus graph whose frequency of occurrence is less than a prescribed threshold, and

pruning the corpus graph by eliminating the identified child nodes and the edges connected thereto from the corpus graph.

6. The system of claim 1, wherein the corpus graph further comprises a plurality of child nodes and a plurality of edges each of which either connects the root node to one of the child nodes or connects one of the child nodes to another one of the child nodes, and the program module for clustering the user utterances in the corpus into intent-wise homogeneous groups of user utterances comprises program modules for:

computing the entropy at each of the child nodes in the corpus graph,

identifying the child nodes in the corpus graph whose entropy is greater than a prescribed threshold, and

pruning the corpus graph by eliminating the identified child nodes and the edges connected thereto from the corpus graph.

7. The system of claim 6, wherein said pruning is performed via a breadth-first traversal of the corpus graph.

8. The system of claim 1, wherein the corpus graph further comprises a plurality of child nodes and a plurality of edges each of which either connects the root node to one of the child nodes or connects one of the child nodes to another one of the child nodes, and the program module for clustering the user utterances in the corpus into intent-wise homogeneous groups of user utterances comprises program modules for:

computing the frequency of occurrence of each of the child nodes in the corpus graph,

initially identifying the child nodes in the corpus graph whose frequency of occurrence is less than a prescribed frequency threshold,

initially pruning the corpus graph by eliminating the initially identified child nodes and the edges connected thereto from the corpus graph,

computing the entropy at each of the child nodes in the initially pruned corpus graph,

subsequently identifying the child nodes in the initially pruned corpus graph whose entropy is greater than a prescribed entropy threshold, and

subsequently pruning the initially pruned corpus graph by eliminating the subsequently identified child nodes and the edges connected thereto from the initially pruned corpus graph.

9. The system of claim 1, wherein the corpus graph further comprises a plurality of child nodes and a plurality of edges each of which either connects the root node to one of the child nodes or connects one of the child nodes to another one of the child nodes, and the program module for clustering the user utterances in the corpus into intent-wise homogeneous groups of user utterances comprises program modules for:

computing the entropy at each of the child nodes in the corpus graph,

initially identifying the child nodes in the corpus graph whose entropy is greater than a prescribed entropy threshold,

initially pruning the corpus graph by eliminating the initially identified child nodes and the edges connected thereto from the corpus graph,

computing the frequency of occurrence of each of the child nodes in the initially pruned corpus graph,

subsequently identifying the child nodes in the initially pruned corpus graph whose frequency of occurrence is less than a prescribed frequency threshold, and

subsequently pruning the initially pruned corpus graph by eliminating the subsequently identified child nodes and the edges connected thereto from the initially pruned corpus graph.

10. The system of claim 1, wherein the corpus graph further comprises a plurality of child nodes and a plurality of edges each of which either connects the root node to one of the child nodes or connects one of the child nodes to another one of the child nodes, and the program module for clustering the user utterances in the corpus into intent-wise homogeneous groups of user utterances comprises program modules for:

computing the semantic similarity of each of the child nodes in the corpus graph to all of the other child nodes in the corpus graph,

identifying the child nodes in the corpus graph whose semantic similarity is less than a prescribed threshold, and

pruning the corpus graph by eliminating the identified child nodes and the edges connected thereto from the corpus graph.

11. The system of claim 1, wherein said SLU classifier training is performed using a machine learning method comprising one of:

a logistic regression method;

or

a decision trees method;

or

a support vector machine method.

12. The system of claim 1, wherein the SLU classifier comprises one of:

a support vector machine;

or

an artificial neural network;

or

a Bayesian statistical classifier.

13. An utterance intent determination system, comprising:

one or more computing devices, said computing devices being in communication with each other via a computer network whenever there is a plurality of computing devices; and

a computer program having program modules executable by the one or more computing devices, the one or more computing devices being directed by the program modules of the computer program to,

receive a corpus of user utterances,

for each of the user utterances in the corpus,

semantically parse the user utterance, and

represent the result of said semantic parsing as a rooted semantic parse graph,

combine the parse graphs representing all of the user utterances in the corpus into a single corpus graph that represents the semantic parses of the entire corpus and comprises a root node that is common to the parse graph representing each of the user utterances in the corpus,

cluster the user utterances in the corpus into intent-wise homogeneous groups of user utterances, said clustering comprising finding subgraphs in the corpus graph that represent different groups of user utterances, each of said different groups having a similar user intent, each of the subgraphs being more specific than the root node alone and more general than the full semantic parses of the individual user utterances,

use the intent-wise homogeneous groups of user utterances to train a spoken language understanding (SLU) classifier,

receive a particular utterance input by a user, and

use the trained SLU classifier to determine the intent of the user from said particular utterance.

14. The system of claim 13, wherein said particular utterance is an uncovered, out-of-domain user utterance.

15. The system of claim 13, wherein the corpus graph further comprises a plurality of child nodes and a plurality of edges each of which either connects the root node to one of the child nodes or connects one of the child nodes to another one of the child nodes, and the program module for clustering the user utterances in the corpus into intent-wise homogeneous groups of user utterances comprises program modules for:

computing the frequency of occurrence of each of the child nodes in the corpus graph,

identifying the child nodes in the corpus graph whose frequency of occurrence is less than a prescribed threshold, and

pruning the corpus graph by eliminating the identified child nodes and the edges connected thereto from the corpus graph.

16. The system of claim 13, wherein the corpus graph further comprises a plurality of child nodes and a plurality of edges each of which either connects the root node to one of the child nodes or connects one of the child nodes to another one of the child nodes, and the program module for clustering the user utterances in the corpus into intent-wise homogeneous groups of user utterances comprises program modules for:

computing the entropy at each of the child nodes in the corpus graph,

identifying the child nodes in the corpus graph whose entropy is greater than a prescribed threshold, and

pruning the corpus graph by eliminating the identified child nodes and the edges connected thereto from the corpus graph.

17. The system of claim 13, wherein the corpus graph further comprises a plurality of child nodes and a plurality of edges each of which either connects the root node to one of the child nodes or connects one of the child nodes to another one of the child nodes, and the program module for clustering the user utterances in the corpus into intent-wise homogeneous groups of user utterances comprises program modules for:

computing the frequency of occurrence of each of the child nodes in the corpus graph,

initially identifying the child nodes in the corpus graph whose frequency of occurrence is less than a prescribed frequency threshold,

initially pruning the corpus graph by eliminating the initially identified child nodes and the edges connected thereto from the corpus graph,

computing the entropy at each of the child nodes in the initially pruned corpus graph,

subsequently identifying the child nodes in the initially pruned corpus graph whose entropy is greater than a prescribed entropy threshold, and

subsequently pruning the initially pruned corpus graph by eliminating the subsequently identified child nodes and the edges connected thereto from the initially pruned corpus graph.

18. The system of claim 13, wherein the corpus graph further comprises a plurality of child nodes and a plurality of edges each of which either connects the root node to one of the child nodes or connects one of the child nodes to another one of the child nodes, and the program module for clustering the user utterances in the corpus into intent-wise homogeneous groups of user utterances comprises program modules for:

computing the entropy at each of the child nodes in the corpus graph,

initially identifying the child nodes in the corpus graph whose entropy is greater than a prescribed entropy threshold,

initially pruning the corpus graph by eliminating the initially identified child nodes and the edges connected thereto from the corpus graph,

computing the frequency of occurrence of each of the child nodes in the initially pruned corpus graph,

subsequently identifying the child nodes in the initially pruned corpus graph whose frequency of occurrence is less than a prescribed frequency threshold, and

subsequently pruning the initially pruned corpus graph by eliminating the subsequently identified child nodes and the edges connected thereto from the initially pruned corpus graph.

19. The system of claim 13, wherein the corpus graph further comprises a plurality of child nodes and a plurality of edges each of which either connects the root node to one of the child nodes or connects one of the child nodes to another one of the child nodes, and the program module for clustering the user utterances in the corpus into intent-wise homogeneous groups of user utterances comprises program modules for:

computing the semantic similarity of each of the child nodes in the corpus graph to all of the other child nodes in the corpus graph,

identifying the child nodes in the corpus graph whose semantic similarity is less than a prescribed threshold, and

pruning the corpus graph by eliminating the identified child nodes and the edges connected thereto from the corpus graph.

20. A computer-implemented process for training a spoken language understanding (SLU) classifier, comprising the actions of:

using one or more computing devices to perform the following process actions, the computing devices being in communication with each other via a computer network whenever a plurality of computing devices is used;

receiving a corpus of user utterances,

for each of the user utterances in the corpus,

semantically parsing the user utterance, and

representing the result of said semantic parsing in a hierarchical structure,

combining the hierarchical structures representing all of the user utterances in the corpus into a single hierarchical structure that represents the semantic parses of the entire corpus and comprises a root node that is common to the hierarchical structure representing each of the user utterances in the corpus,

clustering the user utterances in the corpus into intent-wise homogeneous groups of user utterances, said clustering comprising finding substructures in the single hierarchical structure that represent different groups of user utterances, each of said different groups having a similar user intent, each of the substructures being more specific than the root node alone and more general than the full semantic parses of the individual user utterances,

using the intent-wise homogeneous groups of user utterances to train the SLU classifier, and

outputting the trained SLU classifier.