The neuron and the perceptron

Linear threshold units and the decision boundary

A single perceptron takes an input vector $x \in ℝ^{d}$ , computes an inner product with a weight vector w, adds a scalar bias b, and applies a step function (Heaviside step):

z = w^{T} x + b = \sum_{i = 1}^{d} w_{i} x_{i} + b

\hat{y} = f (z) = {\begin{matrix} 1 & z > 0 \\ 0 & z \leq 0 \end{matrix}

The decision boundary is the affine hyperplane $w^{T} x + b = 0$ . The weight vector w is the normal vector perpendicular to the boundary, determining its orientation, while the bias b determines the perpendicular offset from the origin:

distance from origin to boundary = \frac{| b |}{‖ w ‖_{2}}

The perceptron learning rule and Novikoff's convergence bound

For binary classification with labels $y \in {0, 1}$ and learning rate $η > 0$ , when the perceptron predicts $\hat{y} \neq y$ on sample x, parameters update as:

w \leftarrow w + η (y - \hat{y}) x, b \leftarrow b + η (y - \hat{y})

If $y = 1$ but $\hat{y} = 0$ (false negative), the rule adds $η x$ to w, rotating the normal vector towards x so that $w^{T} x$ increases. If $y = 0$ but $\hat{y} = 1$ (false positive), it subtracts $η x$ .

Novikoff's Theorem (1962)

If a training dataset $D = {(x_{k}, y_{k})}_{k = 1}^{N}$ is linearly separable by an optimal hyperplane $w^{*}$ with margin $γ > 0$ (where $‖ w^{*} ‖ = 1$ and $y_{k} (w^{* T} x_{k} + b^{*}) \geq γ$ ), and all inputs lie within a bounding sphere of radius $R = \max_{k} ‖ x_{k} ‖_{2}$ , then the total number of mistake updates M made by the perceptron is strictly bounded:

M \leq {(\frac{R}{γ})}^{2}

The perceptron is guaranteed to converge in a finite number of steps if the data is separable. However, if the data is not linearly separable, $γ$ does not exist, and the learning rule oscillates indefinitely without converging.

Enable JavaScript to use this local playground. The explanation and sources below work without it.

Algebraic impossibility proof: why a single neuron cannot solve XOR

In 1969, Minsky and Papert highlighted that a single perceptron cannot learn the XOR (exclusive OR) parity function. Here is the formal algebraic proof using system inequalities:

Input $(x_1, x_2)$	Target `y`	Condition on $w_{1} x_{1} + w_{2} x_{2} + b$	Inequality
(0, 0)	0	$w_{1} (0) + w_{2} (0) + b \leq 0$	(1) $b \leq 0$
(0, 1)	1	$w_{1} (0) + w_{2} (1) + b > 0$	(2) $w_{2} + b > 0$
(1, 0)	1	$w_{1} (1) + w_{2} (0) + b > 0$	(3) $w_{1} + b > 0$
(1, 1)	0	$w_{1} (1) + w_{2} (1) + b \leq 0$	(4) $w_{1} + w_{2} + b \leq 0$

Summing inequalities (2) and (3):

(w_{2} + b) + (w_{1} + b) > 0 \Rightarrow w_{1} + w_{2} + 2 b > 0

Subtracting inequality (4) from this result:

(w_{1} + w_{2} + 2 b) - (w_{1} + w_{2} + b) > 0 - 0 \Rightarrow b > 0

This directly contradicts inequality (1) ( $b \leq 0$ ). No real numbers $w_{1}, w_{2}, b$ can satisfy this system of inequalities simultaneously. A single linear threshold unit is fundamentally incapable of separating XOR.

The two-layer resolution: coordinate transformation

XOR can be factored algebraically into elementary boolean operators: $XOR (x_{1}, x_{2}) = AND (OR (x_{1}, x_{2}), NAND (x_{1}, x_{2}))$ . A two-layer network uses two hidden units to map the input space into a new coordinate representation $(h_{1}, h_{2})$ :

h_{1} = step (x_{1} + x_{2} - 0.5) (OR unit)

h_{2} = step (- x_{1} - x_{2} + 1.5) (NAND unit)

y = step (h_{1} + h_{2} - 1.5) (Output AND unit)

Input Space (x1, x2):                 Hidden Feature Space (h1, h2):
  x2                                    h2 (NAND)
  ▲                                     ▲
1 │  ● (0,1)    ○ (1,1)               1 │  ○ (0,0)    ● (0,1) & (1,0)
  │                                     │              [both land at (1,1)]
0 │  ○ (0,0)    ● (1,0)               0 │             ○ (1,1)
  └───────────────────▶ x1              └───────────────────▶ h1 (OR)
     0          1                          0          1
  Linearly inseparable!                 Linearly separable by h1 + h2 - 1.5 = 0

The hidden layer transforms the geometry: both positive points (0, 1) and (1, 0) map to the exact same hidden point (1, 1), while the negative points map to (0, 1) and (1, 0). In hidden space, a single linear threshold boundary separates the two classes cleanly.