Generalization over different cellular automata rules learned by a deep feed-forward neural network by Aach, M., Goebbert, J. H., & Jitsev, J. (2021)

source
(Aach, Goebbert, and Jitsev 2021)
tags
Cellular automata, Neural networks

Summary

This paper studies the generalization abilities of neural networks on tasks involving learning the dynamics of cellular automata rules from examples.

Neural networks are trained to predict the next state of a CA from the three previous timesteps. Different training examples for a single rule corresponds to different initialization.

The authors study three kinds of generalization:

  • Simple generalization: The network is trained on 300 different CA rules and tested on more unseen initial configurations from those 300 rules.
  • Level 1 generalization: Same setup as above but the rules have variable sized neighborhoods
  • Level 2 generalization: The network is trained on 300 rules with different neighborhoods sizes and tested on new initial configurations and 30 new rules.
  • Level 3 generalization: This level has two setups
    • Interpolation: train on rules with neighborhoods \(3\times 3\), \(5 \times 5\) and \(9 \times 9\) and evaluate on rules with neighborhood \(7 \times 7\)
    • Extrapolation: train on rules with neighborhoods \(3\times 3\), \(5 \times 5\) and \(7 \times 7\) and evaluate on rules with neighborhood \(9 \times 9\)

The neural network used is an encoder-decoder architecture, with convolutions and down-sampling to convert input states into a low dimensional vector and convolutions + up-sampling to convert it back to the next predicted state.

For training and validation, all configurations above reach more than 90% accuracy. For the simple and level 1 generalizations (same CA rules), the test accuracy is also very high (> 90%). The test accuracy drops significantly for Level 2 and 3, where the network probably has trouble inferring the rule from the 4 previous steps only, whereas before it could have memorized those rules during training.

Bibliography

  1. . . "Generalization over Different Cellular Automata Rules Learned by a Deep Feed-Forward Neural Network". arXiv:2103.14886 [Nlin], March.

← Back to Notes