Neural networks: From the perceptron to universal approximation

In 1943 the neurophysiologist Warren McCulloch and the young logician Walter Pitts published “A Logical Calculus of the Ideas Immanent in Nervous Activity”. They modelled the neuron as a switch that fires if the sum of its inputs exceeds a threshold, and showed that networks of such neurons can compute any logical function. It was the first time anyone connected the brain with Turing's computation. The crucial piece was missing: how those connections learn.

The perceptron

In 1949 the psychologist Donald Hebb proposed that connections between neurons that fire together are strengthened. Frank Rosenblatt, a psychologist at the Cornell Aeronautical Laboratory, turned that intuition into an algorithm in 1957: the perceptron. It computes a weighted sum of its inputs and answers with its sign:

\hat{y} = sgn (𝐰 \cdot 𝐱 + b) \in {- 1, + 1} .

Geometrically, the equation $𝐰 \cdot 𝐱 + b = 0$ is a line (a hyperplane in high dimension) that splits space in two, one half for each class. What was new was the learning rule: whenever the perceptron gets an example $(𝐱, y)$ wrong, it corrects

𝐰 \leftarrow 𝐰 + η y 𝐱, b \leftarrow b + η y .

If it classifies correctly, it changes nothing. Rosenblatt built a physical version, the Mark I Perceptron, with 400 photocells and potentiometers driven by electric motors as adjustable weights. In July 1958, after a public demonstration, the New York Times wrote that the Navy expected it to be the embryo of a computer able to “walk, talk, see, write, reproduce itself and be conscious of its existence”.

A classification lab. Click to add points of the chosen class. With separable data the perceptron finds a line in a few passes, as Novikoff's theorem guarantees. With XOR it never succeeds: switch to the hidden-layer network and watch it bend the boundary. The background shows the model's confidence in each region.

Theorem (perceptron convergence; Novikoff, 1962)

Suppose $‖ 𝐱_{i} ‖ \leq R$ for every example and there is a unit vector $𝐰^{*}$ that separates the classes with margin $γ > 0$ : $y_{i} (𝐰^{*} \cdot 𝐱_{i}) \geq γ$ . Then the perceptron (with $b$ folded into $𝐰$ and starting from $𝐰 = 𝟎$ ) makes at most

{(\frac{R}{γ})}^{2}

mistakes, regardless of the order of the examples or how many there are.

Proof

Let $𝐰_{k}$ be the vector after the $k$ -th mistake, made on $(𝐱, y)$ . Take $η = 1$ , since its value does not affect the result. Two bounds:

It grows in the right direction: $𝐰_{k} \cdot 𝐰^{*} = 𝐰_{k - 1} \cdot 𝐰^{*} + y 𝐱 \cdot 𝐰^{*} \geq 𝐰_{k - 1} \cdot 𝐰^{*} + γ$ , so $𝐰_{k} \cdot 𝐰^{*} \geq k γ$ .

It does not grow too much: $‖ 𝐰_{k} ‖^{2} = ‖ 𝐰_{k - 1} ‖^{2} + 2 y 𝐰_{k - 1} \cdot 𝐱 + ‖ 𝐱 ‖^{2} \leq ‖ 𝐰_{k - 1} ‖^{2} + R^{2}$ , because there was a mistake ( $y 𝐰_{k - 1} \cdot 𝐱 \leq 0$ ). So $‖ 𝐰_{k} ‖^{2} \leq k R^{2}$ .

By Cauchy–Schwarz, $k γ \leq 𝐰_{k} \cdot 𝐰^{*} \leq ‖ 𝐰_{k} ‖ \leq \sqrt{k} R$ , hence $k \leq (R / γ)^{2}$ .

The XOR problem and the first winter

In 1969 Marvin Minsky and Seymour Papert published Perceptrons, a rigorous mathematical analysis of what a single-layer perceptron can and cannot do. The most famous example is “exclusive or” (XOR): output 1 if exactly one of two binary inputs is 1.

Proposition (XOR is not linearly separable)

There are no $w_{1}, w_{2}, b$ such that $sgn (w_{1} x_{1} + w_{2} x_{2} + b)$ is $+ 1$ at $(0, 1)$ and $(1, 0)$ , and $- 1$ at $(0, 0)$ and $(1, 1)$ .

Proof

We would need $b < 0$ , $w_{2} + b > 0$ , $w_{1} + b > 0$ and $w_{1} + w_{2} + b < 0$ . Adding the second and third gives $w_{1} + w_{2} + 2 b > 0$ , that is, $w_{1} + w_{2} + b > - b > 0$ , which contradicts the fourth.

The book acknowledged that multi-layer networks do not have this limitation, but nobody knew how to train them. Together with the Lighthill report (1973) in the UK, the scepticism cut funding and led to the first AI winter. Rosenblatt died in a boating accident in 1971, without seeing his ideas vindicated.

The hidden layer

The solution is composition. A multi-layer neural network applies a linear transformation, a non-linearity, another linear transformation…

f (𝐱) = W_{2} σ (W_{1} 𝐱 + 𝐛_{1}) + 𝐛_{2} .

The hidden-layer neurons compute new features (for XOR, for instance, “at least one input on” and “both inputs on”), and in that new space the problem is separable. As we saw in the linear algebra chapter, without the non-linearity $σ$ everything would collapse into a single matrix. Since 1986 we know how to train these networks with backpropagation and gradient descent. How far does their expressive power reach?

The universal approximation theorem

Theorem (universal approximation; Cybenko 1989, Hornik 1991, Leshno et al. 1993)

Let $σ$ be a continuous sigmoidal function (or, more generally, any continuous function that is not a polynomial). For every continuous function $f : [0, 1]^{d} \to ℝ$ and every $ε > 0$ there exist $N$ and parameters $α_{i}, b_{i} \in ℝ$ , $𝐰_{i} \in ℝ^{d}$ such that

| f (𝐱) - \sum_{i = 1}^{N} α_{i} σ (𝐰_{i} \cdot 𝐱 + b_{i}) | < ε for all 𝐱 \in [0, 1]^{d} .

With a single, wide enough hidden layer, any continuous function can be approximated as closely as you like. In one dimension the idea is easy to see: a very steep sigmoid is almost a step, and a sum of steps can imitate any curve.

A network with one hidden layer of

N

sigmoid neurons approximates the target curve (grey). Each neuron contributes a smooth step at one position; their heights are adjusted to follow the function. As you raise

N

and the steepness

k

, the maximum error falls as low as you want. It is a constructive proof of the theorem in one dimension.

The theorem should be read with care. It guarantees that the approximation exists, but it does not say how many neurons are needed (there may be exponentially many), nor that gradient descent will find it, nor that the network will work well on data it has not seen. Depth matters: there are functions that a deep network represents with few neurons and that a single-layer network would need exponentially more neurons to approximate (Telgarsky, 2016). That is why learning is deep.

The comeback: deep learning

In 1989 Yann LeCun used backpropagation to train a convolutional network that read handwritten ZIP codes for the US Postal Service. Convolutions reuse the same weights at every position of the image, a way of building into the architecture the knowledge that an edge is an edge wherever it appears. Even so, during the 1990s and 2000s other techniques, such as support vector machines, dominated machine learning.

The change came when three ingredients finally coincided: massive data (ImageNet, 2009, with over a million labelled images for its competition), massive compute (GPUs) and a few technical tricks (ReLU, dropout, good initialization). In 2012 the AlexNet network by Alex Krizhevsky, Ilya Sutskever and Geoffrey Hinton won the ImageNet competition with a top-5 error of 15.3%, against 26.2% for the runner-up. Within a few years deep networks came to dominate vision, speech and, later, language.

One mystery remains. Modern networks have far more parameters than training examples: they could memorize everything, and yet they get new data right. Why? That is the question of learning theory.

References

W. S. McCulloch and W. Pitts (1943). “A Logical Calculus of the Ideas Immanent in Nervous Activity”. Bulletin of Mathematical Biophysics, 5.
F. Rosenblatt (1958). “The Perceptron: A Probabilistic Model for Information Storage and Organization in the Brain”. Psychological Review, 65(6).
A. B. J. Novikoff (1962). “On Convergence Proofs on Perceptrons”. Symposium on the Mathematical Theory of Automata, 12.
M. Minsky and S. Papert (1969). Perceptrons. MIT Press.
G. Cybenko (1989). “Approximation by Superpositions of a Sigmoidal Function”. Mathematics of Control, Signals and Systems, 2(4).
K. Hornik (1991). “Approximation Capabilities of Multilayer Feedforward Networks”. Neural Networks, 4(2).
Y. LeCun et al. (1989). “Backpropagation Applied to Handwritten Zip Code Recognition”. Neural Computation, 1(4).
A. Krizhevsky, I. Sutskever and G. E. Hinton (2012). “ImageNet Classification with Deep Convolutional Neural Networks”. NeurIPS.
M. Telgarsky (2016). “Benefits of depth in neural networks”. COLT.

§The perceptron

§The XOR problem and the first winter

§The hidden layer

§The universal approximation theorem

§The comeback: deep learning