Coding up a vector symbolic architecture example

I’ve been trying to get my head around VSA (a.k.a hyperdimensional computing). The only way I know how to do that is to write some code, so that’s what I’ve done.

The appeal of VSA  the combination of vector representations and an algebra to do some interesting reasoning. The “hyperdimensional” part comes everythng being a large random vector — at least 10,000 random bits for example.

Any random vector is going to be, more or less, orthogonal to any other. That opens the door to an algebra to query those vectors:

• multiplication, to “bind” a key to a value (a vector to another vector);
• addition, to “bundle” vectors together; and
• a distance metric, to find the closest vector to some arbitrary vector.

To understand some of that,  I’ve popped an example on Github. You can ask some interesting questions of random vectors, which is what I’ll work through here. It’s the “What is the Dollar of Mexico?” question you’ll see in this literature.

To start, I’ve defined a “hyperspace” to store vectors. It works on 10,000 dimensional bit vectors:

// This written in the Rust programming language
let seed = 42;
let mut rng = StdRng::seed_from_u64(seed);
let mut hyperspace = Hyperspace::<BitVec>::new(10_000);

This space of vectors (hyperspace) is backed by a data structure called a BitVec.

Random vectors are used to represent “stuff”:

let country = &hyperspace.draw("Country", &mut rng);

I’m “drawing” a vector at random from the space (it is stored in the space). At this point, if you were to print country you’d see [0,1,0,0,1,0,0,1...]. and 9,992 other bits. 

I’m associating a label with the vector because otherwise I’ll just end up printing out huge vectors of random numbers which will be hard to make sense of.

We can look up the labels for a vector:

&hyperspace.label_for(country)
// evaluates to "Country"

This is looking for the closest vector in the store that matches the argument. This is important later when we manipulate vectors, end up with noise and need to clean them up.

We can store a bunch of other values:

let currency = &hyperspace.draw("Currency", &mut rng);
let usa      = &hyperspace.draw("USA",      &mut rng);
let dollar   = &hyperspace.draw("Dollar",   &mut rng);
let mexico   = &hyperspace.draw("Mexico",   &mut rng);
let peso     = &hyperspace.draw("Peso",     &mut rng);

These are all random bit vectors.

Using multiplication, we can “bind” values together. For example, we can create a new vector for “USA is a country” and so on:

let usa_isa_country     = usa.product(country);
let mexico_isa_country  = mexico.product(country);
let dollar_isa_currency = dollar.product(currency);
let peso_isa_currency   = peso.product(currency);

These are values from multiplying two vectors together. This is implemented as XOR. I’ve not stored these in the hyperspace, but we could do.

What’s useful here is that we can “unbind” values by multiplying (XOR-ing) again. When X = A * B: 

A  = [0 1 0 1]
B  = [0 0 1 1]
X  = [0 1 1 0]

We can multiply X by A to recover B:

X  = [0 1 1 0]
A  = [0 1 0 1]
B' = [0 0 1 1]

Values are “bundled” together with addition.  We can create more vectors that combine the ideas of “USA (which is a country) is associated with the Dollar (which is a currency)”, and likewise for Mexico:

let usa_currency = 
   usa_isa_country.add(&dollar_isa_currency, &mut rng);

let mexico_currency = 
   mexico_isa_country.add(&peso_isa_currency, &mut rng);

Addition on bit vectors here is slightly funky. It’s a majority vote (1 + 1 gives you 1, 0 + 0 gives you 0), and otherwise you pick randomly. There are other ways to do it, but that’s why there’s a random number generator involved.

Whereas the result of multiplying of two vectors is dissimilar to either vector, addition produces a vector that is similar to them both.

You can use multiplication to query vectors. This is the fun part. Recall that multiplication is XOR and gives us both “binding” and “unbinding”, it means we can ask “what is the dollar of Mexico?”. Unbind the dollar and apply that to Mexico:

let mexico_dollar_query = 
   (dollar.product(&usa_currency)).product(&mexico_currency);

&hyperspace.label_for(&mexico_dollar_query)
// evaluates to "Peso"

Notice we didn’t have to extract or use the vector for “country” or “currency”. We Asked what role in Mexico is the dollar in the USA.

How does that work? If you multiply all the terms out, you end up with a vector which is “Peso” plus noise. As vectors in the store are orthogonal (because they are large and random), the lookup (label_for call) finds the closest vector to the one we queried, which is “Peso”.

The paper from Kanerva (below) cranks the handle of the maths to show that you end up with “Peso” and some noise:

Here’s a shorter example. Consider a different question: “what role does the dollar play in the USA?”. We unbind dollar from our representation of the USA, and see what we get:

= dollar x usa_currency // Query for the role of the dollar 
= dollar x (usa x country + dollar x currency) // Expand
= (dollar x usa x country) + (dollar x dollar x currency)    
= (dollar x usa x country) + currency

Note that (dollar x dollar) cancelled out, and we end up with some noise plus currency. I say noise as there’s nothing in the hyperspace for the “dollar x usa x country” binding.  The closest thing will be the remaining term, namely “Currency”.

You can read more about this in:

• Kanerva, P. Hyperdimensional Computing: An Introduction to Computing in Distributed Representation with High-Dimensional Random Vectors. Cogn Comput1, 139–159 (2009)
• In a presentation by Kanerva, Computing with High-dimensional vectors.
• And generally at: https://www.hd-computing.com

That’s my first toe into this area. I was delighted to find a Clojure talk by 

Carin Meier was right up my street. She implemented a variation using -1 and 1 as the bits.

https://youtu.be/j7ygjfbBJD0