Mathematical model of memory
Sparse distributed memory (SDM) is a mathematical model of human long-term memory introduced by Pentti Kanerva in 1988 while he was at NASA Ames Research Center.
This memory exhibits behaviors, both in theory and in experiment, that resemble those previously unapproached by machines – e.g., rapid recognition of faces or odors, discovery of new connections between seemingly unrelated ideas, etc. Sparse distributed memory is used for storing and retrieving large amounts (formula_1 bits) of information without focusing on the accuracy but on similarity of information. There are some recent applications in robot navigation and experience-based robot manipulation.
General principle.
It is a generalized random-access memory (RAM) for long (e.g., 1,000 bit) binary words. These words serve as both addresses to and data for the memory. The main attribute of the memory is sensitivity to similarity. This means that a word can be read back not only by giving the original write address but also by giving one close to it, as measured by the number of mismatched bits (i.e., the Hamming distance between memory addresses).
SDM implements transformation from logical space to physical space using distributed data representation and storage, similarly to encoding processes in human memory. A value corresponding to a logical address is stored into many physical addresses. This way of storing is robust and not deterministic. A memory cell is not addressed directly. If input data (logical addresses) are partially damaged at all, we can still get correct output data.
The theory of the memory is mathematically complete and has been verified by computer simulation. It arose from the observation that the distances between points of a high-dimensional space resemble the proximity relations between concepts in human memory. The theory is also practical in that memories based on it can be implemented with conventional random-access memory elements.
Definition.
Human memory has a tendency to congregate memories based on similarities between them (although they may not be related), such as "firetrucks are red and apples are red". Sparse distributed memory is a mathematical representation of human memory, and uses high-dimensional space to help model the large amounts of memory that mimics that of the human neural network. An
important property of such high dimensional spaces is that two randomly chosen vectors are relatively far away from each other, meaning that they are uncorrelated. SDM can be considered a realization of locality-sensitive hashing.
The underlying idea behind a SDM is the mapping of a huge binary memory onto a smaller set of physical locations, so-called "hard locations". As a general guideline, those hard locations should be uniformly distributed in the virtual space, to mimic the existence of the larger virtual space as accurately as possible. Every datum is stored distributed by a set of hard locations, and retrieved by averaging those locations. Therefore, recall may not be perfect, accuracy depending on the saturation of the memory.
Kanerva's proposal is based on four basic ideas:
The binary space N.
The SDM works with n-dimensional vectors with binary components. Depending on the context, the vectors are called points, patterns, addresses, words, memory items, data, or events. This section is mostly about the properties of the vector space N = formula_5. Let n be number of dimensions of the space. The number of points, or possible memory items, is then formula_3. We will denote this number by N and will use N and formula_3 to stand also for the space itself.
Concepts Related to the space N: formula_5
Properties of the space N: formula_5
The space N can be represented by the vertices of the unit cube in n-dimensional Euclidean space. The vertices lie on the surface of an n-dimensional sphere with (Euclidean-metric) radius formula_10. This gives rise to the sphere analogy. We will call a space spherical if
The surface of a sphere (in Euclidean 3d-space) clearly is spherical. According to definition, N is also spherical, since y ⊕ x ⊕ (…) is an automorphism that maps x to y. 
Because N is spherical, it is helpful to think of it as the surface of a sphere with circumference 2n. All points of N are equally qualified as points of origin, and a point and its complement are like two poles at distance n from each other, with the entire space in between. The points halfway between the poles and perpendicular to them are like the equator.
The number of points that are exactly d bits from an arbitrary point x (say, from the point 0) is the number of ways to choose d coordinates from a total of n coordinates, and is therefore given by the binomial coefficient: 
formula_11
The distribution of N thus is the binomial distribution with parameters n and p, where p = 1/2. The mean of the binomial distribution is n/2, and the variance is n/4. This distribution function will be denoted by N(d). 
The normal distribution F with mean n/2 and standard deviation formula_10 is a good approximation to it: 
An outstanding property of N is that most of it lies at approximately the mean (indifference) distance n/2 from a point (and its complement). In
other words, most of the space is nearly orthogonal to any given point, and the larger n is, the more pronounced is this effect.
As neural network.
The SDM may be regarded either as a content-addressable extension of a classical random-access memory (RAM) or as a special type of three layer feedforward neural network. The main SDM alterations to the RAM are:
Neuron model.
An idealized description of neuron is as follows: a neuron has a cell body with two kinds of branches: "dendrites" and an "axon". It receives input signals from other neurons via dendrites, integrates (sums) them and generates its own (electric) output signal which is sent to outside neurons via axon. The points of electric contact between neurons are called "synapses".
When a neuron generates signal it is "firing" and after firing it must "recover" before it fires again.
The relative importance of a synapse to the firing of neuron is called "synaptic weight" (or "input coefficient"). There are two kinds of synapses: excitatory that trigger neuron to "fire" and inhibitory that hinder firing. The neuron is either excitatory or inhibitory according to the kinds of synapses its axon makes.
A neuron fires when the sum of inputs exceed a specific "threshold". The higher the threshold the more important it is that excitatory synapses have input while inhibitory ones do not. Whether a recovered neuron actually fires depends on whether it received sufficient excitatory input (beyond the threshold) and not too much of inhibitory input within a certain period.
The formal model of neuron makes further simplifying assumptions. An "n"-input neuron is modeled by a "linear threshold function" formula_14 as follows :
For formula_15 where n is the number of inputs, let formula_16 be the output at time "t": formula_17, and let formula_18 be the "i"-th input at time "t": formula_19. Let formula_20 be the weight of the "i"-th input and let formula_21 be the threshold.
The "weighted sum" of the inputs at time "t" is defined by formula_22
The "neuron output" at time "t" is then defined as a boolean function: 
formula_23
Where Ft=1 means that the neuron fires at time "t" and Ft=0 that it doesn't, i.e. in order for neuron to fire the weighted sum must reach or exceed the threshold .
Excitatory inputs increase the sum and inhibitory inputs decrease it.
Neuron as address-decoder.
Kanerva's key thesis is that certain neurons could have their input coefficients and thresholds fixed over the entire life of an organism and used as address decoders where "n"-tuple of input coefficients (the pattern to which neurons respond most readily) determines the "n"-bit memory address, and the threshold controls the size of the region of similar address patterns to which the neuron responds.
This mechanism is complementary to adjustable synapses or adjustable weights in a neural network (perceptron convergence learning), as this fixed accessing mechanism would be a permanent "frame of reference" which allows to "select" the synapses in which the information is stored and from which it is retrieved under given set of circumstances. Furthermore, an encoding of the present circumstance would serve as an address.
The address "a" of a neuron with input coefficients "w" where formula_24 is defined as an "n"-bit input pattern that maximizes the weighted sum. The maximum occurs when the inhibitory inputs are zeros and the excitatory inputs are ones.
The "i"-th bit of address is:
formula_25
The "maximum weighted sum" formula_26 is then the sum of all positive coefficients: 
formula_27
And the "minimum weighted sum" formula_28 would correspond to a point opposite the neuron address a`: formula_29
When the threshold c is in range ;math ; s(w) ;c the output of the neuron is 0 for some addresses (input patterns) and 1 for others. If the threshold is above S the output is always 0, if it's below s the output is always 1. So by a proper choice of the threshold a neuron responds only to just one address. When the threshold is S (the maximum for the weighted sum) the neuron responds only to its own address and acts like an address decoder of a conventional random-access memory.
Memory location.
SDM is designed to cope with address patterns that span an enormous address space (order of formula_1). SDM assumes that the address patterns actually describing physical situations of interest are "sparsely" scattered throughout the input space. It is impossible to reserve a separate physical location corresponding to each possible input; SDM implements only a limited number of physical or "hard" locations. The physical location is called a memory (or "hard") location.
Every hard location has associated with it two items:
In SDM a word could be stored in memory by writing it in a free storage location and at the same time providing the location with the appropriate address decoder. A neuron as an address decoder would select a location based on similarity of the location's address to the retrieval cue. Unlike conventional Turing machines SDM is taking advantage of "parallel computing by the address decoders". The mere "accessing the memory" is regarded as computing, the amount of which increases with memory size.
Address pattern.
An N-bit vector used in writing to and reading from the memory. The address pattern is a coded description of an environmental state. (e.g. N = 256.)
Data pattern.
An M-bit vector that is the object of the writing and reading operations. Like the address pattern, it is a coded description of an environmental state. (e.g. M = 256.)
Writing.
Writing is the operation of storing a data pattern into the memory using a particular
address pattern. During a write, the input to the memory consists of an address pattern and a data pattern. The address pattern is used to select "hard" memory locations whose hard addresses are within a certain cutoff distance from the address pattern. The data pattern is stored into each of the selected locations.
Reading.
Reading is the operation of retrieving a data pattern from the memory using a particular address pattern. During a read, an address pattern is used to select a certain number of "hard" memory locations (just like during a write). The contents of the selected locations are bitwise summed and thresholded to derive an M-bit data pattern. This serves as the output read from the memory.
Pointer chains.
All of the items are linked in a single list (or array) of pointers to memory locations, and are stored in RAM. Each address in an array points to an individual line in the memory. That line is then returned if it is similar to other lines. Neurons are utilized as address decoders and encoders, similar to the way neurons work in the brain, and return items from the array that match or are similar.
Critical distance.
Kanerva's model of memory has a concept of a "critical point": prior to this point, a previously stored item can be easily retrieved; but beyond this point an item cannot be retrieved. Kanerva has methodically calculated this point for a particular set of (fixed) parameters. 
The corresponding "critical distance" of a Sparse Distributed Memory can be approximately evaluated minimizing the following equation with the restriction formula_31 and formula_32. The proof can be found in,
formula_33
Where:
Probabilistic interpretation.
An associative memory system using sparse, distributed representations can be reinterpreted as an importance sampler, a Monte
Carlo method of approximating Bayesian inference. The SDM can be considered a Monte Carlo approximation to a multidimensional conditional probability integral. The SDM will produce acceptable responses from a training set when this approximation