Finding topic words for hierarchical summarization

ABSTRACT

Hierarchies have long been used for organization, summarization, and access to information. In this paper we define summarization in terms of a probabilistic language model and use the definition to explore a new technique for automatically generating topic hierarchies by applying a graph-theoretic algorithm, which is an approximation of the Dominating Set Problem. The algorithm efficiently chooses terms according to a language model. We compare the new technique to previous methods proposed for constructing topic hierarchies including subsumption and lexical hierarchies, as well as the top TF.IDF terms. Our results show that the new technique consistently performs as well as or better than these other techniques. They also show the usefulness of hierarchies compared with a list of terms.

REFERENCES

• 1: Peter G. Anick , Suresh Tipirneni, The paraphrase search assistant: terminological feedback for iterative information seeking, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.153-159, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312670]
• 2: Adam L. Berger , Vibhu O. Mittal, OCELOT: a system for summarizing Web pages, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.144-151, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345565]
• 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: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 5: M. Hearst. User interfaces and visualization. In R. Baeza-Yates and B. Riberio-Neto, editors, Modern Information Retrieval, pages 257-323. ACM Press Series, 1999.
• 6: Victor Lavrenko , W. Bruce Croft, Relevance based language models, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.120-127, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383972]
• 7: D. Lawrie and W. Croft. Discovering and comparing topic hierarchies. In Proceedings of RIAO 2000 Conference, pages 314-330, 2000.
• 8: H. Lowe and G. Barnett. Understanding and using the medical subject headings (mesh) vocabulary to perform literature searches. Journal of the American Medical Association, 271(4):1103-1108, 1994.
• 9: Kathleen R. McKeown , Judith L. Klavans , Vasileios Hatzivassiloglou , Regina Barzilay , Eleazar Eskin, Towards multidocument summarization by reformulation: progress and prospects, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.453-460, July 18-22, 1999, Orlando, Florida, United States
• 10: C. Nevill-Manning, I. Witten, and G. Paynter. Lexically-generated subject hierarchies for browsing large collections. International Journal on Digital Libraries, 2(2+3):111-123, 1999.
• 11: Dragomir R. Radev , Hongyan Jing , Malgorzata Budzikowska, Centroid-based summarization of multiple documents: sentence extraction, utility-based evaluation, and user studies, NAACL-ANLP 2000 Workshop on Automatic summarization, p.21-30, April 30-30, 2000, Seattle, Washington [doi>10.3115/1117575.1117578]
• 12: Gerard Salton , Michael J. McGill, Introduction to Modern Information Retrieval, McGraw-Hill, Inc., New York, NY, 1986
• 13: Mark Sanderson , Bruce Croft, Deriving concept hierarchies from text, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.206-213, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312679]
• 14: G. Stein, T. Strzalkowski, G. B. Wise, and A. Bagga. Evaluating summaries for multiple documents in an interactive environment. In LREC, 2000.
• 15: C. J. Van Rijsbergen, Information Retrieval, Butterworth-Heinemann, Newton, MA, 1979
• 16: E. M. Voorhees and D. K. Harman, editors. The Sixth Text REtrieval Conference (TREC-6). Department of Commerce, National Institute of Standards and Technology, 1997.
• 17: Ian H. Witten , Gordon W. Paynter , Eibe Frank , Carl Gutwin , Craig G. Nevill-Manning, KEA: practical automatic keyphrase extraction, Proceedings of the fourth ACM conference on Digital libraries, p.254-255, August 11-14, 1999, Berkeley, California, United States [doi>10.1145/313238.313437]
• 18: Jinxi Xu , W. Bruce Croft, Query expansion using local and global document analysis, Proceedings of the 19th annual international ACM SIGIR conference on Research and development in information retrieval, p.4-11, August 18-22, 1996, Zurich, Switzerland [doi>10.1145/243199.243202]
• 19: YAHOO. Yahoo. www.yahoo.com.

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Algorithms, Design, Experimentation, Performance