Source-linked AI summary
Cellular automata as convolutional neural networks
William Gilpin
TL;DR
The paper asks how the structure of a dynamical process affects the way neural networks represent it, and studies this question with cellular automata. It develops convolutional networks that learn CA rules and finds that rule entropy is associated with the depth and structure of their learned representations.
Problem
Although neural networks have learned predictive representations of diverse dynamical systems, how a process’s underlying structure affects its learned representation remains an open question.
Source: §I · p. 1Method
Results
Simpler, lower-entropy CA tend to produce deeper, hierarchical representations, while higher-entropy CA tend to produce shallower representations.
Source: §IV · p. 4, §V · p. 6Takeaways & Limitations
The learned network structure reflects features of CA rule tables, including their relative entropy.
Source: §VI · p. 8
Abstract
from arXiv · showhide
Deep learning techniques have recently demonstrated broad success in predicting complex dynamical systems ranging from turbulence to human speech, motivating broader questions about how neural networks encode and represent dynamical rules. We explore this problem in the context of cellular automata (CA), simple dynamical systems that are intrinsically discrete and thus difficult to analyze using standard tools from dynamical systems theory. We show that any CA may readily be represented using a convolutional neural network with a network-in-network architecture. This motivates our development of a general convolutional multilayer perceptron architecture, which we find can learn the dynamical rules for arbitrary CA when given videos of the CA as training data. In the limit of large network widths, we find that training dynamics are nearly identical across replicates, and that common patterns emerge in the structure of networks trained on different CA rulesets. We train ensembles of networks on randomly-sampled CA, and we probe how the trained networks internally represent the CA rules using an information-theoretic technique based on distributions of layer activation patterns. We find that CA with simpler rule tables produce trained networks with hierarchical structure and layer specialization, while more complex CA produce shallower representations---illustrating how the underlying complexity of the CA's rules influences the specificity of these internal representations. Our results suggest how the entropy of a physical process can affect its representation when learned by neural networks.
I. INTRODUCTION
Neural networks have learned predictive representations of many dynamical systems, but how a process’s structure affects its learned representation remains an open question. The paper studies this question using cellular automata, showing that convolutional networks can represent and learn arbitrary CA rules and that representation depth depends on rule entropy.
I. INTRODUCTION
- The open question is how the underlying structure of a physical process affects its representation in a neural network trained with standard optimization.Prior work had demonstrated predictive representations across dynamical systems and generative tasks.Source: §I · p. 1
- Cellular automata offer a discrete setting for studying this question, with simple local rules that can produce complex behavior.Conway’s Game of Life, for example, exhibits self-replication and Turing universality.Source: §I · p. 1
- The paper shows that convolutional neural networks can represent arbitrary cellular automata and learn their rules using standard gradient-based training.In large networks, trained representations share sparse patterns, while their effective depth depends on the entropy of the underlying rules.Source: §I · p. 1
II. EQUIVALENCE BETWEEN CELLULAR AUTOMATA AND CONVOLUTIONAL NEURAL NETWORKS
A cellular automaton updates each cell from a finite local neighborhood, while a convolutional network applies the same local operation across image locations. This shared locality and synchronous updating let a CNN represent CA rules as neighborhood feature extraction followed by an output mapping.
II. EQUIVALENCE BETWEEN CELLULAR AUTOMATA AND CONVOLUTIONAL NEURAL NETWORKS
- A CA maps each possible neighborhood input σ to an output state, and locality bounds the size of the rule domain.For the Game of Life, the 3 × 3 neighborhood yields 512 possible 9-bit inputs.Source: §II · pp. 1–2
- A CNN applies shared trainable kernels locally across an image and preserves its spatial dimensions without pooling in the architectures studied.Each convolution consolidates information within a fixed local radius.Source: §II · p. 2
- Because CA updates are local and synchronous, a neural network can approximate each neighborhood rule and apply it convolutionally to all image locations.The paper builds on neural networks’ capacity as universal function approximators.Source: §II · p. 2
- Representing a CA requires extracting neighborhood cases and mapping each case to an output; one analytical construction uses a 3 × 3 convolution followed by 1 × 1 layers.The neighborhood-matching and tree-search constructions provide alternative ways to implement the rule table.Source: §II · p. 2
- In the Game of Life example, an initial convolution extracts the center-cell state and neighbor count, then 1 × 1 layers generate the prediction.With ReLU activations, the illustrated representation uses four neighbor filters with different biases and one identity filter.Source: §II · p. 2
III. A GENERAL NETWORK ARCHITECTURE FOR LEARNING ARBITRARY CELLULAR AUTOMATA
The authors train convolutional mlpconv networks on CA examples and find successful convergence across the rulesets studied. Training progresses from adjusting activation scales to selectively encoding rules, while large networks show repeatable dynamics and near-matched train and test performance.
III. A GENERAL NETWORK ARCHITECTURE FOR LEARNING ARBITRARY CELLULAR AUTOMATA
- Training examples map all 512 binary 3 × 3 neighborhoods to output pixels, using 10 × 10 images and batches of 500 to include every rule input.Presenting all input cases together avoids dependence of network structure on the order in which individual rules are shown.Source: §III · pp. 2–3
- The training architecture uses one 3 × 3 convolution followed by a variable number of 1 × 1 convolutions, with no pooling.All layer parameters are trained together; the final hidden layer sums weighted activations to predict the next lattice-site value.Source: §III · p. 3
- Training uses Adam with an L2 loss, validation-based stopping, and a separate unseen test set; validation rulesets are also held out during hyperparameter tuning.Training stops when rounded predictions reach 100% accuracy on a secondary validation set from the same ruleset.Source: §III · p. 3
- Training converged for every CA ruleset studied, and rounded predictions reached 100% accuracy on the stopping-validation set.Unseen test accuracy was within approximately 0.3% of training accuracy, but this reflects learning the finite input table, not generalizability.Source: §III · p. 3
- In large networks, training is highly repeatable across initializations, training data, CA rules, and modest hyperparameter changes.Doubling depth and width or changing the optimizer and loss produced nearly identical internal structure, though some alternatives changed loss-curve shape or training duration.Source: §III · pp. 3–4
- During Game of Life training, activations progress from random patterns to scale adjustment, then to clusters of related rules and fewer spurious activations.The example network is applied to the glider pattern.Source: §III · p. 4
IV. ANALYSIS OF TRAINED NETWORKS
Across randomly sampled binary CA, rule entropy is associated with differences in training dynamics and the depth of learned representations. Simpler rules produce deeper, tree-like structure, while higher-entropy rules tend toward shallower representations; these patterns are more consistent in large than narrow networks.
IV. ANALYSIS OF TRAINED NETWORKS
- The study samples 2,560 CA across rule-entropy values using five replicated table walks through the binary rule space.Each walk starts from the null rule and switches input symbols to output 1 one at a time.Source: §IV · p. 4
- Simpler CA produce deeper, more tree-like representations, whereas higher-entropy rules tend to produce shallower networks with less-compressible rule tables.The entropy–layer-entropy correlation is present across layers and becomes more prominent deeper in the network.Source: §IV · p. 4
- After a shared initial training transient, simpler CA learn faster and reach shallower rule-table representations with smaller final loss values.Rule entropy affects this training phase because it determines rule-table sparsity and compressibility.Source: §IV · p. 4
- Large networks show universal training curves and activation patterns, but narrow networks exhibit plateaus and may fail to learn every rule.Narrow networks that do terminate show no apparent internal patterns, consistent with random search; larger networks reduce kinetic trapping near shallow minima or saddle points.Source: §IV · pp. 4–5
V. INFORMATION-THEORETIC QUANTIFICATION OF ACTIVATIONS.
The paper uses information-theoretic measures of binary activation patterns to examine how trained networks represent CA rules. Higher-entropy rules tend to yield shallower representations, while simpler rules show more hierarchical structure and layer specialization.
V. INFORMATION-THEORETIC QUANTIFICATION OF ACTIVATIONS.
- Activation entropy is calculated from binary patterns across inputs; Shannon entropy discounts dead neurons, and binarization preserved distinctions between tested inputs.Neurons are marked active when their output is nonzero, and the analysis uses an equiprobable ensemble of input cases.Source: §V · p. 5
- Across trained networks, total activation entropy is approximately 9, even for trivial rules; weight-cost regularization and dropout reduce it.The authors attribute this to early layers retaining unique activation patterns for each input after gradient-based training.Source: §V · p. 6
- Early layers tend to retain broad activation-pattern distributions, while later layers show fewer, less uniformly distributed patterns; theoretical curves contrast pattern matching with layerwise elimination of input cases.The figure compares layerwise entropy with predictions for implementations that eliminate 0%, 45%, or 50% of cases per layer.Source: §V · p. 6
- Higher-entropy CA rules tend to produce shallower networks, whereas simpler rules produce more binary tree-like structure, with the entropy relationship more prominent in deeper layers.The authors relate this pattern to the lower intrinsic compressibility of higher-entropy rule tables.Source: §V · pp. 6–7, Figure 4 · p. 7
- Activation-pattern distributions become progressively narrower and more peaked across layers, especially for networks trained on lower-entropy CA.The passage describes this trend using Zipf plots of activation-pattern frequency against rank.Source: §V · p. 7
- Layerwise entropy increases linearly with total neuron entropy before saturating near total input entropy; higher-entropy CA occupy the saturated regime, while lower-entropy CA remain in the linear regime.The authors state that CA with larger input spaces would require more neurons per layer to reach the large-network limit.Source: §V · p. 7
- In later layers, neurons are associated with features shared across multiple inputs, such as specific neighbor states; the degree of this specialization varies with CA entropy.The authors assess specialization using total correlation between neurons’ activation patterns and the layer pattern.Source: §V · p. 7
VI. DISCUSSION
The discussion presents a CNN architecture for learning arbitrary binary cellular automata and describes how trained networks encode rule-table entropy. It identifies open questions about relating CA rules to apparent dynamical complexity and extending the analysis to broader prediction tasks.
VI. DISCUSSION
- A single 3 × 3 convolution followed by repeated 1 × 1 convolutions can consolidate neighborhood structure and perform local operations, supporting mixtures of shallow pattern matching and deep layerwise tree searching.The authors describe the architecture as capable of learning arbitrary binary CA using standard techniques.Source: §VI · pp. 7–8
- The authors report that trained networks structurally encode relative rule-table entropy, and propose future work on whether process complexity appears as structural motifs in learned representations.They identify open-ended dynamical prediction, including video prediction, as a possible setting for further study.Source: §VI · p. 8
VIII. CODE AVAILABILITY
The paper reports its implementation environment and source-code availability.
VIII. CODE AVAILABILITY
- The CNNs were implemented in Python 3.4 using TensorFlow 1.8, and source code is available in the convoca repository.Source: §VIII · p. 8
A. Representing arbitrary CA with convolutional neural networks
A ReLU mlpconv network can represent any finite-state cellular automaton with finite depth and neuron count. The section illustrates shallow rule-table matching by encoding states and detecting input patterns.
A. Representing arbitrary CA with convolutional neural networks
- A ReLU mlpconv architecture can represent any M-state cellular automaton with finite depth and neuron count.The analytic constructions illustrate possible implementations, not necessarily the representations learned by optimized networks.Source: A. Representing arbitrary CA with… · p. 8
1. Pattern-matching the rule table with a shallow network
- For an L × L input, 1 × 1 convolutions and ReLU produce an L × L × M binary activation stack encoding the states.The conversion is unnecessary for binary cellular automata and uses two layers.Source: §1 · p. 8
- The shallow construction matches each of the M^D possible inputs with filters and rule-table biases, activating exact matches for nonzero outputs.The passage describes this as an upper bound; known quiescent-rule structure can reduce the number of patterns matched.Source: §1 · pp. 8–9
2. Searching the rule table with a deep network
A deep network can represent a cellular automaton by progressively merging inputs that share an output. The section also shows how Game of Life rules can be implemented using center-state and neighbor-count features.
2. Searching the rule table with a deep network
- A deep construction assigns input cases unique activation patterns, then merges cases with the same output symbol before the final layer.For binary Moore-neighborhood rules, a search can reduce 512 cases to two patterns in at most eight layers when λ = 0.5.Source: §2 · p. 9
- Splitting a neighborhood into sub-neighborhoods and matching each yields an n-hot encoding that uniquely represents each input case.For a binary Moore neighborhood, the example uses two sub-neighborhoods to construct a two-hot encoding.Source: §2 · p. 9
- Shallow full-pattern matching can be efficient, while layer-wise search may be preferable when the state count or neighborhood size is large.Other implementations can check separate neighborhood features first and combine them in later layers.Source: §3 · p. 10
3. Network representation of the Game of Life
- Game of Life can be implemented from the center state and neighbor count, with four biased copies of a ReLU neighbor-count filter distinguishing the required counts.The construction uses an identity filter plus neighbor-count filters, then 1 × 1 convolutions to produce the next-state output.Source: §3 · p. 10
- The same architecture applies to outer-totalistic rules with adjusted neighbor filters, while a purely totalistic rule needs only one neighbor-count filter.In Game of Life, cases with zero or one living neighbor need not be distinguished when both yield a dead center cell next.Source: §3 · p. 10
B. Neural network training details
The training setup uses separate unseen data for hyperparameter selection, stopping, and final testing. The reported accuracy and robustness checks show that results persist across larger networks and an alternative optimizer and loss.
B. Neural network training details
- Hyperparameter tuning used fresh validation images associated with unseen rulesets, and separate validation and test images were generated for each ruleset.The second validation set determined when to stop training; the test partition measured final accuracy.Source: B. Neural network training details · pp. 10–11
- After rounding network outputs to the nearest integer, training and test datasets both achieved 100% accuracy.Before rounding, training and test accuracies were within 0.3%; the authors attribute this to exact representation of all input cases.Source: B. Neural network training details · p. 11
- Doubling network depth and width left the reported results almost identical, which the authors attribute to only 512 unique input cases.The comparison used the same loss, hyperparameters, and optimizer as the main network.Source: B. Neural network training details · p. 11
- Changing the loss function and optimizer produced results nearly identical to those of the default network.The alternative setup retained 12 layers with 100 neurons each, with optimal hyperparameters found through a new grid search.Source: B. Neural network training details · p. 11
- The alternative network had a longer universal training transient, but later training and the Hca dependence of internal representations matched the default network's patterns.Hca also strongly affected the later training stages and final loss.Source: B. Neural network training details · p. 11
X. SUPPLEMENTARY MATERIALS AND ADDITIONAL EXPERIMENTS
The supplementary material is available as an ancillary file through the arXiv abstract page. The instructions direct readers to download it from the source formats menu.
X. SUPPLEMENTARY MATERIALS AND ADDITIONAL EXPERIMENTS
- The supplementary material is uploaded as an ancillary file for the arXiv submission.Source: §X · p. 11
- From the abstract landing page, open “Other formats” under the “Download” header.Source: §X · p. 11
- Under “Source,” select “Download source” to obtain the numbered file containing the supplementary material.Source: §X · p. 12