Machine Learning 1, companion to the lecture on universal approximation
A neural network with one hidden layer of ReLU units, one input and one output draws a polyline. Each unit contributes one corner, and training decides where the corners go. This page builds that polyline from single units, fits it to a curve, and shows what happens to the fit as the network gets wider.
A hidden unit computes h(a x + b) with h(z) = max(0, z). Its output is zero where a x + b is negative and grows linearly on the other side, so its graph is a hinge with the corner at x = −b/a. The network scales each unit by an output weight and adds a constant:
y(x) = c + ∑m=1M vm max(0, am x + bm)
Every term is continuous and straight except at its own kink, so the sum is continuous and straight except at the kinks. With M units the graph is a polyline with at most M + 1 pieces. Units whose kink falls outside the interval add no corner there, only a straight contribution, which is why a trained network often shows fewer pieces than it could.
The converse also holds. Take any continuous polyline on an interval [L, R], with corners at p1, …, pk and slopes s0, …, sk on the pieces between them. Then
f(x) = f(L) + s0 max(0, x − L) + ∑j=1k (sj − sj−1) max(0, x − pj)
on the whole interval. The first unit supplies the starting slope, and each corner gets a unit whose output weight is the change in slope at that corner. So on an interval, the one-layer ReLU networks and the continuous polylines are the same functions, and a smooth curve can be approximated by a network exactly as well as it can be approximated by a polyline.
That is easy to quantify. A polyline through the curve with pieces of width h is off by at most h² max|f″| / 8. Doubling the number of pieces halves h, which divides the largest error by four and the mean squared error by roughly sixteen. The gray line in the fifth step follows that rate.
What this page shows in one dimension holds in general. Let f be a continuous function on a closed and bounded region of ℝD, and let the activation h be piecewise continuous, bounded on bounded sets, and not a polynomial. Then for every tolerance ε > 0 there is a network with one hidden layer whose output stays within ε of f everywhere on the region. ReLU meets the conditions. The result in this form is due to Leshno, Lin, Pinkus and Schocken (1993).
The theorem says such a network exists. It does not say how many units it takes, and it does not say that gradient descent will find it. The last two steps show both gaps on this small problem. Training puts the corners where the curve bends, which beats evenly spaced kinks at small widths. From about 14 units on it falls behind, and at 40 units evenly spaced kinks are about ten times better. Some units also get stuck for good. A unit whose kink leaves the data outputs zero on every point, receives no gradient, and stays dead. It happens in wide networks too. Every one of the first eight training runs with 20 units lost between one and four units this way.
With the kinks held fixed, the network is linear in c and the output weights, so the best output weights solve a least squares problem. It is the same problem as linear regression with basis functions, with the units in the role of the basis functions. The difference is that training also moves them.