title: Backpropagation algorithm is stuck in MultiLayer Perceptron
body: <p>I want to implement a MLP (MultiLayer Perceptron) to solve the XOR problem. I am crushing my head on it since a long time because I am not a great scientist, and I want to be sure to understand every line of this program.</p>
  
  <p>I will begin by the questions:</p>
  
  <ol>
  <li>Is there a <strong>specific method for debugging a neural network</strong> ? (such as predefined known weights that lead to an expected solution)</li>
  <li>Is the following <strong>backpropagation algorithm</strong> (in pseudocode) <strong>correct</strong> ?</li>
  <li>Should <strong>the bias</strong> be in this algorithm ? If not, is the bias necessary to solve the XOR problem ? And if yes, should the bias be 1 per neuron, 1 per layer or 1 per network ?</li>
  <li>Is my python implementation correct ? If not, is it about the backpropagation, the forward propagation, the bias absence or otherthing ?</li>
  </ol>
  
  <p>Every response is very welcome. It is not "homework", but if you are very afraid about it, I'll be very happy with only good tips. I still don't use properly numpy, because I'm more a dev than a scientist and have sometimes trouble with matrix equations (I'm currently working on it). Thus, it's very hard for me to well understand the different implementations I found.</p>
  
  <hr>
  
  <p><strong>EDIT :</strong> The algorithm works fine now, and I will highlight the different problems there was in the pseudocode / python implementation:</p>
  
  <p><strong>The theory</strong>:</p>
  
  <ul>
  <li>The <strong>pseudocode was wrong</strong> at the weights adjustement (I edited the code to mark the line WRONG with fix). I used the output layer outputs where I should use the inputs value</li>
  <li>It is effectively <strong>possible to solve the XOR problem without bias</strong> and only 1 hidden layer. What is interesting here is that it only works with 4 neurons in hidden layer or more, but not with 3. However, after benchmarks, adding the bias can considerably accelerate the time to optimum convergence (5x speeder or more)</li>
  </ul>
  
  <p><strong>The python implementation</strong>:</p>
  
  <ul>
  <li>The weights were initialized randomly between 0 and 1 and not between -1 and 1, it couldn't work like this.</li>
  </ul>
  
  <p>Finally, <a href="http://neuralnetworksanddeeplearning.com/chap1.html" rel="nofollow noreferrer">this resource</a> was a big help to understand well the "neurons magic". It didn't help me to debug backpropagation, but it's now evidence that I could never make it work without more theorical knowledges. If, as me, you're more a dev than a scientist, I highly encourage you to check it out.</p>
  
  <hr>
  
  <p>Based on the book "<em>Artifical intelligence for developers</em>" by Virginie MATHIVET, here is the <strong>pseudocode for Backpropagation algorithm</strong> (it's a french book, sorry for bad traductions):</p>
  
  <pre><code>While stop criteria is not achieved:
      Initialize d(i)
  
      For each example:
          Compute output value s(i)                          #1
  
          For each output neuron weight:                     #2
              d(i) = s(i) * (1 - s(i)) * (y(i) - s(i))
          EndFor
  
          For each hidden neuron weight:
              sum = 0
              For each link towards output neuron k:
                  sum += d(k) * w(i-&gt;k)
              EndFor
              d(i) = o(i) * (1 - o(i)) * sum
          EndFor
  
          For each weight of the network:
              If link towards output neuron:
                  w(i) += rate * d(i) * o(i)
              Else
                  w(i) += rate * d(i) * s(i) # WRONG: s(i) should be input(i)
              EndIf
          EndFor
      EndFor
  EndWhile
  </code></pre>
  
  <p>In the above, <code>d(x)</code> are the deltas, <code>o(x)</code> are the hidden layer outputs, <code>s(x)</code> are the output layer outputs, <code>y(x)</code> are the expected outputs and <code>w(x)</code> are the network weights.</p>
  
  <p>I understand that line <strong>#1</strong> is the <strong>forward propagation</strong>, and the lines after <strong>#2</strong> (included) are about <strong>backpropagation</strong>. Thus, the proper algorithm can be written as:</p>
  
  <pre><code>While stop criteria is not achieved:
      Initialize d(i)
  
      For each example:
          output = Forward propagation with example inputs                  #1
          Backpropagation of the error between output and expected output   #2
      EndFor
  EndWhile
  </code></pre>
  
  <p>My problem is that <strong>the algorithm seems to go in circles</strong> with the backpropagation algorithm and the weights changes, for example here are the outputs for the hidden layer:</p>
  
  <pre><code>[Epoch 0, inputs (1.0, 1.0)]: hidden outputs: None
  [Epoch 0, inputs (0.0, 0.0)]: hidden outputs: [ 0.7755638   0.64556638  0.68163599]
  [Epoch 0, inputs (1.0, 0.0)]: hidden outputs: [ 0.5  0.5  0.5]
  [Epoch 0, inputs (0.0, 1.0)]: hidden outputs: [ 0.60747218  0.58975313  0.55246625]
  [Epoch 1, inputs (1.0, 1.0)]: hidden outputs: [ 0.68911554  0.55079694  0.62718831]
  [Epoch 1, inputs (1.0, 0.0)]: hidden outputs: [ 0.77449528  0.64107552  0.67770194]
  [Epoch 1, inputs (0.0, 0.0)]: hidden outputs: [ 0.60728756  0.58957687  0.55230354]
  [Epoch 1, inputs (0.0, 1.0)]: hidden outputs: [ 0.5  0.5  0.5]
  [Epoch 2, inputs (0.0, 0.0)]: hidden outputs: [ 0.68877278  0.54872848  0.6254074 ]
  [Epoch 2, inputs (1.0, 0.0)]: hidden outputs: [ 0.5  0.5  0.5]
  [Epoch 2, inputs (1.0, 1.0)]: hidden outputs: [ 0.60700878  0.58812487  0.5509695 ]
  [Epoch 2, inputs (0.0, 1.0)]: hidden outputs: [ 0.77344667  0.63591436  0.67311723]
  [Epoch 3, inputs (0.0, 0.0)]: hidden outputs: [ 0.68856723  0.54708942  0.62400827]
  [Epoch 3, inputs (1.0, 0.0)]: hidden outputs: [ 0.5  0.5  0.5]
  </code></pre>
  
  <p>Putting the examples in random order do not change anything. Moreover, I tried every learning rates (0.05 to 0.95) with the same result, so I think it's not about bad convergence. Here is my Python implementation:</p>
  
  <pre><code>def sigmoid(x):
      return 1 / (1 + np.exp(-x))
  
  def dsigmoid(y):
      return y * (1.0 - y)
  
  class NeuralNetwork:
  
      def __init__(self, nb_inputs, nb_hidden, nb_outputs, learning_rate):
          self.nb_inputs = nb_inputs
          self.nb_hidden = nb_hidden
          self.nb_outputs = nb_outputs
          self.learning_rate = learning_rate
  
          self.output_deltas = None
          self.output_weights = np.random.random((nb_outputs, nb_hidden)) # WRONG: should be between -1 and 1, not 0 and 1
          self.outputs = None
          self.hidden_deltas = None
          self.hidden_weights = np.random.random((nb_hidden, nb_inputs)) # WRONG: should be between -1 and 1, not 0 and 1
          self.hidden_outputs = None
  
      def forward_propagation(self, inputs):
          self.hidden_outputs = np.zeros((self.nb_hidden,))
          self.outputs = np.zeros((self.nb_outputs,))
  
          # get outputs for hidden layer
          for i in range(self.nb_hidden):
              aggregated = sum([inputs[j] * self.hidden_weights[i][j] for j in range(self.nb_inputs)])
              self.hidden_outputs[i] = sigmoid(aggregated)
  
          # get inputs for output layer
          for i in range(self.nb_outputs):
              aggregated = sum([self.hidden_outputs[j] * self.output_weights[i][j] for j in range(self.nb_hidden)])
              self.outputs[i] = sigmoid(aggregated)
  
      def backpropagation(self, expected_outputs):
  
          # find deltas for output layer 
          for i in range(self.nb_outputs):
              for j in range(self.nb_hidden):
                  self.output_deltas[i][j] = dsigmoid(self.outputs[i]) * (expected_outputs[i] - self.outputs[i])
  
          # find deltas for hidden layer
          for i in range(self.nb_hidden):
              for j in range(self.nb_inputs):
                  total = 0.0
                  for k in range(self.nb_outputs):
                      total += self.output_deltas[k][i] * self.output_weights[k][i]
                  self.hidden_deltas[i][j] = dsigmoid(self.hidden_outputs[i]) * total
  
          # change weights for output layer
          for i in range(self.nb_outputs):
              for j in range(self.nb_hidden):
                  self.output_weights[i][j] += self.learning_rate * self.output_deltas[i][j] * self.outputs[i] # WRONG: should be self.hidden_outputs[j]
  
          # change weights for inputs layer
          for i in range(self.nb_hidden):
              for j in range(self.nb_inputs):
                  self.hidden_weights[i][j] += self.learning_rate * self.hidden_deltas[i][j] * self.hidden_outputs[i] # WRONG: should be inputs[j]
  
      def train(self, data, nb_iterations):
          for i in range(nb_iterations):
              # Init deltas
              self.output_deltas = np.zeros((self.nb_outputs, self.nb_hidden), dtype=np.float64)
              self.hidden_deltas = np.zeros((self.nb_hidden, self.nb_inputs), dtype=np.float64)
  
              # Train on examples with different orders
              for inputs, expected_output in sorted(data.items(), key=lambda x: random.random()):
                  expected_outputs = np.array([expected_output])
  
                  self.forward_propagation(inputs)
                  self.backpropagation(expected_outputs) # WRONG: need inputs: backpropagation(inputs, expected_outputs)
  
      def predict(self, inputs):
          self.forward_propagation(inputs)
          return self.outputs
  </code></pre>