CoChat
Sign Up
PreprintCited by 58AI-based Problem Solving and PlanningBayesian Modeling and Causal InferenceLogic, Reasoning, and Knowledge

Making sense of sensory input

Open access
Evans, Richard, Hernandez-Orallo, Jose, Welbl, Johannes, Kohli, Pushmeet, Sergot, Marek·2019·arXiv
DOI 10.48550/arxiv.1910.02227arXiv 1910.02227
Open this paper in CoChat — free accountOpen PDF

Abstract

This paper attempts to answer a central question in unsupervised learning: what does it mean to "make sense" of a sensory sequence? In our formalization, making sense involves constructing a symbolic causal theory that both explains the sensory sequence and also satisfies a set of unity conditions. The unity conditions insist that the constituents of the causal theory -- objects, properties, and laws -- must be integrated into a coherent whole. On our account, making sense of sensory input is a type of program synthesis, but it is unsupervised program synthesis. Our second contribution is a computer implementation, the Apperception Engine, that was designed to satisfy the above requirements. Our system is able to produce interpretable human-readable causal theories from very small amounts of data, because of the strong inductive bias provided by the unity conditions. A causal theory produced by our system is able to predict future sensor readings, as well as retrodict earlier readings, and impute (fill in the blanks of) missing sensory readings, in any combination. We tested the engine in a diverse variety of domains, including cellular automata, rhythms and simple nursery tunes, multi-modal binding problems, occlusion tasks, and sequence induction intelligence tests. In each domain, we test our engine's ability to predict future sensor values, retrodict earlier sensor values, and impute missing sensory data. The engine performs well in all these domains, significantly out-performing neural net baselines. We note in particular that in the sequence induction intelligence tests, our system achieved human-level performance. This is notable because our system is not a bespoke system designed specifically to solve intelligence tests, but a general-purpose system that was designed to make sense of any sensory sequence.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1910.02227

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Much recent work in ILP uses ASP to learn Datalog, definite, normal, and answer set programs.

    “Much recent work in ILP uses ASP to learn Datalog (Evans et al. 2019), definite (Muggleton et al. 2014; Kaminski et al. 2018; Cropper and Dumancic 2020), normal (Ray 2009; Corapi et al. 2011; Athakravi et al. 2013), and answer set programs (Law et al. 2014).”

    From Learning programs by learning from failures (2021) · cites this paper as Evans et al. 2019

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 82

  1. M. Mathieu, C. Couprie, Y. LeCun, Deep multi-scale video prediction beyond mean square error, e-prints, arXiv:1511.05440, 2015. · arXiv
  2. C. Finn, S. Levine, Deep visual foresight for planning robot motion, in: IEEE International Conference on Robotics and Automation, ICRA, IEEE, 2017, pp. 2786-2793.
  3. S. Racanière, T. Weber, D. Reichert, L. Buesing, A. Guez, D.J. Rezende, A.P. Badia, O. Vinyals, N. Heess, Y. Li, et al., Imagination-augmented agents for deep reinforcement learning, in: Advances in Neural Information Processing Systems, NEURIPS, 2017, pp. 5690-5701.
  4. Z. Liu, R.A. Yeh, X. Tang, Y. Liu, A. Agarwala, Video frame synthesis using deep voxel flow, in: ICCV, 2017, pp. 4473-4481.
  5. L. Buesing, T. Weber, S. Racaniere, S.M.A. Eslami, D. Rezende, D.P. Reichert, F. Viola, F. Besse, K. Gregor, D. Hassabis, D. Wierstra, Learning and querying fast generative models for reinforcement learning, e-prints, arXiv:1802 .03006, 2018.
  6. C. Diuk, A. Cohen, M.L. Littman, An object-oriented representation for efficient reinforcement learning, in: Proceedings of the 25th International Conference on Machine Learning, 2008, pp. 240-247.
  7. J. McCarthy, Challenges to machine learning: relations between reality and appearance, in: International Conference on Inductive Logic Programming, Springer, 2006, pp. 2-9.
  8. G.W. Leibniz, G.W.F. von Leibniz, Leibniz: New Essays on Human Understanding, Cambridge University Press, 1996.
  9. K. Ellis, A. Solar-Lezama, J. Tenenbaum, Unsupervised learning by program synthesis, in: Advances in Neural Information Processing Systems, NEURIPS, 2015, pp. 973-981.
  10. K.J.W. Craik, The Nature of Explanation, vol. 445, CUP Archive, 1967.
  11. P.L. Harris, The Work of the Imagination, Blackwell Publishers, Oxford, 2000.
  12. T. Gerstenberg, J.B. Tenenbaum, Intuitive theories, in: Oxford Handbook of Causal Reasoning, 2017, pp. 515-548.
  13. L. Kaiser, M. Babaeizadeh, P. Milos, Model based reinforcement learning for Atari, preprint, arXiv:1903 .00374v2, 2019.
  14. Z. Ghahramani, An introduction to hidden Markov models and Bayesian networks, in: Hidden Markov models: Applications in Computer Vision, World Scientific, 2001, pp. 9-41.
  15. V. Feinberg, A. Wan, I. Stoica, M. Jordan, J. Gonzalez, S. Levine, Model-based value expansion for efficient model-free reinforcement learning, in: Proceedings of the 35th International Conference on Machine Learning, ICML, 2018.
  16. A. Nagabandi, G. Kahn, R.S. Fearing, S. Levine, Neural network dynamics for model-based deep reinforcement learning with model-free fine-tuning, in: 2018 IEEE International Conference on Robotics and Automation, ICRA, IEEE, 2018, pp. 7559-7566.
  17. P. Battaglia, R. Pascanu, M. Lai, D.J. Rezende, et al., Interaction networks for learning about objects, relations and physics, in: Advances in Neural Information Processing Systems, NEURIPS, 2016, pp. 4502-4510.
  18. M.B. Chang, T. Ullman, A. Torralba, J.B. Tenenbaum, A compositional object-based approach to learning physical dynamics, e-prints, arXiv:1612 .00341, 2016.
  19. D. Mrowca, C. Zhuang, E. Wang, N. Haber, L.F. Fei-Fei, J. Tenenbaum, D.L. Yamins, Flexible neural representation for physics prediction, in: Advances in Neural Information Processing Systems, NEURIPS, 2018, pp. 8813-8824.
  20. A. Sanchez-Gonzalez, N. Heess, J.T. Springenberg, J. Merel, M. Riedmiller, R. Hadsell, P. Battaglia, Graph networks as learnable physics engines for inference and control, preprint, arXiv:1806 .01242, 2018.
  21. A. Lerer, S. Gross, R. Fergus, Learning physical intuition of block towers by example, e-prints, arXiv:1603 .01312, 2016.
  22. A. Bhattacharyya, M. Malinowski, B. Schiele, M. Fritz, Long-term image boundary prediction, in: AAAI Conference on Artificial Intelligence, 2018, pp. 34-50.
  23. J. Oh, X. Guo, H. Lee, R.L. Lewis, S. Singh, Action-conditional video prediction using deep networks in Atari games, in: Advances in Neural Information Processing Systems, NEURIPS, 2015, pp. 2863-2871.
  24. S. Chiappa, S. Racaniere, D. Wierstra, S. Mohamed, Recurrent environment simulators, e-prints, arXiv:1704 .02254, 2017.
  25. D. Ha, J. Schmidhuber, Recurrent world models facilitate policy evolution, in: Advances in Neural Information Processing Systems, NEURIPS, 2018, pp. 2455-2467.
  26. M. Janner, S. Levine, W.T. Freeman, J.B. Tenenbaum, C. Finn, J. Wu, Reasoning about physical interactions with object-oriented prediction and planning, e-prints, arXiv:1812 .10972, 2018.
  27. A. Zhang, A. Lerer, S. Sukhbaatar, R. Fergus, A. Szlam, Composable planning with attributes, in: Proceedings of the International Conference on Machine Learning, vol. 11, ICML, 2018, pp. 11-22.
  28. Z. Xu, Z. Liu, C. Sun, K. Murphy, W. Freeman, J. Tennenbaum, J. Wu, Unsupervised discovery of parts, structure, and dynamics, in: Proceedings of the International Conference on Learning Representations, ICLR, 2019, pp. 1418-1424.
  29. M. Asai, A. Fukunaga, Classical planning in deep latent space: bridging the subsymbolic-symbolic boundary, in: AAAI Conference on Artificial Intelli- gence, 2018, pp. 45-62.
  30. M. Asai, Unsupervised grounding of plannable first-order logic representation from images, e-prints, arXiv:1902 .08093, 2019.
  31. E. Michelioudakis, A. Skarlatidis, G. Paliouras, A. Artikis, Online structure learning using background knowledge axiomatization, in: Joint European Conference on Machine Learning and Knowledge Discovery in Databases, Springer, 2016, pp. 232-247.
  32. E. Michelioudakis, A. Artikis, G. Paliouras, Semi-supervised online structure learning for composite event recognition, preprint, arXiv:1803 .00546, 2018.
  33. R. Kowalski, Predicate logic as programming language, in: IFIP Congress, Vol. 74, 1974, pp. 544-569.
  34. K.R. Apt, Logic programming, in: Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics, 1990, pp. 493-574.
  35. J.W. Lloyd, Foundations of Logic Programming, Springer Science & Business Media, 1987.
  36. M.H. Van Emden, R.A. Kowalski, The semantics of predicate logic as a programming language, J. ACM 23 (4) (1976) 733-742.
  37. M. Gelfond, V. Lifschitz, The stable model semantics for logic programming, in: Proc. Fifth International Conference on Logic Programming, in: Logic Programming, vol. 88, MIT Press, 1988, pp. 1070-1080.
  38. R. Kowalski, Logic for Problem-Solving, Elsevier North-Holland, 1979.
  39. I. Kant, Critique of Pure Reason, Cambridge University Press, 1781.
  40. K.L. Clark, Negation as failure, in: Logic and Databases, Springer, 1978, pp. 293-322.
  41. A. Van Gelder, K.A. Ross, J.S. Schlipf, The well-founded semantics for general logic programs, J. ACM 38 (3) (1991) 619-649.
  42. C. Henson, A. Sheth, K. Thirunarayan, Semantic perception: converting sensory observations to abstractions, IEEE Internet Comput. 16 (2) (2012) 26-34.
  43. M. Gebser, R. Kaminski, B. Kaufmann, T. Schaub, Clingo = ASP + control: preliminary report, e-prints, arXiv:1405 .3694, 2014.
  44. E. Dantsin, T. Eiter, G. Gottlob, A. Voronkov, Complexity and expressive power of logic programming, ACM Comput. Surv. 33 (3) (2001) 374-425.
  45. G. Brewka, I. Niemelä, M. Truszczynski, Answer set optimization, in: Proceedings of the International Joint Conference on Artificial Intelligence, vol. 3, IJCAI, 2003, pp. 867-872.
  46. R. Morel, A. Cropper, L. Ong, Typed meta-interpretive learning of logic programs, in: European Conference on Logics in Artificial Intelligence, JELIA, 2019, pp. 973-981.
  47. M. Mitchell, Analogy-Making as Perception, MIT Press, 1993.
  48. L.L. Thurstone, T.G. Thurstone, Factorial Studies of Intelligence, Psychometric Monographs, 1941, pp. 8-23.
  49. J. Hernandez-Orallo, N. Minaya-Collado, A formal definition of intelligence, in: Proceedings of International Symposium of Engineering of Intelligent Systems, EIS 98, 1998, pp. 146-163.
  50. D.G.T. Barrett, F. Hill, A. Santoro, A.S. Morcos, T. Lillicrap, Measuring abstract reasoning in neural networks, e-prints, arXiv:1807.04225, 2018. · arXiv
  51. A. Holcombe, The binding problem, in: The Sage Encyclopedia of Perception, 2009, pp. 47-71.
  52. K.P. Murphy, Machine Learning: A Probabilistic Perspective, MIT Press, 2012.
  53. D.P. Kingma, J. Ba, Adam: a method for stochastic optimization, e-prints, arXiv:1412 .6980, 2014.
  54. S.H. Muggleton, D. Lin, A. Tamaddoni-Nezhad, Meta-interpretive learning of higher-order dyadic datalog: predicate invention revisited, Mach. Learn. 100 (1) (2015) 49-73, https://doi .org /10 .1007 /s10994 -014 -5471 -y. · DOI · Paper page
  55. A. Cropper, S.H. Muggleton, Learning efficient logic programs, Mach. Learn. (2018) 1-21, https://doi .org /10 .1007 /s10994 -018 -5712 -6. · DOI
  56. M. Law, A. Russo, K. Broda, Inductive learning of answer set programs, in: European Conference on Logics in Artificial Intelligence -(JELIA), 2014, pp. 311-325.
  57. E.T. Mueller, Commonsense Reasoning, Morgan Kaufmann, 2014.
  58. M. Gelfond, Y. Kahl, Knowledge Representation, Reasoning, and the Design of Intelligent Agents, Cambridge University Press, 2014.
  59. A. Cropper, S.H. Muggleton, Learning higher-order logic programs through abstraction and invention, in: Proceedings of the International Joint Con- ference on Artificial Intelligence, IJCAI, IJCAI/AAAI Press, 2016, pp. 1418-1424.
  60. A. Cropper, Efficiently learning efficient programs, Ph.D. thesis, Imperial College, London, UK, 2017, http://hdl .handle .net /10044 /1 /58488.
  61. T. Ribeiro, K. Inoue, Learning prime implicant conditions from interpretation transition, in: Inductive Logic Programming, Springer, 2015, pp. 108-125.
  62. T. Ribeiro, M. Magnin, K. Inoue, C. Sakama, Learning multi-valued biological models with delayed influence from time-series observations, in: 2015 IEEE 14th International Conference on Machine Learning and Applications, ICMLA, 2015, pp. 25-31.
  63. T. Ribeiro, M. Folschette, M. Magnin, O. Roux, K. Inoue, Learning dynamics with synchronous, asynchronous and general semantics, in: International Conference on Inductive Logic Programming, Springer, 2018, pp. 118-140.
  64. T. Ribeiro, S. Tourret, M. Folschette, M. Magnin, D. Borzacchiello, F. Chinesta, O. Roux, K. Inoue, Inductive learning from state transitions over contin- uous domains, in: International Conference on Inductive Logic Programming, Springer, 2017, pp. 124-139.
  65. S. Tourret, E. Gentet, K. Inoue, Learning human-understandable description of dynamical systems from feed-forward neural networks, in: International Symposium on Neural Networks, Springer, 2017, pp. 483-492.
  66. Y. Phua, T. Ribeiro, S. Tourret, K. Inoue, Learning logic program representation for delayed systems with limited training data, in: Inductive Logic Programming, Springer, 2017, pp. 103-119.
  67. A. Solar-Lezama, L. Tancau, R. Bodik, S. Seshia, V. Saraswat, Combinatorial sketching for finite programs, ACM SIGPLAN Not. 41 (11) (2006) 404-415.
  68. D. Corapi, A. Russo, E. Lupu, Inductive logic programming in answer set programming, in: Inductive Logic Programming, Springer, 2012, pp. 91-97.
  69. M. Genesereth, N. Love, General Game Playing: Game Description Language Specification, Computer Science Department, Stanford University, Stanford, CA, USA, Tech. Rep., 2005, pp. 1-48.
  70. S. Moyle, Using theory completion to learn a robot navigation control program, in: International Conference on Inductive Logic Programming, Springer, 2002, pp. 182-197.
  71. R.P. Otero, Induction of the indirect effects of actions by monotonic methods, in: International Conference on Inductive Logic Programming, Springer, 2005, pp. 279-294.
  72. K. Inoue, H. Bando, H. Nabeshima, Inducing causal laws by regular inference, in: International Conference on Inductive Logic Programming, Springer, 2005, pp. 154-171.
  73. D. Corapi, D. Sykes, K. Inoue, A. Russo, Probabilistic rule learning in nonmonotonic domains, in: International Workshop on Computational Logic in Multi-Agent Systems, Springer, 2011, pp. 243-258.
  74. C. Rodrigues, P. Gérard, C. Rouveirol, H. Soldano, Active learning of relational action models, in: International Conference on Inductive Logic Program- ming, Springer, 2011, pp. 302-316.
  75. L. De Raedt, Logical and Relational Learning, Springer Science & Business Media, 2008.
  76. L. Bu, R. Babu, B. De Schutter, et al., A comprehensive survey of multiagent reinforcement learning, IEEE Trans. Syst. Man Cybern., Part C, Appl. Rev. 38 (2) (2008) 156-172.
  77. J. Goodacre, Inductive learning of chess rules using progol, Ph.D. thesis, University of Oxford, 1996.
  78. K. Friston, A theory of cortical responses, Philos. Trans. R. Soc. Lond. B, Biol. Sci. 360 (1456) (2005) 815-836.
  79. E. Dechter, J. Malmaud, R.P. Adams, J.B. Tenenbaum, Bootstrap learning via modular concept discovery, in: Proceedings of the International Joint Conference on Artificial Intelligence, AAAI Press, 2013.
  80. R.J. Henderson, Cumulative learning in the lambda calculus, Ph.D. thesis, Imperial College London, 2013.
  81. K. Ellis, L. Morales, M. Sablé-Meyer, A. Solar-Lezama, J. Tenenbaum, Learning libraries of subroutines for neurally-guided bayesian program induction, in: Advances in Neural Information Processing Systems, 2018, pp. 7805-7815.
  82. K. Ellis, C. Wong, M. Nye, M. Sable-Meyer, L. Cary, L. Morales, L. Hewitt, A. Solar-Lezama, J.B. Tenenbaum, Dreamcoder: growing generalizable, inter- pretable knowledge with wake-sleep bayesian program learning, preprint, arXiv:2006 .08381, 2020.

Cited by

Sorted by citations

Authors
Evans, R., Hernandez-Orallo, J., Welbl, J., Kohli, P., & Sergot, M.
Affiliations
  • Google (United States) (US)
  • Google DeepMind (United Kingdom) (GB)
  • Imperial College London (GB)
Corresponding author
Evans, Richard
ORCID
Venue
arXiv
Publisher
arXiv
Published
2019
Volume
293
Pages
103438-103438
ISSN
0004-3702 (ISSN-L)
DOI
10.48550/arxiv.1910.02227
arXiv
1910.02227
OpenAlex
W2977998177
Cited by
58
References
0
Citations by year
2025: 4 · 2024: 4 · 2023: 25 · 2022: 10 · 2021: 13 · 2020: 1
FWCI
4.55
Type
journal article
Language
en
Open access
Licence
Locations
  • Artificial Intelligence (publishedVersion, cc-by)
  • RiuNet (Universitat Politècnica de València) (publishedVersion, cc-by)
  • arXiv (Cornell University) (submittedVersion)
  • PhilPapers (PhilPapers Foundation) (submittedVersion)
  • arXiv (Cornell University)
Funders
  • Future of Life Institute (RFP2-152)
  • European Commission
  • Federación Española de Enfermedades Raras
  • Ministerio de Economía y Competitividad (RTI2018-094403-B-C32)
  • Generalitat Valenciana (PROMETEO/2019/098)
  • European Regional Development Fund
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › AI-based Problem Solving and Planning
  • Physical Sciences › Computer Science › Artificial Intelligence › Bayesian Modeling and Causal Inference
  • Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
Keywords
unsupervised learning, program synthesis, inductive bias, retrodiction, missing data imputation, interpretability, occlusion, intelligence tests

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review