Artificial Intelligence Neural Network Backpropagation

A demostration of a multilayer neural network with backpropagation.

Neural Network with Backpropagation.

Date: 30-jan-2010

Backpropagation with php: this script implements the backpropagation algorithm in php, solving the XOR problem.

To solve our XOR problem here, knowing that a XOR problem is the logical solution to lines like 1 XOR 0=1, or 1 XOR 0=YES, we are going to  use a neural network.
To know more about a network you need to find good tutorials or books and I will write a small one here to.

We'll give an input data with the answers where our aray(1,0,1) means 1 XOR 0=yes, and we'll also give and the test data where our array (1,0) means 1 XOR 0=? to test the wisdom of our network.

You can check the original source code in C++ here:
http://www.codeproject.com/KB/recipes/BP.aspx

Written by: Tejpal Singh Chhabra

Ok, let's go with the the code:

/**
Exclusive OR (XOR)

0 XOR 0 = 0 (no)
1 XOR 0 = 1 (yes)
0 XOR 1 = 1 (yes)
1 XOR 1 = 0 (no)

The rule: Say yes if the first one is 0 or the second is 1,
but not both.

TODO Scale data for values beyond 0 and 1.

By freedelta freedelta.free.fr January-2010
*/
error_reporting(E_STRICT);
define("_RAND_MAX",32767);

class BackPropagation
{
/* Output of each neuron */
public $output=null;

/* delta error value for each neuron */
public $delta=null;

/* Array of weights for each neuron */
public $weight=null;

/* Num of layers in the net, including input layer */
public $numLayers=null;

/* Array num elments containing size for each layer */
public $layersSize=null;

/* Learning rate */
public $beta=null;

/* Momentum */
public $alpha=null;

/* Storage for weight-change made in previous epoch (three-dimensional array) */
public $prevDwt=null;

/* Data */
public $data=null;

/* Test Data */
public $testData=null;

/* N lines of Data */
public $NumPattern=null;

/* N columns in Data */
public $NumInput=null;


public function __construct($numLayers,$layersSize,$beta,$alpha)
{
$this->alpha=$alpha;
$this->beta=$beta;

// Set no of layers and their sizes
$this->numLayers=$numLayers;
$this->layersSize=$layersSize;

// Seed and assign random weights
for($i=1;$i<$this->numLayers;$i++)
{
for($j=0;$j<$this->layersSize[$i];$j++)
{
for($k=0;$k<$this->layersSize[$i-1]+1;$k++)
{
$this->weight[$i][$j][$k]=$this->rando();
}
// bias in the last neuron
$this->weight[$i][$j][$this->layersSize[$i-1]]=-1;
}
}

// initialize previous weights to 0 for first iteration
for($i=1;$i<$this->numLayers;$i++)
{
for($j=0;$j<$this->layersSize[$i];$j++)
{
for($k=0;$k<$this->layersSize[$i-1]+1;$k++)
{
$this->prevDwt[$i][$j][$k]=(double)0.0;
}
}
}

/*
// Note that the following variables are unused,
//
// delta[0]
// weight[0]
// prevDwt[0]

// I did this intentionaly to maintains consistancy in numbering the layers.
// Since for a net having n layers, input layer is refered to as 0th layer,
// first hidden layer as 1st layer and the nth layer as outputput layer. And
// first (0th) layer just stores the inputs hence there is no delta or weigth
// values corresponding to it.
*/
}

public function rando()
{
return (double)(rand())/(_RAND_MAX/2) - 1;//32767
}

// sigmoid function
public function sigmoid($inputSource)
{
return (double)(1.0 / (1.0 + exp(-$inputSource)));
}

// mean square error
public function mse($target)
{
$mse=0;

for($i=0;$i<$this->layersSize[$this->numLayers-1];$i++)
{
$mse+=($target-$this->output[$this->numLayers-1][$i])*($target-$this->output[$this->numLayers-1][$i]);
}
return $mse/2;
}

// returns i'th outputput of the net
public function Out($i)
{
return $this->output[$this->numLayers-1][$i];
}

// Feed forward one set of input
// to update the output values for each neuron.
// This function takes the input to the net and finds the output of each neuron
public function ffwd($inputSource)
{
$sum=0.0;

// assign content to input layer
for($i=0;$i<$this->layersSize[0];$i++)
{
$this->output[0][$i]=$inputSource[$i]; // outputput_from_neuron(i,j) Jth neuron in Ith Layer
}

// assign output (activation) value to each neuron usng sigmoid func
for($i=1;$i<$this->numLayers;$i++) // For each layer
{
for($j=0;$j<$this->layersSize[$i];$j++) // For each neuron in current layer
{
$sum=0.0;
for($k=0;$k<$this->layersSize[$i-1];$k++) // For each input from each neuron in preceeding layer
{
$sum+=$this->output[$i-1][$k]*$this->weight[$i][$j][$k]; // Apply weight to inputs and add to sum
}
// Apply bias
$sum+=$this->weight[$i][$j][$this->layersSize[$i-1]];
// Apply sigmoid function
$this->output[$i][$j]=$this->sigmoid($sum);
}
}
}

/* --- Backpropagate errors from outputput layer back till the first hidden layer */
public function bpgt($inputSource,$target)
{
/* --- Update the output values for each neuron */
$this->ffwd($inputSource);

///////////////////////////////////////////////
/// FIND DELTA FOR OUPUT LAYER (Last Layer) ///
///////////////////////////////////////////////

for($i=0;$i<$this->layersSize[$this->numLayers-1];$i++)
{
$this->delta[$this->numLayers-1][$i]=$this->output[$this->numLayers-1][$i]*(1-$this->output[$this->numLayers-1][$i])*($target-$this->output[$this->numLayers-1][$i]);
}

/////////////////////////////////////////////////////////////////////////////////////////////
/// FIND DELTA FOR HIDDEN LAYERS (From Last Hidden Layer BACKWARDS To First Hidden Layer) ///
/////////////////////////////////////////////////////////////////////////////////////////////

for($i=$this->numLayers-2;$i>0;$i--)
{
for($j=0;$j<$this->layersSize[$i];$j++)
{
$sum=0.0;
for($k=0;$k<$this->layersSize[$i+1];$k++)
{
$sum+=$this->delta[$i+1][$k]*$this->weight[$i+1][$k][$j];
}
$this->delta[$i][$j]=$this->output[$i][$j]*(1-$this->output[$i][$j])*$sum;
}
}

////////////////////////
/// MOMENTUM (Alpha) ///
////////////////////////

for($i=1;$i<$this->numLayers;$i++)
{
for($j=0;$j<$this->layersSize[$i];$j++)
{
for($k=0;$k<$this->layersSize[$i-1];$k++)
{
$this->weight[$i][$j][$k]+=$this->alpha*$this->prevDwt[$i][$j][$k];
}
$this->weight[$i][$j][$this->layersSize[$i-1]]+=$this->alpha*$this->prevDwt[$i][$j][$this->layersSize[$i-1]];
}
}

///////////////////////////////////////////////
/// ADJUST WEIGHTS (Using Steepest Descent) ///
///////////////////////////////////////////////

for($i=1;$i<$this->numLayers;$i++)
{
for($j=0;$j<$this->layersSize[$i];$j++)
{
for($k=0;$k<$this->layersSize[$i-1];$k++)
{
$this->prevDwt[$i][$j][$k]=$this->beta*$this->delta[$i][$j]*$this->output[$i-1][$k];
$this->weight[$i][$j][$k]+=$this->prevDwt[$i][$j][$k];
}
/* --- Apply the corrections */
$this->prevDwt[$i][$j][$this->layersSize[$i-1]]=$this->beta*$this->delta[$i][$j];
$this->weight[$i][$j][$this->layersSize[$i-1]]+=$this->prevDwt[$i][$j][$this->layersSize[$i-1]];
}
}
}

public function Run($data,$testData)
{
/* --- Threshhold - thresh (value of target mse, training stops once it is achieved) */
$Thresh = 0.0001;
$numEpoch = 200000;
$MSE=0.0;
$NumPattern=count($data); // Lines
$NumInput=count($data[0]); // Columns

/* --- Start training: looping through epochs and exit when MSE error < Threshold */
echo "\nNow training the network....";

for($e=0;$e<$numEpoch;$e++)
{
/* -- Backpropagate */
$this->bpgt($data[$e%$NumPattern],$data[$e%$NumPattern][$NumInput-1]);

$MSE=$this->mse($data[$e%$NumPattern][$NumInput-1]);
if($e==0)
{
echo "\nFirst epoch Mean Square Error: $MSE";
}

if( $MSE < $Thresh)
{
echo "\nNetwork Trained. Threshold value achieved in ".$e." iterations.";
echo "\nMSE: ".$MSE;
break;
}
}

echo "\nLast epoch Mean Square Error: $MSE";

echo "\nNow using the trained network to make predictions on test data....";

for ($i = 0 ; $i < $NumPattern; $i++ )
{
$this->ffwd($testData[$i]);

echo "\n";

for($j=0;$j<$NumInput-1;$j++)
{
echo $testData[$i][$j]." ";
}

echo (double)$this->Out(0);
}

echo "\nThat's it\n";
}

}

/* --- Sample use */

// prepare XOR traing data
$data=array(0=>array(0, 0, 0, 0),
1=>array(0, 0, 1, 1),
2=>array(0, 1, 0, 1),
3=>array(0, 1, 1, 0),
4=>array(1, 0, 0, 1),
5=>array(1, 0, 1, 0),
6=>array(1, 1, 0, 0),
7=>array(1, 1, 1, 1)
);

// prepare test =(data-last output values)
$testData=array(0=>array(0, 0, 0),
1=>array(0, 0, 1),
2=>array(0, 1, 0),
3=>array(0, 1, 1),
4=>array(1, 0, 0),
5=>array(1, 0, 1),
6=>array(1, 1, 0),
7=>array(1, 1, 1)
);
/**
* Defining a net with 4 layers having 3,3,3, and 1 neuron respectively,
* the first layer is input layer i.e. simply holder for the input parameters
* and has to be the same size as the no of input parameters, in out example 3
*/

$layersSize=array(3,3,3,1);
$numLayers = count($layersSize);

// Learning rate - beta
// momentum - alpha
$beta = 0.3;
$alpha = 0.1;

// Creating the net
$bp=new BackPropagation($numLayers,$layersSize,$beta,$alpha);
$bp->Run($data,$testData);

Executing this code will give:

First epoch Mean Square Error: 0.020493650125507
Network Trained. Threshold value achieved in 106696 iterations.
MSE:  9.9954706060445E-5
Last epoch Mean Square Error: 9.9954706060445E-5
Now using the trained network to make predictions on test data....
0  0  0  0.014122508160492
0  0  1  0.97961479190357
0  1  0  0.97215511535403
0  1  1  0.022484255210202
1  0  0  0.9738970157648
1  0  1  0.024623634539114
1  1  0  0.017959480755274
1  1  1  0.98062703774023

You only need to round the last values to get the 0,1 answers
That's it