524
【專欄】穀歌資深工程師深入淺析AlphaGo Zero與深度強化學習
AlphaGo的巨大成功掀起了圍棋界三千年未有之大變局，也使得深度強化學習(Deep Reinforcement Learning)漸為大眾熟悉。尤其是最新推出的AlphaGo Zero完全摒棄了人類知識，並且三天內碾壓了早期版本的AlphaGo，更足顯強化學習和深度學習結合的巨大威力。AlphaGo Zero的論文側重於描述效果，對於方法的論述比較簡短，沒有相關背景的人讀起來可能會有一些困難。本文對強化學習以及AlphaGo Zero算法做了詳細描述。
摘要
- AlphaGo Zero無需任何人類曆史棋譜，僅使用深度強化學習，從零開始訓練三天的成就已遠遠超過了人類數千年積累的圍棋知識。
- 強化學習能夠考慮到算法對於環境的影響, 特別適合解決多回合博弈問題。
- 在強化學習中，數據在運行過程中自主收集，這是AlphaGo Zero能擯棄人類棋譜的原因。
- 強化學習的速度限製通常來源於環境給予反饋的時延。弈棋類問題可以通過左右互搏得到即時反饋，所以弈棋類問題對於強化學習來說是比較容易的一類問題。
- 在強化學習中知識存儲在值函數中，深度強化學習就是利用深度神經網絡來逼近值函數的一類強化學習方法。AlphaGo Zero使用了華人提出的ResNet進行深度學習，提升達到600Elo。
- 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最重大的意義。
第一版本由好幾個部分拚湊起來，像是接力跑一樣，到底是哪個部分最核心最關鍵也說不好。許多人會認為基於人類曆史棋譜的學習是最重要的部分。但是這邊文章證明的是，人類曆史棋譜不僅不幫忙，很有可能是限製算法效率的因素。人類的圍棋知識可能陷入了一個局部最優。如果從這個點出發優化，可以做到比人好一些，但是不可能達到望塵莫及的地步。
AlphaGoZero直接用強化學習從頭開始學習，沒有條條框框，可以探索出完全不同的方式。我認為這就是為什麼新版會強很多的原因。
另外為什麼新版會快很多？第一拿掉了很多無用的部分，計算效率當然更高。第二應該是團隊的工程能力和對工具的熟悉度都有了很大提升，Deepmind2014年加入Google，2016年初第一版的時候對於Google的架構很有可能還不是那麼熟悉，這一版本肯定進行了大量的優化。
原文發布時間為：2017-10-27
本文作者：王晶
本文來自雲棲社區合作夥伴新智元，了解相關信息可以關注“AI_era”微信公眾號
原文鏈接：關於新老AlphaGo的區別和AlphaGo Zero意義的個人看法
最後更新：2017-10-27 16:04:18