Why neural networks struggle with the Game of Life
bdtechtalks.com
bdtechtalks.com
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?
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
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.
I went to a more recent talk by Google and results they handpicked to show were impressive.
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?
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.
I've worked with autoencoder, convolutional and LSTM methods with text that appear to solve problems that they shouldn't be able to solve from
https://en.wikipedia.org/wiki/Variety_(cybernetics)#Law_of_r...
that is, they don't contain a correct structural representation of the problem space or they violate the laws of computer science.
For instance, a neural network might do a finite number of calculations to guess at a good next move and play a mean game of chess. This is an O(1) algorithm that can't possibly do things that would take an O(log N), O(N), O(N^2), ... algorithm to do it. (e.g. explore the game tree exhaustively and prove this is a winning move.) Put it in the context of a variable-runtime algorithm such as MCTS which can iterate over the network multiple times and it will crush a grandmaster.
Thus you run into the space of the halting problem, something that pretends to sort a list in O(N) time and gets away with it, ...
People in the field work with poorly defined problems, pick metrics ungrounded in practice, etc. In particular there is no requirement that the results of a neural network be 'correct' they just have to be better than some alternative.
If you have one of these things either working or almost-working you might get curious and try to set up some little experiment based on an intuition at the microscale (e.g. it's obvious how to hand-build the network, tasks the network couldn't possibly learn) and do experiments like this one where you can synthesize unlimited amounts of data...
... frequently you get lost at sea, suspect that the emperor has no clothes, wonder if you got the math wrong somewhere, might find your system performs worse the more training data you throw at it...
... thus these results don't close in a clear story, they don't get published.
For example, if we were presented a highly sophisticated repetitive pattern and were tasked to figure the underlying tesselation rules that generate it, we would enumerate rulesets that we know already and then try to find parameters for them with the assumption that those parameters are simple.
Again, my point is that to solve GoL, the ML model needs to be given two things: 1) a few rulesets to choose from; 2) an upper limit on complexity of ruleset parameters.
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?
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.
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.
BTW, NFL theorem proves that it itself is never terribly important. Learning algorithm, which uses NFL theorem for making decisions, are in the same position as any other learning algorithm.
Though for arbitrary theoretical problems it’s important.
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.)
[0]: https://blogs.nvidia.com/blog/2020/05/22/gamegan-research-pa...
How could the Greek and Roman engineers not discover and use steam machines? They were so close! The machines are so obvious!
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?"
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.
Vanilla neural networks can predict the next average move, which isn't necessarily the best move. If the model sees a lot of chess games, it will learn a lot of opening moves. But it'll get hopelessly lost within 13 moves.
What's needed is a formulation of self-play, i.e. to apply the AlphaZero / MuZero algorithm. With Game of Life, the game is: given the current board state, predict the next board state. You can have a simple rule like "start with 100 lives; every misprediction subtracts one life."
Since AlphaZero / MuZero plans with respect to a tree search, self-play should rapidly improve for Game of Life.
The crucial difference here is that you're training on a simulation, not examples. It's like the difference between walking around the real world vs seeing random photos of random places.
The alphazero algorithm is quite fun to implement, and somewhat understandable with a bit of effort: https://web.stanford.edu/~surag/posts/alphazero.html
Supervised learning is orders of magnitude more efficient and better understood than reinforcement learning.
Reinforcement learning is an algorithm that can help you find unknown solutions to interact in an optimal way with a system. To predict the next board state, you know the solution already. So, this is a supervised learning problem.
Consider the problem of face completion: https://scikit-learn.org/stable/auto_examples/miscellaneous/...
Given a set of faces, mask off random parts of the face, then try to fill in the holes.
Neural nets excel at that kind of task, because as you say, it's a supervised learning problem: you "know the solution" (the missing face) and you can penalize / reward the model so that it learns a correct face on average.
But game of life is nothing like that. Every board is a valid board. You can set the board to whatever values you want, and then say "Go!" and game of life will happily simulate it.
Therefore the neural network's goal isn't to learn the board state; it's to learn the rules, and to obey the rules. Hence, self-play seems like a reasonable formulation.
Without self-play, your learned network will always overfit or underfit different scenarios. E.g. even if it does well in general, a sparse board might throw it off. Or a board with a bunch of pieces in one corner. Or a board in a checkerboard pattern. But self-play will automatically handle all of these cases, because it's forced to learn the patterns over time.
Minesweeper is another example: it's possible to win every game using nothing but logic (disregarding tiebreakers), so therefore the solution is known. But I don't think it can be formulated as a supervised learning problem. There are too many board states, and the board states are related to each other via logic ("am I obeying the game state?") rather than atoms ("what does a human face look like?")
> How would you gather labels for every possible board state? It would require 768 factorial labels to represent every possibility.
You don't need to represent every possibility. Just a sufficiently large dataset and a neural network with a sufficient amount of prior and size. Note that e.g. video continuation networks already exist and deals with comparable data sizes.
> But game of life is nothing like that. Every board is a valid board.
Yes, but given the previous board (or the board N steps ago) there is only one valid board. Hence, a supervised learning problem.
> Without self-play, your learned network will always overfit or underfit different scenarios.
This confuses me. Why do you think self-play avoids over- and underfitting? How could one approach even solve both over- and underfitting at the same time?
> Minesweeper is another example: it's possible to win every game using nothing but logic (disregarding tiebreakers), so therefore the solution is known. But I don't think it can be formulated as a supervised learning problem.
Sure it can. If the solution is known, just train a neural network to mimic the solution. That's what network distillation is all about.
Game of life is not an adversarial game, there is no opponent, you can not apply self play to learn the rules.
Contrary to go or chess, StarCraft includes asymmetric matchups (three very, very distinct races, so in 1v1 - six possible matchups). Every matchup is played very differently; one trivial example: if you'd try to play a Protoss vs Zerg match like you'd play a Protoss vs Protoss, you're going to lose really, really badly within minutes: the standard PvP opener (wall-off at the main base) is going to leave your natural expansion completely defenceless against a trivial early attack (mass zerglings), which snowballs into a very, very bad economical disadvantage.
So basically when AlphaStar learns, it absolutely must be really good at handling these kinds of asymmetric scenarios (both players/actors having a vastly different arsenal at their disposal, starting from t=0), otherwise it would lose every single non-mirror matchup (while it's actually beating many grandmasters).
Another peculiarity of StarCraft is e.g. with Zerg, as the race that normally opts in to play the very early game a bit blindly (late scout with a slow Overlord vs an earlier worker scout), but must still make some strategic choices, the most common (and optimal) being greed, which occasionally means losing to aggression or missing a chance to punish a greedy opponent. Humans here kind of rely on intuition, metagame, etc.
My question is, can the capabilities to handle the asymmetry, and to play blindly, be exploited by re-modeling a class of problems, such that they become "StarCraft-like" enough? E.g. (naively) if the Game of Life board is not "correct enough" by iteration N, the opponent will flood your base with zerglings ;)
But, starting from a random position in weight space, gradient descent fails to find this optimum and requires a sensibly larger network to succed. Suggesting that the value of the initial weights is primordial (which is in line with the lottery ticket hypothesis)
The Game of Life is interesting to humans for the same reason it's hard for simple NN's to predict it. And it's for the same reason we find it hard to intuitively predict the output from GOF patterns withouts tons of exposure or by just running the rules through in our head like very inefficient computers.
An example of why I am not the one writing article headlines.
When the problem is stated this way, it seems more akin to to predicting the next word in a sentence based on the present word. Wouldn't an LSTM or perhaps a GPT-3 architecture be better suited?
As you can see by the stupidity of my question, I am an ML amateur and neophyte. To be completely naive, how would one approach the problem of designing an ML algorithm to 'learn a convolution kernel' For example, suppose I had a million image pairs generated with a 3x3 'blur' kernel {(.0625,.125,.0625),(.125,.25,.125),(.0625,.125,.0625)} what architecture would be best to feed this data into?
(Beautiful illustration of the “simple rules” that yield complex behaviors: https://www.wolframphysics.org/visual-summary/dark/)
Stephen Wolfram, along with many others (predating him):
An example. Note the dates. (A New Kind of Science is from 2002.)
http://csc.ucdavis.edu/~chaos/Publications/JPC-Publications....
Also see:
Chris Langton: https://en.wikipedia.org/wiki/Christopher_Langton
C. Langton, Studying articial life with cellular automata, Physica D 22 (1986) 120–149.
Complexity of Langton’s ant: https://arxiv.org/abs/nlin/0306022
I don't think this is the paper's "finding" at all. Sure, the Game of Life indicates that simple systems can result in complex, emergent behavior. But, exactly for being a simple set of rules, it is trivial to create a Game of Life implementation (or following this paper's definition, to solve the problem of predicting the nth next state, given the current state).
The findings are rather that neural networks, despite its universality and prediction power, have a hard time learning parameters that solve this trivial task using a minimal architecture, so they require a larger amount of parameters or a very good initial set of weights ("lottery ticket").
It's not about neural networks struggling with the game of life. It is much more subtle than that.
It's that the training algorithms are not able to reach the optimal network even if such network has already been found by hand.
But, it's also a great opportunity. The Game of Life is a simple enough algorithm that we can use it to fine tune NN training algorithms until they can start training with much better initial values for the weights.
I kinda think that's why LightOn is so interesting; they're trying to do neural networks by casting the matrix multiplies as doing optical stuff with photons (if I understand correctly, some kind of compressed sensing training method involving scattering randomized apertures for light).
I don't know much about their tech, but that seems like a paradigm shift compared to GPU cores.. they purport 3- Peta multiply-accumulate ops per second, at 30 watts. https://lighton.ai/our-technology/#1596017080086-e6716927-ba...
Would like to see the benchmarks though, their benchmarks repo doesn't just have it immediately all laid out
Let's say you train a bunch of ML models to solve a problem, these models are m_1, m_2,..., m_n and are ordered according to their performance on the tests/validation set where m_1 is the best model.
Should we expect to see regression to the mean on their predictions scores once we let them do their thing on fresh sets?
In practice, at least for CNN classifiers on ImageNet etc, it seems to be a pretty minor issue overall. Some links: https://arxiv.org/abs/1711.11561 https://arxiv.org/abs/1806.00451 https://arxiv.org/abs/1902.10811 http://gradientscience.org/data_rep_bias/ http://gradientscience.org/data_rep_bias.pdf https://arxiv.org/abs/1905.10498 https://arxiv.org/abs/2002.02559 https://arxiv.org/abs/2006.07159 https://arxiv.org/abs/1805.08974 https://arxiv.org/abs/1902.10178 https://arxiv.org/abs/1912.11370#google
If you do a train/eval/test data split instead, train+eval m_1 through m_n like before, and then rank them based on performance on the test data only after model selection is finished, you won't have that implicit overfitting to the test data, and m_n stands a better chance of beating m_1 on new datasets.
There's another way things can go wrong - if your train/eval/test data doesn't capture the full range of variability of the data source that will be producing your fresh datasets, then even if you do the train/eval/test split correctly, it's quite possible that m_n will do no better than m_1 when operating on fresh data outside of the train/eval/test distribution.
Basically, it is possible to build a sequence of models that actually improve performance on new data, but there are also lots of ways to get it wrong and produce models that look like they're doing better in a controlled environment, but fail to do better in the wild.
They used CNNs in this experiment to learn how far a NN could predict GoL into the future. It can't be done, for GoL is not finite.
E.g. would it be possible for some programmer at Tesla to accidentally find the initial state variables that converges to a fully functioning self-driving algorithm years in advance of the algorithm working through data acquisition?
Basically it's still an open question of exactly how and why the training process can get stuck. It's almost as if the network gets sufficiently strong ideas (Bayesian priors) it starts to discard new evidence (the error signal doesn't help). That's probably why a maximum entropy (random) state is useful to "bootstrap" those efficient subnetworks that then learn fast.
The rules? (i.e. how a cell behaves in the next round depending on its neighborhood)
The evolution of a specific initial setup? (i.e. towards which of the known solutions the network will converge, given its state)