C Programming a Combinatorial Problem Solver

[Simon Kettle]

C Programming a Combinatorial Problem Solver

Well this is another interesting topic and very important to making Neural Networks useful and controlling better how they behave.

As with recognising images and features within images we first presented the network with primitive forms that we built from using the Laplacian Gaussian edge detector. The real power of these neural networks is that they can do a similar operation on the image to find its features and classify them. Imagine for a minute that this is the same task as the convolution matrix performs in edge detection only instead of lots of iterations throughout the image being done one after another the Neural network does these iterations all at once by using its interconnectivity.

It assigns groups of neurons to deal with each part of the image and these groups are called receptive fields responding to only one area of the image and sharing processing of that area with others whose fields overlapp until all the image is processed.

Right now how does this happen how does the network know which neurons are dealing with which segment of the image - it doesnt. It just leanrs to associate solutions to the image that we want it to. Or in other words if we train it to recognise cats it will with varying degrees of success depending on how well it is trained and what primitive information it is trained with.

From this we can gather that it must change alot as networks must change their connections in order to assign receptive fields to different parts of the image or different features of the image. Here begins the job of the combinator. Its like the hardwiring in our brains to recognise shapes and edges and pick out only the useful information that we need.

The combinator will arrive at a solution for an optimal neural network that will later be trained to recognise cats and dogs. But first we need it to score well on basic shapes and primitve features of the image - this is our hard wiring.

Here is a sample of code to get you started on combinational logic. This combinator will select the optimal connectivity and number of neurons in each group or assembly that will constitute our receptive fields for each feature of the image.

Once we have a good working combinator that can be tweeaked and is flexible for a variety of 'neural topology's' - thats the form and the shape of our artificial brain, then we can use it to guide our formless networks into behaviours that once trained will be able to recognise exactly what we want in an image and rebuild the image into something useful.

For example a neural network trained on primitives of dog's and cats could differentiate between them after being trained and initiated with a combinator. More simpler a neural network hard wired for recognising letters and handwriting. But hold on a minute before I copy this code over, what are the primitives from dogs and cats?
Thinking as a machine..

Dogs / Cats
Colour Colour X -

Well this is no good because they often have the same colour and colour doesnt distinguish them when this might vary due to lighting

Size Size / -
This is a good one Dogs and cats dont always have the same size - dogs are generally larger and cats smaller but that again could be dependant on the distance from the camera

We are looking for invarients

Shape Shape


Well this is invarient to size we could take a large dog and make it the same size as a kitten we could blur the image with heuristic and then use another heuristic to find the centers for all the pixels that belong to the blurred image of the dog or cat then we could draw a line between the centers and measure relative distances between them. This would be and invarient that we could use to recognise and differentiate between them.


Anyway heres my code for a basic Combinator.



1. The function you need for combinational logic is based on Factorials and is derived from POLONOMIAL's - to find the number of combinations of M items in N you need the following formula:

n! / ((n - m)!*m!)

The n! means n x (n-1) x (n-2) .. x (n-n+2) its basically a way to find all the combinations of N items or put another way how many ways can you combine N number of neurons that is then divided by the number of ways you can combine M number of N which is (N-M)! x M!

And my presumption is there are similar formula's for other more complex combinations not listed on Wikipedia!!

Here is the basic one for a combinator with M in N which would transpire to M neurons in a N neuron network such that you'd get the right number of M numbered groups of neuron to construct a receptive field containing say 5 of this M sized groups for an image that contains 1000,0000 pixels segmented into 100 100x100 segments

Ofcourse you can then extend this formula with the added features that each group can possess any number of neurons between 5 and 10 say with the goal of finding the right amount of variability to allow for optimal /correct performance and limiting the number of total neurons or layers in the network. Less is more. Why have a Network that can do the same with more neurons simply cos you didnt find the time to build a combinator(TM)!

Once you have this you can then started PRUNING your neural network until you have it hardwired.

Here's the code to get you started.

int No = 100; // number of subfields or neural assembly's
int Nc = 10;  //Number of neurons in each Assembly k
int Ntot = 50; //Total number of Neurons  n
int Layers = 2;


/*Example using letters of alphabet*/

char combin_array[] = {'a','b','c','d','e','f','g','h'};
cout << combin_array[2]<<"\n";
/*First calculate how many possible combinatiosn there are for 3 in 8*/
/*Combinatorial Calculator n! / ((n - m)!*m!)*/


int output[3];int ncomb_int;
int repeat,match,n_int=6,k_int=3;
cpp_int k = k_int;
cpp_int n = n_int;

/*Calculate Factorials*/

cpp_int n_fact=n;
for(int h=1;h<n;h++){
n_fact *= n-h;}
cpp_int k_fact=k;
for(int h=1;h<k;h++){
k_fact *= k-h;
}
cpp_int nk_fact=n-k;
cpp_int nk = n-k;
for(int h=1;h<nk;h++){
nk_fact *= h;}

cpp_int n_comb; 
n_comb = n_fact/(k_fact*nk_fact);

//int n_comb = n!/((n-k)!*k!);
for(int i=0;i<n_comb;i++){        //trick to convert cpp_int to int
ncomb_int++;
}


cout <<"N! = "<<n_fact<<" K! = "<<k_fact<<" (N-K)! = "<<nk_fact<<"\n";
cout <<"Number of combinations of "<<k<<" in "<<n<<"="<<n_comb<< "\n";

Now in order for this to work in C , computing factorials need's alot of integer!! So weve got this library which when you include it you can make purty big numbers!!

#include <boost/multiprecision/cpp_int.hpp>

2. Ok once this is taken care of you have the value for N and that tells you roughly how big your network need's to be. How many neurons is N and then you have n_comb, well thats just my notation and your just going to search with different values of N and K until you get just over the number of combinations you need in n_comb.

Once you know what the values for N and K are (dont forget K has to be between the number of neurons that will process one segment of your image successfully and some upper limit or lower limit to your choosing), you can then apply this second bit of code to generate the combinations. In this example because we are only using the above simple formula of
N!/(N-M)!*M! we only get combinations with multiple repetitions ideally you would adapt the formula to get a variable and controlled number of repetitions. Heres the code for generating the combinations with repetitions:

int combinator[ncomb_int][3];
int select,selectold;
int count=0;

do{

for(int i=0;i<k;i++){
select=rand() % 8;
//cout<<combin_array[select]<<"\n";
if(selectold==select){i--;}else{
output[i]=select;
selectold=select;        }
}
repeat=0;
for(int j=0;j<count;j++){
match=0;
for(int m=0;m<k;m++){
if(output[m]==combinator[count][m]){
match++;
}
if(match==3){repeat=1;j=count;}
}
}
if(repeat!=1){
for(int q=0;q<k;q++){
combinator[count][q]=output[q];
        }
count++;     }
}while(count<n_comb);

cout<<"Last 10 combinations\n";

for(int i=ncomb_int-10;i<ncomb_int;i++){
cout<<"{";
for(int j=0;j<k;j++)   {
cout<<"{"<<combin_array[combinator[i][j]]<<"},";
            }
cout<<"}\n";            }

Have fun and dont forget to checkout my latest chapter from the book 'Coeusian Conspiracy' that I've secretly uploaded to my Google drive heres the link enjoy. bit dot ly / 1P0wmVW

To read more search my pen name on Amazon - 'Sam Shepherd'.