Dialog Prediction Using Lexical and Semantic Features

• US 20100217592A1
• Filed: 10/14/2009
• Published: 08/26/2010
• Est. Priority Date: 10/14/2008
• Status: Active Grant

• Current Assignee: Honda Motor Co., Ltd. (Honda Motor Company)
• Original Assignee: Honda Motor Co., Ltd. (Honda Motor Company)
• Inventors: Ratinov, Lev-Arie, Gupta, Rakesh
• Granted Patent: US 9,348,816 B2
• Time in Patent Office: Days
• US Class Current: 704/236
• CPC Class Codes: G06F 40/35 Discourse or dialogue representation

Abstract

The present invention provides a method for identifying a turn, such as a sentence or phrase, for addition to a platform dialog comprising a plurality of turns. Lexical features of each of a set of candidate turns relative to one or more turns in the platform dialog are determined. Semantic features associated with each candidate turn and associated with the platform dialog are determined to identify one or more topics associated with each candidate turn and with the platform dialog. Lexical features of each candidate turn are compared to lexical features of the platform dialog and semantic features associated with each candidate turn are compared to semantic features of the platform dialog to rank the candidate turns based on similarity of lexical features and semantic features of each candidate turn to lexical features and semantic features of the platform dialog.

Claims

1. A computer-implemented method for identifying a candidate turn for addition to a platform dialog, the method comprising the steps of:

determining one or more lexical features of each candidate turn in a set of candidate turns relative to one or more turns included in the platform dialog;

determining one or more semantic features associated with each candidate turn and associated with the platform dialog, a semantic feature associated with a candidate turn identifying one or more topics associated with the candidate turn and a semantic feature associated with the platform dialog identifying one or more topics associated with the platform dialog;

ranking the set of candidate turns based on a similarity of the one or more lexical features of the one or more candidate turns to one or more lexical features of the platform dialog and based on a similarity of the one or more semantic features of the one or more candidate turns to one or more semantic features of the platform dialog; and

adding a candidate turn having a highest ranking to the platform dialog.

2. The computer-implemented method of claim 1, wherein determining one or more lexical features of each candidate turn relative to one or more turns included in the platform dialog comprises the steps of:

determining overlapping lexical features between a candidate turn and one or more turns included in the platform dialog; and

identifying one or more transition features between the candidate turn and one or more turns included in the platform dialog.

3. The computer-implemented method of claim 2, wherein determining overlapping lexical features between the candidate turn and one or more turns included in the platform dialog comprises the step of:

determining a percentage of lexical features included in the candidate turn and also included in one or more turns included in the platform dialog.

4. The computer-implemented method of claim 3, wherein the overlapping lexical features comprise at least one of:

tokens, stemmed tokens, bigrams or stemmed bigrams.

5. The computer-implemented method of claim 2, wherein determining overlapping lexical features between the candidate turn and one or more turns included in the platform dialog comprises:

determining a temporal proximity of a turn included in the platform to the candidate turn; and

weighting an influence of the turn included in the platform so that a turn included in the platform temporally near the candidate turn has a larger weight.

6. The computer-implemented method of claim 2, wherein identifying one or more transition features between the candidate turn and one or more turns included in the platform dialog comprises the steps of:

generating a plurality of bigrams pairing a feature from the candidate turn with a feature from a turn included in the platform dialog; and

determining whether a bigram includes a pairing of a feature from the candidate turn with a feature from a turn included in the platform dialog associated with incoherence.

7. The computer-implemented method of claim 1, wherein determining one or more semantic features associated with each candidate turn and associated with the platform dialog comprises the step of:

determining evocation relationships between the candidate turn and one or more turns in the platform dialog, an evocation relationship identifying a topic associated with the candidate turn that is evoked from a topic associated with a turn in the platform dialog.

8. The computer-implemented method of claim 7, wherein determining evocation relationships between the candidate turn and one or more turns in the platform dialog comprises the steps of:

extracting a set of evocation relationship pairs from structured data, one or more synsets or clustered data, each evocation relationship including a first word and a second word which is evoked from the first word; and

determining whether a word from the turn in the platform dialog is the first word in an evocation relationship pair and a word from the candidate turn is the second word in the evocation relationship pair.

9. The computer-implemented method of claim 1, wherein determining one or more semantic features associated with each candidate turn and associated with the platform dialog comprises the steps of:

generating a platform concept vector associated with the platform dialog, the platform concept vector associating one or more topics with the platform dialog based on content of the platform dialog;

generating a candidate concept vector associated with the candidate turn, the candidate concept vector associating one or more topics with the candidate turn based on content of the candidate turn; and

comparing the platform concept vector to the candidate concept vector to generate a similarity metric indicating a number of topics overlapping between the platform dialog and the candidate turn.

10. The computer-implemented method of claim 9, wherein generating the candidate concept vector associated with the candidate turn comprises the steps of:

determining one or more topics from labeled data, the labeled data including text data organized into one or more categories;

comparing the candidate turn to the one or more topics from the labeled data to generate one or more similarity values between the candidate turn and each topic; and

storing a set of topics from the labeled data associated with a set of similarity values exceeding a threshold value.

11. The computer-implemented method of claim 1, wherein determining one or more semantic features associated with each candidate turn and associated with the platform dialog comprises the steps of:

determining evocation relationships between the candidate turn and one or more turns in the platform dialog, an evocation relationship identifying a topic associated with the candidate turn that is evoked from a topic associated with a turn in the platform dialog;

generating a platform concept vector associated with the platform dialog, the platform concept vector associating one or more topics with the platform dialog based on content of the platform dialog;

generating a candidate concept vector associated with the candidate turn, the candidate concept vector associating one or more topics with the candidate turn based on content of the candidate turn; and

comparing the platform concept vector to the candidate concept vector to generate a similarity metric indicating a number of topics overlapping between the platform dialog and the candidate turn.

12. A computer program product comprising a computer readable storage medium storing computer executable code for identifying a candidate turn for addition to a platform dialog, the computer executable code performing the steps of:

determining one or more lexical features of each candidate turn in a set of candidate turns relative to one or more turns included in the platform dialog;

determining one or more semantic features associated with each candidate turn and associated with the platform dialog, a semantic feature associated with a candidate turn identifying one or more topics associated with the candidate turn and a semantic feature associated with the platform dialog identifying one or more topics associated with the platform dialog;

ranking the set of candidate turns based on a similarity of the one or more lexical features of the one or more candidate turns to one or more lexical features of the platform dialog and based on a similarity of the one or more semantic features of the one or more candidate turns to one or more semantic features of the platform dialog; and

adding a candidate turn having a highest ranking to the platform dialog.

13. The computer program product of claim 12, wherein determining one or more lexical features of each candidate turn relative to one or more turns included in the platform dialog comprises the steps of:

determining overlapping lexical features between a candidate turn and one or more turns included in the platform dialog; and

identifying one or more transition features between the candidate turn and one or more turns included in the platform dialog.

14. The computer program product of claim 13, wherein determining overlapping lexical features between the candidate turn and one or more turns included in the platform dialog comprises the step of:

determining a percentage of lexical features included in the candidate turn and also included in one or more turns included in the platform dialog.

15. The computer program product of claim 14, wherein the overlapping lexical features comprise at least one of:

tokens, stemmed tokens, bigrams or stemmed bigrams.

16. The computer program product of claim 13, wherein determining overlapping lexical features between the candidate turn and one or more turns included in the platform dialog comprises:

determining a temporal proximity of a turn included in the platform to the candidate turn; and

weighting an influence of the turn included in the platform so that a turn included in the platform temporally near the candidate turn has a larger weight.

17. The computer program product of claim 13, wherein identifying one or more transition features between the candidate turn and one or more turns included in the platform dialog comprises the steps of:

generating a plurality of bigrams pairing a feature from the candidate turn with a feature from a turn included in the platform dialog; and

determining whether a bigram includes a pairing of a feature from the candidate turn with a feature from a turn included in the platform dialog associated with incoherence.

18. The computer program product of claim 12, wherein determining one or more semantic features associated with each candidate turn and associated with the platform dialog comprises the step of:

determining evocation relationships between the candidate turn and one or more turns in the platform dialog, an evocation relationship identifying a topic associated with the candidate turn that is evoked from a topic associated with a turn in the platform dialog.

19. The computer program product of claim 18, wherein determining evocation relationships between the candidate turn and one or more turns in the platform dialog comprises the steps of:

extracting a set of evocation relationship pairs from structured data, one or more synsets or clustered data, each evocation relationship including a first word and a second word which is evoked from the first word; and

determining whether a word from the turn in the platform dialog is the first word in an evocation relationship pair and a word from the candidate turn is the second word in the evocation relationship pair.

20. The computer program product of claim 12, wherein determining one or more semantic features associated with each candidate turn and associated with the platform dialog comprises the steps of:

generating a platform concept vector associated with the platform dialog, the platform concept vector associating one or more topics with the platform dialog based on content of the platform dialog;

generating a candidate concept vector associated with the candidate turn, the candidate concept vector associating one or more topics with the candidate turn based on content of the candidate turn; and

comparing the platform concept vector to the candidate concept vector to generate a similarity metric indicating a number of topics overlapping between the platform dialog and the candidate turn.

21. The computer program product of claim 20, wherein generating the candidate concept vector associated with the candidate turn comprises the steps of:

determining one or more topics from labeled data, the labeled data including text data organized into one or more categories;

comparing the candidate turn to the one or more topics from the labeled data to generate one or more similarity values between the candidate turn and each topic; and

storing a set of topics from the labeled data associated with a set of similarity values exceeding a threshold value.

22. The computer program product of claim 12, wherein determining one or more semantic features associated with each candidate turn and associated with the platform dialog comprises the steps of:

determining evocation relationships between the candidate turn and one or more turns in the platform dialog, an evocation relationship identifying a topic associated with the candidate turn that is evoked from a topic associated with a turn in the platform dialog;

generating a platform concept vector associated with the platform dialog, the platform concept vector associating one or more topics with the platform dialog based on content of the platform dialog;

generating a candidate concept vector associated with the candidate turn, the candidate concept vector associating one or more topics with the candidate turn based on content of the candidate turn; and

comparing the platform concept vector to the candidate concept vector to generate a similarity metric indicating a number of topics overlapping between the platform dialog and the candidate turn.

23. A computing system for identifying a candidate turn for addition to a platform dialog comprising:

identifying a candidate turn for addition to a platform dialog, the method comprising the steps of;

a dialog store including the platform turn and one or more stored dialogs from which a set of candidate turns are generated;

a lexical analysis module coupled to the dialog store, the lexical analysis module determining one or more lexical features of each candidate turn relative to one or more turns included in the platform dialog;

a semantic analysis module coupled to the dialog store, the semantic analysis module determining one or more semantic features associated with each candidate turn and one or more semantic features associated with the platform dialog, a semantic feature associated with a candidate turn identifying one or more topics associated with the candidate turn and a semantic feature associated with the platform dialog identifying one or more topics associated with the platform dialog; and

a dialog prediction module coupled to the dialog store, the lexical analysis module and the semantic analysis module, the dialog prediction module ranking the set of candidate turns based on a similarity of the one or more lexical features of the one or more candidate turns to one or more lexical features of the platform dialog and based on a similarity of the one or more semantic features of the one or more candidate turns to one or more semantic features of the platform dialog and adding a candidate turn having a highest ranking to the platform dialog.

24. The system of claim 23, wherein the semantic analysis module:

determines evocation relationships between the candidate turn and one or more turns in the platform dialog, an evocation relationship identifying a topic associated with the candidate turn that is evoked from a topic associated with a turn in the platform dialog.

25. The system of claim 23, wherein the semantic analysis module:

generates a platform concept vector associated with the platform dialog, the platform concept vector associating one or more topics with the platform dialog based on content of the platform dialog;

generates a candidate concept vector associated with the candidate turn, the candidate concept vector associating one or more topics with the candidate turn based on content of the candidate turn; and

compares the platform concept vector to the candidate concept vector to generate a similarity metric indicating a number of topics overlapping between the platform dialog and the candidate turn.

26. The system of claim 25 wherein the semantic analysis module further:

determines evocation relationships between the candidate turn and one or more turns in the platform dialog, an evocation relationship identifying a topic associated with the candidate turn that is evoked from a topic associated with a turn in the platform dialog.

27. The system of claim 23, wherein the lexical analysis module:

determines overlapping lexical features between a candidate turn and one or more turns included in the platform dialog; and

identifies one or more transition features between the candidate turn and one or more turns included in the platform dialog.