Linear Classifiers › The Perceptron: The Simplest Linear Classifier

Before logistic regression, the perceptron was the first trainable linear classifier, proposed by Frank Rosenblatt in 1958. The perceptron algorithm is simpler than gradient descent: it only updates weights when it makes a mistake.

The perceptron uses labels $y \in \{-1, +1\}$ (rather than $\{0, 1\}$) and predicts $\hat{y} = \text{sign}(\mathbf{w} \cdot \mathbf{x} + b)$. When the prediction is wrong (i.e., $\hat{y} \neq y$), it applies the update:

$$\mathbf{w} \leftarrow \mathbf{w} + y \cdot \mathbf{x}$$ $$b \leftarrow b + y$$

where:

• $y \in \{-1, +1\}$: the true class label
• $\mathbf{x}$: the input feature vector
• Adding $y \cdot \mathbf{x}$ to $\mathbf{w}$: when $y = +1$, moves $\mathbf{w}$ closer to $\mathbf{x}$, increasing the score; when $y = -1$, moves $\mathbf{w}$ away from $\mathbf{x}$, decreasing the score

The perceptron convergence theorem states that if the training data is linearly separable, the perceptron finds a separating hyperplane in a finite number of steps. The bound on the number of mistakes is $R^2 / \gamma^2$, where $R$ is the radius of the smallest sphere containing all training points and $\gamma$ is the margin (the distance from the closest training point to the optimal hyperplane). A larger margin means faster convergence. When there is no separating hyperplane, however, the perceptron loops indefinitely.

Logistic regression with gradient descent is strictly more powerful: it produces probability estimates rather than hard labels, converges to the best linear fit even on non-separable data, and minimizes a smooth convex loss function. The perceptron is primarily of historical and pedagogical interest today, but understanding it helps connect the update rules of modern neural network training to their historical roots. The perceptron's mistake-driven update rule also reappears in online learning settings where data arrives sequentially and one cannot afford to store the full training set.

The perceptron's announcement in 1958 generated enormous excitement. The New York Times ran a story about a machine that could learn. There was widespread belief that general artificial intelligence was imminent. Then, in 1969, Marvin Minsky and Seymour Papert published a thorough mathematical analysis showing that the perceptron could not solve XOR and other non-linearly-separable problems. The result was devastating to the field's optimism and contributed to the first "AI winter," a period of reduced funding and interest in neural network research. The solution, stacking perceptrons in multiple layers with nonlinear activations, was known even at the time, but efficient training algorithms for multilayer networks were not developed until the 1986 popularization of backpropagation. The lesson: architectural expressiveness without a training algorithm is not enough.