A visual proof that neural nets can compute any function

As the article says:

" If you're a mathematician the argument is not difficult to follow, but it's not so easy for most people. That's a pity, since the underlying reasons for universality are simple and beautiful."

Indeed, as a mathematician, the universality of neural networks is obvious to me from their definition. However, this article is explicitly not aimed at mathematicians, and (as far as I can tell) does a good job of presenting the argument without requiring unnecessary math knowledge, which is something that we tend to be bad at doing.

Furthermore, the universality does not directly follow from the quote you provide, as you would still need to show that the hidden layer neurons form a basis. Infact, the article was about constructing such a basis in the neurons. The only thing that bringing in your quote would serve to do is make the article more confusing by unnecessarily introducing the concept of basis functions.

Right. I had a moment of severe mistrust develop around all the times I've heard the phrase "neural network" mouthed in a pitched voice after I studied the math and realized it was barely cooler than Taylor series approximation. For a moment stacked Boltzmann machines were going to stay in obscurity, but then they became "deep learning" while also solving real problems. If there is one thing I could contribute to the popular programming lexicon, it would be making sure that the phrase "isomorphic" gets used for something other than javascript.

> This is basic and obvious math.

Yes. But only once you prove that these are in fact space-spanning basis functions.

Does slapping the world 'basis' magically make results obvious and interesting? Why? Because the word 'basis' carries some of that abstract-mathematics cachet?

I think one of the caveats was that the function should be relatively smooth and continuous, a mandelbrot set isn't very smooth is it?

The advantage of neural networks is that they can be trained. You can give it a set of inputs and desired outputs, and do gradient descent on it.

Neural networks are essentially like trainable digital circuits. The proof of universality shows that neurons can approximate any kind of logic gate (or any input output mapping, like a lookup table.) A lookup table by itself isn't terribly useful, but you can put them in a series and make arbitrary circuits. And that makes (deep) neural networks strictly more powerful than "shallow" methods.

I think you're correct.

That's one of the issues with results from theoretical math- the result is true, but it might not be useful.

As another commenter in the thread talks about, we can get a nearly identical result by using polynomials of extremely large degree, but that doesn't work well, because of overfitting. We could come up with a polynomial that also calculates with arbitrarily high accuracy if a point is in the Mandelbrot set or not, but it might end up being of 10100 degree, which is useless.

Wavelets are my favorite approximate function to build up with.

But yeah, the overfitting problem / approximation is the real issue. I do like seeing the hybrid approaches (Genetic Algorithsm searching random Neural Nets with a little bit of backpropigation for some measure)

What the author means by "close approximation" is clarified later (under the "Two caveats" header). The point is that you can get an arbitrarily close approximation of any continuous function, just by choosing a sufficiently large number of hidden units. That is, for any epsilon > 0, a neural network can approximate any function within epsilon of the function's exact value at all points, with enough hidden units. The smaller the epsilon, the better the approximation you want, and the more hidden units you need.

> I think skilled biological actors use this overfitting to get really good at things without knowing how things actually work.

Perhaps that's the mechanism behind intuition?

By function I think he meant mapping input points to output points in an abstract plane.

So in that sense a piece of music, or a sentence in one language is a point of input, while name of music or sentence in another language is another point.

Everything is a function as long as there is a way to turn that thing into inputs that correspond to outputs.

I would agree that the examples can be somewhat misleading, but not because of computability. Universal approximation theorem for neural networks doesn't care about computability, but it does require that the domain of the function is finite (or to be more precise, compact).

For example, suppose that the function to be approximated is simply f(x) = x. For any real numbers a < b we can produce an approximation that works well for a ≤ x ≤ b, but it cannot be a good approximation for all real numbers x. (The sigmoid in the hidden layer means that every approximation has to be a bounded function, and a bounded function cannot be a good global approximation of f(x) = x.)

Therefore, the translation example works if we assume that the number of different Chinese texts is finite, but otherwise nothing is guaranteed.

I don't think so, since the former is about the occurrence of sequences in stochastic, ergodic processes, and the latter is about approximating deterministic functions.

It's more like given an infinite number of parameters, you have enough degrees of freedom to describe the vector space a function lives in with some set of basis functions, and a neural net supplies that.

This is probably the best book about neural networks for beginners. It's full of intuitive explanations, not too heavy on math, and it has simple code examples.

The book is truly excellent. You need some knowledge of (partial) derivatives and matrices, but other than that it doesn't require any more sophisticated mathematics.

We used it to prepare a 10-day course on neuronal networks for high school students. For anyone interested (and capable of reading German), see https://github.com/iblech/mathematik-der-vorhersagen for some notes, Python code, and videos.

I believe you can see all the source code in your browser.

What would be an example of a practical task that needs to be modeled with such a function?

Also a single layer is not enough to approximate functions in higher dimensions.

You missed this paragraph, which occurs in the first 10% of the article.

The second caveat is that the class of functions which can be approximated in the way described are the continuous functions. If a function is discontinuous, i.e., makes sudden, sharp jumps, then it won't in general be possible to approximate using a neural net.

One of the caveats mentioned in the article is that the neural networks do not necessarily compute a given function precisely, but rather approximate it to an arbitrary accuracy. In the case of the Weierstrass function, this removes any weirdness. This is because, for any accuracy, you could approximate the Weierstrass function as a polynomial. Note that the polynomial example is only to show that the weirdness of the Weierstrass function is not relevant in this context. Approximating it as a polynomial is not necessarily a good approach to approximating it as a neural network.

Isn't it so that all continous functions can be approximated with sums of sine waves too?

That is also cool but without the AI connotations...