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

Making sense of sensory input

Open access
Evans, Richard, Hernández-Orallo, José, Welbl, Johannes, Kohli, Pushmeet, Sergot, Marek·2021·Artificial Intelligence
DOI 10.1016/j.artint.2020.103438
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. In fact, it is able to do all three tasks simultaneously. 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 Apperception 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

Crossref · 10.1016/j.artint.2020.103438

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?

  • Pure ASP-based systems struggle to handle infinite domains because most current ASP solvers only work on ground programs and need a finite grounding.

    “Pure ASP-based systems (Corapi et al., 2011; Kaminski et al., 2018; Evans et al., 2021) struggle to handle infinite domains because (most) current ASP solvers only work on ground programs, i.e. they need a finite grounding.”

    From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Evans et al., 2021

    Section 5.2.4 says that both the authors’ system and ILASP ground ASP programs into propositional clauses before solving, and that grounding size affects memory use. It reports that some ILASP programs were unsolvable because they required too much memory. The paper does not establish that most current ASP solvers work only on ground programs or directly assess pure ASP-based systems on infinite domains. (LLM, conf=0.82)

    Experimental — accuracy not yet measured

  • Generating all possible invented predicates is computationally expensive.

    “However, this placeholder approach is limited because it requires that a user manually specify the arity and argument types of a symbol (Law et al., 2014), which rather defeats the point, or requires generating all possible invented predicates (Evans & Grefenstette, 2018; Evans et al., 2021), which is computationally expensive.”

    From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Evans et al., 2021

    Section 4.1 says the system enumerates templates that include predicate sets, but cannot enumerate all such templates at once because there are infinitely many. Section 4.4 describes substantial computational costs, and the Conclusion says search-space size restricts the system to small-to-medium-size problems. The paper does not specifically establish the cost of generating all possible invented predicates as a separate approach. (LLM, conf=0.80)

    Experimental — accuracy not yet measured

  • The placeholder approach to predicate invention requires generating all possible invented predicates.

    “However, this placeholder approach is limited because it requires that a user manually specify the arity and argument types of a symbol (Law et al., 2014), which rather defeats the point, or requires generating all possible invented predicates (Evans & Grefenstette, 2018; Evans et al., 2021), which is computationally expensive.”

    From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Evans et al., 2021

    Section 4.1, “Iterating through templates” (page unavailable), says the method enumerates templates that include sets of predicates. But it explicitly says it cannot enumerate all such tuples because there are infinitely many; it uses a bound that increases gradually instead. Section 4.4 discusses computational cost, but does not establish that all possible invented predicates must be generated. (LLM, conf=0.85)

    Experimental — accuracy not yet measured

  • A handful of approaches have started to tackle the problem of learning from raw data.

    “A handful of approaches have started to tackle this problem (Manhaeve et al., 2018; Dai et al., 2019; Evans et al., 2021; Dai & Muggleton, 2021), but developing better ILP techniques that can both perceive sensory input and learn complex relational programs would be a major breakthrough not only for ILP, but the whole of AI.”

    From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Evans et al., 2021

    The Introduction describes the Apperception Engine as learning a symbolic program from a sensory sequence, so this paper is an example of an approach tackling the problem. But the Conclusion states that its sensory input must first be discretized by another system; the reported engine does not learn directly from raw continuous data. (LLM, conf=0.85)

    Experimental — accuracy not yet measured

  • Because of the expressivity of logic programs, ILP can learn complex relational theories, such as cellular automata, event calculus theories, and Petri nets, and various forms of non-monotonic programs.

    “Because of the expressivity of logic programs, ILP can learn complex relational theories, such as cellular automata (Inoue et al., 2014; Evans et al., 2021), event calculus theories (Katzouris et al., 2015), and Petri nets (Bain & Srinivasan, 2018), and various forms of non-monotonic programs (Bain & Muggleton, 1991; Inoue & Kudoh, 1997; Sakama, 2001).”

    From Inductive Logic Programming At 30: A New Introduction (2022) · cites this paper as Evans et al., 2021

Self-check

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

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

The citation lists haven’t been fetched yet

References 134 · Cited by 58

Research works printed but not linked: 79

  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. A. Cropper, S.H. Muggleton, Learning efficient logic programs, Mach. Learn. (2018) 1-21, https://doi .org /10 .1007 /s10994 -018 -5712 -6. · DOI
  54. E.T. Mueller, Commonsense Reasoning, Morgan Kaufmann, 2014.
  55. M. Gelfond, Y. Kahl, Knowledge Representation, Reasoning, and the Design of Intelligent Agents, Cambridge University Press, 2014.
  56. 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.
  57. A. Cropper, Efficiently learning efficient programs, Ph.D. thesis, Imperial College, London, UK, 2017, http://hdl .handle .net /10044 /1 /58488.
  58. T. Ribeiro, K. Inoue, Learning prime implicant conditions from interpretation transition, in: Inductive Logic Programming, Springer, 2015, pp. 108-125.
  59. 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.
  60. 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.
  61. 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.
  62. 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.
  63. 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.
  64. A. Solar-Lezama, L. Tancau, R. Bodik, S. Seshia, V. Saraswat, Combinatorial sketching for finite programs, ACM SIGPLAN Not. 41 (11) (2006) 404-415.
  65. D. Corapi, A. Russo, E. Lupu, Inductive logic programming in answer set programming, in: Inductive Logic Programming, Springer, 2012, pp. 91-97.
  66. 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.
  67. S. Moyle, Using theory completion to learn a robot navigation control program, in: International Conference on Inductive Logic Programming, Springer, 2002, pp. 182-197.
  68. 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.
  69. K. Inoue, H. Bando, H. Nabeshima, Inducing causal laws by regular inference, in: International Conference on Inductive Logic Programming, Springer, 2005, pp. 154-171.
  70. 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.
  71. 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.
  72. L. De Raedt, Logical and Relational Learning, Springer Science & Business Media, 2008.
  73. 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.
  74. J. Goodacre, Inductive learning of chess rules using progol, Ph.D. thesis, University of Oxford, 1996.
  75. K. Friston, A theory of cortical responses, Philos. Trans. R. Soc. Lond. B, Biol. Sci. 360 (1456) (2005) 815-836.
  76. 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.
  77. R.J. Henderson, Cumulative learning in the lambda calculus, Ph.D. thesis, Imperial College London, 2013.
  78. 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.
  79. 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.

Authors
Evans, R., Hernández-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
Artificial Intelligence
Publisher
Elsevier BV
Published
2021-04
Volume
293
Pages
103438
ISSN
0004-3702 (ISSN-L)
DOI
10.1016/j.artint.2020.103438
OpenAlex
W2977998177
Cited by
58
References
134
Citations by year
2025: 4 · 2024: 4 · 2023: 25 · 2022: 10 · 2021: 13 · 2020: 1
FWCI
4.59
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
  • European Commission
  • Generalitat Valenciana (PROMETEO/2019/098)
  • Ministerio de Economía y Competitividad (RTI2018-094403-B-C32)
  • 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