Machine learning applied to space-time diagrams of cellular automata

Question

I wonder if machine learning has ever been applied to space-time diagrams of cellular automata. What comprises a training set seems clear: a number of space-time diagrams of one or several (elementary) cellular automata. For a supervised learning task, the corresponding local rules may be given as labels, e.g. in Wolfram's notation. Another label could be the complexity class of the rule (according to some classification, e.g. Wolfram's). But I am more interested in unsupervised learning tasks.

I'm just starting to think about this topic and am not clear, yet, what the purpose of such a learning task should be. It may be (unsupervised) classification, feature extraction, object recognition (objects = gliders), or hypothesis generation ("what's the underlying rule?").

Where can I start or continue my investigation? Has there already work been done into this direction? Is it immediately clear by which ML technique the problem should be approached? Convolutional neural networks?

Answer 1

As you say in your question, there are many directions "machine learning with cellular automata" can take.

Classifying cellular automata space-time diagrams with ML

I know of these two works that use neural networks to classify cellular automata into one of the 4 Wolfram classes:

• https://community.wolfram.com/groups/-/m/t/1417114
• https://direct.mit.edu/isal/proceedings/isal2019/280/99182 [1]

In general, predicting the Wolfram class is tricky because it is not a well-defined notion.

This is part of the larger problem of classifying cellular automata behavior from their space-time diagram (or rule, etc.), for which there are also many non-ML approaches. For example, [2] uses compression to estimate the complexity of the CA, while [3] uses the asymptotic properties of the transient sizes.

In related work [4], Gilpin used a convolutional neural network representation of CA to learn the rules. He estimates the complexity of a rule from "how hard it is to learn that rule."

Cellular automata and neural networks

@Rexcirus has pointed you to the very interesting "Growing neural cellular automata" paper. The same authors have recently been working on a continuous cellular automaton called Lenia, extending it to create Particle Lenia.

The whole idea behind these examples is to use a convolutional neural network to implement a CA-like system. This has many advantages, including being able to use all the NN properties and differentiability to "learn" things with the CA.

There is a fundamental difference between the usual discrete CA and the neural network-based extensions because you move to continuous space. However, there are interesting connections to be made between the two models.

Cellular automata as ML systems

Another approach is using the CA as the basis of a ML system, harvesting its computations to make predictions. This is done with something called reservoir computing. This whole subfield is called reservoir computing with cellular automata (ReCA), and you might be interested in it. Here are a few papers to get you started (including one of mine) [5,6,7,8].

1. Silverman, E. Convolutional Neural Networks for Cellular Automata Classification. Artificial Life Conference Proceedings 31, 280–281 (2019).
2. Zenil, H. Compression-Based Investigation of the Dynamical Properties of Cellular Automata and Other Systems. Complex Systems 19, (2010).
3. Hudcová, B. & Mikolov, T. Classification of Complex Systems Based on Transients. in 367–375 (MIT Press, 2020). doi:10.1162/isal_a_00260.
4. Gilpin, W. Cellular automata as convolutional neural networks. arXiv:1809.02942 [cond-mat, physics:nlin, physics:physics] (2018).
5. Yilmaz, O. Reservoir Computing using Cellular Automata. arXiv:1410.0162 [cs] (2014).
6. Nichele, S. & Molund, A. Deep Reservoir Computing Using Cellular Automata. arXiv:1703.02806 [cs] (2017).
7. Cisneros, H., Mikolov, T. & Sivic, J. Benchmarking Learning Efficiency in Deep Reservoir Computing. in Proceedings of The 1st Conference on Lifelong Learning Agents 532–547 (PMLR, 2022).
8. Glover, T. E., Lind, P., Yazidi, A., Osipov, E. & Nichele, S. The Dynamical Landscape of Reservoir Computing with Elementary Cellular Automata. in ALIFE 2021: The 2021 Conference on Artificial Life (MIT Press, 2021).

Answer 2

I am very much interested in this and will start my research on this at Ghent University soon. I'm preparing results about this approach and some preliminary results for pattern recognition in elementary cellular automaton using convolutional neural networks. I couldn't find much on this, but see e.g. this (very limited) paper.

Please keep me posted via my ResearchGate page if you make any progress :)

Answer 3

I'm afraid that the application is so obscure that this has not been done due to lack of interests. As a supervised learning classification problem it seems a fairly easy one, I bet you should be able to build a computer vision classifier with high accuracy in an afternoon, by finetuning a pretrained convolutional neural network on a small dataset of examples. The latter are easy to generate programmatically.

Perhaps a non trivial example of ML + cellular automata is this work on Growing Neural Cellular Automata, showing how self-organising patterns can emerge from simple rules and be able to rigenerate lost limbs or entire body parts.