Perceptron and Multilayer Networks

A perceptron is a linear classifier with a hard threshold. It multiplies each input by a weight, sums the products, adds a bias, and fires when the total crosses zero. That is the entire forward pass:

z = w·x + b = w1·x1 + w2·x2 + ... + wn·xn + b
ŷ = 1 if z >= 0, else 0

The learning rule is equally small. For a training example (x, y) with labels in {0, 1}, predict ŷ and, only when the prediction is wrong, move the weights toward that example:

when ŷ != y:
    w ← w + η·(y − ŷ)·x
    b ← b + η·(y − ŷ)

Correct predictions leave the model untouched; a mistake slides the weight vector by a step proportional to the example itself. When y = 1 and the perceptron predicted 0, the factor (y − ŷ) = +1 pushes z up for that example; when y = 0 and it predicted 1, the factor is −1 and pushes z down. The bias moves the decision threshold without changing the boundary slope — drop it and every separator is forced through the origin, and OR already needs a shifted line.

Trace it on OR — inputs (0,0)→0, (0,1)→1, (1,0)→1, (1,1)→1 — starting from w = (0, 0), b = 0, learning rate η = 1, visiting the examples in listed order:

Epoch 2 misclassifies (0,0) and then (1,0); epoch 3 misclassifies only (0,0). After that every point is correct: w = (1, 1), b = −1, so the perceptron fires when x1 + x2 ≥ 1 — a line that separates OR completely. Rosenblatt’s perceptron convergence theorem generalizes this outcome: if the classes are linearly separable, the update rule makes only finitely many mistakes and then stops touching the weights. The learning rate changes how fast it finishes, not whether. Separability is the precondition, and the moment the data has no separating line, the guarantee evaporates.

XOR is that moment. Targets: (0,0)→0, (1,1)→0, (0,1)→1, (1,0)→1. No single line separates these four points, and you can prove it in four lines of algebra. Assume a perceptron solves XOR. Classifying (0,1) and (1,0) as 1 forces w2 + b ≥ 0 and w1 + b ≥ 0. Classifying (0,0) and (1,1) as 0 forces b < 0 and w1 + w2 + b < 0. Add the first two inequalities: w1 + w2 + 2b ≥ 0, which rearranges to w1 + w2 + b ≥ −b. Because b < 0, the quantity −b is positive, so w1 + w2 + b > 0 — a direct contradiction of the fourth constraint. No weight vector exists, the update rule revisits mistakes forever, and no learning rate rescues it.

That result, published in Minsky and Papert’s 1969 book Perceptrons, helped end the first neural-network boom: if the basic unit cannot represent XOR, what is stacking supposed to buy? The fix was never a cleverer update rule. The fix is to stop classifying raw inputs and compute features from them first — exactly what t-SNE and UMAP Visualization shows visually when two classes form interleaved clusters no projection can pull apart. A hidden layer bends the boundary by construction, which is the next chapter’s mechanism.

A single perceptron’s boundary is straight because its output is a weighted sum of the raw inputs. The multilayer trick is to stop classifying the inputs: compute new features from the inputs, then classify the features. A hidden layer runs several perceptrons in parallel over the same input, and their outputs become the inputs of the next layer:

h = f(W1·x + b1)     # hidden layer: several units over the raw inputs
ŷ = f(W2·h + b2)     # output unit: one perceptron over the hidden features

XOR falls to three hand-chosen units. Hidden unit h1 = AND: weights (2, 2), bias −3, so z1 = 2x1 + 2x2 − 3 ≥ 0 only when x1 + x2 ≥ 1.5, which fires just for (1,1). Hidden unit h2 = OR: weights (1, 1), bias −0.5, firing whenever x1 + x2 ≥ 0.5. The output unit reads the hidden features with weights (−1, 1) and bias −0.5, so z3 = h2 − h1 − 0.5 ≥ 0 exactly when OR holds and AND does not. Full trace with f as the threshold:

Read what happened geometrically. The raw input space had no separating line, so the hidden layer changed coordinates: (0,0) lands at hidden (0,0), (1,1) at hidden (1,1), and both mixed inputs collapse onto hidden (0,1). In that feature space the straight line h2 − h1 ≥ 0.5 splits the classes cleanly. The output unit is still just a perceptron; the hidden layer made the problem linear. That is the entire idea of a multilayer network: not a smarter classifier at the end, but computed features at the front.

Now count the pieces, because interviews ask. For a batch of 8 examples, x has shape (8, 2). nn.Linear(2, 2) holds a (2, 2) weight tensor plus a length-2 bias: 2·2 + 2 = 6 parameters, and its output has shape (8, 2). nn.Linear(2, 1) holds (1, 2) weights plus one bias: 2·1 + 1 = 3. The whole XOR network is 9 parameters. The general rule: nn.Linear(in, out) contains in·out + out trainable parameters when bias=True, which is the default.

import torch
import torch.nn as nn

net = nn.Sequential(
    nn.Linear(2, 2),    # 2*2 + 2 = 6 parameters
    nn.ReLU(),
    nn.Linear(2, 1),    # 2*1 + 1 = 3 parameters
)
x = torch.tensor([[0., 0.], [0., 1.], [1., 0.], [1., 1.]])
print(net(x).shape)                              # torch.Size([4, 1])
print(sum(p.numel() for p in net.parameters()))  # 9

Scale the arithmetic to something an interviewer will pick at random: an MLP with 784 inputs, one 256-unit hidden layer, and 10 outputs holds (784·256 + 256) + (256·10 + 10) = 200,960 + 2,570 = 203,530 parameters. Notice the distribution: over 98% of the parameters live in the first layer, because its size scales with the input dimension while later layers only scale with adjacent widths. Quote the formula, do the multiplication, and you have the answer.

One caveat keeps this from being the whole story. The hand-trace used threshold activations, and a threshold has zero gradient almost everywhere, so the perceptron update rule cannot train a stack of them — there is no slope to descend. Modern networks keep the architecture and swap in smooth activations (sigmoid, tanh, ReLU) trained by gradient descent. Which nonlinearity to pick, and what saturation does to a deep stack, is Activation Functions; the derivative chain that actually moves those nine parameters is Backpropagation and the Training Loop, and the framework that manages all of it is Building a Network in PyTorch.

One hidden layer is enough — that claim gets drilled into every first course, and it rests on a real theorem. Cybenko (1989) and Hornik (1991) proved that a feedforward network with a single hidden layer containing finitely many neurons can approximate any continuous function on a compact set to arbitrary accuracy, provided the activation is non-polynomial — sigmoids qualify, a bare threshold does not. The precise wording matters, because the fine print decides whether you should build one wide shallow net or a stack of narrow ones.

First, the theorem is about existence, not learnability. It says weights achieving the approximation exist; it says nothing about gradient descent finding them in feasible time. A network that memorizes its 10,000 training examples with 10,000 hidden units honors the spirit of the theorem and generalizes terribly. Out-of-sample error never appears in the statement — generalization is a property of the training procedure and the data distribution, not of raw expressive capacity.

Second, the required width can be exponential. The standard example is parity on n binary inputs: a one-hidden-layer threshold network needs on the order of 2^n units to represent it, while a deep network of linear size represents the same function by composing small pieces. Each extra layer multiplies the set of representable functions by another composition, so depth trades against width exponentially — what a shallow net buys with units, a deep net buys with layers. That is the real reason modern networks are deep. Universal approximation says shallow nets are not vacuous; it is not a design guideline.

Third, arbitrary accuracy hides unbounded weights. Approximating a step or a corner with sigmoids forces weights toward infinity — the approximating family never lands on the target with finite parameters. It is a limit statement, and the cost of approaching that limit is paid in weight magnitude, which collides with weight decay, quantization, and any deployment that must round its numbers.

The practical heuristic the theorem’s fine print hands you: when the data has no obvious internal structure — a few dozen tabular features, a scalar target — one or two hidden layers of 64 to 256 units rarely lose to a deeper stack, and extra depth mostly buys tuning time. Depth pays when the data itself is compositional: edges into shapes into objects in images, sounds into phonemes into words in audio. There each layer reuses the features of the layer above it, and the exponential efficiency of composition from the previous paragraph shows up as accuracy per parameter.

There is also a trap sitting inside the phrase stacking layers. Compose two linear maps and the result is one linear map:

W2·(W1·x + b1) + b2 = (W2·W1)·x + (W2·b1 + b2)   # still one affine map

A ten-layer linear network has exactly the expressive power of single-layer linear regression, no matter how many parameters it accumulates. Every bit of non-linearity in a network comes from the activations between the linear layers — which is why activation choice is the next topic, Activation Functions, and why a deep model that fits a straight line to obviously curved data is a model whose activations are missing or dead.

Interviews raise the theorem in two forms. Can a two-layer network represent XOR? Yes — draw the h1/h2 construction from the previous chapter and name the hidden features. What does universal approximation actually guarantee? A tight answer: with a non-polynomial activation, one hidden layer of finite width can approximate any continuous function on a compact set to arbitrary accuracy — but the width bound can be exponential, the weights may need to grow without bound, and the theorem promises nothing about optimization or generalization. Depth buys efficiency, backprop buys the weights, and nothing in the statement buys generalization.