After several days of thinking about grid cells and localization (still trying to grok a plausible mechanism that would give rise to the observed grid cell behavior), I finally made a somewhat related connection back to the encoders that I thought I would run by the HTM community. While considering the 1D example of grid cell behavior in @rhyolight’s HTM School video, I came up with a simple scalar encoder that I believe has some rather nice properties and is also fairly simple to implement.
The algorithm:
- Choose a set of prime numbers, (e.g. PRIMES = { 2, 3, 5 }), as a basis set.
- Create a bit-array with sum( PRIMES ) bits (e.g. 2+3+5=10). This will hold the encoded representation.
- For each value, p, in the basis set we reserve p-bits in the representation as a ‘modulo module’. (e.g. [ 0 0 | 0 0 0 | 0 0 0 0 0 ] ).
- When encoding an integer, N, we flip the bit in each of these modules corresponding to the modulo operation (e.g. N%p, for each p in PRIMES).
This encoder has some nice properties:
- It’s fairly quick to compute.
- The number of bits in the representation increases slowly (as the sum of the primes in the basis set)
- The number of unique representations increases rapidly (as the product of the primes in the basis set).
- Each integer in the range of 0 to prod( PRIMES )-1 has a unique representation. The representations then repeat for subsequent values.
- Fixed sparsity that scales as (numPrimes/numBits)
Here are a few examples of the scalar encoder in action. The last row in each case shows a sample encoding for a random number in the interval [0, numReps). The first output is the value to be encoded, the second is the base-10 integer corresponding to the binary encoding and the last is the encoded bit string.
primes: 2
numBits: 2
numReps: 2
sparsity: 0.5
0 2 10
primes: 2,3
numBits: 5
numReps: 6
sparsity: 0.4
4 18 10010
primes: 2,3,5
numBits: 10
numReps: 30
sparsity: 0.3
8 546 1000100010
primes: 2,3,5,7
numBits: 17
numReps: 210
sparsity: 0.23529411764705882
135 51216 01100100000010000
primes: 2,3,5,7,11
numBits: 28
numReps: 2310
sparsity: 0.17857142857142858
2139 100933664 0110000001000010000000100000
primes: 2,3,5,7,11,13
numBits: 41
numReps: 30030
sparsity: 0.14634146341463414
13570 1271377494018 10010100000000100000000010000000000000010
primes: 2,3,5,7,11,13,17
numBits: 58
numReps: 510510
sparsity: 0.1206896551724138
290902 163273087536594944 1001000100000100000000001000010000000000000000000000000010
primes: 2,3,5,7,11,13,17,19
numBits: 77
numReps: 9699690
sparsity: 0.1038961038961039
3409963 4.752342892364848e+22 01010000100000100000000010000000000000010010000000000000000000000000000010000
I’d appreciate any feedback you might have, and would be really interested in hearing if anyone has any ideas for how to extend this to floating point values. (I have some thoughts on that, but I’ve not quite worked it all out.)