Enhancing diversity, coverage and balance for summarization through structure learning

ABSTRACT

Document summarization plays an increasingly important role with the exponential growth of documents on the Web. Many supervised and unsupervised approaches have been proposed to generate summaries from documents. However, these approaches seldom simultaneously consider summary diversity, coverage, and balance issues which to a large extent determine the quality of summaries. In this paper, we consider extract-based summarization emphasizing the following three requirements: 1) diversity in summarization, which seeks to reduce redundancy among sentences in the summary; 2) sufficient coverage, which focuses on avoiding the loss of the document's main information when generating the summary; and 3) balance, which demands that different aspects of the document need to have about the same relative importance in the summary. We formulate the extract-based summarization problem as learning a mapping from a set of sentences of a given document to a subset of the sentences that satisfies the above three requirements. The mapping is learned by incorporating several constraints in a structure learning framework, and we explore the graph structure of the output variables and employ structural SVM for solving the resulted optimization problem. Experiments on the DUC2001 data sets demonstrate significant performance improvements in terms of F1 and ROUGE metrics.

REFERENCES

• 1: Ibm many aspects document summarization tool, http://www.alphaworks.ibm.com/tech/manyaspects.
• 2: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Proceedings of the seventh international conference on World Wide Web 7, p.107-117, April 1998, Brisbane, Australia
• 3: Jaime Carbonell , Jade Goldstein, The use of MMR, diversity-based reranking for reordering documents and producing summaries, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.335-336, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291025]
• 4: Charles L.A. Clarke , Maheedhar Kolla , Gordon V. Cormack , Olga Vechtomova , Azin Ashkan , Stefan Büttcher , Ian MacKinnon, Novelty and diversity in information retrieval evaluation, Proceedings of the 31st annual international ACM SIGIR conference on Research and development in information retrieval, July 20-24, 2008, Singapore, Singapore [doi>10.1145/1390334.1390446]
• 5: John M. Conroy , Dianne P. O'leary, Text summarization via hidden Markov models, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.406-407, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.384042]
• 6: Marie desJardins , Eric Eaton , Kiri L. Wagstaff, Learning user preferences for sets of objects, Proceedings of the 23rd international conference on Machine learning, p.273-280, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143879]
• 7: G. ErKan and D. R. Radev. Lexpagerank: Prestige in multi-document text summarization. In EMNLP, Barcelona, Spain, 2004.
• 8: J. Friedman, T. Hastie, and R. Tibshirani. The Elements of Statistical Learning: Data Mining, Inference and Prediction. newblock 2001.
• 9: Jade Goldstein , Vibhu Mittal , Jaime Carbonell , Mark Kantrowitz, Multi-document summarization by sentence extraction, NAACL-ANLP 2000 Workshop on Automatic summarization, p.40-48, April 30-30, 2000, Seattle, Washington [doi>10.3115/1117575.1117580]
• 10: Yihong Gong , Xin Liu, Generic text summarization using relevance measure and latent semantic analysis, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.19-25, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383955]
• 11: Sanda Harabagiu , Finley Lacatusu, Topic themes for multi-document summarization, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076071]
• 12: Hilda Hardy , Nobuyuki Shimizu , Tomek Strzalkowski , Liu Ting , Xinyang Zhang , G. Bowden Wise, Cross-document summarization by concept classification, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564399]
• 13: Hongyan Jing , Kathleen R. McKeown, Cut and paste based text summarization, Proceedings of the 1st North American chapter of the Association for Computational Linguistics conference, p.178-185, April 29-May 04, 2000, Seattle, Washington
• 14: Samir Khuller , Anna Moss , Joseph (Seffi) Naor, The budgeted maximum coverage problem, Information Processing Letters, v.70 n.1, p.39-45, April 01, 1999 [doi>10.1016/S0020-0190(99)00031-9]
• 15: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 16: Kevin Knight , Daniel Marcu, Summarization beyond sentence extraction: a probabilistic approach to sentence compression, Artificial Intelligence, v.139 n.1, p.91-107, July 2002 [doi>10.1016/S0004-3702(02)00222-9]
• 17: Julian Kupiec , Jan Pedersen , Francine Chen, A trainable document summarizer, Proceedings of the 18th annual international ACM SIGIR conference on Research and development in information retrieval, p.68-73, July 09-13, 1995, Seattle, Washington, United States [doi>10.1145/215206.215333]
• 18: Chin-Yew Lin , Eduard Hovy, Automatic evaluation of summaries using N-gram co-occurrence statistics, Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, p.71-78, May 27-June 01, 2003, Edmonton, Canada [doi>10.3115/1073445.1073465]
• 19: D. Metzler and T. Kanungo. Machine learned sentence selection strategies for query-biased summarization. In SIGIR, 2008.
• 20: R. Mihalcea. Language independent extractive summarization. In AAAI, pages 1688--1689, 2005.
• 21: R. Mihalcea and P. Tarau. Textrank: Bringing order into texts. In EMNLP, Barcelona, Spain, 2004.
• 22: Lyndon S. Kennedy , Mor Naaman, Generating diverse and representative image search results for landmarks, Proceeding of the 17th international conference on World Wide Web, April 21-25, 2008, Beijing, China [doi>10.1145/1367497.1367539]
• 23: Tadashi Nomoto , Yuji Matsumoto, A new approach to unsupervised text summarization, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.26-34, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383956]
• 24: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 25: Dou Shen , Zheng Chen , Qiang Yang , Hua-Jun Zeng , Benyu Zhang , Yuchang Lu , Wei-Ying Ma, Web-page classification through summarization, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009035]
• 26: D. Shen, J. T. Sun, H. Li, Q. Yang, and Z. Chen. Document summarization using conditional random fields. In IJCAI, pages 2862--2867, 2007.
• 27: Jian-Tao Sun , Dou Shen , Hua-Jun Zeng , Qiang Yang , Yuchang Lu , Zheng Chen, Web-page summarization using clickthrough data, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076070]
• 28: Ioannis Tsochantaridis , Thorsten Joachims , Thomas Hofmann , Yasemin Altun, Large Margin Methods for Structured and Interdependent Output Variables, The Journal of Machine Learning Research, 6, p.1453-1484, 12/1/2005
• 29: K. Wagsta, M. desJardins, E. Eaton, and J. Montminy. Learning and visualizing user preferences over sets. In AAAI, 2007.
• 30: Xiaojun Wan , Jianwu Yang, CollabSum: exploiting multiple document clustering for collaborative single document summarizations, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277768]
• 31: Yisong Yue , Thorsten Joachims, Predicting diverse subsets using structural SVMs, Proceedings of the 25th international conference on Machine learning, p.1224-1231, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390310]
• 32: Hongyuan Zha, Generic summarization and keyphrase extraction using mutual reinforcement principle and sentence clustering, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564398]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Abstracting methods

General Terms:
Algorithms, Experimentation, Performance

Keywords:
balance, coverage, diversity, structural svm, summarization