COMP30230, Connectionist Computing February 12th 2009

Due on March 6th 2009, by midnight in any time zone of your choice (but start right now, because this will take a significant amount of pondering, and some time coding) Worth 30% of the final mark for COMP4018 5% off each day late

What to do Build a Boltzmann machine (BM) without hidden units, in any programming language of your choice (C, C++, Java, Perl, Python, even Matlab), but without making use of any available neural network/connectionist/machine learning, etc. library.

Your software should be able to:

Create a new BM with any given number of inputs Initialise the weights of the BM to small random values Let the BM run from an input pattern until it converges Implement learning

You need to test your software as follows:

1.Train a 6-neuron BM on the following 3 examples: (-1, -1, -1, -1, -1, 1) (-1, -1, 1, -1, -1, -1) (1, -1, -1, -1, -1, -1)

2.At the end of training, run the BM 5 times starting from each of the following patterns, and print out the state of the BM (values of all neurons) at the end of each run: (-1, -1, -1, -1, 1, 1) (-1, -1, -1, -1, -1, -1) (1, 1, 1, 1, -1, -1)

3.Train a 10-neuron BM on the following 2 examples: (-1, -1, -1, -1, -1, -1, -1, -1, -1, 1) (-1, 1, 1, 1, 1, 1, 1, 1, 1, 1)

4.At the end of training, run the BM 5 times starting from each of the following patterns, and print out the state of the BM (values of all neurons) at the end of each run: (-1, -1, 1, -1, 1, -1, -1, -1, -1, 1) (-1, 1, -1, 1, 1, -1, 1, 1, 1, 1)

Exceptional test (to aim for the max mark) Build patterns representing numbers. You can start from 5x5 or 6x6 grids, draw the numbers, then transform the grids into arrays of 25 or 36 -1 and 1 values (-1 for background, 1 for the number part). 4 or 5 numbers are enough. Train a BM (with 25 or 36 neurons) on the numbers, then try corrupting each of the numbers and run the BM from each of the corrupted numbers a few times. Does the BM correct the corrupted numbers? Elaborate on the results you get. Notice: training a BM with 25-36 units might take several hours (and you may have to try different values for the learning rate, run length, temperature, etc.), so don’t do this on the deadline, if you are counting on it to boost your marks!

What you need to hand in (electronically!) Copy of the whole code. I should be able to compile and run this. Files containing, for both mandatory tests: a.The values of the weights of the BM at the end of each epoch of training b.The states of the BM at the end of each run on the test patterns provided If you run the exceptional test, send me: a file containing the numbers as you drew them; a file containing some report of how training went (for instance, how different are the “awake” and “asleep” components of learning during training? Is this difference decreasing?); a file containing the corrupted numbers you started the trained BM from, and the states of the BM at the end of the runs from these corrupted numbers.

Brief notes on how I would do this (the “pseudo-code” is very close to Perl)

Stuff I need in my BM An integer ($n) attribute/variable with the number of neurons An array$n to store the neuron values (let’s call it $net) An array$n$n containing the weights of the BM ($W) An array$n$n containing the (changes to apply to the weights as a result of training) of the BM ($dw)

I also need something to store the examples and number thereof: how many examples ($P) An array$P$n to store the examples ($examplenumberneuron)

Actions I need to be able to do on my BM

-Create a new BM with any given number of inputs A BM is really just an array of $nx$n weights, and a state of the neurons. So $W and $net as described above define the BM.

-Initialise the weights of the BM to small random values This is trivial. Cycle through all indices of $W and set its values to rand() scaled to be within -0.1,0.1 or so. (If rand() is between 0 and 1, then 0.2(rand()-0.5) does the job.

-Let the BM run from an input pattern until it converges This is a little tricky and there isn’t just one way of doing it, especially because BM depend on a “temperature” parameter. After the neurons of the BM have been set to some values, one needs to cycle through them, check their activations, and flip them with a certain probability, depending on their activation and on the temperature:

for ($q=0;$q<$max_flips;$q++) {
for ($j=0;$j<$n;$j++) {
$z = &activation($j);
$T= some value for the temperature;
if (1/(1+exp(-2$z/$T))>rand()) {
$net$j = 1;
} else {
$net$j = -1;
}
}
}
$max_flips is the number of times all the neurons in the BM are checked to determine if they should flip. A $max_flips in the region of 100 should be OK for the two mandatory tests, but you may need a bigger value for the exceptional test (more neurons). As for the value of the temperature $T, it should be high at the beginning and low at the end. Something like $T=0.1($max_flips-$q)/$max_flips should do.

Computing the activation can be as simple as this:

sub activation($j) {

$z = 0;
for ($i=0;$i<$n;$i++) {
if ($i != $j) {
$z += $W$j$i $net$i;
}
}
return $z; }

-Implement learning This is definitely the trickiest part. The learning equation reads:

Let’s call the term on the left side $dw$i$j. The first part of the equation (the “awake” one) is the following:

This is trivial to implement, for instance:

@dw=();

for ($i=0;$i<$P;$i++) { # for all examples
for ($j=0;$j<$n;$j++) { # for all neurons
for ($k=0;$k<$n;$k++) {
$dw$j$k += $eta$example$i$j$example$i$k;
}
}
}

$eta is the learning rate and should be small (say 0.01 or so).

The second part of the learning equation (the “dreaming” term) is the following:

This term can’t be computed, and needs to be estimated by letting the network run lots of times from random starting points, then computing the sum over all runs of the products between components of the vectors the BM settles into. As rotten as this might sound, an example of code for it can be as simple as the following:

for ($s=0;$s<$samples;$s++) { # “a lot of times”

1. initialise BM to a random start

for ($j=0;$j<$n;$j++) {
if (rand()$net$j=-1;
} else {
$net$j=1;
}
}

1. let the BM evolve ‘til it converges

for ($q=0;$q<$max_flips;$q++) {
for ($j=0;$j<$n;$j++) {
$z = &activation($j);
$T=0.1($max_flips-$q)/$max_flips;
if (1/(1+exp(-2$z/$T))>rand()) {
$net$j = 1;
} else {
$net$j = -1;
}
}
}

1. store the correlations between neuron values in the # final state of the BM. # Note the “-=”, i.e. the BM is un-learning here.

for ($j=0;$j<$n;$j++) {
for ($k=0;$k<$n;$k++) {
$dw$j$k -= $eta$n$net$j$net$k/$samples;
}
}

}

How big should $samples be? 500 or more is a good bet. For the exceptional test you may need to increase this to 1000 or more.

Important suggestion!

Take some time to understand exactly what you are supposed to do, and take some time to plan how to do it. Do not rush coding. You can code the whole assignment in less than 100 lines of code, and in <2 hours, if you know what you are doing.