Topological Sort for Sentence Ordering

Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, pages 2783–2792 July 5 - 10, 2020. c⃝2020 Association for Computational Linguistics 2783 Topological Sort for Sentence Ordering Shrimai Prabhumoye, Ruslan Salakhutdinov, Alan W Black School of Computer Science Carnegie Mellon University Pittsburgh, PA, USA {sprabhum, rsalakhu, awb}@cs.cmu.edu Abstract Sentence ordering is the task of arranging the sentences of a given text in the correct order. Recent work using deep neural networks for this task has framed it as a sequence prediction problem. In this paper, we propose a new fram- ing of this task as a constraint solving problem and introduce a new technique to solve it. Ad- ditionally, we propose a human evaluation for this task. The results on both automatic and human metrics across four different datasets show that this new technique is better at cap- turing coherence in documents. 1 Introduction Sentence ordering is the task of arranging sentences into an order which maximizes the coherence of the text (Barzilay and Lapata, 2008). This is important in applications where we have to determine the se- quence of pre-selected set of information to be pre- sented. This task has been well-studied in the com- munity due to its significance in down stream ap- plications such as ordering of: concepts in concept- to-text generation (Konstas and Lapata, 2012), in- formation from each document in multi-document summarization (Barzilay and Elhadad, 2002; Nal- lapati et al., 2017), events in storytelling (Fan et al., 2019; Hu et al., 2019), cooking steps in recipe gen- eration (Chandu et al., 2019), and positioning of new information in existing summaries for update summarization (Prabhumoye et al., 2019). Stu- dent essays are evaluated based on how coherent and well structured they are. Hence, automated essay scoring (Burstein et al., 2010; Miltsakaki and Kukich, 2004) can use this task to improve the efficiency of their systems. Early work on coherence modeling and sentence ordering task uses probabilistic transition model based on vectors of linguistic features (Lapata, 2003), content model which represents topics as states in an HMM (Barzilay and Lee, 2004), and entity based approach (Barzilay and Lapata, 2008). Recent work uses neural approaches to model co- herence and to solve sentence ordering task. Li and Hovy (2014) introduced a neural model based on distributional sentence representations using re- current or recursive neural networks and avoided the need of feature engineering for this task. In (Li and Jurafsky, 2017), they extend it to domain independent neural models for coherence and they introduce new latent variable Markovian generative models to capture sentence dependencies. These models used windows of sentences as context to predict sentence pair orderings. Gong et al. (2016) proposed end-to-end neural architecture for sen- tence ordering task which uses pointer networks to utilize the contextual information in the entire piece of text. Recently hierarchical architectures have been proposed for this task. In (Logeswaran et al., 2018), the model uses two levels of LSTMs to first get the encoding of the sentence and then …

Content truncated to 500 words