Section 2.2
The Universal Approximation Theorem

The celebrated universal approximation theorem [18, 48] states that for any continuous function \(f: \reals^n \to \reals\) and well-behaved activation function \(\sigma: \reals \to \reals\) (such as the logistic function), then there exists parameters \(A \in \reals^{m \times n}\), \(b \in \reals^m\), \(c \in \reals^m\), and \(d \in \reals\) such that the function \(\hat{f}\) defined by

approximates the function \(f\) everywhere. That is, \(|\hat{f}(x) - f(x)| \leq \epsilon\) for all \(x\).

A visual argument for why the universal approximation theorem holds true is shown in Figure 16. The argument goes as follows. Suppose we have some function \(f\). For simplicity we will assume that the function is defined over the reals (i.e., \(n = 1\)). Then we can break the domain of the function into small mutually exclusive and exhaustive intervals. For each interval \((\alpha, \beta]\) we can define two logistic functions, the first shifted to the start of the interval and the second shifted to the end of the interval. For example,

Subtracting the second logistic from the first produces a hump-shaped function centred on the interval. We can scale this hump to approximate \(f\) over the interval. Let \(\gamma\) be the value of the function, say, at the midpoint of the interval, i.e., \(\gamma = f\!\left(\frac{\alpha + \beta}{2}\right)\). Then the expression,

is a good approximation to the function \(f\) in the interval \((\alpha, \beta]\). We can make the edges of the hump arbitrarily sharp using temperature scaling,

Repeating this process for all of the intervals give the approximation for \(f\) everywhere, completing the argument. For higher-dimensions we would need to combine functions \(\sigma(a^Tx + b)\) using different choices of \(a\) and \(b\) to create an \(n\)-D bump approximating a delta function, which can then be placed at all offsets and scales. Note that the actual proof for the universal approximation theorem is somewhat more technical and relies on results from functional analysis rather than the visual argument presented here.

The universal approximation theorem is a nice theoretical result—we can approximate any reasonable function with a two-layer network (without the final activation function). But the theorem suffers from two practical shortcomings. First, it does not tell us how many parameters we need in the network, and experience suggests that for two-layer networks we need a very large number of parameters to approximate functions well. Second, it does not tell us how to find the parameter values in an efficient way. In turns out that we can reduce the number of parameters by going to deeper networks, i.e., more than two layers. Moreover, learning appears to be easier in deeper networks, although the theory here is not currently well understood. In practice, we often choose activation functions that violate the assumptions of the universal approximation theorem, such as ReLU, and this doesn’t seem to affect the ability for deep networks to learn. Indeed, it often learns better.

A topic that is not taught much, but which is important for understanding learning and comparing trained networks is identifiability.¹ This refers to whether we are able to uniquely identify a multi-layer perceptron’s parameters from the function that it produces, i.e., its input-output relationship. The answer is that we cannot, i.e., the parameters of a neural network are never unique in that there exists a different set of parameters that produce exactly the same input-output mapping. We can see one specific example of how this may happen as follows. Let \(P \in \reals^{m \times m}\) be a permutation matrix and consider the two-layer perceptron from Figure 14, where we omit the final activation function for brevity. Then,

Therefore, parameters \(\{A, b, c, d\}\) and \(\{\tilde{A}, \tilde{b}, \tilde{c}, d\}\) produce exactly the same outputs.