Tutorial 1: Basic operations of vector symbolic algebra

Tutorial 1: Basic operations of vector symbolic algebra#

Week 2, Day 2: Neuro-Symbolic Methods

By Neuromatch Academy

Content creators: P. Michael Furlong, Chris Eliasmith

Content reviewers: Hlib Solodzhuk, Patrick Mineault, Aakash Agrawal, Alish Dipani, Hossein Rezaei, Yousef Ghanbari, Mostafa Abdollahi

Production editors: Konstantine Tsafatinos, Ella Batty, Spiros Chavlis, Samuele Bolotta, Hlib Solodzhuk

Tutorial Objectives#

Estimated timing of tutorial: 1 hour

In this tutorial we will introduce vector symbolic algebra and discuss its main operations.

Setup#

Install and import feedback gadget#

Notice that exactly the neuromatch branch of sspspace should be installed! Otherwise, some of the functionality won’t work.

Install dependencies#

Imports#

Figure settings#

Plotting functions#

Show code cell source Hide code cell source

# @title Plotting functions

def plot_vectors(concepts, labels, shape = (32, 32)):
    """
    Plot vector symbols associated with the given concepts.

    Inputs:
    - concepts (list of sspspace.ssp.SSP): list of concepts which contain associated vectors.
    - labels (list of str): list of strings which represent concepts.
    - shape (tuple, default = (32, 32)): desired image shape.
    """
    with plt.xkcd():
        n = len(concepts)
        for i in range(len(concepts)):
            plt.subplot(1,n,i+1)
            plt.imshow(concepts[i].view(dtype=float,type=np.ndarray).reshape(shape), cmap='Greys')
            plt.xticks([])
            plt.yticks([])
            plt.title(labels[i])

def plot_similarity_matrix(sim_mat, labels, values = False):
    """
    Plot the similarity matrix between vectors.

    Inputs:
    - sim_mat (numpy.ndarray): similarity matrix between vectors.
    - labels (list of str): list of strings which represent concepts.
    - values (bool): True if we would like to plot values of similarity too.
    """
    with plt.xkcd():
        plt.imshow(sim_mat, cmap='Greys')
        plt.colorbar()
        plt.xticks(np.arange(len(labels)), labels, rotation=45, ha="right", rotation_mode="anchor")
        plt.yticks(np.arange(len(labels)), labels)
        if values:
            for x in range(sim_mat.shape[1]):
                for y in range(sim_mat.shape[0]):
                    plt.text(x, y, f"{sim_mat[y, x]:.2f}", fontsize = 8, ha="center", va="center", color="green")
        plt.title('Similarity between vector-symbols')
        plt.xlabel('Symbols')
        plt.ylabel('Symbols')
        plt.show()

def plot_line_similarity_matrix(sim_mat, xaxis_ticks, multiple_objects = True, labels = None, title = "Awesome title!"):
    """
    Plot similarirty matrix (or vector if multiple_objects is False) as lines.

    Inputs:
    - sim_mat (numpy.ndarray): similarity matrix between vectors.
    - xaxis_ticks (list): list of ticks to put in x-axis.
    - multiple_objects (bool, default = True): True if there are a couple of objects to plot similarity.
    - labels (list, default = None): labels to plot.
    - title (str): title of the plot.
    """
    with plt.xkcd():
        if multiple_objects:
            for idx, integer_sims in enumerate(sim_mat):
                if labels:
                    plt.plot(xaxis_ticks, integer_sims.flatten(), label=f'$\phi$[{idx+1}]', marker='o', ls='--')
                else:
                    plt.plot(xaxis_ticks, integer_sims.flatten(), marker='o', ls='--')
        else:
            plt.plot(xaxis_ticks,sim_mat.flatten(), ls='--',marker='o')

    plt.ylabel('Similarity')
    plt.xlabel('n')
    plt.xticks(xaxis_ticks)
    if labels:
        plt.legend(loc='upper right')
    plt.title(title)
    plt.show()

def plot_double_line_similarity_matrix(sim_mat, xaxis_ticks, labels, title):
    """
    Plot similarirty matrix (or vector if multiple_objects is False) as lines for two different matrices.

    Inputs:
    - sim_mat (numpy.ndarray): list of similarity matrix between vectors.
    - xaxis_ticks (list): list of ticks to put in x-axis.
    - multiple_objects (bool, default = True): True if there are a couple of objects to plot similarity.
    - labels (list): labels to plot.
    - title (str): title of the plot.
    """
    with plt.xkcd():
        plt.plot(xaxis_ticks,sim_mat[0].flatten(), ls='--',marker='o', label = labels[0])
        plt.plot(xaxis_ticks,sim_mat[1].flatten(), ls='--',marker='o', label = labels[1])
    plt.ylabel('Similarity')
    plt.xlabel('n')
    plt.xticks(xaxis_ticks)
    plt.legend(loc='upper right')
    plt.title(title)
    plt.show()

def plot_real_valued_line_similarity(sim_mat, x_range, title):
    """
    Inputs:
    - sim_mat (numpy.ndarray): similarity matrix between vectors.
    - x_range (numpy.ndarray): x-axis range.
    - title (str): title of the plot.
    """
    with plt.xkcd():
        plt.plot(x_range, sim_mat)
    plt.xlabel('x')
    plt.ylabel('Similarity')
    plt.title(title)

Set random seed#

Helper functions#

Show code cell source Hide code cell source

# @title Helper functions

# mainly contains solutions to exercises for correct plot output; please don't take a look!
set_seed(42)

vector_length = 1024
symbol_names = ['circle','square','triangle']
discrete_space = sspspace.DiscreteSPSpace(symbol_names, ssp_dim=vector_length, optimize = False)

circle = discrete_space.encode('circle')
square = discrete_space.encode('square')
triangle = discrete_space.encode('triangle')

shape = (circle + square + triangle).normalize()

shape_sim_mat = np.zeros((4,4))

shape_sim_mat[0,0] = (circle | circle).item()
shape_sim_mat[1,1] = (square | square).item()
shape_sim_mat[2,2] = (triangle | triangle).item()
shape_sim_mat[3,3] = (shape | shape).item()

shape_sim_mat[0,1] = shape_sim_mat[1,0] = (circle | square).item()
shape_sim_mat[0,2] = shape_sim_mat[2,0] = (circle | triangle).item()
shape_sim_mat[0,3] = shape_sim_mat[3,0] = (circle | shape).item()

shape_sim_mat[1,2] = shape_sim_mat[2,1] = (square | triangle).item()
shape_sim_mat[1,3] = shape_sim_mat[3,1] = (square | shape).item()

shape_sim_mat[2,3] = shape_sim_mat[3,2] = (triangle | shape).item()

new_symbol_names = ['circle','square','triangle', 'red', 'blue', 'green']
new_discrete_space = sspspace.DiscreteSPSpace(new_symbol_names, ssp_dim=vector_length, optimize=False)

objs = {n:new_discrete_space.encode(np.array([n])) for n in new_symbol_names}

objs['red*circle'] = objs['red'] * objs['circle']
objs['blue*triangle'] = objs['blue'] * objs['triangle']
objs['green*square'] = objs['green'] * objs['square']

new_object_names = ['red','red^','red*circle','circle','circle^']
new_objs = objs.copy()

new_objs['red^'] = new_objs['red*circle'] * ~new_objs['circle']
new_objs['circle^'] = new_objs['red*circle'] * ~new_objs['red']

axis_vectors = ['one']

encoder = sspspace.DiscreteSPSpace(axis_vectors, ssp_dim=1024, optimize=False)

vocab = {w:encoder.encode(w) for w in axis_vectors}

integers = [vocab['one']]

max_int = 5
for i in range(2, max_int + 1):
    integers.append(integers[-1] * vocab['one'])

integers = np.array(integers).squeeze()
integer_sims = integers @ integers.T

five_unbind_two = sspspace.SSP(integers[4]) * ~sspspace.SSP(integers[1])
five_unbind_two_sims = five_unbind_two @ integers.T

new_encoder = sspspace.RandomSSPSpace(domain_dim=1, ssp_dim=1024)

xs = np.linspace(-4,4,401)[:,None]
phis = new_encoder.encode(xs)

real_line_sims = phis[200, :] @ phis.T

phi_shifted = phis[200,:][None,:] * new_encoder.encode([[np.pi/2]])
shifted_real_line_sims = phi_shifted.flatten() @ phis.T

Section 1: High-dimensional vector symbols#

In this section, we are going to start our journey by representing concepts as high-dimensional vectors.

Video 1: Similarity#

Submit your feedback#

Coding Exercise 1: Concepts as High-Dimensional Vectors#

In an arbitrary space of concepts, we will represent the ideas of ‘circle,’ ‘square,’ and triangle.’ For that, we will use the SSP space library (sspspace) to map identifiers for the concepts (strings of their names in this case) into high-dimensional vectors of unit length. It means that for each name, we will uniquely identify \(\mathbf{v}\) where \(||\mathbf{v}|| = 1\).

In this exercise, check that, indeed, vectors are of unit length.

###################################################################
## Fill out the following then remove
raise NotImplementedError("Student exercise: complete check that norms of the vector representations are of unit lengths.")
###################################################################

set_seed(42)

vector_length = 1024
symbol_names = ['circle','square','triangle']
discrete_space = sspspace.DiscreteSPSpace(symbol_names, ssp_dim=vector_length, optimize = False)

circle = discrete_space.encode('circle')
square = discrete_space.encode('square')
triangle = discrete_space.encode('triangle')

print('|circle| =', np.linalg.norm(circle))
print('|triangle| =', np.linalg.norm(...))
print('|square| =', ...)

Click for solution

We can visualize the assigned vectors as 32x32 images (notice that the dimension is 1024; it is exactly 32 multiplied by 32).

plot_vectors([circle, square, triangle], symbol_names)

../../../_images/8bc7e2c9ee5c7c188484b0df49a0363a4eb7d87ef48a4da225ac0e7541e3bbfb.png

As vectors are assigned randomly, the images do not display any meaningful structure.

One of the most useful properties of random high-dimensional vectors is that they are approximately orthogonal. This is an important aspect for vector symbolic algebras (VSAs) since we will use the vector dot product to measure similarity between objects encoded as random, high-dimensional vectors.

Discrete objects are either the same or different, so we expect similarity would be either 1 (the same) or 0 (not the same). Given how we select the vectors that represent discrete symbols if they are the same, they will have the dot product of 1, and if they are different concepts, then they will have a dot product of (approximately) 0.

Below, we use the | operator to indicate similarity. This is borrowed from the bra-ket notation in physics, i.e.,

\[ \mathbf{a}\cdot\mathbf{b} = \langle \mathbf{a} \mid \mathbf{b}\rangle \]

Notice that this operator | is the dot product under the hood.

concepts_sim_mat = np.zeros((3,3))

concepts_sim_mat[0,0] = (circle | circle).item()
concepts_sim_mat[1,1] = (square | square).item()
concepts_sim_mat[2,2] = (triangle | triangle).item()

concepts_sim_mat[0,1] = concepts_sim_mat[1,0] = (circle | square).item()
concepts_sim_mat[0,2] = concepts_sim_mat[2,0] = (circle | triangle).item()
concepts_sim_mat[1,2] = concepts_sim_mat[2,1] = (square | triangle).item()

plot_similarity_matrix(concepts_sim_mat, symbol_names)

../../../_images/d97c9c79b7e13b959242bf3ab1570a6819058e47d5d5da1e369657bc9a0e719e.png

As you can see from the above figure, the three randomly selected vectors are approximately orthogonal. This will be important later when we go to make more complicated objects from our vectors.

Submit your feedback#

Section 2: Bundling#

Estimated timing to here from start of tutorial: 10 minutes

In this section, we are going to explore the bundling operation, which allows us to construct vectors that represent something like sets. Basically, we combine two vectors into a new one that retains similarity to the previous two. We implement bundling using vector addition.

Video 2: Bundling#

Submit your feedback#

Coding Exercise 2: A Composite Object - Shape#

Let’s start with our previous example of different shapes (circle, square, and triangle) and use them to create a new object, ‘shape,’ which will represent all the atomic concepts we’ve introduced.

shape = (circle + square + triangle).normalize()

Notice that we need to normalize the obtained vector. Now, let us calculate the similarity matrix for the three default concepts and the new one.

In the exercise below, complete the similarity matrix calculation.

###################################################################
## Fill out the following then remove
raise NotImplementedError("Student exercise: complete calcualtion of similarity matrix.")
###################################################################

shape_sim_mat = np.zeros((4,4))

shape_sim_mat[0,0] = (circle | circle).item()
shape_sim_mat[1,1] = (square | square).item()
shape_sim_mat[2,2] = (triangle | ...).item()
shape_sim_mat[3,3] = (shape | ...).item()

shape_sim_mat[0,1] = shape_sim_mat[1,0] = (circle | square).item()
shape_sim_mat[0,2] = shape_sim_mat[2,0] = (circle | triangle).item()
shape_sim_mat[0,3] = shape_sim_mat[3,0] = (circle | shape).item()

shape_sim_mat[1,2] = shape_sim_mat[2,1] = (square | triangle).item()
shape_sim_mat[1,3] = shape_sim_mat[3,1] = (square | shape).item()

shape_sim_mat[2,3] = shape_sim_mat[3,2] = (... | ...).item()

Click for solution

plot_similarity_matrix(shape_sim_mat, symbol_names + ["shape"], values = True)

../../../_images/832c476f0989760e84ddfefb1deefe474d0d0dac911fb34446ab5c01865565dd.png

Observe that as each of the basic concepts was included equally in the definition of the ‘shape’ symbol, it has the same similarity between all other vectors, pairwise.

Coding Exercise 2 Discussion#

Why do we need to normalize the vector obtained as a result of the bundling operation? What length do you expect to receive without normalization?

Click for solution

Submit your feedback#

Section 3: Binding & Unbinding#

Estimated timing to here from start of tutorial: 20 minutes

In this section, we will talk about binding, an operation that takes two vectors and produces a new vector that is not similar to either of its constituent elements.

Binding and unbinding are implemented using circular convolution. Luckily, that is implemented for you inside the SSPSpace library. If you would like a refresher on convolution, this Three Blue One Brown video is a good place to start.

Video 3: Binding#

Submit your feedback#

Coding Exercise 3: Colorful Shapes#

We can think of binding as an “and”-like operation. Both arguments need to be the same to produce a similar vector. In this example, let’s think about colors and shapes:

set_seed(42)

new_symbol_names = ['circle','square','triangle', 'red', 'blue', 'green']
new_discrete_space = sspspace.DiscreteSPSpace(new_symbol_names, ssp_dim=vector_length, optimize=False)

objs = {n:new_discrete_space.encode(np.array([n])) for n in new_symbol_names}

Now, we are going to take two of the objects to make new ones: a red circle, a blue triangle, and a green square.

We will combine the two primitive objects using the binding operation, which for us is implemented using circular convolution, and we denote it by

\[\begin{align*} a \circledast b \end{align*}\]

Mathematical details

The circular convolution of two vectors \(\mathbf{a}\) and \(\mathbf{b} \in \mathbb{R}^N\) is defined as:

\[c_j = a \circledast b = \sum_{k=1}^{N} a_k b_{1 + (j-k) \mod N}\]

where \(N\) is the length of the vectors, and \(j\) is the index of the output vector. It’s often more convenient to calculate the circular convolution in the Fourier domain. The circular convolution is equivalent to the element-wise product of the Fourier transforms of the two vectors, followed by an inverse Fourier transform:

\[a \circledast b = \mathcal{F}^{-1}(\mathcal{F}(\mathbf{a}) \odot \mathcal{F}(\mathbf{b}))\]

where \(\mathcal{F}\) is the Fourier transform, \(\odot\) is the element-wise product, and \(\mathcal{F}^{-1}\) is the inverse Fourier transform. The equivalence between these two formulations is a consequence of the convolution theorem.

In the cell below, complete the missing concepts and then observe the computed similarity matrix.

###################################################################
## Fill out the following then remove
raise NotImplementedError("Student exercise: complete derivation of new objects using binding operation.")
###################################################################

objs['red*circle'] = objs['red'] * objs['circle']
objs['blue*triangle'] = ... * objs['triangle']
objs['green*square'] = objs['green'] * ...

Click for solution

Notice how we iterate through all objects in object_names and calculate pairwise dot products (similarity metric).

object_names = list(objs.keys())
obj_sims = np.zeros((len(object_names), len(object_names)))

for name_idx, name in enumerate(object_names):
    for other_idx in range(name_idx, len(object_names)):
        obj_sims[name_idx, other_idx] = obj_sims[other_idx, name_idx] = (objs[name] | objs[object_names[other_idx]]).item()

plot_similarity_matrix(obj_sims, object_names)

../../../_images/fcd1bb9b909ccfba3cea505894753911bd3e1b2d157bf6e426b5f1432cbb8f74.png

As you can see here, not only do the shapes and colors have no similarity, but the compound objects also have no similarity with either of their constituent elements - green * square is not similar to either green or square.

Submit your feedback#

Coding Exercise 4: Foundations of Colorful Shapes#

Video 4: Unbinding#

Submit your feedback#

We can also undo the binding operation, which we call unbinding. It is implemented by binding with the pseudo-inverse of the vector we wish to unbind. We denote the pseudo-inverse of the vector using the ~ symbol.

The SSPSpace library implements the pseudo-inverse for you, but the pseudo-inverse of a vector \(\mathbf{x} = (x_{0},\ldots, x_{d-1})\) is defined:

\[\sim\mathbf{x} = \left(x_{0},x_{d-1},x_{d-2},\ldots,x_{1}\right)\]

Consider the example of our red circle. If we want to recover the shape of the object, we will unbind from it the color:

\[ (\mathtt{red} \circledast \mathtt{circle}) \circledast \sim \mathtt{red} \approx \mathtt{circle} \]

Mathematical details

By the definition of the pseudo-inverse and circular convolution, we have:

\[\mathbf{x} \, \circledast \sim \mathbf{x} = \sum_{k=1}^{N} x_k x_{1 + (j + k - 2) \mod N} \approx \delta_j\]

where \(\delta_j\) is the Kronecker delta function. This is:

exactly equal to 1 when \(j=1\). This is because the vectors in SSP have a norm of 1.
approximately 0 otherwise. This is because the vectors in SSP are random, and so a vector is approximately orthogonal to a shifted version of itself.

The Kronecker delta is the identity function for the circular convolution, and circular convolutions commute, hence:

\[ (\mathtt{a} \circledast \mathtt{b}) \circledast \sim \mathtt{a} = \mathtt{b} \circledast (\mathtt{a} \circledast \sim \mathtt{a}) \approx \mathtt{b} \circledast \delta = \mathtt{b} \]

In the cell below, unbind the color and shape, and then observe the similarity matrix.

new_object_names = ['red','red^','red*circle','circle','circle^']
new_objs = objs

###################################################################
## Fill out the following then remove
raise NotImplementedError("Student exercise: complete derivation of default objects using pseudoinverse.")
###################################################################

new_objs['red^'] = new_objs['red*circle'] * ~new_objs['circle']
new_objs['circle^'] = new_objs[...] * ~new_objs[...]

new_obj_sims = np.zeros((len(new_object_names), len(new_object_names)))

for name_idx, name in enumerate(new_object_names):
    for other_idx in range(name_idx, len(new_object_names)):
        new_obj_sims[name_idx, other_idx] = new_obj_sims[other_idx, name_idx] = (new_objs[name] | new_objs[new_object_names[other_idx]]).item()

plot_similarity_matrix(new_obj_sims, new_object_names, values = True)

Click for solution

Example output:

Looking at the above graph, we can see that the compound red circle object is not similar to either of the elements, but the circle and the unbound circle are similar to one another, and the red and unbound red objects are similar to one another.

With these elements together, we have constructed the basic tools we need to construct complex objects in vector symbolic algebra.

Submit your feedback#

Section 4: Cleanup#

Estimated timing to here from start of tutorial: 30 minutes

In this section we will address the issue of vectors being corrupted with noise.

Video 5: Cleanup#

Submit your feedback#

Coding Exercise 5: Cleanup Memories To Find The Best-Fit#

In the process of computing with VSAs, the vectors themselves can become corrupted due to noise, because we implement these systems with spiking neurons, or due to approximations like using the pseudo-inverse for unbinding, or because noise gets added when we operate on complex structures.

To address this problem, we employ “cleanup memories.” These are lots of ways to implement these systems, but today, we’re going to do it with a single hidden layer neural network. Let’s start with a sequence of symbols, say \(\texttt{fire-fighter},\texttt{math-teacher},\texttt{sales-manager},\) and so on, in that fashion, and create a new vector that is a corrupted combination of all three. We will then use a cleanup memory to find the best-fitting vector in our vocabulary.

In the cell below, you will see the definition of noisy_vector, your task is to complete the calculation of similarity values for this vector and all default ones.

Here, we introduce another graphical way to represent the similarity: by putting a similarity value on the y-axis (instead of the box in the grid) and representing each of the objects by line (the x-axis stays the same, and similarity takes place between the corresponding label on the x-axis and line-object).

###################################################################
## Fill out the following then remove
raise NotImplementedError("Student exercise: complete similarities calculation between noisy vector and given symbols.")
###################################################################
set_seed(42)

symbol_names = ['fire-fighter','math-teacher','sales-manager']
discrete_space = sspspace.DiscreteSPSpace(symbol_names, ssp_dim=1024, optimize=False)

vocab = {n:discrete_space.encode(n) for n in symbol_names}

noisy_vector = 0.2 * vocab['fire-fighter'] + 0.15 * vocab['math-teacher'] + 0.3 * vocab['sales-manager']

sims = np.array([noisy_vector | vocab[...] for name in ...]).squeeze()

plot_line_similarity_matrix(sims, symbol_names, multiple_objects = False, title = 'Similarity - pre cleanup')

Click for solution

Example output:

Conceptually, with a discrete vocabulary, we can clean up a vector by finding the reference vector that’s closest to the noisy vector and replacing it:

\[\text{cleanup}(\boldsymbol{x}) = \arg\max_{\boldsymbol{w} \in \text{vocab}} \boldsymbol{x} \cdot \boldsymbol{w}\]

Now, let’s construct a simple one-hidden layer neural network that does cleanup using a soft version of this operation, replacing the max operation with a softmax. The input weights will be the vectors in the vocabulary, and we will place a softmax function on the hidden layer. The output weights will again be the vectors representing the symbols in the vocabulary.

To snap the corrupted vectors back to the vocabulary, we’ll apply this operation:

\[\text{cleanup}(\boldsymbol{x}) = \text{softmax}(T \cdot \boldsymbol{x} \boldsymbol{W}^T) \boldsymbol{W}\]

Where \(T\) is the temperature parameter, and \(\boldsymbol{W}\) is the matrix of vectors in the vocabulary. As \(T \to \infty\), this operation converges to the original hard max cleanup operation. Your task is to complete the __call__ function. Then, we calculate the similarity between the obtained vector and the ones in the vocabulary.

Observe the result and compare it to the pre-cleanup metrics.

###################################################################
## Fill out the following then remove
raise NotImplementedError("Student exercise: complete Cleanup class.")
###################################################################

set_seed(42)

class Cleanup:
    def __init__(self, vocab, temperature=1e5):
        self.weights = np.array([vocab[k] for k in vocab.keys()]).squeeze()
        self.temp = temperature
    def __call__(self, x):
        ###################################################################
        ## Fill out the following then remove
        raise NotImplementedError("Student exercise: complete similarity calculation between input vector and weights of the network.")
        ###################################################################
        sims = ...
        max_sim = softmax(sims * self.temp, axis=1)
        return sspspace.SSP(...) #sspspace.SSP() wrapper is necessary for further bitwise comparison, it doesn't change the result vector


cleanup = Cleanup(vocab)

clean_vector = cleanup(noisy_vector)

clean_sims = np.array([clean_vector | vocab[name] for name in symbol_names]).squeeze()

plot_double_line_similarity_matrix([sims, clean_sims], symbol_names, ['Noisy Similarity', 'Clean Similarity'], title = 'Similarity - post cleanup')

Click for solution

Example output:

For the scenario where we have a discrete, known vocabulary, we can do this cleanup with a single feed-forward network, and we don’t need to learn any of the synaptic weights.

Submit your feedback#

Section 5: Iterated Binding#

Estimated timing to here from start of tutorial: 45 minutes

In this section, we will represent numbers with iterated binding.

Video 6: Iterated Binding#

Submit your feedback#

Coding Exercise 6: Representing Numbers#

It is often useful to be able to represent numbers. For example, we may want to represent the position of an object in a list, or we may want to represent the coordinates of an object in a grid. To do this, we use the binding operator to construct a vector that represents a number. We start by picking what we refer to as an “axis vector,” let’s call it \(\texttt{one}\), and then iteratively apply binding like this:

\[ \texttt{two} = \texttt{one}\circledast\texttt{one} \]

\[ \texttt{three} = \texttt{two}\circledast\texttt{one} = \texttt{one}\circledast\texttt{one}\circledast\texttt{one} \]

and so on. We extend that to arbitrary integers, \(n\), by writing:

\[ \phi[n] = \underset{i=1}{\overset{n}{\circledast}}\texttt{one} \]

Let’s try that now and see how similarity between iteratively bound vectors develops. In the cell below, you should complete the missing part, which implements the iterative binding mechanism.

###################################################################
## Fill out the following then remove
raise NotImplementedError("Student exercise: complete iterated binding.")
###################################################################

set_seed(42)

#define axis vector
axis_vectors = ['one']

encoder = sspspace.DiscreteSPSpace(axis_vectors, ssp_dim=1024, optimize=False)

#vocabulary
vocab = {w:encoder.encode(w) for w in axis_vectors}

#we will add new vectors to this list
integers = [vocab['one']]

max_int = 5
for i in range(2, max_int + 1):
    #bind one more "one" to the previous integer to get the new one
    integers.append(integers[-1] * vocab[...])

Click for solution

Now, we will observe the similarity metric between the obtained vectors.

integers = np.array(integers).squeeze()
integer_sims = integers @ integers.T

plot_similarity_matrix(integer_sims, [i for i in range(1, 6)], values = True)

../../../_images/725a84630e948ce304af59053a5abb69bfa0e99474221ed9fb9d83fa6947e6e0.png

Here, we will take a look at another graphical representation of the similarity through lines (the only difference with the previous section is the fact that here, we will have a couple of them, each representing a distinct concept).

plot_line_similarity_matrix(integer_sims, range(1, 6), multiple_objects = True, labels = [f'$\phi$[{idx+1}]' for idx in range(5)], title = "Similarity for digits")

../../../_images/8ef7658b90fc2f80457ec819b41a88890701f0071b1578956acbdaffbc6a327e.png

What we can see here is that each number acts like its own vector; they are highly dissimilar, but we can still do arithmetic with them. Let’s see what happens when we unbind \(\texttt{two}\) from \(\texttt{five}\).

In the cell below you are invited to complete the missing parts (be attentive! python is zero-indexed, thus you need to choose the correct indices).

###################################################################
## Fill out the following then remove
raise NotImplementedError("Student exercise: unbinding of two from five.")
###################################################################

five_unbind_two = sspspace.SSP(integers[...]) * ~sspspace.SSP(integers[...])
five_unbind_two_sims = five_unbind_two @ integers.T

Click for solution

plot_line_similarity_matrix(five_unbind_two_sims, range(1, 6), multiple_objects = False,  title = '$(\phi[5]\circledast \phi[2]^{-1}) \cdot \phi[n]$')

../../../_images/440b83782794d22bcffc10d4bcb05b6fa6dff76473317e26fb65037a9c890d17.png

We get what we expected - when we removed \(\texttt{two}\) from \(\texttt{five}\) we get a vector that is similar to \(\texttt{three}\). We can do arithmetic with our vector encoding!

Submit your feedback#

Coding Exercise 7: Beyond Binding Integers#

Video 7: Fractional Binding#

Submit your feedback#

This is all well and good, but sometimes, we want to encode values that are not integers. Is there an easy way to do this? You’ll be surprised to learn that the answer is: yes.

We actually use the same technique, but we recognize that iterated binding can be implemented in the Fourier domain:

\[ \phi[n] = \mathcal{F}^{-1}\left\{\mathcal{F}\left\{\texttt{one}\right\}^{n}\right\} \]

where the power of \(n\) in the Fourier domain is applied element-wise to the vector. To encode real-valued data, we simply let the integer value, \(n\), be a real-valued vector, \(x\), and we let the axis vector be a randomly generated vector, \(X\).

\[ \phi(x) = \mathcal{F}^{-1}\left\{\mathcal{F}\left\{X\right\}^{x}\right\} \]

We call vectors that represent real-valued data Spatial Semantic Pointers (SSPs). We can also extend this to multi-dimensional data by binding different SSPs together.

\[ \phi(x,y) = \phi_{X}(x) \circledast \phi_{Y}(y) \]

In the \(\texttt{sspspace}\) library, we provide an encoder for real- and integer-valued data, and we’ll demonstrate it next by encoding a bunch of points in the range \([-4,4]\) and comparing their value to \(0\), encoded with SSP.

In the cell below, you should complete the similarity calculation by injecting the correct index for the \(0\) element (observe that it is right in the middle of the encoded array).

###################################################################
## Fill out the following then remove
raise NotImplementedError("Student exercise: complete similarity calculation: correct index for `0` and array.")
###################################################################

set_seed(42)
new_encoder = sspspace.RandomSSPSpace(domain_dim=1, ssp_dim=1024)

xs = np.linspace(-4,4,401)[:,None] #we expect the encoded values to be two-dimensional in `encoder.encode()` so we add extra dimension
phis = new_encoder.encode(xs)

#`0` element is right in the middle of phis array! notice that we have 401 samples inside it
real_line_sims = phis[..., :] @ phis.T

Click for solution

plot_real_valued_line_similarity(real_line_sims, xs, title = '$\phi(x)\cdot\phi(0)$')

../../../_images/610fbde31f945b794478e6d300e4d9403ffb637b3e4684d123a1569facc9d825.png

As with the integers, we can update the values post-encoding through the binding operation. Let’s look at the similarity between all the points in the range \([-4,4]\), this time with the value \(\pi/2\), but we will shift it by binding the origin with the desired shift value.

In the cell below, you need to provide the value for which we are going to shift the origin.

###################################################################
## Fill out the following then remove
raise NotImplementedError("Student exercise: provide value to shift and observe the usage of the operation.")
###################################################################

phi_shifted = phis[200,:][None,:] * new_encoder.encode([[...]])
shifted_real_line_sims = phi_shifted.flatten() @ phis.T

Click for solution

plot_real_valued_line_similarity(shifted_real_line_sims, xs, title = '$\phi(x)\cdot(\phi(0)\circledast\phi(\pi/2))$')

../../../_images/b9827ab2ba706b45b58b3aba82c45fcc70d241758cc93672643bb4ac4774f56c.png

We can then take that vector and shift it again to a new location.

new_phi_shifted = phis[200,:][None,:] * new_encoder.encode([[-1.5*np.pi]])
new_shifted_real_line_sims = new_phi_shifted.flatten() @ phis.T

plot_real_valued_line_similarity(new_shifted_real_line_sims, xs, title = '$\phi(x)\cdot(\phi(0)\circledast\phi(-1.5\pi))$')

../../../_images/7f3b140b61fc9482b18809179a6773472e8a7efa8ee0346622572893a2071b98.png

We will go on to use these encodings to build spatial maps in Tutorial 3.

Coding Exercise 7 Discussion#

How would you explain the lines sims = vector @ phis.T in the previous coding exercises?

Click for solution

Submit your feedback#

Video 8: Iterated Binding Conclusion#

Submit your feedback#

Summary#

Estimated timing of tutorial: 1 hour

In this tutorial, we developed the toolbox of the main operations on the vector symbolic algebra. In particular, it includes:

similarity operation (|), which measures how similar the two vectors are (by calculating their dot product);
bundling (+), which creates new set-like objects using vector addition;
binding (\(\circledast\)), which creates a new combined representation of the two given objects using circular convolution;
unbinding (~), which allows to derive a pure object from the bound representation by unbinding another one that stands in the pair;
cleanup, which tries to identify the most similar vector in the vocabulary with multiple possible implementations.
iterated binding, which allows one to “count” by iteratively binding an axis vector with itself.
encoding real-valued data using fractional binding.

In the following tutorials, we will take a look at how we can use these tools to create more complicated structures and derive useful information from them.

Tutorial 1: Basic operations of vector symbolic algebra

Contents

Tutorial 1: Basic operations of vector symbolic algebra#

Tutorial Objectives#

Setup#

Install and import feedback gadget#

Install dependencies#

Imports#

Figure settings#

Plotting functions#

Set random seed#

Helper functions#

Section 1: High-dimensional vector symbols#

Video 1: Similarity#

Submit your feedback#

Coding Exercise 1: Concepts as High-Dimensional Vectors#

Submit your feedback#

Section 2: Bundling#

Video 2: Bundling#

Submit your feedback#

Coding Exercise 2: A Composite Object - Shape#

Coding Exercise 2 Discussion#

Submit your feedback#

Section 3: Binding & Unbinding#

Video 3: Binding#

Submit your feedback#

Coding Exercise 3: Colorful Shapes#

Submit your feedback#

Coding Exercise 4: Foundations of Colorful Shapes#

Video 4: Unbinding#

Submit your feedback#

Submit your feedback#

Section 4: Cleanup#

Video 5: Cleanup#

Submit your feedback#

Coding Exercise 5: Cleanup Memories To Find The Best-Fit#

Submit your feedback#

Section 5: Iterated Binding#

Video 6: Iterated Binding#

Submit your feedback#

Coding Exercise 6: Representing Numbers#

Submit your feedback#

Coding Exercise 7: Beyond Binding Integers#

Video 7: Fractional Binding#

Submit your feedback#

Coding Exercise 7 Discussion#

Submit your feedback#

Video 8: Iterated Binding Conclusion#

Submit your feedback#

Summary#