Back to Curriculum
Basic•Deep Learning
Neural Networks
The building blocks of deep learning: Perceptrons and MLPs.
Interactive Playground
Initializing Interactive Playground...
Research-Level Deep Dive & Equations
The Artificial Perceptron, formulated by Frank Rosenblatt (1958), is the historical foundation of artificial neural networks. A perceptron is a binary classifier mapping an input vector to a scalar output via an affine transformation followed by a step function:
Without loss of generality, we can absorb the bias into the weight vector and augment the input vector with a constant , writing the decision rule as .
The Perceptron Learning Algorithm is an online update rule: for each training observation , if the current weight vector misclassifies the point (meaning ), we update the weights:
where is the learning rate.
### Proof of the Perceptron Convergence Theorem (Novikoff, 1962):
Let the training dataset be linearly separable. This assumption guarantees the existence of a unique, optimal separating weight vector such that:
where represents the functional margin, and we normalize . Let be the maximum Euclidean norm of the input vectors.
Let the initial weights be . Suppose the algorithm makes its -th mistake on observation , updating from to with :
1. **Lower Bound on **:
Taking the inner product of both sides with :
Using the separating margin condition :
By induction, starting from :
By the Cauchy-Schwarz inequality, since :
2. **Upper Bound on **:
Computing the squared norm of :
Since a mistake was made, the term . Furthermore, :
By induction, starting from :
3. **Combining the Bounds**:
Combining the lower and upper bounds on :
This elegant proof establishes that the perceptron is guaranteed to converge to a separating hyperplane in at most steps, depending entirely on the ratio of data spread to the margin.
However, in 1969, Minsky and Papert proved that a single-layer perceptron cannot represent the XOR function because XOR is not linearly separable, inducing a structural bottleneck that was only resolved by multi-layer networks.
Key Equations
Test Your Knowledge
Check whether you have mastered this concept with a quick quiz.
Was this lesson helpful?
Your feedback helps us continuously improve the curriculum and interactive visualizations.