Learning generation templates from dialog transcripts

• US 9,473,637 B1
• Filed: 07/28/2015
• Issued: 10/18/2016
• Est. Priority Date: 07/28/2015
• Status: Active Grant

• Current Assignee: Conduent Business Services, LLC (Conduent, Inc.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Venkatapathy, Sriram, Mirkin, Shachar, Dymetman, Marc
• Primary Examiner(s): Addy, Thjuan K
• Application Number:
  US14/810,817
• Time in Patent Office: 448 Days
• Field of Search: 379/265.07, 379/88.01, 379/88.03, 379/265.12, 379/265.11, 379/265.01, 379/265.05, 379/265.09, 704/270.1
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3329 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 16/90332 Natural language query formulation or dialogue systems
• CPC Class Codes: G06F 40/216 using statistical methods
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/56 Natural language generation
• CPC Class Codes: G10L 15/22 Procedures used during a speech recognition process, e.g. man-machine dialogue
• CPC Class Codes: H04M 2203/355 Interactive dialogue design tools, features or methods
• CPC Class Codes: H04M 2203/357 Autocues for dialog assistance
• CPC Class Codes: H04M 3/42221 Conversation recording systems at the subscriber's set H04M1/656
• CPC Class Codes: H04M 3/5175 Call or contact centers supervision arrangements

Abstract

Agent utterances are generated for implementing dialog acts recommended by a dialog manager of a call center. To this end, a set of word lattices, each represented as a weighted finite state automaton (WFSA), is constructed from training dialogs between call center agents and second parties (e.g. customers). The word lattices are assigned conditional probabilities over dialog act type. For each dialog act received from the dialog manager, the word lattices are ranked by the conditional probabilities for the dialog act type. At least one word lattice is chosen from the ranking, and is instantiated to generate a recommended agent utterance for implementing the recommended dialog act. The word lattices may be constructed by clustering agent utterances of training dialogs using context features from preceding second party utterances and grammatical dependency link features between words within agent utterances. Path variations of the word lattices may define slots or paraphrases.

Claims

1. A call center device operating in conjunction with a telephonic or online chat communication station, the call center device comprising:

a dialog manager configured to determine a recommended agent dialog act based on past dialog between a call center agent and a second party which is received from the telephonic or online chat communication station; and

an utterance generation component configured to generate at least one recommended agent utterance for implementing the recommended dialog act by operations including;

ranking a set of word lattices each represented as a weighted finite state automaton (WFSA) by conditional probabilities p(τ

|DA type) where τ

is a word lattice and DA type is a dialog act type of the recommended dialog act,

choosing at least one word lattice from the ranking, and

instantiating the chosen at least one word lattice to generate the at least one recommended agent utterance;

wherein the dialog manager and the utterance generation component comprise at least one computer programmed to determine the recommended dialog act and to generate the at least one recommended agent utterance.

2. The call center device of claim 1 wherein the utterance generation component is configured to perform the instantiating by:

traversing the WFSA representing the chosen word lattice; and

substituting data provided to the utterance generation component by the dialog manager for any path variation of the WFSA that is identified as a slot.

3. The call center device of claim 1 wherein the utterance generation component is configured to perform the instantiating by:

traversing the WFSA representing the chosen word lattice; and

choosing one path of a path variation of the WFSA that is identified as a paraphrase based on weights of the paths of the paraphrase path variation.

4. The call center device of claim 1 further comprising:

a human-viewable display component configured to display the at least one utterance implementing the recommended dialog act.

5. The call center device of claim 1 wherein the telephonic or online chat communication station is an automated telephonic or online chat communication station and the call center device is configured to generate a single utterance implementing the recommended dialog act which is executed by a speech synthesizer or text messenger component of the automated telephonic or online chat communication station.

6. The call center device of claim 1 further comprising:

a training device comprising at least one computer configured to construct the set of word lattices from training dialogs between call center agents and second parties and to assign to the word lattices τ

the conditional probabilities p(τ

|DA type) over dialog act types DA type.

7. The call center device of claim 6 wherein the training device is configured to construct the set of word lattices by operations including:

extracting features to represent agent utterances of the training dialogs;

clustering the agent utterances of the training dialogs represented by the extracted features to form agent utterance clusters;

aligning the agent utterances of each cluster; and

generating a word lattice represented as a weighted finite state automaton (WFSA) encoding the aligned agent utterances of each cluster.

8. The call center device of claim 7 wherein the extracting includes extracting context features to represent agent utterances from second party utterances of the training dialogs.

9. The call center device of claim 8 wherein the extracting further includes extracting grammatical dependency link features characterizing grammatical dependencies between words within agent utterances.

10. The call center device of claim 7 wherein the aligning comprises applying multiple sequence alignment (MSA) with sequences comprising the agent utterances and each agent utterance comprising words.

11. The call center device of claim 7 wherein the generating of a word lattice includes determining weights of sub-sequences of the word lattice based on numbers of agent utterances merged to form the sub-sequences.

12. The call center device of claim 7 wherein:

the training device is configured to construct the set of word lattices by further operations including classifying each path variation in the word lattices as a slot, a paraphrase, or neither; and

during the instantiating of the chosen at least one word lattice, the utterance generation component is configured to substitute data provided by the dialog manager for any slot path variation and to choose one path of any paraphrase path variation based on weights of the paths of the paraphrase path variation.

13. The call center device of claim 6 wherein:

the training device is further configured to classify each path variation in the word lattices as a slot, a paraphrase, or neither; and

during the instantiating of the chosen at least one word lattice, the utterance generation component is configured to substitute data provided by the dialog manager for any slot path variation and to choose one path of any paraphrase path variation based on weights of the paths of the paraphrase path variation.

14. The call center device of claim 6 wherein the training device is configured to assign to the word lattices τ

the conditional probabilities p(τ

|DA type) by operations that for each word lattice τ

include;

sampling the word lattice τ

to generate sample utterances;

labeling each sample utterance with conditional probabilities p(DA type|utt) where utt is the sample utterance and DA type is a dialog act type; and

generating the conditional probabilities p(τ

|DA type) for the word lattice τ

from the conditional probabilities p(DA type|utt) of the sample utterances.

15. The call center device of claim 14 wherein the conditional probabilities p(τ

|DA type) for the word lattice τ

are generated from the conditional probabilities p(DA type|utt) of the sample utterances using Baye'"'"'s rule.

16. The call center device of claim 14 wherein the labeling comprises labeling each sample utterance with conditional probabilities p(DA type|utt) using a Natural Language Understanding component.

17. A non-transitory storage medium storing instructions readable and executable by one or more electronic data processing devices to perform a method for generating recommended agent utterances for implementing dialog acts recommended by a dialog manager of a call center, the method comprising:

constructing a set of word lattices each represented as a weighted finite state automaton (WFSA) from training dialogs between call center agents and second parties;

assigning to the word lattices conditional probabilities over dialog act type; and

for each recommended dialog act received from the dialog manager;

(i) ranking the set of word lattices by the conditional probabilities for the dialog act type of the recommended dialog act, (ii) choosing at least one word lattice from the ranking, and (iii) instantiating the chosen at least one word lattice to generate at least one recommended agent utterance for implementing the recommended dialog act.

18. The non-transitory storage medium of claim 17 wherein the constructing includes:

extracting features to represent agent utterances of the training dialogs including at least (I) context features extracted from preceding second party utterances in the training dialogs and (II) grammatical dependency link features characterizing grammatical dependencies between words within agent utterances;

clustering the agent utterances of the training dialogs represented by the extracted features to form agent utterance clusters;

aligning the agent utterances of each cluster; and

generating a word lattice represented as a weighted finite state automaton (WFSA) encoding the aligned agent utterances of each cluster with weights of sub-sequences of the word lattice being based on numbers of agent utterances merged to form the sub-sequences.

19. The non-transitory storage medium of claim 17 wherein:

the constructing includes classifying at least some path variations in the word lattices as slots or paraphrases; and

during the instantiating of the chosen at least one word lattice, substituting data provided by the dialog manager for any slot path variation and to choosing one path of any paraphrase path variation based on weights of the paths of the paraphrase path variation.

20. The non-transitory storage medium of claim 17 wherein assigning to the word lattices conditional probabilities over dialog act type includes for each word lattice:

sampling the word lattice to generate sample utterances;

labeling each sample utterance with conditional probabilities p(DA type|utt) where utt is the sample utterance and DA type is a dialog act type, the labeling being performed using a Natural Language Understanding component; and

generating the conditional probabilities over dialog act type for the word lattice from the conditional probabilities p(DA type|utt) of the sample utterances using Baye'"'"'s rule.