阿尔法狗是怎么用机器学习做决策的
雷锋网 作者： 混沌巡洋舰 2016-09-18 18:05:23 查看源网址
阅读数：26
雷锋网注：本文作者许铁， 法国巴黎高师物理硕士 ，以色列理工大学（以色列85%科技创业人才的摇篮, 计算机科学享誉全球）计算神经科学博士，巡洋舰科技有限公司创始人, 曾在香港浸会大学非线性科学中心工作一年。
阿尔法狗这个被大家热议过很久的主题， 里面其实包含了非常深刻的机器学习智慧。 是一部学习机器学习甚至是人类决策的绝好教材。机器学习是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))，然而围棋棋局的特征实在太复杂，如果你来一个线性回归或KNN，一定会死的很惨。 这时候我们的深度学习开始派上用场。它可以自发的学习事物的表征。
图，通过梯度回传训练网络连接
机器学习训练的目标即使得数据被观测到的概率最大，所谓Maximum Likelihood，对于神经网络，就是网络连接参数的调整。
深度学习的过程正如同我们见识一个东西多了，自发的开始具有举一反三能力，因之可以称为把直觉加入了策略选择，这时候你可以通过有限的经验把握无限。 在训练过程中，Alphago不停的根据现有的局面预测专家可能会出的招， 在经过三千万组数据的训练后，深度学习可以达到55.7%的预测率，这个概率说明人类的意图也并不难被猜中，也是为什么人会说和Alphago下棋如同和无数高手过招。 当然，这还不是训练的终结， 此处的神经网络只在描摹高手的动作， 而之后我们要让他能够赢，好比在实践中理解和优化高手的招术，这就是训练的第二步，用强化学习方法， 训练网络连接系数， 具体方法即让现有的策略网络和随机选出一个之前的策略网络进行左右互搏，然后把胜负结果回传到每一步的策略上，进行梯度训练。经过这个过程， 策略网络可以秒掉一些中级爱好者水平的算法和自己之前在描摹各种高手时候的状态。
图：策略网络的思维，计算每种走法出现的概率
训练的最后一步是估值网络，说说这里估值网络是干什么的， 首先，在一个强化学习框架下， 你需要知道每个行为所对应的确定回报，难点在于围棋下完棋才有确定回报，想想围棋步骤中的无限多可能性及得到结果可能的步数就令人生畏，此处深度学习算法的作用正是不需要走完就巧妙的估计出这一步对应的赢利期望， 过程需要用一个深度网络通过强化学习的框架来进行。估值网络的本质在于建立现有行为和长远收益的联系。 有人称为看趋势和全局观。 训练这样一个计算回报的网络作用请往下看。
公式： 训练要解决的问题， 求得状态S下采取策略p最终收益的期望
图： 估值网络的效果图，数字即回报
那么问题来了， 蒙特卡洛树和深度学习两者如何天衣无缝的结合起来呢？ 这就是整个Alphago设计最巧妙的地方 ： 首先，你应该还记得MCTS的框架， 首先MCTS可以拆解为4步：第一selection，在已有的选项（经历过的）中进行抽样选择， 第二expansion， 走到一个没有先前从未经历的局面上，探索新行为，即生成新的枝杈， 第三Evaluation，得到新行为的回报，第四，回传，把回报的结果反向传递给策略。深度学习的结果可以被非常完美的嵌入到蒙特卡洛搜索的步骤里， 首先在expansion的步骤，我们不用从零开始随机的生成一个前所未有的状态，而是用根据前人经验训练的策略网络直接生成新状态， 海量了减小了无用的搜索。 然后， 在Evaluation的步骤上，我们可以不需要跑完整个比赛，而是通过深度学习的结果直接算出这个新姿势可能的长期回报（此处即估值网络的巨大作用，所谓步步看清n久之后的影响），这个计算出的回报，会在最终游戏完成的时候与真正实践的结果相结合完成学习的步骤。
图 ：深度学习如何嵌入蒙特卡洛树搜索
与战胜国际象棋大师的深蓝不同， 在Alphago的情形下机器学习发挥了巨大的作用，因为Alphago的策略和智能主要是在不停看棋谱和左右互搏中进化出来的，对于围棋这样规则非常复杂的东西，设计一套必胜规则几无可能，也只有机器学习（强化学习）的进化和自我改进思想才是最终取胜之法器。也是为什么Alphago的技术对其它人工智能非常有启发。
从整个上面的解析看来， 其实训练Alphago的算法思路并非十分复杂，用一句话总结， 就是在巨人的肩膀上迅速试错。 这也是各种人生决策的最好办法吧。 你说你要活独一无二的人生不模拟任何人，你估计是个撞南墙的傻X，你说你要就看着最牛逼的精英跟着走， 你可能一辈子重复别人的生活。而牛X的人， 显然是站在巨人的肩膀上，边描摹那三千万精英的步法，并深度总结其规律， 然后在变化自己的动作花样。 然而我们人类没有那么多时间完simulation，也没有那么多GPU进行并行运算， 所以我们其实在找的是低搜索成本的近似解，谓之次优解。