From Perceptron to Multilayer Network
Rosenblatt's linear classifier, the XOR failure that exposed its limits, and how stacking layers plus non-linearity turns a single hyperplane into an arbitrarily complex decision boundary.
- Write the perceptron update rule and trace one training epoch by hand
- Prove that a single perceptron cannot represent XOR, geometrically and algebraically
- Explain how a two-hidden-layer network carves decision regions a perceptron cannot
- Distinguish representational power (what a network CAN fit) from trainability (what SGD actually finds)
In 1958 the New York Times reported that the Navy expected the perceptron to "walk, talk, see, write, reproduce itself and be conscious of its existence". It was a single neuron trained on photosensors. Seven years later, Minsky and Papert proved in one book chapter that this machine cannot even solve XOR — the four-point puzzle any child solves by hand. That single counterexample redirected the entire field, and understanding WHY a linear machine fails XOR, and exactly what machinery fixes it, is the foundation everything else in this course stands on.
The perceptron, precisely. Rosenblatt's perceptron is a single artificial neuron with a hard threshold. It receives inputs x1..xn, computes a weighted sum z = w·x + b, and outputs 1 if z >= 0, else 0. It is a linear classifier: the decision boundary w·x + b = 0 is a hyperplane (a line in 2D, a plane in 3D). Everything on one side is positive, everything on the other negative.
The perceptron learning rule. Training is embarrassingly direct. Predict on an example. If the prediction is correct, do nothing. If the model predicted 0 but the label is 1, nudge every weight toward the input: w_i <- w_i + eta * x_i (and b <- b + eta). If it predicted 1 but the label is 0, nudge away: w_i <- w_i - eta * x_i. The geometric picture: each misclassified example pushes the hyperplane so that it flips that point to the correct side. Rosenblatt's Perceptron Convergence Theorem guarantees this procedure finds a separating hyperplane in finite steps — IF one exists. That if is the whole story.
The XOR wall. XOR (exclusive OR) has four points: (0,0)->0, (0,1)->1, (1,0)->1, (1,1)->0. Try to draw a single straight line separating the 1s from the 0s. You cannot: the two 1s sit at opposite corners of a square, and the two 0s sit on the other diagonal. No hyperplane in the input space separates these classes, so no weight setting of a single perceptron represents XOR — the problem is geometric, not an optimization failure. No amount of training data, better learning rate, or clever initialization rescues a model class that cannot express the answer. This is the distinction between representational failure and training failure, and confusing them is the most common beginner error in the field.
What actually solves it: depth plus non-linearity. A multilayer network (MLP) composes multiple neurons into hidden layers, with a non-linear activation between layers. For XOR, one classic construction uses two hidden neurons computing h1 = ReLU(x1 + x2 - 1) and h2 = ReLU(x1 + x2 - 2)... more cleanly, the standard trick: h1 = AND(x1, x2-ish), h2 = OR-ish, output = h2 - h1. In continuous terms, two hidden ReLU units create two half-plane boundaries; the output layer recombines their regions so the positive area becomes the union of two corners. One hyperplane cannot do this; a composition of two can. The general theorem: a network with one hidden layer of sufficient width and a non-linear activation can approximate any continuous function on a compact set to arbitrary accuracy (the universal approximation theorem). Depth is not required for approximation in principle — it is required for efficiency in practice. Functions like hierarchical image structure need exponentially many neurons in a shallow net but polynomially many in a deep one.
From classifier to feature machine. The deeper insight of the MLP is not "more boundaries", it is that hidden layers learn FEATURES. The first hidden layer learns useful rotations and projections of the raw input; the second layer learns combinations of those; the output layer classifies in the learned feature space. What was a non-linearly-separable problem in the raw input often becomes linearly separable in a well-chosen feature space. This is the connection to classical SVM thinking: hand-engineered features plus a linear classifier, except here the features are learned jointly with the classifier by gradient descent through the whole stack.
The honest caveats. Universal approximation says a solution EXISTS in the weight space. It says nothing about whether SGD finds it in reasonable time, whether it generalizes, or whether the needed width is practical. The gap between "can represent" and "can train" is where most of the next four modules live: optimization, initialization, normalization, and architecture design are all responses to that gap.
| Property | Perceptron | Multilayer network |
|---|---|---|
| Decision boundary | Single hyperplane | Piecewise-linear / curved composite boundary |
| Can represent XOR | No — provably | Yes — with one hidden layer of >= 2 units |
| Learning rule | Local: update on misclassification only | Global: gradient of a loss through all layers |
| Features | Uses raw inputs | Learns its own intermediate features |
| Failure mode if it cannot fit | Optimization (no separating plane) | Optimization or capacity — must diagnose which |
1import torch
2import torch.nn as nn
3
4# XOR as a tiny training set
5X = torch.tensor([[0.,0.],[0.,1.],[1.,0.],[1.,1.]])
6y = torch.tensor([[0.],[1.],[1.],[0.]])
7
8# A single linear layer: representational ceiling = a straight line
9linear = nn.Linear(2, 1) # cannot fit XOR, ever
10# A 2-16-1 MLP with ReLU: can fit XOR
11mlp = nn.Sequential(
12 nn.Linear(2, 16), nn.ReLU(),
13 nn.Linear(16, 1), nn.Sigmoid(),
14)
15
16opt = torch.optim.Adam(mlp.parameters(), lr=0.05)
17lossfn = nn.BCELoss()
18for step in range(500):
19 loss = lossfn(mlp(X), y)
20 opt.zero_grad(); loss.backward(); opt.step()
21print(torch.round(mlp(X)).squeeze()) # -> tensor([0., 1., 1., 0.])Model cannot fit even the training set? Either capacity (too small / wrong architecture) or optimization (lr, init, saturation). Fit train but not val? Generalization problem — different playbook. Name the failure before touching hyperparameters.
A theorem about the EXISTENCE of good weights says nothing about SGD finding them. "The network can represent it" and "our run learned it" are different claims — never substitute one for the other in a report or an exam answer.
- 1
Epoch 1, point A=(1,1) label 1
Score = 0*1 + 0*1 = 0 >= 0, so the perceptron predicts 1. Correct. No update. Weights stay (0, 0).
z = 0; pred = 1 (ties go positive); pred == y -> no update - 2
Epoch 1, point B=(0,0) label 0
Score = 0 >= 0, predicts 1. Wrong (label 0). Weights move away from the input: w <- w - 1 * (0,0) = (0,0). No change — this point carries no direction. Continue.
w = (0,0) - (0,0) = (0,0) - 3
Epoch 1, point C=(1,0) label 0
Score = 0, predicts 1. Wrong. Update away: w <- (0,0) - 1*(1,0) = (-1, 0).
w = (-1, 0) - 4
Epoch 2, A=(1,1) label 1
Score = -1*1 + 0*1 = -1 < 0, predicts 0. Wrong. Update toward: w <- (-1,0) + (1,1) = (0, 1).
w = (0, 1) - 5
Epoch 2, B=(0,0) label 0
Score 0 >= 0 predicts 1. Wrong. w <- (0,1) - (0,0) = (0,1). Then C=(1,0): score 0, predicts 1, wrong: w <- (0,1) - (1,0) = (-1, 1).
after B: (0,1); after C: (-1, 1) - 6
Epoch 3, verify all points
A: -1+1 = 0 -> pred 1 (correct). B: 0 -> pred 1 — STILL WRONG. The bias-free perceptron with w=(-1,1) gives B a tie score of 0 which breaks to the positive class. Continue iterating: next A correct, C: -1 < 0 pred 0 correct, B again updates to (-1,1), and so on — with a bias term this oscillation resolves; without one, ties at the origin can persist. The lesson: ties and the missing bias both matter. With bias b and a few more epochs, AND converges to w=(1,1), b=-1.5.
with bias: converges to w=(1,1), b=-1.5 # AND: fires only at (1,1)
Solution
The perceptron learns AND (a linearly separable function) in a handful of updates: with a bias it settles at w=(1,1), b=-1.5, firing only on (1,1). For XOR, no sequence of these updates can succeed — because no single line separates { (0,1), (1,0) } from { (0,0), (1,1) }, the Perceptron Convergence Theorem's precondition ("a separator exists") is violated, and the algorithm will oscillate forever. Depth is the fix, not patience.
Write a four-sentence proof that no linear classifier can fit XOR. Then sketch (words or a diagram) the two-hidden-unit ReLU construction that can: specify each hidden unit's weights and the output unit's weights so the network outputs 0 at (0,0) and (1,1) and 1 at (0,1) and (1,0).
Hint: For the proof: assume a line w1*x1 + w2*x2 + b separates, derive w1 + b < 0 and w1 + b > 0 (or similar contradiction pair). For the construction: h1 = x1 + x2 - 1 gives 1 at the two "middle" corners, h2 = 2 - x1 - x2 also isolates them; output = min(h1, h2) or a small MLP recombining them.
Believing a bigger learning rate or more epochs can fix a representational failure
If the model class cannot express the target (perceptron on XOR), training diverges or cycles forever. Increase capacity or change architecture first; tune optimization second.
Quoting the universal approximation theorem as "MLPs can learn anything"
The theorem says good weights EXIST for any continuous function, given enough width. It says nothing about SGD finding them in feasible time, nor about generalization. Quote it with its caveats or not at all.
Assuming deeper is always better than wider because depth is more parameter-efficient
Depth pays when the target has hierarchical structure (vision, language). On low-dimensional tabular problems a single hidden layer often matches deeper nets. Decide by validation, not fashion.
Forgetting the bias and then misreading ties in hand-traced perceptrons
Without a bias, every hyperplane passes through the origin — the classifier loses a whole degree of freedom. In hand-traces, a score of exactly 0 also needs a stated tie-break convention; pick one (>= 0 is positive) and apply it consistently.
GATE-style: (a) Show that no single perceptron can implement XOR. (b) State the universal approximation theorem, and explain in two sentences why it does not guarantee that gradient descent will train a deep network successfully.
(a) XOR requires f(0,0)=0, f(1,1)=0, f(0,1)=1, f(1,0)=1. A perceptron computes sign(w1*x1 + w2*x2 + b) — a single straight boundary. The positives (0,1) and (1,0) lie on opposite sides of any line that separates (0,0) from (1,1): assuming w1*x1 + w2*x2 + b < 0 at (0,0) and (1,1) gives b < 0 and w1 + w2 + b < 0; requiring > 0 at (0,1) and (1,0) gives w2 + b > 0 and w1 + b > 0; summing the last two: w1 + w2 + 2b > 0, contradicting w1 + w2 + b < 0 with b < 0. Hence no separating hyperplane exists. (b) The theorem: any continuous function on a compact set can be approximated arbitrarily well by a one-hidden-layer network with a non-linear activation, given sufficient width. It is an existence result over the weight space; it gives no algorithm, no sample-complexity bound, and no guarantee that SGD reaches the good region in polynomial time — those are optimization and generalization questions, addressed by the techniques of Modules 2 and 3.
Source: Classic GATE CS/AI deep-learning question; also a staple of ML interviews at the "prove it" level.
- A perceptron is one neuron with a threshold: its boundary is a single hyperplane, trainable by nudging weights on mistakes.
- XOR is not linearly separable, so no perceptron can represent it — a representational, not optimization, failure.
- MLPs compose neurons through hidden layers with non-linear activations, turning raw inputs into learned features where classes become separable.
- Universal approximation: one hidden layer is enough to APPROXIMATE any continuous function; depth buys efficiency, not mere possibility.
- Always distinguish three questions: can it represent? can SGD train it? does it generalize?