Structured Dialogue Discourse Parsing (2022)

Abstract: Dialogue discourse parsing aims to uncover the internal structure of a multi-participant conversation by finding all the discourse links and corresponding relations . Previous work either treats this task as a series of independent multiple-choice problems, in which the link existence and relations are decoded separately, or the encoding is restricted to only local interaction, ignoring the holistic structural information. In contrast, we propose a principled method that improves upon previous work from two perspectives: encoding and decoding. From the encoding side, we perform structured encoding on the adjacency matrix followed by the matrix-tree learning algorithm, where all discourse links and relations in the dialogue are jointly optimized based on latent tree-level distribution. From the decoding side, we perform structured inference using the modified Chiu-Liu-Edmonds algorithm, which explicitly generates the labeled multi-root non-projective spanning tree that best captures the discourse structure. In addition, unlike in previous work, we do not rely on hand-crafted features; this improves the model’s robustness. Experiments show that our method achieves new state-of-the-art, surpassing the previous model by 2.3 on STAC and 1.5 on Molweni (F1 scores).

## introduction discourse parsing is a series of tasks that consist of elementary discourse unit (edu) segmentation, relation directionality classification (optional), and relation type classification between edus @xcite . it serves as the first step of many downstream applications (meyer and popescu-belis, 2012; jansen et al., 2014; narasimhan and barzilay, 2015; bhatia et al., 2015; ji et al., 2016; asher et al., 2016; ji and smith, 2017; li et al., 1 code released at https://github.com/ chijames/structured_dialogue_discourse_ parsing . one straightforward solution to this problem is to transform the parsing structure into a series of local pairwise link prediction problems. in other words, the model is expected to compute some models encoding decoding link & relation prediction use feature mst (2015) local, edge-wise partial mst separate y ilp (2016) local, edge-wise ilp separate y deep-seq. (2019) global, two-staged indp. multiple choice separate y struct-aware (2021) global, fully-connected indp. multiple choice separate y hierarchical (2021) hierarchical indp. multiple choice separate n this work global, structured full mst joint n finally, our method does not rely on human-designed features, hence enjoys better robustness. in contrast to previous work, our core observation is that by adding a dummy utterance at the beginning of the dialogue, the overall structure closely resembles a labeled multi-root nonprojective spanning tree. in light of this observation, we propose a principled dialogue discoursing parser that encodes structural inductive biases during training and inference. the essential elements of our method are the novel structured parameterization of the adjacency matrix, the directed version of matrix-tree theorem @xcite , and the modified directed spanning tree inference algorithm. to the best of our knowledge, this is the first time that the labeled multi-root non-projective spanning tree is applied to the analysis of dialogue discourse structure. in summary, the contributions of this paper are: we are given a dialogue session d and the links and relations between pairs of utterances labeled using the 17 discourse relations defined in @xcite . all the utterances, links, and relations constitute a graph g(v, e, r), where v represents the set of utterances, e represents the links connecting them, and r represents the edge labels. the goal of a discourse parser is to predict e and r given v . there are five existing dialogue discourse parsers to the best of our knowledge @xcite @xcite @xcite . we compare them against each other in detail in the following subsections and provide a summary in ## structure formulation the graph g defined in § 2 can theoretically be any directed acyclic graph, which is generally difficult to optimize. fortunately, we find that by discarding only a small fraction of the edges, which is 6% for the stac corpus and 0% for the molweni corpus, we can recover a spanning tree-like structure that permits efficient learning and structure inference. for the nodes having more than one parent, we keep only the latest one. 2 in addition, for dangling utterances that do not have any parents, we connect them to the dummy root utterance, so we are in fact optimizing a multi-root tree during training time. finally, note that our tree structure allows different links to cross each other (figure 1 ) and each edge also has a relation label, g(v, e, r) is a labeled directed multi-root non-projective spanning tree, which is referred to as tree for conciseness hereinafter 3 . several questions naturally arise: ## experiments 5.1 datasets there are two datasets for us to train the discourse parser, one of which is the stac @xcite corpus, which is a multi-party dialogue corpus collected from an online game, and the other is the ubuntu irc corpus @xcite , which compiles technical discussions about linux. the differences between these two datasets were analyzed in @xcite , where the takeaway messages are: 1) there is no significant difference in their average edu numbers, 2) the lexical distributions are significantly different sharing only a small portion of common tokens, 3) relation distributions are similar. ## related work discourse parsing as discussed in the introduction section, there are three types of discourse parsing formalisms: @xcite , pdtb @xcite , and sdrt (lascarides and @xcite . for the first two tasks, there are transition-based @xcite @xcite and cky-based methods @xcite @xcite in the literature. in this work, we assume that the edus are already given. in practice, there are papers working on segmenting edus @xcite before feeding them to the discourse parser. dialogue disentanglement clustering utterances in a conversation into threads is studied extensively by previous work @xcite @xcite @xcite @xcite @xcite . they predict the reply-to links independently and run a connected component algorithm to construct the threads. this is similar to the uas setting in this work. structured learning algorithms natural language is highly structured suggesting that the introduction of structural bias will facilitate learning. previous work have studied dependency-tree like structures extensively @xcite @xcite @xcite . several works propose to incorporate such inductive bias into intermediate layers of modern nlp models @xcite @xcite . in our work, the induced structure is not only implicitly learned, it is also used to directly decode the labeled tree structure, which is our ultimate goal. ## conclusion in this paper, we propose a principled method for dialogue discourse parsing. from the encoding side, we introduce a structurally-encoded adjacency matrix followed by the matrix-tree theorem, which is used to holistically model all utterances as a tree. from the decoding side, we apply the modified cle algorithm for maximum spanning tree induction. our method achieves state-of-the-art performance on two benchmark datasets. we also benchmark the cross-domain parser performance, and find our parser performs the best in the mostcommonly used and harder las setting. we believe that the techniques described in this work pave the way for more structured analyses of dialogue and interesting research problems in the field of dialogue discourse parsing.