Learning Symmetric Collaborative Dialogue Agents with Dynamic Knowledge Graph Embeddings
We study a symmetric collaborative dialogue setting in which two agents, each with private knowledge, must strategically communicate to achieve a common goal. The open-ended dialogue state in this setting poses new challenges for existing dialogue systems. We collected a dataset of 11K human-human dialogues, which exhibits interesting lexical, semantic, and strategic elements. To model both structured knowledge and unstructured language, we propose a neural model with dynamic knowledge graph embeddings that evolve as the dialogue progresses. Automatic and human evaluations show that our model is both more effective at achieving the goal and more human-like than baseline neural and rule-based models.
1 Introduction
Current task-oriented dialogue systems (Young et al., 2013; Wen et al., 2017; Dhingra et al., 2016) require a pre-defined dialogue state (e.g., slots such as food type and price range for a restaurant searching task) and a fixed set of dialogue acts (e.g., request, inform). However, human conversation often requires richer dialogue states and more nuanced, pragmatic dialogue acts. In contrast, recent open-domain chat systems (Shang et al., 2015; Serban et al., 2015b; Sordoni et al., 2015; Li et al., 2016a) learn a mapping directly from previous utterances to the next utterance. While these models capture open-ended aspects of dialogue, the lack of structured dialogue state prevents them from being directly applied to settings that require interfacing with structured knowledge.
In order to bridge the gap between the two types of systems, we focus on a symmetric collabora-
tive dialogue setting, which is task-oriented but encourages open-ended dialogue acts. In our setting, two agents, each with a private list of items with attributes, must communicate to identify the unique shared item. Consider the dialogue in Figure 1, in which two people are trying to find their mutual friend. When B asks “do you have anyone who went to columbia?”, it suggests that she has some Columbia friends and they probably work at Google. Such conversational implicature is lost when interpreting it as simply requesting information about Columbia. In addition, it is hard to define a state that captures the diverse semantics in these utterances (e.g., defining “most of”, “might be”; see details in Table 1).
To model both structured and open-ended context, we propose the Dynamic Knowledge Graph Network (DynoNet), in which the dialogue state is modeled as a knowledge graph with an embedding for each node (Section 3). Our model is similar
2
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
to EntNet (Henaff et al., 2017) in that node/entity embeddings are updated recurrently given new utterances. The difference is that we structure entities as a knowledge graph; as the dialogue proceeds, new nodes are added and new context is propagated on the graph. An attention-based mechanism (Bahdanau et al., 2015) over the node embeddings drives generation of new utterances. Our model’s use of knowledge graphs captures the grounding capability of classic task-oriented systems and the graph embedding provides the representational flexibility of neural models.
The naturalness of communication in the symmetric collaborative setting enables large-scale data collection: We were able to crowd-source around 11K human-human dialogues on Amazon Mechanical Turk (AMT) in less than 15 hours.1 We show that the new dataset calls for more powerful representation beyond fully-structured states (Section 2.2).
Aside from the third-party human evaluation adopted by most work (Liu et al., 2016; Li et al., 2016b,c), we also conduct partner evaluation (Wen et al., 2017) where AMT workers rate their conversational partners (our models) based on fluency, correctness, cooperation, and human-likeness. We compare DynoNet with baseline neural models and a strong rule-based system. The results show that DynoNet can perform the task with humans efficiently and naturally; it also captures some strategic aspects of human-human dialogues.
The contributions of this work are: (i) a new symmetric collaborative dialogue setting and a large dialogue corpus that push the boundaries of existing dialogue systems; (ii) DynoNet that integrates semantically rich utterances with structured knowledge to represent open-ended dialogue states; (iii) multiple automatic metrics based on bot-bot chat and a comparison of third-party and partner evaluation.
2 Symmetric Collaborative Dialogue
We introduce a collaborative task between two agents and describe the human-human dialogue collection process. We show that our data exhibits diverse, interesting language phenomena.
1The dataset is available publicly at http: //anonymous.
2.1 Task Definition
In the symmetric collaborative dialogue setting, there are two agents, A and B, each with a private knowledge base—KBA and KBB, respectively. Each knowledge base includes a list of items, where each item has a value for each attribute. For example, in the MutualFriends setting, Figure 1, items are friends and attributes are name, school, etc. There is a shared item that A and B both have; their goal is to converse with each other to determine the shared item and select it. Formally, an agent is a mapping from its private KB and the dialogue thus far (sequence of utterances) to the next utterance to generate. A dialogue is considered successful when both agents correctly select the shared item. This setting has parallels in human-computer collaboration where each agent has different expertise.
2.2 Data collection
We created a schema containing 7 attributes and more than 3K entities (attribute values) in total. To elicit linguistic and strategic variants, we generate a random scenario for each task by varying the number of items, the number attributes, and the distribution of values for each attribute. See Appendix B for details of scenario generation.
We crowd-sourced dialogues on AMT by randomly pairing up users to perform the task within 5 minutes.2 To discourage random guessing, we prevent users from selecting more than once every 10 seconds. The chat interface is shown in Appendix C. Our task was very popular and we collected 11K dialogues over a period of 13.5 hours.3
2.3 Dataset statistics
We show the basic statistics of our dataset in Table 3. An utterance is defined as a message sent by the user. The average utterance length is shorter due to the informality of the chat, however, a user usually sends multiple utterances in one turn. Some example dialogues are shown in Table 6 and Appendix H.
We coarsely categorize utterances into inform, ask, answer, greeting, apology by pattern matching (Appendix E). There are 7.4% multi-type utterances and 30.9% multi-entity utterances. In Ta-
2If users exceed the time limit, the dialogue is marked as unsuccessful (but still logged).
3Tasks are put up in batches; the total time excludes intervals between batches.
4Entity names are replaced by entity types.
3
206
207
208
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
256
257
258
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
# dialogues 11439 # completed dialogues 9041 Vocabulary size 4548 Average # of utterances 11.41 Average time taken per task (sec.) 91.18 Average utterance length (tokens) 4.84 Number of linguistic templates4 30370
Table 3: Statistics of the MutualFriends dataset.
ble 1, we show example utterances where the rich semantics cannot be sufficiently represented by traditional slot-value pairs. Even the more standard ones can be challenging due to coreference and conjunctions.
Our dataset also exhibits interesting communication phenomena that add to its complexity. Coreference occurs frequently when people check attributes jointly. Sometimes the mentions are dropped: it simply continues from the previous partner utterance. People occasionally use external knowledge to group items with out-of-schema attributes (e.g., gender based on names, location based on schools). We summarize these phenomena in Table 2. In addition, we find 30% utterances involve cross-talk where the conversation does not progress linearly (e.g., italic utterances in Figure 1). Cross-talk is a common characteristic of online chat that creates ambiguity (Ivanovic, 2005).
One strategic aspect of this task is the order in which attributes are mentioned. We find that peo-
ple tend to start from attributes with fewer unique values, e.g., “all my friends like morning” given the KBB in Table 6, as intuitively it would help exclude items quickly given fewer values to check.5 We provide a more detailed analysis of strategy in Section 4.2 and Appendix F.
3 Dynamic Knowledge Graph Network
The diverse semantics in our data motivates us to combine rich but unstructured representation of the dialogue history with structured knowledge. Our model consists of three components shown in Figure 2: (i) a dynamic knowledge graph, which represents the private KB and dialogue history in a graph (Section 3.1), (ii) a graph embedding over the nodes (Section 3.2), and (iii) an utterance generator (Section 3.3).
The knowledge graph represents entities and relations in the agent’s private KB, e.g., google belongs to company. As the conversation unrolls, utterances are embedded and incorporated to node embeddings of mentioned entities. In Figure 2, “Most of my friends work for Google” updates the embedding of google. Further, mentioned nodes pass on this new information to their neighbors so that related entities (e.g., those in the same row or column) also receive the information. In our example, jessica and josh both receive new context when google and columbia are mentioned.
5Our goal is to model human behavior thus we do not discuss the optimal strategy here.
4
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
The utterance generator, an LSTM, then produces the next utterance by attending to the node embeddings that represent the dialogue state.
3.1 Knowledge Graph
Given a dialogue of T utterances, we construct an evolving graph Gt over the KB and dialogue history for agent A.6 We consider three types of nodes: item nodes, attribute nodes, and entity nodes. Edges between nodes represent their relations. For example, (item-1, hasSchool, columbia) means that the first item has attribute school whose value is columbia. An example graph is shown in Figure 2. The graph is updated at the end of an utterance if new entities (not in KBA) are mentioned; they are added as dangling nodes.7
3.2 Graph Embedding
Given a knowledge graph, we are interested in computing a vector representation for each node v that captures both its unstructured context from the dialogue history and its structured context in the KB. The node embedding V is built from three parts: structural properties of an entity defined by the KB, embeddings of utterances in the dialogue history, and message passing between neighboring nodes.
Node Features. Simple structural properties of the KB often govern what is talked about; e.g., a high-frequency entity is often interesting (consider
6 It is important to differentiate perspectives of the two agents as they have different KBs. Thereafter we assume the perspective of agent A, i.e., accessing KBA and generating utterances for A only, and refer to B as the partner.
7 We use a rule-based lexicon to link text spans to entities. See details in Appendix D.
“All my friends like dancing.”). We represent this type of information as an indicator vector F (v), including the frequency and type (item, attribute, or entity type) of entity v.
Mention Vectors. A mention vector Mt(v) contains unstructured context from utterances relevant to node v up to turn t. Given embedding ut of the last utterance (Section 3.3), we define
Mt(v) = Mt 1(v) + (1 )ut,
=
( W [Mt 1(v), ut] if ut mentions v
1 otherwise
where is the sigmoid function and W is a projection matrix. If no entity is mentioned in ut, we update v in ut 1. This is useful when ut answers a question, e.g., “do you have any google friends?” “No.” To differentiate between the agent’s and the partner’s utterances, Mt(v) consists of two separate components for utterances from each source.
Recursive Node Embeddings. We propagate information between nodes according to the structure of the knowledge graph. In Figure 2, given “anyone went to columbia?”, the agent should focus on her Google friends who went to Columbia. Therefore, we want this information to be sent to item nodes connected to columbia, and one step further to other attributes of these items because they might be implicitly referred to (google which was mentioned previously) or mentioned next (jessica and josh which will be generated).
We compute the embeddings recursively, analogous to belief propagation:
V kt (v) = max v02N(v) tanh
⇣ Wm h V k 1t (v 0 ), R(ev!v0) i⌘ ,
5
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
where V kt (v) is the depth-k node embedding at turn t, Wm is a projection matrix, R is an relation embedding function, ev!v0 denotes the relation from v to v0, and max is an element-wise max operation.8 Example message passing paths are shown in Figure 2.
The final node embedding is the concatenation of embeddings at each depth:
Vt(v) = ⇥ V 0t (v), . . . , V K t (v) ⇤ ,
where K is a hyperparameter (we experiment with K 2 {0, 1, 2}) and V 0t (v) = [F (v),Mt(v)]. The node embedding is updated periodically whenever Mt(v) is updated by a new utterance.
3.3 Utterance Generation
In this section, we describe how an utterance is embedded and generated. Our model is based on a recurrent neural network (RNN). On turn t (we elide the subscript t for notational convenience), upon receiving an utterance of n tokens, {xn}Nn=1, the RNN maps it to a vector: hn = LSTMenc(hn 1, xn). We use the last hidden state hn as the utterance embedding u which updates the mention vectors.
Given (updated) embeddings of each node, we use another RNN to generate the next utterance, where each token is either copied from a node or generated from the vocabulary. Formally,
hn = LSTMdec(hn 1, [xn, ct]),
where ct is a weighted sum of node embeddings in the current turn: ct = P i ↵n,iVt(vi). As shown in Figure 2, entities relevant to generating the next utterance should have high weights. We compute the weights through standard attention mechanism: ↵n = softmax(an) and an,i = wa tanh (W a [hn 1, Vt(vi)]), where wa is a scoring vector and W a is a projection matrix.
The RNN outputs a distribution over words in the vocabulary and the nodes in Gt as in the copying mechanism of Jia and Liang (2016) :
p(xn+1 = w |xn, Gt) / exp (Uwhcn + b) , p(xn+1 = r(vi) |xn, Gt) / exp (an,i) ,
where w is a word in the vocabulary, Uw and b are the model parameters, and r(vi) is the realization of the entity represented by node i, e.g., generating “Google” given the node google.9
8Using sum slightly hurts performance. 9 We realize an entity by sampling from the empirical dis-
tribution of its surface forms in the training set.
3.4 Entity Abstraction
In our setting, the role of an entity is governed by its relation to other entities and relevant utterances. For example, replacing google with alphabet in Figure 1 should make very little difference to the conversation. Note that we do not use an embedding matrix for any entity when computing V (v). Furthermore, in the input embedding layer of the LSTM, we represent an entity by its type embedding concatenated with its node embedding. Accordingly, a regular word is represented as its word embedding concatenated with a zero vector of the same dimension as V . This way, the models’ representation of an entity only depends on its structural property in the KB and the dialogue context.
4 Experiments
4.1 Setup
We use a one-layer LSTM with 100 hidden units and 100-dimensional word vectors for both the encoder and the decoder. We maximize the likelihood of each utterance from perspectives of both agents. The parameters are optimized by AdaGrad (Duchi et al., 2010) with a learning rate of 0.5. We ran at least 10 epochs; after that, training stops if there is no improvement for 5 epochs. By default, we perform K = 2 iterations of message passing to compute node embeddings. We randomly split the data into train, dev, and test sets and only train on successful dialogues. For decoding, we sequentially sample from the output distribution with a softmax temperature of 0.5.10 Hyperparameters are tuned on the dev set. We compare DynoNet with its static cousion (StanoNet) and a rule-based system (Rule). StanoNet uses G0 throughout the dialogue, thus the dialogue context is completely contained in the RNN hidden states instead of being structured around the knowledge graph. Rule maintains weights for each entity and each item in the KB to decide what to talk about and which item to select. It has a pattern-matching semantic parser, a rule-based policy, and a templated generator. See Appendix G for details.
10 Since selection is a common ‘utterance’ in our dataset and neural generation models are susceptible to overgenerating common sentences, we halve its probability during sampling.
6
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
4.2 Evaluation
We test our systems in two interactive settings: bot-bot chat and bot-human chat. We perform both automatic evaluation and human evaluation to test syntactic, semantic, and pragmatic competence of each system.
Automatic Evaluation. First, we compute the cross-entropy (`) of a model on test data. As shown in Table 4, DynoNet has the lowest test loss. Next, we have a model chat with itself on the scenarios from the test set.11 We evaluate the chats with respect to language variation, effectiveness and strategy.
For language variation, we report the average utterance length Lu and the unigram entropy H in Table 4. Compared to Rule, the neural models tend to generate shorter utterances (Li et al., 2016b; Serban et al., 2017). However, they are more diverse; for example, questions are asked in multiple ways such as “Do you have ...”, “Any friends like ...”, “What about ...”.
At the discourse level, we expect the distribution of a bot’s utterance types to match the distribution of human’s. We show percentages of each utterance type in Table 4. For Rule, the decision about which action to take is written in the rules, while StanoNet and DynoNet learned to behave in a more human-like way, frequently informing and asking questions.
To measure effectiveness, we compute the success rate per turn (CT ) and per selection (CS). In Table 4, humans are the best at this game, followed by Rule which is comparable to DynoNet. Next, we investigate the strategies leading to these results.
An agent needs to decide which entity/attribute to check first to quickly reduce the search space. We hypothesize that humans tend to first focus on a majority entity and an attribute with fewer unique values (Section 2.3). We show the average frequency of first-mentioned entities (#Ent1) and the average number of unique values for first-mentioned attributes (|Attr1|) in Table 4.12 Clearly, both DynoNet and StanoNet successfully matched human’s starting strategy by favoring more frequent entities and attributes of smaller do-
11 We limit the number of turns in bot-bot chat to be the maximum number of turns humans took in the test set (46 turns).
12 Both numbers are normalized to [0, 1] with respect to all entities/attributes in the corresponding KB.
main size. To examine the overall strategy, we show the average number of attributes and entities mentioned during the conversation in Table 4. Humans and DynoNet strategically focus on a few attributes and entities, whereas Rule needs almost twice entities to achieve similar success rates. This suggests that the effectiveness of Rule mainly comes from large amounts of unselective information, which is consistent with feedback from their human partners.
Partner Evaluation. We generated 200 new scenarios and put up the bots on AMT using the same chat interface that used for data collection. Each AMT worker is randomly paired with Rule, StanoNet, DynoNet, or another human (but they don’t know which), and we make sure that all four types of agents are tested in each scenario (800 dialogues in total). At the end of each task, humans are asked to rate their partner in terms of fluency, correctness, cooperation, and humanlikeness from 1 (very bad) to 5 (very good), along with optional comments.
As shown in the example dialogues in Table 6, DynoNet cooperates smoothly with the human partner, e.g., replying with relevant information about morning/indoor friends when the partner mentioned that all her friends prefer morning and most like indoor. However, it “lied” when saying that it had a morning friend who likes outdoor. StanoNet starts well but doesn’t continue with the morning friend, because the morning node is not updated dynamically when mentioned by the partner. Rule always informs true facts but poorly follows the partner. In the comments, most complaint about Rule is that it was not ‘listening’ or ‘understanding’. We show the average ratings in Table 5 and the histograms in Appendix H. Overall, DynoNet achieves better partner satisfaction, especially in cooperation.
Third-party Evaluation. Since the evaluator cannot see the partner’s KB, judgment on correctness is a mere guess. Therefore, we also created a third-party evaluation task, where an independent AMT worker is shown a conversation and the KB of one of the agents; she is asked to rate the same aspects of the agent as in the partner eval-
13We only show the most frequent speech acts therefore the numbers do not sum to 1.
14For third-party evaluation, we first take mean of each question then average the ratings.
7
606
607
608
609
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
656
657
658
659
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
uation and provide justifications.15 The average ratings and histograms are shown in Table 5 and Appendix H respectively.
Surprisingly, there is a discrepancy between the two evaluation modes. Manual analysis of the comments indicates that while a participant in the dialogue considers the partner fluent as long as there is no communication overhead, a third person may have higher standards, e.g., thinking short sentences do not fully reveal an agent’s fluency. For human-likeness, partner evaluation is largely correlated with coherence (e.g., not repeating or ignoring past information) and task success, whereas third-party evaluators often rely on informality (e.g., usage of colloquia like “hiya”, capitalization, and abbreviation) or intuition.16 Interestingly, third-party evaluators noted most phenomena listed in Table 2 as indicators of humanbeings, e.g., correcting oneself, making chit-chat other than simply finishing the task.
4.3 Ablation Studies
Our model has two novel designs: entity abstraction and message passing for node embeddings.
15Each agent in a dialogue is rated by at least 5 people. 16 Nevertheless, informality can be easily handcrafted or
learned.
Table 7 shows what happens if we ablate these. When the number of message passing iterations, K, is reduced from 2 to 0, the loss consistently increases. Removing entity abstraction—meaning adding entity embeddings to node embeddings and the LSTM input embeddings—also degrades performance. This shows that DynoNet benefits from contextually-defined, structural node embeddings rather than ones based on a classic lookup table.
Model `
DynoNet (K = 2) 2.16 DynoNet (K = 1) 2.20 DynoNet (K = 0) 2.26 DynoNet - entity abstraction 2.21
Table 7: Ablations of our model on the dev set.
5 Discussion
There has been a recent surge of interest in endto-end task-oriented dialogue systems. Unfortunately, the progress has been limited by the size of available datasets (Serban et al., 2015a). Most work uses a small corpus (< 5K dialogues) through Wizard-of-Oz data collection (Williams et al., 2016; Asri et al., 2016) or simulators (Bordes and Weston, 2017; Li et al., 2016d), which
8
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
mainly focuses on information-query tasks. Current strategic dialogue datasets include Settlers of Catan (Afantenos et al., 2012) (2K turns) and the cards corpus (Potts, 2012) (1.3K dialogues), though neither has offered an end-to-end dialogue system.
Most task-oriented dialogue systems follow the POMDP-based approach (Young et al., 2013). Despite their success (Wen et al., 2017; Dhingra et al., 2016), the requirement for handcrafted slots limits their scalability to new domains and burdens data collection with extra state labeling. To break this limit, Bordes and Weston (2017) propose a Memory-Networks-based approach without domain-specific features. However, the memory is unstructured and interfacing with KBs relies on API calls, whereas our model embeds both the dialogue history and the KB structurally. Williams and Zweig (2016) use an LSTM to automatically infer the dialogue state, but as they focus on dialogue control rather than the full prob-
lem, the LSTM input contains only recognized entities, which restricts the representational power for richer utterances. Our network architecture is most similar to EntNet (Henaff et al., 2017), where memories are also updated by input sentences recurrently. The main difference is that our model allows information to be propagated between structured entities, which is shown to be crucial in our setting (Section 4.3).
In conclusion, we believe the symmetric collaborative dialogue setting and our dataset provide unique opportunities at the interface of traditional task-oriented dialogue and open-domain chat. We also offered DynoNet as a promising means for open-ended dialogue state representation. Looking forward, our dataset facilitates the study of pragmatics and human strategies in dialogue—a good stepping stone towards learning more complex dialogues such as negotiation. It would be interesting to integrate supervised learning with game-theoretic approaches in future.
9
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
This paper proposes a method for building dialogue agents involved in a symmetric collaborative task, in which the agents need to strategically communicate to achieve a common goal.    I do like this paper.  I am very interested in how much data-driven techniques can be used for dialogue management.  However, I am concerned that the approach that this paper proposes, is actually not specific to symmetric collaborative tasks, but to tasks that can be represented as graph operations, such as finding an intersection between objects that the two people know about.  In Section 2.1, the authors introduce symmetric collaborative dialogue setting.  However, such dialogs have been studied before, such as Clark and Wilkes-Gibbs explored (Cognition '86), and Walker's furniture layout task (Journal of Artificial Research '00).  On line 229, the authors say that this domain is too rich for slot-value semantics.  However, their domain is based on attribute value pairs, so their domain could use a semantics represenation based on attribute value-pairs, such as first order logic.  Section 3.2 is hard to follow.        The authors often refer to Figure 2, but I didn't find this example that helpful.        For example, for section 3.1, at what point of the dialogue does this represent?  Is this the same after `anyone went to columbia?'