System and method for using semantic and syntactic graphs for utterance classification

• US 9,905,223 B2
• Filed: 12/09/2015
• Issued: 02/27/2018
• Est. Priority Date: 08/27/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Inventors: Chotimongkol, Ananlada, Hakkani-Tur, Dilek Z., Tur, Gokhan
• Primary Examiner(s): Baker, Matthew
• Application Number:
  US14/963,423
• Publication Number:
  US 20160086601A1
• Time in Patent Office: 811 Days
• Field of Search: 704 9- 10, 704231-232, 704236-257, 704E15001-E15009, 704E15014-E15024, 704E11001-E11007
• CPC Class Codes: G10L 15/00 Speech recognition G10L17/00 takes precedence
• CPC Class Codes: G10L 15/06 Creation of reference templates; Training of speech recognition systems, e.g. adaptation to the characteristics of the speaker's voice G10L15/14 takes precedence
• CPC Class Codes: G10L 15/07 to the speaker
• CPC Class Codes: G10L 15/10 using distance or distortion measures between unknown speech and reference templates
• CPC Class Codes: G10L 15/18 using natural language modelling
• CPC Class Codes: G10L 15/1815 Semantic context, e.g. disambiguation of the recognition hypotheses based on word meaning
• CPC Class Codes: G10L 15/197 Probabilistic grammars, e.g. word n-grams
• CPC Class Codes: G10L 15/28 Constructional details of speech recognition systems

Abstract

Disclosed herein is a system, method and computer readable medium storing instructions related to semantic and syntactic information in a language understanding system. The method embodiment of the invention is a method for classifying utterances during a natural language dialog between a human and a computing device. The method comprises receiving a user utterance; generating a semantic and syntactic graph associated with the received utterance, extracting all n-grams as features from the generated semantic and syntactic graph and classifying the utterance. Classifying the utterance may be performed any number of ways such as using the extracted n-grams, a syntactic and semantic graphs or writing rules.

Claims

1. A method comprising:

receiving, during a natural language dialog between a user and a computing device, an utterance;

generating, via the computing device, a semantic and syntactic graph using the utterance, the semantic and syntactic graph comprising an initial state and a final state associated with the utterance and being generated by adding transitions that encode semantic and syntactic categories of words or word sequences within the utterance;

extracting possible combinations of features from the semantic and syntactic graph, to yield extracted n-grams;

comparing the extracted n-grams to previously classified n-grams, to yield a comparison;

classifying, via the computing device, the utterance as being associated with a call type based on the extracted n-grams and the comparison, wherein the call type is chosen from a predefined set of call types and wherein the call type characterizes a communication, to yield a classified utterance; and

responding, via the computing device and with a computer-generated response, to the user in the natural language dialog based on the classified utterance.

2. The method of claim 1, wherein the semantic and syntactic graph further comprises lexical information.

3. The method of claim 1, wherein the semantic and syntactic graph further comprises named entities and semantic role labels.

4. The method of claim 1, wherein the semantic and syntactic graph further comprises one of speech tags and a syntactic parse of the utterance.

5. The method of claim 1, wherein generating the semantic and syntactic graph extends a feature set of a classifier that classifies the utterance.

6. The method of claim 1, wherein generating the semantic and syntactic graph associated with the utterance further comprises adding transitions encoding semantic and syntactic categories of words to a word graph.

7. The method of claim 1, wherein generating the semantic and syntactic graph associated with the utterance further comprises utilizing one of:

a part of speech tags, a syntactic parse of the utterance, and generic named entity tags.

8. A system comprising:

a processor; and

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

receiving, during a natural language dialog between a user and a computing device, an utterance;

generating a semantic and syntactic graph using the utterance, the semantic and syntactic graph comprising an initial state and a final state associated with the utterance and being generated by adding transitions that encode semantic and syntactic categories of words or word sequences within the utterance;

extracting possible combinations of features from the semantic and syntactic graph, to yield extracted n-grams;

comparing the extracted n-grams to previously classified n-grams, to yield a comparison;

classifying the utterance as being associated with a call type based on the extracted n-grams and the comparison, wherein the call type is chosen from a predefined set of call types and wherein the call type characterizes a communication, to yield a classified utterance; and

responding, with a computer-generated response, to the user in the natural language dialog based on the classified utterance.

9. The system of claim 8, wherein the semantic and syntactic graph further comprises lexical information.

10. The system of claim 8, wherein the semantic and syntactic graph further comprises named entities and semantic role labels.

11. The system of claim 8, wherein the semantic and syntactic graph further comprises one of speech tags and a syntactic parse of the utterance.

12. The system of claim 8, wherein generating the semantic and syntactic graph extends a feature set of a classifier that performs classifying the utterance.

13. The system of claim 8, wherein generating the semantic and syntactic graph associated with the utterance further comprises adding transitions encoding semantic and syntactic categories of words to a word graph.

14. The system of claim 8, wherein generating the semantic and syntactic graph associated with the utterance further comprises utilizing one of:

a part of speech tags, a syntactic parse of the utterance, and generic named entity tags.

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

receiving, during a natural language dialog between a user and the computing device, an utterance;

generating a semantic and syntactic graph using the utterance, the semantic and syntactic graph comprising an initial state and a final state associated with the utterance and being generated by adding transitions that encode semantic and syntactic categories of words or word sequences within the utterance;

extracting possible combinations of features from the semantic and syntactic graph, to yield extracted n-grams;

comparing the extracted n-grams to previously classified n-grams, to yield a comparison;

classifying the utterance as being associated with a call type based on the extracted n-grams and the comparison, wherein the call type is chosen from a predefined set of call types and wherein the call type characterizes a communication, to yield a classified utterance; and

responding, with a computer-generated response, to the user in the natural language dialog based on the classified utterance.

16. The computer-readable storage device of claim 15, wherein the semantic and syntactic graph further comprises lexical information.

17. The computer-readable storage device of claim 15, wherein the semantic and syntactic graph further comprises named entities and semantic role labels.

18. The computer-readable storage device of claim 15, wherein the semantic and syntactic graph further comprises one of speech tags and a syntactic parse of the utterance.

19. The computer-readable storage device of claim 15, wherein generating the semantic and syntactic graph extends a feature set of a classifier that performs classifying the utterance.

20. The computer-readable storage device of claim 15, wherein generating the semantic and syntactic graph associated with the utterance further comprises adding transitions encoding semantic and syntactic categories of words to a word graph.