System and method for the automatic validation of dialog run time systems

• US 9,584,662 B2
• Filed: 11/24/2015
• Issued: 02/28/2017
• Est. Priority Date: 04/16/2004
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Castillo, Cecilia, Roycraft, Theodore J., Wilson, James M.
• Primary Examiner(s): Neway, Samuel G
• Application Number:
  US14/950,062
• Publication Number:
  US 20160080571A1
• Time in Patent Office: 462 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 40/211 Syntactic parsing, e.g. based on context-free grammar [CFG] or unification grammars
• CPC Class Codes: G06F 40/289 Phrasal analysis, e.g. finite state techniques or chunking
• CPC Class Codes: G06F 40/40 Processing or translation of natural language natural language analysis G06F40/20; semantic analysis G06F40/30
• CPC Class Codes: G06F 9/44 Arrangements for executing specific programs
• CPC Class Codes: G06F 9/4498 Finite state machines
• CPC Class Codes: G10L 15/1822 Parsing for meaning understanding
• CPC Class Codes: G10L 15/193 Formal grammars, e.g. finite state automata, context free grammars or word networks
• CPC Class Codes: H04M 2201/18 Comparators
• CPC Class Codes: H04M 3/22 Arrangements for supervision, monitoring or testing
• CPC Class Codes: H04M 3/2218 Call detail recording
• CPC Class Codes: H04M 3/24 with provision for checking the normal operation
• CPC Class Codes: H04M 3/4936 Speech interaction details speech recognition per se G10L15/00
• CPC Class Codes: H04M 3/5175 Call or contact centers supervision arrangements

Abstract

A method, system and module for automatically validating dialogs associated with a spoken dialog service. The method comprises extracting key data from a dialog call detail record associated with a spoken dialog service, transmitting the key data as a dialog to a state-based representation (such as a finite-state machine) associated with a call-flow for the spoken dialog service and determining whether the dialog associated with the key data is a valid dialog for the call-flow.

Claims

1. A method comprising:

converting, via a processor, a call flow into a context free grammar notation;

converting the context free grammar notation into a finite state machine;

generating test dialogs associated with the call flow according to paths through the finite state machine;

extracting key data from a dialog call detail record from a dialog in the test dialogs;

transmitting, to the finite state machine, the key data; and

determining, based on the key data being accepted by the finite state machine, that the dialog is a valid dialog for the call flow.

2. The method of claim 1, wherein the dialog call detail record comprises a prompt issued to a user and a response from the user.

3. The method of claim 2, wherein the dialog call detail record further comprises an interpretation of the response.

4. The method of claim 1, wherein state-based representation comprises a Backus-Naur Form.

5. The method of claim 4, wherein the Backus-Naur Form comprises a sequence of terminal elements and non-terminal elements.

6. The method of claim 5, wherein an in class terminal element of the sequence of terminal elements requires a matching class token.

7. The method of claim 1, further comprising testing the finite state machine prior to the generating of the test dialogs associated with the call flow.

8. The method of claim 7, wherein the testing of the finite state machine is performed using stored real-call records.

9. 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;

converting a call flow into a context free grammar notation;

converting the context free grammar notation into a finite state machine;

generating test dialogs associated with the call flow according to paths through the finite state machine;

extracting key data from a dialog call detail record from a dialog in the test dialogs;

transmitting, to the finite state machine, the key data; and

determining, based on the key data being accepted by the finite state machine, that the dialog is a valid dialog for the call flow.

10. The system of claim 9, wherein the dialog call detail record comprises a prompt issued to a user and a response from the user.

11. The system of claim 10, wherein the dialog call detail record further comprises an interpretation of the response.

12. The system of claim 9, wherein state-based representation comprises a Backus-Naur Form.

13. The system of claim 12, wherein the Backus-Naur Form comprises a sequence of terminal elements and non-terminal elements.

14. The system of claim 13, wherein an in class terminal element of the sequence of terminal elements requires a matching class token.

15. The system of claim 9, the computer-readable storage medium having additional instructions stored which, when executed by the processor, cause the processor to perform operations comprising:

testing the finite state machine prior to the generating of the test dialogs associated with the call flow.

16. The system of claim 15, wherein the testing of the finite state machine is performed using stored real-call records.

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

converting a call flow into a context free grammar notation;

converting the context free grammar notation into a finite state machine;

generating test dialogs associated with the call flow according to paths through the finite state machine;

extracting key data from a dialog call detail record from a dialog in the test dialogs;

transmitting, to the finite state machine, the key data; and

determining, based on the key data being accepted by the finite state machine, that the dialog is a valid dialog for the call flow.

18. The computer-readable storage device of claim 17, wherein the dialog call detail record comprises a prompt issued to a user and a response from the user.

19. The computer-readable storage device of claim 18, wherein the dialog call detail record further comprises an interpretation of the response.

20. The computer-readable storage device of claim 17, wherein state-based representation comprises a Backus-Naur Form.