Concept-based Summarization using Integer Linear Programming: From Concept Pruning to Multiple Optimal Solutions

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1914–1918, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Concept-based Summarization using Integer Linear Programming: From Concept Pruning to Multiple Optimal Solutions Florian Boudin1 Hugo Mougard1 Benoit Favre2 1 LINA - UMR CNRS 6241, Universit´e de Nantes, France {florian.boudin,hugo.mougard}@univ-nantes.fr 2 LIF - UMR CNRS 7279, Universit´e Aix-Marseille, France benoit.favre@lif.univ-mrs.fr Abstract In concept-based summarization, sentence selection is modelled as a budgeted maxi- mum coverage problem. As this problem is NP-hard, pruning low-weight concepts is required for the solver to find optimal solutions efficiently. This work shows that reducing the number of concepts in the model leads to lower ROUGE scores, and more importantly to the presence of mul- tiple optimal solutions. We address these issues by extending the model to provide a single optimal solution, and eliminate the need for concept pruning using an approx- imation algorithm that achieves compara- ble performance to exact inference. 1 Introduction Recent years have witnessed increased interest in global inference methods for extractive summa- rization. These methods formulate summarization as a combinatorial optimization problem, i.e. se- lecting a subset of sentences that maximizes an objective function under a length constraint, and use Integer Linear Programming (ILP) to solve it exactly (McDonald, 2007). In this work, we focus on the concept-based ILP model for summarization introduced by (Gillick and Favre, 2009). In their model, a summary is generated by assembling the subset of sentences that maximizes a function of the unique concepts it covers. Selecting the optimal subset of sentences is then cast as an instance of the budgeted maxi- mum coverage problem1. As this problem is NP-hard, pruning low-weight concepts is required for the ILP solver to find opti- mal solutions efficiently (Gillick and Favre, 2009; 1Given a collection S of sets with associated costs and a budget L, find a subset S′ ⊆ S such that the total cost of sets in S′ does not exceed L, and the total weight of elements covered by S′ is maximized (Khuller et al., 1999). Qian and Liu, 2013; Li et al., 2013). However, re- ducing the number of concepts in the model has two undesirable consequences. First, it forces the model to only use a limited number of concepts to rank summaries, resulting in lower ROUGE scores. Second, by reducing the number of items from which sentence scores are derived, it allows dif- ferent sentences to have the same score, and ulti- mately leads to multiple optimal summaries. To our knowledge, no previous work has men- tioned these problems, and only results corre- sponding to the first optimal solution found by the solver are reported. However, as we will show through experiments, these multiple optimal so- lutions cause a substantial amount of variation in ROUGE scores, which, if not accounted for, could lead to incorrect conclusions. More specifically, the contributions of this work are as follows: • We evaluate (Gillick and Favre, 2009)’s sum- marization model at various concept pruning levels. …

Content truncated to 500 words