[ Jocelyn Ireson-Paine's home page | Free software | Publications | Interactive category theory demonstrations | Contact ]
These modules implement the binary holographic reduced representations described in
The software is here, as a zip file.
This is only a brief introduction: for more information, please read the paper. The idea of holographic reduced representations (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 the principles. There are several versions of HRR, developed by different researchers: I'll talk about that in Kanerva's paper.
In Kanerva's paper, and in my code, vectors are binary, each component being 0 or 1. The fundamental functions are:
⊗
;
merge
;
clean
;
dot
.
Important algebraic properties are:
A ⊗ B = B ⊗ A. (⊗ is commutative.) (A ⊗ B) ⊗ C = A ⊗ (B ⊗ C). (⊗ is associative.) A ⊗ B ⊗ B = A. B ⊗ B ⊗ A = A. (⊗ is self-inverse.) A ⊗ merge( B, C ) = merge( A ⊗ B, A ⊗ C ). (⊗ distributes over merge.)
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
.
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.
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 what this is trying to do.
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 ).
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".
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
.
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.
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.
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) ?
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.
My implementation is coded in Jan Wielemaker's SWI-Prolog.. It contains three modules, and some test programs.
The modules are:
random
,
⊗
,
merge
, and dot
.
clean
operation.
is/2
predicate. This provides a
convenient functional notation for evaluating
HRR expressions from the Prolog top-level interpreter.
The test files have names which end in _TEST1.pl
.
You run them with my Autotest program.
Each file contains a sequence of goals which exercise its
module's exported predicates.
Each module is headed by comments describing its exported predicates. You can see examples of their use in the test files.
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.
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). 1 ?- cd('c:/kb7/hrr'). true. 2 ?- [paths]. % paths compiled 0.00 sec, 1,104 bytes true. Loads search paths used by the modules when referring to other modules. 3 ?- [hrr_vectors]. % hrr_vectors compiled into hrr_vectors 0.02 sec, 5,444 bytes true. Loads the basic vector predicates. 4 ?- [hrr_item_memory]. % hrr_item_memory compiled into hrr_item_memory 0.00 sec, 4,616 bytes true. Loads predicates for handling the item memory. 5 ?- [isv]. % isv compiled into isv 0.02 sec, 5,184 bytes true. Loads the "for-convenience" evaluator. 6 ?- isv_assert_dimension(5). true. Make the dimension something small, so that we can look at the vectors. 7 ?- hrr_item_memory_listing. true. There are no symbols in the memory. 8 ?- X isv a. X = [0, 1, 0, 1, 0]. Has generated a random vector ... 9 ?- hrr_item_memory_listing. a true. ... and added it to the memory. 10 ?- X isv b. X = [0, 0, 1, 0, 0]. Has generated another random vector and added it to memory. 11 ?- hrr_item_memory_listing. a b So these are the two symbols in memory. 12 ?- X isv (a bind b) probe b. X = [0, 1, 0, 1, 0]. X is the vector for a, above. 13 ?- X isv (c bind d) probe d. X = [0, 1, 0, 0, 0]. 14 ?- hrr_item_memory_listing. a b c d true. Statement 13 generated random vectors for c and d, and added them to memory ... 15 ?- hrr_item_memory(Atom,Vector). Atom = a, Vector = [0, 1, 0, 1, 0] ; Atom = b, Vector = [0, 0, 1, 0, 0] ; Atom = c, Vector = [0, 1, 0, 0, 0] ; Atom = d, Vector = [0, 1, 0, 1, 0]. ... as we see. We also see that the above result of (c bind d) probe d is c. And that the dimensionality is so small that there's already a clash of symbols, between a and d. 16 ?- X isv clean( (a bind b) probe b ). X = a-1. The easy way to get the nearest symbol vector to the result of an expression. The vector's name is a, and its similarity with (a bind b) probe b is 1. Which is not surprising, because the algebraic properties of bind and probe mean that (a bind b) probe b is a. 17 ?- hrr_item_memory_retractall. true. Clean the memory, because I'm going to use huge vectors next. 18 ?- hrr_item_memory_listing. true. 19 ?- isv_assert_dimension(10000). true. 20 ?- X isv (c bind d) probe d. X = [1, 1, 0, 0, 0, 0, 0, 1, 1|...]. 21 ?- X isv clean( (c bind d) probe d ). X = c-1. 22 ?- hrr_item_memory_listing. c d true. 23 ?- hrr_item_memory_retractall. true. 24 ?- france isv capital bind paris. true. 25 ?- hrr_item_memory_listing. france capital paris true. 26 ?- X isv clean( france probe paris ). X = capital-1. 27 ?- X isv clean( france probe capital ). X = paris-1. This works exactly the same as the (a bind b) probe b example. 28 ?- france isv merge( capital bind paris, location bind we, money bind euro ). true. france is now a vector that is similar to all the arguments of merge. 29 ?- X isv clean( france probe capital ). X = paris-0.772. 30 ?- X isv clean( france probe paris ). X = capital-0.772. 31 ?- X isv clean( france probe location ). X = we-0.7711. 32 ?- X isv clean( france probe we ). X = location-0.7711. 33 ?- X isv clean( france probe money ). X = euro-0.7273. 34 ?- X isv clean( france probe euro ). X = money-0.7273. 35 ?- hrr_item_memory_listing. france capital paris location we money euro true. 36 ?- sweden isv merge( capital bind stockholm, location bind nwe, money bind krona ). true. 37 ?- X isv clean( sweden probe capital ). X = stockholm-0.7749. 38 ?- X isv clean( sweden probe stockholm ). X = capital-0.7749. 39 ?- X isv clean( sweden probe location ). X = nwe-0.7265. 40 ?- X isv clean( sweden probe nwe ). X = location-0.7265. 41 ?- X isv clean( sweden probe money ). X = krona-0.7718. 42 ?- X isv clean( sweden probe krona ). X = money-0.7718. 43 ?- hrr_item_memory_listing. sweden france capital paris location we money krona euro stockholm nwe true. 44 ?- X isv clean( sweden probe ( france probe paris ) ). X = stockholm-0.6791. What is the "Paris of Sweden"? 45 ?- X isv clean( france probe ( sweden probe krona ) ). X = euro-0.5939. What is the "Krona of France"?