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. 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 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 concept-to-text generation (Konstas and Lapata, 2012), information 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 generation (Chandu et al., 2019), and positioning of new information in existing summaries for update summarization (Prabhumoye et al., 2019). Student 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 coherence and to solve sentence ordering task. Li and Hovy (2014) 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 (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 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 (Logeswaran et al., 2018), the model uses two levels of LSTMs to first get the encoding of the sentence and then get the encoding of the entire paragraph. Cui et al. (2018) use a transformer network for the paragraph encoder to allow for reliable paragraph encoding. Prior work (Lo-geswaran et al., 2018; Cui et al., 2018; Kumar et al., 2020) 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 (Chen et al., 2016), 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 (Gong et al., 2016; Lo-geswaran et al., 2018; Cui et al., 2018) 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. For our task we have a set of N documents D = { d 1 . . . . , d N } . Let the number of sentences in each document d i be denoted by v i , where  i , v i > = 1 . Our task can be formulated as If we have a set { s o 1 , . . . , s o vi } of v i sentences in a random order where the random order is o = [ o 1 , . . . , o v i ] , then the task is to find the right order of the sentences o  = [ o  1 , . . . , o  v i ] . Prior work (Logeswaran et al., 2018; Cui et al., 2018) 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 | = (cid:0) v i 2 (cid:1) . 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. Topological sort (Tarjan, 1976) is a standard algorithm for linear ordering of the vertices of a directed graph. The sort produces an ordering o of the vertices such that for every directed edge u  v from vertex u to vertex v , u comes before v in the ordering o . We use the depth-first search based algorithm which loops through each node of the graph, in an arbitrary order. The algorithm visits each node n and prepends it to the output ordering o only after recursively calling the topological sort on all descendants of n in the graph. The algorithm terminates when it hits a node that has been visited or has no outgoing edges (i.e. a leaf node). Hence, we are guaranteed that all nodes which depend on n are already in the output ordering o when the algorithm adds node n to o . We use topological sort to find the correct ordering o  of the sentences in a document. The sentences can represent the nodes of a directed graph and the directed edges are represented by the ordering between the two sentences. The direction of the edges are the constraints predicted by the classifier. For example, if the classifier predicts the constraint that sentence s 1 precedes s 2 , then the edge s 1  s 2 would be from node of s 1 to s 2 . This algorithm has time complexity of O ( v i + |C i | ) for a document d i . In our current formulation, all the constraints are predicted before applying the sort. Hence, we have to consider all the |C i | = (cid:0) v i 2 (cid:1) edges in the graph. The time complexity of our current formulation is O ( v 2 i ) . But the same technique could be adopted using a Merge Sort (Knuth, 1998) algorithm in which case the time complexity would be O ( v i log v i ) . In this case, the sort algorithm is applied first and the constraint is predicted only for the two sentences for which the relative ordering is required during the sort time. We build a classifier to predict a constraint between two sentences s 1 and s 2 (say). The constraint learnt by the classifier is the relative ordering between the two sentences. Specifically, the classifier is trained to predict whether s 2 follows s 1 or not i.e the the classifier predicts the constraint s 1 < s 2 . BERT based Representation. (B-TSort) We use the Bidirectional Encoder Representations from Transformers (BERT) pre-trained uncased language model (Devlin et al., 2019) and fine-tune it on each dataset using a fully connected perceptron layer. Specifically, we leverage the Next Sentence Prediction objective of BERT and get a single representation for both sentences s 1 and s 2 . The input to the BERT model is the sequence of tokens of sentence s 1 , followed by the separator token [SEP]', followed by the sequence of tokens for sentence s 2 . We use the pooled representation for all the time steps 1 . LSTM based Representation. (L-TSort) In this model we get two separate representations h 1 and h 2 for s 1 and s 2 from a bi-directional LSTM encoder, respectively. We pass the concatenation of h 1 and h 2 as input to two layers of perceptron for constraint prediction. This model is trained to gain insight on the contribution of pre-trained sentence representations for the constraint prediction formulation of the task. This section describes the datasets, the evaluation metric and the results of our experiments. The hyper-paramater settings are reported in Apendix. NSF. NIPS, AAN abstracts. These three datasets contain abstracts from NIPS papers, ACL papers, and the NSF Research Award Abstracts dataset respectively and are introduced in (Logeswaran et al., 2018). The paper also provides details about the statistics and processing steps for curating these three datasets. SIND caption. We also consider the SIND (Se-quential Image Narrative Dataset) caption dataset (Huang et al., 2016) used in the sentence ordering task by (Gong et al., 2016). All the stories in this dataset contain five sentences each and we only consider textual stories for this task. Attention Order Network (AON). This is the current state-of-the-art model (Cui et al., 2018) which formulates the sentence ordering task as a order prediction task. It uses a LSTM based encoder to learn the representation of a sentence. It then uses a transformer network based paragraph encoder to learn a representation of the entire document. It then decodes the sequence of the order by using a LSTM based decoder. BERT Attention Order Network (B-AON). To have a fair comparison between our model and the AON model, we replace the LSTM based sentence representation with the pre-trained uncased BERT model. This model plays a pivotal role of giving us an insight into how much improvement in performance we get only due to BERT. Perfect Match (PMR): calculates the percentage of samples for which the entire sequence was correctly predicted (Chen et al., 2016). PMR = 1 N (cid:80) Ni =1 1 { o i = o  i } , where N is the number of samples in the dataset. It is the strictest metric. Sentence Accuracy (Acc): measures the percentage of sentences for which their absolute position was correctly predicted (Logeswaran et al., 2018). Acc = 1 N (cid:80) Ni =1 1 v i (cid:80) v i j =1 1 { o ij = o  ij } , where v i is the number of sentences in the i th document. It is a also a stringent metric. Kendall Tau (Tau): quantifies the distance between the predicted order and the correct order in terms of the number of inversions (Lapata, 2006). = 1  2 I/ (cid:0) v i 2 (cid:1) , where I is the number of pairs in the predicted order with incorrect relative order and   [  1 , 1] . Rouge-S: calculates the percentage of skip-bigrams for which the relative order is predicted correctly (Chen et al., 2016). Skip-bigrams are the total number of pairs (cid:0) v i 2 (cid:1) in a document. Note that it does not penalize any arbitrary gaps between two sentences as long as their relative order is correct. Rouge S = 1 ( vi 2 ) Skip ( o )  Skip ( o  ) , where the Skip ( . ) function returns the set of skip-bigrams of the given order. Longest Common Subsequence (LCS): calculates the ratio of longest common sub-sequence (Gong et al., 2016) between the predicted order and the given order (consecutiveness is not necessary, and higher is better). Human Evaluation We introduce a human evaluation experiment to assess the orders predicted by the models. We set up a manual pairwise comparison following (Bennett, 2005) and present the human judges with two orders of the same piece of text. The judges are asked Pick the option which is in the right order according to you. They can also pick a third option No Preference' which corresponds to both the options being equally good or bad. In total we had 100 stories from the SIND dataset 2 annotated by 10 judges. We setup three pairwise studies to compare the B-TSort vs AON order, B-TSort vs Gold order and AON vs Gold order (Gold order is the actual order of the text). Each judge annotated a total of 30 stories, 10 in each of the above mentioned categories. The judges were naive annotators. Table 1 shows the results of the automated metrics for the NIPS and SIND datasets 3 . It shows that AON 4 model gains on all metrics when the sentence embeddings are switched to BERT. The L-TSort model which does not utilize BERT embeddings comes close to AON performance on Rouge-S and Tau metrics. This demonstrates that the simple L-TSort method is as accurate as AON in predicting relative positions but not the absolute positions (PMR and Acc metric). Table 1 shows that our method B-TSort does not perform better 2 We choose SIND because all the stories contain 5 sentences and hence it is easy to read for the judges. The orders of the stories are easier to judge as compared to the orders of scientific abstracts like NSF, NIPS and AAN as they require the judges to have an informed background. 3 We fine-tune BERT which is memory intensive. Hence, we show the results of B-AON only on these two datasets as they need 2 transformer layers for paragraph encoder (Cui et al., 2018) 4 We use the code provided by the authors to train the AON and B-AON model. The numbers reported in Table 1 and 2 are our runs of the model. Hence, they differ from the numbers reported in the paper (Cui et al., 2018). only due to BERT embeddings but also due to the design of the experiment. Note that BERT has been trained with the Next Sentence Prediction objective and not the sentence ordering objective like AL-BERT (Lan et al., 2020). We believe that framing this task as a constraint solving task will further benefit from pre-trained language model like AL-BERT. Table 2 shows results for the NSF and AAN datasets and the B-TSort model performs better than the AON model on all metrics. Table 3 shows results for the three human evaluation studies on the SIND dataset. It shows that human judges prefer B-TSort orders 10% more number of times than the B-AON orders 5 . The reference order may not be the only correct ordering of the story. The variability in the orders produced by B-TSort and B-AON is not very high and hence in comparison with Gold orders, we don't see much difference in human preferences. The low scores of AON could be due to the fact that it has to decode the entire sequence of the order. The search space for decoding is very high (in the order of v i ! ). Since our framework, breaks the problem to a pairwise constraint problem, the search space for our model is in the order of v 2 i . Discussion: We perform additional analysis to determine the displacement of sentences in the predicted orders of the models, scalability of the models for longer documents, and an understanding of quality of the human judgements. 5 Examples of B-TSort and B-AON orders are shown in Table 6 and 7 for SIND and NIPS dataset in Appendix. Displacement of sentences in predicted orders is measured by calculating the percentage of sentences whose predicted location is within 1, 2 or 3 positions (in either direction) from their original location. A higher percentage indicates less displacement of sentences. We observed that in spite of lack of a global structure, B-TSort consistently performs better on all datasets for all three window sizes as shown in Table 4. Observe that as window size reduces, the difference between B-TSort and B-AON percentages increases. This implies that displacement of sentences is higher in B-AON despite taking the whole document into account. We additionally perform a comparison of models on documents containing more than 10 sentences and the results are shown in Table 5. B-TSort consistently performs better on all the metrics. SIND dataset is omitted in these experiments as the maximum number of sentences in the story is five for all the stories in the dataset. For each dataset, the Tau difference for longer documents is much higher than the Tau difference on the overall dataset (Ta-ble 1 and 2). This implies that B-TSort performs much better for longer documents. Note that the AON model generates the order and hence need not generate positions for all the sentences in the input. We calculate the percentage of mismatches between the length of the input document and the generated order. For AON model on the NSF dataset which has longest documents, the overall mismatch is 5.85% (Table 4), while the mismatch for documents with more than 10 sentences is 11.60%. The AON model also produces an overall mismatch of 0.84 % on AAN documents while producing a mismatch of 5.17% on longer AAN documents. Similarly, the B-AON model has an overall mismatch of 3.48% for NIPS dataset, and 33.33% mismatch for longer documents. This problem does not arise in our design of the task as it does not have to stochastically generate orders. To better understand the choices of human judges, we observe the average length of stories Model PMR Acc Tau Rouge-S LCS NIPS abstracts B-AON 0.0 29.18 0.51 74.64 63.81 B-TSort 0.0 39.43 0.74 83.26 71.68 NSF abstracts AON 2.12 21.42 0.41 67.45 55.47 B-TSort 0.67 28.57 0.64 68.46 64.86 AAN abstracts AON 0.0 22.70 0.40 68.90 56.19 B-TSort 0.0 36.86 0.69 78.52 72.01 Table 5: Analysis on NIPS, NSF and AAN datasets for documents longer than 10 sentences. calculated in number of tokens. For the B-TSort vs B-AON study, we discover that the average length of the stories for B-TSort, B-AON and No Preference' chosen options is 86, 65 and 47 respectively. This means that B-TSort is better according to human judges for longer stories. Similarly for B-TSort vs Gold experiment, the human judges were confused with longer stories, reiterating that B-TSort performs well with long stories. 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. This work was supported in part by ONR Grant N000141812861, NSF IIS1763562, and Apple. We would also like to acknowledge NVIDIAs GPU support.
abstain abstain objective objective abstain abstain method other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain method abstain result method objective objective result abstain abstain other result abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain method method abstain abstain abstain method abstain abstain abstain abstain method abstain abstain method abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain result abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain objective objective abstain abstain objective other other