Structure Based Permanent Associative Memory
Anatole L. Medyntsev
STRUCTURE-BASED ASSOCIATIVE MEMORY
ABSTRACT
The article describes an approach to an associative memory. In the currently used approaches the structure of links between elements is fixed (permanent) (e.g. Neural Networks (artificial); computers) and only states of elements are changed (e.g. neurons (artificial); cells of computer memory) to store an information. Contrary to those approaches, the described approach uses network of very simple elements with permanent state (i.e. without state), but the structure of links between elements (scheme) in the network depends on information that is stored.
So, the information is stored just in the structure of the network.
As basic element of the structure-based associative memory we uses an element with two entry pins (A and B) and two exit pins (C and D). The logic of the element is the following: C=A+B, D=A-B.
The core part of the paper is the question: how to retrieve the structure of links (scheme) of the network from the set of vectors that the network should store. Several approaches to optimize those schemes are described.
THE GENERAL PRINCIPLES OF THE MEMORY
In the general, the basic ideas of the memory are more or less traditional. We will store in the memory binary vectors. The key vector (i.e. vector that is “searched” in the memory) may contain special values “undefined” to mark unknown bits. So, we use below the vectors with three values {–1 ,0,1} (-1 – false, 0 – undefined, 1 – true).
To find the result vector(s) we define likeness for vectors:
Let’s A and B – two vectors with n elements, then define likeness as
L(A,B)=A1*B1+A2*B2+…+An*Bn
The result of the “recall” is the vector(s) where the likeness is maximal. If there are several vectors with maximum likeness then define of the result of the recall as the following
R=sign(M1+M2+…Mk),
Where M1…Mn – vectors with maximum likenesses value.
EXAMPLES
Let we have the following matrix of the stored vectors: (+ denotes +1, - denotes –1)
++-+
+--+
+++-
---+
----
Let’s [–00-] is the key vector. Then the vector of likenesses is multiplication of the key vector on the matrix.
For first row of the matrix the L value (likeness) is
-1+0+0+(-1)=-2
etc.
The result vector of likenesses will be the following:
[-2,-2,0,0,2]. So, the result of the recall is the vector with likeness =2, i.e. [----].
Let’s consider the another key vector: [+000]. Then the vector of likeness values will be
[1,1,1,-1,-1] and the result is the signum of sum of vectors with the maximum likeness values.
[++-+] + [+--+] + [+++-] =sign([3,1,-1,1])=[1,1,-1,1]
(The summing of result vectors we can consider as multiplication of the maximums vector (vector with 1 where likeness is maximal) on the transpose of the matrix of stored vectors).
So, we can consider the process of “recall” as three-phase process:
1. Calculation the multiplication of the vector on the matrix of the stored vectors.
2. Retrieving the maximums vector.
3. Calculation the multiplication of the maximums vectors on the transpose of the matrix.
THE SCHEME OF THE MEMORY
The main idea of the implementation of the memory is the following. We will not save these storing vectors in the some sort of memory. Instead, we will try to implement the phases 1 and 3 for the given matrix as a “hardware”, specific for the given matrix (given set of the stored vectors).
The banal scheme of the “hardware” is very simple.
Our matrix contains only –1 and +1 so we need only addition/subtract operations to implement the “hardware”.
For each row in the matrix we will use the sequence of elements (each element implements addition or subtract). So that, if an element of the matrix is +1 – the corresponding “hardware” element implements addition, otherwise – subtract.
That scheme is not interesting, because for matrix MxN we need MxN elements that implement addition/subtract. (It is much more expensive than to store the information in the computer’s memory).
However, we can optimize the scheme for the given set of the stored vectors. For example, we may find vectors with identical parts (sequence of bits) and use the same sequence of elements for calculation for such vectors. As result we can build network of “additional/subtract” elements with irregular structure, depended on the stored vectors set (and this network will calculate multiplication of any key vector on the matrix of the stored vectors).
An example of the matrix with very compact scheme of multiplication is well known. It’s Hadamar’s matrix (the rows of the matrix is Walsh functions). The compact scheme for this matrix called Fast Walsh-Fourier Transform. The FWT needs only N*Ln(N) (Ln with base=2) elements “addition/subtract” for matrix NxN. (The operation for phase 3 is just backward Walsh-Fourier transform).
Literature.
Henning F. Harmuth. Sequency Theory Foundations and Applications, 1977
![[info]](http://l-stat.livejournal.com/img/userinfo.gif?v=92.1){kind=small}
amspb1's journal
