DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 564–573 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning Wenhan Xiong and Thien Hoang and William Yang Wang Department of Computer Science University of California, Santa Barbara Santa Barbara, CA 93106 USA {xwhan,william}@cs.ucsb.edu, thienhoang@umail.ucsb.edu Abstract We study the problem of learning to reason in large scale knowledge graphs (KGs). More specifically, we describe a novel re- inforcement learning framework for learn- ing multi-hop relational paths: we use a policy-based agent with continuous states based on knowledge graph embeddings, which reasons in a KG vector space by sampling the most promising relation to extend its path. In contrast to prior work, our approach includes a reward function that takes the accuracy, diversity, and ef- ficiency into consideration. Experimen- tally, we show that our proposed method outperforms a path-ranking based algo- rithm and knowledge graph embedding methods on Freebase and Never-Ending Language Learning datasets.1 1 Introduction In recent years, deep learning techniques have ob- tained many state-of-the-art results in various clas- sification and recognition problems (Krizhevsky et al., 2012; Hinton et al., 2012; Kim, 2014). How- ever, complex natural language processing prob- lems often require multiple inter-related decisions, and empowering deep learning models with the ability of learning to reason is still a challenging issue. To handle complex queries where there are no obvious answers, intelligent machines must be able to reason with existing resources, and learn to infer an unknown answer. More specifically, we situate our study in the context of multi-hop reasoning, which is the task of learning explicit inference formulas, given a large KG. For example, if the KG includes the 1Code and the NELL dataset are available at https:// github.com/xwhan/DeepPath. beliefs such as Neymar plays for Barcelona, and Barcelona are in the La Liga league, then ma- chines should be able to learn the following for- mula: playerPlaysForTeam(P,T) ∧ teamPlaysIn- League(T,L) ⇒ playerPlaysInLeague(P,L). In the testing time, by plugging in the learned formulas, the system should be able to automatically infer the missing link between a pair of entities. This kind of reasoning machine will potentially serve as an essential components of complex QA sys- tems. In recent years, the Path-Ranking Algorithm (PRA) (Lao et al., 2010, 2011a) emerges as a promising method for learning inference paths in large KGs. PRA uses a random-walk with restarts based inference mechanism to perform multiple bounded depth-first search processes to find rela- tional paths. Coupled with elastic-net based learn- ing, PRA then picks more plausible paths using supervised learning. However, PRA operates in a fully discrete space, which makes it difficult to evaluate and compare similar entities and relations in a KG. In this work, we propose a novel approach for controllable multi-hop reasoning: we frame the path learning process as reinforcement learn- ing (RL). In contrast to PRA, we use translation- based knowledge based embedding method (Bor- des et al., 2013) to encode the continuous state …

Content truncated to 500 words