Mining the Gaps: Towards Polynomial Summarization

International Joint Conference on Natural Language Processing, pages 655–660, Nagoya, Japan, 14-18 October 2013. Mining the Gaps: Towards Polynomial Summarization Marina Litvak Sami Shamoon College of Engineering Beer Sheva, Israel marinal@sce.ac.il Natalia Vanetik Sami Shamoon College of Engineering Beer Sheva, Israel natalyav@sce.ac.il Abstract The problem of text summarization for a collection of documents is defined as the problem of selecting a small subset of sentences so that the contents and mean- ing of the original document set are pre- served in the best possible way. In this paper we present a linear model for the problem of text summarization1, where a summary preserves the information cover- age as much as possible in comparison to the original document set. We reduce the problem of finding the best summary to the problem of finding the point on a con- vex polytope closest to the given hyper- plane, and solve it efficiently with the help of fractional (polynomial-time) linear pro- gramming. The experimental results show the superiority of our approach over most of the systems participating in the generic multi-document summarization task (Mul- tiLing) of the TAC 2011 competition. 1 Introduction Automated text summarization is an active field of research in various communities like Informa- tion Retrieval (IR), Natural Language Processing (NLP), and Text Mining (TM). Some authors reduce summarization to the maximum coverage problem (Takamura and Oku- mura, 2009; Gillick and Favre, 2009) that, de- spite a great performance, is known as NP- hard (Khuller et al., 1999). Linear Program- ming helps to find an accurate approximated so- lution to this problem and became very popular in summarization field in the last years (Gillick and Favre, 2009; Woodsend and Lapata, 2010; Hi- toshi Nishikawa and Kikui, 2010; Makino et al., 1This work was partially funded by U.S. Department of Navy, Office of Naval Research. 2011). However, most mentioned works use ex- ponential number of constrains or Integer Linear Programming which is an NP-hard problem. Trying to solve a trade-off between summary quality and time complexity, we propose a novel summarization model solving the approximated maximum coverage problem by linear program- ming in polynomial time. We measure informa- tion coverage by terms2 and strive to obtain a sum- mary that preserves the optimal value of the cho- sen objective function as much as possible in com- parison to the original document. Various objec- tive functions combining different parameters like term’s position and its frequency are introduced and evaluated. Our method ranks and extracts significant sen- tences into a summary and it can be generalized for both single-document and multi-document summarization. Also, it can be easily adapted to cross-lingual/multilingual summarization. Formally speaking, in this paper we introduce (1) a novel text representation model expanding a classic Vector Space Model (Salton et al., 1975) to Hyperplane and Half-spaces, (2) re-formulated extractive summarization problem as an optimiza- tion task and (3) its solution using linear or quadratic programming. The main challenge of this paper is a new text representation model mak- ing possible to represent an …

Content truncated to 500 words