FactRank: Random Walks on a Web of Facts

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 501–509, Beijing, August 2010 FactRank: Random Walks on a Web of Facts Alpa Jain Yahoo! Labs alpa@yahoo-inc.com Patrick Pantel Microsoft Research ppantel@microsoft.com Abstract Fact collections are mostly built using semi-supervised relation extraction tech- niques and wisdom of the crowds meth- ods, rendering them inherently noisy. In this paper, we propose to validate the re- sulting facts by leveraging global con- straints inherent in large fact collections, observing that correct facts will tend to match their arguments with other facts more often than with incorrect ones. We model this intuition as a graph-ranking problem over a fact graph and explore novel random walk algorithms. We present an empirical study, over a large set of facts extracted from a 500 million doc- ument webcrawl, validating the model and showing that it improves fact quality over state-of-the-art methods. 1 Introduction Fact bases, such as those contained in Freebase, DBpedia, KnowItAll, and TextRunner, are increas- ingly burgeoning on the Internet, in government, in high tech companies and in academic laborato- ries. Bar the accurate manual curation typified by Cyc (Lenat, 1995), most fact bases are built us- ing either semi-supervised techniques or wisdom of the crowds techniques, rendering them inher- ently noisy. This paper describes algorithms to validate and re-rank fact bases leveraging global constraints imposed by the semantic arguments predicated by the relations. Facts are defined as instances of n-ary typed re- lations such as acted-in⟨movie, actor⟩, director- of⟨movie, director⟩, born-in⟨person, date⟩, and buy⟨person, product, person⟩. In all but very small fact bases, relations share an argument type, such as movie for the relations acted-in and director-of in the above example. The hypothesis explored in this paper is that when two fact in- stances from two relations share the same value for a shared argument type, then the validity of both facts should be increased. Conversely, we also hypothesize that an incorrect fact instance will tend to match a shared argument with other facts far less frequently. For example, consider the following four facts from the relations acted- in, director-of, and is-actor: t1: acted-in⟨Psycho, Anthony Perkins⟩ t2: *acted-in⟨Walt Disney Pictures, Johnny Depp⟩ t3: director-of⟨Psycho, Alfred Hitchcock⟩ t4: is-actor⟨Anthony Perkins⟩ Our confidence in the validity of t1 increases with the knowledge of t3 and t4 since the argu- ment movie is shared with t3 and actor with t4. Similarly, t1 increases our confidence in the va- lidity of t3 and t4. For t2, we expect to find few facts that will match a movie argument with Walt Disney Pictures. Facts that share the actor argu- ment Johnny Depp with t2 will increase its valid- ity, but the lack of matches on its movie argument will decrease its validity. In this paper, we present FactRank, which for- malizes the above intuitions by constructing a fact graph and running various random walk graph- ranking algorithms over it to re-rank and validate the facts. A collection of facts is modeled in the form of a …

Content truncated to 500 words