A Linear-Time Bottom-Up Discourse Parser with Constraints and Post-Editing

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 511–521, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics A Linear-Time Bottom-Up Discourse Parser with Constraints and Post-Editing Vanessa Wei Feng Department of Computer Science University of Toronto Toronto, ON, Canada weifeng@cs.toronto.edu Graeme Hirst Department of Computer Science University of Toronto Toronto, ON, Canada gh@cs.toronto.edu Abstract Text-level discourse parsing remains a challenge. The current state-of-the-art overall accuracy in relation assignment is 55.73%, achieved by Joty et al. (2013). However, their model has a high order of time complexity, and thus cannot be ap- plied in practice. In this work, we develop a much faster model whose time complex- ity is linear in the number of sentences. Our model adopts a greedy bottom-up ap- proach, with two linear-chain CRFs ap- plied in cascade as local classifiers. To en- hance the accuracy of the pipeline, we add additional constraints in the Viterbi decod- ing of the first CRF. In addition to effi- ciency, our parser also significantly out- performs the state of the art. Moreover, our novel approach of post-editing, which modifies a fully-built tree by considering information from constituents on upper levels, can further improve the accuracy. 1 Introduction Discourse parsing is the task of identifying the presence and the type of the discourse relations between discourse units. While research in dis- course parsing can be partitioned into several di- rections according to different theories and frame- works, Rhetorical Structure Theory (RST) (Mann and Thompson, 1988) is probably the most am- bitious one, because it aims to identify not only the discourse relations in a small local context, but also the hierarchical tree structure for the full text: from the relations relating the smallest discourse units (called elementary discourse units, EDUs), to the ones connecting paragraphs. For example, Figure 1 shows a text fragment consisting of two sentences with four EDUs in total (e1-e4). Its discourse tree representation is shown below the text, following the notation con- vention of RST: the two EDUs e1 and e2 are re- lated by a mononuclear relation CONSEQUENCE, where e2 is the more salient span (called nucleus, and e1 is called satellite); e3 and e4 are related by another mononuclear relation CIRCUMSTANCE, with e4 as the nucleus; the two spans e1:2 and e3:4 are further related by a multi-nuclear relation SE- QUENCE, with both spans as the nucleus. Conventionally, there are two major sub-tasks related to text-level discourse parsing: (1) EDU segmentation: to segment the raw text into EDUs, and (2) tree-building: to build a discourse tree from EDUs, representing the discourse relations in the text. Since the first sub-task is considered rela- tively easy, with the state-of-art accuracy at above 90% (Joty et al., 2012), the recent research focus is on the second sub-task, and often uses manual EDU segmentation. The current state-of-the-art overall accuracy of the tree-building sub-task, evaluated on the RST Discourse Treebank (RST-DT, to be introduced in Section 8), is 55.73% by Joty et al. …

Content truncated to 500 words