7 ms·

As someone who knows quite something on this topic, I do not really see what is the surprise here. Let's ignore the title (neural networks don't struggle, they

by 317070 6y ago

As someone who knows quite something on this topic, I do not really see what is the surprise here. Let's ignore the title (neural networks don't struggle, they just require a sufficiently large network) and go to the heart of the article, which is that neural networks need to be a lot larger than the most efficient solution to work. What did people expect? That you could use gradient descent to find the optimal solution from a random solution? It would have been very surprising to me if that were the case. The reason neural networks work, is because they have so many solutions which are relatively close in parameter space (due to the high dimensionality) such that they can find a local optimum which is decent for most data. To me, the surprising finding of the lottery ticket hypothesis was not that you can show that only a tiny part of the final network is necessary for the final solution, but that if you would have started with only that tiny part, you would retrieve almost the complete performance. I.e. that the initialisation is really important, perhaps more important than your architectural choices. The Game of Life article is merely confirming the finding from the lottery ticket hypothesis paper, but then applied on the Game of Life. I am surprised it picked up so much attention, maybe the Game of Life is a sexy topic to illustrate the issue?

chaboud 6y ago
I agree. I am utterly unsurprised that gradient descent was unable to optimize a “minimal” network to a complete solution of a binary state problem with a Boolean rule set. I’d have been shocked if it went any other way. I’m also reminded of an ‘06 paper by Kreinovich and Shpak, Aggregability is NP-Hard. http://www.cs.utep.edu/vladik/2006/tr06-29.pdf http://www.cs.utep.edu/vladik/2006/tr06-29.pdf Neural networks aren’t magic, and optimization isn’t finding the one needle in a haystack with a blindfold on. This is an intuitive result for anyone mildly conversant in the space. I don’t mind that they went out and did it, though.
- dnautics 6y ago
  Maybe I'm just not conversant enough in the field (I do ML "ops", not ML) but I'm surprised there aren't clever iterative ways of "reducing" the size of a model, for example, rank order the average activation of each parameter in a reducible group across the dataset, find the weakest, set it to zero, identify new misses, retrain with enrichment in the dead samples, reduce the hyperparameter by one.
  - TrainedMonkey 6y ago
    There are: https://medium.com/syncedreview/mit-google-propose-automl-for-model-compression-810be5b007d4 https://medium.com/syncedreview/mit-google-propose-automl-fo... I went to a more recent talk by Google and results they handpicked to show were impressive.
  - 317070 6y ago
    There are, it's called network pruning. You generally can reduce network size 90-95% without loss of accuracy with these methods.
    - ChrisRackauckas 6y ago
      You "just" have to train a huge network first, which is the downside.
cjauvin 6y ago
From a very high level perspective, I think what is somewhat surprising here is the fact that given that the Game of Life rules are quite simple, it should follow that a powerful generalization mechanism (which is what deep neural networks are often described to be) should be able to easily derive them.
- ajuc 6y ago
  The rules would need to be applied recursively for elegant generalization, I think? Do these networks have connections going backwards?
- watwatinthewat 6y ago
  It depends what you mean by "easy" here, but if you define that as "throw a big enough network at it, and it'll figure it out on its own in training", the research cited shows that is the case. The power you describe comes in part from network size (which is why NNs became more useful as we could size up as computing got more powerful/cheaper/more efficient). Small network means less powerful ability. The research showed smaller networks didn't work, but larger ones did. Seems like you'd agree?
  - horsawlarway 6y ago
    The research showed that small networks did work, but they took manual intervention during training. I think the whole point was that a small network is capable of solving this problem, but training from scratch without intervention only rarely produced a viable solution. From the article - But in most cases the trained neural network did not find the optimal solution, and the performance of the network decreased even further as the number of steps increased. The result of training the neural network was largely affected by the chosen set training examples as well as the initial parameters. So a solution was clearly possible even in the smaller networks when trained from scratch, it just wasn't likely. So I agree with your first point - The bigger networks did indeed "figure it out". But I don't agree at all with your second - The smaller networks weren't lacking the power to solve the problem, they were just unlikely to reach the right solution with the available training data.
- 6y ago
craftinator 6y ago
> To me, the surprising finding of the lottery ticket hypothesis was not only that you can show that only a tiny part of the final network is necessary for the final solution, but that if you would have started with only that tiny part, you would retrieve almost the complete performance. As a developer who's dabbled in a few machine learning fields, I've always wondered if there was a way to strip all unused/unlikely paths out of a network to reduce size and increase performance. I've struggled with finding solid information on this (and just the whole ML tooling ecosystem in general). From your experience, are there any tools out there that can aid in this kind of analysis and path stripping?
- blackbear_ 6y ago
  > wondered if there was a way to strip all unused/unlikely paths out of a network to reduce size and increase performance. Sure there is, it is called "pruning". You can easily find works on this with your favorite search engine. "Distillation" is another interesting technique to make models smaller. These techniques are applied after training, to reduce the size of a big network. I don't know any method that can be applied _before_ training, just by inspecting the network.
- harveywi 6y ago
  You may be looking for "Optimal Brain Damage": http://yann.lecun.com/exdb/publis/pdf/lecun-90b.pdf http://yann.lecun.com/exdb/publis/pdf/lecun-90b.pdf
dcolkitt 6y ago
Over the past ten years, neural networks have been extremely successful on a range of problems that prior seemed impossibly difficult. One downside to that though is that people have forgotten the No Free Lunch theorem, and now see neural networks as a silver bullet to use everywhere and always. NFL shows that no learning method works across the space of all possible problems. Every method bakes in a set of empirical priors. To the extent that the problem conforms to those priors, the method does well. But the contrast is that you must "pay the cost" by underperforming in other problems which contradict those priors. To be fair often times the areas that you underperform in are so pathological that they're hardly ever encountered in the real world. Many regression type problems rely on the empirical prior that arbitrarily close real numbers are more similar than random. For example you expect the answer at 2.84394 to be closer 2.84395 than 150,000. In actual physical reality, this prior tends to hold up so well that we're barely even aware when we rely on it. But when it does break (like trying to treat Hamming distances as real distances), it breaks spectacularly. There's no free lunch, but sometimes we can pay the bill with cheap currency. The point of all this, is that you shouldn't be picking learning methods without understanding the empirical priors embedded in your data. Just because a technique works really well on a hard problem, doesn't mean it works really well on all problems. Especially if they're two very different types of problems.
- deleted 6y ago
  [deleted]
- im3w1l 6y ago
  The no-free-lunch theorem is interesting in theory but not terribly relevant in practice. A prior that something can be efficiently approximated will learn anything you could desire to learn, and even stronger assumptions will work for most real world problems.
  - Retric 6y ago
    NFR is extremely important when you’re actually trying to solve specific problems. If the ideal solution involves some output randomness then neutral networks on their own are useless. Poker for example is a terrible fit.
jmull 6y ago
> As someone who knows quite something on this topic, I do not really see what is the surprise here. I'm not sure it was necessarily meant to be be surprising, especially to people experienced with neural networks. (In fact, it looks to me like the article is aimed at people who are curious but do not have a deep understanding.)
smusamashah 6y ago
Do you think GameGAN[0] will be able to pick the rules of game of life? [0]: https://blogs.nvidia.com/blog/2020/05/22/gamegan-research-pacman-anniversary/ https://blogs.nvidia.com/blog/2020/05/22/gamegan-research-pa...
Shorel 6y ago
Yeah, in retrospect everything is so obvious. /facepalm How could the Greek and Roman engineers not discover and use steam machines? They were so close! The machines are so obvious!
- thaumasiotes 6y ago
  You need a more specific question; they did discover and use steam machines. But you probably have a particular use in mind. And once you realize that, you can ask "would steam engines have been helpful to the Greeks in this context?"
- rini17 6y ago
  Their economy did not depend on deep mining and the need to pump water away from mines. This only happened over thousand years later.
auggierose 6y ago
I don't know much about it, but why is it surprising that if you initially put in the answer, you get a good answer out?
sollewitt 6y ago
So I only dabble, but what was surprising for me with GoL on a small grid was how the performance wasn't great even if I'd shown the network almost every possible state during training (omitting a test set). Nets do such amazing things with open ended recognition problems ("what is in this picture") that you sort of just expect them to trivially learn closed form solutions perfectly. I know this is a fallacy, but that is where the surprise came for me.
scoot_718 6y ago
My reading was they hand made a solution, called it optimal (no proof) and then were disappointed when the ANN didn't converge to their weights...

by 317070 6y ago

chaboud 6y ago

I agree. I am utterly unsurprised that gradient descent was unable to optimize a “minimal” network to a complete solution of a binary state problem with a Boolean rule set. I’d have been shocked if it went any other way. I’m also reminded of an ‘06 paper by Kreinovich and Shpak, Aggregability is NP-Hard. http://www.cs.utep.edu/vladik/2006/tr06-29.pdf http://www.cs.utep.edu/vladik/2006/tr06-29.pdf Neural networks aren’t magic, and optimization isn’t finding the one needle in a haystack with a blindfold on. This is an intuitive result for anyone mildly conversant in the space. I don’t mind that they went out and did it, though.

dnautics 6y ago
Maybe I'm just not conversant enough in the field (I do ML "ops", not ML) but I'm surprised there aren't clever iterative ways of "reducing" the size of a model, for example, rank order the average activation of each parameter in a reducible group across the dataset, find the weakest, set it to zero, identify new misses, retrain with enrichment in the dead samples, reduce the hyperparameter by one.
- TrainedMonkey 6y ago
  There are: https://medium.com/syncedreview/mit-google-propose-automl-for-model-compression-810be5b007d4 https://medium.com/syncedreview/mit-google-propose-automl-fo... I went to a more recent talk by Google and results they handpicked to show were impressive.
- 317070 6y ago
  There are, it's called network pruning. You generally can reduce network size 90-95% without loss of accuracy with these methods.
  - ChrisRackauckas 6y ago
    You "just" have to train a huge network first, which is the downside.

cjauvin 6y ago

From a very high level perspective, I think what is somewhat surprising here is the fact that given that the Game of Life rules are quite simple, it should follow that a powerful generalization mechanism (which is what deep neural networks are often described to be) should be able to easily derive them.

ajuc 6y ago
The rules would need to be applied recursively for elegant generalization, I think? Do these networks have connections going backwards?
watwatinthewat 6y ago
It depends what you mean by "easy" here, but if you define that as "throw a big enough network at it, and it'll figure it out on its own in training", the research cited shows that is the case. The power you describe comes in part from network size (which is why NNs became more useful as we could size up as computing got more powerful/cheaper/more efficient). Small network means less powerful ability. The research showed smaller networks didn't work, but larger ones did. Seems like you'd agree?
- horsawlarway 6y ago
  The research showed that small networks did work, but they took manual intervention during training. I think the whole point was that a small network is capable of solving this problem, but training from scratch without intervention only rarely produced a viable solution. From the article - But in most cases the trained neural network did not find the optimal solution, and the performance of the network decreased even further as the number of steps increased. The result of training the neural network was largely affected by the chosen set training examples as well as the initial parameters. So a solution was clearly possible even in the smaller networks when trained from scratch, it just wasn't likely. So I agree with your first point - The bigger networks did indeed "figure it out". But I don't agree at all with your second - The smaller networks weren't lacking the power to solve the problem, they were just unlikely to reach the right solution with the available training data.
6y ago

craftinator 6y ago

> To me, the surprising finding of the lottery ticket hypothesis was not only that you can show that only a tiny part of the final network is necessary for the final solution, but that if you would have started with only that tiny part, you would retrieve almost the complete performance. As a developer who's dabbled in a few machine learning fields, I've always wondered if there was a way to strip all unused/unlikely paths out of a network to reduce size and increase performance. I've struggled with finding solid information on this (and just the whole ML tooling ecosystem in general). From your experience, are there any tools out there that can aid in this kind of analysis and path stripping?

blackbear_ 6y ago
> wondered if there was a way to strip all unused/unlikely paths out of a network to reduce size and increase performance. Sure there is, it is called "pruning". You can easily find works on this with your favorite search engine. "Distillation" is another interesting technique to make models smaller. These techniques are applied after training, to reduce the size of a big network. I don't know any method that can be applied _before_ training, just by inspecting the network.
harveywi 6y ago
You may be looking for "Optimal Brain Damage": http://yann.lecun.com/exdb/publis/pdf/lecun-90b.pdf http://yann.lecun.com/exdb/publis/pdf/lecun-90b.pdf

dcolkitt 6y ago

Over the past ten years, neural networks have been extremely successful on a range of problems that prior seemed impossibly difficult. One downside to that though is that people have forgotten the No Free Lunch theorem, and now see neural networks as a silver bullet to use everywhere and always. NFL shows that no learning method works across the space of all possible problems. Every method bakes in a set of empirical priors. To the extent that the problem conforms to those priors, the method does well. But the contrast is that you must "pay the cost" by underperforming in other problems which contradict those priors. To be fair often times the areas that you underperform in are so pathological that they're hardly ever encountered in the real world. Many regression type problems rely on the empirical prior that arbitrarily close real numbers are more similar than random. For example you expect the answer at 2.84394 to be closer 2.84395 than 150,000. In actual physical reality, this prior tends to hold up so well that we're barely even aware when we rely on it. But when it does break (like trying to treat Hamming distances as real distances), it breaks spectacularly. There's no free lunch, but sometimes we can pay the bill with cheap currency. The point of all this, is that you shouldn't be picking learning methods without understanding the empirical priors embedded in your data. Just because a technique works really well on a hard problem, doesn't mean it works really well on all problems. Especially if they're two very different types of problems.

deleted 6y ago
[deleted]
im3w1l 6y ago
The no-free-lunch theorem is interesting in theory but not terribly relevant in practice. A prior that something can be efficiently approximated will learn anything you could desire to learn, and even stronger assumptions will work for most real world problems.
- Retric 6y ago
  NFR is extremely important when you’re actually trying to solve specific problems. If the ideal solution involves some output randomness then neutral networks on their own are useless. Poker for example is a terrible fit.

jmull 6y ago

> As someone who knows quite something on this topic, I do not really see what is the surprise here. I'm not sure it was necessarily meant to be be surprising, especially to people experienced with neural networks. (In fact, it looks to me like the article is aimed at people who are curious but do not have a deep understanding.)

smusamashah 6y ago

Do you think GameGAN[0] will be able to pick the rules of game of life? [0]: https://blogs.nvidia.com/blog/2020/05/22/gamegan-research-pacman-anniversary/ https://blogs.nvidia.com/blog/2020/05/22/gamegan-research-pa...

Shorel 6y ago

Yeah, in retrospect everything is so obvious. /facepalm How could the Greek and Roman engineers not discover and use steam machines? They were so close! The machines are so obvious!

thaumasiotes 6y ago
You need a more specific question; they did discover and use steam machines. But you probably have a particular use in mind. And once you realize that, you can ask "would steam engines have been helpful to the Greeks in this context?"
rini17 6y ago
Their economy did not depend on deep mining and the need to pump water away from mines. This only happened over thousand years later.

auggierose 6y ago

I don't know much about it, but why is it surprising that if you initially put in the answer, you get a good answer out?

sollewitt 6y ago

So I only dabble, but what was surprising for me with GoL on a small grid was how the performance wasn't great even if I'd shown the network almost every possible state during training (omitting a test set). Nets do such amazing things with open ended recognition problems ("what is in this picture") that you sort of just expect them to trivially learn closed form solutions perfectly. I know this is a fallacy, but that is where the surprise came for me.

scoot_718 6y ago

My reading was they hand made a solution, called it optimal (no proof) and then were disappointed when the ANN didn't converge to their weights...