6 ms·

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 cle

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).

mjw 12y ago
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.
- wall_words 12y ago
  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."
akuma73 12y ago
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.
- pesenti 12y ago
  http://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 ago
  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.
  - JadeNB 12y ago
    > 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!)
    - gwern 12y ago
      Sorry, you were beaten to the joke a long time ago: http://www.oneweirdkerneltrick.com/ http://www.oneweirdkerneltrick.com/
- jbarrow 12y ago
  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/ http://natureofcode.com/book/chapter-10-neural-networks/
- dragonwriter 12y ago
  "Single-layer" is an important restriction there, however.
- JoeAltmaier 12y ago
  Neural nets now use non-linear functions so they can do things like xor.
- jo_ 12y ago
  '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.
  - szabba 12y ago
    I'm pretty sure linearity was also part of the picture -- no matter how many layers of neurons you have, as long as they perform linear combinations, they could all be replaced with a single one (ignoring numeric errors).
    - jo_ 12y ago
      I mentioned this in my post ("given nonlinear activations"), but you're correct to point out its importance. The combination of linear functions is always linear. Full stop. You need at least one non-linear layer to get reasonable results.
deleted 12y ago
[deleted]
skarayan 12y ago
It computes because it is detached, there is no feeling. To learn, we would need to first create something that is conscious, an ever-changing self. It needs to be in reference to itself, not some notion of compute in a detached paradigm.
- robrenaud 12y ago
  This is what is meant by "learn" in the context of machine learning. From wikipedia, http://en.wikipedia.org/wiki/Machine_learning http://en.wikipedia.org/wiki/Machine_learning > "A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E". This definition is notable for its defining machine learning in fundamentally operational rather than cognitive terms, thus following Alan Turing's proposal in Turing's paper "Computing Machinery and Intelligence" that the question "Can machines think?" be replaced with the question "Can machines do what we (as thinking entities) can do?" It's important, because we don't need to care about cognition or consciousness, and we can still write programs that solve problems well by making inferences from patterns in data.
wuliwong 12y ago
This is a chapter from a textbook, one that seems pretty introductory at that. I'd say it is a pretty important piece of information to convey and prove, this ability of neural networks to represent any function. Seems to me that jumping to whether they can "learn any function" as you asked, would certainly have come after this is first established.
Houshalter 12y ago
Sort of. It depends on the learning algorithm used. Typically some form of local optimization is used that gets it to a good local optima. This is usually good enough and fast. However you can use methods of global optimizations or whatever optimization algorithm you want to use. NNs themselves are sort of agnostic to the algorithm you use to set their weights. It's sort of like saying "computers are Turing complete, but can we ever prove that human programmers are smart enough to program any function."
mostly_harmless 12y ago
I think this ability to compute any function is important, and useful in understanding why neural nets work. Neural nets are essentially a blank computation matrix that, through training, best approximates a function. comparing neural net neurons to logic gates in a computer circuit or FPGA, gives a nice intuitive understanding of why the training works in the first place. The training essentially sets up a custom virtual circuit for whatever function you need. Given this property, it seems intuitive that they would be able to learn any function, since any function is representable as logic gates.
samizdatum 12y ago
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 flocked to bask in that alluring flame. The initial flurry of research activity slowed to a background simmer, however. As a steady march of implementation problems was knocked down, it became clear that the limitations of neural nets were inherent to neural nets themselves, rather than any particular implementation detail. For example, the Lagrangians calculated by SVMs are provably convex, in contrast to the lack of a convexity guarantee for neural nets, which happily gradient descent into local minima. There were workarounds, of course, with regularization techniques, stochastic descent, etc. providing some measure of relief, but a migration of research interest away from neural nets seemed increasingly promising, and today, the migration seems largely complete.
- wall_words 12y ago
  > 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 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.pdf 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: nonconvex 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.
sotte 12y ago
If you're interested in the generalization ability of neural networks I can recommend the following paper: "Intriguing properties of neural networks" http://arxiv.org/pdf/1312.6199v4.pdf http://arxiv.org/pdf/1312.6199v4.pdf TLDR: The authors create adversarial examples, i.e., they slightly modify the original images, which look exactly the same to humans but neural networks can't classify the images correctly anymore. What does that imply on the ability to generalize? :) On a more general note: NN are always treated as something magic. I think a "sober view" is that NN are a special way to parameterize non-liner functions. This is neither good nor bad but it's easy to see when you look at, for example, a 2 layer NN: $f(x) = w_2^T \sigma(W_1 \sigma (W_0 x))$
- pmelendez 12y ago
  >"which look exactly the same to humans but neural networks can't classify the images correctly anymore. What does that imply on the ability to generalize?" Usually that means that the model is experimenting overfitting, and that's actually one challenge on any machine learning model.

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).

mjw 12y ago

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.

wall_words 12y ago
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."

akuma73 12y ago

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.

pesenti 12y ago
http://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 ago
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.
- JadeNB 12y ago
  > 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!)
  - gwern 12y ago
    Sorry, you were beaten to the joke a long time ago: http://www.oneweirdkerneltrick.com/ http://www.oneweirdkerneltrick.com/
jbarrow 12y ago
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/ http://natureofcode.com/book/chapter-10-neural-networks/
dragonwriter 12y ago
"Single-layer" is an important restriction there, however.
JoeAltmaier 12y ago
Neural nets now use non-linear functions so they can do things like xor.
jo_ 12y ago
'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.
- szabba 12y ago
  I'm pretty sure linearity was also part of the picture -- no matter how many layers of neurons you have, as long as they perform linear combinations, they could all be replaced with a single one (ignoring numeric errors).
  - jo_ 12y ago
    I mentioned this in my post ("given nonlinear activations"), but you're correct to point out its importance. The combination of linear functions is always linear. Full stop. You need at least one non-linear layer to get reasonable results.

deleted 12y ago

[deleted]

skarayan 12y ago

It computes because it is detached, there is no feeling. To learn, we would need to first create something that is conscious, an ever-changing self. It needs to be in reference to itself, not some notion of compute in a detached paradigm.

robrenaud 12y ago
This is what is meant by "learn" in the context of machine learning. From wikipedia, http://en.wikipedia.org/wiki/Machine_learning http://en.wikipedia.org/wiki/Machine_learning > "A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E". This definition is notable for its defining machine learning in fundamentally operational rather than cognitive terms, thus following Alan Turing's proposal in Turing's paper "Computing Machinery and Intelligence" that the question "Can machines think?" be replaced with the question "Can machines do what we (as thinking entities) can do?" It's important, because we don't need to care about cognition or consciousness, and we can still write programs that solve problems well by making inferences from patterns in data.

wuliwong 12y ago

This is a chapter from a textbook, one that seems pretty introductory at that. I'd say it is a pretty important piece of information to convey and prove, this ability of neural networks to represent any function. Seems to me that jumping to whether they can "learn any function" as you asked, would certainly have come after this is first established.

Houshalter 12y ago

Sort of. It depends on the learning algorithm used. Typically some form of local optimization is used that gets it to a good local optima. This is usually good enough and fast. However you can use methods of global optimizations or whatever optimization algorithm you want to use. NNs themselves are sort of agnostic to the algorithm you use to set their weights. It's sort of like saying "computers are Turing complete, but can we ever prove that human programmers are smart enough to program any function."

mostly_harmless 12y ago

I think this ability to compute any function is important, and useful in understanding why neural nets work. Neural nets are essentially a blank computation matrix that, through training, best approximates a function. comparing neural net neurons to logic gates in a computer circuit or FPGA, gives a nice intuitive understanding of why the training works in the first place. The training essentially sets up a custom virtual circuit for whatever function you need. Given this property, it seems intuitive that they would be able to learn any function, since any function is representable as logic gates.

samizdatum 12y ago

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 flocked to bask in that alluring flame. The initial flurry of research activity slowed to a background simmer, however. As a steady march of implementation problems was knocked down, it became clear that the limitations of neural nets were inherent to neural nets themselves, rather than any particular implementation detail. For example, the Lagrangians calculated by SVMs are provably convex, in contrast to the lack of a convexity guarantee for neural nets, which happily gradient descent into local minima. There were workarounds, of course, with regularization techniques, stochastic descent, etc. providing some measure of relief, but a migration of research interest away from neural nets seemed increasingly promising, and today, the migration seems largely complete.

wall_words 12y ago
> 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 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.pdf 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: nonconvex 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.

sotte 12y ago

If you're interested in the generalization ability of neural networks I can recommend the following paper: "Intriguing properties of neural networks" http://arxiv.org/pdf/1312.6199v4.pdf http://arxiv.org/pdf/1312.6199v4.pdf TLDR: The authors create adversarial examples, i.e., they slightly modify the original images, which look exactly the same to humans but neural networks can't classify the images correctly anymore. What does that imply on the ability to generalize? :) On a more general note: NN are always treated as something magic. I think a "sober view" is that NN are a special way to parameterize non-liner functions. This is neither good nor bad but it's easy to see when you look at, for example, a 2 layer NN: $f(x) = w_2^T \sigma(W_1 \sigma (W_0 x))$

pmelendez 12y ago
>"which look exactly the same to humans but neural networks can't classify the images correctly anymore. What does that imply on the ability to generalize?" Usually that means that the model is experimenting overfitting, and that's actually one challenge on any machine learning model.