From Neurons to Networks
Perceptrons, multilayer networks and activation functions.
Rosenblatt's perceptron learns a line from its own mistakes, and in 1962 Novikoff proved that it stops making them after at most mistakes, however many examples arrive. Stack such units with smooth nonlinearities between them and the line can bend into any shape. This lesson derives both halves: the convergence theorem for one neuron, and the machinery of multilayer networks and their activation functions.
What you’ll learn
- State the perceptron rule in vector form and interpret it as stochastic gradient descent on the perceptron criterion.
- Prove Novikoff's mistake bound , and describe the voted and averaged perceptrons for non-separable data.
- Write the forward pass of a multilayer perceptron in matrix form, count its parameters and derive the output-layer gradient.
- Compare activation functions by range, derivative and failure modes, and explain the vanishing-gradient bound for sigmoids.
The perceptron as an online learner
Take labels and predict . Absorb the bias by appending a constant: and , so and the boundary is a hyperplane through the origin of the augmented space. From here on the tildes are dropped. The perceptron processes examples one at a time and changes only when it errs:
PERCEPTRON(examples (x_i, y_i) with y_i ∈ {−1, +1}, learning rate η > 0)
w ← 0 // augmented: every x_i ends with a 1
repeat until a full pass makes no update:
for i = 1..n:
if y_i (w · x_i) ≤ 0: // wrong side, or on the boundary
w ← w + η y_i x_i
return wWith labels the same rule reads , as in the Input Layer. One pass over the data is an epoch.
Geometrically, an update on adds to that example's signed score , tilting the boundary toward classifying it correctly. The rule is stochastic subgradient descent on the perceptron criterion , whose subgradient at a misclassified example is . Unlike logistic regression's loss, this one is zero for every separating , so the perceptron stops at the first separator it finds, with no preference for a wide margin.
The perceptron updates on a misclassified example with learning rate . What happens to that example's score ?
- It becomes positive, so the example is now classified correctly
- It increases by exactly
- It increases by exactly
- It is unchanged; the update affects only the other examples
Show the answer
B. It increases by exactly
. Whether it crosses zero depends on how negative it was, so one update need not fix the example.
Novikoff’s convergence theorem
Take and let be the weights after updates. Each update adds some with , so the component along grows at least linearly:
Updates happen only when , so the squared norm grows at most linearly:
Combine with Cauchy–Schwarz, since . Linear growth cannot outrun square-root growth for long:
For general , induction shows : every sign test gives the same answer, so the same updates occur. From , the learning rate only rescales the weights.
The bound depends on geometry alone, not on the dimension or the number of examples: a stream of a million separable examples triggers at most updates. For AND on the augmented points have and the best separator has margin , so the bound is 51. From , visiting in order, the pseudocode above makes 18 updates; the widget below, which counts a point exactly on the line as class 0 and so skips some updates, makes 10.
Starting from on separable data, you rerun the perceptron with instead of . How does the number of updates change?
- About five times fewer
- It stays exactly the same
- About five times more
- It can change unpredictably
Show the answer
B. It stays exactly the same
All weights are scaled by 5 at every step, so every sign test, and hence every update, is identical. The learning rate matters only when the starting point is not 0, because then it sets the size of the updates relative to the initial weights.
Non-separable data: voted and averaged perceptrons
On XOR no separator exists (the impossibility proof is in A Short History of AI), and the rule never stops. The weights do not blow up: for a finite dataset they stay bounded in any order of presentation, the perceptron cycling theorem. But the final depends on where in the cycle you happen to stop. Freund and Schapire (1999) turned the whole sequence of intermediate weight vectors into a stable predictor:
VOTED-PERCEPTRON(examples, epochs T)
k ← 0; w_0 ← 0; c_0 ← 0 // c_k counts how long w_k survived
repeat T times:
for i = 1..n:
if y_i (w_k · x_i) ≤ 0: w_{k+1} ← w_k + y_i x_i; c_{k+1} ← 1; k ← k + 1
else: c_k ← c_k + 1
voted(x) = sign( Σ_j c_j · sign(w_j · x) )
averaged(x) = sign( (Σ_j c_j w_j) · x ) // a single vectorWeight vectors that survived many examples get many votes. The averaged version keeps one vector, so it is as cheap as the plain perceptron at prediction time; it became a standard tool for structured prediction in NLP (Collins, 2002).
Freund and Schapire also proved an online-to-batch guarantee: if the examples are i.i.d., the voted perceptron trained by one pass over examples errs on the next one with probability at most times the expected (plus a margin-violation term when the data are not separable). A large margin yields good generalization without ever maximizing the margin, the quantity that support vector machines maximize explicitly.
Multilayer perceptrons
A multilayer perceptron alternates affine maps with an elementwise activation : and for the hidden layers, then an output fed to a sigmoid (two classes) or a softmax (several). A layer of units on top of has parameters. A mini-batch stacked as rows of costs one matrix product per layer: .
For and , training minimizes the cross-entropy, and the sigmoid's derivative is :
The chain rule collapses to "prediction minus target":
The same holds for softmax with cross-entropy, . Backpropagation (Backpropagation & Optimization) carries this error signal down through the layers; for the last weights it is one outer product:
Think first Why can no network with two hidden units (and an increasing activation) enclose the disk?
The output is . If are independent, pick a direction with of the same sign as for both units: two linear conditions in the plane can always be met. Moving along never lowers either term, so from every point assigned to the disk's class the whole ray in direction stays in that class, a band that must cut through the ring. (If , the output is constant along entire lines.) The same argument in shows that a bounded decision region needs at least hidden units.
How many trainable parameters (weights and biases) does a network have?
Show the answer
105
. The neural network widget displays the count; build this network on any dataset to check.
Activation functions
| Name | Notes | ||
|---|---|---|---|
| Step | (for ) | the perceptron; no gradient to follow | |
| Sigmoid | range ; saturates; not zero-centered | ||
| tanh | range ; zero-centered; saturates | ||
| ReLU | no saturation for ; units can "die" | ||
| Leaky ReLU | , | or | keeps a gradient for |
| GELU | smooth; minimum ; standard in transformers (Hendrycks & Gimpel, 2016) | ||
| SiLU (Swish) | smooth; minimum |
With and , the chain rule passes the gradient down one layer through a diagonal matrix of derivatives, each at most :
Unless the weights are large, which pushes units into saturation where is far below , the signal reaching the first layers shrinks geometrically: the vanishing-gradient problem. With unit-norm weights and ten layers:
ReLU's derivative is exactly 1 on active units, so active paths pass gradients without shrinking. With suitable initialization (He et al., 2015) this is a large part of why deep networks with ReLUs became trainable (Glorot, Bordes & Bengio, 2011).
Key takeaways
- The perceptron updates only on mistakes: SGD on , which is satisfied by any separator.
- Novikoff: with radius and margin the perceptron makes at most updates, independent of dimension, data size, order and (from ) the learning rate.
- Without a separator the weights cycle; voted and averaged perceptrons weight intermediate vectors by survival time and come with an online-to-batch guarantee. The dual form gives the kernel perceptron.
- An MLP alternates affine maps and nonlinearities; with sigmoid or softmax outputs and cross-entropy, the output error signal is . In , a bounded decision region needs at least hidden units.
- Sigmoid derivatives are at most , so deep sigmoid stacks shrink gradients geometrically; ReLU-family activations (ReLU, leaky ReLU, GELU, SiLU) keep active paths open.
Check yourself
In the interactive lesson these are scored with your confidence, and what you miss comes back for review.
Every augmented example vector is multiplied by 2, with the labels unchanged. What happens to the Novikoff bound ?
- It becomes 4 times larger
- It doubles
- It is unchanged
- It becomes 4 times smaller
Show the answer
C. It is unchanged
doubles, and so does the margin for the same unit vector . The ratio is scale-free, as it must be: scaling the inputs does not change which points the perceptron gets wrong.
The perceptron rule is stochastic (sub)gradient descent with step size on which per-example loss?
- The hinge loss
- The logistic loss
- The squared loss
- The perceptron criterion
Show the answer
D. The perceptron criterion
Its subgradient is when (choosing it at the kink) and otherwise, which gives exactly on mistakes. It is zero for every separator, so it has no preference for wide margins.
On data that are not linearly separable, why is the averaged perceptron preferred to the last weight vector?
- The last vector depends on the last few mistakes and jumps around as the cycle continues; weighting all vectors by survival time gives a stable predictor with a generalization guarantee
- Averaging makes the data linearly separable
- The averaged perceptron converges to the maximum-margin separator
- The last vector is always worse than random guessing
Show the answer
A. The last vector depends on the last few mistakes and jumps around as the cycle continues; weighting all vectors by survival time gives a stable predictor with a generalization guarantee
Without a separator the rule cycles forever. Long-surviving vectors are the reliable ones, and Freund and Schapire's online-to-batch argument bounds the voted predictor's expected error.
In a 20-layer network with sigmoid activations, the first layers barely change during training. What is the most direct cause?
- The learning rate is too large
- Each layer multiplies the backpropagated gradient by sigmoid derivatives of at most , so it shrinks geometrically with depth
- Sigmoid networks cannot represent functions of 20 layers
- The cross-entropy loss has no gradient for sigmoid outputs
Show the answer
B. Each layer multiplies the backpropagated gradient by sigmoid derivatives of at most , so it shrinks geometrically with depth
Unless weights are large, which saturates the units and makes even smaller, the gradient at layer 1 carries a factor like . ReLUs, careful initialization, normalization and residual connections all attack this.
A one-hidden-layer tanh network must separate a disk of points from a ring of points around it in the plane. What is the fewest hidden units that can do it?
- 1
- 2
- 3
- It cannot be done with one hidden layer
Show the answer
C. 3
With at most two units, some direction increases both units' contributions, so every decision region is unbounded and cuts through the ring. Three soft ridges can enclose a triangle around the disk, which is what the widget finds. In the minimum is .
Go deeper
- Perceptron Convergence & Its Limits · Novikoff’s theorem and the XOR problem.
- Universal Approximation Theorems · What one hidden layer can and cannot do efficiently.
- Why Depth Helps · Depth separations and compositional functions.
Further reading
- F. Rosenblatt, "The perceptron: A probabilistic model for information storage and organization in the brain," Psychological Review 65, 386–408 (1958).
- A. B. J. Novikoff, "On convergence proofs on perceptrons," Proceedings of the Symposium on the Mathematical Theory of Automata 12, 615–622 (Polytechnic Institute of Brooklyn, 1962).
- Y. Freund & R. E. Schapire, "Large margin classification using the perceptron algorithm," Machine Learning 37, 277–296 (1999).
- I. Goodfellow, Y. Bengio & A. Courville, Deep Learning, ch. 6 (MIT Press, 2016).