XOR, MLPs & Softmax
A single perceptron draws one straight line. That is all it can ever do. The XOR problem is the classic proof that one line is not enough, and solving it forced the invention of the multi-layer perceptron (MLP). Understanding why XOR breaks the perceptron, and how a hidden layer fixes it, gives you the deepest intuition for why depth in neural networks matters.
The perceptron learning rule
The perceptron is a linear classifier: . It predicts class 1 when the input is on one side of the hyperplane , and class 0 otherwise.
The perceptron learning rule adjusts weights only when the prediction is wrong:
- If the prediction is correct (), the update is zero.
- If the label is 1 but we predicted 0: push in the direction of (rotate the decision boundary toward the example).
- If the label is 0 but we predicted 1: push away from .
Convergence theorem: If the data is linearly separable, the perceptron algorithm converges in a finite number of steps. If not, it loops forever.
One update, concretely: Suppose , , and we see input with true label . The score is , so — correct, no update. Now suppose with : score , so (wrong). The update pushes the boundary toward this example: , . For the 5-step AND convergence trace with exact weight/bias values at every update:
The XOR problem
XOR outputs 1 when exactly one input is 1:
| XOR | ||
|---|---|---|
| 0 | 0 | 0 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
Plot these four points: the two 0-outputs are at and (the diagonal), and the two 1-outputs are at and (the other diagonal). No single straight line separates the two classes — a formal proof by contradiction using the four boundary inequalities shows this is impossible (see the wiki page above).
Why XOR matters historically
Minsky and Papert's 1969 book Perceptrons proved this limitation and severely cooled AI funding for a decade (the first "AI winter"). The invention of backpropagation and multi-layer networks in the 1980s reignited interest by showing that XOR is trivially solved with one hidden layer.
The hidden layer fix
A two-layer MLP for XOR uses a hidden layer to first transform the inputs into a new representation where the classes are linearly separable, then applies a linear classifier in that transformed space.
Architecture: Input → hidden layer (2 neurons, ReLU) → output (1 neuron, sigmoid).
One set of weights that solves XOR exactly:
Trace through each input:
| Input | ||||
|---|---|---|---|---|
| (0,0) | (0, −1) | (0, 0) | 0 | 0 |
| (1,0) | (1, 0) | (1, 0) | 1 | 1 |
| (0,1) | (1, 0) | (1, 0) | 1 | 1 |
| (1,1) | (2, 1) | (2, 1) | 0 | 0 |
The hidden layer maps and to the same hidden representation — the network has learned that these two different inputs mean the same thing ("exactly one input is on"). The output layer simply classifies this shared representation as class 1.
The hidden layer as a learned feature extractor
The hidden layer does not just detect "is on?" or "is on?" — it detects a higher-level feature: "is at least one input on?" (neuron 1) and "are both inputs on?" (neuron 2). The output layer then computes : one-or-both-on minus twice both-on, which equals 1 iff exactly one is on. This is what universal approximation means in practice: depth creates composable feature detectors.
A feed-forward network, live
Edges: brand = positive weight, rose = negative; thicker = larger magnitude. Neuron brightness shows its activation value. The output neuron is linear — change inputs, activation, width, and depth and watch the forward pass recompute.
Universal approximation theorem
A neural network with one hidden layer of sufficient width can approximate any continuous function on a compact subset of to arbitrary precision. This is the universal approximation theorem (Cybenko 1989, Hornik 1991).
What it says vs. what it doesn't say:
- ✅ There exists a network of finite width that approximates any function.
- ✅ This justifies using neural networks as general-purpose function approximators.
- ❌ It does not say how wide the network needs to be — it could be exponentially large.
- ❌ It does not say that gradient descent will find those weights — the optimization problem may be hard.
- ❌ It does not say a shallow network is as efficient as a deep one — in practice, depth allows exponentially more compact representations.
Softmax outputs for multi-class classification
For binary classification the output neuron uses a sigmoid: , interpreted as .
For -class classification, replace the sigmoid with softmax over output neurons:
where is the -th logit (raw score).
Properties of softmax:
- All outputs are positive:
- Outputs sum to one:
- The largest logit gets the largest probability
- Probabilities are sharpened by large logit differences (high-confidence prediction) and flattened when logits are close (uncertain prediction)
The gradient of the cross-entropy loss with respect to each logit takes a remarkably clean form: . For the true class this is (negative — push that logit up); for every other class it is (positive — push those logits down). The cleanness comes from a cancellation between the softmax Jacobian and the log in cross-entropy. For the 3-class numeric example (), the full chain-rule derivation, and finite-difference verification:
Exercise
A single perceptron cannot solve XOR. What is the simplest architecture that can?
Need a hint?
Think about what a hidden layer adds that a single layer doesn't have.
Exercise
After softmax, a 3-class model outputs probabilities (0.7, 0.2, 0.1). The true label is class 0. What is ∂L/∂z₀, the cross-entropy gradient w.r.t. logit 0?
Need a hint?
For softmax + cross-entropy, ∂L/∂z_k = p̂_k − 1[k=y].
Exercise
A perceptron with w=(1, −1), b=0 sees input x=(2, 3). It predicts 0, but the true label is 1. With learning rate η=1, what are the new weights?
Need a hint?
Perceptron rule: w ← w + η(y − ŷ)x.
Common mistakes
- Using softmax with only 2 classes: for binary classification, a single sigmoid output is equivalent and twice as efficient. Softmax of two logits is equivalent to sigmoid of .
- Applying ReLU before the output layer: the output layer has no activation function (logits) or uses softmax/sigmoid for classification or linear for regression. ReLU on the output would prevent predicting negative values or probabilities.
- Confusing the perceptron learning rule with gradient descent: the perceptron rule only fires on misclassified examples and does not use a differentiable loss. Modern networks use gradient descent on a smooth loss everywhere.
Key takeaways
- Perceptron = linear classifier: it converges on linearly separable data; XOR proves it cannot solve all problems.
- A hidden layer transforms inputs into a new representation where the problem becomes linearly separable.
- Universal approximation guarantees one hidden layer is enough in principle; in practice, depth is exponentially more efficient.
- Softmax maps logits to a probability distribution; cross-entropy loss gives a clean gradient: .
Connection to ML
- Temperature scaling in language models: dividing logits by makes generations more focused ("greedy"); makes them more diverse. Every LLM API exposes a
temperatureparameter that wraps exactly this operation. - Universal approximation in practice: a single hidden layer of sufficient width can approximate any continuous function (Cybenko 1989, Hornik 1991), but the theorem gives no useful width bound; the required width can grow exponentially in the input dimension. Real networks rely on depth rather than width to stay efficient.
- Softmax + cross-entropy everywhere: this combination is the default output for any multi-class classification network, from image classifiers (ImageNet) to language models (next-token prediction over a vocabulary of 50 000+ tokens).
Related concepts
- What is a Neuron?: the single-neuron building block
- Gradient Descent: the optimizer used to train MLPs
- Layers & the Forward Pass: the matrix form of an MLP layer
- Logistic Regression: softmax with one hidden layer is logistic regression on learned features