5 ms·

Certainly a much shorter way to say this: if you have enough lines you can approximate any curve within a margin. This is what large neural networks are doing.

Certainly a much shorter way to say this: if you have enough lines you can approximate any curve within a margin. This is what large neural networks are doing. Another way to look at it: most neural nets are just a bunch of polynomials stitched together. You can see this from the popularity of the relu activation function. when the relu is negative, that poly is always zero in that area. When positive it's some poly multiplied by a const - another poly. For nets that use other activation fns, they try to be linear in the area of most active input. So again they approximate a const * a ploy.

dougabug 6y ago
ReLU networks are piecewise linear.
- RandyRanderson 6y ago
  Have a look at some published nn architectures - you'll typically see a few nonlinear units/transforms and a LOT of ReLU ones.
blackbear_ 6y ago
You are missing the point. The surprising thing about deep learning is that it can generalize to unseen data so well. Polynomial regression cannot.
- mamon 6y ago
  If there is a pattern in data, such as it fitting on a curve, and you approximate that curve, then that should generalize to unseen data. What's surprising about that? A single polynominal regression wouldn't be able to do it, because some curves cannot be expressed as a polynominal, but superposition of multiple polynominals is apparently good enough.
  - moultano 6y ago
    If that worked, people would use it, but it doesn't, so they don't.
  - blackbear_ 6y ago
    > then that should generalize to unseen data. It's not guaranteed at all. Overcomplicated models will "overfit" the training data and generalize very poorly. > some curves cannot be expressed as a polynominal You can approximate any (continuous and blah blah) curve arbitrarily well with Taylor expansions. In fact, polynomials are one of the the most common examples to demonstrate overfitting. See figure 2 on wikipedia (https://en.wikipedia.org/wiki/Overfitting https://en.wikipedia.org/wiki/Overfitting)
- mumblemumble 6y ago
  It doesn't necessarily seem that surprising to me. If I can be really hand-wavy about it -- A lot of deep neural networks achieve their nonlinearity in a very constrained way. They stack linear models on top of each other, and the nonlinearity comes from using a a relatively simple nonlinear function such as logistic or tanh to scale the models' outputs before feeding them into the next one. (Without that step, you'd just have a linear combination of linear functions, which would itself be linear.) That's a pretty constrained form of nonlinearity compared to polynomial regression, which tries to directly fit some high-order polynomial. I don't have anything like the math chops to prove it this, but I believe that means that the neural network is going to tend to favor a relatively smoother decision boundary, whereas polynomial regression is a naturally high variance sort of affair.
  - Darkharbourzz 6y ago
    No, it's not constrained at all. In fact, even single hidden layer networks with nearly arbitrary activation functions are universal approximators (Hornik et al. 1989). Polynomials are also universal approximators (Weierstrass).
    - mumblemumble 6y ago
      I'm not trying to say that neural networks are inherently constrained. I'm saying that, in typical usage, they tend to be used a certain way that I believe introduces some useful constraints. You can use a single hidden layer and an arbitrary activation functions, but, in practice, it's a heck of a lot more common to use multiple hidden layers and tanh. It's worth noting that neural networks didn't take off with Hornik et al. style simple-topology-complex-activation-function universal approximators. They took off a decade or so later, with LeCun-style complex-topology-simple-activation-function networks. That arguably suggests that the paper is of more theoretical than practical interest. It's also worth noting that one of the practical challenges with a single hidden layer and a complex activation function is that it's susceptible to variance. Just like polynomial regression.
      - bonoboTP 6y ago
- lallysingh 6y ago
  How's that different from regular interpolation?
- tbenst 6y ago
  That's a strong unsubstantiated claim. On the other hand, there's been some nice theoretical work arguing that deep learning is a form of polynomial regression. https://arxiv.org/abs/1806.06850 https://arxiv.org/abs/1806.06850
  - moultano 6y ago
    Let us know when polynomial regression succeeds at any machine learning task. A lot of people publish results that say deep learning is "just" something else, where the something else doesn't work.
    - tbenst 6y ago
      How about 80% accuracy on CIFAR-10 with unsupervised training? => logistic regression + Kmeans http://ai.stanford.edu/~acoates/papers/coatesleeng_aistats_2011.pdf http://ai.stanford.edu/~acoates/papers/coatesleeng_aistats_2...
  - blackbear_ 6y ago
    They are both universal approximators. So are support vector machines, gaussian processes and gradient boosted trees. Yet the performance of neural networks is unrivaled in certain tasks, as has been proven over and over again. As a whole, that paper is quite bad (and still unpublished, probably blocked by peer review) because (1) it only considers fully connected networks (which are a minority of models used nowadays) and (2) the experimental validation was done on tasks where neural networks are not very strong. Show me examples of competitive polynomial regression models in language translation, image segmentation and Go playing and I will be convinced.
    - tbenst 6y ago
      To be fair, most of the machine learning literature had no or a poor excuse for peer review. And many deep learning layers can be described by dense layers. For example, convolution. You almost certainly can frame Go playing as polynomial regression but there would undoubtedly be numerical precision & other gradient issues. Deep learning is a practice is remarkably effective, no disagreement there.
ngrilly 6y ago
> if you have enough lines you can approximate any curve within a margin How avoid overfitting the training data?
- RandyRanderson 6y ago
  You're right - a LOT of work goes into this (eg GANs) because these large nNets just start "remembering" the training data.
nemoniac 6y ago
Perhaps you mean: "With four parameters I can fit an elephant, and with five I can make him wiggle his trunk."? https://en.wikiquote.org/wiki/John_von_Neumann https://en.wikiquote.org/wiki/John_von_Neumann
- pmiller2 6y ago
  Side note: You can fit an elephant with just 1 parameter. See https://twitter.com/exobenelson/status/1001473539789213697 https://twitter.com/exobenelson/status/1001473539789213697 and the paper linked therein.
jellyksong 6y ago
This article is about optimization (finding good parameters), not the approximation power of neural networks (which is well-known through the universal approximation theorem).
- RandyRanderson 6y ago
  I know. What we're both saying is: if you have enough lines, you can find the params easily.
dnautics 6y ago
> if you have enough lines you can approximate any curve within a margin. This is what large neural networks are doing. No, this is actually exactly the opposite of what the article is saying. "If you have enough lines you can approximate any curve within a margin" is usually a bad thing because your approximations lose meaning as the number of lines increase. The surprising thing about machine learning is that increasing the "number of lines", if you will, increases the meaning, too, and there's some wierd and subtle properties about mathematics in higher dimensions that makes this work.

dougabug 6y ago

ReLU networks are piecewise linear.

RandyRanderson 6y ago
Have a look at some published nn architectures - you'll typically see a few nonlinear units/transforms and a LOT of ReLU ones.

blackbear_ 6y ago

You are missing the point. The surprising thing about deep learning is that it can generalize to unseen data so well. Polynomial regression cannot.

mamon 6y ago
If there is a pattern in data, such as it fitting on a curve, and you approximate that curve, then that should generalize to unseen data. What's surprising about that? A single polynominal regression wouldn't be able to do it, because some curves cannot be expressed as a polynominal, but superposition of multiple polynominals is apparently good enough.
- moultano 6y ago
  If that worked, people would use it, but it doesn't, so they don't.
- blackbear_ 6y ago
  > then that should generalize to unseen data. It's not guaranteed at all. Overcomplicated models will "overfit" the training data and generalize very poorly. > some curves cannot be expressed as a polynominal You can approximate any (continuous and blah blah) curve arbitrarily well with Taylor expansions. In fact, polynomials are one of the the most common examples to demonstrate overfitting. See figure 2 on wikipedia (https://en.wikipedia.org/wiki/Overfitting https://en.wikipedia.org/wiki/Overfitting)
mumblemumble 6y ago
It doesn't necessarily seem that surprising to me. If I can be really hand-wavy about it -- A lot of deep neural networks achieve their nonlinearity in a very constrained way. They stack linear models on top of each other, and the nonlinearity comes from using a a relatively simple nonlinear function such as logistic or tanh to scale the models' outputs before feeding them into the next one. (Without that step, you'd just have a linear combination of linear functions, which would itself be linear.) That's a pretty constrained form of nonlinearity compared to polynomial regression, which tries to directly fit some high-order polynomial. I don't have anything like the math chops to prove it this, but I believe that means that the neural network is going to tend to favor a relatively smoother decision boundary, whereas polynomial regression is a naturally high variance sort of affair.
- Darkharbourzz 6y ago
  No, it's not constrained at all. In fact, even single hidden layer networks with nearly arbitrary activation functions are universal approximators (Hornik et al. 1989). Polynomials are also universal approximators (Weierstrass).
  - mumblemumble 6y ago
    I'm not trying to say that neural networks are inherently constrained. I'm saying that, in typical usage, they tend to be used a certain way that I believe introduces some useful constraints. You can use a single hidden layer and an arbitrary activation functions, but, in practice, it's a heck of a lot more common to use multiple hidden layers and tanh. It's worth noting that neural networks didn't take off with Hornik et al. style simple-topology-complex-activation-function universal approximators. They took off a decade or so later, with LeCun-style complex-topology-simple-activation-function networks. That arguably suggests that the paper is of more theoretical than practical interest. It's also worth noting that one of the practical challenges with a single hidden layer and a complex activation function is that it's susceptible to variance. Just like polynomial regression.
    - bonoboTP 6y ago
lallysingh 6y ago
How's that different from regular interpolation?
tbenst 6y ago
That's a strong unsubstantiated claim. On the other hand, there's been some nice theoretical work arguing that deep learning is a form of polynomial regression. https://arxiv.org/abs/1806.06850 https://arxiv.org/abs/1806.06850
- moultano 6y ago
  Let us know when polynomial regression succeeds at any machine learning task. A lot of people publish results that say deep learning is "just" something else, where the something else doesn't work.
  - tbenst 6y ago
    How about 80% accuracy on CIFAR-10 with unsupervised training? => logistic regression + Kmeans http://ai.stanford.edu/~acoates/papers/coatesleeng_aistats_2011.pdf http://ai.stanford.edu/~acoates/papers/coatesleeng_aistats_2...
- blackbear_ 6y ago
  They are both universal approximators. So are support vector machines, gaussian processes and gradient boosted trees. Yet the performance of neural networks is unrivaled in certain tasks, as has been proven over and over again. As a whole, that paper is quite bad (and still unpublished, probably blocked by peer review) because (1) it only considers fully connected networks (which are a minority of models used nowadays) and (2) the experimental validation was done on tasks where neural networks are not very strong. Show me examples of competitive polynomial regression models in language translation, image segmentation and Go playing and I will be convinced.
  - tbenst 6y ago
    To be fair, most of the machine learning literature had no or a poor excuse for peer review. And many deep learning layers can be described by dense layers. For example, convolution. You almost certainly can frame Go playing as polynomial regression but there would undoubtedly be numerical precision & other gradient issues. Deep learning is a practice is remarkably effective, no disagreement there.

ngrilly 6y ago

> if you have enough lines you can approximate any curve within a margin How avoid overfitting the training data?

RandyRanderson 6y ago
You're right - a LOT of work goes into this (eg GANs) because these large nNets just start "remembering" the training data.

nemoniac 6y ago

Perhaps you mean: "With four parameters I can fit an elephant, and with five I can make him wiggle his trunk."? https://en.wikiquote.org/wiki/John_von_Neumann https://en.wikiquote.org/wiki/John_von_Neumann

pmiller2 6y ago
Side note: You can fit an elephant with just 1 parameter. See https://twitter.com/exobenelson/status/1001473539789213697 https://twitter.com/exobenelson/status/1001473539789213697 and the paper linked therein.

jellyksong 6y ago

This article is about optimization (finding good parameters), not the approximation power of neural networks (which is well-known through the universal approximation theorem).

RandyRanderson 6y ago
I know. What we're both saying is: if you have enough lines, you can find the params easily.

dnautics 6y ago

> if you have enough lines you can approximate any curve within a margin. This is what large neural networks are doing. No, this is actually exactly the opposite of what the article is saying. "If you have enough lines you can approximate any curve within a margin" is usually a bad thing because your approximations lose meaning as the number of lines increase. The surprising thing about machine learning is that increasing the "number of lines", if you will, increases the meaning, too, and there's some wierd and subtle properties about mathematics in higher dimensions that makes this work.