emnlp emnlp2013 emnlp2013-85 emnlp2013-85-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Xian Qian ; Yang Liu
Abstract: Extractive summarization typically uses sentences as summarization units. In contrast, joint compression and summarization can use smaller units such as words and phrases, resulting in summaries containing more information. The goal of compressive summarization is to find a subset of words that maximize the total score of concepts and cutting dependency arcs under the grammar constraints and summary length constraint. We propose an efficient decoding algorithm for fast compressive summarization using graph cuts. Our approach first relaxes the length constraint using Lagrangian relaxation. Then we propose to bound the relaxed objective function by the supermodular binary quadratic programming problem, which can be solved efficiently using graph max-flow/min-cut. Since finding the tightest lower bound suffers from local optimality, we use convex relaxation 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.
A. Aker and R. Gaizauskas. 2009. Summary generation for toponym-referenced images using object type language models. In Proceedings of RANLP. Miguel Almeida and Andre Martins. 2013. Fast and robust compressive summarization with dual decomposition and multi-task learning. In Proceedings of ACL, pages 196–206, August. Taylor Berg-Kirkpatrick, Dan Gillick, and Dan Klein. 2011. Jointly learning to extract and compress. In Proceedings of ACL-HLT, pages 481–490, June. A. Billionnet and M. Minoux. 1985. Maximizing a supermodular pseudoboolean function: A polynomial algorithm for supermodular cubic functions. Discrete Applied Mathematics, 12(1): 1 11. – Endre Boros and Peter L. Hammer. 2002. Pseudoboolean optimization. Discrete Applied Mathematics, 123(1C3): 155 225. Ronald Brandow, Karl Mitze, and Lisa F. Rau. 1995. Automatic condensation of electronic publications by sentence selection. Information Processing & Management, 3 1(5):675 685. Yllias Chali and Sadid A. Hasan. 2012. On the effectiveness of using sentence compression models for queryfocused multi-document summarization. In COLING, pages 457–474. James Clarke and Mirella Lapata. 2008. Global inference for sentence compression: An integer linear programming approach. J. Artif. Intell. Res. (JAIR), 31:399–429. John Duchi, Shai Shalev-Shwartz, Yoram Singer, and Tushar Chandra. 2008. Efficient projections onto the L1-ball for learning in high dimensions. In Proceedings of ICML, pages 272–279. Jack Edmonds and Richard M. Karp. 1972. Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM, 19(2):248–264, April. H. P. Edmundson. 1969. New methods in automatic extracting. J. ACM, 16(2):264–285, April. Daniel Freedman and Petros Drineas. 2005. Energy minimization via graph cuts: Settling what is possible. In CVPR (2), pages 939–946. Dan Gillick and Benoit Favre. 2009. A scalable global – – model for summarization. In Proceedings of the Workshop on Integer Linear Programming for Natural Language Processing, pages 10–18, June. Dan Gillick, Benoit Favre, and Dilek Hakkani-Tur. 2008. The ICSI summarization system at tac 2008. In Proceedings of the Text Understanding Conference. Matthew R. Gormley and Jason Eisner. 2013. Nonconvex global optimization for latent-variable models. In Proceedings of ACL, pages 444–454, August. Vladimir Kolmogorov and Ramin Zabih. 2004. What energy functions can be minimized via graph cuts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 26:65–81 . 1502 Terry Koo, Alexander M. Rush, Michael Collins, Tommi Jaakkola, and David Sontag. 2010. Dual decomposition for parsing with non-projective head automata. In Proceedings of EMNLP 2010, pages 1288–1298, October. Chen Li, Fei Liu, Fuliang Weng, and Yang Liu. 2013a. Document summarization via guided sentence compression. In Proceedings of EMNLP (to appear), October. Chen Li, Xian Qian, and Yang Liu. 2013b. Using supervised bigram-based ILP for extractive summarization. In Proceedings of ACL, pages 1004–1013, August. Hui Lin and Jeff Bilmes. 2011. A class of submodular functions for document summarization. In Proceedings of ACL, pages 5 10–520, June. Fei Liu and Yang Liu. 2009. From extractive to abstractive meeting summaries: Can it be done by sentence compression? In Proceedings of ACL-IJCNLP 2009, pages 261–264, August. Andr e´ F. T. Martins and Noah A. Smith. 2009. Summarization with a joint model for sentence extraction and compression. In Proceedings of the Workshop on Integer Linear Programming for Natural Langauge Processing, ILP ’09, pages 1–9. Kiyohito Nagano, Yoshinobu Kawahara, and Kazuyuki Aihara. 2011. Size-constrained submodular minimization through minimum norm base. In ICML, pages 977–984. Xian Qian and Yang Liu. 2013. Branch and bound algorithm for dependency parsing with non-local features. TACL, 1: 105–151. Dragomir R. Radev. 2001. Experiments in single and multidocument summarization using mead. In In First Document Understanding Conference. Kristian Woodsend and Mirella Lapata. 2012. Multiple aspect summarization using integer linear programming. In Proceedings of EMNLP-CoNLL, pages 233–243, July.