Summarization Through Submodularity and Dispersion

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 1014–1022, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Summarization Through Submodularity and Dispersion Anirban Dasgupta Yahoo! Labs Sunnyvale, CA 95054 anirban@yahoo-inc.com Ravi Kumar Google Mountain View, CA 94043 tintin@google.com Sujith Ravi Google Mountain View, CA 94043 sravi@gooogle.com Abstract We propose a new optimization frame- work for summarization by generalizing the submodular framework of (Lin and Bilmes, 2011). In our framework the sum- marization desideratum is expressed as a sum of a submodular function and a non- submodular function, which we call dis- persion; the latter uses inter-sentence dis- similarities in different ways in order to ensure non-redundancy of the summary. We consider three natural dispersion func- tions and show that a greedy algorithm can obtain an approximately optimal sum- mary in all three cases. We conduct ex- periments on two corpora—DUC 2004 and user comments on news articles—and show that the performance of our algo- rithm outperforms those that rely only on submodularity. 1 Introduction Summarization is a classic text processing prob- lem. Broadly speaking, given one or more doc- uments, the goal is to obtain a concise piece of text that contains the most salient points in the given document(s). Thanks to the om- nipresent information overload facing all of us, the importance of summarization is gaining; semi- automatically summarized content is increasingly becoming user-facing: many newspapers equip editors with automated tools to aid them in choos- ing a subset of user comments to show. Summa- rization has been studied for the past in various settings—a large single document, multiple docu- ments on the same topic, and user-generated con- tent. Each domain throws up its own set of idiosyn- crasies and challenges for the summarization task. On one hand, in the multi-document case (say, dif- ferent news reports on the same event), the text is often very long and detailed. The precision/recall requirements are higher in this domain and a se- mantic representation of the text might be needed to avoid redundancy. On the other hand, in the case of user-generated content (say, comments on a news article), even though the text is short, one is faced with a different set of problems: volume (popular articles generate more than 10,000 com- ments), noise (most comments are vacuous, lin- guistically deficient, and tangential to the article), and redundancy (similar views are expressed by multiple commenters). In both cases, there is a delicate balance between choosing the salient, rel- evant, popular, and diverse points (e.g., sentences) versus minimizing syntactic and semantic redun- dancy. While there have been many approaches to au- tomatic summarization (see Section 2), our work is directly inspired by the recent elegant frame- work of (Lin and Bilmes, 2011). They employed the powerful theory of submodular functions for summarization: submodularity embodies the “di- minishing returns” property and hence is a natural vocabulary to express the summarization desider- ata. In this framework, each of the constraints (rel- evance, redundancy, etc.) is captured as …

Content truncated to 500 words