Multiple Aspect Summarization Using Integer Linear Programming

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 233–243, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics Multiple Aspect Summarization Using Integer Linear Programming Kristian Woodsend and Mirella Lapata Institute for Language, Cognition and Computation School of Informatics, University of Edinburgh 10 Crichton Street, Edinburgh EH8 9AB k.woodsend@ed.ac.uk, mlap@inf.ed.ac.uk Abstract Multi-document summarization involves many aspects of content selection and sur- face realization. The summaries must be informative, succinct, grammatical, and obey stylistic writing conventions. We present a method where such individual aspects are learned separately from data (without any hand-engineering) but optimized jointly using an integer linear programme. The ILP framework allows us to combine the decisions of the expert learners and to select and rewrite source content through a mixture of objective setting, soft and hard constraints. Experimental results on the TAC-08 data set show that our model achieves state-of-the-art performance using ROUGE and signifi- cantly improves the informativeness of the summaries. 1 Introduction Automatic summarization has enjoyed wide popu- larity in natural language processing (see the pro- ceedings of the Document Understanding and Text Analysis conferences) due to its potential for prac- tical applications but also because it incorporates many important aspects of both natural language un- derstanding and generation. Of the many summa- rization paradigms that have been identified over the years (see Sparck Jones (1999) and Mani (2001) for comprehensive overviews), multi-document sum- marization — the task of producing summaries from clusters of thematically related documents — has consistently attracted attention. Despite considerable research effort, the auto- matic generation of multi-document summaries that resemble those written by humans remains chal- lenging. This is primarily due to the task itself which is complex and subject to several constraints: the summary must be maximally informative and minimally redundant, grammatical, coherent, adhere to a pre-specified length and stylistic conventions. An ideal model would learn to output summaries that simultaneously meet all these constraints from data (i.e., document clusters and their correspond- ing summaries). This global inference problem is, however, hard — the solution space is large and the lack of easily accessible datasets an obstacle to joint learning. It is thus no surprise that previous work has focused on specific aspects of joint learning. Initial global formulations of the multi-document summarization task focused on extractive summa- rization and used approximate greedy algorithms for finding the sentences of the summary. Goldstein et al. (2000) search for the set of sentences that are both relevant and non-redundant, whereas Filatova and Hatzivassiloglou (2004) model multi-document summarization as an instance of the maximum cov- erage set problem.1 More recent work improves on the search problem by considering exact solutions and permits a limited amount of rewriting. McDon- ald (2007) proposes an integer linear programming formulation that maximizes the sum of relevance scores of the selected sentences penalized by the 1Given C, a finite set of weighted elements, a collection T of subsets ofC, and an integer k, find those …

Content truncated to 500 words