跟着AlphaGo 理解深度强化学习框架

管理员账号

2018-08-29

小编说:AlphaGo 这个被大家热议过很久的主题,里面其实包含了非常深刻的机器学习智慧,是学习机器学习甚至是人类决策的绝好教材。机器学习是AlphaGo 取胜的关键,为什么它会发挥巨大作用,请看下文。

了解一门科学技术最好的方法就是找出其核心论文,让我们看看AlphaGo 的核心论文是怎么解读这个问题的。如果把你放在这样一个位置,你会如何设计这盘游戏。

如果大家了解棋牌类游戏以及电脑与之对弈的历史,就会非常清楚老派程序员的套路,也就会明白这类问题最简单的办法就是穷举法,比如历史上著名的八皇后问题,你需要在国际象棋棋盘上摆放八个皇后,使得她们各自不位于对方的纵线、横线或对角线上,你只需要按照一定的方法做一个循环,从第一排往下一排遍历,当碰见摆不开的情形时,就回到上一步重新摆,最后总可以摆出来。

与之类似的方法稍作改进可以很好地解决国际象棋的问题,却难以解决围棋的问题,为什么?因为众所周知,围棋的维度实在太大了,每一次落子都有几百(棋盘19*19 大小)种可能。设想假如一盘棋要在几百步之后得出胜负,会有多少种可能性,确实很难通过任何和穷举法沾边的算法解决。

这里就涉及如何有效地减少搜索空间这个核心问题。这也是为什么一个下围棋的问题需要用到机器学习,因为机器学习可以让你通过有限数据推测所有其他可能(类似一个插值过程)。

在让机器做这件事之前先看看人是怎么做的。我们无时无刻不在决策,也面临如何减少搜索空间的问题。虽然人生有无限种可能,但大多数可能你连考虑都不会考虑。

我们人类用愚蠢和聪明、合理与不合理这些词汇描述各种选择的优劣,并且大脑自动屏蔽大部分不合理的解释。你是如何得到这些答案的呢?第一个就是通过常年的试错来计算每个行为的结果,所谓一朝被蛇咬,十年怕井绳。另一个就是看书,和高手对话,直接学习他们的经验。

反过来就是机器学习的原理,首先说试错学习,或者根据某种行为最终导致的结果来调整行为策略的方法,我们通常称之为强化学习。

强化学习如上图,Agent 会根据环境给予的reward 调整action 的一个反馈系统,最终实现利益最大化,难点在于Agent 的行为通常会改变环境,而环境又会影响行为策略。

具体到围棋上,这个策略的核心是根据围棋的特性:

(1)在每一步双方信息完全已知;

(2)每一步的策略只需考虑这一步的状态。

这允许机器学习用一个非常凶猛的简化框架来解决这个问题,即马尔科夫决策过程。也就是说,我们用一个离散的时间序列来表述状态s,用另一个离散的时间序列表述行为a,两个时间序列有着深刻的耦合关系,下一刻的状态s(t+1)取决于此刻行为a(t)和状态s(t),最终决定下一刻的行为a(t+1)。两者间的关系即策略P(a(t)|s(t)),由于是马尔科夫链,所以每一时刻的策略只与此刻状态s(t)有关。各种棋类就是最明显的马尔科夫链。由于未来存在不确定性,因此策略本身也是一个概率分布函数的形式。最终我们要优化,使得P(s|a)所得到的回报R(s)最大。马尔科夫决策过程是在解决未来状态不确定而行为和状态又具有马氏性时十分有利的方法。

解决马尔科夫决策过程的一个简单实用的算法叫作蒙特卡洛树搜索(MCTS),如下图。

上图描述了蒙特卡洛树与它的四个步骤:选择、扩张、模拟估值和结果回传,对应一个经典的强化学习框架。
蒙特卡洛是大名鼎鼎的随机抽样方法。提到树,大家一定可以想到决策树,树的节点是某一刻的状态,枝杈代表一个决策。而这里的蒙特卡洛树,就是用随机抽样的方法生成整个决策树的过程。

假设电脑现在的状态是s(t),那么你随便扔个骰子走一步,然后电脑模拟的对手也扔个骰子随便走一步,这样下去,总有一刻会分出胜负,这个时候你回顾胜利和失败的人的历史走棋轨迹,赢的走法在其整个决策树上的每个状态(枝叶)都加一分,输的走法每一步位置都减一分,这个分数会影响下一次抽样的概率,使得容易赢的步子会有更大概率取到。玩无数次后,就会选择出特别容易赢的策略。这个过程酷似进化选择算法,就是让那些有优势的选择有更高的繁殖子代概率,从而最终胜出,体现了生物和环境的博弈。

注:这里提个小问题,马尔科夫决策过程威力巨大,而在现实决策里,你要去哪个大学上学,你要选哪个股票,都很难只看当下,这个框架还能用多少呢?

以蒙特卡洛树为代表的强化学习在围棋这种走法可能性超多的情况下,只能部分地减少搜索空间,使得电脑达到一个高级业余选手的水平,而如果要进一步减少搜索空间,应该怎么办呢?人类减少搜索空间的一个重要方法是学习高手经验,背棋谱,看得多了,就有一种犀利的直觉走出一个妙招。转化为数学语言,就是通过看棋谱,取得一个在某种局面下任意策略和最终赢率的对应关系,即使这个局面你从未见过。

注:我们经常会觉得直觉这个东西好像是天上掉下来的异禀,实则恰恰相反,直觉才是最需要学习的。

让机器来做就是有监督学习的回归算法,你要提取棋局的特征,算出对应每一个走法出现的概率P(a(t)|s(t)),然而围棋棋局的特征实在太复杂,这时候我们的深度学习开始派上用场,它可以自发地学习事物的表征。

机器学习训练的目标是使得数据被观测到的概率最大, 所谓MaximumLikelihood,对于神经网络,就是网络连接参数的调整。

深度学习的过程正如同我们见识一个东西多了,自发地开始具有举一反三的能力,自然而然地把直觉加入了策略选择,这时候你可以通过有限的经验把握无限。在训练过程中,AlphaGo 不停地根据现有的局面预测专家可能会出的招,在经过三千万组数据的训练后,深度学习可以达到55.7%的预测率,这个概率说明人类的意图也并不难被猜中,这也是很多人说和AlphaGo 下棋如同和无数高手过招的原因。当然,这还不是训练的终结,此处的神经网络只是在描摹高手的动作,而之后我们要让它能赢,好比在实践中理解和优化高手的招术,这就是训练的第二步,用强化学习方法,训练网络连接系数,具体方法是让现有的策略网络和随机选出的一个之前的策略网络进行左右互搏,然后把胜负结果回传到每一步的策略上,进行梯度训练。经过这个过程,策略网络可以成功战胜一些中级爱好者水平的算法和自己之前在描摹各种高手时候的状态。

策略网络的思维是计算每种走法出现的概率。

训练的最后一步是估值网络。估值网络是做什么的呢?首先,在一个强化学习框架下,你需要知道每个行为所对应的确定回报,难点在于围棋是下完棋才有确定回报的,想想围棋步骤中的无限多可能性以及得到结果可能的步数就令人生畏,此处深度学习算法的作用正是不需要走完就巧妙地估计出这一步对应的盈利期望,过程需要用一个深度网络通过强化学习的框架来进行。估值网络的本质在于建立现有行为和长远收益的联系,有人称之为看趋势和全局观。

公式如下,训练要解决的问题是,求得状态S 下采取策略p 的最终收益。

估值网络的效果图如下。

那么问题来了,蒙特卡洛树和深度学习两者是如何天衣无缝地结合起来的呢?这就是整个AlphaGo 设计最巧妙的地方。首先蒙特卡洛树可以拆解为4 步:

第一步,Selection,在已有的选项(经历过的)中进行抽样选择。

第二步,Expansion,走到一个先前从未经历的局面上,探索新行为,即生成新的枝杈。

第三步,Evaluation,得到新行为的回报。

第四步,Backup,把回报的结果反向传递给策略。深度学习的结果可以被非常完美地嵌入蒙特卡洛搜索的步骤里,首先,在Expansion 的阶段,我们不用从零开始随机生成一个前所未有的状态,而是根据前人经验训练的策略网络直接生成新状态,海量减小了无用的搜索。然后,在Evaluation 步骤,我们无须跑完整个比赛,而是通过深度学习的结果直接算出这个新举措可能的回报(此处即估值网络的作用),这个计算出的回报,会在最终游戏完成的时候与真正的结果相结合,从而完成学习的步骤。

深度学习嵌入蒙特卡洛树搜索的方法如下。

与战胜国际象棋大师的深蓝不同,在AlphaGo 这里,机器学习发挥了巨大的作用,因为AlphaGo 的策略和智能主要是在不停地看棋谱和左右互搏中进化出来的,对于围棋这样规则非常复杂的东西,设计一套必胜规则几无可能,只有机器学习(强化学习)的进化和自我改进思想才是最终取胜的法器。因此AlphaGo 的技术对其他人工智能非常有启发。

从整个解析来看,其实训练AlphaGo 的算法思路并不十分复杂,用一句话总结,就是站在巨人的肩膀上迅速试错。这可能也是各种人生决策的最好方法吧。然而,我们人类没有那么多时间玩Simulation,也没有那么多GPU 进行并行运算,所以我们其实寻找的是低搜索成本的近似解,谓之次优解。

本文选自《机器学习vs复杂系统》一书,作者许铁,电子工业化版社2018年8月出版。

这是一本有关人工智能、机器学习、深度学习、复杂系统的科普读物,本书从跨学科视角来看待人工智能这个技术性的学科。围绕用数学模型预测未来这一主题,介绍算法,主要包括现在流行的机器学习和深度学习算法,以及算法要解决问题本身的复杂性。复杂的问题,需要复杂的算法,而算法设计背后的老师正是自然界的复杂性本身。

读者评论

相关专题

相关博文

  • 机器学习算法实现解析——word2vec源码解析

    机器学习算法实现解析——word2vec源码解析

    赵志勇 2017-05-23

    在阅读本文之前,建议首先阅读“简单易学的机器学习算法——word2vec的算法原理”(目前还没发布),掌握如下的几个概念: 什么是统计语言模型 神经概率语言模型的网络结构 CBOW模型和Skip-gram模型的网络结构 Hierar...

    赵志勇 2017-05-23
    635 0 0 0
  • 深度学习第一天“基本概念”

    深度学习第一天“基本概念”

    款热的AI患者 2017-05-07

    人工智能,机器学习,深度学习 人工智能范围宽泛,机器学习是实现人工智能的一种手段,深度学习是人工智能的一个分支。 深度学习发展史 目前深度学习,基本上是神经网络的代名词。 神经网络发展史基本分为三个阶段 第一阶段类似于仿生(McCul...

    款热的AI患者 2017-05-07
    163 1 0 0
  • 初识视觉SLAM:用相机解决定位和建图问题

    初识视觉SLAM:用相机解决定位和建图问题

    管理员账号 2017-05-04

    小编说:视觉SLAM 是指用相机解决定位和建图问题。本文以一个小机器人为例形象地介绍了视觉SLAM的功能及特点。 SLAM 是Simultaneous Localization and Mapping 的缩写,中文译作“同时定位与...

    管理员账号 2017-05-04
    1020 0 0 0