Topological Sort for Sentence Ordering (2020)

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 framing of this task as a constraint solving problem and introduce a new technique to solve it. Additionally, 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 capturing coherence in documents.

## introduction sentence ordering is the task of arranging sentences into an order which maximizes the coherence of the text @xcite . this is important in applications where we have to determine the sequence of pre-selected set of information to be presented. this task has been well-studied in the community due to its significance in down stream applications such as ordering of: concepts in conceptto-text generation @xcite , information from each document in multi-document summarization @xcite , events in storytelling @xcite , cooking steps in recipe generation @xcite , and positioning of new information in existing summaries for update summarization @xcite . student essays are evaluated based on how coherent and well structured they are. hence, automated essay scoring @xcite 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 @xcite , content model which represents topics as states in an hmm @xcite , and entity based approach @xcite . recent work uses neural approaches to model coherence and to solve sentence ordering task. @xcite introduced a neural model based on distributional sentence representations using recurrent or recursive neural networks and avoided the need of feature engineering for this task. in @xcite , 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. @xcite proposed end-to-end neural architecture for sentence 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 @xcite , the model uses two levels of lstms to first get the encoding of the sentence and then get the encoding of the entire paragraph. @xcite use a transformer network for the paragraph encoder to allow for reliable paragraph encoding. prior work @xcite @xcite has treated this task as a sequence prediction task where the order of the sentences is predicted as a sequence. the decoder is initialized by the document representation and it outputs the index of sentences in sequential order. only in @xcite , this task is framed as a ranking problem. in this work, a pairwise score is calculated between two sentences and then the final score for an order is obtained by summing over all the scores between pairs of sentences. the order which has the maximum score is given as output. instead of considering all possible permutations of a given order, it uses beam-search strategy to find a suboptimal order. most of the recent work @xcite @xcite tries to leverage the contextual information but has the limitation of predicting the entire sequence of the order. this has the drawback that the prediction at the current time step is dependent on the prediction of the previous time step. another limitation of the prior work is the availability of good sentence representations that can help in determining the relative order between two sentences. for this work we frame the task as a constraint learning problem. we train a model which learns to predict the correct constraint given a pair of sentences. the constraint learnt by our model is the relative ordering between the two sentences. given a set of constraints between the sentences of a document, we find the right order of the sentences by using sorting techniques. since we don't attach a score to an order, we don't have to consider all the permutations of an order. our main contribution is a new framing for the sentence ordering task as a constraint solving problem. we also propose a new and simple approach for this task in this new framework. we show that a simple sorting technique can outperform the previous approaches by a large margin given that it has good sentence representations. the bottleneck for most of the hierarchical models is memory required by the representations of all the sentences and the representation of the paragraph. the new framing also obviates these memory issues. the code can be found at https://github.com/shrimai/ topological-sort-for-sentence-ordering . additionally, we introduce a human evaluation for this task and show that our model outperforms the state-of-the-art on all the metrics. ## methodology for our task we have a set of n documents @xmath0. . . . , d n }. let the number of sentences in each document d i be denoted by v i , where ∀i, v @xmath1. our task can be formulated as -if we have a set {s o 1 , . . . , s ov i } of v i sentences in a random order where the random order is @xmath2, . . . , o v i ], then the task is to find the right order of the sentences prior work @xcite learns to predict the sequence of the correct order o * . in this formulation of the task, we have c i set of constraints for document d i . these constraints c i represent the relative ordering between every pair of sentences in d i . hence, we have |c i | = v i 2 . for example, if a document has four sentences in the correct order s 1 < s 2 < s 3 < s 4 , then we have six set of constraints {s 1 < s 2 , s 1 < s 3 , s 1 < s 4 , s 2 < s 3 , s 2 < s 4 , s 3 < s 4 }. constraints c i are learnt using a classifier neural network described in ( §2.2). we finally find the right order o * using topological sort on the relative ordering between all the c i pairs of sentences. ## experimental results this section describes the datasets, the evaluation metric and the results of our experiments. the hyper-paramater settings are reported in apendix. ## conclusion and future work we have shown a new way to design the task of sentence ordering. we provide a simple yet efficient method to solve the task which outperforms the state of the art technique on all metrics. we acknowledge that our current model has the limitation of not including the entire context of the paragraph while making the decision of the relative order of the pairs. our future work is to include the paragraph representation in the constraint prediction model. this will help our methodology to have the benefit of making informed decision while also solving constraints.