Efficient Simulation of Non-uniform Cellular Automata with a Convolutional Neural Network
Michiel Rollier Aisling J. Daly Odemir M. Bruno Jan M. Baetens



Efficiently simulation of νCAs with a CNN



M. Rollier et al.

Univ. Ghent, Dept. Data Anal. & Math. Modelling, BionamiX, Coupure Links 653, B-9000 Ghent, Belgium
michiel.rollier@ugent.be
Univ. São Paulo, São Carlos Inst. Phys., POB 369, BR-13560970 São Carlos, SP, Brazil

Efficient simulation of non-uniform cellular automata with a convolutional neural network
    Michiel Rollier10000-0001-8467-734X Aisling J. Daly10000-0002-3390-2495 Odemir M. Bruno10000-0002-2945-1556 Jan M. Baetens0000-0003-4084-9992
    September 9, 2024
=================================================================================================================================================



§ ABSTRACT  
Cellular automata (CAs) and convolutional neural networks (CNNs) are closely related due to the local nature of information processing. The connection between these topics is beneficial to both related fields, for conceptual as well as practical reasons. Our contribution solidifies this connection in the case of non-uniform CAs (νCAs), simulating a global update in the architecture of the Python package . Additionally, we demonstrate how the highly optimised out-of-the-box multiprocessing in  offers interesting computational benefits, especially when simulating large numbers of νCAs with many cells.






§ INTRODUCTION




 §.§ Elementary and non-uniform cellular automata


Arguably the simplest non-trivial and maximally discrete dynamical system is an elementary cellular automaton (ECA). In this model, a finite or countably infinite number of cells are aligned in one dimension. A cell can be in only two possible states, all cells update their state in discrete time steps based on their own and their direct neighbours's state. Additionally, all cells update their states simultaneously, they do so deterministically, and they all follow the same local update rule (see e.g. <cit.>). Relaxing any of these conditions results in a CA that belongs to a family of discrete models that typically exhibit a richer behaviour, a more complex mathematical description, and well-defined `taxonomic' ties to other families. Our forthcoming comprehensive review on this taxonomy <cit.>) provides an overview.

In particular, allowing certain cells to follow different local update rules results in the family of CAs collectively identified as non-uniform CAs (νCAs). Our review paper <cit.> covers non-uniformity in the most general sense, where the `rule allocation' varies in space and time. However, in the literature <cit.> νCA rule allocation is typically only spatially non-uniform. For this reason, together with the fact that our proposed implementation is more cumbersome in the general interpretation of a νCA, we will only consider spatially non-uniform CAs in this contribution. Additionally, as we will focus on simulating νCAs, we will only be concerned with finite grids. Fig. <ref> contains an example of a νCA with N=32 cells and N_R = 2 elementary rules.



Clearly, allowing non-uniformity implies that the space of possible CA dynamics increases in size considerably. An ECA with N-cells and periodic boundary conditions already has 2^N possible initial configurations, which evolves into different dynamics for each of the 256 elementary rules. A νCA consisting of N cells that each evolve according to one of N_R rules has 2^N × N_R^N such possible initial conditions. This large diversity obstructs mathematical generalisation except in particular cases that are quite remote from applications <cit.>. An empirical approach to phenomenological classification is therefore imperative, but such a computational task requires an efficient means of simulation.



 §.§ CA classification and simulation by means of CNNs



The CA classification problem <cit.> is a challenge at the centre of CA research (see e.g. <cit.>). Considering the fact that we can interpret the spacetime diagrams of CAs as images, computer vision techniques can be mobilised for their classification, including those researched in the domain of deep learning. Within the spectrum of deep learning, convolutional neural networks (CNNs) are wildly popular, largely due to their undeniable success in image processing and computer vision <cit.>. We refer to excellent monographs to gain a good understanding of the topic (e.g. <cit.>), while a good visual introduction is offered by the deep learning series by 3Blue1Brown on YouTube <cit.>.

A lot of diverse data is required in order to effectively train CNNs to identify classes. Fortunately, the local nature of the convolution operation enables not only the identification of CAs, but also their emulation. After all, nodes in a neural network may be identified with CA cells, and a convolutional operation can be interpreted as an update from a local neighbourhood. In fact, as Gilpin <cit.> shows, the global update mechanism on any kind of CA can be accommodated by the architecture of a CNN. This can be achieved both by a clever choice of weights and biases, or by training the network from a random initialisation.

In the CNN, transforming the input configuration to the neighbourhood encoding is performed by the first 1D convolutional layer, with a kernel of width 3 and fixed weights (4, 2, 1), zero bias, and periodic boundary conditions. The output of this convolution is transformed to a matrix with one-hot vectors as columns, and each of the 8 rows of this matrix corresponds to a channel in the first CNN hidden layer. Next, another convolution layer with a kernel of width 1 essentially sums all channels, where this time the weights are determined by the binary representation of the local update rule. The output is then, by design, the ECA configuration after one global update. With a mere 40 parameters, this is an extremely simple CNN, whose computational complexity scales only with the number of cells N. The subsequent steps required to integrate a global update into a CNN framework are shown schematically in Fig. <ref>. This concrete example uses ECA rule 54 and a random initial condition, but the required operations are independent of this choice

[1]
    
    < g r a p h i c s >

    
    skip=-12pt 
    The subsequent (de)composition steps required for updating an ECA configuration, illustrated for 32 randomly initialised cells, evolved over one time step by rule 54. First, each binary size-3 neighbourhood is translated to an integer from 0 to 7 (shown in grey-scale). This integer is encoded as a size-8 one-hot vector (displayed in columns). Depending on the rule table of the local update rule (displayed on the left-hand side), this columns is kept or removed. As a final step, all columns are summed, resulting in the output configuration.
    


The parameters within the CNN (weights and biases) can be calculated, but for more general CAs they would typically be trained. In order for the CNN to be in practice (and consistently) trainable, starting from random weights and biases, some additional features are required. We will not focus on the training procedure here, but we may mention that the most important of such additional features would be activation functions <cit.>. For illustrative purposes we include our convergence towards an optimum in parameter space for a CNN that emulates rule 54 with near perfection in Fig. <ref>. For details on preferred training procedures for CA emulators, we again refer to <cit.>.





 §.§ Scope


The goal of this article is to fill in a gap in the literature, by emulating νCAs by means of CNNs. We can benefit from the extremely streamlined software implementations designed for neural networks, optimised for parallel processing and general performance. That is to say: CNNs can present us with a practical tool for the fast and massive simulation of spacetime diagrams and analyses on these diagrams.

In the next section we will develop a CNN for νCAs, and we will see that this requires only a minimal addition to the architecture outlined above. We discuss some performance characteristics, and conclude with an outlook on the future of the marriage between CAs and CNNs.



§ METHODS


In order to assess the performance of a CNN regarding the simulation of νCAs, we first discuss a popular well-established approach, and then introduce two varieties of CNN extensions.



 §.§ Existing approaches


Some programming languages enable very convenient and computationally optimised ways of simulating and analysing CAs. Wolfram Mathematica is an obvious example, which was in fact partially created for this purpose <cit.>. In Python, the most commonly used package is  <cit.>.

It is straightforward to implement a νCA in  by defining an array that instructs the  method on what rule to apply when to which cell. Adding more or fewer rules (i.e. altering the non-uniformity) should not affect the performance. What does impact the performance, however, is the fact that the non-uniformity of the model no longer allows for caching the states in each step – in  this is encapsulated in the  option (sic). This means that one cannot make any `memory shortcuts' which typically speed up the CA simulation considerably. Fig. <ref> displays an example for an 8-rule νCA simulated in .

[1]
    
    < g r a p h i c s >

    skip=15pt 
    A νCA is easily simulated using the Python package . One does so in two steps: first by defining the rule allocation (left, dependent on time and cell), and second by parsing this information to the  method, which generates the spacetime diagram (right).
    






 §.§ Two approaches for non-uniform CAs in 


Building on the CNN framework for elementary CAs, below we propose two additions which enable the CNN to emulate νCAs. Both additions involve a change in the CNN architecture between the one-hot neighbourhood encoding and the output layer. For technical details we refer to the code and annotations of the  class, available at mrollier/emulating-and-learning-CAs on GitHub, and entirely based on  modules.

Note that the proposed CNNs emulate a single global update. Generating an entire spacetime diagram of T time steps requires feeding the output of the CNN T-1 times back into the input layer, because in the proposed setup, the CNN can only emulate a single global update. Global updates strongly depend on the previous time step, so it is (in general) not possible to distribute the calculation of the CA dynamics into (for example) `all even time steps' and `all odd time steps'. This impossibility is related to the so-called computational irreducibility of CAs, and impedes temporal parallellisation of the computation of its dynamics. Note also that if the rule allocation is independent of time (as is conventionally the case for νCAs), the weights and biases of the CNN remain unchanged.



  §.§.§ A locally-connected hidden layer


The first approach includes a locally connected layer, which is essentially a convolution where the kernel weights are allowed to differ for distinct nodes. Like in Fig. <ref>, all the columns are summed, weighted by the binary representation of the local update rule, but now the weights are not shared. The biases remain zero. The rest of the CNN is identical to that for ECAs. In practice one more intermediate step is added: our model first calculates the entire output configuration as if the CA would be uniform, for each of the N_R rules. Next, the locally connected layer picks out the relevant cells based on which rule was actually allocated to it. While this is less computationally efficient, it does arguably increase interpretability of the model. More relevant in forthcoming research, however, is that this also facilitates flexibility in the training phase. After all, over-parameterisation is one of the key ingredients of deep learning.

Following the required subsequent calculations as explained in Section <ref>, this brings the total number of parameters in the model to

    (3+1) × 8 + 8 × N_R + N_R × N,

if we discard the bias parameters that have been set to zero. For the example depicted in Fig. <ref>, this sums to 352 parameters.



  §.§.§ A sparsely-populated dense layer


A slightly different approach invokes the power of a fully-connected layer, known in the industry as a dense layer. Here, again CA outputs are calculated for each of the rules, but the cell selection now occurs by means of this dense layer. Note that, essentially, a locally connected layer is a dense layer for which all edges have been cut that connect nodes that represent different cells. Whilst this seems superfluous at first, there are two reasons to do so. First,  is heavily optimised for calculating with large matrices, especially if these are sparse. Second, we again have the consideration of more model power and flexibility in future approaches that also involve training via backpropagation.

Technically, the N_R channels containing size-N outputs of the uniform case are first flattened, i.e. deconstructed into a single vector of length N_RN. Next, all elements in this vector (the node values) are connected with the size-N output layer by means of an N_RN × N weights matrix, where most weights are manually set to 0 or 1.

The total number of parameters in this model is therefore

    (3+1) × 8 + 8 × N_R + N_R × N^2,

if again we do not count the vanishing bias parameters. For the example in Fig. <ref>, this now sums to 8288 parameters.



 §.§ Comparison of the three models in four scenarios



It is counter-intuitive that any increase in computing speed is expected at all, considering the clearly large increase in required floating point operations. To be fair, a really well-optimised and parallelised approach tailored to νCA simulation will undoubtedly outperform the proposed over-parameterised CNNs. The main allure, however, is in the combination of ease of use and out-of-the-box high performance of  (or , for that matter), as a result of the global scale of its continuous development.

We will briefly examine where the strengths and weaknesses of the CNN approaches lie, compared to the benchmark approach using . In particular we will consider four scenarios: the performance when adding more rules, more time steps, more cells, and more samples. Tab. <ref> provides a summary of the parameter values (or ranges) that were found to be appropriate for best illustrating the trends and comparisons: these are the domains in which the overall trend in performance for all approaches is easily discernible. Every sample starts from a random initial condition but an identical rule allocation, such that the CNN needs to be initialised only once. Using the  Python package, we simply keep track of how many seconds each model requires for evolving the νCAs, taking the average over ten attempts.



This small-scale experiment was performed using an Intel Core i7-9850H CPU, 6 cores, at 2.6 GHz. We ran Python 3.11.8 and  2.14.0. Note, however, that the numerical value of the timing is secondary to the qualitative comparison.



§ RESULTS


Here we present the computation times of the various scenarios listed in Table <ref>. We always show the  data in blue, the data from the locally connected CNN in orange, and data from the fully connected CNN in green. In order to value the trends, we always show the mean value and the standard deviation from ten independent computations per unique combination of parameters.

Fig. <ref> displays the computation times for the all four scenario. First, we show what happens when the number of rules (the `non-uniformity') is increased by factors of two. Because the number of rules N_R goes up to 256, we also chose N=256, allowing the possibility to allocate each rule at least once. We observe that the computation time is largely independent of N_R for all models, except when a large number of rules is chosen in the densely connected CNN. Rather surprisingly, however, for small values of N_R this densely connected CNN is significantly smaller than the other two.



For the second scenario, the number of time steps increases linearly between 10 and 100, and the computation time in all models appear to increase linearly as well. Except for small T values, the computation time is similar for all three models.

The results from the third scenario are shown for eight linearly spaced values of N between 32 and 256. As expected, 's computation time is proportional to the number of cells. The locally connected CNN also increases more or less linearly – but with a higher `start-up cost'. The computation time of the densely connected CNN is largely independent of N.

For the fourth and final scenario, we consider 11 logarithmically spaced values of S between 1 and 1024. We again observe that using the larger models requires a certain initial cost, but once we want to simulate a large number of diagrams, they are clearly the least time consuming option.







§ DISCUSSION, CONCLUSION AND PROSPECTS


The highly optimised `out-of-the-box' multiprocessing of  is clearly preferred over  in scenarios where we want to generate many samples of νCAs with many cells. This of course is precisely the condition for obtaining statistically significant results in empirical studies of these discrete dynamical systems, especially when training models for automatic classification.

More surprising, however, is that the densely connected CNN almost always beats the locally connected CNN, despite the fact that mathematically speaking, the latter is a subgraph of the former. This is even the case when simulating more cells, despite, as Eq. (<ref>) shows, the quadratic growth of the number of parameters. This precisely demonstrates the point:  is so cleverly optimised, that more complex models can outperform the simpler ones. This is arguably the reason why the  layer is discontinued in more recent versions of .

CNNs are a great tool for efficient simulation, which enables a more thorough exploration of the computational landscape of CAs. Similar approaches will enable the simulation of other types of CAs. As we show in forthcoming work, for example, graph CNNs are quite straightforward to mobilise in the simulation of network automata as well. While we do not claim that  is the computationally optimal solution for CA simulation, it does present the CA researcher with an educational, ergonomic and flexible engine for efficient simulation.

CNNs are more than a tool for studying CAs, however. Arguably the most promising possibilities are created when, inversely, CAs serve the theoretical study and practical applications of CNNs. The training of CAs in the CNN framework may be used to better understand the information flow and learning process of CNNs <cit.>. Another exciting avenue is the mobilisation of CAs for generative neural networks, as was elegantly illustrated in <cit.>. In any case, increased efforts in joining discrete dynamical modelling and deep learning, such as the one shared in this work, offer interesting benefits for both research domains.






  §.§.§ 

The authors have no competing interests to declare that are
relevant to the content of this article.


splncs04


