Probabilistic Text Structuring: Experiments with Sentence Ordering

Probabilistic Text Structuring: Experiments with Sentence Ordering Mirella Lapata Department of Computer Science University of Sheffield Regent Court, 211 Portobello Street Sheffield S1 4DP, UK mlap@dcs.shef.ac.uk Abstract Ordering information is a critical task for natural language generation applications. In this paper we propose an approach to information ordering that is particularly suited for text-to-text generation. We de- scribe a model that learns constraints on sentence order from a corpus of domain- specific texts and an algorithm that yields the most likely order among several al- ternatives. We evaluate the automatically generated orderings against authored texts from our corpus and against human sub- jects that are asked to mimic the model’s task. We also assess the appropriateness of such a model for multidocument summa- rization. 1 Introduction Structuring a set of facts into a coherent text is a non-trivial task which has received much attention in the area of concept-to-text generation (see Reiter and Dale 2000 for an overview). The structured text is typically assumed to be a tree (i.e., to have a hier- archical structure) whose leaves express the content being communicated and whose nodes specify how this content is grouped via rhetorical or discourse re- lations (e.g., contrast, sequence, elaboration). For domains with large numbers of facts and rhetorical relations, there can be more than one pos- sible tree representing the intended content. These different trees will be realized as texts with different sentence orders or even paragraph orders and differ- ent levels of coherence. Finding the tree that yields the best possible text is effectively a search prob- lem. One way to address it is by narrowing down the search space either exhaustively or heuristically. Marcu (1997) argues that global coherence can be achieved if constraints on local coherence are sat- isfied. The latter are operationalized as weights on the ordering and adjacency of facts and are derived from a corpus of naturally occurring texts. A con- straint satisfaction algorithm is used to find the tree with maximal weights from the space of all possi- ble trees. Mellish et al. (1998) advocate stochastic search as an alternative to exhaustively examining the search space. Rather than requiring a global op- timum to be found, they use a genetic algorithm to select a tree that is coherent enough for people to understand (local optimum). The problem of finding an acceptable order- ing does not arise solely in concept-to-text gener- ation but also in the emerging field of text-to-text generation (Barzilay, 2003). Examples of applica- tions that require some form of text structuring, are single- and multidocument summarization as well as question answering. Note that these applications do not typically assume rich semantic knowledge orga- nized in tree-like structures or communicative goals as is often the case in concept-to-text generation. Al- though in single document summarization the posi- tion of a sentence in a document can provide cues with respect to its ordering in the summary, this is not the case in multidocument summarization where sentences are selected from different documents …

Content truncated to 500 words