Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A visual proof that neural nets can compute any function

neuralnetworksanddeeplearning.com

Post reply on HN
Print view View original

21–30 of 86 posts

Re: A visual proof that neural nets can compute any function

#21

Post by Dn_Ab »

akuma73 wrote: post #17
mooneater wrote: post #13

Who cares if they can compute any function. The important question is, can they learn any function, and can they learn in a way that can generalize? (And clearly they can for many useful domains).

What about XOR? From Wikipedia: In 1969 in a famous monograph entitled Perceptrons, Marvin Minsky and Seymour Papert showed that it was impossible for a single-layer perceptron network to learn an XOR function.

If you join a bunch of perceptrons together that limitation goes away. Another path is to make the problem effectively linear again by transforming into higher dimensions, kernels do this with one clever trick that allows them to avoid the computational cost of doing so explicitly.

Re: A visual proof that neural nets can compute any function

#22

Post by jbarrow »

akuma73 wrote: post #17
mooneater wrote: post #13

Who cares if they can compute any function. The important question is, can they learn any function, and can they learn in a way that can generalize? (And clearly they can for many useful domains).

What about XOR? From Wikipedia: In 1969 in a famous monograph entitled Perceptrons, Marvin Minsky and Seymour Papert showed that it was impossible for a single-layer perceptron network to learn an XOR function.

The simple answer is that we no longer use the standard linear perceptrons that McCulloch and Pitts put forth in 1943. The limitations of perceptrons and their training algorithms are well-known and well-studied, and in the last 60 years we've come a long way.

A book came out a little bit ago which covers basic neural networks, and culminates in showing a network that can estimate XOR [1]. I strongly recommend reading not only the chapter, but the whole book.

[1] http://natureofcode.com/book/chapter-10-neural-networks/

Re: A visual proof that neural nets can compute any function

#23

Post by dragonwriter »

akuma73 wrote: post #17
mooneater wrote: post #13

Who cares if they can compute any function. The important question is, can they learn any function, and can they learn in a way that can generalize? (And clearly they can for many useful domains).

What about XOR? From Wikipedia: In 1969 in a famous monograph entitled Perceptrons, Marvin Minsky and Seymour Papert showed that it was impossible for a single-layer perceptron network to learn an XOR function.

"Single-layer" is an important restriction there, however.

Re: A visual proof that neural nets can compute any function

#24

Post by Dn_Ab »

This is a wonderful post. One minor aspect which nags me is that when I read "any function", I think any "effectively calculable method". But regular feedforward MLPs are not Turing Complete (will you be going over recurrent or recursive networks?). If so, it would be useful to note this distinction as I've never seen that point for confusion dealt with properly in one place.

Re: A visual proof that neural nets can compute any function

#25

Post by mturmon »

pesenti wrote: post #16

Does anybody know if this is true for other machine learning techniques?

The same arguments as in the original Cybenko paper, or the Stone-Weierstrass theorem, lend support to the idea that SVMs are universal approximators (with most typical kernels). This has been proven by a couple of authors.

I'm not aware of universal approximation results for random forests, but since they have the same general construction, this would not be surprising.

Re: A visual proof that neural nets can compute any function

#26

Post by maaku »

voidlogic wrote: post #7
tomp wrote: post #4

As mentioned in the article, the formal statement is actually "neural nets can approximate (arbitrarily well, using the supremum metric) any continuous function". For other norms, it can also approximate non-continuous functions.

It would have been pretty interesting if this had NOT held. It would have meant that even though "neural nets can NOT approximate (arbitrarily well, using the supremum metric) any continuous function", a neural network (the humans involved) was able to discover this limitation. I find the idea of a neural net finding a limitation of a neural net, to be interesting.

A "neural net" is what a computer scientist decided to call something that he thought behaved somewhat like a now dated abstract model of what individual neurons worked like, from a period when neuroscience was really in its infancy.

Your brain is not a neural net.

Re: A visual proof that neural nets can compute any function

#27

Post by rcfox »

mturmon wrote: post #15
tomp wrote: post #4

As mentioned in the article, the formal statement is actually "neural nets can approximate (arbitrarily well, using the supremum metric) any continuous function". For other norms, it can also approximate non-continuous functions.

You also need the qualifier "...any continuous function, on a compact set. " Once you add all three qualifiers in (approximate/continuous/compact) it starts to sound more like math and less like a miracle. Incidentally, one thing of great interest is, how does the number of hidden units required behave as a function of dimensionality of the input domain. In dramatic language, "Can neural networks get around the curse…

> how does the number of hidden units required behave as a function of dimensionality of the input domain

If I recall correctly, a non-linear problem can be solved as a linear problem if you consider more dimensions. The hidden layer add dimensions. So, it's not a function of the input domain but of the problem domain, which usually isn't explicitly known.

Re: A visual proof that neural nets can compute any function

#29

Post by sz4kerto »

Feedforward NN's are only useful to a very narrow* set of problems (*-> compared to 'all' problems out there).

Recurrent networks are needed for stateful operation, i.e. where some kind of memory is needed (in any case where the input is spread across some time or the sequence of data is important). And learning in recurrent nets is in very early stages unfortunately.

Re: A visual proof that neural nets can compute any function

#30

Post by lucio »

mikeash wrote: post #5

I liked this article a lot, but I found it extremely confusing how some of the diagrams were interactive and some weren't. Why not make them all interactive? Barring that, an obvious visual indicator when one is interactive would be handy. As it was, I clicked on a lot of static images.

https://www.youtube.com/watch?v=KpUNA2nutbk
Post reply on HN