Task-Oriented Dialogue as Dataflow Synthesis (2020)

Abstract: We describe an approach to task-oriented dialogue in which dialogue state is represented as a dataflow graph. A dialogue agent maps each user utterance to a program that extends this graph. Programs include metacomputation operators for reference and revision that reuse dataflow fragments from previous turns. Our graph-based state enables the expression and manipulation of complex user intents, and explicit metacomputation makes these intents easier for learned models to predict. We introduce a new dataset, SMCalFlow, featuring complex dialogues about events, weather, places, and people. Experiments show that dataflow graphs and metacomputation substantially improve representability and predictability in these natural dialogues. Additional experiments on the MultiWOZ dataset show that our dataflow representation enables an otherwise off-the-shelf sequence-to-sequence model to match the best existing task-specific state tracking model. The SMCalFlow dataset, code for replicating experiments, and a public leaderboard are available at https://www.microsoft.com/en-us/research/project/dataflow-based-dialogue-semantic-machines .

## introduction two central design decisions in modern conversational ai systems are the choices of state and action representations, which determine the scope of possible user requests and agent behaviors. dialogue systems with fixed symbolic state representations (like slot filling systems) are easy to train but hard to extend @xcite . deep continuous state representations are flexible enough to represent arbitrary properties of the dialogue history, but so unconstrained that training a user: where is my meeting at 2 this afternoon? user: can you create a meeting with megan right before that starts? user: megan bowen. place(findevent(eventspec(@xmath0, @xmath1, @xmath2, @xmath3, @xmath4: it's in conference room d. start 'megan' agent: which person named megan did you mean? underconstrainedexception!(invite) agent: ok, i'll book a meeting with megan bowen from 1:30 to 2:00 pm today. eventspec personspec oldloc new rootloc figure 1 : a dialogue and its dataflow graph. turn (1) is an ordinary case of semantic parsing: the agent predicts a compositional query that encodes the user's question. evaluating this program produces an initial graph fragment. in turn (2), that is used to refer to a salient event; the agent resolves it to the event retrieved in (1), then uses it in a subsequent computation. turn (3) repairs an exception via a program that makes a modified copy of a graph fragment. neural dialogue policy "end-to-end" fails to learn appropriate latent states @xcite . this paper introduces a new framework for dialogue modeling that aims to combine the strengths of both approaches: structured enough to enable efficient learning, yet flexible enough to support open-ended, compositional user goals that involve multiple tasks and domains. the framework has two components: a new state representation in which dialogue states are represented as dataflow graphs; and a new agent architecture in which dialogue agents predict compositional programs that extend these graphs. over the course of a dialogue, a growing dataflow graph serves as a record of common ground: an executable description of the entities that were mentioned and the actions and computations that produced them (figure 1 ). while this paper mostly focuses on representational questions, learning is a central motivation for our approach. learning to interpret naturallanguage requests is simpler when they are understood to specify graph-building operations. human speakers avoid repeating themselves in conversation by using anaphora, ellipsis, and bridging to build on shared context @xcite . our framework treats these constructions by translating them into explicit metacomputation operators for reference and revision, which directly retrieve fragments of the dataflow graph that represents the shared dialogue state. this approach borrows from corresponding ideas in the literature on program transformation @xcite and results in compact, predictable programs whose structure closely mirrors user utterances. experiments show that our rich dialogue state representation makes it possible to build better dialogue agents for challenging tasks. first, we release a newly collected dataset of around 40k natural dialogues in english about calendars, locations, people, and weather-the largest goaloriented dialogue dataset to date. each dialogue turn is annotated with a program implementing the user request. many turns involve more challenging predictions than traditional slot-filling, with compositional actions, cross-domain interaction, complex anaphora, and exception handling (figure 2 ). on this dataset, explicit reference mechanisms reduce the error rate of a seq2seq-withcopying model @xcite by 5.9% on all turns and by 10.9% on turns with a cross-turn reference. to demonstrate breadth of applica-bility, we additionally describe how to automatically convert the simpler multiwoz dataset into a dataflow representation. this representation again enables a basic seq2seq model to outperform a state-of-the-art, task-specific model at traditional state tracking. our results show that within the dataflow framework, a broad range of agent behaviors are both representable and learnable, and that explicit abstractions for reference and revision are the keys to effective modeling. ## overview: dialogue and dataflow this section provides a high-level overview of our dialogue modeling framework, introducing the main components of the approach. sections 3-5 refine this picture, describing the implementation and use of specific metacomputation operators. we model a dialogue between a (human) user and an (automated) agent as an interactive programming task where the human and computer communicate using natural language. dialogue state is represented with a dataflow graph. at each turn, the agent's goal is to translate the most recent user utterance into a program. predicted programs nondestructively extend the dataflow graph, construct any newly requested values or real-world side-effects, and finally describe the results to the user. our approach is significantly different from a conventional dialogue system pipeline, which has separate modules for language understanding, dialogue state tracking, and dialogue policy execution @xcite . instead, a single learned model directly predicts executable agent actions and logs them in a graphical dialogue state. programs, graphs, and evaluation the simplest example of interactive program synthesis is question answering: when is the next retreat? agent: it starts on april 27 at 9 am. here the agent predicts a program that invokes an api call (findevent) on a structured input (eventspec) to produce the desired query. 1 this is a form of semantic parsing @xcite . the program predicted above can be rendered as a dataflow graph: here we have annotated two nodes to show that the value of after(now()) is a datetimespec and the value of the returned start node is a specific datetime. evaluated nodes are shaded in our diagrams. exceptions (see §5) block evaluation, leaving downstream nodes unevaluated. the above diagram saves space by summarizing the (structured) value of a node as a string. in reality, each evaluated node has a dashed result edge that points to the result of evaluating it: that result is itself a node in the dataflow graphoften a new node added by evaluation. it may have its own result edge. 2 a node's value is found by transitively following result edges until we arrive its hearer). the fact that next in this context triggered a search for "events after now" was learned from annotations. see §6 for a discussion of how these annotations are standardized in the smcalflow dataset. 2 in other words, a function does not have to return a terminal node. its result may be an existing node, as we will see in §3. or it may be a new non-terminal node, i.e., the root of a subgraph that implements the function. the new nodes in the subgraph are then evaluated further, giving them result edges, although they also remain available for reference and revision. of course, a library function such as findevent or at a node whose result is itself. such a terminal node is either a primitive value (e.g., 2020), or a constructor (e.g., datetime) whose parent nodes' values specify its arguments. a constructor has the same (capitalized) name as the type it constructs. ## reference resolution in a dialogue, entities that have been introduced once may be referred to again. in dataflow dialogues, the entities available for reference are given by the nodes in the dataflow graph. entities are salient to conversation participants to different degrees, and their relative salience determines the ways in which they may be referenced @xcite . for example, it generally refers to the most salient non-human entity, while more specific expressions like the friday meeting are needed to refer to accessible but less salient entities. not all references to entities are overt: if the agent says "you have a meeting tomorrow" and the user responds "what time?", the agent must predict the implicit reference to a salient event. dataflow pointers we have seen that refer is used to find referents for referring expressions. in general, these referents may be existing dataflow nodes or new subgraphs for newly mentioned entities. we now give more detail about both cases. imagine a dialogue in which the dataflow graph contains the following fragment (which translates a mention of easter or answers when is easter?): finddate easter holiday finddatetime easter suppose the user subsequently mentions the day after that. we wish to produce this computation: in our framework, this is accomplished by mapping the day after that to +(refer(), days(1)). the corresponding graph is not quite the one shown above, but it evaluates to the same value: this shows how the refer() call is reified as a node in the dataflow graph. its result is the salient finddatetime node from the previous turnwhose own result, a specific datetime, now serves as the value of refer. we show both result edges here. evaluating + adds a day to this old datetime value to get the result of +, a new datetime. to enable dataflow graph manipulation with referring expressions, all that is required is an implementation of refer that can produce appropriate pointers for both simple references (that) and complex ones (the first meeting). constraints a call to refer is essentially a query that retrieves a node from the dialogue history, using a salience model discussed below. refer takes an optional argument: a constraint on the returned node. indeed, the proper translation of that in the context the day after that would be refer(constraint @xcite ). 3 constraints are predicates built from boolean connectives and the constructions illustrated below: foot_3 to interpret a natural language referring expression, the program prediction model only needs to translate it into a contextually appropriate constraint c. refer(c) is then evaluated using a separate salience retrieval model that returns an appropriate node. the following dialogue shows referring expressions in action: what's happening this morning? agent: you have a planning meeting at 9 am. ## revision beyond referring to previously mentioned entities (nodes), task-oriented dialogues frequently refer to previously executed computations (subgraphs). this is one of the major advantages of representing the dialogue state as a dataflow graph of computations, not just a set of potentially salient entities. ## recovery sometimes users make requests that can be fulfilled only with the help of followup exchanges, if at all. requests might be incomplete: ## data to validate our approach, we crowdsourced a large english dialogue dataset, smcalflow, featuring task-oriented conversations about calendar events, weather, places, and people. figure 2 has an example. smcalflow has several key characteristics: richly annotated: agent responses are executable programs, featuring api calls, function composition, and complex constraints built from strings, numbers, dates and times in a variety of formats. they are not key-value structures or database queries, but instead full descriptions of the runtime behavior needed to react to the user in a real, grounded dialogue system. open-ended: we did not constrain crowdworkers to scripts. instead, they were given general information about agent capabilities and were encouraged to interact freely. a practical dialogue system must also recognize and respond to out-ofscope requests. our dataset includes many such examples (see the fourth user turn in figure 2 ). cross-domain: smcalflow spans four major domains: calendar, weather, places, and people. cross-domain interaction is pervasive (figure 2 ). to cover a rich set of back-end capabilities while encouraging worker creativity, we designed a wide range of scenarios to guide dialogue construction. there are over 100 scenarios of varying topic and granularity. dialogues are collected via a wizard-of-oz process. every dialogue is associated with a scenario. at each turn, a crowdworker acting as the user is presented with a dialogue as context and is asked to append a new utterance. an annotator acting as the agent labels the utterance with a program (which may include refer and revise) and then selects a natural-language response from a set of candidates produced by the language generation model described in §2. the user: can you remind me to go to the airport tomorrow morning at 8am? createcommiteventwrapper( createpreflighteventwrapper( eventbuilder( @xmath5, @xmath6, @xmath7: does this look right? [showing an event card with start at 8 am and the event name] user: make the location laguardia airport. reviseconstraint( @xmath8, @xmath9, @xmath10: how is this? [showing an updated card] user: what can i expect the weather there to be tomorrow morning? weatherqueryapi( @xmath11, @xmath12, @xmath13 agent: it will be partly cloudy with a high of 77 °f and a low of 67 °f in laguardia airport between 6:00 am and 12:00 pm. user: how is the traffic on the way there? ## experiments we evaluate our approach on smcalflow and multiwoz 2.1. all experiments use the open5 we release the conversion script along with smcalflow. nmt @xcite pointer-generator network @xcite , a sequence-to-sequence model that can copy tokens from the source sequence while decoding. our goal is to demonstrate that dataflow-based representations benefit standard neural model architectures. dataflowspecific modeling might improve on this baseline, and we leave this as a challenge for future work. for each user turn i, we linearize the target program into a sequence of tokens z i . this must be predicted from the dialogue contextnamely the concatenated source sequence here c is a context window size, x j is the user utterance at user turn j, y j is the agent's naturallanguage response, and z j is the linearized agent program. each sequence x j , y j , or z j begins with a separator token that indicates the speaker (user or agent). our formulation of context for multi-woz is standard (e.g., @xcite . we take the source and target vocabularies to consist of all words that occur in (respectively) the source and target sequences in training data, as just defined. the model is trained using the adam optimizer @xcite with the maximum likelihood objective. we use 0.001 as the learning rate. training ends when there have been two different epochs that increased the development loss. we use glove800b-300d (cased) and glove6b-300d (uncased) @xcite to initialize the vocabulary embeddings for the sm-calflow and multiwoz experiments, respectively. the context window size c, hidden layer size d, number of hidden layers l, and dropout rates r are selected based on the agent action accuracy (for smcalflow) or dialogue-level exact match (for multiwoz) on the development set from {2, 4, 10}, {256, 300, 320, 384}, {1, 2, 3}, {0.3, 0.5, 0.7} respectively. approximate 1-best decoding uses a beam of size 5. quantitative evaluation for the full representation, c, d, l, and r are 2, 384, 2, and 0.5, respectively. for the inline variant, they are 2, 384, 3, and 0.5. turn-level exact match accuracy is around 73% for the development set and 67% for the test set. inlining metacomputation, which forces the model to explicitly resolve cross-turn computation, reduces accuracy by 5.9% overall, 10.9% on turns involving references, and 9.1% on turns involving revision. dataflow-based metacomputation operations are thus essential for good model performance in all three cases. we further evaluate our approach on dialogue state tracking using multiwoz 2.1. joint goal dialogue prefix dataflow .467 .220 3.07 inline refer .447 .202 2.97 inline both .467 .205 2.90 trade .454 .168 2.73 error analysis beyond the quantitative results shown in tables 2 3 , we manually analyzed 100 smcalflow turns where our model mispredicted. the fourth category, ambiguity errors, is more interesting. in these cases, the predicted plan corresponds to an interpretation of the user utterance that would be acceptable in some discourse context. in a third of these cases, this interpretation is ruled out by either dialogue context (e.g., interpreting what's next? as a request for the next list item rather than the event with the next earliest start time) or commonsense knowledge (make it at 8 means 8 a.m. for a business meeting and 8 p.m. for a dance party). in the remaining cases, the predicted plan expresses an alternative computation that produces the same result, or an alternative interpretation that is also contextually appropriate. ## related work the view of dialogue as an interactive process of shared plan synthesis dates back to grosz and sidner's earliest work on discourse structure @xcite . that work represents the state of a dialogue as a predicate recognizing whether a desired piece of information has been communicated or change in world state effected. goals can be refined via questions and corrections from both users and agents. the only systems to attempt full versions of this shared-plans framework (e.g., @xcite required inputs that could be parsed under a predefined grammar. subsequent research on dialogue understanding has largely focused on two simpler subtasks: contextual semantic parsing approaches focus on complex language understanding without reasoning about underspecified goals or agent initiative. here the prototypical problem is iterated question answering @xcite , in which the user asks a sequence of questions corresponding to database queries, and results of query execution are presented as structured result sets. @xcite describe a semantic parsing representation targeted at more general dialogue problems. most existing methods interpret context-dependent user questions (what is the next flight to atlanta? when does it land?) by learning to copy subtrees @xcite @xcite or tokens @xcite ) from previously-generated queries. in contrast, our approach reifies reuse with explicit graph operators. slot-filling approaches @xcite ) model simpler utterances in the context of full, in-teractive dialogues. it is assumed that any user intent can be represented with a flat structure consisting of a categorical dialogue act and a mapping between a fixed set of slots and string-valued fillers. existing fine-grained dialogue act schemes @xcite can distinguish among a range of communicative intents not modeled by our approach, and slot-filling representations have historically been easier to predict @xcite and annotate @xcite . but while recent variants support interaction between related slots @xcite and fixed-depth hierarchies of slots @xcite , modern slot-filling approaches remain limited in their support for semantic compositionality. by contrast, our approach supports user requests corresponding to general compositional programs. more recent end-to-end dialogue agents attempt to map directly from conversation histories to api calls and agent utterances using neural sequence-to-sequence models without a representation of dialogue state @xcite . while promising, models in these papers fail to outperform rule-or template-driven baselines. @xcite report greater success on a generation-focused task, and promising results have also been obtained from hybrid neuro-symbolic dialogue systems @xcite @xcite . much of this work is focused on improving agent modeling for existing representation schemes like slot filling. we expect that many modeling innovations (e.g., the neural entity linking mechanism proposed by @xcite could be used in conjunction with the new representational framework we have proposed in this paper. like slot-filling approaches, our framework is aimed at modeling full dialogues in which agents can ask questions, recover from errors, and take actions with side effects, all backed by an explicit state representation. however, our notions of "state" and "action" are much richer than in slot-filling systems, extending to arbitrary compositions of primitive operators. we use semantic parsing as a modeling framework for dialogue agents that can construct compositional states of this kind. while dataflow-based representations are widely used to model execution state for programming languages @xcite , this is the first work we are aware of that uses them to model conversational context and dialogue. ## conclusions we have presented a representational framework for task-oriented dialogue modeling based on dataflow graphs, in which dialogue agents predict a sequence of compositional updates to a graphical state representation. this approach makes it possible to represent and learn from complex, natural dialogues. future work might focus on improving prediction by introducing learned implementations of refer and revise that, along with the program predictor itself, could evaluate their hypotheses for syntactic, semantic, and pragmatic plausibility. the representational framework could itself be extended, e.g., by supporting declarative user goals and preferences that persist across utterances. we hope that the rich representations presented here-as well as our new dataset-will facilitate greater use of context and compositionality in learned models for task-oriented dialogue.