Fast Joint Compression and Summarization via Graph Cuts

Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 1492–1502, Seattle, Washington, USA, 18-21 October 2013. c⃝2013 Association for Computational Linguistics Fast Joint Compression and Summarization via Graph Cuts Xian Qian and Yang Liu The University of Texas at Dallas 800 W. Campbell Rd., Richardson, TX, USA {qx,yangl}@hlt.utdallas.edu Abstract Extractive summarization typically uses sen- tences as summarization units. In contrast, joint compression and summarization can use smaller units such as words and phrases, re- sulting in summaries containing more infor- mation. The goal of compressive summariza- tion is to find a subset of words that max- imize the total score of concepts and cut- ting dependency arcs under the grammar con- straints and summary length constraint. We propose an efficient decoding algorithm for fast compressive summarization using graph cuts. Our approach first relaxes the length con- straint using Lagrangian relaxation. Then we propose to bound the relaxed objective func- tion by the supermodular binary quadratic pro- gramming problem, which can be solved ef- ficiently using graph max-flow/min-cut. S- ince finding the tightest lower bound suffers from local optimality, we use convex relax- ation for initialization. Experimental results on TAC2008 dataset demonstrate our method achieves competitive ROUGE score and has good readability, while is much faster than the integer linear programming (ILP) method. 1 Introduction Automatic multi-document summarization helps readers get the most important information from large amounts of texts. Summarization techniques can be roughly divided into two categories: extrac- tive and abstractive. Extractive summarization casts the summarization task as a sentence selection prob- lem: identifying important summary sentences from one or multiple documents. Many methods have been developed in the past decades, including super- vised approaches that use classifiers to predict sum- mary sentences, graph based approaches to rank the sentences, and recent global optimization methods such as integer linear programming (Gillick et al., 2008) (ILP) and submodular maximization methods (Lin and Bilmes, 2011). Though extractive summa- rization is popular because of its simplicity and high readability, it has limitations in that it selects each sentence as a whole, and thus may miss informative partial sentences. To improve the informativeness, joint com- pression and summarization was proposed (Berg- Kirkpatrick et al., 2011), which uses words as sum- marization units, unlike extractive summarization where each sentence is a basic undecomposable u- nit. To achieve better readability, manually defined grammar constraints or automatically learned mod- els based on syntax trees are added during the sum- marization process. Up to now, the state of the art compressive systems are based on integer linear pro- gramming (ILP). Because ILP suffers from expo- nential complexity, word-based compression sum- marization is an order of magnitude slower than sentence-based extraction. One common way to solve an ILP problem is to use its LP relaxation and round the results. How- ever Berg-Kirkpatrick et al. (2011) found that LP relaxation gave poor results, finding unacceptably suboptimal solutions. For speedup, they proposed a two stage method where they performed some sen- tence selection in the first …

Content truncated to 500 words