What is a 'Perceptron'?

What is a 'Perceptron'?

Approach: State the prediction rule and the mistake-driven update, then bound the number of mistakes by the margin and say what happens when no separator exists.

A perceptron is a linear binary classifier that predicts the sign of w^T x + b and learns by adding y*x to the weight vector on every misclassified example. That update is the whole algorithm, and the perceptron convergence theorem bounds it: on data separable with margin gamma and radius R it makes at most (R/gamma)^2 mistakes before it stops, with no dependence on the number of examples or the dimension. On data that are not linearly separable it never settles and cycles forever, which is why a single unit cannot represent XOR and why a hidden layer with a nonlinear activation is needed. The step activation has zero derivative almost everywhere, so the perceptron cannot be trained by gradient descent on its own output, and logistic regression replaces the step with a sigmoid to recover a usable gradient.

Follow-up: Why does the mistake bound carry no dependence on the dimension, and what breaks it when the margin is tiny?

Key concepts: linear classifier, perceptron convergence, margin, linear separability, step activation.