I've found a way to decode SDRs


#1

I have found a way to decode SDRs in some cases.
Suppose you are encoding a scalar. Suppose you use 21 bits to encode each number.
Each number is shifted over by one in the encoder, so adjacent numbers are semantically similar. You now feed the encoded bits into the spatial pooler, and get an SDR. Suppose you would like to be able to do the reverse - get the original encoded value from the SDR.

One way to do it is this: (steps follow).

1. create a buffer the size of the encode buffer, but instead of bits, make it integers.  
2. For every active column do:
3.    For every synapse in that column that has permanence >= permThreshold Do:
4.          lookup the input that feeds that synapse
5.          increment the buffer-count for that input

The buffer will have many non-zero counts.   Too many.   Some will be larger than others.   
So what you have to do is count all non-zero counts above a threshold.   But what threshold 
should you use?   To find out, you do this:

go through the buffer looking for the max count.  
Lets call it: "maximumValueOfAnyCountInBuffer".  Then:
for percent = 100 down to 1
    threshold = percent * maximumValueOfAnyCountInBuffer
    count the number of values >= threshold
    if that count >= 21 bits then
           STOP.  

At this point, you make all bits 1 that are >= threshold, and all other bits zero.

There are a few noise bits that are on in the resulting encoder (but are obvious outliers since this encoding requires contiguous input bits)

Some issues:

  1. what happens if there is noise in the encoded SDR that you are trying to decode? (I have not tried that)
  2. what happens when you use other types of encoder? (I have not tried that)
  3. what happens when you use the temporal pooler, which has all sorts of complications, including having unions of several predicted possibilities?

So I’m not sure if this is of any practical use.


How can I reconstruct the input using an SDR?
#2

If X is the SDR you want to decode, and Ei is the SDR encoding of each possible input i that it could decode into, then why not just compute the overlap Vi = | XEi | for each possible input and use that as a distribution over the possibilities?

To give these values a numerical interpretation you could apply a probability-based activation function on top of this distribution: P(Vi | random sampled SDR), i.e. the probability of getting this much overlap by sampling an SDR at random. This would quantify the chance that this is a random match, and you could apply a hypothesis test (P < 0.001 or something) to the lowest such probability (the best match), and you’d have a measure of confidence in your match.

And further, if you have an idea of the noise distribution N your SDRs are subject to, then you could score the possibilities by P(X | Ei, N), i.e. the probability of degrading Ei into X given noise N.


#3

That does seem to be a simpler, better method. Thanks for coming up with it.


#4

Jake:
One question occurred to me on your method. Suppose there is a tie. Lets take a case where there are 3 bits per pattern. if bits 4,5,6 are on together, we will say that we have encoded the number ‘55’. If bits 5,6,7 are on together, that stands for the number ‘56’. And suppose, after projecting the columns backwards to the encoder, the bits 4,5,6,7 are on. Now we don’t know which of the two patterns we have. They both overlap by the same amount (in this case 100%).

My method used ‘votes’. So if 10 columns together say that bit ‘4’ is on, but only 2 columns say that ‘bit’ 7 is on, then my method would choose ‘4,5,6’ as the pattern. My question is, in cases of ‘ties’ in your method, would it make sense to use ‘votes’ to say one of the two patterns was more probable than the other?


#5

I coded your method, and my method is much better, assuming I got your meaning correct, which is that you just set bits on, without taking any votes, and then try to find what patterns overlap the most. However, I will look into your idea of getting a measure of confidence.
This might be a good alternative to the existing decoding methods that Numenta uses.
It generalizes well, and the average error is low (though I notice when I encode numbers and then decode them back that numbers at the far ends of the range do not decode as well), and you can change many of the active columns and still get the correct answer.
Pretty cool.


#6

@gidmeister I’d like to suggest a small alteration to your method: After step five, instead of dealing with thresholds and percentages, how about simply sorting the inputs in descending order by their buffer-counts and then taking the first 21 of those?


#7

Entropy: Thanks for reducing the entropy of my method. I’ll do that.


#8

Here is the source code to decode SDRs, with your suggested changes, minus the probability distribution, which I have to look at. Its in VB.net, because I rewrote the spatial pooler in that language. Maybe sometime in future I’ll try it on the temporal pooler. Average error when using 2 buckets per scalar number is 0.4.

Sub DecodeSDR(ByRef maxValue As Integer, ByRef minValue As Integer, ByRef overlapscore As Double, ByRef displaystring As String, ByRef recreateBoolBuf() As Boolean,
                  ByRef firstbit As Integer, ByRef lastbit As Integer, ByRef bestguess As Double, ByRef percent As Double, ByRef countEntries As Integer)
        Dim ul As Integer
        Dim i As Integer
        Dim startindex As Integer
        Dim votebuffer() As Integer = Nothing
        Dim vote2buffer() As Integer

        ClassConstants.sp.voteEncoder(votebuffer)
        ul = votebuffer.Length - 1
        ReDim vote2buffer(ul)

        For i = 0 To ul
            vote2buffer(i) = votebuffer(i)
        Next
        Array.Sort(vote2buffer)
        startindex = vote2buffer.Length - classEncoder.bitsPerPattern
        minValue = vote2buffer(startindex)
        maxValue = vote2buffer(ul)

        ClassUtils.DisplayIntegerBufferWithMinCutoff(votebuffer, 30, minValue, displaystring, recreateBoolBuf, countEntries)
        classEncoder.findBestMatch(recreateBoolBuf, bestguess, overlapscore, firstbit, lastbit)
    End Sub
 ' **********************
  Public Sub voteEncoder(ByRef votebuffer() As Integer)
        Dim i As Integer
        Dim j As Integer
        Dim c As classColumn
        Dim s As classSynapse
        Dim ul As Integer = classEncoder.encodedInput.Length - 1
        ReDim votebuffer(ul)

        For i = 0 To ul
            votebuffer(i) = 0
        Next
        For i = 0 To activeColumnIndices.Count - 1
            c = columns(activeColumnIndices(i))
            For j = 0 To c.pDendrite.Count - 1
                s = c.pDendrite(j)
                With s
                    If .permanence >= ClassConstants.connectedPerm Then
                        votebuffer(.sourceInputIndex) = votebuffer(.sourceInputIndex) + 1
                    End If

                End With
            Next
        Next

    End Sub
 ' **********************
    Public Shared Sub DisplayIntegerBufferWithMinCutoff(ByRef intbuf() As Integer, ByVal wrapPoint As Integer, ByVal MinCutoff As Integer,
                                                        ByRef displayString As String, ByRef encbuf() As Boolean, ByRef countEntries As Integer)
        Dim i As Integer
        Dim j As Integer
        Dim sb As New StringBuilder("")
        Dim sb2 As New StringBuilder("")
        Dim sbAll As New StringBuilder("")
        Dim firstwrap As Boolean = True
        Dim stri As String
        Dim lenStrI As Integer
        Dim k As Integer
        Dim strK As String = ""
        ReDim encbuf(intbuf.Length - 1)

        countEntries = 0

        If intbuf.Length = 0 Then
            displayString = "empty"
            Exit Sub
        End If

        j = 0
        For i = 0 To intbuf.Length - 1
            encbuf(i) = False
            If j > 0 Then
                sb.Append(",")
                sb2.Append(",")
            End If
            sb2.Append("(" & i & ")")
            stri = i.ToString
            lenStrI = stri.Length
            strK = ""
            For k = 2 To lenStrI
                strK = strK & " "
            Next
            If intbuf(i) >= MinCutoff Then
                countEntries = countEntries + 1
                sb.Append("[*")
                sb.Append(strK)
                sb.Append("]")

                encbuf(i) = True ' key part
            Else
                sb.Append("[ ")
                sb.Append(strK)
                sb.Append("]")
            End If


            j = j + 1
            If j = wrapPoint Then
                If Not firstwrap Then
                    sbAll.AppendLine("")
                End If
                j = 0
                firstwrap = False
                sbAll.AppendLine(sb2.ToString & Environment.NewLine & sb.ToString)
                sb2.Clear()
                sb.Clear()
            End If
        Next
        If sb.Length > 0 Then
            sbAll.AppendLine("")
            sbAll.AppendLine(sb2.ToString & Environment.NewLine & sb.ToString)
        End If
        displayString = sbAll.ToString
    End Sub
 ' **********************
    Public Shared Sub findBestMatch(ByRef recreateBoolBuf() As Boolean, ByRef bestguess As Double, ByRef overlapscore As Double, ByRef firstbit As Integer, ByRef lastbit As Integer)
        Dim i As Integer
        Dim j As Integer
        Dim tempoverlap As Double
        Dim testUpToIndex As Integer
        Dim tempindex As Integer
        Dim ul As Integer
        Dim guesses As New List(Of Double)
        Dim scores As New List(Of Double)

        ul = recreateBoolBuf.GetUpperBound(0)
        For i = 0 To ul
            If recreateBoolBuf(i) Then
                firstbit = i
                Exit For
            End If
        Next
        For i = ul To 0 Step -1
            If recreateBoolBuf(i) Then
                lastbit = i
                Exit For
            End If
        Next
        If firstbit > lastbit Then
            tempindex = lastbit
            lastbit = firstbit
            firstbit = tempindex
        End If
        testUpToIndex = lastbit - bitsPerPattern + 1
        For i = firstbit To testUpToIndex
            tempoverlap = 0
            For j = i To i + bitsPerPattern - 1
                If recreateBoolBuf(j) Then
                    tempoverlap = tempoverlap + 1
                End If
            Next
            guesses.Add(decodePatternStartingAtIndex(i))
            scores.Add(tempoverlap)
        Next

        For i = 0 To guesses.Count - 1
            If i = 0 Then
                bestguess = guesses(i)
                overlapscore = scores(i)
                Continue For
            End If
            If overlapscore < scores(i) Then
                bestguess = guesses(i)
                overlapscore = scores(i)
            End If
        Next
    End Sub

#9

This chart shows the ‘votes’ when you encode the number ‘50’. the little yellow bars show the values that were chosen.


#10

@gidmeister I haven’t coded in BASIC for many years, but if I understand your logic, in DisplayIntegerBufferWithMinCutoff(), you’re converting an integer representation, intbuf(), into a Boolean representation, encbuf(), using a threshold.

If you change encbuf() and recreateBoolBuf() from Boolean to Integer, then replace “encbuf(i) = False” with “encbuf(i) = 0” and “encbuf(i) = True” with “encbuf(i) = intbuf(i)”, then in findBestMatch() replace “tempoverlap = tempoverlap + 1” with “tempoverlap = tempoverlap + recreateBoolBuf(j)”, that might give you a suitable probability distribution and better accuracy.

After this you could also see what happens if you remove the threshold altogether. It would be interesting to see a comparison of results from these different variations.

By the way, that was a nice pun on my username. Lol.


#11

That makes sense. I wasn’t thinking about inverting the spatial pooler like you’re doing. Carry on!


#12

I like this discussion. Here is how NuPIC handles the encode/decode interface. We have an Encoder base class, and subclasses must provide an implementation of encodeIntoArray and (optionally) decode. Here are NuPIC’s ScalarEncoder implementations of encodeIntoArray and decode.

You might notice that the CoordinateEncoder does not provide a decode function. That means we can’t get predictions of future values. We can still do anomaly detection, however.


#13

Matt: Why is there no decode function for the Coordinate Encoder? It is impossible to go back from a deterministic hash function?
I’ll try out the latest idea from ‘Entropy’ also.


#14

I think it just was not a priority. We wanted to prove out the Coordinate encoder with anomaly detection, and that worked really pretty well. But it was all just an example of a potential HTM application. I’m not entirely familiar with the inner workings of the Coordinate Encoder (although it does not seem all that complex). Could be someone anyone could work on.


#15

Looking at the various types of encoders, I realized my method is limited.
First of all, my method is an “SDR classifier”, not a “decoder”. I used the word “decoder” because I thought that any process going backwards is a decoder:
There are 2 SDRs in the spatial pooler. The first one is produced by the encoder. That first SDR is fed into the spatial pooler to make the second SDR.
If you encoded a scalar, then going backwards from the encoder to the scalar could be called “decoding”. But going back from the spatial pooler SDR is not called “decoding” at least not by Numenta.
This raises a problem. Some encoders use hash functions. Hash functions are “many to one”. So if you have an encoder such as the coordinate encoder, and then try to reverse it, I’m not sure you would be able to.
Suppose we take the coordinate encoder as an example. Using my method you take columns in the spatial pooler as input, and produce some bits in the encoder. But then what? If you can’t decode those bits to the original coordinates then the method is useless.
Furthermore, there would be noise (some bits on in the encoder that should not be, and some off that should be on). I wonder what that would do with trying to decode a encoder that depends on hash functions.
In case anyone has ideas to salvage the method, let me know.


#16

Aha, I see. (So now I must point out the SDRClassifier in NuPIC.)


#17

Some questions (for Matt).

  1. If I encode the SDR classifier in Python, I need access to the synapses and permanences of Nupic in the routine. My classifier can’t work just by having a list of columns that are on or off. Would I have access to the various data-structures?

  2. I was thinking about your encoders (date encoders, coordinate encoders, GPS encoders …), and for my purposes, there always has to be a “decode” method. Some of them have it, some of them do not. But in practice, any encoder that has a hash function cannot have a “decode” method (I think).
    So I then started thinking why people use hash functions, and it seems that the only reason is in situations when you have a limited number of bits in the encoder, but you have too many numbers to represent separately. So you hash those numbers, which is a “many to one” operation, which means you do get collisions sometimes. And that rules out decoders…
    So this means that when you make SDR classifiers, you need to either use statistics, or a neural net (that you train) to go from the list of active columns directly to the value those columns represent. So since my method doesn’t do that (it goes indirectly first from the list of active columns to the bits in the encoder, and secondly from those encoder bits to the original value), I had to come up with an alternative to hash functions. And that leads to question 3:

  3. For my alternative to hash functions, my initial idea was to concatenate two encoders (the way you handle dates in the date-encoder). The first encoder might be a scalar encoder from zero to 99, and the second would be a log encoder. The first encoder would use the simple mathematics MOD function, so 101 would become 1. That initial idea had problems, but it did allow for an estimate of magnitude. Then I realized you could do something a little more clever. You could keep the idea of a MOD 99 encoder, but you could also encode the start of the range separately (as a log of 10).
    So for 0 - 99, the start is 0, for 100 - 199, the start is 1, for 200-299 the start is 2. So this is a separate encoder, but just like in the date-encoder, you can concatenate encoders. It seems by this method that you can get a big range out of a relatively small number of bits, and not miss accuracy either. I’m not completely sure this works, it seems like getting something for nothing, but I will try it out. Does this seem like a valid way to go?
    Thanks


#18

No, I think you’d only have access to predicted cells.

Oh sure, I’m not trying to convince you that you’re wrong, just providing more resources. I’ve always said that encoders is a huge area for innovative thinking in HTM. There are many things that could work, and I encourage you to experiment and continue posting your results for the community. Thanks for what you have come up with so far. I don’t have time to test it out (working on more videos), but perhaps some of our community members can try.


#19

To: Entropy
Here is a probability distribution based on your 2 suggestions for improvements. It has an interesting shape. The value encoded was 44, it was decoded to 43 (but I’m using 1 bucket per bit, which is the least accurate). This is my last post for this thread, but I will hopefully try the algorithm out on more complicated encoders, and if I have the time, on the temporal pooler. Maybe it can be used in practice for anomaly detection, but I certainly can’t recode it into nupic.