Names and Similarities on the Web: Fact Extraction in the Fast Lane

Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the ACL, pages 809–816, Sydney, July 2006. c⃝2006 Association for Computational Linguistics Names and Similarities on the Web: Fact Extraction in the Fast Lane Marius Pas¸ca Google Inc. Mountain View, CA 94043 mars@google.com Dekang Lin Google Inc. Mountain View, CA 94043 lindek@google.com Jeffrey Bigham∗ University of Washington Seattle, WA 98195 jbigham@cs.washington.edu Andrei Lifchits∗ University of British Columbia Vancouver, BC V6T 1Z4 alifchit@cs.ubc.ca Alpa Jain∗ Columbia University New York, NY 10027 alpa@cs.columbia.edu Abstract In a new approach to large-scale extrac- tion of facts from unstructured text, dis- tributional similarities become an integral part of both the iterative acquisition of high-coverage contextual extraction pat- terns, and the validation and ranking of candidate facts. The evaluation mea- sures the quality and coverage of facts extracted from one hundred million Web documents, starting from ten seed facts and using no additional knowledge, lexi- cons or complex tools. 1 Introduction 1.1 Background The potential impact of structured fact reposito- ries containing billions of relations among named entities on Web search is enormous. They en- able the pursuit of new search paradigms, the pro- cessing of database-like queries, and alternative methods of presenting search results. The prepa- ration of exhaustive lists of hand-written extrac- tion rules is impractical given the need for domain- independent extraction of many types of facts from unstructured text. In contrast, the idea of boot- strapping for relation and information extraction was first proposed in (Riloff and Jones, 1999), and successfully applied to the construction of seman- tic lexicons (Thelen and Riloff, 2002), named en- tity recognition (Collins and Singer, 1999), extrac- tion of binary relations (Agichtein and Gravano, 2000), and acquisition of structured data for tasks such as Question Answering (Lita and Carbonell, 2004; Fleischman et al., 2003). In the context of fact extraction, the resulting iterative acquisition ∗Work done during internships at Google Inc. framework starts from a small set of seed facts, finds contextual patterns that extract the seed facts from the underlying text collection, identifies a larger set of candidate facts that are extracted by the patterns, and adds the best candidate facts to the previous seed set. 1.2 Contributions Figure 1 describes an architecture geared towards large-scale fact extraction. The architecture is sim- ilar to other instances of bootstrapping for infor- mation extraction. The main processing stages are the acquisition of contextual extraction patterns given the seed facts, acquisition of candidate facts given the extraction patterns, scoring and ranking of the patterns, and scoring and ranking of the can- didate facts, a subset of which is added to the seed set of the next round. Within the existing iterative acquisition frame- work, our first contribution is a method for au- tomatically generating generalized contextual ex- traction patterns, based on dynamically-computed classes of similar words. Traditionally, the ac- quisition of contextual extraction patterns requires hundreds or thousands of consecutive iterations over the entire text collection (Lita and Carbonell, 2004), often using relatively expensive or …

Content truncated to 500 words