读论文、深入浅出解析 AlphaGo Zero 的技术和应用

1、 引子——‚左右互搏,天下无双

“这降龙十八掌掌法之妙,天下无双,一招已难抵挡,何况他以周伯通双手互搏,一人化二的奇法分进合击?”

——金庸《射雕英雄传》

10 月 18 日 Google DeepMind 在《Nature》发表了最新版本的 AlphaGo Zero 的论文。AlphaGo Zero 在进行了3天的自我训练后,在100局比赛中以100:0击败了上一版本的 AlphaGo ——而上一版本的 AlphaGo Lee 击败了曾 18 次获得围棋世界冠军的韩国九段棋 士李世乭。经过 40 天的自我训练后,AlphaGo Zero 变得更加强大,超越了Master版本的 AlphaGo——Master 曾击败世界上最优秀的棋士、世界第一的柯洁。

QQ20171109-111423@2x

2、 3 分钟看懂 AlphaGo 背后的基础知识点

2.1、 3 张图看懂监督学习、无监督学习、强化学习

机器学习可分类为监督学习、非监督学习、强化学习,如何简单理解?下面三 图以电视剧《人民的名义》为例,通俗介绍了监督学习(当前最火热、应用范围最 大)、非监督学习、强化学习分别是什么。

监督学习是当前使用最多的模型,需要有标注的数据录入模型,对模型训练(优 化模型的参数),训练的后的模型可以就进行推断了(即应用)。

QQ20171109-111531@2x

非监督学习强调不对数据进行任何标注(比如给你一堆图片,但是不告诉你他们分别代表什么),非监督模型可通过一定规则对给定数据进行聚类(Clustering)。

QQ20171109-111602@2x

强化学习包含四要素 Agent,环境状态,Action 行动,Rewards。Agent(机 器)通过一定行动(Action),最后会得到环境的 Rewards(奖励或惩罚),最后机器 会记住获得奖励的行动路径。

QQ20171109-111632@2x

2.2、 2 分钟理围棋类程序的重要算法——蒙特卡洛树搜索 MCTS

蒙特卡洛(Monte Calro)模拟是用大量随机样本解决数值的方法——采样越 多,越接近最优解。蒙特卡洛模拟通过大量随机样本解决数值问题,是一类方法的 统称,诞生于上个世纪 40 年代美国的”曼哈顿计划”,名字来源于赌城蒙特卡罗, 象征概率。简单的案例为计算圆周率π的概率:在一个 1×1 的正方形(内臵一个半 径 1/2 的圆)内撒点,如果点数足够大且均匀分布,那么圆的面积近似于圆中点数 /全部点数,由此可计算出圆周率π。

QQ20171109-111700@2x

蒙特卡洛树搜索(MCTS,Monte Calro Tree Search)指用随机抽样方法生 成决策树的方法,可用于围棋等游戏。决策树是通过树形图描述一系列决策的模型, 广泛用于数据分析。围棋等棋类游戏属于零和博弈(穷举法下最优结果可算出), 原则上可以建立一个足够庞大的博弈树分析走棋策略,通过将所有可能路径遍历 (由最后的节点向前遍历),可以得出各条路径的赢率。由于围棋等游戏的可能性 太多无法穷举遍历,因此人们采用蒙特卡洛模拟方法(随机抽样)与决策树结合。

蒙特卡洛树搜索(MCTS)包括四个步骤:选择(选择一个节点)、扩展(根据一 定规则,向下拓展至其他节点)、模拟(根据一定规则向下选择一条路径,而不是 遍历所有可能的路径)、反向传播(将数值从最后节点出发,自下向上更新决策相 关的参数)。

QQ20171109-111737@2x

蒙特卡洛树搜索(MCTS)在 AlphaGo 之前已被用于围棋软件。根据雷锋网 报道,在 AlphaGo 之前,MCTS 已被用于围棋对弈商业软件 Crazy Stone 和 Zen, 还有最大的开源软件 Pachi 和 Fuego,并取得了较好的成绩。

3、 AlphaGo Zero 为何是大突破——知易行难 3.1、 围棋竞技——知易行难,穷举算法不可行

围棋等棋类游戏的特点:规则明确且条目数较少、目标明确(结果最多只有赢、 输、平)、对阵方有限(几个,通常 2 个)、局面变化多、没有随机因素(不像扑克 牌有发牌的随机因素)。

QQ20171109-111909@2x

在策梅洛定理下,若暴力穷举算法可行,则两人对弈的棋类游戏过程很简单— —决定了谁先手、谁后手之后,游戏结束。策梅洛定理(1913):在二人的有限游 戏中,如果双方皆拥有完全的资讯,并且运气因素并不牵涉在游戏中,那先行或后 行者当一必有一方有必胜/必不败的策略。例如:暴力穷举可行情况下,对于先发 优势的棋类游戏,分配了后手的棋手直接投降。

现实中暴力穷举工作量极大,现实中不可行,因此围棋挑战被称为 AI 界的‚阿 波罗计划‛。围棋的特点是规则明确(且规则条目数较少)、目标明确(结果只有赢、 输、平)、环境简单(对阵只有黑白两方),但局面变化极多(数量级 10^170)。由 于围棋的可能性极大,有 19*19=361 个点,一场 150 回合的围棋有多大 10^170 中局面,另外围棋的规则比较简单,很难基于棋面判断优势和劣势,所以在穷举的 算法中需要构建深度和广度都是几百的决策树结构,穷举算法几乎不可能完成。第 二代谷歌 TPU 计算能力是的 45 TFLOPS(每秒 45*10^12 浮点数运算),与围棋 的可能性数量级相差甚远。

QQ20171109-111957@2x

3.2、 Zero 的最大突破:使用纯强化学习,不再需要录入人类棋谱

AlphaGo Zero 与前面几代 AlphaGo 的共同之处:使用神经网络、蒙特卡洛 树和强化学习,使围棋趋近最优解。由于暴力枚举算法的不可行,前几代 AlphaGo 采用了卷积神经网络(采用一个策略网络 PolicyNet 和一个价值网络 ValueNet)、 蒙特卡洛树、强化学习,取得了超过世界冠军的成绩,使得围棋进一步向最优解靠 拢。新的 Zero 也采用了神经网络、蒙特卡洛树和强化学习,但技术上有许多区别。

QQ20171109-112025@2x

AlphaGo Zero 最大的突破,使用了纯强化学习(不是监督学习),没有借助 人类样本标注。AlphaGo Zero 没有再利用人类历史棋局,训练过程从完全随机开 始,AlphaGo Zero 是在双方博弈训练过程中尝试解决对人类标注样本的依赖,以 前其他版本的 AlphaGo,都经过人类知识的训练,它们被告知人类高手如何下棋。 而最新发布的 AlphaGo Zero 使用了更多原理和算法,从 0 开始,使用随机招式, 40 天后成为围棋界的绝世高手。

QQ20171109-112051@2x

无为而无不为,AlphaGo Zero 放弃监督学习。机器学习主要分为监督学习、 非监督学习和强化学习三种,AlphaGo Zero 主要使用了强化学习,前面其他版本 的 AlphaGo 都使用了监督学习+强化学习的算法,在学习了人类优秀棋局的基础上 进行自我训练。强化学习偏向于控制决策,监督学习偏向映射关系挖掘,可以相互 融合。

QQ20171109-112342@2x

补充:不录入人类棋谱(人工标注的样本)不代表没有数据输入和模型训练, 自我对弈训练后的结果令人振奋。事实上 AlphaGo Zero 的强化学习以自我对弈 (self-play)的结果为输入数据,对神经网络进行训练。真理需要时间来求证,强 化学习依然需要大量数据,但此次 AlphaGo Zero 的自我对弈盘数只 3 天、490 万 局,即可打败 AlphaGo Lee,使包括业内人士都感到振奋。

QQ20171109-112445@2x

3.3、 算法核心仍是蒙特卡洛树算法,策略、估值网络合二为一

蒙特卡洛树算法(MCTS)让围棋 AI 成为可能。MCTS 是一类随机方法的统称。 这类方法的特点是,可以在随机采样上计算得到近似结果,随着采样的增多,得到 的结果是正确结果的概率逐渐加大,但在获得真正的结果之前,无法知道目前得到 的结果是不是真正的结果。MCTS 使用了采样的方法有效地降低了围棋 AI 算法的复 杂度。

深度学习大幅缩减 MCTS 搜索空间,加速其收敛。AlphaGo 借助了深度学习中 的策略网络和估值网络,大幅缩减了 MCTS 的搜索空间。估值网络会为各个可行的 下法评估整个盘面的情况,给出一个‘胜率’,这些值会反馈到 MCTS 中,通过反 复迭代出‘胜率’最高的走法。MCTS 决定了策略网络仅会在‘胜率’较高的地方 继续收敛,这样就可以抛弃某些路线,缩减搜索空间。

其他提高效率的举措:AlphaGo Zero 将策略网络、估值网络合二为一,进一步 提高计算效率。在以前版本的 AlphaGo 中,策略网络、估值网络是两个不同的 DNN (深度神经网络),二者互相独立,在新版本的 AlphaGo Zero 中,DeepMind 巧妙地 将二者合二为一,大幅提高了计算效率。

3.4、 AlphaGo Zero 算法技术简析
核心算法 MCTS 算法的目的是递归迭代找到所有路径中价值最高的,即是找

到采样遍历中的局部最优解,主要步骤如下: a.选择,从根节点每次遍历都选择路径价值(Q+U)最高的路径。直到遍历到

结束节点;
b.拓展和模拟,如果遍历树的过程中遇到没有赋予 Q 值的节点 C,在 C 点拓展节点 D,并根据节点 D 模拟出所有到结束节点,并求出 V 值 c.反向传播,当节点 D 的模拟结束后,更新节点 D 的 V 值,并反向传播至根节点更新路径上的所有 Q 值,重复步骤 a; d.返回。搜索完成后,返回路径中价值最高的路径的搜索概率 π

未标题-1

左右互搏,自我博弈 MCTS+DNN 算法,通过自己与自己博弈训练 DNN(深 度神经网络,主要用了 DNN 中的 CNN 卷积神经网络),策略网络帮助 MCTS 算法 做出较优预测下一步棋,估值网络根据 MCTS 的预测再更新策略网络(目标是策 略函数能逼近估值函数),并继续迭代下一步棋直至棋局结束。算法的潜台词是: MCTS 算法找出的解相对更优,即估值网络的模型更接近于最优解,所以策略网络 模型要向估值网络逼近。

AlphaGo Zero 自我对弈训练的流程:

a. 程序自我博弈,标记为 s1, …, sT。在每个位臵 st,使用最新的神经网络 fθ 执行 MCTS αθ,每个走子选择的依据是通过 MCTS, at ∼ πt 计算的搜索概率,并 记录处于最后状态的 sT 的 Z 值。

b. AlphaGo Zero 中神经网络的训练。该神经网络将棋盘位臵 st 和参数θ作为 输入,输出表示每一走子的概率分布的向量 pt 和一个表示当前玩家在位臵 st 上 的胜率的标量值 vt,目标是调整参数θ让 pt 与πt 的相似度最大且 vt 和 Z 的差距最 小,新的参数θ作为下一步 MCTS 的输入。

QQ20171109-112712@2x

4、 强化学习更贴切人类学习本质,应用前景广泛

4.1、 AlphaGo Zero 带来新思考

作为强化学习的历史性案例,AlphaGo 完全强化带来的新思考:部分场景下, 大量标注数据可能并非必需品。由于人类大脑计算资源有限,在从事围棋等活动时 不可能枚举出所有的落子可能,而更倾向于选择局部最优解,而从 AlphaGo Zero 的棋力来看,人类几千年的围棋认知可能并非完全正确。从应用角度来看,在部分 场景中(不是全部),以后可能不再需要耗费人工去为 AI 的产品做大量的前期准备 工作,类似的深度强化学习算法或许能更容易地被广泛应用到其他人类缺乏了解或 是缺乏大量标注数据的领域。

4.2、 (深度)强化学习的应用场景探析

(深度)强化学习适用于解决有限维度、有反馈,需要做出(连续)决策的相 关应用。由于强化学习每一次输入都会影响到后续的状态和输入,当应用的数据表 征维度较高时,会出现维度灾难的问题。除了 ADAS、机器人以及游戏等应用之外, 深度强化学习还可以应用到以下场景:

1.广告投放,例如算法 LinUCB,会尝试投放更广范围的广告,尽管过去还没 有被浏览很多,能够更好地估计真实的点击率。例如 2016 年双 11,阿里巴巴规模 化上线最前沿的人工智能技术深度增强学习与自适应在线学习,用户点击率提升 10-20%。

2.股票投资,应用强化学习来评价和学习交易策略,根据彭博社的消息, WorldQuant 公司正在使用深度学习做小规模的交易。

3.动态定价,企业根据市场需求和自身供应能力,以不同的价格将同一产品适时 地销售给不同的消费者或不同的细分市场,以实现收益最大化的策略,强化学习中 的 Q-learning 可以用来处理动态定价问题。

4.动态治疗,动态治疗方案(DTR)是医学研究的一个主题,是为了给患者找 到有效的治疗方法。 例如癌症这种需要长期施药的治疗,强化学习算法可以将患 者的各种临床指标作为输入 来制定治疗策略。

5.前沿科学,范围可以包括预测蛋白质分子的形状,设计新材料和进行气候建模。

推荐文章

沪公网安备 31010702002009号