2017

Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning

Das, Rajarshi, Dhuliawala, Shehzaad, Zaheer, Manzil et al.

Understand

Knowledge bases (KB), both automatically and manually constructed, are often incomplete --- many valid facts can be inferred from the KB by synthesizing existing information.

A popular approach to KB completion is to infer new relations by combinatory reasoning over the information found along other paths connecting a pair of entities.
Given the enormous size of KBs and the exponential number of paths, previous path-based models have considered only the problem of predicting a missing relation given two entities or evaluating the truth of a proposed triple.
Additionally, these methods have traditionally used random paths between fixed entity pairs or more recently learned to pick paths between them.

Built on

Programs with common sense
John McCarthy · 1960
Earlier work this paper cites.
Learning logical definitions from relations
J Ross Quinlan · 1990
Earlier work this paper cites.
Logic and artificial intelligence
Nils J Nilsson · 1991
Earlier work this paper cites.
Inductive logic programming
Stephen Muggleton, Ramon Otero, and Alireza Tamaddoni-Nezhad · 1992
Earlier work this paper cites.
Simple statistical gradient-following algorithms for connectionist reinforcement learning
Ronald J Williams · 1992
Earlier work this paper cites.
Inverse entailment and progol
Stephen Muggleton · 1995
Earlier work this paper cites.
Long short-term memory
Sepp Hochreiter and Jürgen Schmidhuber · 1997
Earlier work this paper cites.
Approximating integrals via Monte Carlo and deterministic methods
Michael Evans and Timothy Swartz · 2000
Earlier work this paper cites.
Incremental parsing with the perceptron algorithm
Michael Collins and Brian Roark · 2004
Earlier work this paper cites.
Learning as search optimization: Approximate large margin methods for structured prediction
Hal Daumé III and Daniel Marcu · 2005
Earlier work this paper cites.
Markov logic networks
Matthew Richardson and Pedro Domingos · 2006
Earlier work this paper cites.
Introduction to statistical relational learning
Lise Getoor and Ben Taskar · 2007
Earlier work this paper cites.
Statistical predicate invention
Stanley Kok and Pedro Domingos · 2007
Earlier work this paper cites.
Natural logic for textual inference
Bill MacCartney and Christopher D Manning · 2007
Earlier work this paper cites.
Yago: A core of semantic knowledge
Fabian Suchanek, Gjergji Kasneci, and Gerhard Weikum · 2007
Earlier work this paper cites.
Freebase: A collaboratively created graph database for structuring human knowledge
Kurt Bollacker, Colin Evans, Praveen Paritosh, Tim Sturge, and Jamie Taylor · 2008
Earlier work this paper cites.
Search-based structured prediction
Hal Daumé III, John Langford, and Daniel Marcu · 2009
Earlier work this paper cites.
Distant supervision for relation extraction without labeled data
Mike Mintz, Steven Bills, Rion Snow, and Dan Jurafsky · 2009
Earlier work this paper cites.
Wikispeedia: An online game for inferring semantic distances between concepts
Robert West, Joelle Pineau, and Doina Precup · 2009
Earlier work this paper cites.
Probabilistic similarity logic
Matthias Broecheler, Lilyana Mihalkova, and Lise Getoor · 2010
Earlier work this paper cites.

Similar

Toward an Architecture for Never-ending Language Learning
Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R. Hruschka, Jr., and Tom M. Mitchell · 2010
Cited alongside, same era.
Learning first-order horn clauses from web text
Stefan Schoenmackers, Oren Etzioni, Daniel Weld, and Jesse Davis · 2010
Cited alongside, same era.
Random walk inference and learning in a large scale knowledge base
Ni Lao, Tom Mitchell, and William Cohen · 2011
Cited alongside, same era.
A three-way model for collective learning on multi-relational data
Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel · 2011
Cited alongside, same era.
A reduction of imitation learning and structured prediction to no-regret online learning
Stéphane Ross, Geoffrey J Gordon, and Drew Bagnell · 2011
Cited alongside, same era.
Factorizing yago: scalable machine learning for linked data
Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel · 2012
Cited alongside, same era.
Translating embeddings for modeling multi-relational data
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko · 2013
Cited alongside, same era.
Monte Carlo: concepts, algorithms, and applications
George Fishman · 2013
Cited alongside, same era.
Monte carlo methods
John Hammersley · 2013
Cited alongside, same era.
Distant supervision for relation extraction with an incomplete knowledge base
Bonan Min, Ralph Grishman, Li Wan, Chang Wang, and David Gondek · 2013
Cited alongside, same era.
Relation extraction with matrix factorization and universal schemas
Sebastian Riedel, Limin Yao, Andrew McCallum, and Benjamin M. Marlin · 2013
Cited alongside, same era.
Reasoning with neural tensor networks for knowledge base completion
Richard Socher, Danqi Chen, Christopher D Manning, and Andrew Ng · 2013
Cited alongside, same era.

Then

Traversing knowledge graphs in vector space
Kelvin Guu, John Miller, and Percy Liang · 2015
Later among the works it cites.
Compositional vector space models for knowledge base completion
Arvind Neelakantan, Benjamin Roth, and Andrew McCallum · 2015
Later among the works it cites.
End-to-end memory networks
Sainbayar Sukhbaatar, Jason Weston, and Rob Fergus · 2015
Later among the works it cites.
Representing text for joint embedding of text and knowledge bases
Kristina Toutanova, Danqi Chen, Patrick Pantel, Hoifung Poon, Pallavi Choudhury, and Michael Gamon · 2015
Later among the works it cites.
Embedding entities and relations for learning and inference in knowledge bases
Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng · 2015
Later among the works it cites.
Reinforcement learning neural turing machines
Original
Wojciech Zaremba and Ilya Sutskever · 2015
Later among the works it cites.
Tensorlog: A differentiable deductive database
Original
William Cohen · 2016
Later among the works it cites.
Key-value memory networks for directly reading documents
Alexander Miller, Adam Fisch, Jesse Dodge, Amir-Hossein Karimi, Antoine Bordes, and Jason Weston · 2016
Later among the works it cites.
End-to-end goal-driven web navigation
Rodrigo Nogueira and Kyunghyun Cho · 2016
Later among the works it cites.
Compositional learning of embeddings for relation paths in knowledge base and text
Kristina Toutanova, Victoria Lin, Wen-tau Yih, Hoifung Poon, and Chris Quirk · 2016
Later among the works it cites.
Complex embeddings for simple link prediction
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard · 2016
Later among the works it cites.
Multilingual relation extraction using compositional universal schema
Patrick Verga, David Belanger, Emma Strubell, Benjamin Roth, and Andrew McCallum · 2016
Later among the works it cites.
Chains of reasoning over entities, relations, and text using recurrent neural networks
Rajarshi Das, Arvind Neelakantan, David Belanger, and Andrew McCallum · 2017
Closest in time.
End-to-end differentiable proving
Tim Rocktäschel and Sebastian Riedel · 2017
Closest in time.
Reasonet: Learning to stop reading in machine comprehension
Yelong Shen, Po-Sen Huang, Jianfeng Gao, and Weizhu Chen · 2017
Closest in time.
Deeppath: A reinforcement learning method for knowledge graph reasoning
Wenhan Xiong, Thien Hoang, and William Yang Wang · 2017
Closest in time.
Differentiable learning of logical rules for knowledge base reasoning
Fan Yang, Zhilin Yang, and William W Cohen · 2017
Closest in time.
Deep sets
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola · 2017
Closest in time.
Convolutional 2d knowledge graph embeddings
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel · 2018
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…