Elamur Research⌕
☰
home / papers / 2018 / Can Neural Networks Understand Logical Entailment?

Can Neural Networks Understand Logical Entailment?

Paper · 2018 · Richard Evans, David Saxton, David Amos et al.

Summary

The paper asks whether neural networks can decide if one propositional formula logically entails another. The task works as a clean probe of how well architectures capture purely structural properties of sequences, because variable names carry no meaning and only the connectives matter. The DeepMind authors build a new dataset of triples (A, B, label), with labels computed by the minisat solver. To remove trivial cues, they generate formulas in 4-tuples so that every formula appears in exactly one positive and one negative pair. This equalises length and operator statistics across the two classes. The test splits range from small formulas to very large ones, plus a set of textbook examples. Test and validation formulas that are α-equivalent to training formulas are filtered out. The authors compare bag-of-words baselines, convolutional networks, LSTMs and tree-structured networks. They also introduce PossibleWorldNet, a TreeNet variant inspired by model-theoretic semantics that evaluates formulas across many "possible worlds". Convolutional models show an unsuitable inductive bias, tree models beat LSTMs by exploiting syntax, and PossibleWorldNet outperforms every benchmark. The work provides a testbed for studying structural reasoning and inductive biases.

Key points

  • Dataset sizes: 100,000 train, 5,000 validation, and 5,000 each for test (easy), (hard) and (big). Test (massive) has 2,230 items and test (exam) has 100 items drawn from logic textbooks.
  • Variables and difficulty: formulas use up to 26 variables (a–z). Mean 2^#vars, a proxy for difficulty, grows from about 52 in train to about 848,570 in test (massive).
  • Debiasing: naive sampling leaks shortcuts. For example, positive premises are satisfied by about 3.7 truth assignments on average versus 10.3 for negatives. The 4-tuple scheme brings length and operator-count differences to zero, leaving only a small gap in new variables (1.25 vs 1.60).
  • Anti-memorisation and augmentation: de-Bruijn normal forms are used to drop α-equivalent duplicates. During training, variables are randomly permuted within each example, similar to image crops or flips.
  • Models compared: Linear BoW, MLP BoW, CNNs, LSTMs, TreeNets and the new PossibleWorldNet. Random or majority-class guessing scores 50% because the classes are balanced.

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

🏢GoogleMountain View · United States533 works · 443,885 citations

Also on the byline: University of Westminster.

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 19,503 worksArtificial Intelligence · 18,805 worksArts and Humanities · 17,959 worksLanguage and Linguistics · 17,789 works

Cite

Cite as Richard Evans, David Saxton, David Amos, Pushmeet Kohli and Edward Grefenstette. 2018. Can Neural Networks Understand Logical Entailment?. arXiv:1802.08535.

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

@misc{evans2018can,
  title = {{Can Neural Networks Understand Logical Entailment?}},
  author = {Richard Evans, David Saxton, David Amos, Pushmeet Kohli and Edward Grefenstette},
  year = {2018},
  doi = {10.48550/arxiv.1802.08535},
  eprint = {1802.08535},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1802.08535}
}

References

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

  1. Martı́n Abadi, Ashish Agarwal, Paul Barham, Eugene Brevdo, Zhifeng Chen, Craig Citro, Greg S Corrado, Andy Davis, Jeffrey Dean, Matthieu Devin, et al. Tensorflow: Large-scale machine learning on heterogeneous distributed systems. arXiv preprint arXiv:1603.04467, 2016.
  2. Miltiadis Allamanis, Pankajan Chanthirasegaran, Pushmeet Kohli, and Charles Sutton. Learning continuous semantic representations of symbolic expressions. arXiv preprint arXiv:1611.01423, 2016.
  3. Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473, 2014.
  4. Samuel R Bowman, Gabor Angeli, Christopher Potts, and Christopher D Manning. A large annotated corpus for learning natural language inference. arXiv preprint arXiv:1508.05326, 2015.
  5. Ido Dagan, Oren Glickman, and Bernardo Magnini. The pascal recognising textual entailment challenge. In Machine learning challenges. evaluating predictive uncertainty, visual object classification, and recognising tectual entailment, pp. 177–190. Springer, 2006. find
  6. Jacob Devlin, Jonathan Uesato, Surya Bhupatiraju, Rishabh Singh, Abdel-rahman Mohamed, and Pushmeet Kohli. Robustfill: Neural program learning under noisy i/o. arXiv preprint arXiv:1703.07469, 2017. find
  7. Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska-Barwińska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, et al. Hybrid computing using a neural network with dynamic external memory. Nature, 538 (7626):471–476, 2016. find
  8. Edward Grefenstette, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. Learning to transduce with unbounded memory. In Advances in Neural Information Processing Systems, pp. 1828–1836, 2015. find
  9. Karl Moritz Hermann, Tomas Kocisky, Edward Grefenstette, Lasse Espeholt, Will Kay, Mustafa Suleyman, and Phil Blunsom. Teaching machines to read and comprehend. In Advances in Neural Information Processing Systems, pp. 1693–1701, 2015.
  10. Felix Hill, Antoine Bordes, Sumit Chopra, and Jason Weston. The goldilocks principle: Reading children’s books with explicit memory representations. arXiv preprint arXiv:1511.02301, 2015.
  11. Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9(8): 1735–1780, 1997. find
  12. Armand Joulin and Tomas Mikolov. Inferring algorithmic patterns with stack-augmented recurrent nets. In Advances in neural information processing systems, pp. 190–198, 2015. find
  13. Łukasz Kaiser and Ilya Sutskever. Neural gpus learn algorithms. arXiv preprint arXiv:1511.08228, 2015. find
  14. Nal Kalchbrenner and Phil Blunsom. Recurrent continuous translation models. In EMNLP, volume 3, pp. 413, 2013.
  15. Nal Kalchbrenner, Edward Grefenstette, and Phil Blunsom. A convolutional neural network for modelling sentences. arXiv preprint arXiv:1404.2188, 2014.
  16. Yoon Kim, Yacine Jernite, David Sontag, and Alexander M Rush. Character-aware neural language models. In AAAI, pp. 2741–2749, 2016.
  17. Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
  18. Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convolutional neural networks. In Advances in neural information processing systems, pp. 1097–1105, 2012.
  19. Phong Le and Willem Zuidema. Compositional distributional semantics with long short term memory. arXiv preprint arXiv:1503.02510, 2015. find
  20. Yann LeCun, Yoshua Bengio, et al. Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks, 3361(10):1995, 1995. find
  21. Wang Ling, Edward Grefenstette, Karl Moritz Hermann, Tomáš Kočiskỳ, Andrew Senior, Fumin Wang, and Phil Blunsom. Latent predictor networks for code generation. arXiv preprint arXiv:1603.06744, 2016.
  22. Piotr Mirowski, Razvan Pascanu, Fabio Viola, Hubert Soyer, Andy Ballard, Andrea Banino, Misha Denil, Ross Goroshin, Laurent Sifre, Koray Kavukcuoglu, et al. Learning to navigate in complex environments. arXiv preprint arXiv:1611.03673, 2016. find
  23. Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529–533, 2015. find
  24. Emilio Parisotto, Abdel-rahman Mohamed, Rishabh Singh, Lihong Li, Dengyong Zhou, and Pushmeet Kohli. Neuro-symbolic program synthesis. arXiv preprint arXiv:1611.01855, 2016.
  25. Benjamin C Pierce. Types and programming languages. MIT press, 2002. find
  26. Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. Squad: 100,000+ questions for machine comprehension of text. arXiv preprint arXiv:1606.05250, 2016.
  27. Scott Reed and Nando De Freitas. arXiv:1511.06279, 2015. find
  28. Tim Rocktäschel, Edward Grefenstette, Karl Moritz Hermann, Tomáš Kočiskỳ, and Phil Blunsom. Reasoning about entailment with neural attention. arXiv preprint arXiv:1509.06664, 2015.
  29. David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Marc Lanctot, et al. Mastering the game of go with deep neural networks and tree search. Nature, 529(7587):484–489, 2016. find
  30. Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1556, 2014.
  31. Richard Socher, Brody Huval, Christopher D Manning, and Andrew Y Ng. Semantic compositionality through recursive matrix-vector spaces. In Proceedings of the 2012 joint conference on empirical methods in natural language processing and computational natural language learning, pp. 1201–1211. Associati…
  32. Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 conference on empirical methods in natural language processing, pp. 1631–1642, 201…
  33. Niklas Sorensson and Niklas Een. Minisat v1. 13-a sat solver with conflict-clause minimization. SAT, 2005(53):1–2, 2005. find
  34. Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pp. 3104–3112, 2014.
  35. Kai Sheng Tai, Richard Socher, and Christopher D Manning. Improved semantic representations from tree-structured long short-term memory networks. arXiv preprint arXiv:1503.00075, 2015. find
  36. Yuandong Tian and Yan Zhu. Better computer go player with neural network and long-term prediction. arXiv preprint arXiv:1511.06410, 2015. — [arXiv:1511.06410](https://arxiv.org/abs/1511.06410) find
  37. Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems, pp. 6000–6010, 2017.
  38. Shuohang Wang and Jing Jiang. Learning natural language inference with lstm. arXiv preprint arXiv:1512.08849, 2015.
  39. Wenpeng Yin, Hinrich Schütze, Bing Xiang, and Bowen Zhou. Abcnn: Attention-based convolutional neural network for modeling sentence pairs. arXiv preprint arXiv:1512.05193, 2015.
  40. Wojciech Zaremba, Karol Kurach, and Rob Fergus. Learning to discover efficient mathematical identities. In Advances in Neural Information Processing Systems, pp. 1278–1286, 2014. find
  41. Neural programmer-interpreters. arXiv preprint Xiang Zhang, Junbo Zhao, and Yann LeCun. Character-level convolutional networks for text classification. In Advances in neural information processing systems, pp. 649–657, 2015.
  42. Xiaodan Zhu, Parinaz Sobihani, and Hongyu Guo. Long short-term memory over recursive structures. In International Conference on Machine Learning, pp. 1604–1612, 2015. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/evans-2018-can-neural-networks-understand-logical/