Use of ranked cross document evidence trails for hypothesis generation

ABSTRACT

This paper focuses on detecting how concepts are linked across multiple textdocuments by generating an evidence trail explaining the connection. A traditional search involving, for example, two or more person names willattempt to find documents mentioning both of these individuals. This researchfocuses on a different interpretation of such a query: what is the best evidencetrail across documents that explains a connection between these individuals? For example, allmay be good golfers. A generalization ofthis task involves query terms representing general concepts (e.g. indictment,foreign policy). Such queries reflect a special case oftext mining. Previous attempts to solve this problem have focused on graphapproaches involving hyperlinked documents, and link analysis tools exploiting named entities. A new robust framework is presented, based on (i) generating concept chain graphs, a hybrid content representation, (ii) performing graph matching to select candidate subgraphs, and (iii) subsequently using graphical models to validate hypotheses using ranked evidence trails. We adapt the DUC data set for cross-document summarization to evaluate evidence trails generated by this approach.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: Regina Barzilay , Mirella Lapata, Modeling local coherence: an entity-based approach, Proceedings of the 43rd Annual Meeting on Association for Computational Linguistics, p.141-148, June 25-30, 2005, Ann Arbor, Michigan [doi>10.3115/1219840.1219858]
• 3: R. Barzilay and L. Lee. Catching the drift: Probabilistic content models, with applications to generation and summarization. In DM. Susan Dumais and SRoukos, editors, HLT-NAACL 2004: Main Proceedings, pages 113--120, Boston, Massachusetts, USA, 2004. Association for Computational Linguistics.
• 4: Christos Faloutsos , Kevin S. McCurley , Andrew Tomkins, Fast discovery of connection subgraphs, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014068]
• 5: David Gibson , Jon Kleinberg , Prabhakar Raghavan, Inferring Web communities from link topology, Proceedings of the ninth ACM conference on Hypertext and hypermedia : links, objects, time and space---structure in hypermedia systems: links, objects, time and space---structure in hypermedia systems, p.225-234, June 20-24, 1998, Pittsburgh, Pennsylvania, United States [doi>10.1145/276627.276652]
• 6: A. C. Graesser, D. S. McNamara, M. M. Louwerse, and Z. Cai. Coh-metrix: Analysis of text on cohesion and language. Behavior Research Methods, Instruments and Computers, 36: 193--202, 2004.
• 7: 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]
• 8: T.K. Landauer and S. T. Dumais. A solution to plato's problem: The latent semantic analysis theory of the acquisition, induction, and representation of knowledge. Psychological Review, 104:211--240, 1997.
• 9: Lillian Lee, Measures of distributional similarity, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.25-32, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034693]
• 10: Dekang Lin, Using syntactic dependency as local context to resolve word sense ambiguity, Proceedings of the 35th Annual Meeting of the Association for Computational Linguistics and Eighth Conference of the European Chapter of the Association for Computational Linguistics, p.64-71, July 07-12, 1997, Madrid, Spain
• 11: Kurt Mehlhorn, A faster approximation algorithm for the Steiner problem in graphs, Information Processing Letters, v.27 n.3, p.125-128, March 25, 1988 [doi>10.1016/0020-0190(88)90066-X ]
• 12: 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]
• 13: Rohini k. Srihari , Wei Li , Thomas Cornell , Cheng Niu, Infoxtract: A customizable intermediate level information extraction engine, Natural Language Engineering, v.14 n.1, p.33-69, January 2008 [doi>10.1017/S1351324906004116]
• 14: R. K. Srihari, L. Xu, and A. Bhasin. A text mining model for concept chain graphs. In Proceedings of the IJCAI 2007 workshop on Text Mining and LInk Analysis, 2007.
• 15: Padmini Srinivasan, Text mining: generating hypotheses from MEDLINE, Journal of the American Society for Information Science and Technology, v.55 n.5, p.396-413, March 2004 [doi>10.1002/asi.10389]
• 16: D. R. Swanson. Migraine and magnesium: Eleven neglected connections. Perspectives in Biology and Medicine, 31(4):552--557, 1988.
• 17: Xuerui Wang , Natasha Mohanty , Andrew McCallum, Group and topic discovery from relations and text, Proceedings of the 3rd international workshop on Link discovery, p.28-35, August 21-25, 2005, Chicago, Illinois [doi>10.1145/1134271.1134276]
• 18: Sholom Weiss , Nitin Indurkhya , Tong Zhang , Fred Damerau, Text Mining: Predictive Methods for Analyzing Unstructured Information, SpringerVerlag, 2004

INDEX TERMS

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

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

General Terms:
Algorithms, Experimentation, Security

Keywords:
cross document summarization, graph mining, text mining