Introduction to Hyperdimensional Computing (the HDC kitchen)

Hyperdimensional Computing (HDC) is a brain-inspired computational paradigm that represents and manipulates information using high-dimensional vectors called hypervectors. These vectors typically have thousands of dimensions (often 1.000-10.000), making them "hyperdimensional." The key insight is that high-dimensional spaces have unusual mathematical properties that allow for robust, fault-tolerant computation based on a defined set of operations that enable representing any object or structure as a hypervector.

Rather than listing those properties in the abstract, let's cook with them. In this tutorial we treat HDC as a kitchen:

Our running example is deliberately simple: we will "cook" a 🌮 taco and a 🍔 hamburger, and then add a third plate, a 🥪 chicken club sandwich, to see how the plates relate to each other – and finally do some inference using algebraic operations over our "food" hypervectors.

Setting up our experiment

First of all, we need to define the nature of our hypervectors. For this, we pick with vector-symbolic architecture (VSA) we will work in. This is, essentially, the flavour of hypervectors we will work with. For tutorial sake, we will use BinaryHV, the binary spatter code and arguably the most widely used VSA.

using HyperdimensionalComputing

H = BinaryHV

BinaryHV

Let's create a hypervector to see what one actually looks like:

h = H()

10000-element BinaryHV with 4998 true and 5002 false:
 1
 1
 0
 0
 1
 0
 0
 0
 0
 0
 ⋮
 1
 0
 0
 0
 0
 1
 0
 0
 1

It is just a long vector of bits. For BinaryHV each component is a 0 or a 1:

eltype(h)

Bool

...and there are a lot of them – this is where the "hyper" comes from:

length(h)

10000

Operations

Now that we have defined the nature of the hypervectors we will work with, let's go over each operation we have available to "cook" with hypervectors:

Mapping $\varphi$: every ingredient is a hypervector

The first rule of HDC is that everything is a hypervector. The mapping $\varphi$ takes any object – a word, a number, or here an ingredient – and assigns it a hypervector. The simplest mapping just draws a fresh random hypervector for each item. Let's stock our pantry, giving every ingredient its own random hypervector named (for fun) with its emoji:

🥓 = H()  # bacon
🥩 = H()  # beef
🍞 = H()  # bread
🍔 = H()  # bun
🧀 = H()  # cheese
🍗 = H()  # chicken
🥬 = H()  # lettuce
🥚 = H()  # mayo
🧅 = H()  # onion
🌶️ = H()  # salsa
🍅 = H()  # tomato
🫓 = H()  # tortilla
🦃 = H(); # turkey

Similarity $\delta$: are ingredients similar?

Inference with hypervectors is based on comparing them, therefore we need some way of achieving this. Each VSA defines a similarity or distance measurement to assess how similar are hypervectors between each other.

Because each ingredient is an independent random draw, different ingredients are essentially unrelated ("quasi-orthogonal"). We can check this by comparing beef against a few ingredients at once. similarity(🥩) returns a function that measures similarity to 🥩, which we broadcast over a list:

similarity(🥩).([🥩, 🧀, 🧅])

3-element Vector{Float64}:
 1.0
 0.3308569912443619
 0.33653589538297307

BinaryHV uses the Jaccard similarity, which runs from 0 to 1. A hypervector is perfectly similar to itself (1.0), while two unrelated vectors share about a third of their set bits and so sit near a baseline of ≈ 0.33.

Bundling $\oplus$: mixing

Bundling (a.k.a. superposition) combines hypervectors into a new one that is similar to all of its ingredients, think of tossing everything into one bowl. Let's mix a taco filling:

filling = bundle([🥩, 🧅, 🧀])

10000-element BinaryHV with 5019 true and 4981 false:
 0
 1
 0
 1
 1
 1
 1
 0
 1
 1
 ⋮
 0
 0
 0
 1
 1
 0
 0
 1
 0

You can also use the overloaded + operator:

filling == 🥩 + 🧅 + 🧀

true

The operation "remembers" what went into it: it is clearly similar to each of its ingredients, but not to something we never added (bread is a stranger to this bowl):

similarity(filling).([🥩, 🧅, 🧀, 🍞])

4-element Vector{Float64}:
 0.60625
 0.599075402518731
 0.5904701598860218
 0.3320473593188772

Binding $\otimes$: associating

Binding combines hypervectors into a new one that is dissimilar to its inputs. It is the tool for associating hypervectors to create new concepts. Let's define a ROLE hypervector and bind cheese to it:

ROLE = H(:role)
topping = ROLE * 🧀

10000-element BinaryHV with 4938 true and 5062 false:
 1
 1
 0
 1
 1
 0
 1
 0
 0
 0
 ⋮
 0
 1
 0
 0
 1
 0
 1
 0
 1

The resulting topping sits back at the ~0.33 baseline against both the role and the ingredient, binding hides its operands, so topping looks unrelated to either:

similarity(topping).([🧀, ROLE])

2-element Vector{Float64}:
 0.3321748429354364
 0.3278973399278171

Notably, binding is reversible in some VSAs. For BinaryHV the bind is a bitwise XOR, which is its own inverse, so binding again with the role recovers the ingredient exactly (similarity 1.0). This "unbinding" is what will later let us query a recipe:

similarity(ROLE * topping, 🧀)

1.0

Permutation $\rho$: ordering

Permutation takes a hypervector and cyclically shifts it into a new one that is dissimilar to the original. It is how HDC encodes order, e.g. because in the kitchen, order matters (sear then simmer is not the same as simmer then sear):

similarity(🥩, ρ(🥩))

0.3331557213267617

Applying it repeatedly keeps producing fresh, quasi-orthogonal vectors, giving each position its own signature:

similarity(🥩).([🥩, ρ(🥩, 1), ρ(🥩, 2), ρ(🥩, 3)])

4-element Vector{Float64}:
 1.0
 0.3331557213267617
 0.33049720818931133
 0.3358248798718633

We can use this to encode order or hierarchy, as this produces an alternative version of our original hypervector. Encode a two-step recipe by permuting the second step once (position 0, then position 1), and compare it to the same steps performed in the opposite order:

sear = H(:sear)
simmer = H(:simmer)

similarity(sear + ρ(simmer), simmer + ρ(sear))

0.33432231962238707

Same two actions but with different order. Hypervectors come out unrelated.

Encoding: cooking a plate

We now combine the operations to "cook." There is no single right way to turn a list of ingredients into a plate hypervector: the choice of encoder determines what the resulting vector remembers. The package ships several; here we compare three, from least to most structured, using a taco's ingredients:

ingredients = [🫓, 🥩, 🧅, 🌶️, 🧀]

5-element Vector{BinaryHV}:
 10000-element BinaryHV with 5063 true and 4937 false
 10000-element BinaryHV with 5004 true and 4996 false
 10000-element BinaryHV with 5012 true and 4988 false
 10000-element BinaryHV with 4989 true and 5011 false
 10000-element BinaryHV with 5028 true and 4972 false

multiset creates an unordered bag, it simply bundles the ingredients. It is the simplest encoder, but it forgets everything except which ingredients are present: shuffle them and you get the exact same vector.

multiset(ingredients)

10000-element BinaryHV with 5048 true and 4952 false:
 1
 0
 0
 1
 1
 1
 1
 1
 1
 1
 ⋮
 1
 0
 0
 1
 1
 0
 0
 0
 0

similarity(multiset(ingredients), multiset(shuffle(ingredients)))

1.0

bundlesequence creates an ordered stack, it permutes each ingredient by its position before bundling, encoding ordered presence of hypervectors.

bundlesequence(ingredients)

10000-element BinaryHV with 5029 true and 4971 false:
 1
 0
 1
 1
 1
 1
 1
 1
 1
 1
 ⋮
 1
 0
 0
 1
 0
 1
 0
 0
 0

Now reversing the stack gives an unrelated vector, useful for layered dishes or recipe steps, where sequence matters:

similarity(bundlesequence(ingredients), bundlesequence(reverse(ingredients)))

0.4075418994413408

hashtable creates a a keyed record, it binds each key-value pair and bundles them together. This is the most structured of the three: order is irrelevant, but each ingredient is filed under the role it plays, so we can later query it back.

Let's define our roles:

BASE = H(:base)       # tortilla, bun, bread...
PROTEIN = H(:protein) # beef, chicken, turkey...
VEGGIE = H(:veggie)   # onion, lettuce...
SAUCE = H(:sauce)     # salsa, ketchup, mayo...
EXTRA = H(:extra)     # cheese, bacon...

roles = [BASE, PROTEIN, VEGGIE, SAUCE, EXTRA]

5-element Vector{BinaryHV}:
 10000-element BinaryHV with 4960 true and 5040 false
 10000-element BinaryHV with 4932 true and 5068 false
 10000-element BinaryHV with 5023 true and 4977 false
 10000-element BinaryHV with 4984 true and 5016 false
 10000-element BinaryHV with 4962 true and 5038 false

Our 🌮 taco – a tortilla base, beef, onion, salsa, and a bit of cheese – and our 🍔 hamburger – a bun, beef, lettuce, tomato, and cheese:

taco = hashtable(roles, [🫓, 🥩, 🧅, 🌶️, 🧀])
burger = hashtable(roles, [🍔, 🥩, 🥬, 🍅, 🧀])

10000-element BinaryHV with 5020 true and 4980 false:
 1
 0
 1
 0
 0
 0
 0
 0
 0
 1
 ⋮
 1
 0
 0
 1
 1
 1
 1
 1
 0

Each plate is now a single hypervector encoding its whole (structured) recipe. The three encoders trade off resolving power against simplicity: multiset answers only "what is in it?", bundlesequence also captures "in what order?", and hashtable captures "what plays which role?" – the one we need to reason about recipes.

Comparison: are two plates alike?

With every plate living in the same space, we can reason about them in two complementary ways: by measuring similarity and by doing algebra on the hypervectors.

Measuring similarity

Let's add a third plate, a 🥪 club sandwich. This one is interesting: its protein could be chicken or turkey. We express that ambiguity directly by superposing (bundling) the two poultry options into a single hypervector that is similar to both:

poultry = 🍗 + 🦃

10000-element BinaryHV with 4964 true and 5036 false:
 1
 1
 1
 0
 0
 1
 1
 1
 0
 0
 ⋮
 1
 1
 0
 0
 0
 0
 1
 0
 1

The sandwich is then bread, that poultry, lettuce, mayo, and bacon:

sandwich = hashtable(roles, [🍞, poultry, 🥬, 🥚, 🥓])

10000-element BinaryHV with 4990 true and 5010 false:
 0
 1
 1
 0
 0
 0
 0
 0
 1
 1
 ⋮
 0
 1
 0
 1
 1
 1
 0
 1
 1

How close are the taco and the hamburger? The shared beef and cheese make them noticeably alike, while the sandwich shares only its lettuce with the burger and nothing with the taco:

similarity(taco).([burger, sandwich])

2-element Vector{Float64}:
 0.4788110653325486
 0.32908873855949067

We can look at all three plates at once with a similarity matrix (rows/columns are taco, burger, sandwich):

plates = [taco, burger, sandwich]
similarity(plates)

3×3 Matrix{Float64}:
 1.0       0.478811  0.329089
 0.478811  1.0       0.398435
 0.329089  0.398435  1.0

The pattern matches culinary intuition: taco and burger are the most alike (shared beef + cheese), burger and sandwich are mildly alike (shared lettuce), and taco and sandwich are strangers. Similar recipes give similar vectors.

Algebra: querying and mapping between plates

Because binding is reversible, a plate is not a black box – it is a little database we can query. Unbinding a plate with a role recovers the ingredient that filled it. We compare the result against the pantry with nearest_neighbor:

pantry = [🫓, 🍔, 🍞, 🥩, 🍗, 🦃, 🧅, 🥬, 🌶️, 🍅, 🥚, 🧀, 🥓]
names = [
    "tortilla", "bun", "bread", "beef", "chicken", "turkey", "onion",
    "lettuce", "salsa", "tomato", "mayo", "cheese", "bacon",
]

nearest_neighbor(taco * PROTEIN, pantry)

(0.5284204075379194, 4, Bool[0, 1, 0, 1, 1, 1, 1, 1, 1, 1  …  1, 0, 0, 0, 0, 1, 0, 0, 0, 0])

The result is a (similarity, index, hypervector) tuple pointing at the winning ingredient – here, the taco's protein is beef. Remember the sandwich's ambiguous protein? Querying it recovers both poultry options and rejects beef, exactly as the superposition intended:

similarity(sandwich * PROTEIN).([🍗, 🦃, 🥩])

3-element Vector{Float64}:
 0.42428977272727275
 0.4112388250319285
 0.3333333333333333

Sweeping every role reconstructs the full menu straight from the plate hypervectors alone:

recover(plate, role) = names[nearest_neighbor(plate * role, pantry)[2]]
[recover(plate, role) for plate in plates, role in roles]

3×5 Matrix{String}:
 "tortilla"  "beef"     "onion"    "salsa"   "cheese"
 "bun"       "beef"     "lettuce"  "tomato"  "cheese"
 "bread"     "chicken"  "lettuce"  "mayo"    "bacon"

Each row is a plate, each column a role. Unbinding also works the other way around: give a plate an ingredient and it tells you the role that ingredient plays.

rolenames = ["BASE", "PROTEIN", "VEGGIE", "SAUCE", "EXTRA"]
rolenames[argmax(similarity(taco * 🧅).(roles))]

"VEGGIE"

This two-way lookup lets us map concepts from one dish to another. Suppose we like the onion in our taco and ask: "what plays the same part in the burger?" We do it in two clean steps – first find onion's role in the taco, then read that role out of the burger:

onion_role = roles[argmax(similarity(taco * 🧅).(roles))]   # 🧅 is the taco's VEGGIE...
recover(burger, onion_role)                                    # ...and the burger's VEGGIE is?

"lettuce"

The system answers lettuce: onion is to the taco what lettuce is to the burger. We have inferred an analogy the recipes never stated explicitly – the kind of associative reasoning that makes hyperdimensional representations so powerful.

Wrap-up

In one sitting we cooked three plates and met the whole HDC toolkit:

• Mapping turned emojis into hypervectors, deterministically: the same ingredient always gets the same hypervector.
• Bundling mixed ingredients into a filling similar to each of its parts (and let a protein be "chicken or turkey").
• Binding associated ingredients with roles and, being its own inverse, let us un-associate them again.
• Permutation made order matter.
• Different combinators (multiset, bundlesequence, hashtable) remember different things about the same ingredients.
• Similarity told us which plates are alike, and algebra let us query recipes and map concepts from one dish to another.

The takeaways generalize far beyond the kitchen: all data lives in the same high-dimensional space, the representation is robust to noise thanks to the blessing of dimensionality, and hypervectors plus a handful of encoders can represent richly structured data.

From here, have a look at "What's the Dollar of Mexico?" for more analogical reasoning, or at the Iris dataset example for a full classification workflow on numeric data.

This page was generated using Literate.jl.