{'fraction_non_alphanumeric': 0.033315930300854925, 'fraction_numerical': 0.01174704692292632, 'mean_word_length': 4.688010393466963, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
State-Machine-Based Dialogue Agents with Few-Shot Contextual Semantic Parsers

This paper presents a methodology and toolkit for creating a rule-based multi-domain conversational agent for transactions from (1) language annotations of the domains’ database schemas and APIs and (2) a couple of hundreds of annotated human dialogues. There is no need for a large annotated training set, which is expensive to acquire. The toolkit uses a pre-defined abstract dialogue state machine to synthesize millions of dialogues based on the domains’ information. The annotated and synthesized data are used to train a contextual semantic parser that interprets the user’s latest utterance in the context of a formal representation of the conversation up to that point. Developers can refine the state machine to achieve higher accuracy. On the MultiWOZ benchmark, we achieve over 71% turn-by-turn slot accuracy on a cleaned, reannotated test set, without using any of the original training data. Our state machine can model 96% of the human agent turns. Our training strategy improves by 9% over a baseline that uses the same amount of hand-labeled data, showing the benefit of synthesizing data using the state machine.


Introduction
Virtual assistants and task-oriented dialogue agents are transforming how consumers interact with computers. This has led to active research on using Wizard-of-Oz dialogues to train dialogue state tracking networks (Ren et al., 2019;Zhou and Small, 2019;Zhang et al., 2019b;Chen et al., 2020;Heck et al., 2020), and even full neural networks that track dialogue states, implement dialogue policies and generate agent utterances (Williams and Zweig, 2016;Eric and Manning, 2017;Zhang et al., 2019b;Peng et al., 2020;Hosseini-Asl et al., 2020). Meanwhile, commercial dialogue agents are typically built using dialogue trees, where each node of the tree represents an agent utterance and a small set of intents capturing the anticipated user responses (Gao et al., 2018).
Wizard-of-Oz conversations (Kelley, 1984) have traditionally been used to study dialogue state tracking. We realize that they can be put to use to create effective rule-based agents and their language understanding models. We have developed a toolkit, called CoDA (Contextual Dialogue Agent), that can create multi-domain rule-based agents, along with a semantic parsing model for NLU, from just a couple of hundreds of annotated human dialogues. We eliminate the need of collecting and annotating thousands of dialogues for training.
Modeled as a rule-based state machine, the agent has an explicit dialogue policy that is under the control of the developer. State machines are more interpretable than a data-driven system, and decision procedures, such as recommender systems, can be plugged in to maximize business objectives. A rulebased agent is also safer, especially in applications where the agent can cause irrevocable side effects, or perform dangerous or destructive actions.
Our first goal is to create a rule-based agent that mimics the human agent in the given dialogues. We create the first iteration of the agent's state machine by instantiating it from a pre-defined abstract model with information on its domain. This information includes the domain's database schemas and APIs and a few annotations on how the attributes and parameters are referred to in natural language. Currently, our abstract model is defined for performing transactions on multiple domains. Each state transition, represented as a rule, takes a formal representation summarizing the current state of the conversation (the result state), and returns the agent state as well as a possible user response, captured formally as an user state.
Our second goal is to create an accurate semantic parser to understand the user's input. Our semantic parser is contextual in that it is fed the current dialogue state and the agent state and only the latest utterance of the user, and produces the new state of the dialogue. Parsing only the latest user utterance is a significantly easier task than parsing the whole history of the conversation, which leads to higher accuracy in practice. Unlike methods based on dialogue trees, our neural model generalizes the state machine to understand utterances beyond it.
Using the state machine, CoDA automatically synthesizes millions of dialogues for the domain, which are used to train the contextual parser. The supplied annotated dialogues are used partly to finetune the model and partly as validation and test data. As the developer annotates the validation set and analyzes the parsing errors, the developer can refine the state machine and improve the synthesized dialogues. This helps the agent match the human agent, and allows the neural model to understand more user sentences.

Contributions
The contributions of our paper are as follows: 4. Our approach can understand the user utterances on the MultiWOZ test set with 58% accuracy, and can identify the correct slots for 71% of the turns, even though it is trained with data equivalent to less than 2% of the Mul-tiWOZ training set (combined with a large amount of synthesized data).

Background & Related Work
Dialogue State Tracking Dialogue State Tracking is the task of predicting a formal representation of the conversation at any point, usually in the form of slots and values. Since the release of the MultiWOZ dataset, a number of models have been proposed for this task, based either on question-answering (Gao et al., 2019), a pointergenerator (Wu et al., 2019), matching to a finite ontology (Lee et al., 2019a), or some combination of the latter two (Zhang et al., 2019a). All these models encode the full history of the dialogue. Previous work has already proposed including the current dialogue state as auxiliary input to the DST network (Mrkšić et al., 2017;Lei et al., 2018;Heck et al., 2020). Yet, these methods must parse at least the current agent turn, because they lack the fine-grained annotations of the agent utterances that are necessary to disambiguate the user's input. Our methodology can produce the annotated training set so that understanding agent utterances is unnecessary, simplifying the task and yielding higher accuracy in practice.
A different line of work previously proposed parsing utterances individually to identify the dialogue act and slots, and using a rule-based state tracker to compute the current state Zhong et al., 2018). Such models do not recompute the full user state at every turn, so they cannot handle state changes outside of the state machine defined ahead of time. Results on MultiWOZ show these methods do not achieve state-of-the-art accuracy.
Data Acquisition for DST In the recent years, a number of very large DST datasets have been released (Budzianowski et al., 2018;Byrne et al., 2019;Rastogi et al., 2019;Lee et al., 2019b). The preferred technique to acquire such datasets is through Wizard-Of-Oz (Kelley, 1984), a technique in which two humans are instructed to converse with each other, with one person taking the role of the agent. Acquiring datasets through WOZ is expensive, and the annotation quality is poor; the MultiWOZ dataset, despite reannotation (Eric et al., 2019), still suffers from inconsistency (Zhou and Small, 2019). A different technique is paraphrasing, which synthesizes a large corpus of datasets using a fixed grammar; a fraction of the datasets are then paraphrased by crowdworkers. Originally proposed for semantic parsing (Wang et al., 2015), paraphrasing has been applied to dialogues (Shah et al., 2018;Rastogi et al., 2019). Yet, crowdsourced paraphrases are also expensive. Furthermore, previous work suggests there can be a gap between performance on paraphrases and performance on real data (Campagna et al., 2019). Our approach based on synthesis and few-shot training has a significant cost advantage, while preserving the variety of WOZ dialogues and having annotations that are correct by construction.
Zero-and Few-Shot DST Zero-and few-shot transfer learning for MultiWOZ were proposed by Wu et al. (2019) as a way to generalize to new domains.  found that, by using data synthesized from a small finite state machine, it is possible to apply traditional dialogue state trackers in a zero-shot setting (training on four domains and testing on the fifth). Yet, they could not match the accuracy of training with the full dataset. Our approach extends their idea of synthesized data, but by modifying the representation and focusing only on understanding the user, achieves accuracy comparable to results on the full dataset.
Concurrent to this work, Peng et al. (2020) found that it is possible to build an agent using a few-shot learning regime by pretraining on many dialogue datasets at once. They do not evaluate their DST performance, and only report agent policy performance in the end-to-end setting. Our goal instead is to build a safer and more interpretable rule-based policy. Hence, we focus exclusively on the DST task. Note that if the interpretation is correct, our agent is guaranteed to provide a correct response.

State-Machine-Driven Dialogue Agents
Our tool accepts a state machine, described as a list of states, and a small number of rules describing how states are connected, with possible utterances for the agent and possible follow ups from the user. Our toolkit uses the state machine to synthesize a large training set, which is used to train a con- textual semantic parser. The parser takes as input the current state of the conversation and the user's latest utterance and produces the new state.

Overview
At each turn, the agent keeps track of: • a user state, a formal representation of the last utterance from the user, in terms of queries to a database and API calls; • a result state, which captures the database queries and API calls that were previously issued as well as their result; • an agent state, a formal representation of the sentence to be uttered by the agent.

Execution-Time Dialogue Loop
Consider the example of the first user utterance in a dialogue shown in Fig. 1. The user request for an Indian restaurant is fed into the contextual semantic parser, called CTXNLU; the context is the current agent state and result state, both of which are empty in the first turn. Here the request is translated into the user state, "Exec: Restaurant(food="Indian")", which is a database query for a restaurant filtering on the slot food with value "Indian". Next the command is added to the result state and executed; in this case, the matched Indian restaurants are also added to the result state. Because there are multiple results, the agent's rule-based system decides to ask the user to refine the search with a question on the choice of area, as captured by the agent state: "SearchQuestion: area". A grammar-based algorithm converts that state into the sentence "Do you have a specific part of town in mind?". This finishes one turn of the dialogue. The agent and result states are then fed back to the CTXNLU as context for the next user utterance.

State Representation
User State Representation There is one common abstract state machine that can be used for all domains. Each user utterance can be classed as one of the following abstract states: "Greet", "Exec", "AskRecommend", "Insist", "Cancel", and "End". As the conversation starts, the user typically greets the agent, then queries data or requests actions such as making a reservation, perhaps asks for recommendations, reiterates some request, and then cancels or ends the conversation. As shown above, a user state is an abstract state name (e.g. Exec), followed by the executable commands, either queries or actions. Executable commands contain the domain-specific slot-value pairs (e.g. Restaurant(food="Indian")). The user state also includes the slots that the user is requesting; for example, the utterance "What food does Curry Prince serve?" would be represented as: Exec: food of Restaurant(name="Curry Prince"); Including the requested slot is necessary for the agent to respond appropriately. Note that the abstract state name depends on the specific state machine in use. Unlike methods based on annotating dialogue acts (Bunt, 2006;Budzianowski et al., 2018), it is not possible to decide the set of abstract states before the state machine is built.
We separate the database query part and the action (booking) into different executable commands. The neural model predicts only the commands that are mentioned in the current turn; those commands update the previous ones in the result state from the same domain. We observe that in MultiWOZ typically the user first chooses an item (hotel, restaurant, train) and then performs an action. Hence, in most cases the neural model is only predicting either the query or the action. This reduces the amount of information the model has to predict at a given turn, and reduces error. When it is necessary for a particular utterance, we also train the model to predict both query and action at the same time.
Our design is based on executable semantics for the query and action. The design provides an unambiguous specification of when a slot should be predicted. It excludes from the user state the slots that were only provided or proposed by the agent. It also allows the user to remove slots that are no longer relevant. This avoids a large class of errors in the MultiWOZ dataset, as the convention of when to include slots in the annotation was ambiguous and not followed consistently.

Agent State Representation
There are 15 abstract states for the agent: Greet, SearchQuestion, RecommendOne, ProposeRefinedQuery, Action-Success, etc. The agent state can also include an executable command that is proposed by the agent to the user. For example, the agent utterance "Curry Prince serves Indian food. Would you like me to book it?" would have agent state: RecommendOne: propose action Restaurant.MakeReservation(name="Curry Prince"); Capturing what is offered by the agent is necessary to understand what the user means if they accept the offer with a short phrase such as "yes". While previous work already proposed tracking both requested and provided slots (Lei et al., 2018;, and standard annotation schemes track slots informed by the agent (Budzianowski et al., 2018), our state representation is the first to separately track slots proposed by the agent as query refinement.

Creating the Dialogue State Machine
The state machine is represented by a set of state transition rules. Each rule is a pair of grammarbased templates, one for the agent turn and one for an expected follow-up user turn. An example of a rule is shown in Fig. 2. The templates are rule: RECOMMEND <sep> ACCEPT RECOMMEND := "How about" NAME "? It" VB SLOT ACCEPT := "Sure, I like that, can I" ACTION ACTION := "book it" VB SLOT := "serves" FOOD NAME := "Curry Garden" | "Rajmahal" | . . . FOOD := "Indian" | "Italian" | . . . Figure 2: Example of a state transition rule. The rule consists of two templates, one for the agent and one for the user, separated by "<sep>". The ACTION and VB SLOTS templates are provided by the developer as annotations for the API and database columns, and the NAME and FOOD templates are automatically generated from the database.
associated with semantic functions that accept the current result state and return the appropriate agent and user state. Our abstract state machine includes 29 rules, which is comparable in size to the state machine proposed by . A developer building an agent can instantiate the state machine in a new domain by supplying the database schema, action APIs, and a small number of annotations on each field (Xu et al., 2020). This immediately yields an agent that behaves similarly as the human agents in the MultiWOZ benchmark.
Furthermore, a developer can refine the state machine by studying human conversations. They can add abstract states, rules in the state machine, as well as templates to generate more natural utterances. This allows incremental refinement to improve the model performance.

Generating the Agent and Training Data
The same state machine is used both to provide the agent behavior at run time, and to synthesize data for training. The agent templates are used both at training and execution time to provide the agent responses, while the user templates are only used to synthesize training data. At training time, all possible transitions are synthesized, so that we can model the human behavior on the validation set; at execution time the developer specifies which of the possible actions the agent should take. The system automatically computes the new result state given the previous result state and the user state. It uses simulation during training data synthesis, and it calls the underlying API at execution time.
We use the algorithm developed by  to synthesize the dialogues to use in training. The algorithm keeps a working set with a fixed number of dialogues, and samples among the

Contextual Semantic Parsing Model
Our CTXNLU neural model is based on the BERT-LSTM model introduced by Xu et al. (2020), which we adapt to encode the formal states. Fig. 3 shows the overall architecture of CTXNLU. The model is an encoder-decoder (Sutskever et al., 2014) neural network that uses the pretrained BERT (Devlin et al., 2018) as the encoder, and uses an LSTM (Hochreiter and Schmidhuber, 1997) decoder.
We feed to the encoder a concatenation of Result State, Agent State, and User Utterance. Including User Utterance and formal states in the same encoder is beneficial since several layers of selfattention present in the Transformer network of BERT can capture dependencies between what the user is saying (e.g. "it") and the context (e.g. the first restaurant in Result State). On the decoder side, the LSTM state is initialized with the average of the encoder's last layer. At each time step, we use a pointer-generator module (See et al., 2017) to produce the next token of the user state in an autoregressive fashion. The model is trained with token-level cross-entropy loss and teacher forcing.

Few-Shot Training
Our technique employs few-shot training to maximize the effectiveness of synthesized data, with small amounts of manually annotated data. We use the synthesized dataset to train the model initially. The model with the highest validation accuracy is then fine-tuned on the few-shot training set. Details of the training strategy are in the supplementary material.

Preprocessing
We apply the same preprocessing used by TRADE (Wu et al., 2019) to the input utterances. We also use a rule-based preprocessor to identify time expressions, and replace them with placeholder tokens. All slot values in the result and agent states that have string or time type are replaced with a placeholder when input to the network.
We normalize all slot values to match the database, regardless of typos, with the exception of entity names (hotel, restaurant and attraction names in MultiWOZ), which are normalized to match the utterance. This allows us to understand open-world entities using the copying mechanism, while still using the neural model to normalize enumerated slots (such as "area" and "price" in MultiWOZ). When comparing the slot values for equality, we normalize entity names via a database lookup.

Evaluation
In this section, we evaluate our technique's effectiveness at building an agent for the MultiWOZ benchmark (Budzianowski et al., 2018). We evaluate 4 research questions: (1) How well can our state machine match the human agent behavior?
(2) How well can we learn to interpret the user sentences with our model? (3) How does our approach compare to the state of the art? (4) What aspects of our approach are the most effective?

Experimental setting
We conduct our experiments using the MultiWOZ dataset (Budzianowski et al., 2018). This dataset includes dialogues across five domains -Attraction, Hotel, Restaurant, Taxi and Train -as well as dialogues spanning multiple domains. To conduct our experiments, we reannotated the validation and test set to include the additional dialogue state annotations. Reannotation was performed by the authors of the paper. For reasons of cost, we only reannotated about 36% of the validation set, and discarded the rest. When considering only the slots, about 83% of all turns in the test sets changed in our reannotation; this is due to mistakes in annotation, inconsistent normalization of names, and inconsistent annotation of slots offered by the agent. Note that MultiWOZ has already been fully reannotated once (Eric et al., 2019), but others have already found problems in the 2.1 version (Zhou and Small, 2019). We also dropped 1% of turns from the test set due to unrecoverable human errors, such as the  user acting as the agent, the agent talking about an entity that is not in the database, or the agent booking a completely wrong restaurant or hotel. For training, we use our dialogue model to synthesize a large, initial training set containing 1,477,079 dialogues across all five domains. We then further split the original validation set and take 168 dialogues as few shot training, while leaving the remaining ones as validation; the few-shot set is equivalent in size to less than 2% of the original training set. We do not use the original training set. The details of our final datasets are shown in Table 1. All new data will be released upon publication.
Our system uses the Genie Toolkit for data synthesis (Campagna et al., 2019) and the Huggingface Transformers library for the model (Wolf et al., 2019). Details of our generation and hyperparameters are included in the supplementary material. All our code will be released open-source.

Evaluation Of Agent State Machine
Our overall goal is to build an agent that is able to mimic the MultiWOZ human agents. In our first experiment, we evaluate how well our state machine covers the actions taken by human agents. Our state machine can fail to model the human agent in three ways: 1. Transitions that we explicitly exclude. For example, the human agent might decide to book a restaurant without telling the user in advance which restaurant they will book. We explicitly disallow this behavior, as we do not want the agent to take actions without confirmation.
2. Transitions that are not yet captured in our state machines. These use agent states representable in our formal language, but have no rules that can generate them. An example is asking the user whether they would like to hear a certain piece of information. The state  is representable as proposing a new query, but it is not generated by our state machine.
3. States that are not representable in our state machine. These are agent turns that need an extension of the formal language. An example of this error is when the user issues a request for multiple domains in a single turn, and the agent responds to both at once.
To identify these errors, we analyze the human agent on the validation set. We use the validation set because the analysis informs the design of the state machine. We exclude all turns where the human agent made a mistake. We find that 95.6% of the agent turns are covered by our state machine. Of the remaining 4.4%, 1.6% of turns are state transitions that we explicitly exclude from our model, while 1.2% could be captured by our dialogue model in the future. Finally, 1.5% of the agent states are not yet representable. Overall, this result shows that our model, despite having only 6 user states, 15 agent states and 29 transitions, captures the human agent's behavior very well. Furthermore, by annotating a small amount of validation data, it is possible to identify and add new states and state transitions.

Understanding User Utterances
Our next experiment measures how well our CTXNLU model understands user utterances. We assume that the agent will confirm what it hears from the user, and if there is an error, it will be corrected, to avoid accumulation of errors as the dialogue continues. We thus propose the Turn-By-Turn Accuracy metric: given that the formal state correctly captures the state up to that point of the dialogue, what is the accuracy of understanding the user's next utterance? We report both Exact Match, which indicates all elements of the predicted user state are correct, and Slots Only, which indicates all the user-provided slots are correct.
Our results are reported in Table 2. On the test set, our model achieves a 57.8% turn-by-turn exact match accuracy, and predicts the correct slots for 71.1% of the turns. The validation accuracy is higher because we used the validation set to refine our state machine; yet, we achieve good performance on the test set too. This is a promising result that shows that the model can learn the user's language well enough to bootstrap the agent.

Evaluation Of User State Machine
Our state machine includes an approximation of the user's behavior, and we expect that the neural model will generalize to new state transitions. To understand how often our model needs to generalize, and the accuracy when generalizing, we break down the error based on whether each turn was representable in the state machine.
We perform this analysis on the validation set, as it informs the design of the state machine. We first find that 16.4% of the validation turns have the same result state, agent state, and user state in training (with different utterances), and for these the accuracy is 90.3%. This speaks to the strength of having a large, automatically synthesized training set. Second, 66.8% of the turns are representable in the state machine, while not in the training set; on these, the accuracy is 71.8%. This shows the state machine has very good coverage of real world conversations, and the neural model can learn it well. Finally, 16.8% require generalization beyond the state machine; on these turns, we achieve an accuracy of 47.5%. This indicates that the model can still generalize effectively outside the synthesized training data. We also observed that about half of the turns in the last category are points where the user switches domains. These can occur at arbitrary points of the dialogue, but our state machine limits when they occur to avoid confusion. Yet, the network can still pick up enough information from the utterance to interpret it correctly.

Contextual Semantic Parsing Vs. Dialogue State Tracking
Our goal is to build an agent that can interpret the user's utterances and act accordingly, turn by turn. Prior work instead attempted to compute the current state given a full conversation. They measured the Joint Accuracy metric, which checks for the correctness of all predicted slots given a full conversation, while we use Turn-by-Turn Accuracy.
In the interactive setting, both metrics measure how well an agent can understand the current user's utterance and continue the conversation, and they are comparable. Note that our approach is easier Model Accuracy Joint Accuracy (MultiWOZ 2.1) TRADE (Wu et al., 2019) 45.6 SUMBT (Lee et al., 2019a) 46.7 DSTQA (Zhou and Small, 2019) 51.2 DST-Picklist (Zhang et al., 2019a) 53.3 SST (Chen et al., 2020) 55.2 TripPy (Heck et al., 2020) 55.3 SimpleTOD (Hosseini-Asl et al., 2020) 55.7 Turn-By-Turn Accuracy (Cleaned Test Set) CTXNLU 71.1 We compare the two approaches in Table 3. Note that we cannot evaluate the existing models on our new test set, because we cannot afford to reannotate the training set to retrain them. Our results show that our model can be more effective than the state of the art at predicting the correct state for the next turn of the conversation while only using a tiny fraction of the annotated data.
We also measure the accuracy up to the first error in the dialogue. This is the number of turns that the model can predict correctly, assuming no more correct predictions after the first error. This metric captures the fact that, if a database query is performed incorrectly, the conversation cannot continue. The metric was not reported previously, so we can only compare against TRADE, for which code is available. CTXNLU achieves an up-to-firsterror accuracy of 37.6% on the cleaned test set, while TRADE has an accuracy of 37.3% on the original test set (which matches its training). Our model achieves state-of-the-art accuracy, despite being trained with only a tiny amount of real data.

Ablation Study
In our next analysis, we wish to evaluate how different aspects of our methodology combine in our results. We compare the following experiments: • Our full methodology, training the CTXNLU model with synthesized data and then finetuning on the few shot training set.  • Training with only synthesized data, without any few-shot data.
• Training with only the few shot dataset, without any synthesized training.
The results of this analysis on the validation set are shown in Table 4. Using only few-shot data is better than using only synthesized data, but using both is even better, by about 9%. This shows the effectiveness of synthesized data in training: it can boost the small amount of manually-annotated data, to yield high accuracy with little cost.

Conclusion
This paper presents a methodology to build dialogue agents at a fraction of the cost of previous methods. We built an abstract state machine for transaction dialogues, which any developer can instantiate in their domain with a database, APIs, and a few annotations. From the state machine, we derive an agent that employs a safe, rule-based policy. The state machine covers 96% of the agent turns and 83% of the user turns on the MultiWOZ benchmark. Using the state machine we generate millions of synthetic sentences, which, when combined with a small set of annotated human conversations, produce an effective neural model to track the user dialogue state. Observing how the model errs on human dialogues informs how to improve the state machine and the model's accuracy.
Unlike prior work that uses the full history of the conversation, our model takes as input only the current formal state of the conversation and the latest utterance of the user, and produces the new user state. This is a simpler problem and leads to higher accuracy.
Our methodology allows us to evaluate on the MultiWOZ benchmark, by reannotating only the evaluation sets and not using the training data. We achieve 57% turn-by-turn exact match accuracy, and 71% accuracy at predicting all slots. The results suggest that our methodology can be effective at bootstrapping dialogue agents from scratch at a significantly reduced cost.