Inferring Ranked Dialog Flows from Human-to-Human Conversations (2022)

Abstract: We present a novel technique to infer ranked dialog flows from human-to-human conversations that can be used as an initial conversation design or to analyze the complexities of the conversations in a call center. This technique aims to identify, for a given service, the most common sequences of questions and responses from the human agent. Multiple dialog flows for different ranges of top paths can be produced so they can be reviewed in rank order and be refined in successive iterations until additional flows have the desired level of detail. The system ingests historical conversations and efficiently condenses them into a weighted deterministic finite-state automaton, which is then used to export dialog flow designs that can be readily used by conversational agents. A proof-of-concept experiment was conducted with the MultiWoz data set, a sample output is presented and future directions are outlined.

## introduction virtual assistants are an attractive solution to customer service automation. while their language understanding capabilities and general knowledge of the world is limited in comparison with human agents, they can provide relatively simple services to an unlimited number of concurrent customers when coupled with cloud technologies. additionally, they ensure an homogeneous experience, according to their programming. it is common practice to program a virtual assistant to fall back to a human agent whenever it detects it cannot provide a service, combining the strengths of both human and machine. another usage of virtual assistants is to suggest to human agents a list of potential answers during a conversation with a customer, providing the agent potential useful information from previous interactions with the customer or from the customer profile, but letting the human decide the final answer. nowadays there exists a wide range of platforms for implementing virtual assistants, such as google dialogflow, foot_0 amazon lex, 2 microsoft bot framework, foot_2 and rasa. 4 however, implementing a virtual assistant or extending it to support new services is not a trivial task. for the case of new services, one has to imagine how the conversations for that given service will be, or run a wizard of oz experiment with potential customers to gather examples of conversations. once a conversational agent is deployed, it is often necessary to review its performance and adapt it to the actual conversations. for the case of services that are already being provided by human agents (e.g. in a call center), it is possible to review the conversation recordings in order to design a virtual assistant that will be better suited when first deployed. however, manually reviewing the call recordings can be time consuming. in this paper we propose a technique to extract the most common workflows or dialog flows human agents follow when providing a specific service, once the calls are segregated by service. 5 the types of agent questions and responses are first identified and labeled (e.g."where are you going?" → "destination request"), for which we use proprietary software. once the dialog utterances are replaced by the labels, hundreds of conversation paths can be condensed and ranked in seconds as a weighted finite-state automaton. different ranges of best paths in the automaton can then be exported as a succession of manageable-size dialog flows for their manual review (examples in the supplementary material). the conversational designer can then review them in rank order and decide when to stop, taking into account the added value of each successive dialog flow and the time available. 2 related work @xcite present graph2bots, a tool that also aims to assist conversational agent designers. similarly to us, they first identify types of utterances or dialog turns, which they call dialog phases. then they build a graph with all possible dialog phases as nodes, and all possible transitions between consecutive dialog phases in the dialogs. frequencies of dialog phases and transitions can then be used in order to filter out less frequent portions of the graph. we have also experimented with this kind of dialog phase graph and found several inconveniences we aim to overcome, namely 1. big convoluted graphs that, although they can be filtered, they are not partitioned so one can examine successive and manageable subsets of paths, one subset at a time, 2. the resulting graph represents concatenations of consecutive subsequences of 2 dialog phases from multiple dialogs, resulting in paths that do not actually exist in the dataset and produce confusion (figure 1 ), and 3. the overgeneration of paths results in loops (figure 2 ), which prevent the dialog flows from being loaded into conversational agent platforms as initial designs. @xcite propose an unsupervised approach to dialog structure inference based on a variational recurrent neural network with a structured attention layer that supports both 1 to 1 and multiparty conversations. however the reported times to train these models are in the order of hours, which in our use case would be impractical. @xcite and paul (2012) combine hidden markov models and topic modeling to model the dialog structures as conversation states with probabilities to shift to other states, where each state models the potential language or topics in that state. ## rationale this work builds on top of the output of a proprietary suite of tools for the analysis of call center conversations. this output comprises a set of dialog transcripts segregated by intent (e.g. booking a restaurant), where the utterances have been labeled by speaker role (agent/customer), classified into question/response/other, and then grouped into clusters of semantically equivalent questions/responses. 6 for each group of questions or responses, a canonical form of the question or response is provided to serve as the normalized version, analogous to the dialog phases in @xcite . our goals are: also, as additional requirements, 1. the paths in these dialog flows should come from actual dialogs and not be concatenations of subsequences from different dialogs (e.g. figures 1 and 2 ), in order to avoid confusion and loops, 2. the size of individual dialog flows (number of paths) should be limited by means of a parameter, and 3. the dialog flows should also include some examples of potential customer utterances that may appear before and after each agent question or response so that one can determine the triggers of specific questions and responses as well as potential customer responses. we do not intend to determine exact types of customer utterances but to provide a variety of examples since customer utterances tend to be more varied than agent utterances: whereas customers may request a service just a few times and may have no prior knowledge of the service protocols, agents deliver the same services multiple times to multiple customers and must adhere to established protocols and regulations. ## methodology overall, our proposed approach consists of 6 main steps: we build an nfa as depicted in figure 3 , with a linear sequence of states (nodes) and transitions (edges) for each dialog, where transitions are annotated with the normalized agent utterances and states with the customer utterance examples. note we only consider agent questions and responses, and other kinds of agent utterances are simply ignored (e.g. greetings). consecutive sequences of customer utterances between 2 agent utterances are simply concatenated and treated as a single utterance. consecutive sequences of agent utterances with no customer utterances in between result in a state that is annotated with no customer utterance (a state may have no customer utterance). formally, an nfa is defined as a 5-tuple (q, σ, δ, q i , f ) with • @xmath0, q 1 , . . . , q |q|-1 }, as a finite set of states, a path in the automaton is an alternation of states and input symbols q i , σ i , q i+1 , σ i+1 , . . . starting and ending with a state, where for every subsequence q j , σ j , q j +1 there is a transition δ(q j , σ) = q j+1 . we say an automaton recognizes, represents or accepts an input sequence σ i . . . σ i+n iff there exists at least one path from an initial state to a final state with the same sequence of input symbols. we say an automaton is not deterministic iff it contains at least 2 paths starting from an initial state and labeled with the same sequence of input symbols (multiple states can be reached by consuming the same input sequence). note having more than one initial state is sufficient for being non-deterministic. we define the partial map ζ c : @xmath1, if any. ## methodology extension an inconvenience of the method described above is that all the customer utterances that may start a conversation get grouped together in the dfa initial state (e.g. utterances a, e, and i of state s 0 in figure 5 ). we would like to split this group into potential utterances that may precede each first agent utterance, so that we can also determine what triggered each first agent utterance. this can be achieved by modifying the way in which the nfa is built, as illustrated in figure 11 : we simply duplicate the first transition of each individual dialog, leaving the new initial states with no customer utterances. upon minimization, the new first agent utterances will only allow for grouping the first customer utterances that are followed by the same agent utterance. upon exporting the dialog flows, these first agent utterances are simply to be ignored. 6 results we have tested this methodology with a sample of 492 restaurant booking dialogs from multiwoz @xcite . on a macbook pro (2018), it took 4.3 seconds to run the extended method from nfa building (4083 states and 3591 transitions) to dfa ranking and pruning (1704 states, 2176 transitions) for a big enough k so all paths (488) were ranked and kept. filtering the customer utterances took 36.8 additional seconds, though taking into account that this process included computing multilingual sentence embeddings @xcite for all the customer utterances, it could be considerably reduced by using a gpu. exporting a dialog flow of 50 paths into svg with graphviz (gansner and north, 2000) took 2.5 seconds. two flows are shown as supplementary material, and a wide range of flows has been provided as accompanying materials. ranking criterion is frequency aggregation so longer paths are produced. for simplicity, only the top rank of each transition is shown. the process factors out prefixes and suffixes of agent utterance sequences, which to some extent allows for identifying the most common full sequences. the flows exactly reflect what is found in the data, which is what we initially intended. ## conclusion and future work this paper presented a novel and efficient method for inferring ranked dialog flows from human-tohuman conversations in seconds. this method converts the dialogs into summarised and digestible artefacts, in the form of weighted finite-state automata with ranked transitions. the method is intended to be used together with a semi-supervised iterative process of identification of types of agent utterances, hence the quick generation of the ranked dialog flows is a must. future work includes 1) splitting the customer bubbles across the entire dialog flows to have separate groups of examples of customer utterances before each agent bubble, 2) to identify dialog substructures such as subsequences of agent questions and responses that may appear in any order, so they can be replaced by a subautomaton call and allow for further path collapsing, and 3) to allow for a controlled amount of overgeneration/noise in the automaton that maximizes the number of collapsed paths (adding missing subsequences that allow for further minimization).