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

• US 9,218,810 B2
• Filed: 04/15/2014
• Issued: 12/22/2015
• Est. Priority Date: 08/27/2005
• Status: Expired due to Fees

• Current Assignee: Nuance Communications, Inc. (Microsoft Corporation)
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Hakkani-Tur, Dilek Z., Tur, Gokhan, Chotimongkol, Ananlada
• Primary Examiner(s): Desir, Pierre-Louis
• Assistant Examiner(s): KOVACEK, DAVID M
• Application Number:
  US14/252,817
• Publication Number:
  US 20140229179A1
• Time in Patent Office: 616 Days
• Field of Search: 704 9- 10, 704231-232, 704236-245, 704246-257, 704E15001-E15009, 704E15014-E15024, 704E11001-E11007
• US Class Current: 1/1
• 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:

generating, via a processor, a semantic and syntactic graph associated with a first call type;

converting the semantic and syntactic graph into a first finite state transducer;

composing the first finite state transducer with a second finite state transducer to form a third finite state transducer, wherein the second finite state transducer comprises all possible n-grams, and wherein the third finite state transducer comprises a subset of the all-possible n-grams;

extracting the subset of the all-possible n-grams as features from the third finite state transducer, to yield extracted n-grams;

associating an utterance with a second call type based on the extracted n-grams, to yield a classified utterance, wherein the second call type is determined based on semantic and syntactic features in the extracted n-grams; and

responding to a user in a 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 2, wherein the semantic and syntactic graph further comprises named entities and semantic role labels.

4. The method of claim 2, 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 performs classifying the utterance.

6. The method of claim 1, wherein generating a 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 a semantic and syntactic graph associated with the utterance further comprises utilizing one of:

part of speech tags, a syntactic parse of the utterance, generic named entity tags, supertags and word stems in the graph.

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;

generating a semantic and syntactic graph associated with a first call type;

converting the semantic and syntactic graph into a first finite state transducer;

composing the first finite state transducer with a second finite state transducer to form a third finite state transducer, wherein the second finite state transducer comprises all possible n-grams, and wherein the third finite state transducer comprises a subset of the all-possible n-grams;

extracting the subset of the all-possible n-grams as features from the third finite state transducer, to yield extracted n-grams;

associating an utterance with a second call type based on the extracted n-grams, to yield a classified utterance, wherein the second call type is determined based on semantic and syntactic features in the extracted n-grams; and

responding to a user in a 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 9, wherein the semantic and syntactic graph further comprises named entities and semantic role labels.

11. The system of claim 9, 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 a 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 a semantic and syntactic graph associated with the utterance further comprises utilizing one of:

part of speech tags, a syntactic parse of the utterance, generic named entity tags, supertags and word stems in the graph.

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

generating a semantic and syntactic graph associated with a first call type;

converting the semantic and syntactic graph into a first finite state transducer;

composing the first finite state transducer with a second finite state transducer to form a third finite state transducer, wherein the second finite state transducer comprises all possible n-grams, and wherein the third finite state transducer comprises a subset of the all-possible n-grams;

extracting the subset of the all-possible n-grams as features from the third finite state transducer, to yield extracted n-grams;

associating an utterance with a second call type based on the extracted n-grams, to yield a classified utterance, wherein the second call type is determined based on semantic and syntactic features in the extracted n-grams; and

responding to a user in a 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 16, wherein the semantic and syntactic graph further comprises named entities and semantic role labels.

18. The computer-readable storage device of claim 16, 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 a semantic and syntactic graph associated with the utterance further comprises adding transitions encoding semantic and syntactic categories of words to a word graph.