Formulating Neural Sentence Ordering as the Asymmetric Traveling Salesman Problem (2021)

Abstract: The task of Sentence Ordering refers to rearranging a set of given sentences in a coherent ordering. Prior work (Prabhumoye et al., 2020) models this as an optimal graph traversal (with sentences as nodes, and edges as local constraints) using topological sorting. However, such an approach has major limitations – it cannot handle the presence of cycles in the resulting graphs and considers only the binary presence/absence of edges rather than a more granular score. In this work, we propose an alternate formulation of this task as a classic combinatorial optimization problem popular as the Traveling Salesman Problem (or TSP in short). Compared to the previous approach of using topological sorting, our proposed technique gracefully handles the presence of cycles and is more expressive since it takes into account real-valued constraint/edge scores rather than just the presence/absence of edges. Our experiments demonstrate improved handling of such cyclic cases in resulting graphs. Additionally, we highlight how model accuracy can be sensitive to the ordering of input sentences when using such graphs-based formulations. Finally, we note that our approach requires only lightweight fine-tuning of a classification layer built on pretrained BERT sentence encoder to identify local relationships.

## introduction a logical and coherent structure is an important characteristic of easily comprehensible text. as such, modeling the structure of coherent texts has been an important problem in nlp @xcite . in this paper, we work on the task of sentence ordering, wherein given an unordered set of sentences, the aim is to generate the most coherent ordering among them ( much prior work has formulated sentence ordering as a sequence prediction task @xcite , by first encoding the input sentences, and then predicting the ordering or numbering of the sentences. there have also been attempts to model the task as a ranking problem @xcite . more recently, prabhumoye et al. (2020) model this as a constraint-solving problem, wherein they first identify the relative ordering between pairs of sentences using a bert-based @xcite classifier. thereafter, they formulate it as performing a topological sort on a graph, wherein each sentence is a node in a graph, and each directed edge represents a pairwise constraint. compared to prior work, it simplifies the decoding process by using a graph traversal formulation. however, the topological sort algorithm used for translating constraints into the final order leads to major limitations. firstly, it cannot handle cycles in the resulting graph, and picks some arbitrary ordering in such cases (figure 1 ). our analysis shows that cycles were present in more than 54% of the graphs across the four datasets under consideration. secondly, though the underlying classifier can provide more fine-grained scores, the scores are discretized/binarized to run the topological sorting algorithm. this leads to a loss of useful information in the decoding process. in this work, we propose a reformulation of neural sentence ordering as the classical traveling salesman problem, while leveraging the recent progress in large pre-trained models such as bert. we build upon the classification model used in @xcite and overcome the limitations in their approach by making better use of the information yielded by the classifier, taking into account global dependencies by employing a combinatorial minimization objective, and working with an overall framework that can handle cycles in the resulting graph. our contributions can be summarized as follows. firstly, we provide a novel formulation of the sentence ordering task as the traveling salesman problem. compared to the previous graphbased approach of using topological sorting, our proposed technique gracefully handles the presence of cyclic constraints. moreover, it is more expressive since it admits real-valued soft constraints as opposed to hard binary constraints. secondly, experiments with multiple datasets demonstrate improved results under some setups compared to the baselines using alternative graph-based formulation. finally, we observe how certain choices in data pre-processing in graph-based approaches for sentence ordering can affect accuracy scores. we propose and use a more robust data processing and evaluation. the code is publicly available. 1 ## background in this section, we first formally describe the task of sentence ordering. then we discuss its formulation as a constrained graph traversal, and discuss limitations of prior formulations of the task as a graph traversal problem. ## sentence ordering as the traveling salesman problem as mentioned previously, our objective is to work with soft constraints rather than binary constraints. to enable the use of such soft constraints, we cast the sentence ordering task as a traveling salesman traversal with respect to the graph denoting sentences as nodes, and constraints as edges. in the rest of this section, we first briefly describe the traveling salesman problem (tsp) (section 3.1), then describe how we reduce the sentences ordering as tsp (section 3.2). thereafter, we discuss the procedure to identify soft constraints using a classifier built on bert representations. finally, we discuss the solutions to solve tsp given a graph (section 3.4). ## analysis and discussions in this section, we analyze our model on additional parameters including scalability, end-point performance, and displacement. note that in this section, we use the bertsp-approx method for comparison with b-tsort as the bertsp-approx variant can be uniformly applied across all the datasets under consideration, as opposed to bertsp-ensemble which is a mixture of two methods. ## related work in the recent past, numerous neural approaches have been proposed for sentence ordering. @xcite used a pairwise ranking model @xcite that assigns a score to the relative ordering of every pair of sentences. prabhumoye et al. (2020) train a classifier to predict an order constraint between any two sentences and use sorting based on these constraints to predict the final order. @xcite construct multiple constraint graphs which are integrated into sentence representations by graph isomorphism networks and ranked via listmle. the use of a pointer decoder for sequential prediction @xcite @xcite along with an intermediate paragraph encoder @xcite @xcite for better capturing the global dependencies has been proposed in many variants. @xcite replace the pointer decoder with a feed-forward neural network and use ranking loss to enable simultaneous prediction of scores for all sentences. the pairwise approaches generally suffer from lack of global interactions while pointer-based ap- we have proposed a traveling salesman problem based formulation for sentence ordering. the use of such graph-based optimizations have been explored in past work in nlp such as arm-to-text generation @xcite , opinion summarization @xcite , multi-document summarization (al-saleh and menai, 2018), etc. ## conclusion we demonstrate the potential of a simpler, cheaper yet effective approach for the task of sentence ordering. our reformulation of the task as an asymmetric tsp allows for the application of exact and heuristic graphical algorithms which are lighter and more transparent as opposed to heavier neural approaches. future work: in place of bert, use of alternative model architectures like albert, xlnet and bart may provide better sentence representations for sentence ordering as their language modeling objectives better align with this task. in the decoding part, more heuristic-based or neural-based approaches to combinatorial optimization may provide better alternatives.