In this paper, we introduce a framework of reservoir computing that is capable of both connectionist machine intelligence and symbolic computation. Cellular automaton is used as the reservoir of dynamical systems. A cellular automaton is a very sparsely connected network with logical nodes and nonlinear/logical connection functions, hence the proposed system corresponds to a binary valued and nonlinear neuro-symbolic architecture. Input is randomly projected onto the initial conditions of automaton cells and nonlinear computation is performed on the input via application of a rule in the automaton for a period of time. The evolution of the automaton creates a space-time volume of the automaton state space, and it is used as the reservoir. In addition to being used as the feature representation for pattern recognition, binary reservoir vectors can be combined using Boolean operations as in hyperdimensional computing, paving a direct way symbolic processing. To demonstrate the capability of the proposed system, we make analogies directly on image data by asking 'What is the Automobile of Air'?, and make logical inference using rules by asking 'Which object is the largest?' Web: ozguryilmazresearch.net 1The literature review is narrowed down in this paper due to space considerations. Please visit our published papers to get a wider view of our architecture among existing reservoir and hyperdimensional computing approaches.
We have introduced a holistic intelligence framework capable of simultaneous pattern recognition Yilmaz (2015b) and symbolic computation Yilmaz (2015a,c). Cellular automaton is the main computational block that holds a distributed representation of high order input attribute statistics as in neural architectures (Figure 1 b). The proposed architecture is a cross fertilization of cellular automata, reservoir computing and hyperdimensional computing frameworks (Figure 1 a). The cellular automata (CA) computation can be viewed as a feedforward network with logical nodes and connections, as shown in Figure 1 c. In this paper, we analyze the symbolic computation capability of the system on making analogies and rule based logical inferences, directly on the image data. The results show that (Figure 2), binary vector representation of images derived through CA evolution provide very precise analogies and accurate rule based inference, even though very small number of examples are provided. In the next subsection we review cellular automata 1, then introduce relevant neuro-symbolic computation studies. Finally, we state our contribution.
Input
Win
CA Rule Reservoir Computing
Hyperdimensional
Computing time Cellular Automata
Reservoir
Wout
Output
c Cellular automaton is a discrete computational model consisting of a regular grid of cells, each in one of a finite number of states (Figure 1 c). The state of an individual cell evolves in time according to a fixed rule, depending on the current state and the state of its neighbors. The information presented as the initial states of a grid of cells is processed in the state transitions of cellular automaton and computation is typically very local. Essentially, a cellular automaton is a very sparsely connected network with logical nodes and nonlinear/logical connection functions (Figure 1 c). Some of the cellular automata rules are proven to be computationally universal, capable of simulating a Turing machine (Cook, 2004).
The rules of cellular automata are classified according to their behavior: attractor, oscillating,
chaotic, and edge of chaos (Wolfram, 2002). Turing complete rules are generally associated with the
last class (rule 110, Conway game of life). Lyapunov exponent of a cellular automaton can be
computed and it is shown to be a good indicator of the computational power of the automata
Uniting the expressive power of mathematical logic and pattern recognition capability of distributed
representations (eg. neural networks) has been an open question for decades although several
successful theories have been proposed
Along the same vein,
In this paper, we borrow these tools of hyperdimensional computing framework, and build a semantically more meaningful representation by removing the randomness and replacing it with the cellular automata computation. This provides not only a more expressive symbolic computation architecture, but also enables pattern recognition capabilities otherwise not possible with random vectors. 1.3
We provide a low computational complexity method Yilmaz (2015b) for recurrent computation using cellular automata based hyperdimensional computing. It is shown that the framework has a great potential for symbolic processing such that the cellular automata feature space can directly be combined by Boolean operations as in hyperdimensional computing, hence they can represent concepts and form a hierarchy of semantic interpretations. We demonstrate this capability by making analogies directly on images and infer relationships using logical rules. In the next section, we give the details of the algorithm, and then provide results experiments that demonstrate our contributions. 2
In our reservoir computing method, data are passed on a cellular automaton instead of an echo state network and the nonlinear dynamics of cellular automaton provide the necessary projection of the input data onto an expressive and discriminative space. Compared to classical neuron-based reservoir computing, the reservoir design is trivial: cellular automaton rule selection. Utilization of edge of chaos automaton rules ensures Turing-complete computation in the reservoir, which is not guaranteed in classical reservoir computing approaches.
The reservoir computing system receives the input data. First, the encoding stage translates the input into the initial states of a 1D elementary cellular automaton. For binary input data, each feature dimension can randomly be mapped onto the cells of the cellular automaton. For this type of mapping, the size of the CA should follow the input data’s feature dimension. After encoding, suppose that the cellular automaton is initialized with the vector A0P1 , in which P1 corresponds to a random permutation of raw input data. Then, cellular automata evolution is computed using a prespecified rule, Z (1D elementary CA rule), for a fixed period of iterations (I): A1P1 = Z(A0P1 ); A2P1 = Z(A1P1 ); :::
AI P1 = Z(AI 1P1 ): The evolution of the cellular automaton is recorded such that, at each time step a snapshot of the whole states in the cellular automaton is vectorized and concatenated. Therfore, we concatenate the evolution of cellular automata to obtain a reservoir for a single permutation:
AP1 = [A0P1 ; A1P1 ; A2P1 ; :::AI P1 ] It is experimentally observed that multiple random permutation mappings significantly improve accuracy. There are R number of different random mappings, i.e., separate CA reservoirs, and they are combined into a large reservoir feature vector:
AR = [AP1 ; AP2 ; AP3 ; :::APR ]: The computation in CA takes place when cell activities due to nonzero initial values (i.e., input) mix and interact. Both prolonged evolution duration (large I ) and existence of different random mappings (large R) increase the probability of long-range interactions, hence improve computational power and enhance representation. 3
Hyperdimensional computing uses random very large-sized binary vectors to represent objects, concepts, and predicates. Then, appropriate binding and grouping operations are used to manipulate the vectors for hierarchical concept building, analogy-making, learning from a single example, etc., that are hallmarks of symbolic computation. The large size of the vector provides a vast space of random vectors, two of which are always nearly orthogonal. Yet, the code is robust against a distortion in the vector due to noise or imperfection in storage because after distortion it will still stay closer to the original vector than the other random vectors.
The grouping operation is normalized vector summation, and it enables forming sets of objects/concepts. Suppose we want to group two binary vectors, V1 and V2. We compute their elementwise sums, and the resultant vector contains 0, 1 and 2 entries. We normalize the vector by accepting the 0 entries as they are, transforming 2 entries into 1. Note that, these are consistent within the two initial vectors. Then, the inconsistent entries are randomly decided: 1 entries as transformed into 0 or 1. Many vectors can be combined iteratively or in a batch to form a grouped representation of the bundle. The resultant vector is similar to all the elements of the vector due to the fact that consistent entries are untouched. The elements of the set can be recovered from the reduced representation by probing with the closest item in the memory, and consecutive subtraction. Grouping is essential for defining ’a part of’, ’contains’ relationships. + symbol will be used for normalized summation in the following arguments.
There are two binding operations: bitwise XOR (circled plus symbol, ) and permutation 2.
Binding operation maps (randomizes) the vector to a completely different space, while preserving the
distances between two vectors. As stated in
A few representative examples to demonstrate the expressive power of hyperdimensional computing: 1. We can represent pairs of objects via multiplication. OA;B = A object vectors.
2. A triplet is a relationship between two objects, defined by a predicate. This can similarly be
formed by TA;P;B = A P B. These types of triplet relationships are very successfully utilized
for information extraction in large knowledge bases
C = X
A1 + Y
A2 + Z
A3;
where A1, A2 and A3 are vectors for attributes and X , Y and Z are the values of the attributes for a
specific composite object.
4. A value of an attribute for a composite object can be substituted by multiplication. Suppose we
have assignment X A1, then we can substitute A1 with B1 by, (X A1) (A1 B1) = X B1.
It is equivalent to say that A1 and B1 are analogous. This property is essential for analogy making.
2Please see
Mxy = M1 Fyz = F1 Gxz = G1
X + M2
Y; Y + M2 X + G2
Z;
Z; Rxyz = Gxz
(Mxy + Fyz): Mab = M1 Fbc = F1
0 Gac = Rxyz
A + M2 B + M2
B;
C; (Mab + Fbc); where vector G0ac is expected to be very similar to Gac, which says ”Anna is the grandmother of Cid”. Please note that the if-then rules represented by hyperdimensional computing can only be if-and-only-if logical statements because operations used to represent the rules are symmetric. Without losing the expressive power of classical hyperdimensional computing, we are introducing cellular automata to the framework. In our approach, we use binary cellular automata reservoir vector as the representation of objects and predicates instead of random vectors to be used for symbolic computation. There are two major advantages of this approach over random binary vector generation: 1. Reservoir vector enables connectionist pattern recognition and statistical machine learning (as demonstrated in Yilmaz (2015b)) while random vectors are mainly tailored for symbolic computation. 2. The composition and modification of objects can be achieved in a semantically more meaningful way. The semantic similarity of the two data instances can be preserved in the reservoir hyperdimensional vector representation, but there is no straightforward mechanism for this in the classical hyperdimensional computing framework. 4
In order to demonstrate the power of enabled logical operation, we will use analogy making.
Analogy making is crucial for generalization of what is already learned. We tested the capability of our
symbolic system using images. The example given here follows ”What is the Dollar of Mexico?”
in
3The example is adapted from
Land = Animal
Horse + V ehicle
Automobile; Air = Animal
Bird + V ehicle
Airplane: In these two concepts, CA features of Horse and Bird images are used to bind with the Animal filler, and CA features of Automobile and Airplane images are used to bind with the Vehicle filler 4. Animal and Vehicle fields are represented by two random vectors 5, those with the same size as the CA features. Multiplication is performed by xor ( ) operation and vector summation is again identical to Snaider (2012). The products, Land and Air are also CA feature vectors, and they represent the merged concept of observed animals and vehicles in Land and Air respectively. We can ask the analogical question ”What is the Automobile of Air?”, AoA in short. The answer can simply be given by this equality (inference):
AoA = Automobile
Land
Air: AoA is a CA feature vector and expected to be very similar to Airplane concept vector. We tested the analogical accuracy using unseen Automobile test images (50 in total), computing their CA feature vectors followed by AoA inference, then finding the closest concept class vector to AoA vector (max inner product). It is expected to be the Airplane class. The result of this experiment is given in Figure 2 a 6 for various R and I combinations. The multiplication of the two defines the amount of feature expansion due to cellular automata state space. The analogy on CA features is 98 percent accurate (for both R and I equals 128), whereas if the binary hidden layer activity is used instead of CA features (corresponds to R and I equal to 1), the analogy is only 21 percent accurate. This result clearly demonstrates the benefit of CA feature expansion for symbolic computation. The devised analogy implicitly assumes that Automobile concept is already encoded in the concept of Land. What if we ask ”What is the Truck of Air?”? Even though Truck images are not used in building the Land concept, due to the similarity of Truck and Automobile concepts, we might still get good analogies. The results on this second order analogy is contrasted in Table 1. Automobile and Horse (i.e. ”What is the Horse of Air?”, the answer should be Bird.) are first order analogies and they result in comparably superior performance as expected, but second order analogy is much higher than chance level (i.e., 10 percent).
Please note that these analogies are performed strictly on the sensory data, i.e., images. Given an image, the system is able to retrieve a set of relevant images that are linked through a logical statement.
4There are 50 training images for each class. CA rule 110 is used for evolution. And mean of 20 Monte Carlo simulations is given to account for randomness in experiments 5Also 22 percent non-zero elements 6These are extended results for our previous publication Yilmaz (2015a). We were unable to test for large R and I values due to hardware limitations.
79
68
A very small number of training data is used, yet we can infer conceptual relationships between images surprisingly accurately. However, again it should be emphasized that this is only a single experiment with a very limited analogical scope, and more experiments are needed to understand the limits of the proposed architecture.
It is possible to build much more complicated concepts using hierarchies. For example, Land and
Air are types of environments and can be used as fillers in Environment field. Ontologies are helpful
to narrow down the set of required concepts for attaining a satisfactory description of the world.
Other modalities such as text data are also of great interest, (see
In order to test proposed architecture’s capability for logical inference, we define a rule and form a knowledge base on image data. Then we make an inference on the knowledge base by applying the rule. The inference may or may not be right, hence the symbolic system is not completely sound. 7 For demonstration of logical inference on our system, we define size relationships among different objects using the following rule set.
Object in image X is larger than object in image Y :
Lxy = L1
X + L2 Sxz = S1
X + S2
Y:
Z: Tz = T1
Z: Then the rule is stated as ’If object in X is larger than object in Y and smaller than object in Z, largest object is in Z’. The rule vector is computed as the manipulation of object vectors using hyperdimensional computing framework:
Rxyz = Tz (Lxy + Sxz ): Our knowledge base is again formed on the images of CIFAR 10 dataset. First, we use Truck, Automobile, and Airplane images (50 each) to compute X , Y and Z concept vectors (CA rule 110); then we obtain the rule vector Rxyz as explained above utilizing the concept vectors. In a completely different set of test image triplet, we make use of single Truck, Automobile, and Airplane images and compute their vector representation; a, b and c respectively. Knowledge base is created on the object vectors in three test images:
Lab = L1 Sac = F1 a + L2 a + M2 b; c; as ’object in image a is larger than object in image b, and object in image a is smaller than object in image c’. Can we infer the largest object? When we apply the rule vector on existing knowledge base, we get an estimate for the vector representation of the largest object:
Test = Rxyz (Lab + Sac): We compute the Hamming distance of Test to existing object vectors (i.e. a, b and c), then it is possible to decide on the estimated largest object, i.e. closest vector to Test which should be vector 7The completeness of the system requires a proof and it is a future work. c. The average accuracy of 50 different test image triplets are shown in Figure 2 b. The chance level is 33 percent and it is observed that the binary neural representation (i.e., both R and I is equal to 1) is around 50 percent accurate, whereas cellular automata state space provides a 100 percent inference accuracy for a relatively small reservoir size. Please note that, similar to analogy making experiments logical inference is performed directly on image data and we can make object size inference using a very small number of example images (50). 6
Along with the pattern recognition capabilities of cellular automata based reservoir computing
Yilmaz (2015b), hyperdimensional computing framework enables symbolic processing. Due to the
binary categorical indicator nature of the representation, the rules that make up the knowledge base
and feature representation of the data that make up the statistical model live on the same space,
which is essential for combining connectionist and symbolic capabilities. It is possible to make
analogies, form hierarchies of concepts, and apply logical rules on the reservoir feature vectors 8.
To illustrate the logical query, we have shown the capability of the system to make analogies on
image data. We asked the question ”What is the Automobile of Air?” after building Land and Air
concepts based on the images of Horse, Automobile (Land), Bird and Airplane (Air). The correct
answer is Airplane and the system infers this relationship with 98 percent accuracy, with only 50
training images per class. Additionally we have tested the performance of our architecture on rule
based logical inference on images. We defined an object size related rule on image data, provided a
knowledge base and inferred the largest object strictly using the image features.
Neural network data embeddings (eg.
This research is supported by The Scientific and Technological Research Council of Turkey (TUBI˙TAK) Career Grant, No: 114E554. Snaider, J. (2012). Integer sparse distributed memory and modular composite representation, . Wolfram, S. (2002). A new kind of science volume 5. Wolfram media Champaign.