The perceptron and linear separability
Train a single artificial neuron with the perceptron rule, and see why it cannot learn XOR.
def train_perceptron(data, epochs=20):
w = [0, 0]
b = 0
for _ in range(epochs):
mistakes = 0
for (x1, x2), target in data:
output = 1 if w[0] * x1 + w[1] * x2 + b > 0 else 0
error = target - output
if error:
w[0] += error * x1
w[1] += error * x2
b += error
mistakes += 1
if mistakes == 0:
return w, b, True
return w, b, False
AND = [((0, 0), 0), ((0, 1), 0), ((1, 0), 0), ((1, 1), 1)]
XOR = [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 0)]
print(train_perceptron(AND))
print(train_perceptron(XOR)[2])([2, 1], -2, True) False
Explanation
The perceptron, introduced by Frank Rosenblatt in 1958, is the simplest artificial neuron. It computes a weighted sum of its inputs plus a bias and outputs 1 if the sum is above zero, and 0 otherwise. Geometrically it draws a line, or in higher dimensions a hyperplane, and classifies points by which side they fall on.
The perceptron learning rule adjusts the weights only when the neuron makes a mistake. For each wrong prediction it adds error × input to each weight and error to the bias, where error is the target minus the output. The perceptron convergence theorem guarantees that if the classes can be separated by a line, this procedure finds a separating line in a finite number of mistakes.
The AND function is linearly separable, so the program finds weights (2, 1) and bias −2 and stops when an entire pass makes no mistakes. XOR is not linearly separable: no single line puts (0,1) and (1,0) on one side and (0,0) and (1,1) on the other, so the rule never reaches a pass with zero mistakes, and the program reports False after its limit of 20 passes. This limitation, emphasized by Minsky and Papert in 1969, is the reason networks with hidden layers are needed.
Explore the dry run
def train_perceptron(data, epochs=20): w = [0, 0] b = 0 for _ in range(epochs): mistakes = 0 for (x1, x2), target in data: output = 1 if w[0] * x1 + w[1] * x2 + b > 0 else 0 error = target - output if error: w[0] += error * x1 w[1] += error * x2 b += error mistakes += 1 if mistakes == 0: return w, b, True return w, b, False AND = [((0, 0), 0), ((0, 1), 0), ((1, 0), 0), ((1, 1), 1)]XOR = [((0, 0), 0), ((0, 1), 1), ((1, 0), 1), ((1, 1), 0)]print(train_perceptron(AND))print(train_perceptron(XOR)[2])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
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| The neuron's output: 1 when the weighted sum plus bias is positive. | — | — | |
| The error is 0 when correct, +1 when the neuron should have fired, and −1 when it fired wrongly. | — | — | |
| Move the weights toward the input for a missed positive, away from it for a false positive. Nothing changes when the answer is right. | — | — | |
| AND is linearly separable: the rule converges to weights (2, 1) and bias −2 with a clean pass. | — | ([2, 1], -2, True) | |
| XOR is not linearly separable, so no pass is ever mistake-free: it reports False. | — | ([2, 1], -2, True) False |
Cost and common mistakes
Each pass costs O(n·d) for n examples with d inputs. For separable data the number of mistakes is bounded by (R/γ)², where R is the data radius and γ the margin.
- The convergence guarantee holds only for linearly separable data. On other data the weights keep changing.
- The weights found are not unique. Different starting points or example orders give different separating lines.
- A single neuron cannot represent XOR. Stacking neurons into layers with nonlinear activations overcomes the limit.
Try it yourself
Check that the learned weights classify (1, 0) correctly.
Reveal answer and reasoning
2·1 + 1·0 − 2 = 0, which is not greater than 0, so the output is 0, the correct AND value.