Number of combinations?

Community Lounge
1

If we have a TM with 5 rows and 100 columns, the possible number of 100bit patterns (by cols) are 5^100.
How many are the possible states if only 20 of those 100 bits can be ON, instead the full 100 ?

thanks

2

First, there are n choose w column combinations.
Then, for every column combination there are (nCellsPerColumn)^w cell combinations.
Therefore the total number of states is 100! / (100-20)! * 5^20.

edit: I meant combinations but I used permutations, therefore the formula above is wrong. See below for correct formula.

1 Like
3

You meant ā€˜permutationsā€™ not ā€˜combinationsā€™ , right ?

or isnt it :

100!/ ((100-20)! * 20! )

5

Oops, I actually meant combinations but I used the permutations formula instead!
Itā€™s indeed 100! / ((100-20)! * 20!) * 5^20
Or more generic: n! / (w!(n-w)!) * (nCellsPerColumn)^w

6

Please excuse if Iā€™ve made a mistake, but when you have 5 rows and 100 columns, your total number of columns == 500. Would you not use the formula over the whole column/cell matrix rather than calculate for one row?

Thus making the formula:

500! / ((500-100)! * 100!) * 5^100

Just curious?

7

That is true, but i think that @mraptor meant 100 columns and 5 cells per column, not 5 rows as input topology, so the total number of columns is just 100. Because by having w = n the formula reduces to 5^100, which was the starting point (also mentioned in the TM paper).

Side note: why does TM accept multidimensional inputs and not exclusively flat vectors? I can understand this feature in SP making use of input topology, but as far as I know the TM computation does not care about topology, so the interface is just confusing.

1 Like
8

Ok, if he meant columns/cells then that makes sense now, thanks. Topology (> 1) dimensions is possible with the SP in certain terms. The dimensions variable is expressed as a 2D entity but it isnā€™t ā€œcommittedā€ in terms of how it relates to columnar dimensionality - meaning it will treat the dimensionality as a flat array at times, and internally I donā€™t believe the distinction is that important except when computing wrap-around locations for neighborhood computations.

If you look here and here, it seems it in fact treats the activeColumns input as a flat vector? Which interface were you looking at?

9

I am not sure what you mean, but I assume itā€™s the fact the input is always passed as a flat vector (of course, any N-dimensional array is flat in the low-level memory) but in the case of SP with local inhibition, elements on different rows in the input matrix can be treated as neighbors despite being far in the flattened format. No problem with this.

I donā€™t know Java but at least in Python and C++, the problem is in the constructors / init, that columnDimensions is a vector instead of a simple scalar, suggesting that it matters if you input columnDimensions = (m, n) instead of columnDimensions = (m*n) as in the case of SP, when in the case of TM it doesnā€™t.

10

Iā€™m going to attempt an explanation here, and you can tell me if it makes sense or you would like it explained in other terms, ok? :stuck_out_tongue:

The dimensionality of the input field and the SP dimensionality must match: meaning that the same number of dimensions are needed however they donā€™t have to match when looking at the flat input vector width and the flat SP column vector width. This is the case as far as I remember due to the outer-vector calculation of the infamous rightVecSumAtNZ() method. This was a constraint I remember having to get enormous clarity around while writing the Java version of the SP.

Whether or not this constraint is (still?) the case with the Python and C++ versions or not, I believe the reason why it is specified the same way in the SP and TM is just for the sake of uniformityā€¦ If you look here in the C++ TM code, the only value which is pertinent is the number_of_columns, so you are correct in that the dimensionality isnā€™t made use of in that algorithm.

Python offers a convenience syntax which allows one to get around the constraint of specifying two dimensions, but the Java and C++ versions of course donā€™t have this kind of syntax candy.

Long answer short. Yes, the (multi) dimensionality is not really used in the TM, but whether it is specified in multiple dimensions or as a flat dimension, the number of columns must be the same, I believe.

11

Sorry for the stupid question. I have always had a problem of converting the word-problem to combinatorics.

In this case you pick the combination formula n-choose-w, because ā€¦ ?
It is easy to understand that with 2 types (0,1) and 100 positions you get 2^100 permutations.
Then it is easy to imagine 5-rows as 5 types and then the possible permutation of X positions then 5^X permutation.

But why combinations for 20 out of 100 bits of 2 types?

I think I got it ā€¦ along this description: http://www.math.ucsd.edu/~jverstra/154-part1.pdf

Permutations are : sequences built from sets
Combinations are : sets built from set.

So ā€¦ we have 100 bits, so we create set S = {1,2,3 ā€¦ 100 }
So sets of 20 elements of S is the answer.

Set: unique elements
Sequence : ordered elements, may repeat