title: Backpropagation Algorithm Implementation
body: <p>I'm following <a href="http://msdn.microsoft.com/en-us/magazine/jj658979.aspx" rel="nofollow">this article</a>. I'm using the article to understand the logic, but I've implemented it differently using <code>structs</code>. </p>
  
  <h1>The problem</h1>
  
  <p>The problem is that it never converges to the desired outputs. I don't get the output that I want. Which means that the weights are not updated correctly. If I train the network for a sufficiently large number of times, the output stop changing, which means the weights don't get updated so the network thinks that it has got the correct weights, but the output shows otherwise.</p>
  
  <p>Each neuron holds an array of <code>Paths</code>. Weight is a property of <code>Path</code> and the <code>Neurons</code> can send values 'down a' <code>Path</code> and it gets to the <code>Neuron</code> on the other side.</p>
  
  <p>Below is the code...</p>
  
  <pre><code>const double e =2.7182818284;
  </code></pre>
  
  <p>Neuron:</p>
  
  <pre><code>struct Neuron{
  
  double value;   //Local input
  double bias;
  double gradient;
  double out; //Output value
  Path *p;    //path array 
  int nc; //number of paths/connections belonging to *this
  
  
  
  };
  </code></pre>
  
  <p>Path:</p>
  
  <pre><code>struct Path{
      double weight;
      double prevDelta;
      double delta;
      int nid;    //neuron id in *n
  };
  </code></pre>
  
  <p><code>Layers</code> contain <code>Neurons</code>. <code>Paths</code> identify <code>Neurons</code> with an integer <code>nid</code>, which is the index of the <code>Neuron</code> array in the neighboring <code>Layer</code>.</p>
  
  <p>Layer:</p>
  
  <pre><code>struct Layer{
  
      int nneurons;   //number of neurons in cluster/layer
      Neuron *n;   //Local Neuron array to reference
      Layer *neighbor;
  
  
      void Transfer(int nid)  //compute target Neuron's input and assign it to it
  
      {
  
          double valueOut=0;
          Neuron *temp;
          temp=&amp;n[nid];
  
          //for each connection, send w*v to paired neuron
          for(int i=0; i&lt;n[nid].nc; i++)
          {
              valueOut=temp-&gt;p[i].weight * temp-&gt;out;
  
              //neuron nid(as referenced by p[]), which is in the other layer, receives the value
              neighbor-&gt;n[temp-&gt;p[i].nid].value+=valueOut;
  
          }
  
  
      }
  
      void Initialize(int size)
      {
  
              nneurons=size;
              n=new Neuron[nneurons];
  
              for(int i=0; i&lt;nneurons; i++)
              {
                  n[i].value=0.0;
                  n[i].bias=1.0;
                  n[i].out=0.0;
  
              }
  
      }
  
      void FormConnections(Layer&amp; nl)//with neighboring layer
      {
          neighbor=&amp;nl;
  
          int nCon=neighbor-&gt;nneurons;
  
          for(int i=0; i&lt;nneurons; i++)
          {
  
              n[i].nc=nCon;
              n[i].p=new Path[nCon];
  
              //neuron 'i' will link its paths to neurons in the other layer
              for(int ii=0; ii&lt;n[i].nc; ii++)
              {
                  n[i].p[ii].weight=1.0;
                  n[i].p[ii].prevDelta=0.0;
                  n[i].p[ii].nid=ii;
  
              }
  
          }
  
      }
  
  };
  </code></pre>
  
  <p>Brain(the Neural Network):</p>
  
  <pre><code> class Brain{
     public:
  
  double eta;
  double alpha;
  Layer   input,
          hidden,
          output;
  
  double *target;
  
  void GetInput(double* in){
      for(int i=0; i&lt;input.nneurons; i++)
          input.n[i].value=in[i];
  
  }
  
  void GetDesiredOutput(double* t)
  {
      target=t;
  }
  
  void Initialize(int inputsize, int hiddensize, int outputsize)
  {
      input.Initialize(inputsize);
      hidden.Initialize(hiddensize);
      output.Initialize(outputsize);
  
      input.FormConnections(hidden);
      hidden.FormConnections(output);
  
  }
  
  void BP()
  {
  
      //Calculate gradients for output
      for(int i=0; i&lt;output.nneurons; i++)
      {output.n[i].gradient=(target[i] - output.n[i].out) * (1 - output.n[i].out) * (1 + output.n[i].out);}
  
      Neuron* temp;
      for(int i=0; i&lt;hidden.nneurons; i++)
          {
              temp=&amp;hidden.n[i];
              temp-&gt;gradient=0;
              //for each connection...
              for(int ii=0; ii&lt;hidden.n[i].nc; ii++)
              {
                  //temp's gradient gets values in the form w1*g2 + w2*g2 + ... + wn*gn,
                  //where w is the weight of p that leads to output.n[i] from temp(hidden), and g
                  //is the gradient of that output at p[CurrentConnection].nid
  
                  temp-&gt;gradient+= temp-&gt;p[ii].weight * output.n[temp-&gt;p[ii].nid].gradient;
              }
  
              //Multiply the resultant sums with d/dx S(x)
              temp-&gt;gradient*= (temp-&gt;out)*(1-temp-&gt;out);
  
  
          }
      /
  
  /---------------------------------------------------------------------------
          //Calculate delta
  
          for(int i=0; i&lt;input.nneurons; i++)
          {
              temp=&amp;input.n[i];
  
              //temp-&gt;bias=eta*temp-&gt;gradient;
  
              for(int ii=0; ii&lt;input.n[i].nc; ii++)
              {   
                  temp-&gt;p[ii].delta=eta* hidden.n[temp-&gt;p[ii].nid].gradient* temp-&gt;value;
                  temp-&gt;p[ii].weight=temp-&gt;p[ii].prevDelta*alpha+temp-&gt;p[ii].delta;
                  temp-&gt;p[ii].prevDelta=temp-&gt;p[ii].delta;
              }
          }
  
          for(int i=0; i&lt;hidden.nneurons; i++)
          {
              temp=&amp;hidden.n[i];
  
              temp-&gt;bias=eta*temp-&gt;gradient;
  
              for(int ii=0; ii&lt;hidden.n[i].nc; ii++)
              {   temp-&gt;p[ii].delta=eta* output.n[temp-&gt;p[ii].nid].gradient* temp-&gt;value;
                  temp-&gt;p[ii].weight=temp-&gt;p[ii].prevDelta*alpha+temp-&gt;p[ii].delta;
                  temp-&gt;p[ii].prevDelta=temp-&gt;p[ii].delta;
              }
  
          }
  
          for(int i=0; i&lt;output.nneurons; i++)
          {
              temp=&amp;output.n[i];
  
              temp-&gt;bias=eta*temp-&gt;gradient;
          }
      Zero(hidden);
      Zero(output);
      }
  
      void Process()
      {
          for(int i=0; i&lt;input.nneurons; i++)
          {   input.n[i].out=input.n[i].value;
              input.Transfer(i);//transfer each neuron data in input to hidden
          }
          for(int i=0; i&lt;hidden.nneurons; i++)
          {
  
              hidden.n[i].out=Sigmoid(hidden.n[i].value + hidden.n[i].bias);
  
              hidden.Transfer(i);
          }
  
          for(int i=0; i&lt;output.nneurons; i++)
          {
  
              output.n[i].out=HyperTan(output.n[i].value + output.n[i].bias);
              cout&lt;&lt;"Output "&lt;&lt;i&lt;&lt;": "&lt;&lt;output.n[i].out&lt;&lt;endl;
          }
  
  
      }
  
      void Zero(Layer &amp;l){ for(int i=0; i&lt;l.nneurons; i++) l.n[i].value=0.0;}
      void Randomize(Layer &amp;l)
      {
          for(int i=0; i&lt;l.nneurons; i++)
          {
              for(int ii=0; ii&lt;l.n[i].nc; ii++)
              {
                  l.n[i].p[ii].weight=rand()%100/10;
  
              }
          }
      }
      Brain(){eta=0.9; alpha=0.4;}
  
       double Sigmoid(double x)
    {
      if (x &lt; -45.0) return 0.0;
      else if (x &gt; 45.0) return 1.0;
      else return (1.0 / (1.0 + pow(e, -x)));
    }
    double HyperTan(double x)
    {
      if (x &lt; -10.0) return -1.0;
      else if (x &gt; 10.0) return 1.0;
      else return tanh(x);
    }
  };
  </code></pre>
  
  <p>A typical program would be:</p>
  
  <pre><code>Brain b;
  
  double data[]={1.0,2.0, 3.0};
  double ddata[]={-0.25,0.14};
  
  
  
  b.Initialize(3,4,2);
  
  b.GetDesiredOutput(ddata);
  b.GetInput(data);
  
  
  b.Process();
  b.BP();
  </code></pre>
  
  <p>Example:
  eta= 0.9, alpha= 0.4
   for input 1.0, 2.0, 3.0 </p>
  
  <p>I get:</p>
  
  <blockquote>
    <p>-0.117471 and 0.0661122 </p>
  </blockquote>
  
  <p>The expected output is:</p>
  
  <blockquote>
    <p>-0.25, 0.14</p>
  </blockquote>
  
  <p><strong>UPDATE(25/12/2013):</strong>
  The problem was in calculating the delta values for hidden-to-output weights, and there was an additional error when updating the weights using these new deltas, which all take place in the same for loop. I simply assigned the new weights, while I was supposed to <em>add</em> them to the previous weights.</p>