Findings on Conversation Disentanglement (2021)

Abstract: Conversation disentanglement, the task to identify separate threads in conversations, is an important pre-processing step in multi-party conversational NLP applications such as conversational question answering and con-versation summarization. Framing it as a utterance-to-utterance classification problem â i.e. given an utterance of interest (UOI), find which past utterance it replies to â we explore a number of transformer-based models and found that BERT in combination with handcrafted features remains a strong baseline. We then build a multi-task learning model that jointly learns utterance-to-utterance and utterance-to-thread classification. Observing that the ground truth label (past utterance) is in the top candidates when our model makes an error, we experiment with using bipartite graphs as a post-processing step to learn how to best match a set of UOIs to past utterances. Experiments on the Ubuntu IRC dataset show that this approach has the potential to out-perform the conventional greedy approach of simply selecting the highest probability candidate for each UOI independently, indicating a promising future research direction.

## introduction in public forums and chatrooms such as reddit and internet relay chat (irc), there are often multiple conversations happening at the same time. figure 1 shows two threads of conversation (blue and green) running in parallel. conversation disentanglement, a task to identify separate threads among intertwined messages, is an essential preprocessing step for analysing entangled conversations in multiparty conversational applications such as question answering @xcite and response selection @xcite . it is also useful in constructing datasets for dialogue system studies @xcite . in link prediction, the model that estimates the relevance between a pair of utterances plays an important role. to this end, we explore three transformer-based pretrained models: bert @xcite , albert @xcite and poly-encoder @xcite . these variants are selected by considering performance, memory consumption and speed. we found that bert in combination with handcrafted features remains a strong baseline. observing that utterances may be too short to contain sufficient information for disentanglement, we also build a multi-task learning model that learns to jointly link a uoi to a past utterance and a cluster of past utterances (i.e. the conversation threads). for clustering, we experiment with bipartite graph matching algorithms that consider how to best link a set of uois to their top candidates, thereby producing globally more optimal clusters. when the graph structure is known, we show that this approach substantially outperforms conventional greedy clustering method, although challenges remain on how to infer the graph structure. to summarise: ## related work conversation disentanglement methods can be classified into two categories: (1) two-step methods and ( 2 ) end-to-end methods. in two-step methods, the first step is to measure the relations between utterance pairs, e.g., replyto relations @xcite or same thread relations @xcite . either feature-based models @xcite or deep learning models @xcite are used. afterwards a clustering algorithm is applied to recover separate threads using results from the first step. @xcite @xcite use a greedy graph partition algorithm to assign an utterance u to the thread of u which has the maximum relevance to u among candidates if the score is larger than a threshold. kummerfeld et al. (2019); zhu et al. (2020 ) use a greedy algorithm to recover threads following all reply-to relations independently identified for each utterance. @xcite propose a graph connected component-based algorithm. end-to-end methods construct threads incrementally by scanning through a chat log and either append the current utterance to an existing thread or create a new thread. (2020) build a transition-based model that uses three lstms for utterance encoding, context encoding and thread state updating, respectively. ## notations and task definition given a chat log u with n utterances {u 1 , u 2 , • • • , u n } in chronological order, the goal of conversation disentanglement is to obtain a set of disjoint threads @xmath0, t 2 , • • • , t m }. each thread t l contains a collection of topicallycoherent utterances. utterance u i contains a list of n i tokens w i 1 , w i 2 , • • • , w i n i . the task can be framed as a reply-to relation identification problem, where we aim to find the parent utterance for every u @xmath1, i.e., if an utterance u i replies to a (past) utterance u j , u j is called the parent utterance of u i . when all reply-to utterance pairs are identified, t can be recovered unambiguously by following the reply-to relations. henceforth we call the target utterance u i an utterance of interest (uoi). we use u @xmath2, where u j is the parent utterance of u i . the reply-to relation is asymmetric, i.e., u @xmath3. we use a candidate pool c i to denote the set of candidate utterances from which the parent utterance is selected from. ## dataset we conduct experiments on the ubuntu irc dataset @xcite , which contains questions and answers about the ubuntu system, as well as chit-chats from multiple participants. split chat logs ann. utt threads avg. parent train 153 67463 17327 1.03 valid 10 2500 495 1.04 test 10 5000 964 1.04 ## experiments we start with studying pairwise models that take as input a pair of utterances and decide whether a reply-to relation exists (section 5.1). then, we add dialogue history information into consideration and study a multi-task learning model (section 5.2) built upon the pairwise models. in section 5.3, we further investigate a globally-optimal approach based on bipartite graph matching, considering the top parent candidates of multiple uois together to help resolve conflicts in the utterance matches. ## conclusion in this paper, we frame conversation disentanglement as a task to identify the past utterance(s) that each utterance of interest (uoi) replies to, and conduct various experiments to explore the task. we first experiment with transformer-based models, and found that bert combined with manual features is still a strong baseline. next we propose a multi-task learning model to incorporate dialogue history into bert, and show that the method is effective especially when manual features are not available. based on the observation that most utterances' parents are in the top-ranked candidates when there are errors, we experiment with bipartite graph matching that matches a set of uois and candidates together to produce globally more optimal clusters. the algorithm has the potential to outperform standard greedy approach, indicating a promising future research direction. avoid infeasibility: