THE PERCEPTRON (Rosenblatt, 1958) adds two things to the McCulloch-Pitts neuron: REAL-VALUED, ADJUSTABLE WEIGHTS A LEARNING RULE that sets them from examples THE MODEL is otherwise the same: net = Σᵢ wᵢxᵢ + b y = 1 if net ≥ 0, else 0 (a step function) THE PERCEPTRON LEARNING RULE — the whole of it: for each training example (x, t): compute the output y compute the ERROR e = t − y update every weight wᵢ ← wᵢ + η · e · xᵢ update the bias b ← b + η · e where t is the TARGET, y the actual output, and η the LEARNING RATE. READ WHAT THE RULE DOES, because the three cases explain it entirely: e = 0 the output was correct → NO CHANGE. The perceptron only learns from mistakes. e = +1 the target was 1 and the output 0 — the net input was too small, so ADD xᵢ to each weight, pushing net up for this input. e = −1 the target was 0 and the output 1 — SUBTRACT xᵢ, pushing net down. AND NOTE THE FACTOR xᵢ: a weight is changed only in proportion to its input. A weight whose input was 0 is not changed at all, which is correct — that input contributed nothing to the error. THE ALGORITHM: initialise the weights (small random values, or zero) repeat: for each training example: apply the update rule until no example produces an error (or a limit is reached) ONE PASS THROUGH THE TRAINING SET IS AN EPOCH. THE PERCEPTRON CONVERGENCE THEOREM (Rosenblatt / Novikoff): IF the training data is LINEARLY SEPARABLE, the perceptron learning rule is guaranteed to find a separating boundary in a FINITE number of steps, for any positive learning rate. THIS IS A GENUINELY STRONG GUARANTEE, and it is what made the perceptron important. But note what it does NOT say: · it says nothing if the data is not separable — and in that case the algorithm never terminates, oscillating indefinitely · it does not find the BEST boundary, only SOME boundary. The margin may be tiny, which is what support vector machines later addressed. · the number of steps depends on the margin, and can be large for a narrow one

TRAINING A PERCEPTRON ON THE AND FUNCTION, with η = 0.5, all weights and the bias starting at 0. This is the standard exam question, worked to convergence. Training set: (0,0)→0 (0,1)→0 (1,0)→0 (1,1)→1 Activation: y = 1 if net ≥ 0, else 0 EPOCH 1 x = (0,0), t = 0: net = 0.0 → y = 1. e = −1 w ← (0.0, 0.0) [inputs are 0, so no weight change] b ← 0 + 0.5(−1) = −0.5 x = (0,1), t = 0: net = 0(0) + 0(1) − 0.5 = −0.5 → y = 0. CORRECT, no change. x = (1,0), t = 0: net = −0.5 → y = 0. CORRECT. x = (1,1), t = 1: net = −0.5 → y = 0. e = +1 w ← (0 + 0.5, 0 + 0.5) = (0.5, 0.5) b ← −0.5 + 0.5 = 0.0 EPOCH 2 x = (0,0), t = 0: net = 0.0 → y = 1. e = −1 b ← −0.5 x = (0,1), t = 0: net = 0.5 − 0.5 = 0.0 → y = 1. e = −1 w ← (0.5, 0.5 − 0.5) = (0.5, 0.0) b ← −1.0 x = (1,0), t = 0: net = 0.5 − 1.0 = −0.5 → y = 0. CORRECT. x = (1,1), t = 1: net = 0.5 + 0 − 1.0 = −0.5 → y = 0. e = +1 w ← (1.0, 0.5), b ← −0.5 EPOCH 3 x = (0,0): net = −0.5 → 0. CORRECT. x = (0,1), t = 0: net = 0.5 − 0.5 = 0.0 → y = 1. e = −1 w ← (1.0, 0.0), b ← −1.0 x = (1,0), t = 0: net = 1.0 − 1.0 = 0.0 → y = 1. e = −1 w ← (0.5, 0.0), b ← −1.5 x = (1,1), t = 1: net = 0.5 − 1.5 = −1.0 → y = 0. e = +1 w ← (1.0, 0.5), b ← −1.0 EPOCH 4 x = (1,0), t = 0: net = 1.0 − 1.0 = 0.0 → y = 1. e = −1 w ← (0.5, 0.5), b ← −1.5 x = (1,1), t = 1: net = 1.0 − 1.5 = −0.5 → y = 0. e = +1 w ← (1.0, 1.0), b ← −1.0 EPOCH 5 x = (0,1), t = 0: net = 1.0 − 1.0 = 0.0 → y = 1. e = −1 w ← (1.0, 0.5), b ← −1.5 EPOCH 6 — no errors. CONVERGED. THE FINAL WEIGHTS: w = (1.0, 0.5), b = −1.5. VERIFY: (0,0): net = −1.5 → 0 ✓ (0,1): net = 0.5 − 1.5 = −1.0 → 0 ✓ (1,0): net = 1.0 − 1.5 = −0.5 → 0 ✓ (1,1): net = 1.5 − 1.5 = 0.0 → 1 ✓ ALL FOUR CORRECT. The decision boundary is x₁ + 0.5x₂ = 1.5. TWO THINGS WORTH NOTICING IN THE TRACE: 1. IT TOOK SIX EPOCHS FOR FOUR EXAMPLES. Convergence is guaranteed, not fast, and the path wanders — the weights reached (1.0, 0.5) at epoch 3, moved away, and returned. 2. THE SOLUTION IS NOT UNIQUE. w = (1, 1), b = −1.5 also works, as does w = (2, 2), b = −3. The perceptron finds SOME separator determined by the order of the examples and the initial weights, not the best one.

THE PERCEPTRON CAN ONLY LEARN LINEARLY SEPARABLE FUNCTIONS, for the geometric reason established in the mathematical-model topic: wᵀx + b = 0 is a hyperplane, and a single perceptron classifies by which side of it a point lies on. THE SEPARABLE CASES: AND, OR, NAND, NOR, NOT — all learnable THE NON-SEPARABLE CASE: XOR — not learnable, by the four-inequality proof of the McCulloch-Pitts topic AND THE SCALE OF THE LIMITATION, which is the part usually omitted: of the 16 possible boolean functions of two variables, 14 are linearly separable and 2 are not (XOR and its complement XNOR). That sounds mild. BUT THE FRACTION COLLAPSES WITH MORE INPUTS — of the 2^(2ⁿ) boolean functions of n variables, the separable proportion tends rapidly to zero. For n = 4 there are 65,536 functions and only 1,882 are linearly separable, under 3%. MINSKY AND PAPERT'S 1969 ANALYSIS went further than XOR. They proved that a perceptron with LOCAL receptive fields cannot compute global predicates such as CONNECTEDNESS — whether a figure is a single connected shape — no matter how many units it has, unless the units see the whole image. THAT WAS THE DEEPER RESULT, and it was about the limits of local feature detection rather than about XOR specifically. WHAT THE FIELD CONCLUDED, AND WHY IT WAS WRONG: the CORRECT conclusion: a SINGLE-LAYER perceptron is limited the INFERRED conclusion: neural networks are a dead end THE MULTILAYER SOLUTION WAS ALREADY KNOWN — the XOR construction from three units appears in the McCulloch-Pitts topic and predates the criticism by twenty-six years. WHAT WAS MISSING WAS A LEARNING RULE FOR HIDDEN LAYERS. WHY THE PERCEPTRON RULE CANNOT TRAIN A HIDDEN LAYER — the precise obstacle, and it is the credit assignment problem from the reinforcement learning topic: the rule needs the ERROR e = t − y at each unit for an OUTPUT unit the target t is given by the training data for a HIDDEN unit THERE IS NO TARGET — nobody says what a hidden unit should have output and the step function's derivative is 0, so gradient information cannot be propagated either TWO OBSTACLES, AND BOTH HAD TO BE REMOVED: replace the step function with something differentiable (the Adaline and delta rule topics), then derive how to assign blame backward (backpropagation). Seventeen years passed between the criticism and the solution being widely known. THE PERCEPTRON'S PLACE IN THE PROGRESSION: MP NEURON no learning PERCEPTRON learns; step activation; single layer; linearly separable only; CONVERGENCE GUARANTEED when separable ADALINE linear activation, so gradient descent on a continuous error becomes possible; converges even when NOT separable MLP + BACKPROP hidden layers become trainable A FINAL NOTE ON WHAT THE PERCEPTRON GOT RIGHT, since the limitation is usually all that is remembered: IT ESTABLISHED THAT A MACHINE COULD LEARN A CLASSIFICATION FROM LABELLED EXAMPLES, with a convergence proof. That is the template every supervised learning algorithm since has followed, and the perceptron rule is still the simplest example of learning from error that exists.