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

• US 8,700,404 B1
• Filed: 08/27/2005
• Issued: 04/15/2014
• Est. Priority Date: 08/27/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Chotimongkol, Ananlada, Hakkani-Tur, Dilek Z., Tur, Gokhan
• Primary Examiner(s): Desir, Pierre-Louis
• Assistant Examiner(s): KOVACEK, DAVID M
• Application Number:
  US11/212,266
• Time in Patent Office: 3,153 Days
• Field of Search: 704 9- 10, 704231-232, 704236-245, 704246-257, 704E15001-E15009, 704E15014-E15024, 704E11001-E11007
• US Class Current: 704/257
• 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 a user utterance as part of a natural language dialog with a human user;

applying a word n-gram classifier to the user utterance to obtain a first call type for the utterance;

when a confidence associated with the first call type meets a threshold level, associating the user utterance with the first call type to yield a classified utterance;

when the confidence associated with the first call type does not meet the threshold level, performing the steps of;

(i) generating a semantic and syntactic graph associated with the user utterance;

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

(iii) 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 n-grams;

(iv) extracting the n-grams as features from the third finite state transducer, to yield extracted n-grams; and

(v) associating the user 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 the human 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 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 user utterance.

6. The method of claim 1, wherein generating a semantic and syntactic graph associated with the user 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 user 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. The method of claim 1, wherein extracting the n-grams as features from the semantic and syntactic graph further comprises enumerating all paths of the third finite state transducer.

9. The method of claim 1, wherein classifying the user utterance further comprises classifying the user utterance using one of:

the extracted n-grams, the semantic, and syntactic graph and writing rules.

10. 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 a user utterance as part of a natural language dialog with a human user;

applying a word n-gram classifier to the user utterance to obtain a first call type for the utterance;

when a confidence associated with the first call type meets a threshold level, associating the user utterance with the first call type to yield a classified utterance;

when the confidence associated with the first call type does not meet the threshold level, performing the steps of;

(i) generating a semantic and syntactic graph associated with the user utterance;

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

(iii) 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 n-grams;

(iv) extracting the n-grams as features from the third finite state transducer, to yield extracted n-grams; and

(v) associating the user 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 the human user in the natural language dialog based on the classified utterance.

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

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

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

14. The system of claim 10, wherein generating the semantic and syntactic graph further extends a feature set of a classifier that classifies the user utterance.

15. The system of claim 10, wherein generating the semantic and syntactic graph associated with the received utterance further adds transitions encoding semantic and syntactic categories of words to a word graph.

16. The system of claim 10, wherein generating the semantic and syntactic graph associated with the user utterance further utilizes one of:

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

17. The system of claim 10, wherein extracting the n-grams as features from the semantic and syntactic graph further enumerates all paths of the third finite state transducer.

18. The system of claim 10, wherein classifying the user utterance further classifies the user utterance using one of:

the extracted n-grams, the semantic and syntactic graph and writing rules.

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

receiving a user utterance as part of a natural language dialog with a human user;

applying a word n-gram classifier to the user utterance to obtain a first call type for the utterance;

when a confidence associated with the first call type meets a threshold level, associating the user utterance with the first call type to yield a classified utterance;

when the confidence associated with the first call type does not meet the threshold level, performing the steps of;

(i) generating a semantic and syntactic graph associated with the user utterance;

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

(iii) 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 n-grams;

(iv) extracting the n-grams as features from the third finite state transducer, to yield extracted n-grams; and

(v) associating the user 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 the human user in the natural language dialog based on the classified utterance.

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

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

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

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

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

25. The computer-readable storage device of claim 19, wherein generating a semantic and syntactic graph associated with the user 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.

26. The computer-readable storage device of claim 19, wherein extracting n-grams as features from the semantic and syntactic graph further comprises enumerating all paths of the third finite state transducer.

27. The computer-readable storage device of claim 19, wherein classifying the user utterance further comprises classifying the user utterance based on one of:

the extracted n-grams, the semantic and syntactic graph and writing rules.