7
$\begingroup$

The well-known universal approximation theorem states that neural network with one hidden layer can approximate any continuous function on every compact subset of $\mathbb{R}^d$.

My question is whether there is any paper which considers the approximation on the whole $\mathbb{R}^d$ domain?

In my opinion, since the main themes of neural network are image recognition and natural language processing,

it is enough to consider functions on a compact subset.

However along with its great success, its application field is now widely opened to problems based on whole $\mathbb{R}^d$ domain.

Although I can find some papers (Chen and Chen, 1990; Ito, 1992), they cannot tackle with whole $\mathbb{R}^d$ domain, because the former introduces the "extended real line" $\bar{\mathbb{R}}^d$ instead of $\mathbb{R}^d$, and the latter considers only continuous function with compact support.

If you know the related paper, could you please tell me?

[1] T. Chen, H. Chen, and R.-W. Liu (1990), "A constructive proof of approximation by superposition of sigmoidal functions for neutral networks", preprint.

[2] Y. Ito (1992), "Approximation of continuous functions on $\mathbf{R}^d$ by linear combinations of shifted rotations of a sigmoid function with and without scaling", Neural Networks, Volume 5, Issue 1, pp. 105-115.

$\endgroup$

1 Answer 1

4
$\begingroup$

I do not think a universal approximation theorem on all of $\mathbb{R}^d$ is possible with the uniform norm. In $L^p$ for $p < \infty$ there may be hope in some cases.

Let us first look at the problem in the framework of the classical universal approximation theorem, where we use the uniform norm. I will restrict my attention to $d = 1$, but the argument is the same for arbitrary $d$.

Next, we need to make an assumption on the activation function $\rho$. I would like this activation function to be reasonable in the sense that it satisfies the following property: For every $N \in \mathbb{N}$, there exists a continuous function $f_N$ such that $$ \inf_{g \in nets(N, \rho) }\sup_{x \in [0,1]}|f_N(x) - g(x)| > 1/4, $$ where $nets(N, \rho)$ is the set of neural networks with activation function $\rho$ and $N$ neurons. (The constant $1/4$ is entirely arbitrary and can be replaced by anything positive.) At the end of this answer, I will show that every sensible activation function satisfies this property.

With this notion, it is now pretty easy to show that a universal approximation theorem on $\mathbb{R}$ is impossible. We simply try to approximate a continuous function $f$ which satisfies that $$ f_{[2N, 2N+1]}(x) = f_N(x) \text{ for } x \in \mathbb{R}. $$ Assume that there exists a neural network $g$ that approximates $f$ uniformly with an error of less than $1/4$. Let us say that $g$ has $M$ neurons. Then $g(\cdot -2M)$ is a neural network with $M$ neurons, which on $[0,1]$ approximates $f_{M}$ with an error of less than $1/4$. This is a contradiction.

To finish things, we study the assumption on the activation function. If $\rho$ does not satisfy the assumption above, then there exists an $N^* \in \mathbb{N}$ such that the set of neural networks with $N^*$ neurons approximates every continuous function up to an error at most $1/4$. As a consequence, we can see that $$ \{ \mathrm{sign} \circ g \ \colon \ g \in nets(N, \rho\} $$ is a set of functions with infinite VC dimension. One can find many conditions on activation functions that lead to bounded VC dimensions. For example in Anthony, Bartlett, Neural Network Learning: Theoretical Foundations, 2009, Theorems 8.3, Theorem 8.4, Theorem 8.6, it is shown that piecewise polynomial activation functions and activation functions computed with algorithms that use finitely many arithmetic operations and finitely many comparisons such as $\geq$, $<$, $=$, $\neq$ fall into this category. In addition, from a machine learning perspective, we would not like to work with hypotheses classes of infinite VC dimension anyhow.

Now if we are looking at (unweighted) $L^p$ approximation of continuous functions that are also in $L^p$ then one can be lucky, but it really depends:

  1. Shallow ReLU neural networks in $d > 1$ for example cannot exactly represent compactly supported functions unless they are the zero function. They also only have finitely many piecewise affine pieces. As a result, if a shallow ReLU network is not globally zero, then it will be bounded away from zero on a set of infinite measure. Hence, any global approximation measured with an $L^p$ norm of a compactly supported function will have a constant error.

  2. Deep ReLU neural networks can exactly implement hat functions. Given a continuous $L^p$ function and an $\epsilon > 0$ we can find a compact set $K$ such that if we restrict the function to this set the resulting error would be less than $\epsilon$. Next, we can approximate that restricted function with hat functions which are supported in $K$. This shows the density in $L^p$.

  3. If $p = 2$ and your activation function is such that you can implement basis functions of $L^2$ with a small global(!) $L^2$ error, then this also immediately gives a universal approximation theorem on $L^2$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.