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