Augmenting Non-Collaborative Dialog Systems with Explicit Semantic and Strategic Dialog History
Authors: Yiheng Zhou
Yulia Tsvetkov
Alan W Black
Zhou Yu
Venue:  (2020)
Keywords: dialog systems
history tracking

Abstract: We study non-collaborative dialogs, where two agents have a conflict of interest but must strategically communicate to reach an agreement (e.g., negotiation). This setting poses new challenges for modeling dialog history because the dialog's outcome relies not only on the semantic intent, but also on tactics that convey the intent.  We propose to model both semantic and tactic history using finite state transducers (FSTs). Unlike RNN, FSTs can explicitly represent dialog history through all the states traversed, facilitating interpretability of dialog structure. We train FSTs on a set of strategies and tactics used in negotiation dialogs. The trained FSTs show plausible tactic structure and can be generalized to other non-collaborative domains (e.g., persuasion). We evaluate the FSTs by incorporating them in an automated negotiating system that attempts to sell products and a persuasion system that persuades people to donate to a charity. Experiments show that explicitly modeling both semantic and tactic history is an effective way to improve both dialog policy planning and generation performance. 

AUGMENTING NON-COLLABORATIVE DIALOG SYs- TEMS WITH EXPLICIT SEMANTIC AND STRATEGIC DI-
ALOG HISTORY
Yiheng Zhou ? Yulia Tsvetkov Alan W Black Zhou Yu
Language Technologies Institute, Carnegie Mellon University Computer Science Department, University of California, Davis
(yihengz1, awb, ytsvetko)@ccs cww.cmmwweee.. edu, joyueucdavis.
ABSTRACT
We study non-collaborative dialogs, where two agents have conflict of inter- est but must strategically communicate to reach an agreement (e.g., negotiation). This setting poses challenges for modeling dialog history because the dia- log's outcome relies not only on the semantic intent, but also on tacties that con- vey the intent. We propose to model both semantic and tactic history using finite state transducers (FSTs). Unlike RNN, FSTs can explicitly represent dialog his- tory through all the states traversed, facilitating interpretability of dialog structure. We train FSTs on a set of strategies and tactics used in negotiation dialogs. The trained FSTs show plausible tactic structure and be generalized other non- collaborative domains (e.g.. persuasion). We evaluate the FSTs by incorporating them an automated negotiating system that attempts sell products and a per- suasion system that persuades people to donate to charity. Experiments show that explicitly modeling both semantic and tactic history is an effective way improve both dialog policy planning and generation performance.
INTRODUCTION
In collaborative dialog settings, agents work together and communicate to reach common goal (He et al., (017). such as booking flight and making restaurant reservation. Historically, in collab- orative setting, the dialog history and structure is modeled explicitly by tracking semantic content, for example, the set of used slot-value pairs (Bowden et al., 2017 Larionov et al. 2018 Zeigler & Mazor 1995a b). Prior work also models dialog history implicitly by using encoder-decoder model (Sordoni et al. 2015 Shang et al.) 2015) Vinyals Le 2015 Li et al. 2016 Wen et al,, 2013 Yao al. 2013). Although these techniques show promising results in col collaborative setting, they have drawbacks when applied to non-collaborative settings, where agents have competing in- terests and goals but aim reach an agreement, and they various strategies and tactics reach an agreement favorable to them. In non-collaborative dialog settings, leveraging effective sequences of tactics is important controlling for semantic content, and different tactic sequences lead to different outcomes (Zhou et al. 2019).
Learning latent dialog structure efficiently is challenging for dialog systems. Prior work mainly focused on applying hidden Markov models (HMMs) to capture contextual dependencies within dialogs (Chotimongkol 2008 Ritter et al., 2010: Zhai & Williams) 2014). Recently, [Shi et al. (219)) proposed to use discrete variational recurrent neural network (D-VRNN) for learning latent dialog structure because of its flexibility and nonlinear nature. In this paper, we take different approach by using pre-trained FSTs to learn latent dialog structure. FSTs have been used in many traditional dialog systems and have proven to be effective across different domains (Larionov et al. 2018 Zeigler & Mazor 1995a inter alia).
We focus on modeling dialog in non-collaborative settings, and propose to explicitly leverage the dialog structure, including history of tactics and dialog acts, to improve dialog planning and gener- ation. Specifically, we use weighted ESTs to learn dialog acts and tactics history and then integrate the learned FSTs encoder-decoder pipeline make the end-to-end system capture semantic and

---

tactic history. FSTs have several advantages a traditional recurrent neural network. First, an FST can explicitly track the entire path it traversed, which gives additional symbolic constraints and information about the dialog history. Due to the more informative history representation, has a better prediction of the next step (dialog act/strategy) compared to an RNN, as we empirically confirm. A trained FST serves as scaffold for dialog history tracking. Second, FST is more inter- pretable, as each state is explicitly represented by an action distribution. It is thus easier for humans interpret model decision.
FST
To leverage pre-trained FSTs, we propose an FST-enhanced hierarchical encoder-decoder model (FeHED). Our model, depicted in Figure II consists of natural language understanding (NLU) module, two pre-trained FSTs, and natural language generation (NLG) module. The NLU mod- ule has set of classifiers, where each one responsible for detecting a dialog act or a negotia- tion/persuasion strategy/tactics from a given utterance. FST's model a latent dialog structure, which can encode dialog history. One FST trained on sequences of dialog acts (FST-DA) and the other FST is trained sequences of strategies (FST-S). The NLG module is hierarchical encoder- decoder model (HED), which conditions on the outputs from FST-(DA, S} and previous utterances to predict strategies and generate system response.
We focus on (1) a bargaining scenario where a seller negotiates with a buyer over a given product through chat interface online (He et al. 2018). and (2) persuasion dialog setting where per- suader, in an online chat, attempts to persuade the persuadee to donate their earnings to a charity (Wang al. 2019). We propose automated agent that plays the role of the seller/persuader. Existing work only focuses on dialog acts, such as "disagree", which capture shallow semantics. However, these dialog acts cannot capture the pragmatics of the dialog acts. For example, whether the user disagrees politely or rudely impacts the dialog system's 's behavior. To capture pragmatic content, we employ negotiation strategies and tactics introduced by Zhou et al. (2019), motivated by negotiation literature. For persuasion dialog setting, we adopt set of persuasion strategies from Wang et al. (201)). Besides pragmatics, these strategies also capture nomain-specifii semantics that dialog acts do not cover.
We evaluate our seller/persuader models using standard measures, BLEU (Papineni et al. 2002 and accuracy of predicting strategies. Additionally, we propose unigram and bigram accuracy of strate- gies to evaluate dialog models fairly. Experiment results show that FeHED significantly outperforms all the baseline models four of the five metrics. Moreover, quantitative analysis shows that it is important to model both semantic and tactic history. Finally, qualitative analysis demonstrates that FSTs can track tactic history better than RNN in non-collaborative settings.
MODEL
Figure I giiees an overview of FeHED. There are four components in FeHED; dialog act classifier, a strategy classifier, two finite state transducers (FST-DA/S), and a hierarchical encoder-decoder model (HED). The four components are connected. The output of the dialog act classifier and strategy classifier the input of the FSTs The FSTs' output is the input for HED along with utterance embedding. Finally, HED generates both the next strategy and the next utterance.
Dialog Act Classifier converts utterances, denoted by u1, u2. uy into sequence of dialog acts da,, daz..., da:
Strategy Classifier converts utterances into sequence of strategies and tactics st1, st2, ..., sta used in each utterance.
EST-DA/S takes a sequence of dialog acts da,, daz, ..., da, or strategies st,,st,, ..., st, (green da/st da/st da/st
dotted lines in Figure D and returns a sequence of state embeddings 81 ,82 "... 8t
da/st (indicated by blue dotted lines) and un, u2, Uy to predict a set of possible strategies st/41 in the next utterance and generate the response ue+1-
HED conditions on 81 dafst da/st 8t
Sy
We describe each component next.
2

---

Dialog Act Classifier
Stralegy Classifier
U1
U/-2 u Ut
FST-DA
8/
FST-S
de
da
start
HED
Strategy Predictor
Utterance
U1g
Encoder
Dialog Encoder
kg
S
Utterance Decoder
U1+11
Figure FST-enhanced hierarchical encoder-decoder (FeHED). FeHED first takes dialog his- tory U1, .2.. Ue and feeds it to dialog act and strategy classifiers. Dialog act/strategy classi- fiers then output sequence of dialog acts daj, dd,,d,,,.. da, or strategies st1, st2,.. st,, which, in turn, fed to FSTs (green dotted lines). FSTs then output sequence of state embedding da/st da/et. da/st $1 52 St. to the hierarchical encoder-decoder (HED; blue dotted lines). Lastly, HED generates the system response u,+1 and predicts the next strategies st/-1- The red dotted line indi- cates a posterior constraint. + represents concatenation.
2.1 DIALOG ACT CLASSIFER
We follow the setting in He et al. (2018) and define list of seven dialog acts, including introduction, iniriate-price, insist on price, agree, disagree, inform and inquire. He et al. (2018) detect these dialog acts with set of handcrafted regular expressions. Details about dialog acts are given in Appendix A.I
2.2 STRATEGY CLASSIFIERS
We use fifteen negotiation tacties, proposed by Zhou et (2019). operationalizing strategies and tactics described in economics and behavioral science research on negotiation (Pruiti 1981; Baz- erman et al. 2000 Fisher & Ury 1981 Lax Sebenius, 2006 Thompson et al. (2110). These include thetoric strategies, e.g., talk informally, use certainty words, and behavioral strategies, e.g., build rapport, address buyer's 's concerns. Part of these strategies are implemented using regular expressions, for example, "please" is a salient word for communicate politely. Other strategies are implemented using linear classifiers, trained on negotiation dialogs. Details about negotiation strate- gies given in Appendix A.2
We adopt set of persuasion strategies, developed by Wang et al. (2019), based on Elaboration Likelihood Model (ELM) theory from social psychology (Petty & Cacioppo 1986). Persuasion strategies include persuasive appeal, c.g., logical appeal. emotion appeal, and persuasive inquiry, e.g., source-related inquiry. personal-related inquiry. These strategies captured with hybrid recurrent convolutional neural network classifiers (Wang et al. 2019). Details about persuasion strategies given in Appendix A.3
2.3
FSTS FOR SEMANTIC AND STRATEGIC DIALOG HISTORY
Two FSTs were trained to learn latent dialog structure. One is trained with dialog act sequences, while the other one is trained with strategy sequences.
Training data for FSTs is sequences of dialog acts or strategies, where each sequence extracted from dialog by using dialog act/strategy classifier. We initialize FST with single ergodic node
3

---

where all edges go back to itself. We then iterate over this initial FST and split the state(s). We greedily select a state split, based on splitting on the incoming dialog act/strategy that minimizes the entropy of the two generated states. This follows the algorithm often used in node splitting in building decision trees (Breiman et al. 1984). There is no well-defined stopping criteria, therefore, hyperparameter. We show example of trained FST- DA with 3 states in Appendix A.4 By looking at incoming and outgoing edges of node, we can understand which dialog state this node represents. For example, if the incoming edge of state is "seller answering a question" and the outgoing edge is "buyer inquiring", then in this state, the buyer most likely to ask question.
need choose the number of states
The trained FST gives probability mass function (PMF) for the likelihood of transfer from the cur- rent state to each of the possible dialog acts. We use this vector of probabilities as a state embedding (&t (st (dd//s)), which can be generated for each utterance and concatenated to other utterance representa- tions, At test time, we use our dialog act or strategy classifiers to choose the predicted dialog act or strategy, and transition to the new state in the FST to get the PDF for the next set of dialog acts. The FST not only returns the current state embedding, but also the embeddings of state it traversed since the start state.
2.4 HIERARCHICAL ENCODER DEODDERDDEDDDRHHED
Let Mr
1w wh where w is the i-th word current utterance ut. We use a standard GRU (Cho et al. 2014) to encode u, into hidden state representation hy-
M GRU"(u)
We concatenate the utterance embedding with the output of FST-DA and FST-S to enrich the utter- ance embedding incorporate dialog history. 1, = [h;; st st Finally, we use another GRU to combine all utterances till current time to encode the entire dialog into hidden state h
h GRU (h1" 14,h hh.,h.,
Then we predict the utterance strategies s4441 and finally, generate system response We+11 using 1g
Strategy predictor Before generating system response, we add intermediate step to predict the set of possible strategies st,+1 in it. The output st,+1 is 15-dimensional binary-value vector, where each dimension represents whether a certain negotiation strategy occurred uz+1- We compute the probability of the j-th strategy occurring in u4+1
p(stu+15 1bbz) o (W bb))
where W and by are learned parameters. We denote the negative log likelihood of strategies LST as the loss function of this task:
LSt
Σ
log(ste+1.))
Σ
log(1 s14415),
=1
where s1/41 is the ground truth strategies.
Utterance decoder is standard GRU decoder with attention (Bahdanau et al.) 2015). The input of this decoder is the dialog hidden state hę concatenated with the predicted strategics st,+1- calculates probability distribution p over vocabulary at time j conditioning on the previous word:
D softmax(GRUde ([stet]iss h&] w)
Cross entropy loss LNLG is used for this generation task:
LNLG
Σ
log(p)tt))
{my [my
4

---

where 1/41 is the target utterance.
Finally, we combine the strategy prediction task and system utterance generation loss together. We also add posterior constraint to enforce the generated utterances and the predicted negotiation strategies align with each other:
Ejoint LNLO aLSt 3 E 1 (ste-11 $ u141)
where a, 3 are constants (both set 1.0 in experiments) and the last term is posterior constraint (the red dotted line in Figure T that has a positive value if the strategies in the generated utterance Mt+1 does contain strategies in the predicted strategies s14+1. We jointly train strategy predictor and utterance decoder using Ljoint-
3 EXPERIMENTS
Datasets We evaluate our model's performance on two non-collaborative dialog data sets, CraigslistBargain (He et al. 2018) and Persuasion For Good (Wang et al., 2219). CraigslistBar- gain consists dialogs two people buying and selling products. The negotiation scenarios are crawled from cwweeraalllii list com, which includes product description, an optional product pho- tos, and its listing price. The buyer is given a private target price which strictly lower than the listing price. The data collected Amazon Mechanical Turk (AMT) platform with Turkers role-playing with each other. The seller aims to obtain as much profit as possible while the buyer tries to purchase the product with price close the private target price. Both parties encour- aged to reach an agreement. There are in total 5,383 dialogs for training, 643 for validation and 656 for testing. The average conversation length is 9.2 turns. The vocabulary size of the data is 13,928.
Persuasion For Good dataset is also collected on AMT, where two workers were randomly assigned the roles of persuader and persuadee. The goal of the persuader is to persuade the persuadee to donate his/her task carning to charity, Save the Children. There are 1,017 dialogs, where 300 are annotated with persuasion strategies. We split the dataset into 180 training dialogs, 60 for validation and 60 for test. The average conversation length is 10.43 turns. The vocabulary size is 8, 8,141.
Experimental setup
train each model for 20 epochs and choose the one that performs best on validation dataset. We use mini-batch of 20 and learning rate of 5e for encoders and 5e for utterance decoder. The encoders and decoder are GRUs, each has two layers and a hidden state size of 300.
We compare FcHED to a list of baselines and present their results in Table I
HED: vanilla HED that does not consider dialog act nor strategy.
FeHED + CF: We replace the indicator in Ljoint with cross-entropy loss.
FeHED-as SP: To test the importance of modeling strategies alone, we remove everything that
involves strategies, specifically, strategy prediction, tracking and decoding.
FeHED FSTs:: To test the importance of incorporating semantic and strategic history, we remove both FST-DA and FST-S from FeHED.
FeHED-EST--/DA: To test which type of history is more important, semantic or tactic, we remove either FST-S FST-DA from FeHED.
HED+RNN: We compare our approach with He et al. 2018 's method, by replacing FST in FeHED with RNN encoding tactic sequence.
Sequicity: Lei et al. 2018)) use belief
splin span to model dialog state and improve system performance. However, Sequicity cannot be directly applied to problem. For a fair comparison, replace
Lei al. (2018)'s 's values in a belief span with dialog acts and strategies.
Evaluation We evaluate FeHED's performance (1) on the ability of generating high quality sponses, and (2) on whether the responses carry the correct strategy. We also explore the effective- ness of history tracking by performing ablation study. Lastly, we conduct human evaluation to test the dialog system's persuasiveness, coherence and naturalness.
To evaluate FeHED's responses four types of metrics:

---

Strategy predictor's F1 and accuracy (S.F1 and S.acc). We evaluate strategy prediction perfor- mance along with response generation quality, to assess strategy tracking. However, not every model in Table[]can output strategy. For these models. replace their utterance decoder with strategy predictor and retrain the model by optimizing LST- We evaluate the retrained model by measuring its F1 score and accuracy.
We use BLEU to evaluate generation quality. Although in other generation tasks BLEU is standard measure, in dialog modeling is a reliable metric, as different sentences can convey the same content in different ways.
Utterance decoder's accuracy of generated strategies (Uni.acc, Biaacc). We first apply our strategy classifier to extract strategies in generated utterance. Then, the extracted strategies are compared with ground truth to calculate strategies can be appropriate given the same dialog history. Therefore, we expand the ground truth strategy set by sampling dialogs with similar dialog history (previous two turns). We use the expanded ground truth set to calculate bigram accuracy (Bi.acc).
accuracy (Uni.acc). Due to the nature of dialogs, multiple
Human evaluation!! We also conducted two types of human evaluation for the negotiation task: (1) third-person rating: (2) second-peree periddo-pooon rating. For perrd-peroon rating, randomly give each participant four different types dialogs and ask him/her to rate each dialog's 's seller terms of persuasiveness, coherence, and naturalness (on a scale of to 5). These dialogs have FeHED, FeHED-FST-DA, FeHED-FST-S or HED to play the role of seller. For second-person rating, we ask participants to conduct four conversations by playing the role of buyer negotiate with FeHED, FcHED-FST-D FeHED-FST: and HED, respectively. Then, we ask them to com- pare and rate each model in terms of persuasiveness, coherence, and naturalness (on scale of to 5).
3.1
RESULTS
Negotiation Bi.acc
Persuasion
Models
Uni.ace
S.ace
S.FI
BLEU
Uni.acc
Bí.ace
S.ace
S.F1
BLEU
FeHED
49.6
59.3
61.9
22.8
20.6
0.18
0.77
18.2
13.5
FeHED+CE
50.3
59.6
60.4
21.5
20.7
0.18
0.78
0.79
18.2
13.7
-FSTs
42.3
55.1
42.4
19.5
20.5
0.13
0.70
0.80
15.6
13.6
-FST-S
43.1
54.3
46.7
20.2
20.9
0.12
0.70
0.75
17.4
13.8
-FST-DA
42.8
54.9
49.2
20.8
20.3
0.10
0.70
16.8
14.0
SSP
46.5
56.3
47.3
20.4
20.5
0.15
0.67
0.78
18.0
13.9
HED+RNN
46.5
56.8
57.2
15.5
20.3
0.16
0.75
0.77
17.9
13.6
Sequicity
44.0
57.9
16.2
HED
36.9
51.2
38.4
15.6
20.8
0.12
0.66
0.77
15.8
14.1
Table I: Ablation and baseline results. FeHED achieves the best performance on all metrics except BLEU, Moreover, removing any component results a significant decrease in performance.
Table shows the result of negotiation and persuasion dialogs. FeHED achieves the best perfor- mance on all metrics except BLEU. However, single-reference BLEU assumes only one possible system response while dialog system can have multiple valid responses. Comparing with vanilla HED model, FeHED improves S.ace by +23.5, S.FI by +7.2, Uni.ace by +12.7 and Bi.acc by +8.1, while maintaining comparable BLEU score. This suggests that incorporating semantic and tactic in- formation leads to a better dialog system. We also evaluate model performance when ablating one or more model components. Result shows that removing any FST causes worse performance, which suggests modeling both semantic and strategic history is necessary. Moreover, the HED+RNN setup confirms that FST's better model semantic and tactic history than RNNs in non-collaborative settings. Noticeably, all models' S.FI are low, which may be due to the fact that the negotiation strategy set large and some of them have low frequency training data, therefore causing overall low per- formance. We also observe that S.ace is higher than Uni.ccc for all the models. This is expected, because predicting negotiation strategies more straightforward than generating system utterances with the correct negotiation strategies. Although Sequicity has very high Uni.ace and Bi.acc, it has much lower BLEU score compared all the other models except FeHED. is likely because
'The study was approved by the IRB.

---

Sequicity CopyNet (Gu et al. 2016). which is not designed for non-collaborative dialogs but rather collaborative tasks (e.g. booking a restaurant). Negotiation and persuasion tasks yield similar results, confirming that the benefit of using FSTs to model both semantic and strategic history is not limited to single domain.
Second-person Rating
Third-per person Rating
Sale Price
Sale Price
Models
Persuasive
Coherent
Natural
Persuasive
Coherent
Natural
FeHED
2.6
2.8
3.0
0.84
3.2
3.9
3.5
0.68
FST-DA
2.5
2.4
0.70
3.5
0.64
FST-S
2.0
2.4
2.4
0.64
2.9
3.4
3.3
0.59
HED+RNN
2.3
2.5
2.6
0.49
2.8
3,8
3,6
0.44
HED
1.8
1.9
1.9
0.62
2.9
3,4
3.1
0.50
Table 2: Human evaluation ratings for (on a scale from to 5) for FeHED, FeHED -FSTDA, FeHED-FSTS and HED. We conducted third-person rating and second-person rating. Sale price is normalized.
Table 2 shows the results of human evaluation. For third-person rating, we asked an expert to generate 20 dialogs by negotiating with FeHED, FeHED-FST-DA FedHED-S, HED+RNN and HED respectively (5 dialogs each). We then recruited 50 people on AMT to rate these generated dialogs. Result shows that FeHED is more persuasive, coherent and natural than all the baselines. For second-person rating, we asked 50 participants on AMT to play the role of buyer to negotiate with FeHED, that FeHED outperforms RNN and other models on all the metrics except naturalness. It is likely because RNN is trained jointly with HED, but it not good at explicitly tracking and preserving the history. Although FST is learned separately, it forces the model to learn the history through list of traversed states. We analyze the generated dialogs for human evaluation and find that baselines are more likely to accept unfair offers and apply inappropriate strategies.
HED RNNN and HED respectively. Results show
Listing Price:
Buyer's Target Price: 36
Title: 2017 NEW Stans 24 and 26 Tubeless Tire Kit
Product Description: "I have NEW Stan's Tubeless tire Conversion kit for sale for 24 AND 26 wheels/tires. Pick up Walnut Creek, CA evenings"
Seller (FeHED): S Buyer (Human): B
Seller (HED): S Buyer (Human):
B:
Hello! Hi
B: Hello! Hello
FST:
(intro, 0.4%) (init-price, 0.19)...
B:
How old is your kit?
B: How old is your kit?
S:
only had it for months.
S: It's only year old.
FST:
(inform, 0.51), (disagree, 0.20)... ...
B: The price bit high, can you do 30?
B: The price bit high, can you do 30? can do that.
can't go that low, could go down 38.4.
FST: (propose price, 0.51), (agree. 0.1.)...
B:
How about 35?
S: <offer 30>
B: <accept>>
Seller (FeHlED): S Buyer (Human):
Seller (HED+RNN):: Buyer (Human): B
B:
Hello!
B: Hello!
S:
Hello
S: Hello
B:
How much are you looking for?
B: How much are you looking for?
I'm asking for it.
I'm asking for it.
B:
Can you do 30 dollars and can pick it up?
B: Can you do 30 dollars and can pick it up?
S:
How about 37.6 ? I will deliver to you.
S: Can you do 37.6?
FST: (negotiate side offers, 0.49)
Table 3: Examples of generated responses with and without FSTs.

---

Finally, show and example of a negotiation dialog. The first example in Table 3 shows the dialog with the bot that uses history tracking (FeHED). For the examples with FeHED, we also show top most likely dialog acts given by the current state of FSTs. As shown in bold text in the first two examples in Table 3] HED tends to agree with buyer's proposal although they have just started negotiating the price. On the other hand, FeHED adopts a more appropriate action: rejects buyer's ' proposal and gives a counter price. This is likely because FSTs give the system a state embedding, where (propose price) has the highest probability (0.51), which tells the system that in the current state, the probability of making counter price is 0.51. Besides (propose price, 0.51), other generated utterances are mostly following the top most likely dialog acts proposed by FSTs (e.g. (intro, 0.49), (inform, 0.51)).
Table shows that FST models dialog history better than RNN in non-collaborative setting. Two examples in the last row of Table 3 provide an example. Noticeably, FeHED recognizes tactics used in the previous utterance ("pick it up")) and responds "I will deliver to you"; but with RNN, the bot ignores the previous tactic history and proposes another price. Presumably, this is because FST explicitly captures tactics used in the history, while RNN does not.
4 RELATED WORK
Our work extends the line of research on non-collaborative dialog tasks, such as negotiation and persuasion. Lewis et al. (2017) demonstrated a task where collection of items are divided between two agents. Some prior work also focus on a strategic board game called Settlers of Catan where players can offer resources in exchange for others and they can also reply to offers from other players (Cuayáhuitl et al. 2015 Keizer et al.) 2017). However, these tasks do not require modeling rich communication skills, but focus on decision-making skills. Therefore, prior studies on these tasks only focus tactic history but ignore semantic content. To consider both semantic and tactic history, we choose a bargaining scenario proposed by He et al. (2018), where a seller and a buyer negotiate price over an item for sale. To show the generalizability of our work, we also choose persuasion dialog setting proposed by [Wang et al. (2019), where a persuader tries to strategically convince persuadee to donate his/her earnings to charity.
Most end-to-end approaches incorporate history through hidden states (Sordoni et al. 2015; Shang al. 20155 /Vinyals & Le| [2015] Li et al.) 2016; Wen et al., 2015 Yao et al.) (2015). Such methods only focus on capturing semantic history. Lei et al. (2018) proposed a text span called belief span for encoding dialog history. which is combined with a simple seq2seq model improve dialog gen- eration. Specifically, belief span tracks entities mentioned so far (e.g. restaurant types) to explicitly model dialog history. We utilize trained FSTs to encode dialog history instead of a text span. Addi- tionally, it requires human annotations as supervision to train a belief span, while our FSTs are fully unsupervised. Therefore, our FSTs can be applied to other domains easily.
Rule-based dialog modules incorporate history using symbolic rules. Larionov et al. (2018 8): Zeigler & Mazor (195aa b) use a finite-state automata to keep track of dialog context. Fang et al. (2018) suggests buil building& a hierarchical dialog manager that keeps track of engagement, coherence, and user experience. Bowden et al. (2017) utilizes a state graph structure to model dialog flows. He et al.) (2018) applies neural model to predict a sequence of dialog acts as dialog manager. We also utilize finite-state machine in FeHED, but it is automatically learned using unsupervised data. Moreover, use FSTs to learn the dialog structure instead of using it directly the dialog manager.
CONCLUSION
In non-collaborative dialog settings, it is important to not only track the semantic intent, but also strategies and tactics that express this intent. To improve non-collaborative dialog planning and generation, we propose to explicitly model both semantic and tactic history by using automatically trained FSTs We then evaluate the trained FSTs on negotiation dialog system and a persuasion dialog system. Result shows that explicitly modeling both semantic and tactic history achieves the best performance. We have also shown that FST models tactic history better than RNN in non- collaborative dialog settings
All sources and data will be publicly released.
8

---

REFERENCES
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In Proc. ICLR, 2015.
Max H. Bazerman, Jared Curhan, Don Moore, and Kathleen Valley. Negotiation. Annual review of psychology, 51(1):279-3144 2000.
K. K. Bowden, S. Oraby, J. Wu, A. Misra, and M. Walker. Combining search with structured data to create a more engaging user experience in open domain dialogue. In Proc. SCAI, 2017.
Breiman, Friedman, R. Olshen, and Stone. Classification and Regression Trees. Wadsworth & Brooks, Pacific Grove, CA., 1984.
K. Cho, B. van Merrienboer, D. Bahdanau, and Y. Bengio. On the properties of neural machine translation: Encoder-decoder approaches. In arXiv preprint arXiv:1409. 1259, 2014.
Ananlada Chotimongkol. Learning the structure of task-oriented conversations from the corpus of in domain dialogs. In Ph.D. thesis, Carnegie Mellon University, Language Technologies Institute, School of Computer Science, 2008.
Heriberto Cuayáhuitl, Simon Keizer, and Oliver Lemon. Strategic dialogue management via deep reinforcement learning. In NIPS Workshop on Deep Reinforcement Learning, 2015.
Hao Fang, Hao Cheng, Maarten Sap, Elizabeth Clark, Ari Holtzman, Yejin Choi, Noah A. Smith, and Mari Ostendorf. Sounding board: A user-centric and content-driven social chatbot. In Proc. NAACL, 2018.
Roger Fisher and William Ury. Getting to Yes: Negotiating Agreement Without Giving In. Boston, MA: Houghton Mifflin Company, 1981.
Jiatao Gu, Zhengdong Lu, Hang Li, and Victor OK Li. Incorporating copying mechanism in sequence-to--sequece learning. Proc. ACL, 2016.
He He, Anusha Balakrishnan, Mihail Eric, and Percy Liang. Learning symmetric collaborative dialogue agents with dynamic knowledge graph embeddings. In Proc. ACL, 2017.
He He, Derek Chen, Anusha Balakrishnan, and Percy Liang. Decoupling strategy and generation in negotiation dialogues. EMNLP, 2018.
Simon Keizer, Markus Guhe, Heriberto Cuayáhuitl, Ioannis Efstathiou, Klaus- Peterr Engelbrecht, Mihai Dobre, Alex Lascarides, and Oliver Lemon. Evaluating persuasion strategies and deep reinforcement learning methods for negotiation dialogue agents. In Proc. EACI, 2017.
George Larionov, Zachary Kaden, Hima Varsha Dureddy, Gabriel Bayomi T. Kalejaiye, Mihir Kale, Srividya Pranavi Potharaju, Ankit Parag Shah, and Alexander Rudnicky. Tartan: retrieval- based social bot powered by dynamic finite-state machine architecture. In arXiv: 181200160, 2018.
David Lax and James Sebenius. 3-D Negotiation: Powerful tools change the game your most important deals. Harvard Business Press, 2006.
Wenqiang Lei, Xisen Jin, Zhaochun Ren, Xiangnan He, Min-Yen Kan, and Dawei Yin. Sequicity: Simplifying task-oriented dialogue systems with single seuuence-to-eqqeeee architectures. In Proc. ACL, 2018
Mike Lewis, Denis Yarats, Yann Dauphin, Devi Parikh, and Dhruv Batra. Deal or deal? end-to- end learning of negotiation dialogues. In Proc. EMNLP, pp. 2443-2453, 2017.
Jiwei Li, Michel Galley, Chris Brockett, Georgios Spithourakis, Jianfeng Gao, and Bill Dolan. A persona-based neural conversation model. In Proc Association for Computational Linguistics (ACL), 2016.
Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. BLEU: a method for automatic evaluation of machine translation. In Proc. ACI., pp. 311-318, 2002.

---

Richard E Petty and John T Cacioppo. The elaboration likelihood model of persuasion. In Commu- nication and persuasion, pp. 1-24. Springer, 1986.
Dean G. Pruitt. Negotiation behavior. New York: Academic Press, 1981.
Alan Ritter, Colin Cherry, and Bill Dolan. Unsupervised modeling of twitter conversations. In Proc.
NAACL, 2010.
Lifeng Shang. Zhengdong Lu, and Hang Li. Neural responding machine for short-text conversation. In Proceedings ACL, 2015.
Weiyan Shi, Tiancheng Zhao, and Zhou Yu. Unsupervised dialog structure learning. In Proc. NAACL, 2019.
Alessandro Sordoni, Michel Galley, Michael Auli, Chris Brockett, Yangfeng Ji, Meg Mitchell, Jian- Yum Nie, Jianfeng Gao, and Bill Dolan. neural network approach sentext-sensitvee generation of conversational responses. In Proc. NAACL-HLT, 2015.
Leigh L Thompson, Jiunwen Wang, and Brian C Gunia. Negotiation. Annual review of psychology, 61:491-515, 2010.
Oriol Vinyals and Quoc Le. A neural conversational model. Proc. ICML. Deep Learning Work- shop, 2015.
Xuewei Wang, Weiyan Shi, Richard Kim, Yoojung Oh, Sijia Yang, Jingwen Zhang, and Zhou Yu. Persuasion for good: Towards personalized persuasive dialogue system for social good. In Proc. ACL, 2019.
Tsung-Hsien Hsien Wen, Milica Gasic, Nikola Mrksic, Pei-Hao Su, David Vandyke, and Steve Young. A diversity-promotte objective function for neural conversation models. In Proc. EMNLP, 2015.
Kaisheng Yao, Geoffrey Zweig, and Baolin Peng. Attention with intention for neural network con- versation model. In NIPS workshop on Machine Learning for Spoken Language Understanding and Interaction., 2015.
Zeigler and B. Mazor Dialog design for speech-interactive automation system. In Proc. EU- ROSPEECH, 1995a.
B Zeigler and B. Mazor. A formal technique for automated dialogue development. In Proc. DIS, 1995b.
Ke Zhai and Jason D Williams. Discovering latent structure in task-oriented dialogues. In Proc. ACI, 2014.
Yiheng Zhou, He He, Alan W Black, and Yulia Tsvetkov. A dynamic strategy coach for effective negotiation. In Proc. SigDial, 2019.
A
APPENDIX
A.1
DIALOG ACTS
Mcaning
Dialog Act
Example
Detector
Greetings
(intro)
"Hello there!"
rule
Propose the price
(init-price) (insist) (agree)
"Can you do dollars?"
rule
Insists an offer
"I can't 't lower than 30 dollars." " "OR, you have deal."
rule
Agree with the current proposal
rule
Disagree
current proposal
(disagree)
"sorry
go that low."
rule
Answer buyer's question
(inform)
"This bike is brand new."
rule
Ask question
(inquire)
"Which color do you prefer?"
rule
Table A list of dialog acts from
HH al.
2018
10

---

A.2 NEGOTIATION STRATEGIES
Negotiation
Action
Example
Detector
Strategy
Describe product)
"The car has leather seats." "45k miles" "less than 50k miles"
classifier
Focus interests, not positions
Rephrase product)
classifier
Embellish product)
"a luxury car with attractive leather seats"
classifier
(Address concerns)
"I' ve just luken it to maintuinence."
classifier
(Communicate interests)
"I'd like sell it asap."
classifier
(Propose price)
"How about $9k?"
classifier
Invent options for mutual gain
(Do not propose first) (Negotiate side offers) (Hedge)
n/a
rule
can deliver it for you"
rulc
"I could come down a bit."
rule
(Communicate politely)
greetings, gratitude, apology, "please"
rule
Build trust
Build rapport)
MMy kid really liked this bike, but he outgrew it."
rule
(Tal informally)
"Absolutely, ask away!"
rule
Show dominance)
"The absolute highest I can 640.0."
rule
Insist your position
Negative sentiment)
"Sadly simply cannot go under 500 dollars."
rule
(Certainty words)
"It has always had screen protector"
rule
Table 5: A list of negotiation strategies from Zhou et al. (2019).
A.3 PERSUASION STRATEGIES
Persuasion Strategy
Action
Example
Detector
Logical appcal Emotion appeal
(Use reasoning)
"This donation will make an impact for children."
classifier
(Elicit specific emotions)
"Millions of children are facing violence."
classifier
Credibility appeal
(Ctte organizational impacts)
"This charity has program called sponsor child."
classifier
Foot-in-the-dor
(Start with small donation)
"How about we donate 0.2 each first ?" "I want to donate some amount from this survey." "I donated I dollar this charity before."
classifier
Self-modeling
(Make donation myself)
classifier
Personal story
(Tell personal donation story)
classifier
Donation information
Give information donation)
"Research team will send money to this charity." "Have you heard of Save the Children before? ?" "Are you interested in donating some money? ?"
classifier
Source-related inquiry
(Ask about the charity)
classifier
Task-related inquiry
Ask opinion of donation)
classifier
Personal related inquiry
(Ask personal experience)
"Have you ever donated to any churity before?"
classifier
Table 6: A set of persuasion strategies from Wang et al. 2019
A.4
DIALOG STATES EST EXAMPLE

---

seller:
veler: intro
Start
seller:
buyer: inquiry
buyar: intro
Figure 2: An example of FST-DA with three states, For each edge, only show the top frequent
dialog acts for better visualization.
12


Reviews:
[{"review_id": "Sye3Ss8Q5B", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This is an interesting paper about use of Finite State Transducers to model semantic and tactic history in dialogues. This can be fruitful in settings where negotiation settings.\n\nI have some basic questions.\n\nWhy not a direct comparison with the models proposed by Wang et al., 2019, He et al., 2019?\n\nWhy is human evaluation performed only w.r.t. HED and its variant but not Sequicity?\n\n How do you come up with number 37.6 in negotiation dialogue?\n\nI think, there is a long way to go to solve the considered dialogue modeling problem. I like the application of FSTs for the problem. Why not compare w.r.t. HMMs as you mention it as a choice in the intro?\n\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BygDgZA3KB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposed a framework for non-collaborative dialog systems. To track the history better, the authors propose to apply two pre-trained finite state transducers (FSTs) to take the sequence of dialog acts or strategies as inputs and output sequences of state embeddings for the hierarchical encoder-decoder (HED) part as inputs. The authors test their model on two tasks, a bargain task and a persuasion task.\n\nThe model that the authors prepose makes sense to me. It seems that the FSTs can successfully help the model to track the history better and propose useful state embeddings for the rest part of the model, on both dialog acts and strategies. Also, the authors have done a comprehensive empirical study to show the gain of the proposed techniques over the pure HED model and some baseline method. So I think this is a good work. But potentially it would be better if the authors can show more insights and details for the FSTs. \n\nSome detailed comments:\n\n1. The example dialogs in Table 3 show us that the FSTs can output dialog act distributions that can help the agent behave better compared to the case with an RNN for tracking the history, and the case without FST/RNN. This shows the success of the FST framework.\n\n2. The authors have done a comprehensive comparison for the cases with / without the two FSTs, as well as the case without the strategy predictor. Also, the authors compared with another existing method (Sequicity). The proposed method performs well compared to the baseline methods, on both general performances and the two types of human-evaluations. This shows the good empirical performance of the proposed method.\n\n3. This paper can be better if the authors can provide more insights and details for the FSTs. For example, why FST is better than RNN? The authors mentioned something about that, but it is not clear enough and it will be great if the authors can provide more discussions on this. In addition, the output alphabets and the sets of states are not clear for the FSTs, it will be better if the authors show the full details for the FSTs, as in my opinion this is the major contribution of this work.\n\n4. A minor comment: There are some inaccurate expressions in this paper. For example, the authors mentioned that the FSTs about put probabilistic density functions. However, to my understanding, the set of dialog acts is finite, hence FSTs output probabilistic mass functions, not probabilistic density functions. Please proofread about that.\n\nQuestion:\n\n1. Can you explain more about the choice for the parameters? For example, why the possible strategy output is a 15-dimensional binary-value vector?\n\n2. For the loss L_{joint}, shouldn't it be (st_{t+1,j}\\not\\in u_{t+1}) in the indicator function?\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A"}, "extra_text": {}}, {"review_id": "B1xaAx7AKH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work presents two FST models to explicitly incorporate semantic and strategic/tactic information into dialog systems. Experiments on two datasets from prior work show the advantage of this model. \n\nGiven the writing of this paper, I am not sure I understand the novelty of this work on the modeling side. Particularly, section 2.3 is too brief to provide enough technical details so readers can understand how exactly the two FST models work and why they are effective in encoding semantic and strategic information. With the important details being left out, it is difficult to evaluate the novelty of this work. \n\nIn addition, although the evaluation in section 3 shows the proposed model outperforms some existing competitive systems. The experiment setup is questionable:\n\n- Both competitive systems (He et al., 2018) and (Lei et al., 2018) are not exactly the same as proposed in these two works. To make a fair comparison, I strongly suggest running the systems released from their works\n- The evaluation measurements used in the human evaluation is not directly comparable to prior work, which makes it further unclear about the performance of the proposed model. \n\n\nSome additional comments on details\n\n- In the paragraph before section 2.4, I think \"probability density function\" should be \"probability distribution\", since the random variables are discrete.\n- In the joint loss function (the equation before section 3), why use an indicator function instead of the cross-entropy loss for the last term? \n- In experimental setup, my understanding is that the model was jointly trained with all components. Why there are two separate learning rates?\n- In evaluation, what are the exact definitions of Uni.acc and Bi.acc? I read this paragraph multiple times, and I am still not sure whether I understand it correctly. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes use of two pre-trained FST models to explicitly incorporate semantic and strategic/tactic information from dialog history into non-collaborative (negotiation) dialog systems. Experiments on two datasets from prior work show the advantage of this model in automated and human evaluation. While all reviewers found the work interesting, they made many suggestions regarding the presentation. Author'(s) rebuttal included explanations and changes to the presentation. Hence, I suggest acceptance as a poster presentation.
Decision: Accept (Poster)