10 ms·
A visual proof that neural nets can compute any function
- deleted 12y ago[deleted]
- deleted 12y ago[deleted]
- tomp 12y agoAs 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.
- voidlogic 12y agoIt 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.
- gphil 12y agoMore generally, logic can be used to demonstrate the limitations of logic: https://en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_theorems https://en.wikipedia.org/wiki/G%C3%B6del's_incompleteness_th... You could say that a neural network found this limitation of neural networks, to the extent that neural networks could be defined in terms mathematical logic. However, it's not guaranteed that the neural networks in our brain could be explained in these terms--the physical processes underlying them are not fully understood.
- voidlogic 12y ago>More generally, logic can be used to demonstrate the limitations of logic This is of course true, but nevertheless it is an interesting result (hence why we study Gödel's incompleteness theorem).
- mjw 12y agoHumans are not neural networks in the formal sense used here, not even close.
- voidlogic 12y agoYou should explain in concrete terms why that is the case. I think its apparent that the human brain is a much more complex and advanced neural network (Intel 4004 vs Intel i7 perhaps?), but to say it is not is interesting and I would like to hear why.
- arjie 12y agoBecause the neural network described there is just an abstraction that has mathematical and (with some modification) practical utility. Real neurons do not behave in the way the model behaves. Synapses have plasticity, not just neurons. I'm not sure if synaptic efficacy (i.e. how much pre-synaptic input influences output) is fully understood even now. To put it simply, it is possible for ANNs to fail at something and for us to succeed at the same thing.
- mtdewcmu 12y agoRight-- in the musculoskeletal system there are mechanisms that operate approximately like pulleys; so I think you can say "a person is a neural net" in exactly the same sense as you can say "a person is a pulley." Neural nets are models of systems that we see in the human body that have been simplified and adapted such that they can be used as tools. It's not clear what lessons about humans can be drawn from studying NNs.
- mjw 12y agoPerhaps "not even close" was a bit strong, but I'm talking about a neural net as a specific mathematical model here. To say that the brain "is" an instance of a particular mathematical model isn't even really meaningful. At best you could try to argue that the brain is "modelled well by <formalism> for <purpose>", although I think you'd lose that argument for all but the weakest of purposes. I'm not a neurobiologist (if you are please correct/clarify!), but here are just a few of doubtless many significant differences as I understand them: * Real neurons don't update in a bunch of coordinated discrete timesteps, as an ANN learning algorithm does. They can fire independently and in continuous time. * Real neurons' activation behaviour is closer to sudden delta-function-like spikes, rather than a smooth activation function or something which allows them to stay in a firing state for longer than a short pulse. * The structure of the connection graph of neurons in the brain is incredibly more complex than that of artificial neural net models, can change over time, isn't split into obvious layers from input to output, there isn't a clearly-identifiable error signal which is used to train it at the outputs, ... * A real neuron is an incredibly complex biological system whose behaviour can be modulated in all sorts of ways and which I expect would take a nightmarishly complicated set of PDEs to model with any degree of realism even as an isolated unit. To think we've captured all aspects of their behaviour relevant to human cognition with a simple weighted sum and a sigmoid (say) seems pretty naive. Details aside though, the idea that you can start drawing deep philosophical conclusions about the nature of human thought, our ability to conceive of our own limitations etc, based on an analogy between a complex biological system and a simple mathematical formalism which is at best loosely influenced by certain limited aspects of it -- it's just silly, one of those "not even wrong" sort of statements.
- maaku 12y agoA "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.
- jo_ 12y agoCertainly 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?
- maaku 12y agoThe 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.
- Tenobrus 12y agoAre you saying there is literally nothing in the brain that can be abstracted away? This seems like a very bold claim.
- maaku 12y agoNo, absolutely not. I'm saying that a "neural net" a la McCulloch doesn't accurately model how computation is performed by the brain. You can't accurately model human thinking by recording the brain's connections as a classical neural net. That's all I'm saying.
- gphil 12y agoYep, my first thought upon seeing the title was: wait, what about non-computable functions?
- mturmon 12y agoYou 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 of dimensionality?" The Cybenko proof does not give enlightenment about that question. Andrew Barron (http://www.stat.yale.edu/~arb4/ http://www.stat.yale.edu/~arb4/) had some results that seemed to indicate the dependence was moderate (not exponential). I'm not aware what the state of the art currently is.
- rcfox 12y ago> 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.
- mturmon 12y agoThe 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 ...).
- mikeash 12y agoI 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.
- lucio 12y agohttps://www.youtube.com/watch?v=KpUNA2nutbk https://www.youtube.com/watch?v=KpUNA2nutbk
- deleted 12y ago[deleted]
- jokoon 12y agowho's to doubt neural networks are completely awesome ? Any more news about those chips that were optimized for neural networks ? Was it IBM or Samsung ?
- j2kun 12y agoWe have very few theoretical results about neural networks. So not completely awesome.
- jokoon 12y agoI mean there is a big future for neural networks
- j2kun 12y agoWell you asked a question and I answered it honestly :)
- jokoon 12y ago> So not completely awesome. I don't think I understand your point. By awesome I meant it's a very exciting/interesting field of research. I don't mean to call thermodynamics awesome because it powers cars or because it's a well research field. Trying to understand how the brain works or making a computer that works in a similar way is awesome to me. If there are still computational limitations that makes it not practical, that's still an awesomely interesting subject.
- jbarrow 12y agoIt was the IBM SyNAPSE Chip [1]. It's actually been known since 1988/89 that neural networks can approximate any continuous function [2], but this chapter explains how in a much more intuitive sense. [1] http://www.research.ibm.com/cognitive-computing/neurosynaptic-chips.shtml#fbid=m4f-fhy-N2- http://www.research.ibm.com/cognitive-computing/neurosynapti... [2] http://dl.acm.org/citation.cfm?id=70408 http://dl.acm.org/citation.cfm?id=70408
- mooneater 12y agoWho 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).
- mjw 12y agoQuite. 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.
- wall_words 12y agoThis 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."
- akuma73 12y agoWhat 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.
- pesenti 12y agohttp://en.wikipedia.org/wiki/Feedforward_neural_network#mediaviewer/File:XOR_perceptron_net.png http://en.wikipedia.org/wiki/Feedforward_neural_network#medi...
- Dn_Ab 12y agoIf 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.
- pesenti 12y agoDoes anybody know if this is true for other machine learning techniques?
- mturmon 12y agoThe 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.
- Dn_Ab 12y agoThis 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.
- sz4kerto 12y agoFeedforward 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.
- Houshalter 12y agoThey 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.
- bmease 12y agoI 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.
- numlocked 12y agoThis 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'.
- Tloewald 12y agoCan't the same be said for Fourier series, which make no claims to be some kind of AI? And likewise humble polynomials: http://en.wikipedia.org/wiki/Stone%E2%80%93Weierstrass_theorem http://en.wikipedia.org/wiki/Stone%E2%80%93Weierstrass_theor...
- mtdewcmu 12y agoYes (I am not expert in neural nets, but that appears to be exactly what this is saying). If you look at what goes into a neural net and compare it to what goes into a Fourier transform, it should be obvious that neural nets have even more than they actually need to do this task.
- j2kun 12y agoThis statement doesn't make sense to me. A neural network literally can't produce anything besides a continuous function, and the universality theorem says that there is no continuous function they can't (approximately) produce. So what could you possibly mean when you say neural networks have "more" than they need to do something which characterizes exactly what they can and can't do?
- mtdewcmu 12y agoThere are more coefficients than necessary. The FT has the minimum; it's bijective.
- signa11 12y agomay i also humbly suggest the two vol. series called "parallel distributed processing" (rumelhart et al) which provides an excellent overview of early NN research.
- mostly_harmless 12y agoI wrote about this a few weeks ago: http://serialprog.blogspot.ca/2014/07/neural-networks-like-custom-virtual.html http://serialprog.blogspot.ca/2014/07/neural-networks-like-c... My point of view was that neurons in neural nets are essentially analogue logic gates. Given that combinations of logic gates are Turing complete, combinations of neural net neurons should be also. My writing is not quite as nice or rigorous as the parent post, but the whole point of the blog is to get better at self-expression and explaining things.
- molixiaoge 12y agoget it
- coherentpony 12y agoComputing a function and approximating a function are two different disciplines. When approximating a function, one must also talk about the sense in which the approximation is being made. That is, L^2? H^1? Pointwise?
- mkoryak 12y agoFor me "visual proof" was a java program I wrote in 2005 that used genetic algorithms to evolve a neural network checker AI. It beat me every time: https://github.com/mkoryak/Evolutionary-Neural-Net-Checker-AI https://github.com/mkoryak/Evolutionary-Neural-Net-Checker-A...
- theophrastus 12y agoIf neural nets can compute any function (as seems neatly proven here) then can they compute any function in more than a single way? If so, then upon applying the novel input (which was our goal following training) how can we know that the particular way which was computed via training set is 'right' for our novel input? If this is all true then it would seem to make neural nets perfectly unreliable as a means to modeling..?