Granted Patent B2

US 12,412,571 · App. 17/649,097 · Granted Sep 9, 2025

Inventors: Javier Miguel Sastre-Martinez (Dublin, IE); Aisling Nugent (Dublin, IE)

Assignee: Accenture Global Solutions Limited

G10L15/193G06N20/00G10L15/22G06F40/279G10L15/1822G10L2015/223

Abstract

Claims (69)

1. A method, comprising:

receiving, by a device, non-deterministic finite state automata (NFSA) to represent a set of dialog flows associated with a human-machine interface,

wherein each dialog flow is represented in the NFSA as a set of non-overlapping paths, wherein states in the NFSA are annotated with one or more user utterances, and wherein transitions in the NFSA are annotated with an agent utterance type;

generating, by the device, a deterministic finite state automaton (DFSA) that includes a minimum set of states that represents all dialog flows included in the set of dialog flows represented in the NFSA and does not represent dialog flows that are not included in the set of dialog flows represented in the NFSA;

assigning, by the device, a weight to each transition in the DFSA;

traversing, by the device, the DFSA to identify a set of K paths that have highest total weight based on the weight assigned to each transition in the DFSA;

pruning, by the device, the DFSA to remove any states and any transitions that do not belong to the set of K paths that have the highest total weight;

generating, by the device, an output that includes information related to one or more subsets of the set of K paths that have the highest total weight; and

providing, by the device, the output to an automated conversational flow system, wherein the automated conversational flow system configures a virtual agent associated with the human-machine interface to enable interaction between a user and the virtual agent.

2. The method of claim 1 , wherein generating the DFSA includes:

collapsing, from an end of the NFSA to a beginning of the NFSA, one or more states in the NFSA that are reachable by a common input symbol; and

collapsing, from the beginning of the NFSA to the end of the NFSA, one or more states in the NFSA that are reachable by a common input symbol.

3. The method of claim 1 , wherein the weight assigned to each transition in the DFSA is based on a frequency that is based on a quantity of times that an equivalent transition is represented in the set of dialog flows represented by the NFSA.

4. The method of claim 1 , wherein the weight assigned to each transition in the DFSA is based on a probability that is based on a frequency associated with the transition relative to a total quantity of outgoing transitions from a source state associated with the respective transition.

5. The method of claim 1 , wherein traversing the DFSA to identify the set of K paths that have the highest total weight includes:

adding a temporary final state to the DFSA, wherein each transition to the temporary final state has a null weight; and

traversing the DFSA by following a topological sort, in a forward direction from an initial state of the DFSA to the temporary final state,

wherein traversing the DFSA includes associating each respective state in the DFSA with Kor fewer highest cumulative weights based on the weight assigned to each respective transition that is included in up to K paths that led to the respective state.

6. The method of claim 5 , wherein pruning the DFSA includes:

assigning, at the temporary final state, respective ranks to each path in the set of K paths that have the highest total weight; and

traversing the DFSA by following a reverse of the topological sort, in a backward direction from the temporary final state to the initial state of the DFSA, to propagate the respective ranks to the transitions that are included in the set of K paths,

wherein the states and the transitions that are removed from the DFSA include states and transitions that are not associated with one or more of the respective ranks associated with the set of K paths that have the highest total weight; and

removing the temporary final state from the DFSA.

7. The method of claim 1 , wherein the output includes a visualization or a data export of the information related to the one or more subsets of the set of K paths having the highest total weight.

8. The method of claim 1 , wherein an initial state in the DFSA includes one or more outgoing transitions to one or more states that correspond to user utterances starting a dialog.

9. The method of claim 1 , further comprising:

determining, for each state in the minimized set of states included in the DFSA, N user utterances that best represent the respective state using a clustering technique; and

associating each state in the minimized set of states included in the DFSA with the N user utterances that best represent the respective state.

10. A dialog modeling system, comprising:

one or more memories; and

one or more processors, coupled to the one or more memories, configured to:

receive non-deterministic finite state automata (NFSA) to represent a set of dialog flows associated with a human-machine interface,

wherein each dialog flow is represented in the NFSA as a set of non overlapping paths, wherein states in the NFSA are annotated with one or more user utterances, and wherein transitions in the NFSA are annotated with an agent utterance type;

generate a deterministic finite state automaton (DFSA) that includes a minimum set of states that represents all dialog flows included in the set of dialog flows represented in the NFSA and does not represent dialog flows that are not included in the set of dialog flows represented in the NFSA;

assign a weight to each transition in the DFSA;

traverse the DFSA to identify a set of K paths that have a highest total weight based on a weight assigned to each transition in the DFSA;

prune the DFSA to remove any states and any transitions that do not belong to the set of K paths that have the highest total weight;

generate an output that includes information related to one or more subsets of the set of K paths that have the highest total weight; and

provide the output to an automated conversational flow system, wherein the automated conversational flow system configures a virtual agent associated with the human-machine interface to enable interaction between a user and the virtual agent.

11. The dialog modeling system of claim 10 , wherein the one or more processors, to generate the DFSA, are configured to:

collapse, from an end of the NFSA to a beginning of the NFSA, one or more states in the NFSA that are reachable by a common input symbol; and

collapse, from the beginning of the NFSA to the end of the NFSA, one or more states in the NFSA that are reachable by a common input symbol.

12. The dialog modeling system of claim 10 , wherein the weight assigned to each transition in the DFSA is based on one or more of a frequency, a probability, or a rank.

13. The dialog modeling system of claim 10 , wherein the one or more processors, to traverse the DFSA to identify the set of K paths that have the highest total weight, are configured to:

add a temporary final state to the DFSA, wherein each transition to the temporary final state has a null weight;

traverse the DFSA by following a topological sort, in a forward direction from an initial state of the DFSA to the temporary final state,

wherein the one or more processors, to traverse the DFSA, are configured to associate each respective state in the DFSA with Kor fewer highest cumulative weights based on the weight assigned to each respective transition that is included in up to K paths that led to the respective state;

assign, at the temporary final state, respective ranks to each path in the set of K paths that have the highest total weight; and

traverse the DFSA by following a reverse of the topological sort, in a backward direction from the temporary final state to the initial state of the DFSA, to propagate the respective ranks to the transitions that are included in the set of K paths,

wherein the states and the transitions that are removed from the DFSA include states and transitions that are not associated with one or more of the respective ranks associated with the set of K paths that have the highest total weight; and

remove the temporary final state from the DFSA.

14. The dialog modeling system of claim 10 , wherein an initial state in the DFSA includes one or more outgoing transitions to one or more states that correspond to user utterances starting a dialog.

15. The dialog modeling system of claim 10 , wherein the one or more processors are further configured to:

determine, for each state in the minimized set of states included in the DFSA, N user utterances that best represent the respective state using a clustering technique; and

associate each state in the minimized set of states included in the DFSA with the N user utterances that best represent the respective state.

16. A non-transitory computer-readable medium storing a set of instructions, the set of instructions comprising:

one or more instructions that, when executed by one or more processors of a dialog modeling system, cause the dialog modeling system to:

receive non-deterministic finite state automata (NFSA) to represent a set of dialog flows associated with a human-machine interface,

wherein each dialog flow is represented in the NFSA as a set of non overlapping paths, wherein states in the NFSA are annotated with one or more user utterances, and wherein transitions in the NFSA are annotated with an agent utterance type;

generate a deterministic finite state automaton (DFSA) that includes a minimum set of states that represents all dialog flows included in the set of dialog flows represented in the NFSA and does not represent dialog flows that are not included in the set of dialog flows represented in the NFSA;

assign a weight to each transition in the DFSA;

traverse the DFSA to identify a set of K paths that have a highest total weight based on a weight assigned to each transition in the DFSA;

prune the DFSA to remove any states and any transitions that do not belong to the set of K paths that have the highest total weight;

generate an output that includes information related to one or more subsets of the set of K paths that have the highest total weight; and

provide the output to an automated conversational flow system, wherein the automated conversational flow system configures a virtual agent associated with the human-machine interface to enable interaction between a user and the virtual agent.

17. The non-transitory computer-readable medium of claim 16 , wherein the weight assigned to each transition in the DFSA is based on a frequency that is based on a quantity of times that an equivalent transition is represented in the set of dialog flows represented by the NFSA.

18. The non-transitory computer-readable medium of claim 16 , wherein the weight assigned to each transition in the DFSA is based on a probability that is based on a frequency associated with the transition relative to a total quantity of outgoing transitions from a source state associated with the respective transition.

19. The non-transitory computer-readable medium of claim 16 , wherein the output includes a visualization or a data export of the information related to the one or more subsets of the set of K paths having the highest total weight.

20. The non-transitory computer-readable medium of claim 16 , wherein an initial state in the DFSA includes one or more outgoing transitions to one or more states that correspond to user utterances starting a dialog.

Assignments (1)

Continuity (1)

References Cited (28)