Learning to find answers to questions on the Web

ABSTRACT

We introduce a method for learning to find documents on the Web that contain answers to a given natural language question. In our approach, questions are transformed into new queries aimed at maximizing the probability of retrieving answers from existing information retrieval systems. The method involves automatically learning phrase features for classifying questions into different types, automatically generating candidate query transformations from a training set of question/answer pairs, and automatically evaluating the candidate transformations on target information retrieval systems such as real-world general purpose search engines. At run-time, questions are transformed into a set of queries, and reranking is performed on the documents retrieved. We present a prototype search engine, Tritus, that applies the method to Web search engines. Blind evaluation on a set of real queries from a Web search engine log shows that the method significantly outperforms the underlying search engines, and outperforms a commercial search engine specializing in question answering. Our methodology cleanly supports combining documents retrieved from different search engines, resulting in additional improvement with a system that combines search results from multiple Web search engines.

REFERENCES

• 1: Steven Abney , Michael Collins , Amit Singhal, Answer extraction, Proceedings of the sixth conference on Applied natural language processing, p.296-301, April 29-May 04, 2000, Seattle, Washington [doi>10.3115/974147.974188]
• 2: Eugene Agichtein , Steve Lawrence , Luis Gravano, Learning search engine specific query transformations for question answering, Proceedings of the 10th international conference on World Wide Web, p.169-178, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371976]
• 3: Diego Molla-Aliod , Jawad Berri , Michael Hess, A Real World Implementation of Answer Extraction, Proceedings of the 9th International Workshop on Database and Expert Systems Applications, p.143, August 26-28, 1998
• 4: Adam Berger , Rich Caruana , David Cohn , Dayne Freitag , Vibhu Mittal, Bridging the lexical chasm: statistical approaches to answer-finding, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.192-199, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345576]
• 5: Eric Brill, A simple rule-based part of speech tagger, Proceedings of the third conference on Applied natural language processing, March 31-April 03, 1992, Trento, Italy [doi>10.3115/974499.974526]
• 6: Brill, E., Lin, J., Banko, M., Dumais, S., and Ng, A. 2001. Data-intensive question answering. In Proceedings of the TREC-10 Question Answering Track. 393--400.
• 7: Sergey Brin , Lawrence Page, The anatomy of a large-scale hypertextual Web search engine, Computer Networks and ISDN Systems, v.30 n.1-7, p.107-117, April 1, 1998
• 8: Burke, R., Hammond, K., and Kozlovsky, J. 1995. Knowledge-based information retrieval for semi-structured text. In AAAI Fall Symposium on AI Applications in Knowledge Navigation and Retrieval. 19--24.
• 9: Claire Cardie , Vincent Ng , David Pierce , Chris Buckley, Examining the role of statistical and linguistic knowledge sources in a general-knowledge question-answering system, Proceedings of the sixth conference on Applied natural language processing, p.180-187, April 29-May 04, 2000, Seattle, Washington [doi>10.3115/974147.974172]
• 10: Croft, W. B. 2000. Combining approaches to information retrieval. Advan. Info. Retrieval. 1--36.
• 11: Eric J. Glover , Gary W. Flake , Steve Lawrence , Andries Kruger , David M. Pennock , William P. Birmingham , C. Lee Giles, Improving Category Specific Web Search by Learning Query Modifications, Proceedings of the 2001 Symposium on Applications and the Internet (SAINT 2001), p.23, January 08-12, 2001
• 12: Sanda M. Harabagiu , Marius A. Paşca , Steven J. Maiorano, Experiments with open-domain textual Question Answering, Proceedings of the 18th conference on Computational linguistics, p.292-298, July 31-August 04, 2000, Saarbrücken, Germany [doi>10.3115/990820.990863]
• 13: David Hawking , Nick Craswell , Paul Thistlewaite , Donna Harman, Results and challenges in Web search evaluation, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.31 n.11-16, p.1321-1330, May 17, 1999
• 14: Hovy, E., Gerber, L., Hermjakob, U., Junk, M., and Lin, C.-Y. 2000. Question answering in Webclopedia. In Proceedings of the TREC-9 Question Answering Track. 655--672.
• 15: Ittycheriah, A., Franz, M., Zhu, W.-J., and Ratnaparkhi, A. 2000. IBM's statistical question answering system. In Proceedings of the TREC-9 Question Answering Track. 231--234.
• 16: Hideo Joho , Mark Sanderson, Retrieving descriptive phrases from large amounts of free text, Proceedings of the ninth international conference on Information and knowledge management, p.180-186, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354817]
• 17: Judith Klavans , Min-Yen Kan, Role of verbs in document analysis, Proceedings of the 17th international conference on Computational linguistics, August 10-14, 1998, Montreal, Quebec, Canada
• 18: Cody C. T. Kwok , Oren Etzioni , Daniel S. Weld, Scaling question answering to the Web, Proceedings of the 10th international conference on World Wide Web, p.150-161, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371973]
• 19: Steve Lawrence , Kurt Bollacker , C. Lee Giles, Indexing and retrieval of scientific literature, Proceedings of the eighth international conference on Information and knowledge management, p.139-146, November 02-06, 1999, Kansas City, Missouri, United States [doi>10.1145/319950.319970]
• 20: Steve Lawrence , C. Lee Giles, Context and Page Analysis for Improved Web Search, IEEE Internet Computing, v.2 n.4, p.38-46, July 1998 [doi>10.1109/4236.707689]
• 21: Gideon S. Mann, Learning how to answer questions using trivia games, Proceedings of the 19th international conference on Computational linguistics, p.1-7, August 24-September 01, 2002, Taipei, Taiwan [doi>10.3115/1072228.1072330]
• 22: George A. Miller, WordNet: a lexical database for English, Communications of the ACM, v.38 n.11, p.39-41, Nov. 1995 [doi>10.1145/219717.219748]
• 23: 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]
• 24: Moldovan, D., Harabagiu, S., Pasca, M., Mihalcea, R., Goodrum, R., Girju, R., and Rus, V. 1999. Lasso: A tool for surfing the answer net. In Proceedings of the TREC-8 Question Answering Track. 175--184.
• 25: Prager, J., Chu-Caroll, J., and Czuba, K. 2002. Statistical answer-type identification in open-domain question answering. In Proceedings of the Human Language Technology Conference (HLT-2002). 137--143.
• 26: Dragomir Radev , Weiguo Fan , Hong Qi , Harris Wu , Amardeep Grewal, Probabilistic question answering on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511500]
• 27: Dragomir R. Radev , Hong Qi , Zhiping Zheng , Sasha Blair-Goldensohn , Zhu Zhang , Weiguo Fan , John Prager, Mining the web for answers to natural language questions, Proceedings of the tenth international conference on Information and knowledge management, October 05-10, 2001, Atlanta, Georgia, USA [doi>10.1145/502585.502610]
• 28: S. E. Robertson, On term selection for query expansion, Journal of Documentation, v.46 n.4, p.359-364, Dec. 1990 [doi>10.1108/eb026866]
• 29: Robertson, S. and Sparck-Jones, K. 1976. Relevance weighting of search terms. J. Amer. Soc. Info. Sci. 27, 129--146.
• 30: S. E. Robertson , S. Walker, On relevance weights with little relevance information, Proceedings of the 20th annual international ACM SIGIR conference on Research and development in information retrieval, p.16-24, July 27-31, 1997, Philadelphia, Pennsylvania, United States
• 31: Robertson, S., Walker, S., and Beaulieu, M. 1998. Okapi at TREC-7: automatic ad hoc, filtering, VLC and interactive track. In TREC-7 Proceedings. 253--264.
• 32: Rocchio, J. 1971. Relevance feedback in information retrieval, G. Salton, Ed. The SMART Retrieval System--Experiments in Automatic Document Processing. 313--323.
• 33: Gerard Salton, Automatic text processing: the transformation, analysis, and retrieval of information by computer, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989
• 34: Barry Schiffman , Kathleen R. McKeown, Experiments in automated lexicon building for text searching, Proceedings of the 18th conference on Computational linguistics, July 31-August 04, 2000, Saarbrücken, Germany [doi>10.3115/992730.992750]
• 35: Elicitation queries to the excite Web search engine, Proceedings of the ninth international conference on Information and knowledge management, p.134-140, November 06-11, 2000, McLean, Virginia, United States [doi>10.1145/354756.354811]
• 36: Voorhees, E. 1999a. Overview of the Eighth Text REtrieval Conference (TREC-8). In Proceedings of TREC-8. 1--24.
• 37: Voorhees, E. 1999b. The TREC-8 question answering track report. In Proceedings of TREC-8. 77--82.
• 38: Voorhees, E. 2000. Overview of the TREC-9 question answering track. In Proceedings of TREC-9. 71--80.
• 39: Voorhees, E. 2001. Overview of the TREC-2001 question answering track. In Proceedings of TREC-10. 42--51.
• 40: Voorhees, E. and Tice, D. M. 1999. The TREC-8 question answering track evaluation. In Proceedings of TREC-8. 84--106.
• 41: Jinxi Xu , W. Bruce Croft, Improving the effectiveness of information retrieval with local context analysis, ACM Transactions on Information Systems (TOIS), v.18 n.1, p.79-112, Jan. 2000 [doi>10.1145/333135.333138]

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:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process; Retrieval models; Query formulation
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness); Information networks
      H.3.5 On-line Information Services
          Subjects: Web-based services

General Terms:
Algorithms, Experimentation, Performance

Keywords:
Web search, information retrieval, meta-search, query expansion, question answering