High-dimensional Cellular Automata for Neural Network represenation

The NKS Summer School 2009 project

Zdenek Buk

Department of Computer Science and Engineering
Faculty of Electrical Engineering
Czech Technical University in Prague

zdenek.buk@fel.cvut.cz ,  http://cig.felk.cvut.cz

Abstract

In this work the behavior of the four-dimensional cellular automata and their possible usage for the neural network representation have been studied. In this presentation several methods of visualization of the 4D cellular automata evolution are shown and the simple experiment how to extract the neural network topology and weight settings from the CA configuration is described. The neural network has been tested on the time-delayed XOR problem.

Introduction

Neural networks are nature inspired computational structures able to learn and adapt to given problem. Many training algorithms exist, some of them are able to train the weights of inter-neuron connections, some of them are able to construct the whole topology of the network and also the type of activation functions used in the neurons. The image on the right shows one simple recurrent neural network with three neurons, one external input and threshold.

Usually we are using the gradient based methods of learning, genetic algorithms — or evolutionary algorithms in general —or combinations of this methods (hybrid learning).

({{, }})

A common problem when evolutionary algorithms are used is the representation (encoding) of the solution (neural network) in the genome. The representation should be general, but not so complicated with respect to the crossover operations.

Representation of NN by CA

The basic idea of “Hyper encoding” is to use high-dimensional space to encode the structure of the network. We are not using the adjacency matrix directly, but we are using  the spatial representation of the network –  the positions of the particular neuron in space.

For 1D networks, we need a 2D space for representation of such network.

4D Cellular Automata

Visualization of 4D CA

Visualization of the first 128 (of the whole set of 1024) totalistic binary 4D CA, for 10 steps of evolution from simple initial conditions.  Repetitive classes of behavior can be seen.

Experiments

I have reduced the experiments with the 4D CA behavior to binary totalistic CA with the von Neuman neighborhood (1024 rules).

The visualizations in this work use the reduction of space — the whole 4D space is flattened and shown in time, so the images look similar to 1D automata visualizations. For behavior analysis the Fourier DCT was calculated for each cell, the frequency spectra is shown in the right part of the following images.

All rules have been tested for neural network generation — the goal for the network was to solve the so called Time-Delayed XOR problem. The network has one single input and is trained to response like this:

y(t)=x(t-d)XORx(t-d+1)

where y(t) is the output and x(t) is the binary input at time t. d is the time delay.

Symmetric initial conditions have been used in final experiments with neural networks – the hypercube 2x2x2x2 is transformed into a symmetric configuration 3x3x3x3 and is used as the initial condition. This gives us 65 536 possible initial conditions and there are 1024 rules, so finally 67 108 864 configurations (if the number of time steps for CA evolution is constant).

initialConditions[2,1]

Manipulate[Grid[Map[ArrayPlot[#,ImageSize->80/((s+1)/2)]&,initialConditions[i,s],{2}]],{{i,1,"Init"},0,2^16-1,1},{{s,1,"Size"},{1,2}},FrameLabel->"Symetric initial condition"]

The following image shows the example of the evolution of one 4D CA (four dimensional space is flatten into 2D), the averaging is used for real values representations.

The corresponding neural network is shown here:

Conclusion

Total amount of 67 108 864 (1024×(2^(2^4))) configurations have been tested on very small testing paterns in Time-Delayed XOR experiments to find possibly interesting ones. There are now running experiments for testing these interesting configurations on longer patterns to find the best solution. This search process is now done by brute-force — testing all possible configurations — the next step is to apply some kind of evolutionary optimization to find the solution. For larger instances (longer evolution of CA, bigger CA mesh, bigger network, etc.) the brute-firce is of course not possible to use.

As a side-effect the package for working with 4D CA's and their visualizations has been created.

The promising configurations are now studied in detail.

Technical details

Visualizations in the early stages of the project have been calculated on ALTIX 3700 supercomputer, the experiments with particular configurations of CAs have been done on one Core2Quad 2.4GHz and later two more Core2Quad 2.4GHz have been added into the configuration.

The results of the experiments have been exported into the MySQL server (storing now more than 67 milions of CAs/experiments configurations). Promising configurations are now extracted from the the SQL server an the experiments with these configurations are running in more precise way (longer evolution time, larger testing series, etc.).

Acknowledgments

Parts of the project have been calculated using the ALTIX 3700 supercomputer at the Supercomputing Centre of Czech Technical University in Prague.

Initialization Code

initialConditions[num_Integer,nbrSize_Integer:1]:=Module[
{binary,init},
binary=IntegerDigits[num,2,((*nbrSize*)1+1)^4];
init=Nest[Partition[#,((*nbrSize*)1+1)]&,binary,3];
ArrayPad[First@Map[Drop[#,1]&,{ArrayPad[init,1,"Reflected"]},4],nbrSize-1]
];