4 ms·

I'm confused by findings like this one, and I'm hoping someone here can educated me. There are many known universal approximations. Deep networks are one. SVMs

I'm confused by findings like this one, and I'm hoping someone here can educated me. There are many known universal approximations. Deep networks are one. SVMs are one. Heck, cubic splines are one, and they've been in use for nearly a hundred years IIRC. The problem has never been one of finding a sufficiently powerful approximator. It has been training that approximator. My understanding of the significant advancement made by deep learning is that we finally figured out how to train a specific kind of universal approximator in a way such that it finds very good separation surfaces for what used to be impossible-to-solve classification problems. But it should be no surprise to anyone that there exist, in theory, other universal approximations that approximately reproduce the same separation surfaces, should it? I'd expect any universal approximator to be powerful enough to reproduce the separation surfaces, hence the meaning of the word "universal". The problem was always finding the right weights, not finding the right approximator architecture. Am I missing something?

xksteven 6y ago
My understanding of the read was to show "how" they're equivalent as opposed to how to actually construct such an approximator or learn it. Similar to showing a problem falls in NP, you can reduce the problem down to another problem in NP and be done with it.
- sdenton4 6y ago
  Agree, but also think the result may be too general to be useful. Proving that you can rewrite any network learned with gradient descent this way kinda suggests that the architecture doesn't matter, but we know that's not true. Eg, why are networks with skip connections SO much better than networks without? What about batch normalization? This makes me suspicious that it's a nice theoretical result a bit too high level to be useful. Yes, it was proved years ago that you can train an arbitrary function with a wide enough two-layer net, but it's not a terribly practical way to approach the world. Now we have architectures much better than two-layer networks, and, for that matter, SVMs. There's a number of problems with svms; complexity for training and inference scales with the amount of training data, which is pretty sad panda for complex problems. Extremely spicy/cynical take: it's not cool to say "you all should go look at all these possible applications" when the thrust is the paper is to prop up the relevance of an obsolete approach. You gotta do the actual work to close the gap if you still want your PhD to be worth something... That said, I haven't read the paper terribly closely, and am always happy to be proven wrong!
  - mycall 6y ago
    > why are networks with skip connections SO much better than networks without? What are the leading theories for why this seems to be the case? Less nodes to capture and direct decisions?
    - sdenton4 6y ago
      Oh there's plenty of good explantation in the neural network literature (my eli5: the skip connections make the default mapping an identity instead of a zero mapping; you can start by doing no harm, and improve from there). The method was suggested by knowledge from differential equations. All I'm saying is that the "everything is secretly an svm" viewpoint is probably too coarse to explain these interesting and effective structural differences.
  - nightski 6y ago
    I'd be curious if re-framing a trained neural network model as a SVM gives you insight into it's support vectors and maybe a little understanding on why the NN works the way it does?
  - runT1ME 6y ago
    >suggests that the architecture doesn't matter, but we know that's not true. Eg, why are networks with skip connections SO much better than networks without? What about batch normalization? Is this true though, or does network architecture only matter in terms of efficiency? This is non rhetorical, I really don't know much about deep learning. :) I guess i'm asking if with enough data and compute, is architecture still relevant?
    - sdenton4 6y ago
      These things matter a lot in practice. Imagine a giant million dimensional loss surface, where each point is a set of weights for the model. Then the gradient is pushing us around on this surface, trying to find a 'minimum.' Current understanding (for a while, actually) is that you never really hit minima so much as giant mostly-flat regions where further improvement maybe takes a million years. The loss surfaces for models with skip connections seem to be much, much nicer. https://papers.nips.cc/paper/2018/file/a41b3bb3e6b050b6c9067c67f663b915-Paper.pdf https://papers.nips.cc/paper/2018/file/a41b3bb3e6b050b6c9067... In effect, there's a big gap between an existence proof and actually workable models, and the tricks of the trade do quite a lot to close the gap. (And there are almost certainly more tricks that we're still not aware of! I'm still amazed at how late in the game batch normalization was discovered.) OTOH, so long as you're using the basic tricks of the trade, IME architecture doesn't really matter much. Our recent kaggle competition for birdsong identification was a great example of this: pretty much everyone reported that the difference between five or so 'best practices' feature extraction architectures (various permutations of resnet/efficientnet) was negligible.
riku_iki 6y ago
> It has been training that approximator. Also it is representation of approximator itself and data compression. For cubic splines to approximate some NN you likely would need enormous number of intervals covering input space.
- VHRanger 6y ago
  Also, cubic splines don't extrapolate like the other mentioned models
make3 6y ago
An issue with deep learning is that it is very hard to analyse from a theoretical mathematical perspective, to prove things about them. Kernels have been studied thoroughly from a theoretical perspective and people have proven things about them. The goal of papers such as these is to find ways in which deep neural networks and kernel methods are similar, so that theoretical results and tools found for kernel methods may be adapted to deep neural networks.
sebasv_ 6y ago
Finding the right architecture, or more in general the right model, is very much still the main problem. You should be careful with the meaning you ascribe to the word 'universal'. The list of universal approximators is massive, and the sub-list of universal approximators that can be trained with OLS is still substantial. Still these models can differ significantly: - How efficient are they (in #parameters required for a certain error) for specific tasks? There is a known 'maximum efficiency' for general tasks, but in high dimensions this efficiency is terrible, such that many models will fail terribly on high-dimensional data. Hence, you should pick a model that is exceptionally good for a specific task, although it might be less efficient for other tasks. - How well can the model cope with noise? If your dependent variable is severely distorted (think financial data) then you need a model that can balance between interpolating datapoints and averaging out the noise. Just to name my two favorite properties. The first one is _kind of_ related to learnability, since an inefficient model is often pretty much impossible to learn.
talolard 6y ago
50/50 I can shed some light or am way over my head: The point of the paper is that if you train a deep learning model with gradient descent then the resulting model is effectively a kernel machine, regardless of model architecture. The nice thing about a kernel machine is that it is simple (just one hidden layer) and we are able to use to analyze a kernel machine more effectively and conveniently. So, I think the contribution here isn't "these sets of universal aproximators are equivalent" but rather "We have this effective but opauge deep learning thing, turns it it's actual a kernel machine in retropsect so we can bring 'kernel tooling' to analyze the deep learning mode"
- pbhjpbhj 6y ago
  Does that mean in theory we can uncover an underlying model, a theorem effectively, that the model is effectively approximating and so remove some of the uncertainty?
  - talolard 6y ago
    If I understand the paper (which is questionable), that's what the author is aiming for. E.g. he's saying 1) We can make these amazing black boxes 2) We don't really understand them 3) But when we make them with gradient descent they end up being almost kernel machines 4) We know a lot about kernel machines, so we can use that to "remove some uncertainty"
- nine_k 6y ago
  Does this essentially mean that any multi-layer RNN can be reasonably approximated by a 1-layer network (something like a perceptron) for the "playback" purposes, that is, for recognition / transformation, not learning? This may have colossal practical implications, as long as the approximation stays good enough.
  - dkural 6y ago
    Wouldn't this one-layer network be a lot less "compressive" than the multi-layer net, and in some sense "duplicate" subnetworks in earlier layers?
natn 6y ago
An even simpler universal approximator that the authors overlooked for some reason is just to use a very large hash map. There are some practical issues around generalization and storage but it has very predictable precision.
- osipov 6y ago
  > There are some practical issues around generalization and storage but it has very predictable precision. That's the kind of thinking that will get you into academia and will keep you there! Keep it up sport! Don't forget to mention that exploring these issues is future work.

xksteven 6y ago

My understanding of the read was to show "how" they're equivalent as opposed to how to actually construct such an approximator or learn it. Similar to showing a problem falls in NP, you can reduce the problem down to another problem in NP and be done with it.

sdenton4 6y ago
Agree, but also think the result may be too general to be useful. Proving that you can rewrite any network learned with gradient descent this way kinda suggests that the architecture doesn't matter, but we know that's not true. Eg, why are networks with skip connections SO much better than networks without? What about batch normalization? This makes me suspicious that it's a nice theoretical result a bit too high level to be useful. Yes, it was proved years ago that you can train an arbitrary function with a wide enough two-layer net, but it's not a terribly practical way to approach the world. Now we have architectures much better than two-layer networks, and, for that matter, SVMs. There's a number of problems with svms; complexity for training and inference scales with the amount of training data, which is pretty sad panda for complex problems. Extremely spicy/cynical take: it's not cool to say "you all should go look at all these possible applications" when the thrust is the paper is to prop up the relevance of an obsolete approach. You gotta do the actual work to close the gap if you still want your PhD to be worth something... That said, I haven't read the paper terribly closely, and am always happy to be proven wrong!
- mycall 6y ago
  > why are networks with skip connections SO much better than networks without? What are the leading theories for why this seems to be the case? Less nodes to capture and direct decisions?
  - sdenton4 6y ago
    Oh there's plenty of good explantation in the neural network literature (my eli5: the skip connections make the default mapping an identity instead of a zero mapping; you can start by doing no harm, and improve from there). The method was suggested by knowledge from differential equations. All I'm saying is that the "everything is secretly an svm" viewpoint is probably too coarse to explain these interesting and effective structural differences.
- nightski 6y ago
  I'd be curious if re-framing a trained neural network model as a SVM gives you insight into it's support vectors and maybe a little understanding on why the NN works the way it does?
- runT1ME 6y ago
  >suggests that the architecture doesn't matter, but we know that's not true. Eg, why are networks with skip connections SO much better than networks without? What about batch normalization? Is this true though, or does network architecture only matter in terms of efficiency? This is non rhetorical, I really don't know much about deep learning. :) I guess i'm asking if with enough data and compute, is architecture still relevant?
  - sdenton4 6y ago
    These things matter a lot in practice. Imagine a giant million dimensional loss surface, where each point is a set of weights for the model. Then the gradient is pushing us around on this surface, trying to find a 'minimum.' Current understanding (for a while, actually) is that you never really hit minima so much as giant mostly-flat regions where further improvement maybe takes a million years. The loss surfaces for models with skip connections seem to be much, much nicer. https://papers.nips.cc/paper/2018/file/a41b3bb3e6b050b6c9067c67f663b915-Paper.pdf https://papers.nips.cc/paper/2018/file/a41b3bb3e6b050b6c9067... In effect, there's a big gap between an existence proof and actually workable models, and the tricks of the trade do quite a lot to close the gap. (And there are almost certainly more tricks that we're still not aware of! I'm still amazed at how late in the game batch normalization was discovered.) OTOH, so long as you're using the basic tricks of the trade, IME architecture doesn't really matter much. Our recent kaggle competition for birdsong identification was a great example of this: pretty much everyone reported that the difference between five or so 'best practices' feature extraction architectures (various permutations of resnet/efficientnet) was negligible.

riku_iki 6y ago

> It has been training that approximator. Also it is representation of approximator itself and data compression. For cubic splines to approximate some NN you likely would need enormous number of intervals covering input space.

VHRanger 6y ago
Also, cubic splines don't extrapolate like the other mentioned models

make3 6y ago

An issue with deep learning is that it is very hard to analyse from a theoretical mathematical perspective, to prove things about them. Kernels have been studied thoroughly from a theoretical perspective and people have proven things about them. The goal of papers such as these is to find ways in which deep neural networks and kernel methods are similar, so that theoretical results and tools found for kernel methods may be adapted to deep neural networks.

sebasv_ 6y ago

Finding the right architecture, or more in general the right model, is very much still the main problem. You should be careful with the meaning you ascribe to the word 'universal'. The list of universal approximators is massive, and the sub-list of universal approximators that can be trained with OLS is still substantial. Still these models can differ significantly: - How efficient are they (in #parameters required for a certain error) for specific tasks? There is a known 'maximum efficiency' for general tasks, but in high dimensions this efficiency is terrible, such that many models will fail terribly on high-dimensional data. Hence, you should pick a model that is exceptionally good for a specific task, although it might be less efficient for other tasks. - How well can the model cope with noise? If your dependent variable is severely distorted (think financial data) then you need a model that can balance between interpolating datapoints and averaging out the noise. Just to name my two favorite properties. The first one is _kind of_ related to learnability, since an inefficient model is often pretty much impossible to learn.

talolard 6y ago

50/50 I can shed some light or am way over my head: The point of the paper is that if you train a deep learning model with gradient descent then the resulting model is effectively a kernel machine, regardless of model architecture. The nice thing about a kernel machine is that it is simple (just one hidden layer) and we are able to use to analyze a kernel machine more effectively and conveniently. So, I think the contribution here isn't "these sets of universal aproximators are equivalent" but rather "We have this effective but opauge deep learning thing, turns it it's actual a kernel machine in retropsect so we can bring 'kernel tooling' to analyze the deep learning mode"

pbhjpbhj 6y ago
Does that mean in theory we can uncover an underlying model, a theorem effectively, that the model is effectively approximating and so remove some of the uncertainty?
- talolard 6y ago
  If I understand the paper (which is questionable), that's what the author is aiming for. E.g. he's saying 1) We can make these amazing black boxes 2) We don't really understand them 3) But when we make them with gradient descent they end up being almost kernel machines 4) We know a lot about kernel machines, so we can use that to "remove some uncertainty"
nine_k 6y ago
Does this essentially mean that any multi-layer RNN can be reasonably approximated by a 1-layer network (something like a perceptron) for the "playback" purposes, that is, for recognition / transformation, not learning? This may have colossal practical implications, as long as the approximation stays good enough.
- dkural 6y ago
  Wouldn't this one-layer network be a lot less "compressive" than the multi-layer net, and in some sense "duplicate" subnetworks in earlier layers?

natn 6y ago

An even simpler universal approximator that the authors overlooked for some reason is just to use a very large hash map. There are some practical issues around generalization and storage but it has very predictable precision.

osipov 6y ago
> There are some practical issues around generalization and storage but it has very predictable precision. That's the kind of thinking that will get you into academia and will keep you there! Keep it up sport! Don't forget to mention that exploring these issues is future work.