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 = ${\displaystyle \{0,1\}^{n}}$. Let n be number of dimensions of the space. The number of points, or possible memory items, is then ${\displaystyle 2^{n}}$. We will denote this number by N and will use N and ${\displaystyle 2^{n}}$ to stand also for the space itself.^[6]

Concepts Related to the space N: ${\displaystyle \{0,1\}^{n}}$^[6]

• Origin, 0: The point with all coordinates 0 is called the origin, 0 = 000...00.
• Complement, 'x: The complement, or opposite, of point x is the n-tuple that has ones where x has zeros and vice versa.
• Norm, |x|: The norm of point x is the number of ones in its binary representation.
• Difference, x − y: The difference of two points x and y is the n-tuple that has ones where x and y differ and zeros elsewhere. It is the bitwise 'exclusive or': x − y = x ⊕ y. The difference commutes: x − y = y − x.
• Distance, d(x, y) The distance between two points x and y is the number of dimensions at which x and y differ. It is called the Hamming distance (its square root is the Euclidean distance) and is expressed in bits. Distance is the norm of the difference: d(x, y) = |x − y|
• Betweenness, x:y:z: Point y is between points x and z if and only if the distance from x to z is the sum of the distances from x to y and from y to z; that is, x:y:z ⇔ d(x, z) = d(x, y) + d(y, z). It is easily seen that every bit of a point in between is a copy of the corresponding bit of an endpoint.
• Orthogonality, x ⊥ y: Point x is orthogonal to point y, or the two are perpendicular or indifferent, if and only if the distance between the two is half the number of dimensions: x ⊥ y ⇔ d(x, y) = n/2. The distance n/2 is called indifference distance of space N. If x is orthogonal to y, it is also orthogonal to its complement 'y (x is halfway between y and 'y).
• Circle, O(r,x) A circle with radius r and center x is the set of points that are at most r bits from x: O(r,x) = {y | d(x, y) ≤ r}.

Properties of the space N: ${\displaystyle \{0,1\}^{n}}$^[1][6]

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 ${\displaystyle {\sqrt {n}}/2}$. This gives rise to the sphere analogy. We will call a space spherical if

1. any point x has a unique opposite 'x,
2. the entire space is between any point x and its opposite 'x, and
3. all points are "equal" (meaning that for any two points x and y there is a distance preserving automorphism of the space that maps x to y, so that from any of its points the space "looks" the same).

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.

Distribution of the space N

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: ${\displaystyle {\binom {n}{d}}={\frac {n!}{d!(n-d)!}}}$

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 ${\displaystyle {\sqrt {n}}/2}$ is a good approximation to it: N(d) = Pr{d(x, y) ≤ d} ≅ F{(d − n / 2)/ ${\displaystyle {\sqrt {n/4}}}$}

Tendency to orthogonality

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:^[13]

• The SDM calculates Hamming distances between the reference address and each location address. For each distance which is less or equal to the given radius the corresponding location is selected.
• The memory is represented by counters (where n is number of locations and m is the input data length) instead of single-bit storage elements.
• Writing to the memory, instead of overwriting, is as follows:
  • if the i-bit of the input data is 1, the corresponding counters (counters in the selected locations (rows) and in the i-th columns) are incremented,
  • if the i-bit of the input data is 0, the corresponding counters are decremented.
• Reading (or recall) from the memory is similar:
  • The contents of the selected locations are summed columnwise.
  • Each sum is thresholded. If the sum is greater than or equal to the threshold value the corresponding output bit is set to 1, in the opposite case it is cleared. Note that the thresholds may be zero, if the training input vectors are closed to orthogonal ones.

Memory location

SDM is designed to cope with address patterns that span an enormous address space (order of ${\displaystyle 2^{1000}}$). 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.^[7]

Every hard location has associated with it two items:

• a fixed hard address, which is the N-bit address of the location
• a contents portion that is M-bits wide and that can accumulate multiple M-bit data patterns written into the location. The contents' portion is not fixed; it is modified by data patterns written into the memory.

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.^[1]

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 ${\displaystyle d\in N}$ and ${\displaystyle d\leqslant n}$. The proof can be found in,^[17][18]

${\displaystyle {\tilde {f}}(d)=\left\{{\frac {1}{2}}\cdot \left[1-N\left(z<{\frac {w\cdot shared(d)}{\sqrt {\theta }}}\right)+N\left(z<{\frac {-w\cdot shared(d)}{\sqrt {\theta }}}\right)\right]-{\frac {d}{n}}\right\}^{2}}$

Where:

• ${\displaystyle d}$: is the distance to the target;
• ${\displaystyle n}$: is the number of dimensions;
• ${\displaystyle N}$: is the normalized normal distribution with mean zero and variance one;
• ${\displaystyle w}$: is the number of times the target bitstring was written in memory;
• ${\displaystyle \theta }$: is the total of random bitstrings in all ${\displaystyle h}$ hard-locations activated by a read operation; i.e., the size of a cell assembly;
• ${\displaystyle shared(d)}$: is the mean number of shared hard-locations activated by two bitstrings ${\displaystyle d}$ bits away from each other. One can find some values for a 1000-dimensional SDM in Kanerva's book, Table 7.1, p. 63, or the equations to calculate to any SDM in Appendix B, p. 125 of the same book.

The Best Match Search

SDM can be applied to the problem of finding the best match to a test word in a dataset of stored words.^[1][29] or, in other words, the Nearest neighbor search problem.

Consider a memory with N locations where ${\displaystyle N=2^{n}}$. Let each location have the capacity for one n-bit word (e.g. N= 2¹⁰⁰ 100-bit words), and let the address decoding be done by N address decoder neurons. Set the threshold of each neuron x to its maximum weighted sum ${\displaystyle |x|}$ and use a common parameter d to adjust all thresholds when accessing the memory. The effective threshold of neuron x will be then ${\displaystyle x-|d|}$ which means that the location x is accessible every time the address x is within d bits of the address presented to memory (i.e. the address held by the address register). With ${\displaystyle d=0}$ we have a conventional random-access memory. Assume further that each location has a special location-occupied bit that can be accessed in the same way as the regular datum bits. Writing a word to a location sets this location-occupied bit. Assume that only occupied location can be read.

To file the data in memory, start by setting ${\displaystyle d=n}$ and issue a command to clear the location-occupied bit. This single operation marks all memory as unoccupied regardless of the values of the address register. Then set ${\displaystyle d=0}$ and write each word y of the data set with y itself as the address. Notice that each write operation affects only one location: the location y. Filing time is thus proportional to the number of words in the dataset.

Finding the best match for a test word z, involves placing z in the address register and finding the least distance d for which there is an occupied location. We can start the search by setting ${\displaystyle d=0}$ and incrementing d successively until an occupied location is found. This method gives average search times that are proportional to the number of address bits or slightly less than ${\displaystyle n/2}$^[1] because the nearest occupied location can be expected to be just under ${\displaystyle n/2}$ bits from z (with binary search on d this would be O(log(n)).

With 100-bit words 2¹⁰⁰ locations would be needed, i.e. an enormously large memory. However if we construct the memory as we store the words of the dataset we need only one location (and one address decoder) for each word of the data set. None of the unoccupied locations need to be present. This represents the aspect of sparseness in SDM.

Speech recognition

SDM can be applied in transcribing speech, with the training consisting of "listening" to a large corpus of spoken language. Two hard problems with natural speech are how to detect word boundaries and how to adjust to different speakers. The memory should be able to handle both. First, it stores sequences of patterns as pointer chains. In training – in listening to speech – it will build a probabilistic structure with the highest incidence of branching at word boundaries. In transcribing speech, these branching points are detected and tend to break the stream into segments that correspond to words. Second, the memory's sensitivity to similarity is its mechanism for adjusting to different speakers – and to the variations in the voice of the same speaker.^[7]

"Realizing forgetting"

Decay Functions

The exponential decay function The negated-translated sigmoid function

At the University of Memphis, Uma Ramamurthy, Sidney K. D'Mello, and Stan Franklin created a modified version of the sparse distributed memory system that represents "realizing forgetting." It uses a decay equation to better show interference in data. The sparse distributed memory system distributes each pattern into approximately one hundredth of the locations, so interference can have detrimental results.^[30]

Two possible examples of decay from this modified sparse distributed memory are presented

Exponential decay mechanism: ${\displaystyle \!f(x)=1+e^{-ax}}$

Negated-translated sigmoid decay mechanism: ${\displaystyle f(x)=1-[{\frac {1}{1+e^{-a(x-c)}}}]}$

In the exponential decay function, it approaches zero more quickly as x increases, and a is a constant (usually between 3-9) and c is a counter. For the negated-translated sigmoid function, the decay is similar to the exponential decay function when a is greater than 4.^[30]

As the graph approaches 0, it represents how the memory is being forgotten using decay mechanisms.

Genetic sparse distributed memory

Ashraf Anwar, Stan Franklin, and Dipankar Dasgupta at The University of Memphis; proposed a model for SDM initialization using Genetic Algorithms and Genetic Programming (1999).

Genetic memory uses genetic algorithm and sparse distributed memory as a pseudo artificial neural network. It has been considered for use in creating artificial life.^[31]

Statistical prediction

SDM has been applied to statistical prediction, the task of associating extremely large perceptual state vectors with future events. In conditions of near- or over- capacity, where the associative memory behavior of the model breaks down, the processing performed by the model can be interpreted as that of a statistical predictor and each data counter in an SDM can be viewed as an independent estimate of the conditional probability of a binary function f being equal to the activation set defined by the counter's memory location.^[32]

Artificial general intelligence

• LIDA uses sparse distributed memory to help model cognition in biological systems. The sparse distributed memory places space is recalling or recognizing the object that it has in relation to other objects. It was developed by Stan Franklin, the creator of the "realizing forgetting" modified sparse distributed memory system.^[33] Transient episodic and declarative memories have distributed representations in LIDA (based on modified version of SDM^[34]), there is evidence that this is also the case in the nervous system.^[35]
• CMatie is a 'conscious' software agent developed to manage seminar announcements in the Mathematical Sciences Department at the University of Memphis. It is based on SDM augmented with the use of genetic algorithms as an associative memory.^[36]
• Hierarchical temporal memory utilizes SDM for storing sparse distributed representations of the data.

Reinforcement learning

SDMs provide a linear, local function approximation scheme, designed to work when a very large/high-dimensional input (address) space has to be mapped into a much smaller physical memory. In general, local architectures, SDMs included, can be subject to the curse of dimensionality, as some target functions may require, in the worst case, an exponential number of local units to be approximated accurately across the entire input space. However, it is widely believed that most decision-making systems need high accuracy only around low-dimensional manifolds of the state space, or important state "highways".^[37] The work in Ratitch et al.^[38] combined the SDM memory model with the ideas from memory-based learning, which provides an approximator that can dynamically adapt its structure and resolution in order to locate regions of the state space that are "more interesting"^[39] and allocate proportionally more memory resources to model them accurately.

Object indexing in computer vision

Dana H. Ballard's lab^[40] demonstrated a general-purpose object indexing technique for computer vision that combines the virtues of principal component analysis with the favorable matching properties of high-dimensional spaces to achieve high precision recognition. The indexing algorithm uses an active vision system in conjunction with a modified form of SDM and provides a platform for learning the association between an object's appearance and its identity.