learning sequences HTM style using if-then machines

I think this one will be hard for me to clearly explain. The gist is that in this post I will describe an if-then machine implementation of high order sequences as used by Jeff Hawkins and team in their HTM theory (hierarchical temporal memory). See for example here and here. Now, let's be clear, I'm just implementing high order sequence memory, HTM style, not the rest of the theory.

The key motivation is this diagram (from here):

It took me a lot of thinking to work out how to convert that to superpositions and so on, but I now have it working. The key step was the idea of append-column[k] and random-column[k].

Say we want to learn two sequences, "A B C D E" and "X B C Y Z". The first step is mapping these sample kets to random superpositions, HTM style with 40 random bits on, out of 65,536 (I found 2048 to be too small):

full |range> => range(|1>,|65536>)
encode |A> => pick[40] full |range>
encode |B> => pick[40] full |range>
encode |C> => pick[40] full |range>
encode |D> => pick[40] full |range>
encode |E> => pick[40] full |range>
encode |X> => pick[40] full |range>
encode |Y> => pick[40] full |range>
encode |Z> => pick[40] full |range>

As a for example, here is what |A> and |B> look like:

encode |A> => |46581> + |5842> + |10554> + |18717> + |22884> + |34164> + |29694> + |65161> + |12166> + |31602> + |44350> + |60318> + |56003> + |946> + |40363> + |21399> + |64582> + |48142> + |14277> + |31325> + |2860> + |23765> + |33211> + |31290> + |22292> + |44135> + |19071> + |20005> + |9723> + |24764> + |52728> + |23103> + |63140> + |36678> + |14336> + |30736> + |17101> + |31846> + |34044> + |1587>
encode |B> => |50346> + |24515> + |20535> + |25449> + |58467> + |60274> + |340> + |6820> + |12051> + |27589> + |14914> + |63705> + |64633> + |30620> + |35953> + |6121> + |15493> + |11297> + |53700> + |63426> + |61028> + |23552> + |18147> + |39314> + |32615> + |35069> + |21863> + |31562> + |48151> + |58234> + |58634> + |54619> + |23797> + |3313> + |41804> + |26164> + |8110> + |45699> + |59767> + |32480>

Now, learn the sequences:

-- learn the sequences:
pattern |node 1> => append-column[10] encode |A>
then |node 1> => random-column[10] encode |B>

pattern |node 2> => then |node 1>
then |node 2> => random-column[10] encode |C>

pattern |node 3> => then |node 2>
then |node 3> => random-column[10] encode |D>

pattern |node 4> => then |node 3>
then |node 4> => random-column[10] encode |E>


pattern |node 11> => append-column[10] encode |X>
then |node 11> => random-column[10] encode |B>

pattern |node 12> => then |node 11>
then |node 12> => random-column[10] encode |C>

pattern |node 13> => then |node 12>
then |node 13> => random-column[10] encode |Y>

pattern |node 14> => then |node 13>
then |node 14> => random-column[10] encode |Z>

where:

pattern |node 1> represents A
then |node 1> and pattern |node 2> represent B'
then |node 2> and pattern |node 3> represent C'
then |node 3> and pattern |node 4> represent D'
then |node 4> represents E'
pattern |node 11> represents X
then |node 11> and pattern |node 12> represent B''
then |node 12> and pattern |node 13> represent C''
then |node 13> and pattern |node 14> represent Y''
then |node 14> encodes Z''

Let's take a look at the superpositions for A, B' and B'':

pattern |node 1> => |46581: 0> + |46581: 1> + |46581: 2> + |46581: 3> + |46581: 4> + |46581: 5> + |46581: 6> + |46581: 7> + |46581: 8> + |46581: 9> + |5842: 0> + |5842: 1> + |5842: 2> + |5842: 3> + ...
pattern |node 2> => |50346: 5> + |24515: 4> + |20535: 1> + |25449: 9> + |58467: 8> + |60274: 6> + |340: 4> + |6820: 5> + ...
pattern |node 12> => |50346: 8> + |24515: 7> + |20535: 9> + |25449: 6> + |58467: 8> + |60274: 3> + |340: 5> + |6820: 7> + ... 

Now for the interesting bit! Stitching these patterns together to make if-then machines:

next (*) #=> then similar-input[pattern] |_self>
name (*) #=> similar-input[encode] extract-category |_self>

where, the next operator takes a given pattern, and returns the next one in sequence, and the name operator casts the pattern back to the original kets |A>, |B>, etc. Unfortunately this bit of the code is not finished, so we have to implement them long hand:

input-encode |*> #=> append-column[10] encode |_self>
step-1 |*> #=> similar-input[encode] extract-category then similar-input[pattern] input-encode |_self>
step-2 |*> #=> similar-input[encode] extract-category then similar-input[pattern] then similar-input[pattern] input-encode |_self>
step-3 |*> #=> similar-input[encode] extract-category then similar-input[pattern] then similar-input[pattern] then similar-input[pattern] input-encode |_self>
step-4 |*> #=> similar-input[encode] extract-category then similar-input[pattern] then similar-input[pattern] then similar-input[pattern] then similar-input[pattern] input-encode |_self>

And finally:

-- step through the sequence starting with A:
sa: step-1 |A>
|B>

sa: step-2 |A>
1.0|C>

sa: step-3 |A>
0.87|D> + 0.13|Y>

sa: step-4 |A>
0.87|E> + 0.13|Z>

-- step through the sequence starting with B:
sa: step-1 |B>
1.0|C>

sa: step-2 |B>
0.5|D> + 0.5|Y>

sa: step-3 |B>
0.5|E> + 0.5|Z>

sa: step-4 |B>
|>

-- step through the sequence starting with C:
sa: step-1 |C>
0.5|D> + 0.5|Y>

sa: step-2 |C>
0.5|E> + 0.5|Z>

sa: step-3 |C>
|>

sa: step-4 |C>
|>

-- step through the sequence starting with X:
sa: step-1 |X>
|B>

sa: step-2 |X>
1.0|C>

sa: step-3 |X>
0.87|Y> + 0.13|D>

sa: step-4 |X>
0.87|Z> + 0.13|E>

So it all works pretty well! Though I wonder how long sequences can be, before you just get noise?

Next, let's see them all at once in a pretty table:

table[ket,step-1,step-2,step-3,step-4] rel-kets[encode]
+-----+----------------+----------------+----------------+----------------+
| ket | step-1         | step-2         | step-3         | step-4         |
+-----+----------------+----------------+----------------+----------------+
| A   | B              | 1.00 C         | 0.87 D, 0.13 Y | 0.87 E, 0.13 Z |
| B   | 1.00 C         | 0.50 D, 0.50 Y | 0.50 E, 0.50 Z |                |
| C   | 0.50 D, 0.50 Y | 0.50 E, 0.50 Z |                |                |
| D   | 1.00 E         |                |                |                |
| E   |                |                |                |                |
| X   | B              | 1.00 C         | 0.87 Y, 0.13 D | 0.87 Z, 0.13 E |
| Y   | 1.00 Z         |                |                |                |
| Z   |                |                |                |                |
+-----+----------------+----------------+----------------+----------------+

Wow! That table is perfect. We have very cleanly learnt our two sequences.