Incorporating Vector Space Similarity in Random Walk Inference over Knowledge Bases

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 397–406, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics Incorporating Vector Space Similarity in Random Walk Inference over Knowledge Bases Matt Gardner Carnegie Mellon University mg1@cs.cmu.edu Partha Talukdar∗ Indian Institute of Science ppt@serc.iisc.in Jayant Krishnamurthy Carnegie Mellon University jayantk@cs.cmu.edu Tom Mitchell Carnegie Mellon University tom@cs.cmu.edu Abstract Much work in recent years has gone into the construction of large knowledge bases (KBs), such as Freebase, DBPedia, NELL, and YAGO. While these KBs are very large, they are still very incomplete, ne- cessitating the use of inference to fill in gaps. Prior work has shown how to make use of a large text corpus to augment ran- dom walk inference over KBs. We present two improvements to the use of such large corpora to augment KB inference. First, we present a new technique for combin- ing KB relations and surface text into a single graph representation that is much more compact than graphs used in prior work. Second, we describe how to incor- porate vector space similarity into random walk inference over KBs, reducing the fea- ture sparsity inherent in using surface text. This allows us to combine distributional similarity with symbolic logical inference in novel and effective ways. With exper- iments on many relations from two sepa- rate KBs, we show that our methods sig- nificantly outperform prior work on KB inference, both in the size of problem our methods can handle and in the quality of predictions made. 1 Introduction Much work in recent years has gone into the construction of large knowledge bases, either by collecting contributions from many users, as with Freebase (Bollacker et al., 2008) and ∗ Research carried out while at the Machine Learning Department, Carnegie Mellon University. DBPedia (Mendes et al., 2012), or automat- ically from web text or other resources, as done by NELL (Carlson et al., 2010) and YAGO (Suchanek et al., 2007). These knowl- edge bases contain millions of real-world enti- ties and relationships between them. However, even though they are very large, they are still very incomplete, missing large fractions of possi- ble relationships between common entities (West et al., 2014). Thus the task of inference over these knowledge bases, predicting new relation- ships simply by examining the knowledge base it- self, has become increasingly important. A promising technique for inferring new re- lation instances in a knowledge base is random walk inference, first proposed by Lao and Cohen (2010). In this method, called the Path Ranking Algorithm (PRA), the knowledge base is encoded as a graph, and random walks are used to find paths that connect the source and target nodes of relation instances. These paths are used as features in a logistic regression classifier that predicts new instances of the given relation. Each path can be viewed as a horn clause using knowledge base re- lations as predicates, and so PRA can be thought of as a kind of discriminatively trained logical in- …

Content truncated to 500 words