Optimizing an Approximation of ROUGE - a Problem-Reduction Approach to Extractive Multi-Document Summarization

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 1825–1836, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Optimizing an Approximation of ROUGE – a Problem-Reduction Approach to Extractive Multi-Document Summarization Maxime Peyrard and Judith Eckle-Kohler Research Training Group AIPHES and UKP Lab Computer Science Department, Technische Universit¨at Darmstadt www.aiphes.tu-darmstadt.de, www.ukp.tu-darmstadt.de Abstract This paper presents a problem-reduction approach to extractive multi-document summarization: we propose a reduction to the problem of scoring individual sen- tences with their ROUGE scores based on supervised learning. For the summariza- tion, we solve an optimization problem where the ROUGE score of the selected summary sentences is maximized. To this end, we derive an approximation of the ROUGE-N score of a set of sentences, and define a principled discrete optimization problem for sentence selection. Mathe- matical and empirical evidence suggests that the sentence selection step is solved almost exactly, thus reducing the problem to the sentence scoring task. We perform a detailed experimental evaluation on two DUC datasets to demonstrate the validity of our approach. 1 Introduction Multi-document summarization (MDS) is the task of constructing a summary from a topically re- lated document collection. This paper focuses on the variant of extractive and generic MDS, which has been studied in detail for the news domain us- ing available benchmark datasets from the Docu- ment Understanding Conference (DUC) (Over et al., 2007). Extractive MDS can be cast as a budgeted sub- set selection problem (McDonald, 2007; Lin and Bilmes, 2011) where the document collection is considered as a set of sentences and the task is to select a subset of the sentences under a length constraint. State-of-the-art and recent works in extractive MDS solve this discrete optimization problem using integer linear programming (ILP) or submodular function maximization (Gillick and Favre, 2009; Mogren et al., 2015; Li et al., 2013b; Kulesza and Taskar, 2012; Hong and Nenkova, 2014). The objective function that is maximized in the optimization step varies considerably in pre- vious work. For instance, Yih et al. (2007) maxi- mize the number of informative words, Gillick and Favre (2009) the coverage of particular concepts, and others maximize a notion of “summary wor- thiness”, while minimizing summary redundancy (Lin and Bilmes, 2011; K˚ageb¨ack et al., 2014). There are also multiple approaches which max- imize the evaluation metric for system sum- maries itself based on supervised Machine Learn- ing (ML). System summaries are commonly eval- uated using ROUGE (Lin, 2004), a recall oriented metric that measures the n-gram overlap between a system summary and a set of human-written ref- erence summaries. The benchmark datasets for MDS can be em- ployed in two different ways for supervised learn- ing of ROUGE scores: either by training a model that assigns ROUGE scores to individual tex- tual units (e.g., sentences), or by performing structured output learning and directly maximiz- ing the ROUGE scores of the created summaries (Nishikawa et al., 2014; Takamura and Okumura, 2010; Sipos et al., 2012). The latter approach suf- fers both …

Content truncated to 500 words