252-ps6

Computer Science 252
Neural Networks

Assignment 6: Vector Symbolic Architectures

Objectives

    1. Enhance our understanding of VSA by implementing the “Dollar of Mexico” analogy example from Kanerva (2008).
    2. Understand the use of permutation to implement sequencing.

As I mentioned in class, we will use Ross Gayler’s Multiply/Add/Permute flavor of VSA, which is extremely simple to implement in NumPy.

Part 1: Getting started

To get started, create a script vsa.py containing a little function randvec that accepts a vector size n and uses numpy.random.random_integers to return a vector of n random values that are either -1 or +1. (As we’ve done before, you can do this by generating 0s and 1s, then multiplying by 2 and subtracting 1). I tested mine thus:

>>> from vsa import randvec
>>> randvec(10)
array([-1, -1,  1,  1, -1, -1, -1, -1, -1, -1])
>>> randvec(10)
array([ 1,  1, -1, -1, -1,  1,  1, -1, -1, -1])
>>> randvec(10)
array([-1, -1, -1, -1,  1, -1, -1,  1,  1,  1])

Next, you can copy/paste your vector cosine function from the previous (LSA) assignment, to validate that the MAP architecture works as advertised:

>>> from vsa import randvec, cosine
>>> a = randvec(1000)
>>> b = randvec(1000)
>>> c = randvec(1000)
>>> d = randvec(1000)
>>> x = a*b + c*d # Associate A with B and C with D
>>> y = c * x     # Probe the association vector with C; answer should be D
>>> cosine(y, a)
-0.03508232077228117
>>> cosine(y, b)
-0.052623481158421748
>>> cosine(y, c)
-0.029235267310234306
>>> cosine(y, d)
0.68410525505948272

As you can see, the query worked as expected: when we query the association vector X with the probe C, we get a result vector Y that is highly correlated with the vector D and has a very small, negative correlation with the other vectors.

Part 2: Creating a test framework

Although it is nice to see that VSA works as advertised so far, testing it by hand like this is obviously pretty time-consuming. So you should now create a class VSA that will automate much of this process. This class should have:

    • a constructor accepting the vector size n
    • a method to create a random vector with a name you specify as a string
    • a method to return the name of the “winner” (most likely) vector in a query

Here is the same example, but using the testing class:

>>> from vsa import VSA
>>> vsa = VSA(1000)
>>> a = vsa.randvec('A')
>>> b = vsa.randvec('B')
>>> c = vsa.randvec('C')
>>> d = vsa.randvec('D')
>>> x = a*b + c*d
>>> y = c*x
>>> vsa.winner(y)
'D'

All this is pretty easy to do if your VSA class maintains a dictionary of its vectors, keyed by their corresponding names. Then, given an input vector like y in the example, your winner method can just loop over the dictionary entries, returning the key of the entry whose vector that has the highest cosine with y.

Part 3: Solving analogies holistically with Multiply, Add

Now that you have a simple test framework, it will be easy to run Kanerva’s “Dollar of Mexico” example:

>>> vsa = VSA(10000) # Ten thousand elements, as per Kanerva (2008)
>>> nam = vsa.randvec('name')
>>> usa = vsa.randvec('USA')
>>> cap = vsa.randvec('capital')
>>> wdc = vsa.randvec('Washington, DC')
>>> mon = vsa.randvec('money')
>>> dol = vsa.randvec('dollar')
>>> mex = vsa.randvec('Mexico')
>>> mxc = vsa.randvec('Mexico City')
>>> pes = vsa.randvec('peso')
>>> ustates = nam*usa + cap*wdc + mon*dol
>>> mexico  = nam*mex + cap*mxc + mon*pes
>>> fum = ustates * mexico
>>> query = dol*fum
>>> vsa.winner(query)
'peso'

Part 4: Implementing permutation and inverse permutation

To complete our implementation of the Multiply/Add/Permute architecture, let’s add permutation and inverse permutation to our VSA class. This can be easily done using a call to numpy.random.permutation, which accepts an array size n and returns a permuted array of indices from 0 through n-1. Because we’ll want to use the same permutation indices every time, this call should be in the constructor for your VSA class, which will store the indices for future use in a permute method that you should also write. Because permutation must be invertible, you should also write a perminv method. A little googling (numpy permute inverse) will show you how to get the indices to invert the permutation. Here is a simple test I did to validate my permute and perminv methods. Note that perminv undoes the effects of permute, as desired:

>>> vsa = VSA(10)
>>> x = vsa.randvec('X')
>>> y = vsa.permute(x)
>>> x
array([ 1,  1,  1,  1,  1, -1, -1,  1,  1,  1])
>>> y
array([-1,  1,  1,  1,  1,  1,  1,  1,  1, -1])
>>> vsa.perminv(y)
array([ 1,  1,  1,  1,  1, -1, -1,  1,  1,  1])

Part 5: Encoding sequences via Permute

For the grand finale, let’s use our permute and perminv methods to encode and decode a sequence of symbols. As shown in slide #17 of the lecture notes, a sequence (list) of symbols can be encoded into a vector using the following algorithm:

    1. Start with a result vector of zeros.
    2. For each symbol in the sequence, last to first:
      1. Add the vector for this symbol to the current result vector
      2. Permute the result vector
    3. Return the result vector

So your next step should be to add a seqencode method to your VSA class. This method should accept a list of symbols, such as ['A', 'B', 'C'] and return a vector representing the encoding of that sequence.

Why does our loop go backwards over the sequence (step 2)? If you think about it, this encoding is a bit like a stack: the last symbol added will be at the “top” of the result vector. So to ensure that the first symbol in the sequence is the last one added, we loop over the sequence in reverse order.

To test your seqencode method, you’ll need to add a seqdecode method. This method should take a vector returned by seqencode and return the list of symbols encoded by that vector. Another look at Slide 17 of the lecture notes gives us the algorithm for this method:

    1. Start with an empty result list.
    2. Until the entire sequence has been decoded:
      1. Replace the vector by its inverse permutation
      2. Get the winning symbol for the vector and append this symbol to the result list
    3. Return the result list

So now you start writing seqdecode, and you run into a problem: in step 2, what does until the entire sequence is decodedmean? If all you’re given is the encoding vector, how do you know how many symbols it “contains”? I.e., how do you known when you’re done decoding?

Fortunately, the answer to this puzzle lies in the methods you have already written. Rather than giving you the answer, I’ll provide a hint: look again at the code inside the winner method you invoke in step 4 of the algorithm. If you are still puzzling over this after thinking about it for a while, ask me, and we’ll work it out together.

What to turn into github

All you need to turn in for this assignment is your vsa.py script. I will test it as shown in Parts 2, 3, and 5 above, using this script. So you don’t need to have a main in your own code for this assignment.

Extra-Credit Option

Add functions btencode and btdecode for encoding/decoding binary trees. To keep from decoding forever, you can assume a maximum depth.