北京大学生物信息平台论坛

 找回密码
 立即注册
搜索
热搜: 通知 活动

AlphaGo简明教程(冯建兴)

[复制链接]
licheng 发表于 2016-1-29 16:17:30 | 显示全部楼层 |阅读模式
AlphaGo简明教程
作者:冯建兴

Human-level concept learning through Bayesian program induction from a single example
文章链接:http://www.nature.com/nature/journal/v529/n7587/full/nature16961.html



最近Google的AlphaGo很火,我也不能免俗,走马观花的看了看。到底这个算法是怎么做的?下面我用一种尽量简单的语言来描述我对这个工作的看法。

下棋这个事儿说简单点就是你看到任何一个棋盘的布局,你知道下一步最好的步骤是怎么走的。就GO来说,每一步你有最多361种走法。用机器学习的语言来说,你要做的就是构建一个输入为棋盘布局,输出有361个的分类器。传统做法是用手工构建一些特征,然后用任何你想用的分类器即可。对应于文中的方法是“ linear softmax of small pattern features”。当然这个方法效果不咋地“accuracy of 24.2%”。当前流行的方法是CNN,这也很好理解,输入无外乎是19*19个点的黑白图像,输出就是一个361的softmax。只要训练样本够多,可以想到随便一个CNN都能比手工构建的特征构成的分类器好用。文章作者得到的准确性是“57.0%”。也许你会问,哪来的训练样本?很简单,找到历史上高手对战的棋局就好了,作者是从KGS Go Server上搞的。随便torch,theano,caffe啥的实现这样一个CNN那是小菜一碟。

有了这个CNN,虽然效果很好,不过对于圈内人来说,这也太简单了,不值一提。为了进一步提高效果,作者用到了reinforcement learning。这个玩意儿历史悠久,在这个paper里面的做法其实很简单,如下操作。从训练的比较好的网络(还有参数)里面,选两个,然后自相残杀。走了最多走361步以后,绝大多数情况都有一个会赢(否则是平局)。那么采用下面的公式更新网络参数:


其中z_t就是1或者-1,赢了就是1。那个p_{\rho}就是前面的CNN网络。通过这种方式“RL policy network won more than 80% of games against the SL policy network"。这一步实现也很简单,不停的模拟然后更新参数即可。

假设对于任何一个棋局,你都能估计出白方是否会获胜,那你就无敌了,为什么呢?因为无论你是白方黑方,你都可以选择会导致你获胜的走法。 当然,世界上还没有这么牛的人或者计算机。那怎么做呢?做法就是像个办法估计每个棋局的得分,对应于文中也就是定义一个value function。作者的做法就是用另外一个CNN来描述这个函数。这第二个CNN和前面CNN的结构除了输出不是一个概率分布以外其它完全一样。 那如何训练这个CNN呢?也很简单,因为对于每一个完整的棋局来说,你都知道最后谁输(-1)谁赢(1),那这个过程中的每一个棋局也都知道了它的得分。最后的结果是 MSEs能到0.226,很NB的。这个的效果和前面RL能实现效果相当,但是就算时间小的多(15,000 times less computation)

有了上面的CNN,RL还有value function,估计效果也还可以了。在实际对战的时候,还可以做得更好。做法很简单,每走一步的时候多看几步棋。然后根据前面的函数来给每一步棋打分,最后选择打分最高的那个策略即可。这样的一个坏处是可能陷入局部最优,所以就有了文中的MCTS(Monte Carlo tree search)。也就是在多看几步的时候每次是以一定的概率随机的选择(rollout)。具体有很多细节需要参见文章,多看两遍就知道怎么计算的。这部分我认为比前面的CNN,RL,value function都花时间。

如此看来算法本身不是那么遥不可及,那为什么是Google做了这个工作,并且影响这么大,而不是其它Reseach group?我想至少有如下几个原因

1. 人。这个DeepMind的来头可不小,在被Google收购之前由目前人工智能几个最大牛的弟子组成。

2. 勇气。Go这个东西研究了这么多年,大家都认为很难,有勇气投入这么多精力去做的地方不多。

3. 硬件。这个算法需要的硬件不算多,40个cpu,8个gpu。不过能分配这样的资源来一个Go项目上组估计不多。

4. 基础。DeepMind在之前有一个DL和RL结合的玩游戏的Nature paper。此外还有一个CNN下围棋的工作(在facebook之前)。这两个工作和AlphaGo直接相关。

5. 影响力。邀请到欧洲冠军下几局也不是一般人能做的

6. 工程。就像Google在最近NIPS的工作说的,机器学习算法只是整个系统很小一部分,外围的支撑代码占据了绝大多数的工作量。要高效的实现这个分布式系统并不容易。也没几个研究组能做得这么好。

7. 媒体。做过所有的算法、工程之后,google应该有很强的和媒体打交道的团队来包装。就这一点就秒杀很多大学的研究团队。

作者: feeldead@gmail.com
版本:2
欢迎转发
2016.01.30




IMG_20160129_162019.png

相关帖子

回复

使用道具 举报

北京大学生物信息平台论坛

GMT+8, 2017-9-20 06:34 , Processed in 0.102175 second(s), 30 queries .

Powered by Discuz! X3

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表