# HTM with Residue Number Systems and Vector Symbolic Algebra

## Background: Grid Cells

Grid cells are a well documented population of neurons with some remarkable properties. Grid cells are grouped together into modules that operate independently and have different scales and orientations. Each cell responds in physical locations in the world that form a regular hexagonal grid. A population of cells can be represented as a finite space in which each cell fires in a single location and the when you move beyond the boundaries of the space you wrap around to the other side.

One of the primary advantages of grid cells is that they maintain a two dimensional position that aggregates movements over time. This provides path integration, or the ability to determine your relative position across multiple movements.

TODO

## The Grid Cell Trick

Grid cell modules are implementations of a Reside Number System with two dimensions. Each module represents a finite relative space and a set of modules together represent specific locations in a very large world.

The Grid Cell Trick is a mechanism that utilizes three populations of grid cells to relate two values (the input populations) together to form a transform (the output population). In addition to combining two values to get a transform, you can combine a value with a transform to get the other relative value. The two values may be two types of locations, in which case the operation may provide a new representation that encodes the relative position of the locations. This is an example of a Residue Number System "subtraction." Alternatively, the locations can be combined addititively to allow the combining of many locations.

Note that encoding and decoding values are the only operations that involve all of the modules in a layer. All other operations happen either within a single module in a layer, or between one module from each layer. We currently assume that the inter-layer operations operate on modules with the same number of neurons and with the same scale and orientation. This is not the case between modules in the same layer.

## Vector Symbolic Algebra (VSA)

Also called Holographic Reduced Representations, among other things.

VSA defines a set of operations that apply to arrays of values. The values can be complex numbers, real values, or binary. The work in Bruno's group at Berkeley seems most interested in VSA with complex values, which in some ways is similar to our grid cell modules that have two independent dimensions.

This table gives a primer on the types of operations that are defined by VSA, along with the SDR variant and differences.

Operation Description Notation SDR Variant SDR Variant Differences
Bind Binary operation that combines two values to get a new value with the same dimensionality. Can be apply recursively to bind many values together. $$A \otimes B$$ Grid cell trick that is equivalent to a mathematical addition or subtraction implemented with a residue number system. The subtraction variant cannot be recursively applied and can only bind two values together.
Unbind Binary operation that strips one of the originally bound values, leaving the others. $$A^{-1}\otimes(A \otimes B) \approx B$$ Grid cell trick that takes a transform plus value from one input to get the value for the other input. Same limitations as binding.
Permutation Change a value in a way that can be reversed before or after bind/unbind operations. Unary operation. Distributive over superpositions. $$P^{-1}(P(A)) \approx A$$ The SDR variant is leveraged for path integration. It is a binary operation that takes a magnitude. For integer magnitudes, this is analogous to applying the unary permutation multiple times but is a generalized description that supports multiple dimensions and positive and negative values. It has a property called reduction, meaning that the magnitudes are aggregated, or $$P(P(A, i), j) = P(A, i+j)$$. Note equivalence between permutation and bind described below. The extra parameter and reduction property enables path integration across multiple dimensions.
Superposition Multiple values can be combined into a set representation. Other operations that are distributive will apply to all items in the set. Useful for checking whether new items belong to the set without the need for bind. $$A + B + C$$ The SDR variant is the union operation, or bitwise OR. This operation becomes more important with SDRs since the "subtraction" bind operation cannot combine more than two elements.

### Implementing Permutation with Bind

Note that permutation is a special case of binding. In typical VSA with a unary permutation, the permutation operation can be implemented as a bind with a fixed value. The inverse permutation then is just an unbind of the same fixed value. In our grid cell / SDR implementation, the binary permutation can be implemented as the binding of a value in one input population with the permutation magnitude as the second input. This can be applied recursively, binding the result of the previous operation with a new permutation magnitude, to apply multiple permutations that respect the reduction (path integration) property.

### Binding 3+ SDRs

The current SDR / grid cell variant of bind and unbind are not symmetric. If you implement bind as addition, then both unbinds are subtrations. If you implement bind as subtraction, then one unbind is addition while the other is subtraction. In order to bind more than two values, the bind operation must be addition. This does not work for our transform though, because the transform must be invariant to permutations applied to both inputs, which requires it to be a "subtraction". In other words, $$P(A, x) \otimes P(B, x) = A \otimes B$$.



In [ ]: