Perceptron

A perceptron is a model in machine learning that classifies an input by applying a threshold to a weighted sum of its features. The term also denotes the error-correcting algorithm used to learn those weights from labeled examples. In its standard form, it is a binary linear classifier and a basic building block of artificial neural networks. Its learning rule converges when the training examples are linearly separable, but this guarantee does not extend to arbitrary datasets. (cs.cornell.edu)

Historical development

Frank Rosenblatt introduced the perceptron in 1957 as a model for systems dealing with perception and memory. His research connected early artificial intelligence with experimental devices that could modify their responses through learning. The Mark I Perceptron was a hardware implementation designed for visual pattern recognition; its surviving equipment is held by the Smithsonian’s National Museum of American History. (si.edu)

In 1969, Marvin Minsky and Seymour Papert published Perceptrons: An Introduction to Computational Geometry. They studied the expressive power and limitations of particular perceptron configurations, including restrictions associated with their feature representations. These results concerned specified mathematical models, rather than establishing that all neural networks were incapable of complex learning. (mitpress.mit.edu)

Mathematical model

For an input vector $x=(x_1,\ldots,x_d)$, a perceptron computes

where $w$ contains the learned weights and $b$ is a bias, or intercept. A threshold activation function converts this score into a class label. With labels $-1$ and $+1$, one convention is

The treatment of a score exactly equal to zero is a convention that must be specified. The bias can be incorporated into the weight vector by appending a constant feature equal to one. (cs.cornell.edu)

In a vector space, the equation $w^\top x+b=0$ defines a hyperplane when $w\neq0$: a line in two dimensions, a plane in three, and its higher-dimensional analogue. The two predicted classes occupy opposite half-spaces. Although thresholding makes the output discontinuous, the classification boundary is linear in the supplied features. (cs.cornell.edu)

Learning rule

Perceptron training is a form of supervised learning. Given training data consisting of pairs $(x_i,y_i)$, the algorithm processes examples individually. A common formulation updates whenever

It then applies

where $\eta>0$ is the learning rate. Correctly classified examples with a strictly positive signed score leave the parameters unchanged. Examples on the boundary trigger an update under this formulation, regardless of the prediction tie convention. (cs.cornell.edu)

The update increases the signed score of the example that triggered it, although it may alter predictions for other examples. Training can repeatedly traverse a fixed dataset or operate through online learning, processing examples as they arrive. Implementations commonly impose an iteration limit or another stopping criterion when perfect separation is unavailable. (scikit-learn.org)

The rule can also be interpreted through the loss function

For a negative signed score, the update is a stochastic subgradient step on this loss; at zero, an appropriate subgradient gives the same update. The score is not, by itself, a calibrated class probability. (scikit-learn.org)

Convergence and limitations

The perceptron convergence theorem states that a finite, strictly linearly separable dataset admits only finitely many updates under the standard rule. For zero initialization and unit-rate updates, suppose augmented inputs have norms at most $R$, and a unit-length separating vector gives every example a signed margin of at least $\gamma>0$. The number of updates is bounded by

Thus, a larger separation margin yields a stronger bound. The theorem concerns finding a separator, not finding the separator with the largest margin or guaranteeing accuracy on unseen examples. (cs.cornell.edu)

If the classes cannot be separated in the supplied feature space, the classical algorithm need not converge. A standard counterexample is exclusive OR (XOR): the binary inputs $(0,0)$ and $(1,1)$ belong to one class, while $(0,1)$ and $(1,0)$ belong to the other. No straight line separates these assignments. Additional nonlinear features or an appropriate hidden layer can change their representability. (cs.cornell.edu)

Extensions and related models

Feature engineering can transform inputs before classification. A kernel method instead allows a perceptron to use inner products in a transformed feature space without explicitly constructing its coordinates. The boundary may then be nonlinear in the original inputs while remaining linear in the transformed representation. Voted perceptron variants combine successive classifiers rather than retaining only the final weight vector. Unlike a support vector machine, the classical perceptron does not explicitly optimize a maximum-margin objective. (cseweb.ucsd.edu)

A multilayer perceptron is a distinct, more expressive architecture composed of successive layers of weighted units and nonlinear activations. Hidden layers allow nonlinear mappings. Such networks are generally trained using backpropagation to calculate derivatives and gradient-based optimization to update parameters, rather than applying the original perceptron rule independently throughout the network. They can perform classification or regression, and their training objectives may include regularization to penalize large weights and limit overfitting. Their nonlinear training problem does not inherit the single-layer perceptron’s convergence theorem. (scikit-learn.org)