Simple Algorithm
Artificial Intelligence · Hidden Layer · 22 min

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 (R/γ)2(R/\gamma)^2 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 (R/γ)2(R/\gamma)^2, 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 y∈{−1,+1}y\in\{-1,+1\} and predict y^=sign⁡(w⋅x+b)\hat y=\sign(\mathbf w\cdot\mathbf x+b). Absorb the bias by appending a constant: x~=(x,1)\tilde{\mathbf x}=(\mathbf x,1) and w~=(w,b)\tilde{\mathbf w}=(\mathbf w,b), so y^=sign⁡(w~⋅x~)\hat y=\sign(\tilde{\mathbf w}\cdot\tilde{\mathbf x}) 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 w\mathbf w only when it errs:

text
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 w

With labels t∈{0,1}t\in\{0,1\} the same rule reads w←w+η(t−y^)x\mathbf w\leftarrow\mathbf w+\eta(t-\hat y)\mathbf x, as in the Input Layer. One pass over the data is an epoch.

Geometrically, an update on (x,y)(\mathbf x,y) adds η∥x∥2\eta\norm{\mathbf x}^2 to that example's signed score y w⋅xy\,\mathbf w\cdot\mathbf x, tilting the boundary toward classifying it correctly. The rule is stochastic subgradient descent on the perceptron criterion L(w)=∑imax⁡(0,−yi w⋅xi)L(\mathbf w)=\sum_i\max(0,-y_i\,\mathbf w\cdot\mathbf x_i), whose subgradient at a misclassified example is −yixi-y_i\mathbf x_i. Unlike logistic regression's loss, this one is zero for every separating w\mathbf w, so the perceptron stops at the first separator it finds, with no preference for a wide margin.

Check your understanding

The perceptron updates on a misclassified example (x,y)(\mathbf x,y) with learning rate η\eta. What happens to that example's score y w⋅xy\,\mathbf w\cdot\mathbf x?

  1. It becomes positive, so the example is now classified correctly
  2. It increases by exactly η∥x∥2\eta\norm{\mathbf x}^2
  3. It increases by exactly η\eta
  4. It is unchanged; the update affects only the other examples
Show the answer

B. It increases by exactly η∥x∥2\eta\norm{\mathbf x}^2

y(w+ηyx)⋅x=y w⋅x+ηy2∥x∥2=y w⋅x+η∥x∥2y(\mathbf w+\eta y\mathbf x)\cdot\mathbf x=y\,\mathbf w\cdot\mathbf x+\eta y^2\norm{\mathbf x}^2=y\,\mathbf w\cdot\mathbf x+\eta\norm{\mathbf x}^2. Whether it crosses zero depends on how negative it was, so one update need not fix the example.

Novikoff’s convergence theorem

DerivationProof
  1. u⋅wk=u⋅wk−1+yi u⋅xi ≥ u⋅wk−1+γ⟹u⋅wk≥kγ\mathbf u\cdot\mathbf w_k=\mathbf u\cdot\mathbf w_{k-1}+y_i\,\mathbf u\cdot\mathbf x_i\ \ge\ \mathbf u\cdot\mathbf w_{k-1}+\gamma\quad\Longrightarrow\quad\mathbf u\cdot\mathbf w_k\ge k\gamma

    Take η=1\eta=1 and let wk\mathbf w_k be the weights after kk updates. Each update adds some yixiy_i\mathbf x_i with yi u⋅xi≥γy_i\,\mathbf u\cdot\mathbf x_i\ge\gamma, so the component along u\mathbf u grows at least linearly:

  2. ∥wk∥2=∥wk−1∥2+2yi wk−1⋅xi+∥xi∥2≤∥wk−1∥2+R2⟹∥wk∥2≤kR2\norm{\mathbf w_k}^2=\norm{\mathbf w_{k-1}}^2+2y_i\,\mathbf w_{k-1}\cdot\mathbf x_i+\norm{\mathbf x_i}^2\le\norm{\mathbf w_{k-1}}^2+R^2\quad\Longrightarrow\quad\norm{\mathbf w_k}^2\le kR^2

    Updates happen only when yi wk−1⋅xi≤0y_i\,\mathbf w_{k-1}\cdot\mathbf x_i\le0, so the squared norm grows at most linearly:

  3. kγ ≤ u⋅wk ≤ ∥wk∥ ≤ k R⟹k≤(Rγ)2k\gamma\ \le\ \mathbf u\cdot\mathbf w_k\ \le\ \norm{\mathbf w_k}\ \le\ \sqrt k\,R\quad\Longrightarrow\quad k\le\Big(\frac R\gamma\Big)^2

    Combine with Cauchy–Schwarz, u⋅wk≤∥wk∥\mathbf u\cdot\mathbf w_k\le\norm{\mathbf w_k} since ∥u∥=1\norm{\mathbf u}=1. Linear growth cannot outrun square-root growth for long:

  4. sign⁡(η w⋅x)=sign⁡(w⋅x)⟹identical updates for every η>0\sign\big(\eta\,\mathbf w\cdot\mathbf x\big)=\sign(\mathbf w\cdot\mathbf x)\quad\Longrightarrow\quad\text{identical updates for every }\eta>0

    For general η\eta, induction shows wk(η)=η wk(1)\mathbf w_k^{(\eta)}=\eta\,\mathbf w_k^{(1)}: every sign test gives the same answer, so the same updates occur. From w=0\mathbf w=0, 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 (R/γ)2(R/\gamma)^2 updates. For AND on {0,1}2\{0,1\}^2 the augmented points have R=3R=\sqrt3 and the best separator has margin γ=1/17≈0.243\gamma=1/\sqrt{17}\approx0.243, so the bound is 51. From w=0\mathbf w=0, visiting (0,0),(0,1),(1,0),(1,1)(0,0),(0,1),(1,0),(1,1) 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.

Check your understanding

Starting from w=0\mathbf w=0 on separable data, you rerun the perceptron with η=1\eta=1 instead of η=0.2\eta=0.2. How does the number of updates change?

  1. About five times fewer
  2. It stays exactly the same
  3. About five times more
  4. 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 w\mathbf w 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:

text
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 vector

Weight 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 mm examples errs on the next one with probability at most 2m+1\frac2{m+1} times the expected (R/γ)2(R/\gamma)^2 (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 φ\varphi: h(0)=x\mathbf h^{(0)}=\mathbf x and h(l)=φ(W(l)h(l−1)+b(l))\mathbf h^{(l)}=\varphi\big(\mathbf W^{(l)}\mathbf h^{(l-1)}+\mathbf b^{(l)}\big) for the hidden layers, then an output z=W(L)h(L−1)+b(L)z=\mathbf W^{(L)}\mathbf h^{(L-1)}+b^{(L)} fed to a sigmoid (two classes) or a softmax (several). A layer of nln_l units on top of nl−1n_{l-1} has nlnl−1+nln_ln_{l-1}+n_l parameters. A mini-batch stacked as rows of H(l−1)H^{(l-1)} costs one matrix product per layer: H(l)=φ(H(l−1)W(l)⊤+1b(l)⊤)H^{(l)}=\varphi\big(H^{(l-1)}\mathbf W^{(l)\top}+\mathbf 1\mathbf b^{(l)\top}\big).

XOR(x1,x2)=ReLU(x1+x2)−2 ReLU(x1+x2−1)(x1,x2∈{0,1})\mathrm{XOR}(x_1,x_2)=\mathrm{ReLU}(x_1+x_2)-2\,\mathrm{ReLU}(x_1+x_2-1)\qquad(x_1,x_2\in\{0,1\})
Check the corners: 0−00-0, 1−01-0, 1−01-0, 2−22-2. Two hidden units do what no single unit can.
DerivationThe output layer and its gradient
  1. ℓ=−yln⁡p−(1−y)ln⁡(1−p),dpdz=p(1−p)\ell=-y\ln p-(1-y)\ln(1-p),\qquad\frac{dp}{dz}=p(1-p)

    For y∈{0,1}y\in\{0,1\} and p=σ(z)p=\sigma(z), training minimizes the cross-entropy, and the sigmoid's derivative is σ′=σ(1−σ)\sigma'=\sigma(1-\sigma):

  2. ∂ℓ∂z=(−yp+1−y1−p) p(1−p)=p−y\frac{\partial\ell}{\partial z}=\Big(-\frac yp+\frac{1-y}{1-p}\Big)\,p(1-p)=p-y

    The chain rule collapses to "prediction minus target":

  3. ∂ℓ∂W(L)=(p−y) h(L−1)⊤\frac{\partial\ell}{\partial\mathbf W^{(L)}}=(p-y)\,\mathbf h^{(L-1)\top}

    The same holds for softmax with cross-entropy, ∂ℓ/∂zk=pk−1[y=k]\partial\ell/\partial z_k=p_k-\mathbf 1[y=k]. 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 σ(v1φ(a1⋅x+b1)+v2φ(a2⋅x+b2)+c)\sigma\big(v_1\varphi(\mathbf a_1\cdot\mathbf x+b_1)+v_2\varphi(\mathbf a_2\cdot\mathbf x+b_2)+c\big). If a1,a2\mathbf a_1,\mathbf a_2 are independent, pick a direction r\mathbf r with aj⋅r\mathbf a_j\cdot\mathbf r of the same sign as vjv_j for both units: two linear conditions in the plane can always be met. Moving along r\mathbf r never lowers either term, so from every point assigned to the disk's class the whole ray in direction r\mathbf r stays in that class, a band that must cut through the ring. (If a1∥a2\mathbf a_1\parallel\mathbf a_2, the output is constant along entire lines.) The same argument in Rd\R^d shows that a bounded decision region needs at least d+1d+1 hidden units.

Predict before you look

How many trainable parameters (weights and biases) does a 2→8→8→12\to8\to8\to1 network have?

Show the answer

105

(2⋅8+8)+(8⋅8+8)+(8⋅1+1)=24+72+9=105(2\cdot8+8)+(8\cdot8+8)+(8\cdot1+1)=24+72+9=105. The neural network widget displays the count; build this network on any dataset to check.

Activation functions

Nameφ(z)\varphi(z)φ′(z)\varphi'(z)Notes
Step1[z>0]\mathbf 1[z>0]00 (for z≠0z\neq0)the perceptron; no gradient to follow
Sigmoid1/(1+e−z)1/(1+e^{-z})σ(1−σ)≤14\sigma(1-\sigma)\le\tfrac14range (0,1)(0,1); saturates; not zero-centered
tanh2σ(2z)−12\sigma(2z)-11−tanh⁡2z≤11-\tanh^2z\le1range (−1,1)(-1,1); zero-centered; saturates
ReLUmax⁡(0,z)\max(0,z)1[z>0]\mathbf 1[z>0]no saturation for z>0z>0; units can "die"
Leaky ReLUmax⁡(αz,z)\max(\alpha z,z), α≈0.01\alpha\approx0.01α\alpha or 11keeps a gradient for z<0z<0
GELUz Φ(z)z\,\Phi(z)Φ(z)+z ϕ(z)\Phi(z)+z\,\phi(z)smooth; minimum ≈−0.17\approx-0.17; standard in transformers (Hendrycks & Gimpel, 2016)
SiLU (Swish)z σ(z)z\,\sigma(z)σ(z)(1+z(1−σ(z)))\sigma(z)\big(1+z(1-\sigma(z))\big)smooth; minimum ≈−0.28\approx-0.28
Φ\Phi and ϕ\phi are the standard normal CDF and density. Since tanh⁡(z)=2σ(2z)−1\tanh(z)=2\sigma(2z)-1, a tanh network equals a sigmoid network with rescaled weights and biases; tanh is preferred in hidden layers because it is zero-centered.
DerivationWhy deep sigmoid networks are hard to train
  1. ∂ℓ∂h(l−1)=W(l)⊤diag⁡(σ′(z(l))) ∂ℓ∂h(l)⟹∥∂ℓ∂h(1)∥≤∥∂ℓ∂h(L)∥∏l=2L∥W(l)∥4\frac{\partial\ell}{\partial\mathbf h^{(l-1)}}=\mathbf W^{(l)\top}\operatorname{diag}\big(\sigma'(\mathbf z^{(l)})\big)\,\frac{\partial\ell}{\partial\mathbf h^{(l)}}\quad\Longrightarrow\quad\Big\lVert\frac{\partial\ell}{\partial\mathbf h^{(1)}}\Big\rVert\le\Big\lVert\frac{\partial\ell}{\partial\mathbf h^{(L)}}\Big\rVert\prod_{l=2}^{L}\frac{\norm{\mathbf W^{(l)}}}{4}

    With h(l)=σ(z(l))\mathbf h^{(l)}=\sigma(\mathbf z^{(l)}) and z(l)=W(l)h(l−1)+b(l)\mathbf z^{(l)}=\mathbf W^{(l)}\mathbf h^{(l-1)}+\mathbf b^{(l)}, the chain rule passes the gradient down one layer through a diagonal matrix of derivatives, each at most 14\tfrac14:

  2. 4−9≈3.8×10−64^{-9}\approx3.8\times10^{-6}

    Unless the weights are large, which pushes units into saturation where σ′\sigma' is far below 14\tfrac14, the signal reaching the first layers shrinks geometrically: the vanishing-gradient problem. With unit-norm weights and ten layers:

  3. ReLU′(z)=1[z>0]∈{0,1}\mathrm{ReLU}'(z)=\mathbf 1[z>0]\in\{0,1\}

    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 w←w+ηyx\mathbf w\leftarrow\mathbf w+\eta y\mathbf x only on mistakes: SGD on max⁡(0,−y w⋅x)\max(0,-y\,\mathbf w\cdot\mathbf x), which is satisfied by any separator.
  • Novikoff: with radius RR and margin γ\gamma the perceptron makes at most (R/γ)2(R/\gamma)^2 updates, independent of dimension, data size, order and (from w=0\mathbf w=0) 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 p−yp-y. In Rd\R^d, a bounded decision region needs at least d+1d+1 hidden units.
  • Sigmoid derivatives are at most 14\tfrac14, 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.

Question 1

Every augmented example vector is multiplied by 2, with the labels unchanged. What happens to the Novikoff bound (R/γ)2(R/\gamma)^2?

  1. It becomes 4 times larger
  2. It doubles
  3. It is unchanged
  4. It becomes 4 times smaller
Show the answer

C. It is unchanged

RR doubles, and so does the margin γ=min⁡iyi u⋅xi\gamma=\min_iy_i\,\mathbf u\cdot\mathbf x_i for the same unit vector u\mathbf u. The ratio is scale-free, as it must be: scaling the inputs does not change which points the perceptron gets wrong.

Question 2

The perceptron rule is stochastic (sub)gradient descent with step size η\eta on which per-example loss?

  1. The hinge loss max⁡(0, 1−y w⋅x)\max(0,\,1-y\,\mathbf w\cdot\mathbf x)
  2. The logistic loss ln⁡(1+e−y w⋅x)\ln(1+e^{-y\,\mathbf w\cdot\mathbf x})
  3. The squared loss (y−w⋅x)2(y-\mathbf w\cdot\mathbf x)^2
  4. The perceptron criterion max⁡(0, −y w⋅x)\max(0,\,-y\,\mathbf w\cdot\mathbf x)
Show the answer

D. The perceptron criterion max⁡(0, −y w⋅x)\max(0,\,-y\,\mathbf w\cdot\mathbf x)

Its subgradient is −yx-y\mathbf x when y w⋅x≤0y\,\mathbf w\cdot\mathbf x\le0 (choosing it at the kink) and 00 otherwise, which gives exactly w←w+ηyx\mathbf w\leftarrow\mathbf w+\eta y\mathbf x on mistakes. It is zero for every separator, so it has no preference for wide margins.

Question 3

On data that are not linearly separable, why is the averaged perceptron preferred to the last weight vector?

  1. 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
  2. Averaging makes the data linearly separable
  3. The averaged perceptron converges to the maximum-margin separator
  4. 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.

Question 4

In a 20-layer network with sigmoid activations, the first layers barely change during training. What is the most direct cause?

  1. The learning rate is too large
  2. Each layer multiplies the backpropagated gradient by sigmoid derivatives of at most 14\tfrac14, so it shrinks geometrically with depth
  3. Sigmoid networks cannot represent functions of 20 layers
  4. 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 14\tfrac14, so it shrinks geometrically with depth

Unless weights are large, which saturates the units and makes σ′\sigma' even smaller, the gradient at layer 1 carries a factor like (∥W∥/4)19(\norm{\mathbf W}/4)^{19}. ReLUs, careful initialization, normalization and residual connections all attack this.

Question 5

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. 1
  2. 2
  3. 3
  4. 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 Rd\R^d the minimum is d+1d+1.

Go deeper

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).