XOR, MLPs & SoftmaxOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

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: y^=1[w⊤x+b>0]\hat{y} = \mathbb{1}[\mathbf{w}^\top \mathbf{x} + b > 0]. It predicts class 1 when the input is on one side of the hyperplane w⊤x+b=0\mathbf{w}^\top \mathbf{x} + b = 0, and class 0 otherwise.

The perceptron learning rule adjusts weights only when the prediction is wrong:

w←w+η (y−y^) x,b←b+η (y−y^)\mathbf{w} \leftarrow \mathbf{w} + \eta\,(y - \hat{y})\,\mathbf{x}, \qquad b \leftarrow b + \eta\,(y - \hat{y})
  • If the prediction is correct (y=y^y = \hat{y}), the update is zero.
  • If the label is 1 but we predicted 0: push w\mathbf{w} in the direction of x\mathbf{x} (rotate the decision boundary toward the example).
  • If the label is 0 but we predicted 1: push w\mathbf{w} away from x\mathbf{x}.

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 w=[0.5,−0.3]\mathbf{w} = [0.5, -0.3], b=0b = 0, and we see input x=[1,0]\mathbf{x} = [1, 0] with true label y=1y = 1. The score is 0.5(1)+(−0.3)(0)=0.5>00.5(1) + (-0.3)(0) = 0.5 > 0, so y^=1\hat{y} = 1 — correct, no update. Now suppose x=[0,1]\mathbf{x} = [0, 1] with y=1y = 1: score =0.5(0)+(−0.3)(1)=−0.3<0= 0.5(0) + (-0.3)(1) = -0.3 < 0, so y^=0\hat{y} = 0 (wrong). The update pushes the boundary toward this example: w←[0.5,−0.3]+1⋅[0,1]=[0.5,0.7]\mathbf{w} \leftarrow [0.5, -0.3] + 1 \cdot [0, 1] = [0.5, 0.7], b←0+1=1b \leftarrow 0 + 1 = 1. For the 5-step AND convergence trace with exact weight/bias values at every update:

Deep dive
The Perceptron Learning Algorithm
Includes runnable notebook

The XOR problem

XOR outputs 1 when exactly one input is 1:

x1x_1x2x_2XOR
000
101
011
110

Plot these four points: the two 0-outputs are at (0,0)(0,0) and (1,1)(1,1) (the diagonal), and the two 1-outputs are at (1,0)(1,0) and (0,1)(0,1) (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 x∈R2\mathbf{x} \in \mathbb{R}^2 → hidden layer (2 neurons, ReLU) → output (1 neuron, sigmoid).

One set of weights that solves XOR exactly:

W1=[1111],b1=[0−1],W2=[1−2],b2=0\mathbf{W}_1 = \begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix}, \quad \mathbf{b}_1 = \begin{bmatrix} 0 \\ -1 \end{bmatrix}, \quad \mathbf{W}_2 = \begin{bmatrix} 1 & -2 \end{bmatrix}, \quad b_2 = 0

Trace through each input:

Inputz1=W1x+b1\mathbf{z}_1 = \mathbf{W}_1\mathbf{x}+\mathbf{b}_1h=ReLU(z1)\mathbf{h} = \text{ReLU}(\mathbf{z}_1)z2=W2h+b2z_2 = \mathbf{W}_2\mathbf{h}+b_2y^\hat{y}
(0,0)(0, −1)(0, 0)00
(1,0)(1, 0)(1, 0)11
(0,1)(1, 0)(1, 0)11
(1,1)(2, 1)(2, 1)00

The hidden layer maps (1,0)(1,0) and (0,1)(0,1) to the same hidden representation (1,0)(1, 0) — 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 x1x_1 on?" or "is x2x_2 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 h1−2h2h_1 - 2h_2: 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

inputhidden 1output1.00-0.500.350.560.000.22
output ŷ0.217
activationReLU
parameters13

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 Rn\mathbb{R}^n 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: y^=σ(z)∈(0,1)\hat{y} = \sigma(z) \in (0, 1), interpreted as P(y=1∣x)P(y=1|\mathbf{x}).

For KK-class classification, replace the sigmoid with softmax over KK output neurons:

p^k=ezk∑j=1Kezj,k=1,…,K\hat{p}_k = \frac{e^{z_k}}{\sum_{j=1}^{K} e^{z_j}}, \quad k = 1, \ldots, K

where zk=wk⊤h+bkz_k = \mathbf{w}_k^\top \mathbf{h} + b_k is the kk-th logit (raw score).

Properties of softmax:

  • All outputs are positive: p^k>0\hat{p}_k > 0
  • Outputs sum to one: ∑kp^k=1\sum_k \hat{p}_k = 1
  • 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 zkz_k takes a remarkably clean form: ∂L/∂zk=p^k−1[k=y]\partial \mathcal{L}/\partial z_k = \hat{p}_k - \mathbb{1}[k=y]. For the true class this is p^y−1\hat{p}_y - 1 (negative — push that logit up); for every other class it is p^k\hat{p}_k (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 (z=(2,1,−1)⇒p^≈(0.705,0.259,0.035)\mathbf{z} = (2, 1, -1) \Rightarrow \hat{\mathbf{p}} \approx (0.705, 0.259, 0.035)), the full chain-rule derivation, and finite-difference verification:

Deep dive
Softmax + Cross-Entropy Gradient
Includes runnable notebook

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

  1. Using softmax with only 2 classes: for binary classification, a single sigmoid output is equivalent and twice as efficient. Softmax of two logits (z1,z2)(z_1, z_2) is equivalent to sigmoid of z1−z2z_1 - z_2.
  2. 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.
  3. 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: p^k−1[k=y]\hat{p}_k - \mathbb{1}[k=y].

Connection to ML

  • Temperature scaling in language models: dividing logits by T<1T < 1 makes generations more focused ("greedy"); T>1T > 1 makes them more diverse. Every LLM API exposes a temperature parameter 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

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelatedGo deeper
XOR, MLPs & SoftmaxLinear Algebra for MLCalculus for MLWhat is a Neuron?Gradient DescentLayers & the Forward PassLogistic RegressionThe Perceptron Learning A…Softmax + Cross-Entropy G…