C#: backpropagation learns XOR

Before you start

C# arrays and Math functions; the XOR forward-pass idea.

Train a 2-2-1 sigmoid network by gradient descent until it computes XOR.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

Backpropagation computes how the loss changes with each weight by applying the chain rule from the output back to the inputs. For a sigmoid unit with output a, the derivative is a·(1 − a). The output error signal is (a − target)·a·(1 − a), and each hidden unit's signal is its share of the output signal, passed back through the weight and its own derivative.

Gradient descent then nudges every weight by −rate × signal × input. The network has two inputs, two hidden sigmoid units, and one output. Because XOR is not linearly separable, the hidden layer is necessary. The starting weights are fixed so the run is repeatable. Training from random starting weights can occasionally get stuck, and then it is restarted.

Code example

using System;
using System.Globalization;

class Program {
  static double Sigmoid(double z) {
    return 1.0 / (1.0 + Math.Exp(-z));
  }

  static void Main() {
    double[,] inputs = { { 0, 0 }, { 0, 1 }, { 1, 0 }, { 1, 1 } };
    double[] targets = { 0, 1, 1, 0 };
    double[,] w1 = { { 0.5, -0.4 }, { 0.9, 0.7 } };
    double[] b1 = { 0.1, -0.3 };
    double[] w2 = { 0.8, -0.6 };
    double b2 = 0.2;
    double rate = 0.5;

    for (int epoch = 0; epoch < 20000; epoch++) {
      for (int n = 0; n < 4; n++) {
        double[] h = new double[2];
        for (int j = 0; j < 2; j++) {
          h[j] = Sigmoid(inputs[n, 0] * w1[0, j] + inputs[n, 1] * w1[1, j] + b1[j]);
        }
        double o = Sigmoid(h[0] * w2[0] + h[1] * w2[1] + b2);

        double dOut = (o - targets[n]) * o * (1 - o);
        for (int j = 0; j < 2; j++) {
          double dHidden = dOut * w2[j] * h[j] * (1 - h[j]);
          w2[j] -= rate * dOut * h[j];
          w1[0, j] -= rate * dHidden * inputs[n, 0];
          w1[1, j] -= rate * dHidden * inputs[n, 1];
          b1[j] -= rate * dHidden;
        }
        b2 -= rate * dOut;
      }
    }

    for (int n = 0; n < 4; n++) {
      double[] h = new double[2];
      for (int j = 0; j < 2; j++) {
        h[j] = Sigmoid(inputs[n, 0] * w1[0, j] + inputs[n, 1] * w1[1, j] + b1[j]);
      }
      double o = Sigmoid(h[0] * w2[0] + h[1] * w2[1] + b2);
      Console.WriteLine(inputs[n, 0] + " XOR " + inputs[n, 1] + " -> " + Math.Round(o) + " (" + o.ToString("F3", CultureInfo.InvariantCulture) + ")");
    }
  }
}

Output

0 XOR 0 -> 0 (0.013)
0 XOR 1 -> 1 (0.989)
1 XOR 0 -> 1 (0.989)
1 XOR 1 -> 0 (0.011)

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1using System;

2using System.Globalization;

4class Program {

5 static double Sigmoid(double z) {

6 return 1.0 / (1.0 + Math.Exp(-z));

7 }

9 static void Main() {

10 double[,] inputs = { { 0, 0 }, { 0, 1 }, { 1, 0 }, { 1, 1 } };

11 double[] targets = { 0, 1, 1, 0 };

12 double[,] w1 = { { 0.5, -0.4 }, { 0.9, 0.7 } };

13 double[] b1 = { 0.1, -0.3 };

14 double[] w2 = { 0.8, -0.6 };

15 double b2 = 0.2;

16 double rate = 0.5;

18 for (int epoch = 0; epoch < 20000; epoch++) {

19 for (int n = 0; n < 4; n++) {

20 double[] h = new double[2];

21 for (int j = 0; j < 2; j++) {

22 h[j] = Sigmoid(inputs[n, 0] * w1[0, j] + inputs[n, 1] * w1[1, j] + b1[j]);

23 }

24 double o = Sigmoid(h[0] * w2[0] + h[1] * w2[1] + b2);

26 double dOut = (o - targets[n]) * o * (1 - o);

27 for (int j = 0; j < 2; j++) {

28 double dHidden = dOut * w2[j] * h[j] * (1 - h[j]);

29 w2[j] -= rate * dOut * h[j];

30 w1[0, j] -= rate * dHidden * inputs[n, 0];

31 w1[1, j] -= rate * dHidden * inputs[n, 1];

32 b1[j] -= rate * dHidden;

33 }

34 b2 -= rate * dOut;

35 }

36 }

38 for (int n = 0; n < 4; n++) {

39 double[] h = new double[2];

40 for (int j = 0; j < 2; j++) {

41 h[j] = Sigmoid(inputs[n, 0] * w1[0, j] + inputs[n, 1] * w1[1, j] + b1[j]);

42 }

43 double o = Sigmoid(h[0] * w2[0] + h[1] * w2[1] + b2);

      Console.WriteLine(inputs[n, 0] + " XOR " + inputs[n, 1] + " -> " + Math.Round(o) + " (" + o.ToString("F3", CultureInfo.InvariantCulture) + ")");

45 }

46 }

47}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
A moderate learning rate for a tiny network.	`—`	—
Output error signal: error times the sigmoid derivative.	`dOut = (o − t)·o·(1 − o)`	—
Pass the signal back through the output weight and the hidden unit's derivative.	`chain rule`	—
Update the output weight before the hidden weights change further.	`weights move downhill`	—
After training, the outputs round to 0, 1, 1, 0.	`weights move downhill`	0 XOR 0 -> 0 (0.013) 0 XOR 1 -> 1 (0.989) 1 XOR 0 -> 1 (0.989) 1 XOR 1 -> 0 (0.011)

Behind the scenes

How C# processes this code

C# compiles to code for the .NET runtime, which invokes the program entry point.

Cost and common mistakes

O(epochs · n · weights) for this tiny network.

Training can stall at a poor solution for some initial weights. Random restarts or better initialisation helps.
The hidden-layer error signal must use the output weight from before it is updated. Here dHidden is computed before w2[j] changes, which is the correct order.
Verify gradients numerically (a gradient check) when you write backpropagation by hand.

Try it yourself

What breaks if the sigmoid is replaced by a linear function?

Reveal answer and reasoning

The whole network collapses to a single linear map, which cannot represent XOR.