A visual proof that neural nets can compute any function • Hacker News Board

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

#31

Post by mturmon » Tue, Sep 02, 2014, 7:07 PM UTC

rcfox wrote: post #27

mturmon wrote: post #15

Earlier quoted context omitted.

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.

The question in the OP concerns approximation of the f(.) in:

  y = f(x)

where the input "x" is d-dimensional (say).

Some problems (i.e., choice of "f") could be easy. Maybe f only depends on one element of x, for example. There would be no curse of dimensionality in this case. Same situation if "f" depends only on any fixed number of elements of "x".

I think this is roughly what you mean by "dimension of problem domain." Fix an "f", that defines a problem. And you're right, efficient solution of that fixed problem is important!

My remark (which is also in the last paragraphs of the Cybenko reference cited in the OP) had to do with increasingly difficult problems.

How to get such a sequence of problems? Suppose you take a simple function like

  f(x) = exp(-0.5 * dot(x,x))

i.e., the Gaussian, and approximate it with a linear superposition of 1-d sigmoids (as a neural net would).

The question is, is there an explicit dependence on dimensionality, and is that dependence exponential in d?

And of course, for more general function classes (not just the single Gaussian function above), is there such a dependence? If it is not exponential, that would be astonishing, revolutionary.

The reason this setup ("vary the problem size") is interesting is that we would clearly like to use neural nets for increasingly higher-dimensional problems (e.g., learn appearance of 32x32 cats, then 64x64 cats, then ...).

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

#32

Post by jo_ » Tue, Sep 02, 2014, 7:21 PM UTC

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 easily overlooked and absolutely essential modifier. Very few networks these days are single layers. (Three is the minimum for infinite dimensional functional approximation, given nonlinear activations.) Deep Networks you see in new research papers these days have, at minimum, perhaps three layers. Some by LeCun et al. will go as high as nine or twelve layers, with four or sixteen layers in breadth.

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

#33

Post by jo_ » Tue, Sep 02, 2014, 7:26 PM UTC

rcfox wrote: post #27

mturmon wrote: post #15

Earlier quoted context omitted.

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.

You are correct. This is Cover's Theorem.

"A complex pattern-classification problem, cast in a high-dimensional space nonlinearly, is more likely to be linearly separable than in a low-dimensional space, provided that the space is not densely populated." - Cover, Geometrical and Statistical properties of systems of linear inequalities with applications in pattern recognition., 1965

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

#34

Post by bmease » Tue, Sep 02, 2014, 7:26 PM UTC

I loved reading that and interacting with the plots. It totally changes the dynamic of learning when you can interact and play with it in real time.

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

#35

Post by jo_ » Tue, Sep 02, 2014, 7:33 PM UTC

maaku wrote: post #26

voidlogic wrote: post #7

Earlier quoted context omitted.

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.

Certainly not in the deeper senses of the phrase.

If we take the phrase neural network to mean, "a series of deeply and widely interconnected elements which assist or inhibit the transmission of signals to one another, activated by the inputs exceeding a threshold," then I think there's a pretty good amount of overlap.

I understand there's a temporal signaling model (pulses at varying rates, not steady state signals) and stochastic information (like random firing and a bunch of noise), but once we abstract out the axons, dendrites, and neurochemicals, is there another piece of functional equipment which drastically effects things? How does our simplified view that small, individually stupid pieces, acting in concert to produce complex behavior differ from the real brain?

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

#36

Post by numlocked » Tue, Sep 02, 2014, 7:38 PM UTC

This is also why Neural Nets are susceptible to overfitting and fell out of vogue in the 90s :) They will merrily fit themselves, very precisely, to your noisy, wiggly data. Obviously there are ways to combat this, but it seems like an corollary to their 'universality'.

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

#37

Post by gohrt » Tue, Sep 02, 2014, 7:40 PM UTC

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…

> it starts to sound more like math and less like a miracle.

that applies to all of math. There are no miracles.

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

#38

Post by JadeNB » Tue, Sep 02, 2014, 7:42 PM UTC

Dn_Ab wrote: post #21

akuma73 wrote: post #17

Earlier quoted context omitted.

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.

> kernels do this with one clever trick that allows them to avoid the computational cost of doing so explicitly

Minsky and Papert hate him! Use this one weird trick ….

(Sorry; I couldn't resist!)

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

#39

Post by JadeNB » Tue, Sep 02, 2014, 7:48 PM UTC

gohrt wrote: post #37

mturmon wrote: post #15

Earlier quoted context omitted.

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…

> it starts to sound more like math and less like a miracle. that applies to all of math. There are no miracles.

> > it starts to sound more like math and less like a miracle.

> that applies to all of math. There are no miracles.

Err, what applies to all of math? That it sounds like math?

I do not agree that there are no miracles—plenty of mathematics is miraculous. As a first example off the top of my head, the areas of squares that can be drawn with vertices on the integer lattice in the plane are the integers whose prime factorisations include an even number of times each prime `p` for which `p + 1` is divisible by 4. This is a miraculous relationship between geometry and number theory, and it's just the tip of an iceberg!

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

#40

Post by maaku » Tue, Sep 02, 2014, 8:16 PM UTC

jo_ wrote: post #35

maaku wrote: post #26

Earlier quoted context omitted.

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.

Certainly not in the deeper senses of the phrase. If we take the phrase neural network to mean, "a series of deeply and widely interconnected elements which assist or inhibit the transmission of signals to one another, activated by the inputs exceeding a threshold," then I think there's a pretty good amount of overlap. I understand there's a temporal signaling model (pulses at varying rates, not steady state signals)…

The point is more that you can't abstract neurons away into a simple "analog in, digital out" pseudo-transistor with fixed connections and expect that to describe how the brain works. The brain makes active use of all those details you are abstracting away, in ways that would make your model's predictions differ from reality.