Channels ▼

Jocelyn Paine

Dr. Dobb's Bloggers

Binary Holographic Reduced Representations in SWI-Prolog

August 25, 2008

It's a forbidding title: what is a "binary holographic reduced representation"? Answer: a lovely way to do analogical reasoning on information encoded as high-dimensional vectors. I've just put an implementation for Jan Wielemaker's SWI-Prolog which you can download from my Web site. In this posting, I'll explain about it and HRRs, ending with a session listing where you can see Prolog answering the question "What is the Paris of Sweden?"

My code implements the binary HRRs described in:

 The idea of HRRs is to represent symbolic information by high-dimensional vectors, and use these vectors for analogical reasoning. In real life, one would make this efficient by using special hardware; my Prolog implementation is not meant to be efficient, but only to demonstrate principles. There are several versions of HRR, developed by different researchers: because it was easy to implement, I decided to use the one from Kanerva's paper.

Vector functions, and some algebraic properties

In Kanerva's paper, and in my code, vectors are binary, each component being 0 or 1. The fundamental functions are:

  • ⊗;
  • merge;
  • clean;
  • dot.
There is also a function for generating random vectors, each component of which has an equal probability of being 0 or 1. Other versions of HRR have analogous functions.

To understand how HRRs work, you have to know their algebraic properties, and use these in simplifying "HRR equations". If you're not familiar with ideas such as commutativity and associativity, it doesn't matter — you can see HRRs at work by skipping to the Prolog session at the end of this post.

These are some important properties that I'll use later:

A ⊗ B = B ⊗ A.  <em>(⊗ is commutative.)</em>  
(A ⊗ B) ⊗ C = A ⊗ (B ⊗ C).  <em>(⊗ is associative.)</em>  
A ⊗ B ⊗ B = A. B ⊗ B ⊗ A = A.  <em>(⊗ is self-inverse.)</em>  
A ⊗ merge( B, C ) = merge( A ⊗ B, A ⊗ C ). <em>(⊗ distributes over merge.)</em> 

Using ⊗ to store a field in, and select it from, a record

With these in mind, suppose we have two vectors called paris and capital. We define a third vector:

france = capital ⊗ paris.  
Then:
capital ⊗ france = capital ⊗ capital ⊗ paris                  
                       = paris. 
By commutativity and associativity, france ⊗ capital is also paris.

The point is that we can regard france as a data structure with a capital field whose value is paris. (When I use these names, I mean the vectors they denote.) Then applying ⊗ to france and capital acts as a field selector, and extracts the value paris.

Symmetry between field selectors and fillers

The above reasoning would work the same way for paris ⊗ france, returning capital. Although I may want to treat capital as a field selector and paris as its value, nothing about the vectors themselves forces us to treat one as essentially different from the other. I shan't say much more about this symmetry, but it is an important point of HRR research.

Storing more than one field

Now suppose we have six vectors: capital, paris, location, we (standing for "Western Europe"), money, and euro. And let us now define france by a more complicated equation:

france = merge( capital ⊗ paris, location ⊗ we, money ⊗ euro ). 
You can see from the names that we're building a record structure.

Selecting when there is more than one field

What happens if we ⊗ with capital, as before? We get these equations. The second follows because ⊗ distributes over merge, and the third because ⊗ is self-inverse:

capital ⊗ france = capital ⊗ merge( capital ⊗ paris, location ⊗ we, money ⊗ euro ).                  
                      = merge( capital ⊗ capital ⊗ paris, capital ⊗ location ⊗ we, capital ⊗ money ⊗ euro ).                  
                      = merge( paris, capital ⊗ location ⊗ we, capital ⊗ money ⊗ euro ).  

Using dot product and "clean-up" to discard irrelevant data

This is interesting because there are more properties of the vector functions which are important.

First, we assume that A dot B, the vector dot-product, measures how similar A is to B. So if A dot B > A dot C, A is more like B than it is like C.

We also assume that our implementation has an "item memory" or "clean-up memory" that stores all vectors that act as symbols we shall want to recognise. In the above example, these would be capital, paris, location, we, money, and euro.

The point of the item memory is that in a real-life implementation in hardware, and given a vector V, we could very quickly test which vector in the memory V is most similar to. This is "clean up".

How similarity relates to ⊗ and merge

Now we need two more properties:

A ⊗ B is similar neither to A nor to B.  
A merge B is similar to A and to B. 

  So look back at the earlier equations:

capital ⊗ france = capital ⊗ merge( capital ⊗ paris, location ⊗ we, money ⊗ euro ).                  
                      = merge( capital ⊗ capital ⊗ paris, capital ⊗ location ⊗ we, capital ⊗ money ⊗ euro ).                  
                      = merge( paris, capital ⊗ location ⊗ we, capital ⊗ money ⊗ euro ).  
Because of the third line and the fact that merge( A, B ) is similar to both A and to B, capital ⊗ france is similar to paris, and to capital ⊗ location ⊗ we, and to capital ⊗ money ⊗ euro.

How this relates to the item memory

I said earlier that in this example, the item memory holds capital, paris, location, we, money, and euro.

Assume also that these six vectors have been randomly generated, so that they are extremely unlikely to be similar to one another. This is a crucial assumption, part of any HRR implementation. It is also why we use high-dimensional vectors: the higher the dimension, the more room there is for random vectors to be unlike one another.

Then if we search the item memory for capital ⊗ france, paris will be the most similar to it. The vectors capital ⊗ location ⊗ we and capital ⊗ money ⊗ euro are similar to capital ⊗ france too, but they're not in the item memory, so a search won't find them.

Analogical reasoning

By extending the example, we can do some interesting analogical reasoning. Let's introduce some new vectors:

sweden = merge( capital ⊗ stockholm, location ⊗ nwe, money ⊗ krona ). 
(I am using nwe to stand for North-West Europe.)

Now, what is

sweden ⊗ (france ⊗ paris) ? 

Well, france ⊗ paris is similar to capital, by the same reasoning as above. And then if we ⊗ that with sweden, and clean up the result, we should get stockholm. We have used HRRs to solve the analogy problem "what is the Paris of Sweden"? This is one of the examples in Kanerva's paper, and it's why researchers find HRRs so appealing: because of their promise for efficient analogical reasoning.

A session with HRRs in Prolog

The listing below shows a sample Prolog session with the predicates. It ends with two examples from Kanerva's paper: storing information about France, and answering the questions "what is the Paris of Sweden?" and "what is the Krona of France?" Note that for the ⊗ function, I use two names: bind, and probe. These do exactly the same as one another, but the names make it easier to see whether one is storing data in, or retrieving it from, a vector.

 In this listing, queries that I've typed begin with ?- and are in normal font. Output is also normal font, not starting with ?-. My comments are in italics. Devotees of SWI-Prolog will notice that I've removed a few pieces of output: the 'true' after some queries, and the query numbers.

Welcome to SWI-Prolog (Multi-threaded, 32 bits, Version 5.6.58) 
Copyright (c) 1990-2008 University of Amsterdam. 
SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software, 
and you are welcome to redistribute it under certain conditions. 
Please visit http://www.swi-prolog.org for details.
 
For help, use ?- help(Topic). or ?- apropos(Word).  
 
?- [paths]. 
% paths compiled 0.00 sec, 1,104 bytes true.  
<em>Loads search paths used by the modules when referring to other modules.</em>   
?- [hrr_vectors]. 
% hrr_vectors compiled into hrr_vectors 0.02 sec, 5,444 bytes true. 
<em>Loads the basic vector predicates.</em>  
?- [hrr_item_memory]. 
% hrr_item_memory compiled into hrr_item_memory 0.00 sec, 4,616 bytes true. 
<em>Loads predicates for handling the item memory.</em>  
?- [isv]. 
% isv compiled into isv 0.02 sec, 5,184 bytes true. 
<em>Loads the interactive evaluator.</em>
?- isv_assert_dimension(10000).
<em>Tell the system to use 10,000-dimensional vectors.</em> <br />
?- france isv capital bind paris. 
<em>Make a vector called france, equal to random</em>
<em>vector capital ⊗ random vector paris. </em><br />
?- X isv clean( france probe paris ).  <br />
X = capital-1.  
<em>Search the item memory for the closest</em>
<em>vector to france ⊗ paris. This</em>
<em>is capital, which has similarity 1 to</em>
<em>france ⊗ paris. I.e. it is the same</em>
<em>vector. </em><br />
?- X isv clean( france probe capital ). 
X = paris-1. 
?- france isv merge( capital bind paris, location bind we, money bind euro ). 
<em>Now we build a record structure.</em>
<em>france becomes a vector that is similar to all </em>
<em>the arguments of merge.</em>  
?- X isv clean( france probe capital ). 
X = paris-0.772.  
<em>Searching the item memory for</em>
<em>france ⊗ capital gives paris,</em>
<em>which is 0.772 similar to it. This</em>
<em>matches better than the other</em>
<em>vectors in the memory, namely</em>
<em>euro, money, we, location, and</em>
<em>capital. </em><br />
?- X isv clean( france probe paris ). 
X = capital-0.772.
?- X isv clean( france probe location ). 
X = we-0.7711.  
?- X isv clean( france probe we ). 
X = location-0.7711.  
?- X isv clean( france probe money ). 
X = euro-0.7273.
?- X isv clean( france probe euro ). 
X = money-0.7273.
<em>The queries above show how</em>
<em>we can retrieve other values given</em>
<em>their field selectors, or other selectors</em>
<em>given their values.</em> <br />
?- sweden isv merge( capital bind stockholm, location bind nwe, money bind krona  ). 
<em>Now build another record,</em>
<em>for sweden. </em><br />
?- X isv clean( sweden probe capital ). 
X = stockholm-0.7749. 
<em>We can get its content</em>
<em>in the same way. </em><br />
?- X isv clean( sweden probe stockholm ). 
X = capital-0.7749.
?- X isv clean( sweden probe location ). 
X = nwe-0.7265.  
?- X isv clean( sweden probe nwe ). 
X = location-0.7265.
?- X isv clean( sweden probe money ). 
X = krona-0.7718.  
?- X isv clean( sweden probe krona ). 
X = money-0.7718.     
?- X isv clean( sweden probe ( france probe paris ) ). 
X = stockholm-0.6791. 
<em>What is the "Paris of Sweden"?</em>  
?- X isv clean( france probe ( sweden probe krona ) ). 
X = euro-0.5939. 
<em>What is the "Krona of France"?</em> 

 

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video