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

• US 9,213,692 B2
• Filed: 03/21/2014
• Issued: 12/15/2015
• Est. Priority Date: 04/16/2004
• Status: Expired due to Fees

• Current Assignee: Nuance Communications, Inc. (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/221,435
• Publication Number:
  US 20140288921A1
• Time in Patent Office: 634 Days
• Field of Search: 717100-167
• 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:

inputting key data to a finite state-based representation, wherein the key data is extracted from a dialog call detail record associated with a run-time behavior of a dialog between a spoken dialog service and a user, wherein the dialog call detail record traces and records turns in the dialog during a call by the user; and

determining, via a processor and during the call, whether the finite state-based representation has accepted the key data based on whether the finite-based representation accepts a sentence from the dialog in a grammar, wherein the grammar is defined by a Backus-Naur Form implemented as the finite state-based representation.

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

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

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

5. The method of claim 4, wherein only an “

in class”

terminal element requires a matching class token.

6. The method of claim 1, further comprising when the finite state-based representation has accepted the key data, generating dialogs to automatically test the finite state-based representation.

7. The method of claim 6, further comprising performing further testing of the finite state-based representation using stored real-call records.

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

inputting key data to a finite state-based representation, wherein the key data is extracted from a dialog call detail record associated with a run-time behavior of a dialog between a spoken dialog service and a user, wherein the dialog call detail record traces and records turns in the dialog during a call by the user; and

determining, via the processor and during the call, whether the finite state-based representation has accepted the key data based on whether the finite-based representation accepts a sentence from the dialog in a grammar, wherein the grammar is defined by a Backus-Naur Form implemented as the finite state-based representation.

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

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

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

12. The system of claim 11, wherein only an “

in class”

terminal element requires a matching class token.

13. The system of claim 8, the computer-readable storage medium having additional instructions stored which result in operations comprising when the finite state-based representation has accepted the key data, generating dialogs to automatically test the finite state-based representation.

14. The system of claim 13, the computer-readable storage medium having additional instructions stored which result in operations comprising performing further testing of the finite state-based representation using stored real-call records.

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

inputting key data to a finite state-based representation, wherein the key data is extracted from a dialog call detail record associated with a run-time behavior of a dialog between a spoken dialog service and a user, wherein the dialog call detail record traces and records turns in the dialog during a call by the user; and

determining, via the computing device and during the call, whether the finite state-based representation has accepted the key data based on whether the finite-based representation accepts a sentence from the dialog in a grammar, wherein the grammar is defined by a Backus-Naur Form implemented as the finite state-based representation.

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

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

18. The computer-readable storage device of claim 15, wherein the Backus-Naur Form comprises a sequence of terminal elements and non-terminal elements.

19. The computer-readable storage device of claim 18, wherein only an “

in class”

terminal element requires a matching class token.

20. The computer-readable storage device of claim 15, the computer-readable storage medium having additional instructions stored which result in operations comprising when the finite state-based representation has accepted the key data, generating dialogs to automatically test the finite state-based representation.