Addressee and Response Selection in Multi-Party Conversations with Speaker Interaction RNNs

Abstract: In this paper, we study the problem of addressee and response selection in multi-party conversations. Understanding multi-party conversations is challenging because of complex speaker interactions: multiple speakers exchange messages with each other, playing different roles (sender, addressee, observer), and these roles vary across turns. To tackle this challenge, we propose the Speaker Interaction Recurrent Neural Network (SI-RNN). Whereas the previous state-of-the-art system updated speaker embeddings only for the sender, SI-RNN uses a novel dialog encoder to update speaker embeddings in a role-sensitive way. Additionally, unlike the previous work that selected the addressee and response separately, SI-RNN selects them jointly by viewing the task as a sequence prediction problem. Experimental results show that SI-RNN significantly improves the accuracy of addressee and response selection, particularly in complex conversations with many speakers and responses to distant messages many turns in the past.

Real-world conversations often involve more than two speakers. In the Ubuntu Internet Relay Chat channel (IRC), for example, one user can initiate a discussion about an Ubuntu-related technical issue, and many other users can work together to solve the problem. Dialogs can have complex speaker interactions: at each turn, users play one of three roles (sender, addressee, observer), and those roles vary across turns.
In this paper, we study the problem of addressee and response selection in multi-party conversations: given a responding speaker and a dialog context, the task is to select an addressee and a response from a set of candidates for the responding speaker. The task requires modeling multi-party conversations and can be directly used to build retrieval-based dialog systems BIBREF0 , BIBREF1 , BIBREF2 , BIBREF3 .
The previous state-of-the-art Dynamic-RNN model from BIBREF4 ouchi-tsuboi:2016:EMNLP2016 maintains speaker embeddings to track each speaker status, which dynamically changes across time steps. It then produces the context embedding from the speaker embeddings and selects the addressee and response based on embedding similarity. However, this model updates only the sender embedding, not the embeddings of the addressee or observers, with the corresponding utterance, and it selects the addressee and response separately. In this way, it only models who says what and fails to capture addressee information. Experimental results show that the separate selection process often produces inconsistent addressee-response pairs.
To solve these issues, we introduce the Speaker Interaction Recurrent Neural Network (SI-RNN). SI-RNN redesigns the dialog encoder by updating speaker embeddings in a role-sensitive way. Speaker embeddings are updated in different GRU-based units depending on their roles (sender, addressee, observer). Furthermore, we note that the addressee and response are mutually dependent and view the task as a joint prediction problem. Therefore, SI-RNN models the conditional probability (of addressee given the response and vice versa) and selects the addressee and response pair by maximizing the joint probability.
On a public standard benchmark data set, SI-RNN significantly improves the addressee and response selection accuracy, particularly in complex conversations with many speakers and responses to distant messages many turns in the past. Our code and data set are available online.
We follow a data-driven approach to dialog systems. BIBREF5 singh1999reinforcement, BIBREF6 henderson2008hybrid, and BIBREF7 young2013pomdp optimize the dialog policy using Reinforcement Learning or the Partially Observable Markov Decision Process framework. In addition, BIBREF8 henderson2014second propose to use a predefined ontology as a logical representation for the information exchanged in the conversation. The dialog system can be divided into different modules, such as Natural Language Understanding BIBREF9 , BIBREF10 , Dialog State Tracking BIBREF11 , BIBREF12 , and Natural Language Generation BIBREF13 . Furthermore, BIBREF14 wen2016network and BIBREF15 bordes2017learning propose end-to-end trainable goal-oriented dialog systems.
Recently, short text conversation has been popular. The system receives a short dialog context and generates a response using statistical machine translation or sequence-to-sequence networks BIBREF16 , BIBREF17 , BIBREF18 , BIBREF19 , BIBREF20 , BIBREF21 . In contrast to response generation, the retrieval-based approach uses a ranking model to select the highest scoring response from candidates BIBREF0 , BIBREF1 , BIBREF2 , BIBREF3 . However, these models are single-turn responding machines and thus still are limited to short contexts with only two speakers. As for larger context, BIBREF22 lowe2015ubuntu propose the Next Utterance Classification (NUC) task for multi-turn two-party dialogs. BIBREF4 ouchi-tsuboi:2016:EMNLP2016 extend NUC to multi-party conversations by integrating the addressee detection problem. Since the data is text based, they use only textual information to predict addressees as opposed to relying on acoustic signals or gaze information in multimodal dialog systems BIBREF23 , BIBREF24 .
Furthermore, several other papers are recently presented focusing on modeling role-specific information given the dialogue contexts BIBREF25 , BIBREF26 , BIBREF27 . For example, BIBREF25 meng2017towards combine content and temporal information to predict the utterance speaker. By contrast, our SIRNN explicitly utilizes the speaker interaction to maintain speaker embeddings and predicts the addressee and response by joint selection.
 BIBREF4 ouchi-tsuboi:2016:EMNLP2016 propose the addressee and response selection task for multi-party conversation. Given a responding speaker INLINEFORM0 and a dialog context INLINEFORM1 , the task is to select a response and an addressee. INLINEFORM2 is a list ordered by time step: INLINEFORM3 
where INLINEFORM0 says INLINEFORM1 to INLINEFORM2 at time step INLINEFORM3 , and INLINEFORM4 is the total number of time steps before the response and addressee selection. The set of speakers appearing in INLINEFORM5 is denoted INLINEFORM6 . As for the output, the addressee is selected from INLINEFORM7 , and the response is selected from a set of candidates INLINEFORM8 . Here, INLINEFORM9 contains the ground-truth response and one or more false responses. We provide some examples in Table TABREF30 (Section SECREF6 ).
In this section, we briefly review the state-of-the-art Dynamic-RNN model BIBREF4 , which our proposed model is based on. Dynamic-RNN solves the task in two phases: 1) the dialog encoder maintains a set of speaker embeddings to track each speaker status, which dynamically changes with time step INLINEFORM0 ; 2) then Dynamic-RNN produces the context embedding from the speaker embeddings and selects the addressee and response based on embedding similarity among context, speaker, and utterance.
Figure FIGREF4 (Left) illustrates the dialog encoder in Dynamic-RNN on an example context. In this example, INLINEFORM0 says INLINEFORM1 to INLINEFORM2 , then INLINEFORM3 says INLINEFORM4 to INLINEFORM5 , and finally INLINEFORM6 says INLINEFORM7 to INLINEFORM8 . The context INLINEFORM9 will be: DISPLAYFORM0 
with the set of speakers INLINEFORM0 .
For a speaker INLINEFORM0 , the bold letter INLINEFORM1 denotes its embedding at time step INLINEFORM2 . Speaker embeddings are initialized as zero vectors and updated recurrently as hidden states of GRUs BIBREF28 , BIBREF29 . Specifically, for each time step INLINEFORM3 with the sender INLINEFORM4 and the utterance INLINEFORM5 , the sender embedding INLINEFORM6 is updated recurrently from the utterance: INLINEFORM7 
where INLINEFORM0 is the embedding for utterance INLINEFORM1 . Other speaker embeddings are updated from INLINEFORM2 . The speaker embeddings are updated until time step INLINEFORM3 .
To summarize the whole dialog context INLINEFORM0 , the model applies element-wise max pooling over all the speaker embeddings to get the context embedding INLINEFORM1 : DISPLAYFORM0 
The probability of an addressee and a response being the ground truth is calculated based on embedding similarity. To be specific, for addressee selection, the model compares the candidate speaker INLINEFORM0 , the dialog context INLINEFORM1 , and the responding speaker INLINEFORM2 : DISPLAYFORM0 
where INLINEFORM0 is the final speaker embedding for the responding speaker INLINEFORM1 , INLINEFORM2 is the final speaker embedding for the candidate addressee INLINEFORM3 , INLINEFORM4 is the logistic sigmoid function, INLINEFORM5 is the row-wise concatenation operator, and INLINEFORM6 is a learnable parameter. Similarly, for response selection, DISPLAYFORM0 
where INLINEFORM0 is the embedding for the candidate response INLINEFORM1 , and INLINEFORM2 is a learnable parameter.
The model is trained end-to-end to minimize a joint cross-entropy loss for the addressee selection and the response selection with equal weights. At test time, the addressee and the response are separately selected to maximize the probability in Eq EQREF12 and Eq EQREF13 .
While Dynamic-RNN can track the speaker status by capturing who says what in multi-party conversation, there are still some issues. First, at each time step, only the sender embedding is updated from the utterance. Therefore, other speakers are blind to what is being said, and the model fails to capture addressee information. Second, while the addressee and response are mutually dependent, Dynamic-RNN selects them independently. Consider a case where the responding speaker is talking to two other speakers in separate conversation threads. The choice of addressee is likely to be either of the two speakers, but the choice is much less ambiguous if the correct response is given, and vice versa. Dynamic-RNN often produces inconsistent addressee-response pairs due to the separate selection. See Table TABREF30 for examples.
In contrast to Dynamic-RNN, the dialog encoder in SI-RNN updates embeddings for all the speakers besides the sender at each time step. Speaker embeddings are updated depending on their roles: the update of the sender is different from the addressee, which is different from the observers. Furthermore, the update of a speaker embedding is not only from the utterance, but also from other speakers. These are achieved by designing variations of GRUs for different roles. Finally, SI-RNN selects the addressee and response jointly by maximizing the joint probability.
[t] Dialog Encoder in SI-RNN [1] Input INLINEFORM0 : INLINEFORM1 INLINEFORM2 where INLINEFORM3 // Initialize speaker embeddings INLINEFORM4 INLINEFORM5 //Update speaker embeddings INLINEFORM6 // Update sender, addressee, observers INLINEFORM7 INLINEFORM8 INLINEFORM9 // Compute utterance embedding INLINEFORM10 INLINEFORM11 // Update sender embedding INLINEFORM12 // Update addressee embedding INLINEFORM13 // Update observer embeddings INLINEFORM14 INLINEFORM15 // Return final speaker embeddings Output INLINEFORM16 for INLINEFORM17 
To encode an utterance INLINEFORM0 of INLINEFORM1 words, we use a RNN with Gated Recurrent Units BIBREF28 , BIBREF29 : INLINEFORM2 
where INLINEFORM0 is the word embedding for INLINEFORM1 , and INLINEFORM2 is the INLINEFORM3 hidden state. INLINEFORM4 is initialized as a zero vector, and the utterance embedding is the last hidden state, i.e. INLINEFORM5 .
Figure FIGREF4 (Right) shows how SI-RNN encodes the example in Eq EQREF9 . Unlike Dynamic-RNN, SI-RNN updates all speaker embeddings in a role-sensitive manner. For example, at the first time step when INLINEFORM0 says INLINEFORM1 to INLINEFORM2 , Dynamic-RNN only updates INLINEFORM3 using INLINEFORM4 , while other speakers are updated using INLINEFORM5 . In contrast, SI-RNN updates each speaker status with different units: INLINEFORM6 updates the sender embedding INLINEFORM7 from the utterance embedding INLINEFORM8 and the addressee embedding INLINEFORM9 ; INLINEFORM10 updates the addressee embedding INLINEFORM11 from INLINEFORM12 and INLINEFORM13 ; INLINEFORM14 updates the observer embedding INLINEFORM15 from INLINEFORM16 .
Algorithm SECREF4 gives a formal definition of the dialog encoder in SI-RNN. The dialog encoder is a function that takes as input a dialog context INLINEFORM0 (lines 1-5) and returns speaker embeddings at the final time step (lines 28-30). Speaker embeddings are initialized as INLINEFORM1 -dimensional zero vectors (lines 6-9). Speaker embeddings are updated by iterating over each line in the context (lines 10-27).
In this subsection, we explain in detail how INLINEFORM0 / INLINEFORM1 / INLINEFORM2 update speaker embeddings according to their roles at each time step (Algorithm SECREF4 lines 19-26).
As shown in Figure FIGREF17 , INLINEFORM0 / INLINEFORM1 / INLINEFORM2 are all GRU-based units. INLINEFORM3 updates the sender embedding from the previous sender embedding INLINEFORM4 , the previous addressee embedding INLINEFORM5 , and the utterance embedding INLINEFORM6 : INLINEFORM7 
The update, as illustrated in the upper part of Figure FIGREF17 , is controlled by three gates. The INLINEFORM0 gate controls the previous sender embedding INLINEFORM1 , and INLINEFORM2 controls the previous addressee embedding INLINEFORM3 . Those two gated interactions together produce the sender embedding proposal INLINEFORM4 . Finally, the update gate INLINEFORM5 combines the proposal INLINEFORM6 and the previous sender embedding INLINEFORM7 to update the sender embedding INLINEFORM8 . The computations in INLINEFORM9 (including gates INLINEFORM10 , INLINEFORM11 , INLINEFORM12 , the proposal embedding INLINEFORM13 , and the final updated embedding INLINEFORM14 ) are formulated as: INLINEFORM15 
 where INLINEFORM0 INLINEFORM1 are learnable parameters. INLINEFORM2 uses the same formulation with a different set of parameters, as illustrated in the middle of Figure FIGREF17 . In addition, we update the observer embeddings from the utterance. INLINEFORM3 is implemented as the traditional GRU unit in the lower part of Figure FIGREF17 . Note that the parameters in INLINEFORM4 / INLINEFORM5 / INLINEFORM6 are not shared. This allows SI-RNN to learn role-dependent features to control speaker embedding updates. The formulations of INLINEFORM7 and INLINEFORM8 are similar.
The dialog encoder takes the dialog context INLINEFORM0 as input and returns speaker embeddings at the final time step, INLINEFORM1 . Recall from Section SECREF7 that Dynamic-RNN produces the context embedding INLINEFORM2 using Eq EQREF11 and then selects the addressee and response separately using Eq EQREF12 and Eq EQREF13 .
In contrast, SI-RNN performs addressee and response selection jointly: the response is dependent on the addressee and vice versa. Therefore, we view the task as a sequence prediction process: given the context and responding speaker, we first predict the addressee, and then predict the response given the addressee. (We also use the reversed prediction order as in Eq EQREF21 .)
In addition to Eq EQREF12 and Eq EQREF13 , SI-RNN is also trained to model the conditional probability as follows. To predict the addressee, we calculate the probability of the candidate speaker INLINEFORM0 to be the ground-truth given the ground-truth response INLINEFORM1 (available during training time): DISPLAYFORM0 
The key difference from Eq EQREF12 is that Eq EQREF19 is conditioned on the correct response INLINEFORM0 with embedding INLINEFORM1 . Similarly, for response selection, we calculate the probability of a candidate response INLINEFORM2 given the ground-truth addressee INLINEFORM3 : DISPLAYFORM0 
At test time, SI-RNN selects the addressee-response pair from INLINEFORM0 to maximize the joint probability INLINEFORM1 : DISPLAYFORM0 
 In Eq EQREF21 , we decompose the joint probability into two terms: the first term selects the response given the context, and then selects the addressee given the context and the selected response; the second term selects the addressee and response in the reversed order.
Data Set. We use the Ubuntu Multiparty Conversation Corpus BIBREF4 and summarize the data statistics in Table TABREF24 . same The whole data set (including the Train/Dev/Test split and the false response candidates) is publicly available. The data set is built from the Ubuntu IRC chat room where a number of users discuss Ubuntu-related technical issues. The log is organized as one file per day corresponding to a document INLINEFORM0 . Each document consists of (Time, SenderID, Utterance) lines. If users explicitly mention addressees at the beginning of the utterance, the addresseeID is extracted. Then a sample, namely a unit of input (the dialog context and the current sender) and output (the addressee and response prediction) for the task, is created to predict the ground-truth addressee and response of this line. Note that samples are created only when the addressee is explicitly mentioned for clear, unambiguous ground-truth labels. False response candidates are randomly chosen from all other utterances within the same document. Therefore, distractors are likely from the same sub-conversation or even from the same sender but at different time steps. This makes it harder than BIBREF22 lowe2015ubuntu where distractors are randomly chosen from all documents. If no addressee is explicitly mentioned, the addressee is left blank and the line is marked as a part of the context.
Baselines. Apart from Dynamic-RNN, we also include several other baselines. Recent+TF-IDF always selects the most recent speaker (except the responding speaker INLINEFORM0 ) as the addressee and chooses the response to maximize the tf-idf cosine similarity with the context. We improve it by using a slightly different addressee selection heuristic (Direct-Recent+TF-IDF): select the most recent speaker that directly talks to INLINEFORM1 by an explicit addressee mention. We select from the previous 15 utterances, which is the longest context among all the experiments. This works much better when there are multiple concurrent sub-conversations, and INLINEFORM2 responds to a distant message in the context. We also include another GRU-based model Static-RNN from BIBREF4 ouchi-tsuboi:2016:EMNLP2016. Unlike Dynamic-RNN, speaker embeddings in Static-RNN are based on the order of speakers and are fixed. Furthermore, inspired by BIBREF30 zhou16multi and BIBREF19 serban2016building, we implement Static-Hier-RNN, a hierarchical version of Static-RNN. It first builds utterance embeddings from words and then uses high-level RNNs to process utterance embeddings.
Implementation Details For a fair comparison, we follow the hyperparameters from BIBREF4 ouchi-tsuboi:2016:EMNLP2016, which are chosen based on the validation data set. We take a maximum of 20 words for each utterance. We use 300-dimensional GloVe word vectors, which are fixed during training. SI-RNN uses 50-dimensional vectors for both speaker embeddings and hidden states. Model parameters are initialized with a uniform distribution between -0.01 and 0.01. We set the mini-batch size to 128. The joint cross-entropy loss function with 0.001 L2 weight decay is minimized by Adam BIBREF31 . The training is stopped early if the validation accuracy is not improved for 5 consecutive epochs. All experiments are performed on a single GTX Titan X GPU. The maximum number of epochs is 30, and most models converge within 10 epochs.
For fair and meaningful quantitative comparisons, we follow BIBREF4 ouchi-tsuboi:2016:EMNLP2016's evaluation protocols. SI-RNN improves the overall accuracy on the addressee and response selection task. Two ablation experiments further analyze the contribution of role-sensitive units and joint selection respectively. We then confirm the robustness of SI-RNN with the number of speakers and distant responses. Finally, in a case study we discuss how SI-RNN handles complex conversations by either engaging in a new sub-conversation or responding to a distant message.
Overall Result. As shown in Table TABREF23 , SI-RNN significantly improves upon the previous state-of-the-art. In particular, addressee selection (ADR) benefits most, with different number of candidate responses (denoted as RES-CAND): around 12% in RES-CAND INLINEFORM0 and more than 10% in RES-CAND INLINEFORM1 . Response selection (RES) is also improved, suggesting role-sensitive GRUs and joint selection are helpful for response selection as well. The improvement is more obvious with more candidate responses (2% in RES-CAND INLINEFORM2 and 4% in RES-CAND INLINEFORM3 ). These together result in significantly better accuracy on the ADR-RES metric as well.
Ablation Study. We show an ablation study in the last rows of Table TABREF23 . First, we share the parameters of INLINEFORM0 / INLINEFORM1 / INLINEFORM2 . The accuracy decreases significantly, indicating that it is crucial to learn role-sensitive units to update speaker embeddings. Second, to examine our joint selection, we fall back to selecting the addressee and response separately, as in Dynamic-RNN. We find that joint selection improves ADR and RES individually, and it is particularly helpful for pair selection ADR-RES.
Number of Speakers. Numerous speakers create complex dialogs and increased candidate addressee, thus the task becomes more challenging. In Figure FIGREF27 (Upper), we investigate how ADR accuracy changes with the number of speakers in the context of length 15, corresponding to the rows with T=15 in Table TABREF23 . Recent+TF-IDF always chooses the most recent speaker and the accuracy drops dramatically as the number of speakers increases. Direct-Recent+TF-IDF shows better performance, and Dynamic-RNNis marginally better. SI-RNN is much more robust and remains above 70% accuracy across all bins. The advantage is more obvious for bins with more speakers.
Addressing Distance. Addressing distance is the time difference from the responding speaker to the ground-truth addressee. As the histogram in Figure FIGREF27 (Lower) shows, while the majority of responses target the most recent speaker, many responses go back five or more time steps. It is important to note that for those distant responses, Dynamic-RNN sees a clear performance decrease, even worse than Direct-Recent+TF-IDF. In contrast, SI-RNN handles distant responses much more accurately.
same
Case Study. Examples in Table TABREF30 show how SI-RNN can handle complex multi-party conversations by selecting from 10 candidate responses. In both examples, the responding speakers participate in two or more concurrent sub-conversations with other speakers.
Example (a) demonstrates the ability of SI-RNN to engage in a new sub-conversation. The responding speaker “wafflejock" is originally involved in two sub-conversations: the sub-conversation 1 with “codepython", and the ubuntu installation issue with “theoletom". While it is reasonable to address “codepython" and “theoletom", the responses from other baselines are not helpful to solve corresponding issues. TF-IDF prefers the response with the “install" key-word, yet the response is repetitive and not helpful. Dynamic-RNN selects an irrelevant response to “codepython". SI-RNN chooses to engage in a new sub-conversation by suggesting a solution to “releaf" about Ubuntu dedicated laptops.
Example (b) shows the advantage of SI-RNN in responding to a distant message. The responding speaker “nicomachus" is actively engaged with “VeryBewitching" in the sub-conversation 1 and is also loosely involved in the sub-conversation 2: “chingao" mentions “nicomachus" in the most recent utterance. SI-RNN remembers the distant sub-conversation 1 and responds to “VeryBewitching" with a detailed answer. Direct-Recent+TF-IDF selects the ground-truth addressee because “VeryBewitching" talks to “nicomachus", but the response is not helpful. Dynamic-RNN is biased to the recent speaker “chingao", yet the response is not relevant.
SI-RNN jointly models who says what to whom by updating speaker embeddings in a role-sensitive way. It provides state-of-the-art addressee and response selection, which can instantly help retrieval-based dialog systems. In the future, we also consider using SI-RNN to extract sub-conversations in the unlabeled conversation corpus and provide a large-scale disentangled multi-party conversation data set.
We thank the members of the UMichigan-IBM Sapphire Project and all the reviewers for their helpful feedback. This material is based in part upon work supported by IBM under contract 4915012629. Any opinions, findings, conclusions or recommendations expressed above are those of the authors and do not necessarily reflect the views of IBM.

Figure and table captions:
Table 1: Notations for the task and model.
Figure 1: Dialog encoders in DYNAMIC-RNN (Left) and SI-RNN (Right) for an example context at the top. Speaker embeddings are initialized as zero vectors and updated recurrently as hidden states along the time step. In SI-RNN, the same speaker embedding is updated in different units depending on the role (IGRUS for sender, IGRUA for addressee,GRUO for observer).
Figure 2: Illustration of IGRUS (upper, blue), IGRUA (middle, green), and GRUO (lower, yellow). Filled circles are speaker embeddings, which are recurrently updated. Unfilled circles are gates. Filled squares are speaker embedding proposals.
Table 2: Addressee and response selection results on the Ubuntu Multiparty Conversation Corpus. Metrics include accuracy of addressee selection (ADR), response selection (RES), and pair selection (ADR-RES). RES-CAND: the number of candidate responses. T : the context length.
Table 3: Data Statistics. “AdrMention Freq” is the frequency of explicit addressee mention.
Figure 3: Effect of the number of speakers in the context (Upper) and the addressee distance (Lower). Left axis: the histogram shows the number of test examples. Right axis: the curves show ADR accuracy on the test set.
Table 4: Case Study. denotes the ground-truth. Sub-conversations are coded with different numbers for the purpose of analysis (sub-conversation labels are not available during training or testing).

Questions about this paper:
what is the average number of speakers in the dataset?
by how much is accuracy improved?

Answers:
26.8
The accuracy of addressee selection is improved by 11.025 percent points on average, the accuracy of response selection is improved by 3.09 percent points on average.