Using Supervised Bigram-based ILP for Extractive Summarization

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 1004–1013, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Using Supervised Bigram-based ILP for Extractive Summarization Chen Li, Xian Qian, and Yang Liu The University of Texas at Dallas Computer Science Department chenli,qx,yangl@hlt.utdallas.edu Abstract In this paper, we propose a bigram based supervised method for extractive docu- ment summarization in the integer linear programming (ILP) framework. For each bigram, a regression model is used to es- timate its frequency in the reference sum- mary. The regression model uses a vari- ety of indicative features and is trained dis- criminatively to minimize the distance be- tween the estimated and the ground truth bigram frequency in the reference sum- mary. During testing, the sentence selec- tion problem is formulated as an ILP prob- lem to maximize the bigram gains. We demonstrate that our system consistently outperforms the previous ILP method on different TAC data sets, and performs competitively compared to the best results in the TAC evaluations. We also con- ducted various analysis to show the im- pact of bigram selection, weight estima- tion, and ILP setup. 1 Introduction Extractive summarization is a sentence selection problem: identifying important summary sen- tences from one or multiple documents. Many methods have been developed for this problem, in- cluding supervised approaches that use classifiers to predict summary sentences, graph based ap- proaches to rank the sentences, and recent global optimization methods such as integer linear pro- gramming (ILP) and submodular methods. These global optimization methods have been shown to be quite powerful for extractive summarization, because they try to select important sentences and remove redundancy at the same time under the length constraint. Gillick and Favre (Gillick and Favre, 2009) in- troduced the concept-based ILP for summariza- tion. Their system achieved the best result in the TAC 09 summarization task based on the ROUGE evaluation metric. In this approach the goal is to maximize the sum of the weights of the lan- guage concepts that appear in the summary. They used bigrams as such language concepts. The as- sociation between the language concepts and sen- tences serves as the constraints. This ILP method is formally represented as below (see (Gillick and Favre, 2009) for more details): max � i wici (1) s.t. sjOccij ≤ ci (2) � j sjOccij ≥ ci (3) � j ljsj ≤ L (4) ci ∈ {0, 1} ∀i (5) sj ∈ {0, 1} ∀j (6) ci and sj are binary variables (shown in (5) and (6)) that indicate the presence of a concept and a sentence respectively. wi is a concept’s weight and Occij means the occurrence of concept i in sentence j. Inequalities (2)(3) associate the sen- tences and concepts. They ensure that selecting a sentence leads to the selection of all the concepts it contains, and selecting a concept only happens when it is present in at least one of the selected sentences. There are two important components in this concept-based ILP: one …

Content truncated to 500 words