即將于2017年11月8日在北京國家會議中心舉辦的AI World 2017世界人工智能大會，我們請到CMU教授、冷撲大師發明人Tuomas Sandholm，百度副總裁王海峰，微軟全球資深副總裁王永東，阿里巴巴副總裁、iDST副院長華先勝，亞馬遜AWS機器學習總監Alex Smola，科大訊飛執行總裁胡郁，華為消費者事業群總裁邵洋等國內外人工智能領袖參會并演講，一起探討中國與世界AI的最新趨勢。
新智元專欄
作者：王晶
【新智元導讀】AlphaGo的巨大成功掀起了圍棋界三千年未有之大變局，也使得深度強化學習(Deep Reinforcement Learning)漸為大眾熟悉。尤其是最新推出的AlphaGo Zero完全摒棄了人類知識，并且三天內碾壓了早期版本的AlphaGo，更足顯強化學習和深度學習結合的巨大威力。AlphaGo Zero的論文側重于描述效果，對于方法的論述比較簡短，沒有相關背景的人讀起來可能會有一些困難。本文對強化學習以及AlphaGo Zero算法做了詳細描述。
作者簡介：王晶，Google廣告大數據部門資深工程師，從事機器學習算法研發，2014年博士畢業于波士頓大學，主要研究方向強化學習。2010年本科畢業于華中科技大學。
1. AlphaGo Zero無需任何人類歷史棋譜，僅使用深度強化學習，從零開始訓練三天的成就已遠遠超過了人類數千年積累的圍棋知識。
2. 強化學習能夠考慮到算法對于環境的影響, 特別適合解決多回合博弈問題。
3. 在強化學習中，數據在運行過程中自主收集，這是AlphaGo Zero能擯棄人類棋譜的原因。
4. 強化學習的速度限制通常來源于環境給予反饋的時延。弈棋類問題可以通過左右互搏得到即時反饋，所以弈棋類問題對于強化學習來說是比較容易的一類問題。
5. 在強化學習中知識存儲在值函數中，深度強化學習就是利用深度神經網絡來逼近值函數的一類強化學習方法。AlphaGo Zero使用了華人提出的ResNet進行深度學習，提升達到600Elo。
6. AlphaGo Zero使用的強化學習方法稱為Policy Iteration （策略迭代法）。Alphago Zero交替使用深度學習評估策略(policy evaluation)和蒙特卡洛樹搜索優化策略(policy improvement)。
強化學習（Reinforcement Learning）是機器學習里面一個分支。如果說強化學習在AlphaGo之前版本里面還是初試牛刀的話，那在AlphaGo zero里面就真正大顯神威了。根據deepmind的論文，新版本AlphaGo Zero經過三天的訓練輕易達到對老版本的100:0的勝率，并且完全無需人類棋譜。可以說，AlphaGo Zero僅僅三天的成就就遠遠超過了人類數千年的圍棋探索。
為什么強化學習能夠這么強？這要和它的特點有關系。強化學習和傳統機器學習的區別有如下幾點：
傳統機器學習假設算法本身對于環境無影響，強化學習破除了這個限制，能夠考慮到了算法對于環境的影響, 這使得強化學習特別適合解決多回合博弈或者順序決策問題（sequential decision making）問題。事實上，這類問題在生活中是非常普遍的，比如股市的交易。傳統機器學習可以預測股票價格，但是只有不使用結果進行買賣模型才會長期有效。如果你預測完了之后你根據據測去做多或著做空這個股票，那么其他的股票買家可能因為你的行為改變了自身行為，你原來的訓練的模型便會失效，而強化學習可以考慮到這點。
在強化學習中，數據是在運行過程中自主收集。這解決了機器學習中常見的訓練數據難于獲取的問題。AlphaGoZero之所以能夠完全摒棄人類知識就是因為所有的數據都是通過機器互博生成。從這個意義上來說，強化學習的算法具有自主學習能力。這就是強化學習在機器人領域里面使用比較廣泛的原因。但是要注意到的是，通常強化學習的速度限制并不是來自于算法的訓練，而是來自于環境給予反饋的延時。比如說股票交易里，股票的漲跌必須過一段時間才能發生，股市關閉的時候也不可能有反饋。所以就不可能像AlphaGo Zero這么快。
具有強化學習能力的程序或機器人被稱為代理（Agent）。代理所解決的問題被抽象為環境（environment）。注意，這里的并不是說我們通常意義的環境，而實際上是一個具有特定行為的另一個代理。環境可以處于多種狀態，狀態之間的轉換可以用馬科夫過程表述（markovian decision process）。代理的目標是通過與環境的交互學會環境的內在狀態和與環境打交道的最優策略。
代理算法和環境的一次交互稱為迭代。算法需要有一個基本的策略（policy），在每次迭代過程中，算法會根據這個策略選擇一個動作（action）。在接收到算法的動作之后，環境會返回一個信號（reward），正代表獎勵，負代表懲罰。代理會根據這個信號來評價自己先前策略是否好。下圖是一個強化學習的示意圖：
用強化學習解決問題，我們需要首先把要解決的問題轉化成為一個環境（environment）。環境需要如下的要素：
狀態空間（state space）：對于圍棋來說，每一個棋盤布局（記為s）就是一個狀態。所有可能的棋盤布局就是狀態空間。
動作空間 （action space）：對于圍棋來說，所有可能落子的位置就是一個動作空間
可行動作 （allowable action）： 在給定狀態下，什么動作是可行，什么是不可以的。在圍棋里，就是給定一個棋盤，哪里可以落子，哪里不可以。
狀態轉化：你落子之后，對手可能會下的子。如果是兩臺alpha zero互搏的話，相互是對方環境的一個部分。
獎勵函數：你落子之后得到的信號。在圍棋里面，就是勝率的一個正函數。勝率越大，獎賞越大。
在強化學習里面，知識可以通過一個稱為狀態－動作值函數（state-action value function) 的結構的存儲。通常大家用符號Q(s,a)來表示這個函數，這就是所謂Q-learning的來歷。簡而言之，Q(s,a)是對于狀態s，采取動作a的期望獎勵(expectedreward)。
在最早期的強化學習算法里面，Q(s,a)就是一張表的形式來存儲的。每次算法會查這個表，然后選取能夠帶來期望收益最大的動作。需要注意的是，實際過程中算法還需要考慮到過早收斂的問題（可以用探索exploration來解決，我們會稍后聊到）。顯而易見，如果狀態空間很大，或者是連續空間，那么查表就不管用了，需要使用函數逼近的方式，這就是神經網絡的強項了。
在深度強化學習就是利用深度神經網絡來逼近值函數的一類強化學習方式。而AlphaGo就是深度強化學習的代表。
下面開始正式的介紹AlphaGo Zero的實現。
在AlphaGo里面，并沒有直接用神經網絡逼近狀態－動作值函數Q(s,a)，而且用來逼近另外一種值函數－－狀態值函數。簡而言之：
V(s)是棋盤布局s下自己的平均勝率。
V的定義域要遠遠小于Q，所以逼近起來容易一些。但是V中的信息需要一定的轉化才能用來決定落子位置。
先介紹一種經典的方式（雖然AlphaGo Zero沒有采用這種方式）：大概的方式是先通過V重建出Q，然后再用查表法類似的概念來確定落子位置。如何重建呢？要點在于如下公式：
其中P(s, a, s') 是在布局s的情況下，落子a處，對方落子之后，布局會變為s'的概率。r(s,a) 是這一步的收益（但是在AlphaGoZero里面實際是一個常量，只取決于最終的勝負）。這個公式的意思是，如果一個落子能夠平均意義上將我的帶到一個更好的布局，那么這個落子的平均期望收益就更好。如果我們有辦法知道轉化概率P(.,.,.)的話，那么就可以通過V來重建出Q。
那么我們怎么才能夠知道概率呢？一個方式是嘗試很多次在布局s的情況下落子到位置a，然后用真正跳到布局s'的頻數除以總共試的次數就是估計的概率了。不幸的是，這個方法對于仿真次數要求很高，不是很實用。
在AlphaGo早期版本里面，利用了另外一個神經網絡來解決這個問題。大概的思路是把估計Q和根據Q的信息預測下一步的落子位置的這個兩個部分合起來當作一個黑箱，用來逼近值函數V的神經網絡被稱為 Value Network
用來預測落子位置的神經網絡被稱為 Policy Network
AlphaGo Zero在此基礎上又進一步改進。將兩個網絡融合稱為一個神經網絡。對于每一個可能的棋盤布局s，這個神經網絡輸出如下兩個結果：
當前勝率(v)：在當前的盤面下己方取勝的概率。v就是之前版本里value network的輸出
落子概率(p)：這是一個向量，每一個維度對應棋盤上的一個位置，向量的第a個元素是落子到位置a的概率。p就是之前版本里policynetwork的輸出。
蒙特卡洛樹搜索MCTS
前一部分提到的落子概率也被稱為策略（policy）。有了落子概率，非常簡單的方式是直接按照這個概率進行落子。但是事實上這會導致神經網絡總是原地踏步。這是因為Policy Network的訓練數據是自己和自己下棋（self-play）生成的輸出，僅僅自己學習自己是不會有改進的。
所以這里需要有一個辦法來利用值函數V的信息來優化這個策略。在AlphaGo系列算法里面是使用蒙特卡洛樹搜索（Monte Carlo TreeSearch）來進行策略優化的。上圖是AlphaGo的結構圖，MCTS的輸出是依據值函數V得到的一個更優策略，它將被用于通過self－play來生成數據供深度神經網絡學習。MCTS也是AlphaGo能夠通過self－play不斷變強的最重要的原因。
這一種強化學習方法被稱為 PolicyIteration （策略迭代法）。這個方法里面交替執行如下兩步：
策略評估（policy evaluation）：估計當前policy的value function。也就是神經網絡在做的事情
策略優化（policy improvement）：使用蒙特卡洛樹搜索根據估計的valuefunction改進的policy
下面詳細介紹一下這個策略優化是怎么進行的。在圍棋行棋的過程中，每一次落子都有多種變化，可以用一個多叉樹來表示。樹的每一個節點代表了一種棋盤布局s，每一個邊代表了在一種布局s下的一種落子方式a。
在MCTS里面，每一個邊存儲四個信息
Q(s, a): 平均收益：這個就是前文提到的狀態－動作值函數。
N(s, a)：訪問次數
W(s,a): 總收益
P(s,a): 出現狀態s并且選擇了動作a的先驗概率。這個先驗概率就是神經網絡預測的落子概率。
AlphaGo Zero的MCTS有如下的四個步驟。我們會依次介紹：
推演落子規則 (Select)
在每一個節點s，AlphaGo Zero會根據如下的公式來選擇下一次落子位置
其中U(s,a)=cpuctP(s,a)bN(s,b)1 N(s,a)。 U(s,a)是一個confidence interval 的upbound。cpuct決定探索（exploration）的程度。
MCTS在進行搜索的過程中，嘗試重建狀態動作值函數Q。然后根據查表法類似的原理選擇能使期望收益最大的動作。注意到這個增加了一個額外的選項U(s,a)。為什么這個選項重要呢？有兩個原因
即使我們Q的估計完全準確，如果我們每次都選最優的，那么算法很快會收斂到一個局部解跳不出來了，所以我們需要避免讓算法老走一樣的棋，增加一些探索其他選項的機會。這就跟小孩子學習一樣，必須通過適當的犯錯才能夠學習到更多。
我們里的值函數只是一個估計值，不一定準確。
推演和判定 (Expand and Evaluate)
AlphaGo Zero會根據前面的落子規則不斷的落子，這就相當于棋手在腦海中進行推演。但是圍棋的搜索空間即使對于計算機來說也是太大，alphago zero只會推演（仿真）到一定步數就停止了。假設最后的布局是s', 那么AlphaGo Zero會調用深度神經網絡來預測這局推演結束時自己的勝率v(s') 。這樣的推演過程會進行多次。
復盤 (Backup)
等一次推演結束后，AlphaGo Zero會根據推演的結果更新自己的知識，也就是值函數Q（s，u）。對于任意棋盤布局s和任意一種可能落子方案，AlphaGo Zero會依據最終的勝率調整落子的知識（存儲在值函數Q(s, a) 里面）。值函數的更新公式如下：
對于這個公式的理解重點在于這個求和符號。
代表的是一次推演出現了在布局s的情況下AlphaGo Zero選擇了落子a處，并且這次推演最終布局是s'。N(s, a)是說有多少次這種情況發生。v(s')是最終盤面的勝率，相當于最終的獎勵。這個獎勵被平均分配到每次決策中。
真正落子(Play)
在不斷的推演復盤再推演的過程中，行棋會不斷的優化。經過一段時間優化，推演的落子概率就是一個更加好的策略。MCTS的輸出
其中\pi_a是落子到位置a的概率，是一個參數，\tau用來指定溫度。如果溫度越高，落子越隨機，溫度越低落子越確定。
深度學習訓練
在AlphaGo Zero里使用的是有監督的深度學習。而訓練樣本來自于自己和自己博弈的訓練數據（self play）。每一步Alpha Zero都會根據MCTS來選擇落子處，直到分出勝負。勝者的單步獎勵（記為z）是＋1，負者的單步獎勵是－1。
前文提到AlphaGo Zero里面的神經網絡實際上是把AlphaGo里面的Policy Network和Value Network糅合在一起了，所以這個神經網絡也有兩個目標
讓輸出的落子概率p和MCTS的輸出越接近越好
讓預測的值函數v和實際的獎勵z越接近越好
最終的要優化的損失函數是
損失函數l包含三項：第一項是為了優化值函數的預測，第二項是為了優化落子概率的預測，第三項是為了防止過擬合。
AlphaGo Zero每1000步會將一個神經網絡存檔，并且把這個存檔和歷史最優版本比較，如果勝率超過歷史最優的55%，這個版本將會被更新為歷史最優。并且在生成數據時，只使用歷史最優的神經網絡的self－play數據作為深度網絡的訓練數據。這樣可以增加算法的優化速度。
AlphaGo Zero里使用的是深度殘差網絡（ResNet），論文里面提到ResNet帶來了600 Elo的提升。這個方法是何凱明，Xiangyu Zhang, Shaoqing Ren, 孫劍等人在微軟亞洲研究院工作期間提出，孫劍是曠視(face )的首席科學家，何凱明現在在facebook AI部門。這可以看出華人科學家在現在在深度學習領域里面有相當舉足輕重的地位。
論文里面還提到了很多工程實現和調參的細節。我暫時還沒有自己實現，但這些細節應該對AlphaGo Zero最終效果起到了至關重要的幫助。這邊文章主要描述方法，有機會我會另辟文描述工程實現。
關于新老AlphaGo的區別和AlphaGo Zero意義的個人看法
新版方法上面并沒有增加，反而是減少了很多部分：依據人類棋譜學習的監督學習部分，快速走子部分都被拿掉了。兩個神經網絡被融合成一個。在我看來，少就是多，這就是AlphaGo Zero最重大的意義。
· https://deepmind.com/blog/alphago-zero-learning-scratch/
· https://storage.googleapis.com/deepmind-media/alphago/AlphaGoNaturePaper.pdf
· Deep Residual Learning for Image Recognition： https://arxiv.org/abs/1512.03385
