Differentiable learning of automata



Learning stack machines, random access machines, nested hierarchical parsing machines, Turing machines and whatever other automata-with-memory that you wish, from data. In other words, teaching computers to program themselves, via a deep learning formalism.

Differentiable pointers

This is a kind of obvious idea and there are some charming toy examples. Indeed this is wort-of what we have traditionally imagined AI might do.

Obviously a hypothetical superhuman Artificial General Intelligence would be good at handling computer-science problems; It’s not the absolute hippest research area right now though, on account of being hard in general, just like we always imagined from earlier attempts. Some progress has been made. My sense is that most of the hyped research that looks like differentiable computer learning is in the slightly-better-contained area of reinforcement learning where more progress can be made, or in the hot area of transformer networks which are harder to explain but solve the same kind of problems whilst looking different inside..

Related: grammatical inference.

Incoming

Blazek claims his neural networks implement predicate logic directly and yet are tractable which would be interesting to look into [Blazek and Lin (2021);BlazekNeural2020;BlazekDeep2021].

Google branded: Differentiable neural computers.

Christopher Olah’s Characteristically pedagogic intro

Adrian Colyer’s introduction to neural Turing machines.

Andrej Karpathy’s memory machine list has some good starting point.

Facebook’s GTN might solve this kind of problem:

GTN is an open source framework for automatic differentiation with a powerful, expressive type of graph called weighted finite-state transducers (WFSTs). Just as PyTorch provides a framework for automatic differentiation with tensors, GTN provides such a framework for WFSTs. AI researchers and engineers can use GTN to more effectively train graph-based machine learning models.

References

Blazek, Paul J., and Milo M. Lin. 2020. A Neural Network Model of Perception and Reasoning.” arXiv:2002.11319 [Cs, q-Bio], February.
———. 2021. Explainable Neural Networks That Simulate Reasoning.” Nature Computational Science 1 (9): 607–18.
Blazek, Paul J., Kesavan Venkatesh, and Milo M. Lin. 2021. Deep Distilling: Automated Code Generation Using Explainable Deep Learning.” arXiv:2111.08275 [Cs], November.
Bottou, Leon. 2011. From Machine Learning to Machine Reasoning.” arXiv:1102.1808 [Cs], February.
Clark, Peter, Oyvind Tafjord, and Kyle Richardson. 2020. Transformers as Soft Reasoners over Language.” In IJCAI 2020.
Ellis, Kevin, Armando Solar-Lezama, and Josh Tenenbaum. 2016. Sampling for Bayesian Program Learning.” In Advances in Neural Information Processing Systems 29, edited by D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett, 1289–97. Curran Associates, Inc.
Graves, Alex, Greg Wayne, and Ivo Danihelka. 2014. Neural Turing Machines.” arXiv:1410.5401 [Cs], October.
Graves, Alex, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska-Barwińska, Sergio Gómez Colmenarejo, et al. 2016. Hybrid Computing Using a Neural Network with Dynamic External Memory.” Nature advance online publication (October).
Grefenstette, Edward, Karl Moritz Hermann, Mustafa Suleyman, and Phil Blunsom. 2015. Learning to Transduce with Unbounded Memory.” arXiv:1506.02516 [Cs], June.
Gulcehre, Caglar, Sarath Chandar, Kyunghyun Cho, and Yoshua Bengio. 2016. Dynamic Neural Turing Machine with Soft and Hard Addressing Schemes.” arXiv:1607.00036 [Cs], June.
Hannun, Awni, Vineel Pratap, Jacob Kahn, and Wei-Ning Hsu. 2020. Differentiable Weighted Finite-State Transducers.” arXiv:2010.01003 [Cs, Stat], October.
Jaitly, Navdeep, David Sussillo, Quoc V. Le, Oriol Vinyals, Ilya Sutskever, and Samy Bengio. 2015. A Neural Transducer.” arXiv:1511.04868 [Cs], November.
Kaiser, Łukasz, and Ilya Sutskever. 2015. Neural GPUs Learn Algorithms.” arXiv:1511.08228 [Cs], November.
Kim, Jason Z., and Dani S. Bassett. 2022. A Neural Programming Language for the Reservoir Computer.” arXiv:2203.05032 [Cond-Mat, Physics:nlin], March.
Lamb, Luis C., Artur Garcez, Marco Gori, Marcelo Prates, Pedro Avelar, and Moshe Vardi. 2020. Graph Neural Networks Meet Neural-Symbolic Computing: A Survey and Perspective.” In IJCAI 2020.
Lample, Guillaume, and François Charton. 2019. Deep Learning for Symbolic Mathematics.” arXiv:1912.01412 [Cs], December.
Looks, Moshe, Marcello Herreshoff, DeLesley Hutchins, and Peter Norvig. 2017. Deep Learning with Dynamic Computation Graphs.” In Proceedings of ICLR.
Perez, Julien, and Fei Liu. 2016. Gated End-to-End Memory Networks.” arXiv:1610.04211 [Cs, Stat], October.
Putzky, Patrick, and Max Welling. 2017. Recurrent Inference Machines for Solving Inverse Problems.” arXiv:1706.04008 [Cs], June.
Wang, Cheng, and Mathias Niepert. 2019. State-Regularized Recurrent Neural Networks.” arXiv.
Wang, Xin, Yudong Chen, and Wenwu Zhu. 2021. A Survey on Curriculum Learning.” arXiv.
Wei, Qi, Kai Fan, Lawrence Carin, and Katherine A. Heller. 2017. An Inner-Loop Free Solution to Inverse Problems Using Deep Neural Networks.” arXiv:1709.01841 [Cs], September.
Weston, Jason, Sumit Chopra, and Antoine Bordes. 2014. Memory Networks.” arXiv:1410.3916 [Cs, Stat], October.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.