System and method of dialog trajectory analysis

• US 8,340,971 B1
• Filed: 01/05/2005
• Issued: 12/25/2012
• Est. Priority Date: 01/05/2005
• Status: Active Grant

• Current Assignee: Hyundai Motor Company (Hyundai Motor Group), Kia Corp.
• Original Assignee: AT&T Intellectual Property II LP (AT&T, Inc.)
• Inventors: Abella, Alicia, Wright, Jeremy Huntley
• Primary Examiner(s): Godbold, Douglas
• Application Number:
  US11/029,320
• Time in Patent Office: 2,911 Days
• Field of Search: 704/1, 704/9, 704/10, 704/270, 704/270.1, 379/265.01
• US Class Current: 704/270.1
• CPC Class Codes: G06F 40/00 Handling natural language data speech analysis or synthesis, speech recognition G10L
• CPC Class Codes: G10L 13/02 Methods for producing synthetic speech; Speech synthesisers
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding
• CPC Class Codes: G10L 2015/225 Feedback of the input speech
• CPC Class Codes: H04M 3/493 Interactive information services, e.g. directory enquiries ; Arrangements therefor, e.g. interactive voice response [IVR] systems or voice portals

Abstract

The invention comprises computer-readable media, methods and systems for performing a dialog analysis and using that analysis to release an updated spoken dialog system. The method embodiment of the invention comprises receiving data associated with dialogs, extracting turn by turn details of the dialog and generating from the extracted details an empirical call-flow representation of the dialog. The call data may be call-logs and user audio. The empirical call-flow representation may be a finite-state machine with nodes that represent call-states and the arcs between nodes represent user responses. Nodes may also represent sub-dialogs. The call-flow representation is presented graphically to a user for easier analysis and understanding. Significant changes in the dialog can be identified as hot-spots for improvement in the next release of the spoken dialog system.

Claims

1. A method of analyzing dialogs, the method comprising:

receiving, via a processor, call-logs associated with a plurality of dialogs between a dialog system and users and external information about at least one user;

extracting a first portion of turn-by-turn details of dialogs from the call-logs comprising at least a time stamp associated with a turn in the plurality of dialogs;

inferring a second portion of the turn-by-turn details unavailable in the call-logs based on the first portion of the turn-by-turn details using a call-flow specification as a guide, the second portion of the turn-by-turn details comprising an interleaved sequence of at least two attributes that characterize a system state and a user response; and

generating, from the first portion of the turn-by-turn details, the external information about the user, and the second portion of the turn-by-turn details, an empirical call-flow representation of the dialog.

2. The method of claim 1, further comprising identifying details of interactions between the dialog system and the person.

3. The method of claim 1, further comprising visually presenting the empirical call-flow.

4. The method of claim 3, wherein visually presenting the empirical call-flow further comprises presenting the call-flow on an interactive web-page.

5. The method of claim 3, wherein the visually presented empirical call-flow comprises dialog system actions as nodes and user responses as arcs between nodes.

6. The method of claim 1, wherein the data associated with the plurality of dialogs further comprises call audio.

7. The method of claim 1, wherein the plurality of dialogs is a human to human dialog.

8. The method of claim 1, wherein the plurality of dialogs is between a human and an automated dialog system.

9. The method of claim 1, wherein the empirical call-flow representation of the dialog is a stochastic finite-state machine.

10. The method of claim 1, wherein extracting the first portion of the turn-by-turn details of the plurality of dialogs further comprises partitioning the plurality of dialogs into two plurality of sub-dialogs.

11. The method of claim 10, wherein each at least one sub-dialog ends in one of the following ways:

proceed to next dialog, transfer to agent or another system, end call by system or hang-up by caller.

12. The method of claim 10, further comprising identifying a hot-spot associated with a particular sub-dialog.

13. The method of claim 12, wherein the empirical call-flow representation of the plurality of dialogs emphases the identified hot-spot.

14. The method of claim 10, further comprising:

detecting changes in dialog behavior at a sub-dialog terminal node; and

if changes are detected, searching among arcs associated with the call-flow representation of the dialog for an influence for the detected change.

15. The method of claim 1, further comprising:

compressing the empirical call-flow representation of the plurality of dialogs.

16. The method of claim 15, wherein compressing the empirical call-flow representation of the plurality of dialogs further comprises compressing sub-graphs within the empirical call-flow representation that contain no significant detected changes into a single arc between nodes.

17. A method of generating a visual representation of a plurality of dialogs, the method comprising:

identifying, via a processor, data associated with the plurality of dialogs between a dialog system and users and external information at least one user retrieved from a database, the data comprising call-logs for the plurality of dialogs identifying a first portion of turn-by-turn details of the plurality of dialogs;

appending a dialog outcome to the data, the dialog outcome received in a data feed of the call logs;

inferring a second portion of the turn-by-turn details of the plurality of dialogs unavailable from the call-logs based on the plurality of dialogs outcome using a call-flow specification as a guide, the second portion of the turn-by-turn details comprising an interleaved sequence of at least two attributes that characterize a system state and a user response; and

generating from the appended dialog outcome, identified data, the second portion of the turn-by-turn details, and the external information about the user, a dialog representation comprising nodes related to a dialog state and arcs related to user responses.

18. The method of claim 17, wherein identifying data further comprises either extracting directly from call-logs or inferring interleaved sequences of a plurality of chosen attributes that characterize a dialog system state and a user response.

19. The method of claim 17, wherein the outcome is one of:

transfer to agent, transfer to a spoken dialog system, system end-call, user hang-up without completion or service completion.

20. The method of claim 17, wherein the identified data and appended outcomes comprise a dialog trajectory.

21. The method of claim 20, wherein generating the dialog representation further comprises sorting, counting, and converting the dialog trajectory into a minimized stochastic finite state machine.

22. The method of claim 21, wherein outcomes are encoded in terminal nodes of the finite state machine.

23. The method of claim 17, further comprising presenting a visual representation of dialog representation.

24. The method of claim 23, wherein the visual representation is presented on a web-based display client.

25. A system for analyzing dialogs, the system comprising:

a processor;

means for controlling the processor to receive data associated with a plurality of dialogs between a dialog system and users and external information about at least one user retrieved from a database, the data comprising call-logs for the plurality of dialogs;

means for controlling the processor to extract a first portion of turn-by-turn details of the plurality of dialogs from a data feed of the call-logs comprising at least a time stamp associated with a turn in the plurality of dialogs;

means for controlling the processor to infer a second portion of the turn-by-turn details unavailable in the call-logs based on the first portion of the turn-by-turn details using a call-flow specification as a guide, the second portion of the turn-by-turn details comprising an interleaved sequence of at least two attributes that characterize a system state and a user response, the call-flow specification describing actions that should be performed based on user input; and

means for controlling the processor to generate from the first portion of the turn-by-turn details, the external information about the user, and the second portion of the turn-by-turn details an empirical call-flow representation of the plurality of dialogs.

26. The system of claim 25, further comprising means for controlling the processor to visually present the empirical call-flow representation.

27. A system for analyzing dialogs, the system comprising:

a processor;

a first module configured to control the processor to receive call-logs associated with a plurality of dialogs between a dialog system and users and external information about at least one user;

a second module configured to control the processor to extract a first portion of turn-by-turn details of dialogs from of the call-logs comprising at least a time stamp associated with a in the plurality of dialogs;

a third module configured to control the processing to infer a second portion of the turn-by-turn details unavailable in the call-logs based on the first portion of the turn-by-turn details using a call-flow specification as a guide, the second portion of the turn-by-turn details comprising an interleaved sequence of at least two attributes that characterize a system state and a user response; and

a fourth module configured to control the processor to generate, from the first portion of the turn-by-turn details, the external information about at least one user, and the second portion of the turn-by-turn details an empirical call-flow representation of the plurality of dialogs.

28. The system of claim 27, further comprising a fifth module configured to control the processor to visually present the empirical call-flow representation.

29. A non-transitory computer-readable medium storing instructions for controlling a computing device to analyze dialogs, the instructions comprising:

receiving call-logs associated with a plurality of dialogs between a dialog system and users and external information about at least one user;

extracting a first portion of turn-by-turn details of dialogs from the call-logs comprising at least a time stamp associated with a turn in the plurality of dialogs;

inferring a second portion of the turn-by-turn details unavailable in the call-logs based on the first portion of the turn-by-turn details using a call-flow specification as a guide, the second portion of the turn-by-turn details comprising an interleaved sequence of at least two attributes that characterize a system state and a user response; and

generating, from the first portion of the turn-by-turn details, the external information about the at least one user, and the second portion of the turn-by-turn details an empirical call-flow representation of the plurality of dialogs.

30. A non-transitory computer-readable medium storing instructions for controlling a computing device to analyze dialogs, the instructions comprising:

identifying data associated with a plurality of dialogs between a dialog system and users and external information about at least one user retrieved from a database;

appending a dialog outcome to the data, the dialog outcome received in a data feed of call logs;

inferring a second portion of the turn-by-turn details of the dialog unavailable from the call-logs based on the dialog outcome using a call-flow specification as a guide, the second portion of the turn-by-turn details comprising an interleaved sequence of at least two attributes that characterize a system state and a user response; and

generating from the dialog outcome, identified data, the second portion of the turn-by-turn details, and the external information about the user, a dialog representation comprising nodes related to a dialog state and arcs related to user responses.