了解一門(mén)科學(xué)技術(shù)最好的方法就是找出其核心論文，讓我們看看AlphaGo 的核心論文是怎么解讀這個(gè)問(wèn)題的。如果把你放在這樣一個(gè)位置，你會(huì)如何設(shè)計(jì)這盤(pán)游戲。 如果大家了解棋牌類游戲以及電腦與之對(duì)弈的歷史，就會(huì)非常清楚老派程序員的套路，也就會(huì)明白這類問(wèn)題最簡(jiǎn)單的辦法就是窮舉法，比如歷史上著名的八皇后問(wèn)題，你需要在國(guó)際象棋棋盤(pán)上擺放八個(gè)皇后，使得她們各自不位于對(duì)方的縱線、橫線或?qū)蔷€上，你只需要按照一定的方法做一個(gè)循環(huán)，從第一排往下一排遍歷，當(dāng)碰見(jiàn)擺不開(kāi)的情形時(shí)，就回到上一步重新擺，最后總可以擺出來(lái)。 與之類似的方法稍作改進(jìn)可以很好地解決國(guó)際象棋的問(wèn)題，卻難以解決圍棋的問(wèn)題，為什么？因?yàn)楸娝苤瑖宓木S度實(shí)在太大了，每一次落子都有幾百（棋盤(pán)19*19 大小）種可能。設(shè)想假如一盤(pán)棋要在幾百步之后得出勝負(fù)，會(huì)有多少種可能性，確實(shí)很難通過(guò)任何和窮舉法沾邊的算法解決。 這里就涉及如何有效地減少搜索空間這個(gè)核心問(wèn)題。這也是為什么一個(gè)下圍棋的問(wèn)題需要用到機(jī)器學(xué)習(xí)，因?yàn)闄C(jī)器學(xué)習(xí)可以讓你通過(guò)有限數(shù)據(jù)推測(cè)所有其他可能（類似一個(gè)插值過(guò)程）。 在讓機(jī)器做這件事之前先看看人是怎么做的。我們無(wú)時(shí)無(wú)刻不在決策，也面臨如何減少搜索空間的問(wèn)題。雖然人生有無(wú)限種可能，但大多數(shù)可能你連考慮都不會(huì)考慮。 我們?nèi)祟愑糜薮篮吐斆鳌⒑侠砼c不合理這些詞匯描述各種選擇的優(yōu)劣，并且大腦自動(dòng)屏蔽大部分不合理的解釋。你是如何得到這些答案的呢？第一個(gè)就是通過(guò)常年的試錯(cuò)來(lái)計(jì)算每個(gè)行為的結(jié)果，所謂一朝被蛇咬，十年怕井繩。另一個(gè)就是看書(shū)，和高手對(duì)話，直接學(xué)習(xí)他們的經(jīng)驗(yàn)。 反過(guò)來(lái)就是機(jī)器學(xué)習(xí)的原理，首先說(shuō)試錯(cuò)學(xué)習(xí)，或者根據(jù)某種行為最終導(dǎo)致的結(jié)果來(lái)調(diào)整行為策略的方法，我們通常稱之為強(qiáng)化學(xué)習(xí)。 強(qiáng)化學(xué)習(xí)如上圖，Agent 會(huì)根據(jù)環(huán)境給予的reward 調(diào)整action 的一個(gè)反饋系統(tǒng)，最終實(shí)現(xiàn)利益最大化，難點(diǎn)在于Agent 的行為通常會(huì)改變環(huán)境，而環(huán)境又會(huì)影響行為策略。 具體到圍棋上，這個(gè)策略的核心是根據(jù)圍棋的特性： （1）在每一步雙方信息完全已知； （2）每一步的策略只需考慮這一步的狀態(tài)。 這允許機(jī)器學(xué)習(xí)用一個(gè)非常兇猛的簡(jiǎn)化框架來(lái)解決這個(gè)問(wèn)題，即馬爾科夫決策過(guò)程。也就是說(shuō)，我們用一個(gè)離散的時(shí)間序列來(lái)表述狀態(tài)s，用另一個(gè)離散的時(shí)間序列表述行為a，兩個(gè)時(shí)間序列有著深刻的耦合關(guān)系，下一刻的狀態(tài)s(t+1)取決于此刻行為a(t)和狀態(tài)s(t)，最終決定下一刻的行為a(t+1)。兩者間的關(guān)系即策略P(a(t)|s(t))，由于是馬爾科夫鏈，所以每一時(shí)刻的策略只與此刻狀態(tài)s(t)有關(guān)。各種棋類就是最明顯的馬爾科夫鏈。由于未來(lái)存在不確定性，因此策略本身也是一個(gè)概率分布函數(shù)的形式。最終我們要優(yōu)化，使得P(s|a)所得到的回報(bào)R(s)最大。馬爾科夫決策過(guò)程是在解決未來(lái)狀態(tài)不確定而行為和狀態(tài)又具有馬氏性時(shí)十分有利的方法。 解決馬爾科夫決策過(guò)程的一個(gè)簡(jiǎn)單實(shí)用的算法叫作蒙特卡洛樹(shù)搜索（MCTS），如下圖。 上圖描述了蒙特卡洛樹(shù)與它的四個(gè)步驟：選擇、擴(kuò)張、模擬估值和結(jié)果回傳，對(duì)應(yīng)一個(gè)經(jīng)典的強(qiáng)化學(xué)習(xí)框架。 蒙特卡洛是大名鼎鼎的隨機(jī)抽樣方法。提到樹(shù)，大家一定可以想到?jīng)Q策樹(shù)，樹(shù)的節(jié)點(diǎn)是某一刻的狀態(tài)，枝杈代表一個(gè)決策。而這里的蒙特卡洛樹(shù)，就是用隨機(jī)抽樣的方法生成整個(gè)決策樹(shù)的過(guò)程。 假設(shè)電腦現(xiàn)在的狀態(tài)是s(t)，那么你隨便扔個(gè)骰子走一步，然后電腦模擬的對(duì)手也扔個(gè)骰子隨便走一步，這樣下去，總有一刻會(huì)分出勝負(fù)，這個(gè)時(shí)候你回顧勝利和失敗的人的歷史走棋軌跡，贏的走法在其整個(gè)決策樹(shù)上的每個(gè)狀態(tài)（枝葉）都加一分，輸?shù)淖叻恳徊轿恢枚紲p一分，這個(gè)分?jǐn)?shù)會(huì)影響下一次抽樣的概率，使得容易贏的步子會(huì)有更大概率取到。玩無(wú)數(shù)次后，就會(huì)選擇出特別容易贏的策略。這個(gè)過(guò)程酷似進(jìn)化選擇算法，就是讓那些有優(yōu)勢(shì)的選擇有更高的繁殖子代概率，從而最終勝出，體現(xiàn)了生物和環(huán)境的博弈。
以蒙特卡洛樹(shù)為代表的強(qiáng)化學(xué)習(xí)在圍棋這種走法可能性超多的情況下，只能部分地減少搜索空間，使得電腦達(dá)到一個(gè)高級(jí)業(yè)余選手的水平，而如果要進(jìn)一步減少搜索空間，應(yīng)該怎么辦呢？人類減少搜索空間的一個(gè)重要方法是學(xué)習(xí)高手經(jīng)驗(yàn)，背棋譜，看得多了，就有一種犀利的直覺(jué)走出一個(gè)妙招。轉(zhuǎn)化為數(shù)學(xué)語(yǔ)言，就是通過(guò)看棋譜，取得一個(gè)在某種局面下任意策略和最終贏率的對(duì)應(yīng)關(guān)系，即使這個(gè)局面你從未見(jiàn)過(guò)。
讓機(jī)器來(lái)做就是有監(jiān)督學(xué)習(xí)的回歸算法，你要提取棋局的特征，算出對(duì)應(yīng)每一個(gè)走法出現(xiàn)的概率P(a(t)|s(t))，然而圍棋棋局的特征實(shí)在太復(fù)雜，這時(shí)候我們的深度學(xué)習(xí)開(kāi)始派上用場(chǎng)，它可以自發(fā)地學(xué)習(xí)事物的表征。 機(jī)器學(xué)習(xí)訓(xùn)練的目標(biāo)是使得數(shù)據(jù)被觀測(cè)到的概率最大， 所謂MaximumLikelihood，對(duì)于神經(jīng)網(wǎng)絡(luò)，就是網(wǎng)絡(luò)連接參數(shù)的調(diào)整。 深度學(xué)習(xí)的過(guò)程正如同我們見(jiàn)識(shí)一個(gè)東西多了，自發(fā)地開(kāi)始具有舉一反三的能力，自然而然地把直覺(jué)加入了策略選擇，這時(shí)候你可以通過(guò)有限的經(jīng)驗(yàn)把握無(wú)限。在訓(xùn)練過(guò)程中，AlphaGo 不停地根據(jù)現(xiàn)有的局面預(yù)測(cè)專家可能會(huì)出的招，在經(jīng)過(guò)三千萬(wàn)組數(shù)據(jù)的訓(xùn)練后，深度學(xué)習(xí)可以達(dá)到55.7%的預(yù)測(cè)率，這個(gè)概率說(shuō)明人類的意圖也并不難被猜中，這也是很多人說(shuō)和AlphaGo 下棋如同和無(wú)數(shù)高手過(guò)招的原因。當(dāng)然，這還不是訓(xùn)練的終結(jié)，此處的神經(jīng)網(wǎng)絡(luò)只是在描摹高手的動(dòng)作，而之后我們要讓它能贏，好比在實(shí)踐中理解和優(yōu)化高手的招術(shù)，這就是訓(xùn)練的第二步，用強(qiáng)化學(xué)習(xí)方法，訓(xùn)練網(wǎng)絡(luò)連接系數(shù)，具體方法是讓現(xiàn)有的策略網(wǎng)絡(luò)和隨機(jī)選出的一個(gè)之前的策略網(wǎng)絡(luò)進(jìn)行左右互搏，然后把勝負(fù)結(jié)果回傳到每一步的策略上，進(jìn)行梯度訓(xùn)練。經(jīng)過(guò)這個(gè)過(guò)程，策略網(wǎng)絡(luò)可以成功戰(zhàn)勝一些中級(jí)愛(ài)好者水平的算法和自己之前在描摹各種高手時(shí)候的狀態(tài)。 策略網(wǎng)絡(luò)的思維是計(jì)算每種走法出現(xiàn)的概率。 訓(xùn)練的最后一步是估值網(wǎng)絡(luò)。估值網(wǎng)絡(luò)是做什么的呢？首先，在一個(gè)強(qiáng)化學(xué)習(xí)框架下，你需要知道每個(gè)行為所對(duì)應(yīng)的確定回報(bào)，難點(diǎn)在于圍棋是下完棋才有確定回報(bào)的，想想圍棋步驟中的無(wú)限多可能性以及得到結(jié)果可能的步數(shù)就令人生畏，此處深度學(xué)習(xí)算法的作用正是不需要走完就巧妙地估計(jì)出這一步對(duì)應(yīng)的盈利期望，過(guò)程需要用一個(gè)深度網(wǎng)絡(luò)通過(guò)強(qiáng)化學(xué)習(xí)的框架來(lái)進(jìn)行。估值網(wǎng)絡(luò)的本質(zhì)在于建立現(xiàn)有行為和長(zhǎng)遠(yuǎn)收益的聯(lián)系，有人稱之為看趨勢(shì)和全局觀。 公式如下，訓(xùn)練要解決的問(wèn)題是，求得狀態(tài)S 下采取策略p 的最終收益。 估值網(wǎng)絡(luò)的效果圖如下。 那么問(wèn)題來(lái)了，蒙特卡洛樹(shù)和深度學(xué)習(xí)兩者是如何天衣無(wú)縫地結(jié)合起來(lái)的呢？這就是整個(gè)AlphaGo 設(shè)計(jì)最巧妙的地方。首先蒙特卡洛樹(shù)可以拆解為4 步： 第一步，Selection，在已有的選項(xiàng)（經(jīng)歷過(guò)的）中進(jìn)行抽樣選擇。 第二步，Expansion，走到一個(gè)先前從未經(jīng)歷的局面上，探索新行為，即生成新的枝杈。 第三步，Evaluation，得到新行為的回報(bào)。 第四步，Backup，把回報(bào)的結(jié)果反向傳遞給策略。深度學(xué)習(xí)的結(jié)果可以被非常完美地嵌入蒙特卡洛搜索的步驟里，首先，在Expansion 的階段，我們不用從零開(kāi)始隨機(jī)生成一個(gè)前所未有的狀態(tài)，而是根據(jù)前人經(jīng)驗(yàn)訓(xùn)練的策略網(wǎng)絡(luò)直接生成新?tīng)顟B(tài)，海量減小了無(wú)用的搜索。然后，在Evaluation 步驟，我們無(wú)須跑完整個(gè)比賽，而是通過(guò)深度學(xué)習(xí)的結(jié)果直接算出這個(gè)新舉措可能的回報(bào)（此處即估值網(wǎng)絡(luò)的作用），這個(gè)計(jì)算出的回報(bào)，會(huì)在最終游戲完成的時(shí)候與真正的結(jié)果相結(jié)合，從而完成學(xué)習(xí)的步驟。 深度學(xué)習(xí)嵌入蒙特卡洛樹(shù)搜索的方法如下。 與戰(zhàn)勝國(guó)際象棋大師的深藍(lán)不同，在AlphaGo 這里，機(jī)器學(xué)習(xí)發(fā)揮了巨大的作用，因?yàn)锳lphaGo 的策略和智能主要是在不停地看棋譜和左右互搏中進(jìn)化出來(lái)的，對(duì)于圍棋這樣規(guī)則非常復(fù)雜的東西，設(shè)計(jì)一套必勝規(guī)則幾無(wú)可能，只有機(jī)器學(xué)習(xí)（強(qiáng)化學(xué)習(xí)）的進(jìn)化和自我改進(jìn)思想才是最終取勝的法器。因此AlphaGo 的技術(shù)對(duì)其他人工智能非常有啟發(fā)。 從整個(gè)解析來(lái)看，其實(shí)訓(xùn)練AlphaGo 的算法思路并不十分復(fù)雜，用一句話總結(jié)，就是站在巨人的肩膀上迅速試錯(cuò)。這可能也是各種人生決策的最好方法吧。然而，我們?nèi)祟悰](méi)有那么多時(shí)間玩Simulation，也沒(méi)有那么多GPU 進(jìn)行并行運(yùn)算，所以我們其實(shí)尋找的是低搜索成本的近似解，謂之次優(yōu)解。 本文選自《機(jī)器學(xué)習(xí)vs復(fù)雜系統(tǒng)》一書(shū)，作者許鐵，電子工業(yè)化版社2018年8月出版。 這是一本有關(guān)人工智能、機(jī)器學(xué)習(xí)、深度學(xué)習(xí)、復(fù)雜系統(tǒng)的科普讀物，本書(shū)從跨學(xué)科視角來(lái)看待人工智能這個(gè)技術(shù)性的學(xué)科。圍繞用數(shù)學(xué)模型預(yù)測(cè)未來(lái)這一主題，介紹算法，主要包括現(xiàn)在流行的機(jī)器學(xué)習(xí)和深度學(xué)習(xí)算法，以及算法要解決問(wèn)題本身的復(fù)雜性。復(fù)雜的問(wèn)題，需要復(fù)雜的算法，而算法設(shè)計(jì)背后的老師正是自然界的復(fù)雜性本身。 |
|
|
