你好,游客 登录
背景:
阅读新闻

【一文读懂AlphaGo Zero算法】白话蒙特卡洛树搜索和ResNet

[日期:2017-10-26] 来源:新智元  作者: [字体: ]

【AI WORLD 2017世界人工智能大会倒计时14天】

致敬1024程序员节,庆祝新智元微信粉丝突破23万,大会限时8 折票抢购中!从现在开始,点击文末“阅读原文1024”,即可尊享大会全部论坛 8 折购票,活动截止至10月27日0点。

对AI来说,德州扑克是比围棋更难的游戏!世界人工智能大会邀请到战胜了人类德扑职业玩家的“冷扑大师”Libratus发明人CMU教授Tuomas Sandholm,带来题为《用于策略推理的超人AI》的精彩分享!

新智元专栏 

作者:邓侃

【新智元导读】AlphaGo Zero 令人惊艳。不过,有些评论似乎渲染过度,把它的算法说得神乎其神。大数医达创始人,CMU计算机学院暨机器人研究所博士邓侃在本文中,尝试用大白话,通俗地解释 AlphaGo Zero,弄清楚蒙特卡洛树搜索(Monte Carlo Tree Search,MCTS)、深度学习启发函数和置信上限这三大核心概念。

AlphaGo Zero 引起巨大社会轰动

只告诉机器围棋的基本规则,但是不告诉它人类摸索了上千年才总结出来的定式等围棋战术,让机器完全依靠自学,打败人类。这个题目不仅新鲜,而且热辣。

上周 DeepMind AlphaGo 人工智能围棋团队的一篇新论文,题目是“Mastering the Game of Go without Human Knowledge”。

这篇论文不仅被顶级学术期刊 Nature 发表,而且立刻被媒体反复报导,引起社会热议。

这篇论文让人惊艳的亮点有四,

  1. 只告诉机器围棋规则,但是不告诉它定式等等人类总结的围棋战术,也不让它读人类棋手比赛的棋谱,让机器完全自学成才。

  2. 机器完全靠自己摸索,自主总结出了定式等等围棋战术,而且还发现了人类上千年来没有发现的定式。

  3. 从零开始,机器自学了不到 40 天,就超越了前一版 AlphaGo(AlphaGo Master),而 AlphaGo Master 几个月前,曾以 60 : 0 的战绩,战胜了当今几乎所有人类围棋高手。

  4. AlphaGo Zero 的算法,比 AlphaGo Master 简练很多。

不过,有些关于AlphaGo Zero 的评论,似乎渲染过度,把它的算法,说得神乎其神。本文尝试用大白话,通俗地解释一下 AlphaGo Zero 的算法。

AlphaGo Zero 的算法,说来并不复杂。理解清楚 Monte Carlo Tree Search、深度学习启发函数和置信上限,这三个概念就行了。

Monte Carlo Tree Search:不穷举所有组合,找到最优或次优位置

围棋棋面总共有 19 * 19 = 361 个落子位置。假如电脑有足够的计算能力,理论上来说,我们可以穷举黑白双方所有可能的落子位置,找到最优落子策略。

但是,如果穷举黑白双方所有可能的落子位置,各种组合的总数,大约是 250^150 数量级。这个数太大了,以至于用当今世界最强大云计算系统,算几十年也算不完。

有没有不穷举所有组合,就能找到最优或者次优落子策略的算法呢?有,Monte Carlo Tree Search 就是这样一种算法。

刚刚开始教机器下围棋的时候,机器除了规则,对围棋一无所知。让两台机器对弈,分别执黑子与白子。只要不违反规则,以均等概率,在所有合法的位置上,随意选择一个地点落子。

黑方先行,它有 361 个合法投子位置。黑方先随机考虑一个候选位置,譬如天元(9,9)。开局是否投子在天元呢?取决于假如投子在此,是否有可能赢得胜利。如何估算赢得胜利的可能性呢?黑方模拟对局。

假如黑方第一手投子天元,那么白方的第二手会投子哪里呢?根据均等概率的初步策略,白方有 360 个合法位置,在任何一处投子的概率均等。假如白方的第二手投子在棋盘的最边缘(0,0)。

接下去,黑方在剩余的 359 个合法位置中,随机选择一个落子位置。接下去白方投子。如此重复,直到终局。

完成这样一次对局模拟的过程,上限是 361 手,计算成本很低。

假如黑白两个机器,以黑方投子天元开局,一路乱走,最终以黑方胜利。那么根据 Monto Carlo Tree Search 算法,投子天元的开局,有可能获胜,那么第一手,就真的投子天元。

假如一路乱走,最终黑方失败,那么黑方就换一个候选位置,再次模拟对局。假如第二次模拟对局以黑方获胜,就投子在第二个位置。假如失败,那就再换到第三个候选位置,第三次模拟对局。如此重复。

这样反复乱走,收集到了第一批棋谱,当然,这些棋谱的水平,惨不忍睹。

水平之所以惨不忍睹,是因为 “以均等概率,在所有合法的位置上,随意选择一个地点落子” 的下棋策略。

如何通过自学,不断改进下棋策略?

AlphaGo Zero 用深度学习神经网络来解决这个问题。

用深度学习网络实现启发函数

AlphaGo Zero 用 CNN 来改进围棋投子策略。具体到 CNN 的系统架构,AlphaGo Zero 用的是 Residual 架构 ResNet。而 Residual 架构是其时任职于微软亚洲研究院的中国人 Kaiming He、Xiangyu Zhang、Shaoqing Ren、Jian Sun,于 2015 年发明的。

ResNet 的输入是当前的棋面 S_{t} 。它的输出有两个,

  1. 当前棋面 S_{t} 的赢率,v( S_{t} ),赢率就是最终获胜的概率,是一个数值。

  2. 下一手投子的位置及其概率,P( a_{t+1} | S_{t} ),这是一个向量。投子的位置可能有多种,每个位置的概率不同,概率越高,说明在以往的棋谱中,经常投子在这个位置。

  3. 用先前收集到的棋谱,来训练 ResNet,拟合输入 S_{t},以及输出 P( a_{t+1} | S_{t} ) 向量和当前棋面的赢率 v( S_{t} )。

AlphaGo Zero 只用机器自我对弈的棋谱,来训练 ResNet。

当然,也可以用人类棋手的棋谱来训练 ResNet。理论上来说,用人类棋手的棋谱来训练 ResNet,AlphaGo Zero 的水平,会在更短时间内,获得更快提升。

但是,即便不用人类棋手的棋谱,只用机器自我对弈的棋谱,来训练 ResNet,在短短 40 天内,AlphaGo Zero 就已经超越人类棋手的水平。这个速度,实在让人惊艳。

ResNet 训练好了以后,仍然用 Monte Carlo Tree Search,继续让机器自我对弈。只不过把投子的策略,从均等概率的随机投子,改为根据 ResNet 的指导,来决定下一手的投子位置。

论文配图:MCTS 使用神经网络模拟落子选择的过程

具体策略如下,

  1. 根据当前棋面 S_{t},让 ResNet 估算下一手可能的投子位置,a_{t+1},及其概率 P( a_{t+1} | S_{t} )。

  2. 下一手的投子位置,a_{t+1} 有多种,每一种位置的赢率 v(S_{t+1}) ,和投子概率 P( a_{t+1} | S_{t} ) 不同。赢率和投子概率越高,得分越高。

  3. 赢率 v(S_{t+1}) 和 投子概率 P( a_{t+1} | S_{t} ) ,是对以往棋谱的总结。而置信上限(Upper Confidence Bound,UCB ),是来鼓励探索新的投子位置,越是以往很少投子的位置,UCB( a_{t+1} ) 得分越高。

  4. 综合考虑下一手的棋面的赢率 v( S_{t+1} ),投子概率 P( a_{t+1} | S_{t} ) ,和置信上限 UCB( a_{t+1} ),给下一手的各个投子位置打分。取其中得分最高者,来指导 Monto Carlo Tree Search,决定下一个投子的位置。

用改进了投子策略的 Monte Carlo Tree Search,继续让机器自我对弈,这样得到更多棋谱。然后,用这些棋谱,再次训练 ResNet,提高赢率和投子概率的估算精度。如此循环重复,不断提高 ResNet 的精度。

定式(Joseki)与投子位置热力图

投子概率 P( a_{t+1} | S_{t} ) ,反应了下一手投子位置的热力图。各个位置被投子的概率非常不均等,其中某些位置被投子的概率,比其它位置显著地高。

这些位置,加上前面几手的落子位置和相应的棋面,就是围棋定式(Joseki)。

论文补充材料:训练中AlphaGo Zero偏好的投子位置热力图

AlphaGo Zero 在五天以内,就通过机器自我对弈,总结出了常见的定式。

而人类发现这些定式,花费了几百年。

更加令人惊艳的是,AlphaGo Zero 还发现了新的定式,而这些定式,人类迄今为止并没有发现。

点击查看大图:在 2 小时时间限制下,AlphaGo Zero (20 个残差模块,训练 3 天) 对战 AlphaGo Lee 的 20 局,每局展示了前 100 步棋。

总结一下,AlphaGo Zero 的算法非常简洁,Monte Carlo Tree Search + ResNet。

与传统的 A* 算法比较一下,Monte Carlo Tree Search 只是 A* 算法中的树拓展的一种特例,而 ResNet 是 A* 算法中启发函数的一种特例。

将深度强化学习和蒙特卡洛树搜索用于智能医疗

除了下围棋,深度强化学习和蒙特卡洛树搜索已经用于智能医疗,给医生推荐最佳后续化验和检查项目,补充病情描述,用最小的代价,找到诊断金指标,提高诊断精度。

11月8日,新智元AI World 2017世界人工智能大会,邓侃博士将在 AI Industry 会场发表演讲《多模态智能疾病诊断系统的四大技术难点》,该系统把 CNN、RNN、Attention、GAN、RL、MCTR、Knowledge Graph 等多种前沿技术融为一体,构建医学智能诊断新体系。

邓侃 大数医达创始人

CMU计算机学院暨机器人研究所博士

邓侃,上海交通大学本科及硕士,美国卡内基梅隆大学(CMU)计算机学院暨机器人研究所博士,专攻人工智能及数据挖掘。历任美国甲骨文公司(Oracle)主任系统架构师,美国泰为手机导航公司(Telenav)北京分公司总经理,百度高级总监并主管网页搜索和知识图谱。2015年,邓侃创建北京大数医达科技有限公司,旨在将深度强化学习技术应用于医疗健康领域。

《多模态智能疾病诊断系统》演讲重点介绍该系统以下 4 个方面的技术难点:

  1. 把多模态数据,都转换成以医疗知识图谱为轴心的语义向量,在同一个参照系下进行相互比较和交叉操作。

  2. 在知识图谱为轴心的语义向量空间中,融合多模态数据,并使用生成对抗模型提供可行又可靠的质量评估方案。

  3. 用卷积神经网络技术,从病情描述中提炼病情特征,用聚焦机制,从医学知识图谱中补充相应病理逻辑,优化疾病的诊断与验证。

  4. 用深度强化学习和蒙特卡洛搜索树技术,给医生推荐最佳后续化验和检查项目,补充病情描述,用最小的代价,找到诊断金指标,提高诊断精度。

收藏 推荐 打印 | 录入:Cstor | 阅读:
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数
点评:
       
评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款