Unsupervised Resolution of Objects and Relations on the Web

Proceedings of NAACL HLT 2007, pages 121–130, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Unsupervised Resolution of Objects and Relations on the Web Alexander Yates Turing Center Computer Science and Engineering University of Washington Box 352350 Seattle, WA 98195, USA ayates@cs.washington.edu Oren Etzioni Turing Center Computer Science and Engineering University of Washington Box 352350 Seattle, WA 98195, USA etzioni@cs.washington.edu Abstract The task of identifying synonymous re- lations and objects, or Synonym Resolu- tion (SR), is critical for high-quality infor- mation extraction. The bulk of previous SR work assumed strong domain knowl- edge or hand-tagged training examples. This paper investigates SR in the con- text of unsupervised information extrac- tion, where neither is available. The pa- per presents a scalable, fully-implemented system for SR that runs in O(KN log N) time in the number of extractions N and the maximum number of synonyms per word, K. The system, called RESOLVER, introduces a probabilistic relational model for predicting whether two strings are co-referential based on the similarity of the assertions containing them. Given two million assertions extracted from the Web, RESOLVER resolves objects with 78% precision and an estimated 68% re- call and resolves relations with 90% pre- cision and 35% recall. 1 Introduction Web Information Extraction (WIE) sys- tems extract assertions that describe a rela- tion and its arguments from Web text (e.g., (is capital of, D.C., United States)). WIE systems can extract hundreds of millions of assertions containing millions of different strings from the Web (e.g., the TEXTRUNNER system (Banko et al., 2007)).1 WIE systems often extract assertions that describe the same real-world object or relation using different names. For example, a WIE system might extract (is capital city of, Washington, U.S.), which describes the same relationship as above but contains a different name for the relation and each argument. Synonyms are prevalent in text, and the Web cor- pus is no exception. Our data set of two million as- sertions extracted from a Web crawl contained over a half-dozen different names each for the United States and Washington, D.C., and three for the “is capital of” relation. The top 80 most commonly extracted objects had an average of 2.9 extracted names per entity, and several had as many as 10 names. The top 100 most commonly extracted re- lations had an average of 4.9 synonyms per relation. We refer to the problem of identifying synony- mous object and relation names as Synonym Res- olution (SR).2 An SR system for WIE takes a set of assertions as input and returns a set of clusters, with each cluster containing coreferential object strings or relation strings. Previous techniques for SR have focused on one particular aspect of the problem, ei- ther objects or relations. In addition, the techniques either depend on a large set of training examples, or are tailored to a specific domain by assuming knowl- edge of the domain’s schema. Due to the number and diversity of the relations extracted, these tech- 1For a demo see www.cs.washington.edu/research/textrunner. 2Ironically, …

Content truncated to 500 words