More on n-tuples

Remember the n-tuples? No? they are down there (V) a little bit.

 

The smaller the value of n, the smaller the memory requirement, which is obviously a Good Thing.  The problem is, if you make n too small, each of the RAM elements can become saturated very quickly.  I like to work with extreme examples, so let us look at n=0.  This is not going to be interesting, but I feel the urge.  An n-tuple with n=0 should take up 1 bit of ram – but it’s address is made up of no bits from the data, so it is totally useless!  OK, so how about n=1?  Each recogniser looks at 1 element of the picture, and if it is white (say) then the RAM is 01, and if it is black, the RAM is 10.  Using such a recognizer is about as useful as printing the image out, mincing it with a fine solution of water and alcohol, and then employing a colorimeter to tell you how dark the resulting solution was.  Oh, and keeping a blank sheet of paper alongside, just for a laugh.

 

Now, let us look at n=2.  We need 2^2=4 bits to store the information.  If we tabulate the possibilities (inputs down the left hand side):

 

	3	2	1	0
WW	0	0	0	1
WB	0	0	1	0
BW	0	1	0	0
BB	1	0	0	0

 

Let’s train one with WB.  The 2-tuple now holds a binary value of 0010.  If we trained it on a whole series of 2-pixel elements from a number of sources, if we assume for the moment that due to noise, camera angle yada-yada the distribution of pixels is more or less random across the whole set of images, we will reach the point where it has become saturated.  We could reasonably expect it to be able to learn 4 images, on average, before becoming full, and, essentially, useless – the ‘yes man’ of the recognizer world.

 

It seems sensible then to design such a network with a value of n which allows as many images to be stored as are necessary for the application at hand.  For instance, if I have 600 sets of sample data for each category of thing I want to identify, it would make sense to have this number of images fit easily within each of my n-tuple recognizers RAMs, without saturation being a problem.  As a rule of thumb (and I am more than open to being challenged on this) I would suggest that 2^n should be twice the number of samples, or thereabouts.  In this case, 2048 (2^11) is the next power of two up from 2*600, but 1024 is not so much smaller that I wouldn’t consider 10 as a suitable value of n.

 

Now, if we have 1024 bits per recognizer, they take up 128 bytes each.  As the samples are all from the same class, we would hope that there is, generally, a large amount of overlap in the information.  Those recognizers which address discriminatory micro-features in the image (ie the ones which are useful to us) will be of most interest to us.  If the nature of the data is such that we can ignore the rest, we can store the discriminating recognizers in rather less space than we would need to store the whole lot.  In the case I am considering, my data ‘image’ consists of just over 1million bits.  This means I will need to have at least 100,000 recognizers if they are 10-tuple, more with over sampling (ie 12.8million bytes x the over sampling factor). 

 

Consider the memory requirement, for instance, if I chose n to be 16 instead.  Now each recognizers RAM size is 65536 bits (8KB), but I would only need just over half as many.  Which is good news as this now needs  500MBx over sampling factor.  Or does it?

 

 

Each of my samples can have the address it references in the RAM stored as 2 bytes (16 bits…), so an alternative representation of the recognizer is an array of up to 600 integers (unsigned).  That is 1200 bytes each, making the whole lot fit in to 75MB x over sampling factor.  Much tidier!