Knowledge Base Completion via Coupled Path Ranking

Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, pages 1308–1318, Berlin, Germany, August 7-12, 2016. c⃝2016 Association for Computational Linguistics Knowledge Base Completion via Coupled Path Ranking Quan Wang†, Jing Liu‡, Yuanfei Luo†, Bin Wang†, Chin-Yew Lin‡ †Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China {wangquan,luoyuanfei,wangbin}@iie.ac.cn ‡Microsoft Research, Beijing 100080, China {liudani,cyl}@microsoft.com Abstract Knowledge bases (KBs) are often greatly incomplete, necessitating a demand for K- B completion. The path ranking algorith- m (PRA) is one of the most promising ap- proaches to this task. Previous work on PRA usually follows a single-task learn- ing paradigm, building a prediction mod- el for each relation independently with its own training data. It ignores meaningful associations among certain relations, and might not get enough training data for less frequent relations. This paper proposes a novel multi-task learning framework for PRA, referred to as coupled PRA (CPRA). It first devises an agglomerative clustering strategy to automatically discover relation- s that are highly correlated to each other, and then employs a multi-task learning s- trategy to effectively couple the prediction of such relations. As such, CPRA takes in- to account relation association and enables implicit data sharing among them. We empirically evaluate CPRA on benchmark data created from Freebase. Experimen- tal results show that CPRA can effective- ly identify coherent clusters in which rela- tions are highly correlated. By further cou- pling such relations, CPRA significantly outperforms PRA, in terms of both predic- tive accuracy and model interpretability. 1 Introduction Knowledge bases (KBs) like Freebase (Bollack- er et al., 2008), DBpedia (Lehmann et al., 2014), and NELL (Carlson et al., 2010) are extremely useful resources for many NLP tasks (Cucerzan, 2007; Schuhmacher and Ponzetto, 2014). They provide large collections of facts about entities and their relations, typically stored as (head entity, re- lation, tail entity) triples, e.g., (Paris, capitalOf, France). Although such KBs can be impressively large, they are still quite incomplete and missing crucial facts, which may reduce their usefulness in downstream tasks (West et al., 2014; Choi et al., 2015). KB completion, i.e., automatically infer- ring missing facts by examining existing ones, has thus attracted increasing attention. Approaches to this task roughly fall into three categories: (i) path ranking algorithms (PRA) (Lao et al., 2011); (ii) embedding techniques (Bordes et al., 2013; Guo et al., 2015); and (iii) graphical models such as Markov logic networks (MLN) (Richardson and Domingos, 2006). This paper focuses on PRA, which is easily interpretable (as opposed to em- bedding techniques) and requires no external logic rules (as opposed to MLN). The key idea of PRA is to explicitly use paths connecting two entities to predict potential rela- tions between them. In PRA, a KB is encoded as a graph which consists of a set of heterogeneous edges. Each edge is labeled with a relation type that exists between two entities. Given a specific relation, random walks are first employed to find paths between two entities that have the given rela- tion. …

Content truncated to 500 words