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

61–70 of 86 posts

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

#61

Post by wall_words »

samizdatum wrote: post #59
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).

The biologically-inspired nature of neural nets was a steady, mesmerizing flame for machine learning research. A chance to work on an extremely simple, provably universal system that had embarrassingly obvious rhetorical implications for profound-sounding problems like the computability of consciousness, or the computational complexity of the human brain, proved too seductive for the legions of research-moths that fl…

> but a migration of research interest away from neural nets seemed increasingly promising, and today, the migration seems largely complete.

What are you talking about? Deep learning is one of the hottest areas of research today, and a lot of it has to do with neural networks. NN's are the state of the art in several domains. Case in point: http://image-net.org/challenges/LSVRC/2014/results. All of the top entries use convolutional networks; in fact, almost all of the entries do.

The fact that the loss function represented by a neural network can be highly nonconvex is what makes them so effective in the domains in which they are used. See this presentation by Yann LeCun for more info: http://www.cs.nyu.edu/~yann/talks/lecun-20071207-nonconvex.p...

"ML theory has essentially never moved beyond convex models, the same way control theory has not really moved beyond linear systems. Often, the price we pay for insisting on convexity is an unbearable increase in the size of the model, or the scaling properties of the optimization algorithm ... This is not by choice: non­convex models simply work better. Have you tried acoustic modeling in speech with a convex loss? ... To learn hierarchical representations (low-level features, mid- level representations, high-level concepts....), we need “deep architectures”. These inevitably lead to non-convex loss functions."

This isn't to say that NN's are going to solve all our problems, but to say that there has been a shift in interest away from NN's is absurd.

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

#62

Post by wall_words »

mjw wrote: post #19
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).

Quite. It's not hard to come up with models or families of functions which share this property. What matters is not only whether they can learn it but how much data they need to learn it to a given degree of accuracy. This is the kind of question addressed by nonparametric statistics and statistical learning theory.

This is an important statement and should be upvoted more. Case in point: "the Weierstrass approximation theorem states that every continuous function defined on a closed interval [a, b] can be uniformly approximated as closely as desired by a polynomial function."

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

#63

Post by mturmon »

mtdewcmu wrote: post #54
mturmon wrote: post #31

Earlier quoted context omitted.

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 domai…

I think I know the problem you're referring to (despite not having the right kind of specialist training to actually work in this field). I think that the fact that random or quasirandom probes are able to explore these high-dimensional spaces fairly effectively is evidence that the problem is somehow not exponential and therefore tractable in some fashion. Does that sound relevant?

Yes, your observation is relevant.

One has to be careful to separate the functional-approximation problem (which is in the OP) from the statistical-model-selection problem (which is NOT in the OP).

The statistical-model-selection problem is easier in some ways (you don't have to approximate the function everywhere, just where you get data; if you didn't get data somewhere, you don't care what happens there).

It is harder in some ways (all that probabilistic folderol, plus, your data is noisy).

There are results that give rates for the functional-approximation problem. By rates, I mean, how good is the approximation versus number of hidden units. The best work I know of is by Andrew Barron, but that was in the mid/late 1990s. He's like a genius bulldozer, so his papers are tough going. You'll note that the Cybenko results, like in the OP, do not give rates. This is obviously a huge difference.

There are also results in the statistical-model-selection problem, of course. With rates. That's Vladimir Vapnik's big contribution, later carried on by others. One of the main results is that a model class has an intrinsic complexity (VC dimension, or other measures) and you only need to have order-of that many random probes to get (close to) the best model in the class. No matter what the dimensionality of the space where the data lives.

This is precisely the point you're making above.

My comment is getting too long, but: notice that the statistical-model-selection work only speaks about how to get (close to) the best model in the model class. You then have to make sure your model class is full enough to get close to the optimal rule (which is chosen by Nature, or whatever).

So to make a full theory, you need both pieces: how to choose a big-enough model class (functional approx.) and how to select a good-enough member of the model class (statistical model selection).

Typically there is a total error having one term for each of the two effects, and therefore a balancing act between making the model class big enough to approximate anything, vs. making it small so that you can easily select a good model. If you look at it sideways, this therefore looks like an optimization problem with a Lagrange multiplier penalizing model complexity. So it's quite elegant.

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

#64

Post by seanmcdirmid »

wall_words wrote: post #61
samizdatum wrote: post #59

Earlier quoted context omitted.

The biologically-inspired nature of neural nets was a steady, mesmerizing flame for machine learning research. A chance to work on an extremely simple, provably universal system that had embarrassingly obvious rhetorical implications for profound-sounding problems like the computability of consciousness, or the computational complexity of the human brain, proved too seductive for the legions of research-moths that fl…

> but a migration of research interest away from neural nets seemed increasingly promising, and today, the migration seems largely complete. What are you talking about? Deep learning is one of the hottest areas of research today, and a lot of it has to do with neural networks. NN's are the state of the art in several domains. Case in point: http://image-net.org/challenges/LSVRC/2014/results . All of the top entries u…

Parent might be living in the recent past. There was a migration away from NNs in the 90s/early 00s, then Hinton and other people brought it back to life...with a vengeance :)

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

#67

Post by Tenobrus »

maaku wrote: post #40
jo_ wrote: post #35

Earlier quoted context omitted.

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.

Are you saying there is literally nothing in the brain that can be abstracted away? This seems like a very bold claim.

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

#68

Post by Houshalter »

sz4kerto wrote: post #29

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.

They are universal function approximators, which means they can map any set of input values to any set of output values. Of course to do this sometimes requires rote memorization of every possible input and it's output, rather than generalizing the function with a few parameters.

Adding more layers improves on this and allows you to make functions that compose multiple smaller functions. The problem with this is the nonlinearities cause the gradients to explode or vanish after a few layers. So the amount of computing power required to train them is huge.

Recurrent NNs had the same problem since they are equivalent to a very deep feed forward network; where every layer is a time step and the weights between every layer are the same.

But the invention of Long Short Term Memory has made training RNNs practical. Basically, as I understand it, some connections do not use nonlinearities so the gradients don't explode or vanish.

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

#69

Post by Houshalter »

mturmon wrote: post #60
mtdewcmu wrote: post #53

Earlier quoted context omitted.

>> Once you add all three qualifiers in (approximate/continuous/compact) it starts to sound more like math and less like a miracle. I agree. The problem with attempting to make subtle technical points digestible by untrained people is that the larger meaning of the exercise is likely to be lost along with the details. This would probably be a good demonstration to show to investors in your NN-based startup, because i…

Yep, it's funny how different people can have different reactions. The headline of the article said "any function", and so did the first sentence of the post ("any function at all"). Later on in the article, it's qualified, but tempers are already rising. Here come people with their non-computable functions, their unmeasurable functions, their nowhere-continuous functions, all wanting to get approximated. In sup norm…

It can learn any input to output mapping. What more do you want?
Post reply on HN