5
$\begingroup$

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.

enter image description here

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?

$\endgroup$

3 Answers 3

4
+50
$\begingroup$

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:

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).
$\endgroup$
4
  • 1
    $\begingroup$ Thanks a lot, Hugo! Do you have an intuition if classifying cellular automata by (typical) isolated states could work (not sequences = spacetime diagrams). Spontaneously you may say, "no, won't work". But maybe it deserves a second look. $\endgroup$ Feb 18, 2023 at 11:02
  • 1
    $\begingroup$ @Hans-PeterStricker, the problem with isolated states is that you cannot tell if it is part of a constant or periodic pattern or a more complex structure that evolves over time. There might be interesting structures in a single state, but they are not that interesting if they never change. $\endgroup$
    – hugcis
    Feb 20, 2023 at 13:21
  • 1
    $\begingroup$ @Hans-PeterStricker, Also, for a general review of CA classification, see this article $\endgroup$
    – hugcis
    Feb 28, 2023 at 14:34
  • $\begingroup$ Thanks a lot for the link to this valuable paper. I knew about it but haven't read it until now. Especially footnotes [33] and [34] are very promising references. $\endgroup$ Mar 12, 2023 at 15:25
2
$\begingroup$

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 :)

$\endgroup$
2
  • $\begingroup$ Can you elaborate on the goal of the research? Is the goal to automatically identifying rules leading to complex patterns? If so, how is "complex" defined? $\endgroup$
    – Rexcirus
    Feb 16, 2023 at 15:10
  • $\begingroup$ As it’s currently written, your answer is unclear. Please edit to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers in the help center. $\endgroup$
    – Community Bot
    Feb 17, 2023 at 10:40
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for the link to growing neural cellular automata - it's fascinating. $\endgroup$ Feb 16, 2023 at 10:12

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .