NOTE: The complete notebook of this post is attached at the end.

Introduction

During the time while I worked on this project, I learned not only a great deal about cellular automaton, but machine learning algorithms in general. Before I started the mentorship program, I had the opportunity to participate in the Wolfram Mathematica Summer Camp in 2015. There I became extremely interested in Mathematica and machine learning. This was a mentorship project since the topic of cellular automaton is quite difficult to learn alone. So with the help of a mentor, I was able to learn more about cellular automaton as well as work hands on with them. Please see the attached file for all of the information. Thanks.

Background Information

Cellular Automaton

Cellular automaton are defined as mathematical models for complex natural systems containing large numbers of identical components with local interactions. Automaton consist of a lattice of sites, each with a finite set of possible values. These values, the value of each site, evolve synchronously in discrete time steps according to identical rules. Additionally, the value of each site is determined by the previous values of the neighborhood sites around it. Even though these automaton are simply defined, it has been shown that they can consist of complex behaviors.

Classes of Cellular Automaton

Stephen Wolfram proposes a class system. This system has four different classes: class I, II, III, and IV. Class I is defined to have very simple behavior, and that almost all initial conditions lead to exactly the same uniform final state of the cellular automaton. Some examples of class I cellular automata are rules 0, 32, and 160.

Class II cellular automaton show many different possible final states, but all consist of a certain set of simple internal structures that must either: (1) remain the same forever, or (2) repeat every few steps. Examples of this class are rules 4, 108, and 250.

Class III automaton have a more complex behavior. There seems to be an aspect of randomness, although triangles and other small-scale structures are seen at some levels. Examples are rules 22, 30, and 150.

Class IV involves a complex mixture of order and randomness. There are localized structures that are produced which seem fairly simple, but these structures move and interact in very complicated ways. An example of this class is rule 110.

Part 1: Understanding the Behavior of all 4 Classes

Before creating a classifier, it is necessary to determine how to distinguish the 4 classes from each other. There are stark differences between classes 1 and 2, and classes 3 and 4. This difference is a mathematical difference so a test can be run on the automaton to check and see if it is class 1 or 2, or class 3 or 4. Examples of all 4 classes are shown below.

Image[CellularAutomaton[{32,{3,1},1},RandomInteger[2,400],400]/2]

This is an example of a class 1 cellular automaton.

Image[CellularAutomaton[{4,{3,1},1},RandomInteger[2,400],400]/2]

This is an example of a class 2 cellular automaton.

Image[CellularAutomaton[{22,{3,1},1},RandomInteger[2,400],400]/2]

This is an example of a class 3 cellular automaton.

Image[CellularAutomaton[{110,{3,1},1},RandomInteger[2,400],400]/2]

This is an example of a class 4 cellular automaton.

The test created checks to see if the automaton has a set cycle where the pattern in creates repeats itself. The following code excerpt shows how the test was created.

CyclicNormalize[list_]:=Sort[Table[RotateRight[list,i],{i,Length[list]}]][[1]]
CyclicCylcingQ[list_]:=MemberQ[CyclicNormalize/@Most[list],CyclicNormalize[Last[list]]]
CyclicCylcingQ[{x_}]:=False
CyclicCylcingQ[{}]:=False

EvolutionClass[rules_,x_,t_]:=Module[{h,k=2,res=1}, 
    If[MatchQ[rules,{_,_Integer,___}],k=rules[[2]]];
    If[MatchQ[rules,{_,{_Integer,1},___}],k=rules[[2,1]]];
    Catch[Do[
       h=CellularAutomaton[rules,RandomInteger[k-1,x],t];
       If[Not[Apply[SameQ,h[[-1]]]||CyclicCylcingQ[h]],Throw[res="3 or 4"]];
       If[Not[Apply[SameQ,h[[-1]]]],res=2],{3}];res]]

However, to determine the difference between classes 3 and 4, some image processing techniques were necessary. Additionally, the use of ClassifierFunction was necessary.

Part 2: Identifying the Best Image Processing Functions to Build a Classifier

Creating test images from all 3 color totalistic cellular automaton

As a base case for the project, all 3 color totalistic cellular automaton were used. There are a total of 2187 of them, and a few class 3 and class 4 CAs were picked out. The creation of the images is shown below along with the rules used.

classthrees={3,10,12,18,21,24,28,30,31,45,46,48,49,51,57,63,66,69,72,75,78,83,84,91,92,93,95,96,97,99,100,102,105,109,110};
classfours={15,34,65,69,88,99,133,136,148,153,157,203,228,231,248,258,262,266,294,331,379,397,458,553,593,629,797,801,805,914,963,964,966,967,997};
testimages=Image[CellularAutomaton[{#,{3,1},1},RandomInteger[2,400],400]/2]&/@Join[classthrees[[;;8]],classfours[[;;8]]];
testimages3=Image[CellularAutomaton[{#,{3,1},1},RandomInteger[2,400],400]/2]&/@Join[classthrees[[9;;]],classfours[[9;;]]];
testimages2=Image[CellularAutomaton[{#,{3,1},1},RandomInteger[2,400],400]/2]&/@Join[classthrees[[;;8]],classfours[[;;8]]];
testimages4=Image[CellularAutomaton[{#,{3,1},1},RandomInteger[2,400],400]/2]&/@Join[classthrees[[9;;]],classfours[[9;;]]];

Creating a function to classify test images with a specific filter

The function created works on the set "testimages" and is able to use any image association and its specification. Additionally, an accuracy function was created in order to measure how accurate the filter was at identifying the cellular automaton. These functions are shown below.

ClassifyWithFilter[filter_,o:OptionsPattern[]]:=Classify[<|"3"->Map[filter,testimages[[;;8]]],"4"->Map[filter,testimages[[9;;]]]|>,o]
ClassifyWithFilter[filter_,imageassociation_,o:OptionsPattern[]]:=Classify[<|"3"->Map[filter,imageassociation[["3"]]],"4"->Map[filter,imageassociation[["4"]]]|>,o]
AccuracyTest0[filter_,classifier_,o:OptionsPattern[]]:=AccuracyTest0[filter,classifier,Automatic,"Accuracy",o]
AccuracyTest0[filter_,classifier_,imageassociation_,o:OptionsPattern[]]:=AccuracyTest0[filter,classifier,imageassociation,"Accuracy",o]
AccuracyTest0[filter_,classifier_,Automatic,measurement_,o:OptionsPattern[]]:=AccuracyTest0[filter,classifier,<|"3"->testimages3[[;;35-8]],"4"->testimages3[[35-8+1;;]]  |>,measurement,o]
AccuracyTest0[filter_,classifier_,imageassociation_,measurement_,o:OptionsPattern[]]:=ClassifierMeasurements[classifier,
    <|"3"->Map[filter,imageassociation[["3"]]],"4"->Map[filter,imageassociation[["4"]]]|>,measurement,o]

Examples of how to use ClassifyWithFilter and the best Image Processing functions that were found

Rotate 45 Degrees

imageRotate45DegFilter=ImageRotate[#,45 Degree]&;
imageRotate45DegClassifier=ClassifyWithFilter[imageRotate45DegFilter];
AccuracyTest0[imageRotate45DegFilter,imageRotate45DegClassifier]

0.814815

Rain

rainFilter=ImageTransformation[#,Function[p,With[{C=150.,R=35.},{p[[1]]+(R*Cos[(p[[1]]-C)*360*2/R]/6),p[[2]]}]]]&;
rainClassifier=ClassifyWithFilter[rainFilter];
AccuracyTest0[rainFilter,rainClassifier]

0.796296

Identity

identityFilter=Identity[#]&;
identityClassifier=ClassifyWithFilter[identityFilter];
AccuracyTest0[identityFilter,identityClassifier]

0.703704

Part 3: The Errors

Throughout the whole extent of this project, there was one large error. Every time an accuracy test was run, the seed for generating the CAs changed. This made all accuracy tests unreliable. This was as far as the research was conducted due to time constraints. However, please feel free to pick up this project as it is quite promising.