Multi-document summarization via sentence-level semantic analysis and symmetric matrix factorization

ABSTRACT

Multi-document summarization aims to create a compressed summary while retaining the main characteristics of the original set of documents. Many approaches use statistics and machine learning techniques to extract sentences from documents. In this paper, we propose a new multi-document summarization framework based on sentence-level semantic analysis and symmetric non-negative matrix factorization. We first calculate sentence-sentence similarities using semantic analysis and construct the similarity matrix. Then symmetric matrix factorization, which has been shown to be equivalent to normalized spectral clustering, is used to group sentences into clusters. Finally, the most informative sentences are selected from each group to form the summary. Experimental results on DUC2005 and DUC2006 data sets demonstrate the improvement of our proposed framework over the implemented existing summarization systems. A further study on the factors that benefit the high performance is also conducted.

REFERENCES

• 1: http://www-nlpir.nist.gov/projects/duc/pubs/.
• 2: Massih-Reza Amini , Patrick Gallinari, The use of unlabeled data to improve supervised learning for text summarization, 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.564397]
• 3: D. Arnold, L. Balkan, S. Meijer, R. Humphreys, and L. Sadler. Machine Translation: an Introductory Guide. Blackwells-NCC, 1994.
• 4: Christopher M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 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: Inderjit S. Dhillon, Co-clustering documents and words using bipartite spectral graph partitioning, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.269-274, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502550]
• 7: Chris Ding , Xiaofeng He, K-means clustering via principal component analysis, Proceedings of the twenty-first international conference on Machine learning, p.29, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015408]
• 8: Chris Ding , Tao Li , Wei Peng , Haesun Park, Orthogonal nonnegative matrix t-factorizations for clustering, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150420]
• 9: G. Erkan and D. Radev. Lexpagerank: Prestige in multi-document text summarization. In Proceedings of EMNLP 2004.
• 10: C. Fellbaum. WordNet: An Electronic Lexical Database. MIT Press, 1998.
• 11: Jade Goldstein , Mark Kantrowitz , Vibhu Mittal , Jaime Carbonell, Summarizing text documents: sentence selection and evaluation metrics, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.121-128, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312665]
• 12: 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]
• 13: 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]
• 14: T. Hirao, Y. Sasaki, and H. Isozaki. An extrinsic evaluation for question-biased text summarization on qa tasks. In Prodeedings of NAACL 2001 workshop on Automatic Summarization.
• 15: Hongyan Jing , Kathleen R. McKeown, Cut and paste based text summarization, Proceedings of the first conference on North American chapter of the Association for Computational Linguistics, p.178-185, April 29-May 04, 2000, Seattle, Washington
• 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: D. D. Lee and H. S. Seung. Algorithms for non-negative matrix factorization. In NIPS 2001.
• 18: Tao Li, A general model for clustering binary data, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081894]
• 19: 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]
• 20: Chin-Yew Lin , Eduard Hovy, From single to multi-document summarization: a prototype system and its evaluation, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073160]
• 21: I. Mani. Automatic summarization. John Benjamins Publishing Company, 2001.
• 22: R. Mihalcea and P. Tarau. A language independent algorithm for single and multiple document summarization. In Proceedings of IJCNLP 2005.
• 23: Martha Palmer , Daniel Gildea , Paul Kingsbury, The Proposition Bank: An Annotated Corpus of Semantic Roles, Computational Linguistics, v.31 n.1, p.71-106, March 2005 [doi>10.1162/0891201053630264]
• 24: S. Park, J.-H. Lee, D.-H. Kim, and C.-M. Ahn. Multi-document summarization based on cluster using non-negtive matrix factorization. In Proceedings of SOFSEM 2007.
• 25: Dragomir R. Radev , Eduard Hovy , Kathleen McKeown, Introduction to the special issue on summarization, Computational Linguistics, v.28 n.4, p.399-408, December 2002 [doi>10.1162/089120102762671927]
• 26: Dragomir R. Radev , Hongyan Jing , Małgorzata Styś , Daniel Tam, Centroid-based summarization of multiple documents, Information Processing and Management: an International Journal, v.40 n.6, p.919-938, November 2004 [doi>10.1016/j.ipm.2003.10.006]
• 27: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 28: G. Sampathsampath and M. Martinovic. A Multilevel Text Processing Model of Newsgroup Dynamics. 2002.
• 29: D. Shen, J.-T. Sun, H. Li, Q. Yang, and Z. Chen. Document summarization using conditional random fields. In Proceedings of IJCAI 2007.
• 30: Jianbo Shi , Jitendra Malik, Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.22 n.8, p.888-905, August 2000 [doi>10.1109/34.868688]
• 31: Andrew Turpin , Yohannes Tsegay , David Hawking , Hugh E. Williams, Fast generation of result snippets in web search, 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.1277766]
• 32: X. Wan, J. Yang, and J. Xiao. Manifold-ranking based topic-focused multi-document summarization. In Proceedings of IJCAI 2007.
• 33: W.-T. Yih, J. Goodman, L. Vanderwende, and H. Suzuki. Multi-document summarization by maximizing informative content-words. In Proceedings of IJCAI 2007.
• 34: H. Zha. Generic summarization and keyphrase extraction using mutual reinforcement principle and sentence clustering. In Prodeedings of SIGIR 2005.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Text analysis

General Terms:
Algorithms, Experimentation, Performance

Keywords:
multi-document summarization, sentence-level semantic analysis, symmetric non-negative matrix factorization