Perceptron; neural network as XOR gate

A perceptron is a single neuron that outputs 1 when the weighted sum of its inputs reaches a threshold, otherwise 0; it is a linear classifier.

A single perceptron cannot do XOR

For output 1 on (0,1) and (1,0) and 0 on (0,0) and (1,1) we need: 0 < θ, w1 ≥ θ, w2 ≥ θ, w1 + w2 < θ. But w1, w2 ≥ θ > 0 gives w1 + w2 ≥ 2θ > θ, a contradiction. The points are not linearly separable (no single straight line separates them).

Two-layer design

XOR = (x1 AND NOT x2) OR (NOT x1 AND x2). Use a hidden layer of two perceptrons and one output perceptron (step: fire if net ≥ 1).

 x1 --(+1)--> [h1] --(+1)-->\
    \  /(-1)                 [ y ]
     \/                      /
     /\  (-1)               /
 x2 --(+1)--> [h2] --(+1)--/

• h1: weights x1 = +1, x2 = −1, threshold 1 (computes x1 AND NOT x2)
• h2: weights x1 = −1, x2 = +1, threshold 1 (computes NOT x1 AND x2)
• y: weights h1 = +1, h2 = +1, threshold 1 (h1 OR h2)

The outputs 0, 1, 1, 0 match XOR (checked by program).

Answer: XOR needs a multilayer perceptron with one hidden layer; the hidden layer transforms the inputs into a linearly separable form. Such networks are trained by back-propagation.