Hypervectors

What is Hyperdimensional Computing?

Hyperdimensional computing (HDC) represents concepts as high-dimensional vectors (also called hypervectors) and manipulates them with algebraic operations, typically the dimension (of vectors) can be as high as thousands or millions.

The key insight is that random vectors in high-dimensional spaces are nearly orthogonal: giving each concept a unique, robust representation that tolerates potential ambiguity and interference, all without central orchestration.

In that sense, the traditional mantra of curse of dimensionality becomes the blessing of dimensionality.

Motivated readers should perform their own background research on this topic and make judgement of their own. There are quite a few introductory papers covering this topic.

Sparse Binary Representation

kongming specializes in sparse binary hypervectors. Each vector has a fixed, large number of dimensions (e.g., 65,536/64K or 1,048,576/1M), but only a very small fraction of them are “on” (set to 1). The sparsity is controlled by the Model configuration.

Furthermore, we focus on a special sparse binary configuration: SparseSegmented where each vector is divided into equal-sized segments, and exactly one bit is ON per segment. For example, each of the 8bit-model hypervectors will have total dimension of $2^{16}=65536$, divided into $256$ segments, where each segment of $256$ dimension will have one (and only one) ON bit.

Alternatively you can imagine each SparseSegmented hypervector as a list of phasors, where the offset of ON bit (within the host segment) represents the discretized phase.

In general, this unique constraint enables:

• Compact storage: only the offset of ON bit need to be stored, and we only need to store the bare entropy for the presentation;
• Efficient operations: Unlike neural nets, where weights are recorded in float-point numbers, binary operations can be performed very efficiently with modern memory / CPUs, and without the need of GPU for either float-point operations or matrix manipulations.

Similarity and distance measure

Two vectors are compared via overlap — the count of segments with the same ON bit offset. This is conceptually equivalent to a dimension-wise AND operation.

Naturally, a vector’s overlap with itself equals its cardinality $M$.

For a model with dimension $N$ and sparsity $s$, the expected overlap between two random vectors $A$ and $B$ is:

$$\text{E}[O(A,B)]=N{s}^2=1$$

Actually, the overlap (of random vectors) follows a Poisson distribution with $\lambda =1$.

The commonly-used distance measure (or dis-similar measure) for binary vectors is Hamming Distance, equivalent to a bitwise XOR operation. As we discussed (and proved) in the paper, the overlap and Hamming distance for sparse binary hypervectors are two sides of the same coin, with the following equation:

$$2\times O(A,B)+H(A,B)=2M$$

The closer two vectors in Hamming space, the more overlap they have.

Supported Models

A Model determines the total number of dimensions (width), how those dimensions are divided into segments (cardinality and sparsity), and therefore implies critical storage and compute characteristics.

Model properties

All model functions take a Model enum value and return the derived property:

How to Choose a Model

• MODEL_64K_8BIT: Fast prototyping, tiny memory footprint, and high performance (due to SIMD). Good for tests, experiments and production.
• MODEL_1M_10BIT: General-purpose, balances performance and storage.
• MODEL_16M_12BIT: General-purpose, for the adventurous.
• MODEL_256M_14BIT / MODEL_4G_16BIT: Very high capacity, not there yet.

In general, larger models provide more orthogonal space (lower collision probability) at the cost of more memory per vector.