Elamur Research⌕
☰
home / papers / 2017 / End-to-End Differentiable Proving

End-to-End Differentiable Proving

Paper · 2017 · Tim Rocktäschel and Sebastian Riedel

Summary

Neural link prediction models complete knowledge bases (KBs) by learning symbol embeddings and judging similarity, but they score each fact in isolation. This makes multi-step inference such as transitivity difficult for them. Symbolic provers like Prolog chain inferences easily but cannot generalize across symbols that are similar but not identical. Rocktäschel and Riedel propose Neural Theorem Provers (NTPs), which bridge the two. NTPs follow Prolog's backward chaining algorithm to recursively build a neural network for each query. Variable binding stays symbolic, while exact symbol matching is replaced by an RBF-kernel similarity between embeddings. Because the proof success score is differentiable, gradient descent can learn symbol representations and the parameters of rule templates, such as transitive patterns. The induced rules can then be decoded into readable first-order clauses. The authors evaluate on Countries, Kinship, Nations and UMLS. NTPλ, an NTP trained jointly with ComplEx as an auxiliary loss, beats ComplEx on three of the four KBs. This shows that a differentiable reasoner can be both accurate and interpretable.

Key points

  • Method: Unification compares non-variable symbols using an RBF kernel (µ = 1/√2) over embeddings, and partial proof scores are combined with min. The core operations are OR and AND modules modeled on Prolog.
  • Optimizations: The architecture is made practical through joint training with a neural link predictor (ComplEx), batch proving, and approximate gradient computation.
  • Results: Vanilla NTPs beat ComplEx only on Countries S3 and Nations. NTPλ leads in most tasks, with AUC-PR gains over ComplEx significant on all Countries tasks (p < 0.0001).
  • Interpretability: Induced rules recover the logic needed for the Countries tasks and capture transitivity on UMLS, a pattern that ComplEx struggles to encode.
  • Limitations: Scalability to large KBs is limited, and function terms are not yet supported. A TensorLog-based differentiable rule learner scales better, but the ComplEx baseline outperformed it on HITS@10 (UMLS 1.00 vs 0.70; Kinship 0.98 vs 0.73).

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of OxfordOxford · United Kingdom122 works · 160,277 citations🎓University College LondonLondon · United Kingdom107 works · 22,923 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

Cite

Cite as Tim Rocktäschel and Sebastian Riedel. 2017. End-to-End Differentiable Proving. arXiv:1705.11040.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1705.11040 · arXiv 1705.11040

@misc{rocktaschel2017end,
  title = {{End-to-End Differentiable Proving}},
  author = {Tim Rocktäschel and Sebastian Riedel},
  year = {2017},
  doi = {10.48550/arxiv.1705.11040},
  eprint = {1705.11040},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1705.11040}
}

References

69 references, 12 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Maximilian Nickel, Volker Tresp, and Hans-Peter Kriegel. Factorizing YAGO: scalable machine learning for linked data. In Proceedings of the 21st World Wide Web Conference 2012, WWW 2012, Lyon, France, April 16-20, 2012, pages 271–280, 2012. doi: 10.1145/2187836.2187874. — [doi:10.1145/2187836.2187874](https://doi.org/10.1145/2187836.2187874) find
  2. Sebastian Riedel, Limin Yao, Andrew McCallum, and Benjamin M. Marlin. Relation extraction with matrix factorization and universal schemas. In Human Language Technologies: Conference of the North American Chapter of the Association of Computational Linguistics, Proceedings, June 9-14, 2013, Westin Pe… find
  3. Richard Socher, Danqi Chen, Christopher D. Manning, and Andrew Y. Ng. Reasoning with neural tensor networks for knowledge base completion. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held Dece…
  4. Kai-Wei Chang, Wen-tau Yih, Bishan Yang, and Christopher Meek. Typed tensor decomposition of knowledge bases for relation extraction. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, October 25-29, 2014, Doha, Qatar, A meeting of SIGDAT, a Specia… find
  5. Bishan Yang, Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In International Conference on Learning Representations (ICLR), 2015.
  6. Kristina Toutanova, Danqi Chen, Patrick Pantel, Hoifung Poon, Pallavi Choudhury, and Michael Gamon. Representing text for joint embedding of text and knowledge bases. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, EMNLP 2015, Lisbon, Portugal, September 17…
  7. Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Complex embeddings for simple link prediction. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, pages 2071–2080, 2016.
  8. Hervé Gallaire and Jack Minker, editors. Logic and Data Bases, Symposium on Logic and Data Bases, Centre d’études et de recherches de Toulouse, 1977, Advances in Data Base Theory, New York, 1978. Plemum Press. ISBN 0-306-40060-X. find
  9. Stephen Muggleton. Inductive logic programming. New Generation Comput., 8(4):295–318, 1991. doi: 10.1007/BF03037089. — [doi:10.1007/bf03037089](https://doi.org/10.1007/bf03037089) find
  10. Stanley Kok and Pedro M. Domingos. Statistical predicate invention. In Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA, June 20-24, 2007, pages 433–440, 2007. doi: 10.1145/1273496.1273551. — [doi:10.1145/1273496.1273551](https://doi.org/10.1145/1273496.1273551) find
  11. Matt Gardner, Partha Pratim Talukdar, Bryan Kisiel, and Tom M. Mitchell. Improving learning and inference in a large knowledge-base using latent syntactic cues. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, EMNLP 2013, 18-21 October 2013, Grand Hyatt Seat… find
  12. Matt Gardner, Partha Pratim Talukdar, Jayant Krishnamurthy, and Tom M. Mitchell. Incorporating vector space similarity in random walk inference over knowledge bases. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing, EMNLP 2014, October 25-29, 2014, Doha, Qata… find
  13. Islam Beltagy, Stephen Roller, Pengxiang Cheng, Katrin Erk, and Raymond J Mooney. Representing meaning with a combination of logical and distributional models. Computational Linguistics, 2017.
  14. Arvind Neelakantan, Benjamin Roth, and Andrew McCallum. Compositional vector space models for knowledge base completion. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing of the Asian F…
  15. Baolin Peng, Zhengdong Lu, Hang Li, and Kam-Fai Wong. Towards neural network-based reasoning. CoRR, abs/1508.05508, 2015. — [arXiv:1508.05508](https://arxiv.org/abs/1508.05508) find
  16. Rajarshi Das, Arvind Neelakantan, David Belanger, and Andrew McCallum. Chains of reasoning over entities, relations, and text using recurrent neural networks. In Conference of the European Chapter of the Association for Computational Linguistics (EACL), 2017. find
  17. Dirk Weissenborn. Separating answers from queries for neural reading comprehension. abs/1607.03316, 2016. — [arXiv:1607.03316](https://arxiv.org/abs/1607.03316) find
  18. Yelong Shen, Po-Sen Huang, Jianfeng Gao, and Weizhu Chen. Reasonet: Learning to stop reading in machine comprehension. In Proceedings of the Workshop on Cognitive Computation: Integrating neural and symbolic approaches 2016 co-located with the 30th Annual Conference on Neural Information Processing… find
  19. Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. CoRR, abs/1410.5401, 2014. find
  20. Jason Weston, Sumit Chopra, and Antoine Bordes. Memory networks. CoRR, abs/1410.3916, 2014. find
  21. Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. Learning to transduce with unbounded memory. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 18… find
  22. Armand Joulin and Tomas Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pages 190–198, 2015. find
  23. Arvind Neelakantan, Quoc V. Le, and Ilya Sutskever. Neural programmer: Inducing latent programs with gradient descent. In International Conference on Learning Representations (ICLR), 2016. find
  24. Scott E. Reed and Nando de Freitas. Neural programmer-interpreters. In International Conference on Learning Representations (ICLR), 2016. find
  25. Marcin Andrychowicz, Misha Denil, Sergio Gomez Colmenarejo, Matthew W. Hoffman, David Pfau, Tom Schaul, and Nando de Freitas. Learning to learn by gradient descent by gradient descent. In Advances in Neural Information Processing Systems 29: Annual Conference on Neural Information Processing Systems… find
  26. Matko Bosnjak, Tim Rocktäschel, Jason Naradowsky, and Sebastian Riedel. Programming with a differentiable forth interpreter. In International Conference on Machine Learning (ICML), 2017. find
  27. Stuart J. Russell and Peter Norvig. Artificial Intelligence - A Modern Approach (3. internat. ed.). Pearson Education, 2010. ISBN 978-0-13-207148-2. find
  28. Lise Getoor. Introduction to statistical relational learning. MIT press, 2007. find
  29. Jacob Andreas, Marcus Rohrbach, Trevor Darrell, and Dan Klein. Learning to compose neural networks for question answering. In NAACL HLT 2016, The 2016 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, San Diego California, USA, Ju…
  30. David S Broomhead and David Lowe. Radial basis functions, multi-variable functional interpolation and adaptive networks. Technical report, DTIC Document, 1988. find
  31. Allen Van Gelder. Efficient loop detection in prolog using the tortoise-and-hare technique. J. Log. Program., 4(1):23–31, 1987. doi: 10.1016/0743-1066(87)90020-3. — [doi:10.1016/0743-1066(87)90020-3](https://doi.org/10.1016/0743-1066%2887%2990020-3) find
  32. J. Ross Quinlan. Learning logical definitions from relations. Machine Learning, 5:239–266, 1990. doi: 10.1007/BF00117105. find
  33. William Yang Wang and William W. Cohen. Joint information extraction and reasoning: A scalable statistical relational learning approach. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processin… find
  34. Antoine Bordes, Nicolas Usunier, Alberto García-Durán, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meetin…
  35. Guillaume Bouchard, Sameer Singh, and Theo Trouillon. On approximate reasoning capabilities of low-rank vector spaces. In Proceedings of the 2015 AAAI Spring Symposium on Knowledge Representation and Reasoning (KRR): Integrating Symbolic and Neural Approaches, 2015. find
  36. Maximilian Nickel, Lorenzo Rosasco, and Tomaso A. Poggio. Holographic embeddings of knowledge graphs. In Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA., pages 1955–1961, 2016. find
  37. Fan Yang, Zhilin Yang, and William W. Cohen. Differentiable learning of logical rules for knowledge base completion. CoRR, abs/1702.08367, 2017. find
  38. Artur S. d’Avila Garcez, Krysia Broda, and Dov M. Gabbay. Neural-symbolic learning systems: foundations and applications. Springer Science & Business Media, 2012. find
  39. Jude W Shavlik and Geoffrey G Towell. An approach to combining explanation-based and neural learning algorithms. Connection Science, 1(3):231–253, 1989. find
  40. Geoffrey G. Towell and Jude W. Shavlik. Knowledge-based artificial neural networks. Artif. Intell., 70 (1-2):119–165, 1994. doi: 10.1016/0004-3702(94)90105-8. — [doi:10.1016/0004-3702(94)90105-8](https://doi.org/10.1016/0004-3702%2894%2990105-8) find
  41. Artur S. d’Avila Garcez and Gerson Zaverucha. The connectionist inductive learning and logic programming system. Appl. Intell., 11(1):59–77, 1999. doi: 10.1023/A:1008328630915. — [doi:10.1023/a:1008328630915](https://doi.org/10.1023/a:1008328630915) find
  42. Lokendra Shastri. Neurally motivated constraints on the working memory capacity of a production system for parallel processing: Implications of a connectionist model based on temporal synchrony. In Proceedings of the Fourteenth Annual Conference of the Cognitive Science Society: July 29 to August 1,… find
  43. Liya Ding. Neural prolog-the concepts, construction and mechanism. In Systems, Man and Cybernetics, 1995. Intelligent Systems for the 21st Century., IEEE International Conference on, volume 4, pages 3603–3608. IEEE, 1995. find
  44. Manoel V. M. França, Gerson Zaverucha, and Artur S. d’Avila Garcez. Fast relational learning using bottom clause propositionalization with artificial neural networks. Machine Learning, 94(1):81–104, 2014. doi: 10.1007/s10994-013-5392-1. — [doi:10.1007/s10994-013-5392-1](https://doi.org/10.1007/s10994-013-5392-1) find
  45. Gustav Sourek, Vojtech Aschenbrenner, Filip Zelezný, and Ondrej Kuzelka. Lifted relational neural networks. In Proceedings of the NIPS Workshop on Cognitive Computation: Integrating Neural and Symbolic Approaches co-located with the 29th Annual Conference on Neural Information Processing Systems (NI… find
  46. William W. Cohen. Tensorlog: A differentiable deductive database. CoRR, abs/1605.06523, 2016. — [arXiv:1605.06523](https://arxiv.org/abs/1605.06523) find
  47. Luciano Serafini and Artur S. d’Avila Garcez. Logic tensor networks: Deep learning and logical reasoning from data and knowledge. In Proceedings of the 11th International Workshop on Neural-Symbolic Learning and Reasoning (NeSy’16) co-located with the Joint Multi-Conference on Human-Level Artificial… find
  48. Ni Lao, Tom M. Mitchell, and William W. Cohen. Random walk inference and learning in A large scale knowledge base. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, EMNLP 2011, 27-31 July 2011, John McIntyre Conference Centre, Edinburgh, UK, A meeting of SIGD… find
  49. Ni Lao, Amarnag Subramanya, Fernando C. N. Pereira, and William W. Cohen. Reading the web with learned syntactic-semantic inference rules. In Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, EMNLP-CoNLL 2012, Ju… find
  50. Tim Rocktäschel, Matko Bosnjak, Sameer Singh, and Sebastian Riedel. Low-Dimensional Embeddings of Logic. In ACL Workshop on Semantic Parsing (SP’14), 2014. find
  51. Tim Rocktäschel, Sameer Singh, and Sebastian Riedel. Injecting logical background knowledge into embeddings for relation extraction. In NAACL HLT 2015, The 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Denver, Colorado, U… find
  52. Ivan Vendrov, Ryan Kiros, Sanja Fidler, and Raquel Urtasun. Order-embeddings of images and language. In International Conference on Learning Representations (ICLR), 2016.
  53. Zhiting Hu, Xuezhe Ma, Zhengzhong Liu, Eduard H. Hovy, and Eric P. Xing. Harnessing deep neural networks with logic rules. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL 2016, August 7-12, 2016, Berlin, Germany, Volume 1: Long Papers, 2016.
  54. Thomas Demeester, Tim Rocktäschel, and Sebastian Riedel. Lifted rule injection for relation embeddings. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, EMNLP 2016, Austin, Texas, USA, November 1-4, 2016, pages 1389–1399, 2016. find
  55. Ekaterina Komendantskaya. Unification neural networks: unification by error-correction learning. Logic Journal of the IGPL, 19(6):821–847, 2011. doi: 10.1093/jigpal/jzq012. — [doi:10.1093/jigpal/jzq012](https://doi.org/10.1093/jigpal/jzq012) find
  56. Steffen Hölldobler. A structured connectionist unification algorithm. In Proceedings of the 8th National Conference on Artificial Intelligence. Boston, Massachusetts, July 29 - August 3, 1990, 2 Volumes., pages 587–593, 1990. find
  57. Stefan Schoenmackers, Jesse Davis, Oren Etzioni, and Daniel S. Weld. Learning first-order horn clauses from web text. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, EMNLP 2010, 9-11 October 2010, MIT Stata Center, Massachusetts, USA, A meeting of SIGDAT, a… find
  58. Stephen H Muggleton, Dianhuan Lin, and Alireza Tamaddoni-Nezhad. Meta-interpretive learning of higher-order dyadic datalog: Predicate invention revisited. Machine Learning, 100(1):49–73, 2015. find
  59. Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural Computation, 9(8):1735–1780, 1997. doi: 10.1162/neco.1997.9.8.1735. find
  60. Rémi Coulom. Efficient selectivity and backup operators in monte-carlo tree search. In Computers and Games, 5th International Conference, CG 2006, Turin, Italy, May 29-31, 2006. Revised Papers, pages 72–83, 2006. doi: 10.1007/978-3-540-75538-8_7. — [doi:10.1007/978-3-540-75538-8_7](https://doi.org/10.1007/978-3-540-75538-8_7) find
  61. Levente Kocsis and Csaba Szepesvári. Bandit based monte-carlo planning. In Machine Learning: ECML 2006, 17th European Conference on Machine Learning, Berlin, Germany, September 18-22, 2006, Proceedings, pages 282–293, 2006. doi: 10.1007/11871842_29. — [doi:10.1007/11871842_29](https://doi.org/10.1007/11871842_29) find
  62. David Silver, Aja Huang, Chris J. Maddison, Arthur Guez, Laurent Sifre, George van den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Vedavyas Panneershelvam, Marc Lanctot, Sander Dieleman, Dominik Grewe, John Nham, Nal Kalchbrenner, Ilya Sutskever, Timothy P. Lillicrap, Madeleine Leach, Koray… find
  63. Marwin H. S. Segler, Mike Preuß, and Mark P. Waller. Towards "alphachem": Chemical synthesis planning with tree search and deep neural network policies. CoRR, abs/1702.00020, 2017. — [arXiv:1702.00020](https://arxiv.org/abs/1702.00020) find
  64. Mark E. Stickel. A prolog technology theorem prover. New Generation Comput., 2(4):371–383, 1984. doi: 10.1007/BF03037328. — [doi:10.1007/bf03037328](https://doi.org/10.1007/bf03037328) find
  65. Cezary Kaliszyk, François Chollet, and Christian Szegedy. Holstep: A machine learning dataset for higher-order logic theorem proving. In International Conference on Learning Representations (ICLR), 2017. find
  66. Sarah M. Loos, Geoffrey Irving, Christian Szegedy, and Cezary Kaliszyk. In International Conferences on Logic for Programming, Artificial Intelligence and Reasoning (LPAR), 2017. find
  67. Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
  68. Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the Thirteenth International Conference on Artificial Intelligence and Statistics, AISTATS 2010, Chia Laguna Resort, Sardinia, Italy, May 13-15, 2010, pages 249–256, 2010. find
  69. Martín Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Gregory S. Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Ian J. Goodfellow, Andrew Harp, Geoffrey Irving, Michael Isard, Yangqing Jia, Rafal Józefowicz, Lukasz Kaiser, Manjunath Kudlur, Josh Le… — TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systems

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/rocktaschel-2017-end-end-differentiable-proving/