Mining the web for answers to natural language questions

ABSTRACT

The web is now becoming one of the largest information and knowledge repositories. Many large scale search engines (Google, Fast, Northern Light, etc.) have emerged to help users find information. In this paper, we study how we can effectively use these existing search engines to mine the Web and discover the "correct" answers to factual natural language questions.We propose a probabilistic algorithm called QASM (Question Answering using Statistical Models) that learns the best query paraphrase of a natural language question. We validate our approach for both local and web search engines using questions from the TREC evaluation. We also show how this algorithm can be combined with another algorithm (AnSel) to produce precise answers to natural language questions.

REFERENCES

• 1: The Fast search engine. http://www.alltheweb.com, 2001.
• 2: Michele Banko , Vibhu O. Mittal , Michael J. Witbrock, Headline generation based on statistical translation, Proceedings of the 38th Annual Meeting on Association for Computational Linguistics, p.318-325, October 03-06, 2000, Hong Kong [doi>10.3115/1075218.1075259]
• 3: Adam L. Berger , Peter F. Brown , Stephen A. Della Pietra , Vincent J. Della Pietra , John R. Gillett , John D. Lafferty , Robert L. Mercer , Harry Printz , Luboš Ureš, The Candide system for machine translation, Proceedings of the workshop on Human Language Technology, March 08-11, 1994, Plainsboro, NJ [doi>10.3115/1075812.1075844]
• 4: Adam Berger , John Lafferty, Information retrieval as statistical translation, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.222-229, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312681]
• 5: Peter F. Brown , John Cocke , Stephen A. Della Pietra , Vincent J. Della Pietra , Fredrick Jelinek , John D. Lafferty , Robert L. Mercer , Paul S. Roossin, A statistical approach to machine translation, Computational Linguistics, v.16 n.2, p.79-85, June 1990
• 6: Peter F. Brown , Vincent J. Della Pietra , Stephen A. Della Pietra , Robert L. Mercer, The mathematics of statistical machine translation: parameter estimation, Computational Linguistics, v.19 n.2, June 1993
• 7: Kenneth Ward Church, A stochastic parts program and noun phrase parser for unrestricted text, Proceedings of the second conference on Applied natural language processing, February 09-12, 1988, Austin, Texas [doi>10.3115/974235.974260]
• 8: A. P. Dempster, N. M. Laird, and D. B. Rubin. Maximum likelihood from incomplete data via the EM algorithm (with discussion). Journal of the Royal Statistical Society series B, 39: l-38, 1977.
• 9: The Excite query corpus. ftp:Nftp.excite.comlpub/jack/Excite-Log-l2201999.gz, 1999.
• 10: Eric J. Glover , Steve Lawrence , Michael D. Gordon , William P. Birmingham , C. Lee Giles, Web Search---Your Way, Communications of the ACM, v.44 n.12, p.97-102, December 2001 [doi>10.1145/501317.501319]
• 11: S. Harabagiu, D. Moldovan, M. Pasta, R. Mihalcea, M. Surdeanu, R. Bunescu, R. Girju, V. Rus, and P. Morarescu. The TREC-9 question answering track evaluation. In Text Retrieval Conference TREC-9, Gaithersburg, MD, 200 1.
• 12: Frederick Jelinek, Statistical methods for speech recognition, MIT Press, Cambridge, MA, 1998
• 13: Kevin Knight , Jonathan Graehl, Machine transliteration, Computational Linguistics, v.24 n.4, p.599-612, December 1998
• 14: K. Knight and D. Marcu. Statistics-based summarization -step one: sentence compression. In Proceedings, Seventeenth Annual Conference of the American Association for ArtiJicial Intelligence, Austin, Texas, August 2000.
• 15: Christopher D. Manning , Hinrich Schütze, Foundations of statistical natural language processing, MIT Press, Cambridge, MA, 1999
• 16: A. Mikheev. Tagging sentence boundaries. In Proceedings, SIGIR 2000,200O.
• 17: G. A. Miller, R. Beckwith, C. Fellbaum, D. Gross, and K. J. Miller. Introduction to WordNet: An on-line lexical database. International Journal of Lexicography (special issue), 3(4):235-312, 1990.
• 18: Mandar Mitra , Amit Singhal , Chris Buckley, Improving automatic query expansion, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.206-214, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.290995]
• 19: Fernando Pereira , Naftali Tishby , Lillian Lee, Distributional clustering of English words, Proceedings of the 31st annual meeting on Association for Computational Linguistics, p.183-190, June 22-26, 1993, Columbus, Ohio [doi>10.3115/981574.981598]
• 20: Jay M. Ponte , W. Bruce Croft, A language modeling approach to information retrieval, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.275-281, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291008]
• 21: John Prager , Eric Brown , Anni Coden , Dragomir Radev, Question-answering by predictive annotation, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.184-191, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345574]
• 22: D. R. Radev, K. Libner, and W. Fan. An empirical evaluation of the capability of state-of-the-art search engines to answer natural language questions. Submitted, 2001.
• 23: Dragomir R. Radev , John Prager , Valerie Samn, Ranking suspected answers to natural language questions using predictive annotation, Proceedings of the sixth conference on Applied natural language processing, p.150-157, April 29-May 04, 2000, Seattle, Washington [doi>10.3115/974147.974168]
• 24: E. Voorhees and D. Tice. The TREC-8 question answering track evaluation. In Text Retrieval Conference TREC-8, Gaithersburg, MD, 2000.

INDEX TERMS

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

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

          Nouns: World Wide Web (WWW)

General Terms:
Algorithms, Design, Languages