Rik, This is great!! Nicely done. I am not sure I understand your question: Although the union property is related to what happens going from the TP at one level to the SP at the next level, that is not what motivated looking for the union property of SDRs.
In a single region, a single CLA, the TP is making a prediction of what is going to happen next. The union property allows the CLA to make multiple simultaneous predictions. The goal is to check to see if the next input matches one of the predictions. The capacity to distinguish these different predictions is a measure of how many things we can anticipate at the same time and still be confident we will notice something unexpected happens. This is an important property of an animal, to notice that something is unexpected. As Subutai pointed out, it is significant that with SDRs we can make multiple simultaneous predictions using the same fixed set of cells. The brain doesn't build a dynamic list of predictions, plus it is computationally efficient to do a single comparison which checks for all the predictions at once. Sometimes we know precisely what is going to happen next and other times there are many possibilities. Having a system that accommodates both is essential. In the CLA a mis-prediction happens at the columnar level. This is also useful and unique. It means we know what part of the input is wrong and what part is right. The "wrong part" could be topologically related to a sensory array (e.g. this part of visual field is wrong) or it could be more semantically related higher in the hierarchically (e.g. the verb action doesn't match vs. the verb tense doesn't match). When we have a column mis-match all the cells in the column become active. In the real brain we know that mis-predictions lead to significant more activity in the area of mis-prediction. We also know that excess activity will open up the gated pathway through the thalamus. Thus a mis-prediction forces attention on the part of the input that was mis-predicted. Jeff -----Original Message----- From: nupic [mailto:[email protected]] On Behalf Of Rik Sent: Monday, November 04, 2013 5:55 AM To: [email protected] Subject: [nupic-dev] SDR capacity Hi, Yesterday in the CLA presentation at the hackathon Subutai was asking "how many 40-out-of-2048 SDRs can you store in an SDR?" where "storing" meaning or'ing them all up (as in Boolean "or") and then comparing the combined SDR to a sample SDR. (The combined SDR may actually not be so sparse anymore but I stick to calling all bit vectors "SDR" here.) All "1" bits of the sample SDR should only be present in the result if the sample was part of the set in the first place, otherwise it'd be a false positive. A matching random SDR would almost certainly be a false positive as any realistic set of input SDRs are a vanishingly small subset of all possible SDRs. Since false positives are inevitable and their probability increases the more SDRs you "or" together, the question should really ask for a capacity given a desired probability of false positives, or rather a desired accuracy which is the complement (1 - x) of false positives (there being no false negatives). So how does the accuracy relate to the capacity? And what's the capacity for the above 40/2048 assuming a desired accuracy of, say, 99%? The attached Mathematica notebook "sdr_capacity.nb" seeks to work this out. First the accuracy is determined as a function of length, density and capacity and then solved for capacity. Starting with the example 40-out-of-2048, the density is 40/2048 = .0195 meaning 1.95% of bits are "1" and the density of 0's (called "density0") is 1 - density = .9804. Because two bits or'ed together are only 0 if both bits are 0, the density0 of two SDRs or'ed together is the product of the original density0's. Or for the case of, say, 100 SDRs of the same density0 or'ed together: density0^100 = .1142. The density (of 1's) is then 1 - density0 = .8858 (= 1814 bits for a length of 2048). To determine the probability of a random SDR to have all its 1-bits present in the combined SDR we take its first 1-bit position and check for a presence of 1 in the combined SDR. With a density of .8858 the probability is .8858. If true we can then picture taking that 1-bit out of the combined SDR leaving an empty spot (not a 0-bit). The remaining SDR shorted by one bit pretty much still has the same density, this is an approximation for low densities in the original and sample SDRs. So for all 40 bits the probability is again the product of all 40 probabilities = .8858^40 = .0078. (In reality the density goes down as you remove 1's so this approximation overestimates the probability of false positives a little bit and underestimates the accuracy. The exact calculation is left as an exercise for the reader.) The accuracy then is the complement (1 - x) of the probability of a false positive = .9922 or 99.22%. In general, in Mathematica notation: PoolerAccuracy[length_, density_, capacity_] := N[1 - (1 - (1 - density)^capacity)^(length*density)] Plotted for capacities from 0 to 1000, the attached graph "accuracy.png" shows the expected sigmoid function with a sharp drop off in accuracy starting from around 120. Mathematica then solves for capacity and for the values of length = 2048, density 40/2048 and accuracy .99 yields a capacity of 112. The attached plots "capacity_vs_density.png" and "capacity_vs_length.png" show that decreasing density or increasing length increase capacity. To test my own math I perform a little experiment in attached Mathematica notebook "sdr_experiment.nb". I combined 100 SDRs using Boolean "or" and then test 10,000 sample SDRs against the combined SDR. This yields an accuracy of 9892 out of 10,000 = 99% as expected. All correct? And how does this relate to CLA? The temporal pooler feeds an or'ed SDR of the current input and all predictions into the spatial pooler with its learned one SDR per each column. This doesn't test for exact matches, it's more like a certain percentage of bits has to match and that percentage depends on match rates of the neighbors. This requires some other model of "capacity" than the above. Correct? Cheers Rik _______________________________________________ nupic mailing list [email protected] http://lists.numenta.org/mailman/listinfo/nupic_lists.numenta.org
