That was really cool! It seemed after the brilliant play in the middle the most probable moves for winning required Lee Sedol to make impossibly bad mistakes for a professional, which would be a prior that AlphaGo doesn't incorporate. I've heard the training data was mostly amateur games so perhaps the value/policy networks were overfit? Or maybe greedily picking the highest probability, common with tree search approaches, is just suboptimal?
Failure to generalize is not always caused by overfitting. Even if there is no overfitting, deep neural networks seem to learn a surprisingly discontinuous function. Consequently, in rare cases, they can misclassify things with great confidence. [0]
From the cited paper,
> [Experimental results] suggest that adversarial examples are somewhat universal and not just the results of overfitting to a particular model or to the specific selection of the training set.
Anyway, Monte Carlo Tree Search is bad at losing positions. In general, you want to delay the impending catastrophe as long as possible instead of making stupid moves that make your position worse and worse. However, MCTS uses random rollouts to the end of the game, which sometimes make it difficult to ascertain if the inevitable doom is near or far.
Also, MCTS converges very, very slowly and is likely to miss a unique, single winning continuation.
I think it is probably a combination of both AlphaGo's value network failing to realize the good position of Lee Sedol after his brilliant play, and the MCTS failing to spot the unique winning sequence for Lee, that caused it to make the mistake. But we should probably wait for official analysis from the Deepmind team to see what exactly went wrong.
I'm hoping someone creates adversarial formations for AlphaGo if Google ever releases their model :)
One thing I've been pondering is if many adversarial samples exist. The board is rather low dimensional (19 x 19) and discrete. While certainly a massive state space, one of the suggestions for why adversarial images work is that the real number line is incredibly dense.
For example our possible Go board space is 2^(log2(3) * 19^2) for Go but 2^(24 * 28^2) for greyscale [0, 1] normalized single precision float imagery for MNIST. Thats an exponentially bigger space (I think something like 1e910 times bigger!), and gets only larger if you train with double precision, have larger images, add multiple color channels, add more nonlinear layers, etc.
I think it's more that the value network includes moves which look plausible but won't concentrate around the answer to a forcing move as having >99% probability. A human has a heuristic: "I must play here else I lose" but AG assumes its opponent might play anywhere that the ANN calls reasonable.
If the value/policy model is predictive with a dataset containing only amateur games, but fails to generalize to unseen data with professional games, that seems like a case of overfitting to a dataset only containing amateur games. In this case the expected value network may be different for amateur games than professional games.
Sorry, I'm being a little academic. Overfitting is when the model fits to noise or error. Overfitting is not synonymous with "inability to generalize beyond the train and test distribution."
For all we know AlphaGo has perfectly fit amateur games, but professional games are on a whole different level
All depends on how you define your data sets I suppose. IGS games include some professional games which, if it is the case that AG is perfectly trained on the amateur mode, were smoothed away.
Again, the only way to tell if overfitting specifically (and not other factors that are more likely) is the issue is performance on a held out test set.
That's the only empirical way, yes. We can also just talk about what it would mean in theory, though. In this case, we'd say that AlphaGo is well trained to the training data set sampling distribution but that may be far from the actual world game distribution.
You are implying overfitting is the only reason a model ever performs poorly. That is not true. Just because a model does poorly does not mean overfitting must be the issue.
The value/policy model includes a few hundred thousand amateur games, and a few hundred million games of self-play. Once AlphaGo beat Fan Hui those would have been games of self-play versus the equivalent of a professional. So overfitting is probably not a problem. I think it's a basic incentive mismatch - MCTS algorithms tend to like close games, whereas humans will try crazy moves when losing to throw off their opponent.
