Reproducing "Connectionist-Symbolic Machine Intelligence using Cellular Automata based Reservoir-Hyperdimensional Computing" ←

by Ozgur Yilmaz, arxiv.org/abs/1503.00851

So, maybe i miss-read something but one experiment is supposed to input a few binary values then run it few hundred iterations and feed a batch of the last CA states to a ridge linear readout to recover the inputs. It's supposed to show that the CA can hold values over a longer period and is therefore suitable as a computing reservoir.

Initially i thought it interesting but then i realized that a lot of CA rules would satisfy this without much computing going on. Imagine a rule that simply copies the alive cell in the middle and all input bits are placed with a little distance to each other. Then the readout actually get's the unmodified input as source to recover the input, which isn't a proof of anything.

So i probably misunderstood something. Anyways, i ran the following setup to test the idea a bit:

The dataset consist of the 9-bit binary representations of numbers 0 - 511. 100 samples are randomly selected and moved to the validation set.

A single fixed random mapping of the input values to the CA state space is used to spread the values across a 200 cell wide input state such that no input is closer than 5 cells to another input. The edges of the state are toroid, e.g. they wrap around. Initial state is zero, except the input bits.

All 256 possible rules in the classic wolfram binary-state 3-neighbourhood CA are run for 500 iterations and the last 200 iterations are fed to the sklearn.linear_model.Ridge readout. The training-set is used to train the readout.

When simply querying for the reproduction of the input values, in fact 169 rules have zero training error and 145 even generalize to have zero validation error. (csv)

5-bit xor ←

Next the readout was trained to produce the xor of the first and last 5 bits of a 10-bit number. These sets have 924 and 100 samples for train and test.

Here are the top-50 rules:

(mae is mean absolute error, csv)

Note that Steven Wolfram's favorite rule 30 is not able to generalize to the validation data. Only 6 rules generalize completely and 23 have zero training error.

8-bit square ←

Here, the 9-bit numbers are used again and the target values are 8-bit binary representations of the result of (n * n) mod 251. Only 50 samples are moved to the validation set so the training set has size 462. Can the CA reservoir generalize to calculate the square of a number?

(csv)

It seems, no. The top-most number of correct validation results is 2 among all 256 rules. Again, 23 rules have zero training error. At least.

The well-performing rules are identical in both experiments:

 18,  22,  30,  45,  60,  75,  86,  89, 101, 102, 105, 124, 
126, 129, 135, 146, 149, 150, 153, 161, 182, 193, 195

Shown as binary representation, which are the lookup values for the 3-neighbourhood (* marks rules that generalized perfectly in the xor experiment):

 18: [0, 1, 0, 0, 1, 0, 0, 0]
 22: [0, 1, 1, 0, 1, 0, 0, 0]
 30: [0, 1, 1, 1, 1, 0, 0, 0]
 45: [1, 0, 1, 1, 0, 1, 0, 0]
 60: [0, 0, 1, 1, 1, 1, 0, 0] *
 75: [1, 1, 0, 1, 0, 0, 1, 0]
 86: [0, 1, 1, 0, 1, 0, 1, 0]
 89: [1, 0, 0, 1, 1, 0, 1, 0]
101: [1, 0, 1, 0, 0, 1, 1, 0]
102: [0, 1, 1, 0, 0, 1, 1, 0] *
105: [1, 0, 0, 1, 0, 1, 1, 0] *
124: [0, 0, 1, 1, 1, 1, 1, 0]
126: [0, 1, 1, 1, 1, 1, 1, 0]
129: [1, 0, 0, 0, 0, 0, 0, 1]
135: [1, 1, 1, 0, 0, 0, 0, 1]
146: [0, 1, 0, 0, 1, 0, 0, 1]
149: [1, 0, 1, 0, 1, 0, 0, 1]
150: [0, 1, 1, 0, 1, 0, 0, 1] *
153: [1, 0, 0, 1, 1, 0, 0, 1] *
161: [1, 0, 0, 0, 0, 1, 0, 1]
182: [0, 1, 1, 0, 1, 1, 0, 1]
193: [1, 0, 0, 0, 0, 0, 1, 1]
195: [1, 1, 0, 0, 0, 0, 1, 1] *

the bits correspond to these neighbourhood states:

000 100 010 110 001 101 011 111

Below are plots of the state history (100 iterations, toroid 101-cell state) for these particular rules, starting from a single seed cell:

more tests ←

Tried a couple of things :rofl:

Among them is feeding the input data sequentially to the CA state. For the following table, the input sequence is placed in the first state slice as above, then every seq_input_stride steps the input is inserted again to the running CA state. Either a copy of the first input slice or sequentially: every input bit one after another, at their respective fixed random positions.

Training objective was to reproduce the binary float representation of the input number (0 to 511). Only tried the 23 strong rules from above and iterations and output_steps where fixed after preliminary tests.

(readout_var is the variance of the linear readout matrix)

It can generalize to a high degree in this task. Although all the sequential-input-or-not and even the different rules do not change the numbers too much. For the square of number experiment above this setup still does not get better than 6 correct validation samples out of 100.

Mhh, so what about higher order CAs? If we allow 3 states instead of 2, the 1D replacement CA suddenly has astonishing 3^3^3, or 3^27 possible rules. A do-nothing python loop through that number already takes 300 hours:

for r in tqdm(range(7_625_597_484_987)):
    pass

0%|                  | 567,067,242/7,625,597,484,987 [01:24<314:10:54, 6,741,520.98it/s]