Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Lee Sedol Beats AlphaGo in Game 4

gogameguru.com

Post reply on HN
Print view View original

131–140 of 471 posts

Re: Lee Sedol Beats AlphaGo in Game 4

#131

Post by kotach »

argonaut wrote: post #130
kotach wrote: post #119

Earlier quoted context omitted.

They train using trajectories but train them to guess the trajectory locally, not globally. Discounted long-term rewards are just a hack, they aren't joint learning. The concept of label bias, or decision bias is a joint/structured learning concept. It is a machine learning concept, it has nothing to do with the application. There are training modes with mathematical guarantee that the local decisions will minimize t…

Yes, I'm pretty sure we're not talking about the same thing. I'm precisely talking about the trajectories not seen problem. Nothing is going to save you from the fact that the net has not seen a certain state before.

That's not really a problem. Given a large enough dataset you want to generalize from it - there are always states not present in the dataset - the whole point is now to extract features out of your dataset to allow generalization on unseen states. Seeing all of the Go games isn't possible.

The compounding errors problem that stems from decision bias isn't because you haven't seen the trajectory, it is because the model isn't trained jointly.

We're talking about the same thing. You just aren't familiar with the difference present between joint learning discriminative models and local decision classifiers (Markov entropy model vs conditional random fields - or recursive CNNs trained on joint loss over the sequence or recursive CNNs trained to minimize the loss of all local decisions).

In the case of Go, one would try to minimize the loss over the whole game of Go, or over the local decisions made during the game of Go. The latter will result in decision bias - that will lead to compounding errors. The joint learning has a guarantee that the compounding error has a globally sound bound. (proofs are information theory based and put mathematical guarantees on discriminative models applied to sequence labelling (or sequence decision making))

edit:

Checkout the lecture below, around the 16 minute mark it has a Super Mario example and describes exactly the problem you mentioned. The presenter is one of leading figures in joint learning.

https://www.cs.umd.edu/media/2015/12/video/17235-daume-stuff...

It is completely supervised learning problem. But, look at reinforcement learning as a process that has to have a step of generating a meaningful game from which a model can learn. After you have generated bazillion of meaningful games you can discard the reinforcement and just learn. You now try to get as close to the global "optimal" policy as you can, instead of trying to go from an idiot player to a master.

Of course, the data will have flaws if your intermediate model plays with a decision bias. So, instead of training the intermediate to have a bias, train it without :D

Re: Lee Sedol Beats AlphaGo in Game 4

#132

Post by apetresc »

versteegen wrote: post #107
apetresc wrote: post #32

Earlier quoted context omitted.

The thing is, Lee Sedol didn't "find the right moves"; the wedge at L11 shouldn't have worked. If black's 79th move had been at L10 instead of K10, Sedol would likely have resigned on the spot.

Ah! This matches up with Demis' tweet that black's 79th move was later determined to be a mistake. In MCTS you wouldn't normally go back to moves you've already played unless it's an incomplete information game. However I guess for reinforcement learning (even if it's not actually done during these matches), you would go back and update the estimated values of moves already played, which explains how they know that.

Demis clarified what he meant by that in a subsequent tweet – it wasn't that AlphaGo re-evaluated move 79, it's that the winrate only plummeted after move 87, which was beyond the point of no return: https://twitter.com/demishassabis/status/708934687926804482

Re: Lee Sedol Beats AlphaGo in Game 4

#133

Post by dasyatidprime »

argonaut wrote: post #51

If it's true that AlphaGo started making a series of bad moves after its mistake on move 79, this might tie into a classic problem with agents trained using reinforcement learning, which is that after making an initial mistake (whether by accident or due to noise, etc.), the agent gets taken into a state it's not familiar with, so it makes another mistake, digging an even deeper hole for itself - the mistakes then co…

Both are plausible for humans as well, I would say (in a more general sense). Certainly mistake spirals from not quite knowing how to deal with the consequences of the first mistake have happened to me personally, and I recall descriptions of people in poverty having to play more aggressively to get a shot at the part of civilization they want to be in, though unfortunately I don't have a source.

Re: Lee Sedol Beats AlphaGo in Game 4

#134

Post by thangalin »

yulunli wrote: post #101

AlphaGo obviously made mistakes in game 4 under the pressure from LSD's brilliant play. I'd like to know if the "dumb moves" are caused by the lack of pro data or some more fundamental flaws with the algorithm/methodology. AlphaGo was trained on millions of amateur games, but if Google/Deepmind builds a website where people (including prop players) can play with AlphaGo, it would be interesting to see who improves fa…

AlphaGo doesn't feel pressure.

http://i.imgur.com/ny3RhD4.png

My guess is that Sedol won because he introduced sufficient complexity through cutting points and numerous black groups (see the image). Since AlphaGo uses Value and Policy networks to determine the hot spots to analyse using Monte Carlo tree searches, by making a game rife with lots of simultaneous fights, Sedol dodged the one-two punch of Value and Policy networks combined with MCTS.

In other words, if Sedol can make over a dozen points of interest on the board, AlphaGo cannot deeply assess them all. In the image, there are at least 13 interesting moves and cuts plus up to 15 groups (depending if lone stones are considered groups by AlphaGo). I suspect that this position was far more complex than at any point during any of the three previous games.

It might also explain the meltdown of playing out an unfavourable ladder (the P10 group, as P8 is another possible move).

Re: Lee Sedol Beats AlphaGo in Game 4

#135

Post by jballanc »

wodenokoto wrote: post #127
jballanc wrote: post #56

So AlphaGo is just a bot after all... Toward the end AlphaGo was making moves that even I (as a double-digit kyu player) could recognize as really bad. However, one of the commentators made the observation that each time it did, the moves forced a highly-predictable move by Lee Sedol in response. From the point of view of a Go player, they were non-sensical because they only removed points from the board and didn't a…

I doubt its loss function tries to maximize the prediction of the opponents next move.

I doubt it's considering that directly. What I'm guessing (without having really studied the paper in depth) is that if you have two board positions which would score identically in the end, but where one has fewer remaining liberties than the other (i.e. one is deeper into the tree), then it will be scored more highly.

In other words, the humans commentating the game were evaluating the moves as non-sensical because the outcome (AlphaGo plays here so Lee plays here) is a foregone conclusion and doesn't change the human evaluation of the board position. What it does do is remove uncertainty (AlphaGo plays here, but Lee screws up and plays somewhere else). In their evaluation, humans tend to value that uncertainty (i.e. counting on the possibility of a mistake), but I'd guess that AlphaGo penalizes the uncertainty (i.e. known board positions are scored higher than potential board positions), leading it to over-value simple advancement of the board in the end-game.

Re: Lee Sedol Beats AlphaGo in Game 4

#136

Post by leereeves »

mikeyouse wrote: post #11

Relevant tweets from Demis; Lee Sedol is playing brilliantly! #AlphaGo thought it was doing well, but got confused on move 87. We are in trouble now... Mistake was on move 79, but #AlphaGo only came to that realisation on around move 87 When I say 'thought' and 'realisation' I just mean the output of #AlphaGo value net. It was around 70% at move 79 and then dived on move 87 Lee Sedol wins game 4!!! Congratulations! H…

Any chance of explaining the mistake on move 79 to someone who's only played a few casual games of Go?

Re: Lee Sedol Beats AlphaGo in Game 4

#139

Post by bsimpson »

techdragon wrote: post #83
Bytes wrote: post #8

I was not expecting Lee Sedol to come back and win a game after his first three losses. AlphaGo seemed to be struggling at the end of the match.

I was hoping Lee Sedol would be able to at least win one, humans can 'learn fast'. We cant learn 24/7 in parallel like a computer, but we do seem to have quite the talent at learning 'situational' things very quickly, quite likely because our very survival depended on it in the deep distant past. :-) I don't believe AlphaGo had the time to do any additional training between matches. So effectively Lee has the ability…

It's been said elsewhere that AlphaGo studying such a corpus of matches that even every match Lee ever recorded wouldn't be enough to bias it. I presume this also means that adding the last 3 games to that corpus would still not be enough to affect AlphaGo meaningfully.

Re: Lee Sedol Beats AlphaGo in Game 4

#140

Post by toolslive »

mikeyouse wrote: post #11

Relevant tweets from Demis; Lee Sedol is playing brilliantly! #AlphaGo thought it was doing well, but got confused on move 87. We are in trouble now... Mistake was on move 79, but #AlphaGo only came to that realisation on around move 87 When I say 'thought' and 'realisation' I just mean the output of #AlphaGo value net. It was around 70% at move 79 and then dived on move 87 Lee Sedol wins game 4!!! Congratulations! H…

"Do not anthropomorphise computers. They really hate that" (NN)
Post reply on HN