Cellular Automaton
Cellular Automaton (CA) is a discret time model used in many areas and also know for heavily discussed by Stephan Wolfram in „A new kind of science“. They are best known for „Game of life“. Such a model consists of a regular grid which changes by each discret timestep. The changes are defined by a set of rules which change the state of each cell. Each rules takes the surrounding states of the cells into account. Here an example:
(souce: wikipedia)
So let’s define the model:
We have a set of cells and each cell has neighour cells. To generalize the above mentioned grid we use a graph \(G\) which is a grid graph with edges \(E\) and nodes/vertices \(V\). Further we have a set of k states \(\sigma \in \Sigma\) and \(|\Sigma| = k\) each node \(v \in V\) has such an initial state \(i : V \rightarrow I \subseteq \Sigma\) (at this point the definition is kind of a „relaxed“ graph coloring). Further the system changes it’s state by each discret timetemp \(t\). So we have a transition function \(\phi : \Sigma^n \rightarrow \Sigma\) which changes the state of a vertex \(v \in V\) based on the neighbour nodes‘ states given to \(\phi\) via an n-tuple. \(\phi_{t_i}\) determines the state at timestep \(t_i\). Further for the timestep \(t_0\) we have the initial states via \(i()\). For each further timestep \(t_i\) the states of all vertices is calculated via \(\phi()\) synchronously and takes the states from the timestep \(t_{i-1}\)
When running such a CA it can: 1) reach a fixed state which does not change anymore, hence it is deterministic: \(\phi_{t_{i-1}} = \phi_{t_i}\) 2) reach a state beginning from that timestep \(t_{i-d}\) the state will cyclic, repeatly occure s.t. \(\exists v \in V: \phi(v)_{t_{i-d}} = \phi(v)_{t_i} = \phi(v)_{t_{i+d}}\). In that cycle this equation holds for every timestep for the specific \(v\). Since there can be many v but the cycle size \(d\) is different it is not possible to define a termination criteria based on the states. It is hence necessary to define an abortion criteria.
The first problem: Termination
To reach an abortion cirteria we define one further parameter. First \(l : \mathbb{N} \rightarrow \mathbb{N}\) which takes the timestep \(t_i\) as parameter and gives the number of cells which are „live“ (e.g. which has to be taken into account and are „not dead cells“).
\(\frac{(l(t) – l(t – 1))^{2}}{|V| + t^2} < \xi\)
\(|V|\) gives the number of vertices in the grid graph \(G\). To give an intuition of this formular (it very easy I think). The dividend first calculates the difference between two states and gives the square product of this difference. First of all this ensures that the difference is positive and second, like the mean squared error, some drastically changes in the cellular automaton has higher impact on the result. It did not check if it will give better results if we increase the potency number. Further the divisor: At the beginning \(t\) will be 1 (since we can not calculate the change in the first state \(t=0\)) and to that we add the number of vertex (cells) we have at all. This polynom which adds the overall number is necessary to keep the result of the formular „low“. Otherwise we get a strange scale. Think about the situation where we only have \(t^2\) at the divisor. It will end up at \(t=1\) with the dividend itself an maybe will give a large number. The \(t^2\) is added to ensure that the whole result of the formular is getting lower and lower for sure to reach the criteria. The \(\xi\) is now a threshold which will be defined to reach the abortion.
I already implemented this abortion criteria at the game of life. See it on github: https://github.com/mrqc/spiking-neural-networks-with-cellular-automaton. with \(\xi = 0.1\).
I will start now to put up a model of Spiking Neural Networks (SNN) which can transfer a spike train via such a CA model.
Notes: There exists a concept called CoDi, which is a cellular automaton model for spiking neural networks. My first thoughts about this was one year ago and I did not know that something like this exists. I will have a look at it.