Scaling Textual Inference to the Web

Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 79–88, Honolulu, October 2008. c⃝2008 Association for Computational Linguistics Scaling Textual Inference to the Web Stefan Schoenmackers, Oren Etzioni, and Daniel S. Weld Turing Center University of Washington Computer Science and Engineering Box 352350 Seattle, WA 98195, USA stef,etzioni,weld@cs.washington.edu Abstract Most Web-based Q/A systems work by find- ing pages that contain an explicit answer to a question. These systems are helpless if the answer has to be inferred from multiple sen- tences, possibly on different pages. To solve this problem, we introduce the HOLMES sys- tem, which utilizes textual inference (TI) over tuples extracted from text. Whereas previous work on TI (e.g., the lit- erature on textual entailment) has been ap- plied to paragraph-sized texts, HOLMES uti- lizes knowledge-based model construction to scale TI to a corpus of 117 million Web pages. Given only a few minutes, HOLMES doubles recall for example queries in three disparate domains (geography, business, and nutrition). Importantly, HOLMES’s runtime is linear in the size of its input corpus due to a surprising property of many textual relations in the Web corpus—they are “approximately” functional in a well-defined sense. 1 Introduction and Motivation Numerous researchers have identified the Web as a rich source of answers to factual questions, e.g., (Kwok et al., 2001; Brill et al., 2002), but often the desired information is not stated explicitly even in a textual corpus as massive as the Web. Consider the question “What vegetables help prevent osteoporo- sis?” Since there is likely no sentence on the Web directly stating “Kale prevents osteoporosis”, a sys- tem must infer that kale is an answer by combining facts from multiple sentences, possibly from differ- ent pages, which justify that conclusion: i.e., that kale is a vegetable, kale contains calcium, and cal- cium helps prevent osteoporosis. Figure 1: The architecture of HOLMES. Textual Inference (TI) methods have advanced in recent years. For example, textual entailment tech- niques aim to determine whether one textual frag- ment (the hypothesis) follows from another (the text) (Dagan et al., 2005). While most TI researchers have focused on high-quality inferences from a small source text, we seek to utilize sizable chunks of the Web corpus as our source text. In order to do this, we must confront two major challenges. The first is uncertainty: TI is an imperfect process, particularly when applied to the Web corpus, hence probabilistic methods help to assess the confidence in inferences. The second challenge is scalability: how does infer- ence time scale given increasingly large corpora as input? 1.1 HOLMES: A Scalable TI System This paper describes HOLMES, an implemented sys- tem, which addresses both challenges by carrying out scalable, probabilistic inference over ground assertions extracted from the Web. The input to HOLMES is a conjunctive query, a set of inference rules expressed as Horn clauses, and large sets of ground assertions extracted from the Web, WordNet, and other knowledge bases. As shown in Figure 1, HOLMES chains backward from …

Content truncated to 500 words