阿爾法狗怎麼用機器學習做決策：馬爾科夫鍊減少搜尋空間說起(附PDF公号發“馬鍊搜尋”下載下傳)
以色列理工Dr許鐵 資料簡化DataSimp 今天
資料簡化DataSimp導讀：AlphGo下棋核心技術5千字短文，來自以色列理工大學許鐵博士混沌巡洋艦2016-09-18首發《阿爾法狗是怎麼用機器學習做決策的》，作為了解AlphaGo論文的知識基礎之一。下篇推出本公号創立首篇論文《AlphaGo算法論文《精通圍棋博弈的深層神經網絡和樹搜尋算法》漢譯(《自然》nature16961原文翻譯，機器學習經典)》新修訂的中英文對照版本。公号輸入框回複關鍵字，可下載下傳本文PDF。
阿爾法狗怎麼用機器學習做決策：馬爾科夫鍊減少搜尋空間說起(5263字)
目錄
B 阿爾法狗是怎麼用機器學習做決策的(4151字)
1.傳統棋類遊戲算法之窮舉法
2.圍棋遊戲算法之馬爾科夫決策法
3.蒙特卡洛樹和深度學習無縫結合解決圍棋問題
參考文獻(609字)Appx(1236字).資料簡化DataSimp社群簡介
資料DataSimp社群分享：資訊與資料處理分析、資料科學研究前沿、資料資源現狀和資料簡化基礎的科學知識、技術應用、産業活動、人物機構等資訊。歡迎大家參與投稿，為資料科學技術做貢獻，使國人盡快提高資料能力，提高社會資訊流通效率。做事要平台，思路要跟進；止步吃住行，無力推文明。要推進人類文明，不可止步于敲門呐喊；設計空想太多，無法實作就虛度一生；工程能力至關重要，秦隴紀與君共勉之。
B 阿爾法狗是怎麼用機器學習做決策的(4151字)
阿爾法狗是怎麼用機器學習做決策的
文|許鐵，源|混沌巡洋艦2016-09-18；資料簡化DataSimp©20190104Fri
阿爾法狗這個被大家熱議過很久的主題，裡面其實包含了非常深刻的機器學習智慧。是一部學習機器學習甚至是人類決策的絕好教材。機器學習是Alphago取勝的關鍵，為什麼它會發揮巨大作用，請看下文。
了解一門科學技術最好的方法就是找出其核心論文，讓我們看看阿法狗的核心論文是怎麼解讀這個問題的。以及如果把你放在這樣一個位置，會如何設計這盤遊戲。
1.傳統棋類遊戲算法之窮舉法
1.1 窮舉法解決八皇後問題
如果大家了解棋牌類遊戲以及電腦與之對弈的曆史，則會非常清楚老派程式員的套路，那就會明白這類問題最簡單的辦法就是窮舉法，比如曆史著名的八皇後問題，你需要在國際象棋棋盤上擺放八個皇後，而使得她們各自不位于對方的縱線，橫線或對角線上，你隻需要按照一定的方法做一個循環，從第一排往下一排周遊，當你碰見擺不開的情形，就回到上一步最終重新擺，最後總可以把沒有問題的組合求出來。
圖1：八皇後，窮盡并知難而退就夠了，八個女人也不難安排
1.2 圍棋盤面無法窮舉
與之類似的方法稍作改進可以很好的解決國際象棋的問題，卻難以做到解決圍棋的問題，為什麼？因為衆所周知的，圍棋的次元實在太大了，每一次落子都有幾百(棋盤19*19大小)種可能，設想假如一盤棋要在幾百步之後得出勝負，你有多少種可能性，确實很難通過任何和窮舉法沾邊的算法解決掉。
這裡就涉及如何有效的減少搜尋空間，這個核心問題。這也是為什麼一個下圍棋的問題需要用到機器學習的關鍵，因為機器學習讓你通過有限資料推測所有其他可能(類似一個插值過程)。
要讓機器做這個事先看看人是怎麼做的，其實決策的核心就是如何減少搜尋空間的問題。雖然人生的可能在一定程度是無限的，但大多數可能你連考慮都不會考慮，比如去北韓移民或到孟加拉國賣香蕉。我們人類用愚蠢，聰明，合理，不合理這些詞彙描述各種選擇的優劣，并且大腦自動屏蔽大部分不合理的解釋。你是如何得到這些答案的呢？第一個就是如何通過常年的試錯來計算每個行為的結果，所謂一朝被蛇咬，十年怕井繩。另一個就是看書，和高手對話直接學習它們的經驗。
反過來就是機器學習的原理，首先說試錯學習，或者根據某種行為最終導緻的結果來調整行為政策的方法，我們通常稱之為強化學習。
圖2：強化學習通常用如上框圖實作，即agent會根據環境給與的reward調整action的一個回報系統，最終實作利益最大化，難點在于agent的行為通常改變環境，而環境影響行為政策。
2.圍棋遊戲算法之馬爾科夫決策法
而具體到圍棋上，這個政策的核心是根據圍棋的特性：
1.在每一步雙方資訊完全已知
2.每一步的政策隻需考慮這一步的狀态
這允許機器學習用一個非常兇猛的簡化架構來解決這個問題，馬爾科夫決策過程。也即是說我們用一個離散的時間序列來表述狀态s，另一個離散的時間序清單述行為a，兩個時間序列有着深刻的耦合關系，下一刻的狀态s(t+1)取決于此刻行為a(t)和狀态s(t)，最終決定下一刻的行為a(t+1)兩者間的關系即政策P(a(t)|s(t))，由于是馬爾科夫鍊，是以每一時刻的政策隻與此刻狀态s(t)有關。
2.1 馬鍊決策過程的機率分布函數優化
各種棋類就是最明顯的馬鍊。由于未來存在不确定性，政策本身也是一個機率分布函數的形式。最終我們要優化采取P(s|a)所得到的回報R(s)最大。馬爾科夫決策過程是在解決未來狀态不确定而狀态和行為又具有馬氏性時十分有利的方法。
解決馬爾科夫決策過程的一個簡單實用粗暴的算法叫做蒙特卡洛樹搜尋(MCTS)。
圖3：蒙特卡洛樹與它的四個步驟，選擇，擴張，模拟估值和結果回傳，對應一個經典的強化學習架構
說到蒙特卡洛，這是大名鼎鼎的随機抽樣方法。所謂樹，大家一定可以想到決策樹，樹的節點是某一刻的狀态，而枝杈代表一個決策，而這裡的蒙特卡洛樹，即用随機抽樣的方法生成整個決策樹的過程。
假設電腦現在的狀态是s(t)，那麼你随便扔個篩子走一步，然後電腦模拟的對手也扔個篩子随便走一步，這樣下下去，總有一刻會分出勝負，這個時候你回顧勝利和失敗的人的曆史走棋軌迹，赢的走法在其整個決策樹上的每個狀态(枝葉)都加一分，輸的走法每一步位置都減一分，這個分數會影響下一次抽樣的機率，使得容易赢的步子會有更大機率取到。最終依次往複電腦和電腦玩無數次後，就會選擇出特别容易赢的政策。這個過程酷似進化選擇算法，就是讓那些有優勢的選擇有更高的繁殖子代機率，進而最終勝出，展現了生物和環境的博弈。
注：這裡提個小問題，馬爾科夫決策過程威力巨大，而在現實決策裡，你要去哪個大學上學，你要選哪個股票，都的政策選擇都很難隻看當下，這個架構還能用多少呢？
2.2 馬鍊決策的監督學習回歸優化
以蒙特卡洛樹為代表的強化學習在圍棋這樣走法的可能性超多的情況下，隻能部分的減少搜尋空間，使得電腦達到一個進階業餘選手的水準，而如果我們要進一步減少搜尋空間，需要怎麼辦呢?此時我們可以再回去想剛提到的人類減少搜尋空間的一個重要方法是學習高手經驗，對，沒錯，背棋譜，看的多了，就有一種犀利的直覺走出一個妙招。轉化為數學語言，就是通過看棋譜，取得一個在某種局面下任意政策和最終赢率的對應關系，即使這個局面你從未見過。
注：此處小心我們經常會覺得直覺這個東西好像是天上掉下來的異禀，實則恰相反。直覺才是最需要學習的。
讓機器來做就是有監督學習的回歸算法，你要提取棋局的特征，算出對應每一個走法出現的機率P(a(t)|s(t))，然而圍棋棋局的特征實在太複雜，如果你來一個線性回歸或KNN，一定會死的很慘。這時候我們的深度學習開始派上用場。它可以自發的學習事物的表征。
圖4：通過梯度回傳訓練網絡連接配接
機器學習訓練的目标即使得資料被觀測到的機率最大，所謂Maximum Likelihood，對于神經網絡，就是網絡連接配接參數的調整。
深度學習的過程正如同我們見識一個東西多了，自發的開始具有舉一反三能力，因之可以稱為把直覺加入了政策選擇，這時候你可以通過有限的經驗把握無限。在訓練過程中，Alphago不停的根據現有的局面預測專家可能會出的招，在經過三千萬組資料的訓練後，深度學習可以達到55.7%的預測率，這個機率說明人類的意圖也并不難被猜中，也是為什麼人會說和Alphago下棋如同和無數高手過招。當然，這還不是訓練的終結，此處的神經網絡隻在描摹高手的動作，而之後我們要讓他能夠赢，好比在實踐中了解和優化高手的招術，這就是訓練的第二步，用強化學習方法，訓練網絡連接配接系數，具體方法即讓現有的政策網絡和随機選出一個之前的政策網絡進行左右互搏，然後把勝負結果回傳到每一步的政策上，進行梯度訓練。經過這個過程，政策網絡可以秒掉一些中級愛好者水準的算法和自己之前在描摹各種高手時候的狀态。
圖6：政策網絡的思維，計算每種走法出現的機率
訓練的最後一步是估值網絡，說說這裡估值網絡是幹什麼的，首先，在一個強化學習架構下，你需要知道每個行為所對應的确定回報，難點在于圍棋下完棋才有确定回報，想想圍棋步驟中的無限多可能性及得到結果可能的步數就令人生畏，此處深度學習算法的作用正是不需要走完就巧妙的估計出這一步對應的赢利期望，過程需要用一個深度網絡通過強化學習的架構來進行。估值網絡的本質在于建立現有行為和長遠收益的聯系。有人稱為看趨勢和全局觀。訓練這樣一個計算回報的網絡作用請往下看。
圖8：訓練要解決的問題，求得狀态S下采取政策p最終收益的期望公式
圖9：估值網絡的效果圖，數字即回報
3.蒙特卡洛樹和深度學習無縫結合解決圍棋問題
那麼問題來了，蒙特卡洛樹和深度學習兩者如何天衣無縫的結合起來呢？這就是整個Alphago設計最巧妙的地方：首先，你應該還記得MCTS的架構，首先MCTS可以拆解為4步：第一selection，在已有的選項(經曆過的)中進行抽樣選擇，第二expansion，走到一個沒有先前從未經曆的局面上，探索新行為，即生成新的枝杈，第三Evaluation，得到新行為的回報，第四，回傳，把回報的結果反向傳遞給政策。深度學習的結果可以被非常完美的嵌入到蒙特卡洛搜尋的步驟裡，首先在expansion的步驟，我們不用從零開始随機的生成一個前所未有的狀态，而是用根據前人經驗訓練的政策網絡直接生成新狀态，海量了減小了無用的搜尋。然後，在Evaluation的步驟上，我們可以不需要跑完整個比賽，而是通過深度學習的結果直接算出這個新姿勢可能的長期回報(此處即估值網絡的巨大作用，所謂步步看清n久之後的影響)，這個計算出的回報，會在最終遊戲完成的時候與真正實踐的結果相結合完成學習的步驟。
圖10：深度學習如何嵌入蒙特卡洛樹搜尋
與戰勝國際象棋大師的深藍不同，在Alphago的情形下機器學習發揮了巨大的作用，因為Alphago的政策和智能主要是在不停看棋譜和左右互搏中進化出來的，對于圍棋這樣規則非常複雜的東西，設計一套必勝規則幾無可能，也隻有機器學習(強化學習)的進化和自我改進思想才是最終取勝之法器。也是為什麼Alphago的技術對其它人工智能非常有啟發。
從整個上面的解析看來，其實訓練Alphago的算法思路并非十分複雜，用一句話總結，就是在巨人的肩膀上迅速試錯。這也是各種人生決策的最好辦法吧。你說你要活獨一無二的人生不模拟任何人，你估計是個撞南牆的傻X，你說你要就看着最牛逼的精英跟着走，你可能一輩子重複别人的生活。而牛X的人，顯然是站在巨人的肩膀上，邊描摹那三千萬精英的步法，并深度總結其規律，然後在變化自己的動作花樣。然而我們人類沒有那麼多時間完simulation，也沒有那麼多GPU進行并行運算，是以我們其實在找的是低搜尋成本的近似解，謂之次優解。
(注：本文由許鐵博士授權資料簡化社群(公衆号：資料簡化DataSimp)釋出，轉載請聯系作者微信号562763765。混沌巡洋艦創始人許鐵，法國巴黎高師實體碩士，以色列理工大學(以色列85%科技創業人才的搖籃，計算機科學享譽全球)計算神經科學博士，巡洋艦科技有限公司創始人，曾在香港浸會大學非線性科學中心工作一年。)
轉載本公号文章請注明作者、出處、時間等資訊，如“此文轉自©微信公号：資料簡化DataSimp，作者：秦隴紀等，時間：2016.3.15Tue譯編。”字樣，詳情郵件咨詢[email protected]，轉載請保留本資訊。本公号文章保留一切權利，如有引文/譯注/出處不明或遺漏、版權問題等，請給公号回複消息留言，或發郵件到[email protected]。歡迎資料科學和人工智能學界、産業界同仁賜稿，投稿郵箱[email protected]，範圍：AI/語言處理/資料/智能等科學技術論文。
免責說明：以上内容來自混沌巡洋艦媒體文章，已獲作者授權。文章隻為學術新聞資訊傳播，注明出處文字參考文獻可溯源。本公衆号不持有任何傾向性，亦不表示認可其觀點或其所述。
改革開放40周年，謹向改革者緻敬。我國教育太粗淺落後，文字化基礎教育應該縮減到十年内，應該全民普及大學教育，發展研究和合作教育。書從何來、讀書做甚？應反思并校正當今社會脫離低層、權力黑箱、資訊封閉、泛管教化、毫無民主、閹割人性之弊。秦隴紀提議開學後9月10日設定學習節，号召溫故知新、終身學習；9月28日孔子陽曆誕辰設為教師節，号召全人類樹立溫故知新素養；整個9月份定位公民學習月，加強傳統、文藝、科技、産品、時事的知識學習。十一國慶節後，設定國情宣傳周、選舉人演講周、投票選舉月，十月份定位國家公民月。全年做生活實踐、校園實驗、社會實習，文化輔之；3-9月份則以感受、認知、實踐、實驗、協作、實習為主。
—END—
參考文獻(609字)
1. 譯者：資料精簡DataSimp英譯組秦隴紀等，來源：自然(英國期刊)．AlphaGo算法論文《精通圍棋博弈的深層神經網絡和樹搜尋算法》漢譯(《自然》nature16961原文翻譯，機器學習經典)．[EB/OL]；資料簡化．https://weixin.qq.com/，2016-03-16，通路日期：2019-01-04．
2. 許鐵，來源：混沌巡洋艦．阿爾法狗是怎麼用機器學習做決策的．[EB/OL]；雷鋒網，https://www.leiphone.com/news/201609/kilC8EBaAhUMCNh8.html，2016-09-18，通路日期：2019-01-04．
3. 譯者：秦隴紀，來源：自然(英國期刊)．中英AlphaGo論文：精通圍棋博弈的深層神經網絡和樹搜尋算法．[EB/OL]；資料簡化．https://weixin.qq.com/，2019-01-05，通路日期：2019-01-04．
x.秦隴紀．資料簡化社群Python官網Web架構概述；資料簡化社群2018年全球資料庫總結及18種主流資料庫介紹；資料科學與大資料技術專業概論；人工智能研究現狀及教育應用；資訊社會的資料資源概論；純文字資料溯源與簡化之神經網絡訓練；大資料簡化之技術體系．[EB/OL]；資料簡化DataSimp(微信公衆号)，http://www.datasimp.org，2017-06-06．
阿爾法狗怎麼用機器學習做決策：馬爾科夫鍊減少搜尋空間說起(5263字)
(标題下「資料簡化DataSimp」文字連結，點選後繼續點“關注”接收推送)
秦隴紀©2010-2019資料簡化DataSimp
簡介：阿爾法狗怎麼用機器學習做決策：馬爾科夫鍊減少搜尋空間說起。作者：許鐵，法國巴黎高師實體碩士，以色列理工大學(以色列85%科技創業人才搖籃、計算機科學享譽全球)計算神經科學博士，巡洋艦科技有限公司創始人，香港浸會大學非線性科學中心工作一年。來源：混沌巡洋艦2016-09-18首發文章《阿爾法狗是怎麼用機器學習做決策的》/許鐵授權/資料簡化社群/秦隴紀微信群聊公衆号，參考文獻附引文出處。公号輸入欄回複關鍵字“馬鍊搜尋”或文末連結“閱讀原文”可下載下傳本文8k字10圖8頁PDF資料；标題下藍連結“資料簡化DataSimp”關注後，菜單項有文章分類頁。
主編譯者：秦隴紀，資料簡化DataSimp/科學Sciences/知識簡化新媒體創立者，資料簡化社群創始人，資料簡化OS設計師/架構師，ASM/Cs/Java/Python/Prolog程式員，英語/設計/IT教師。每天大量中英文閱讀/設計開發調試/文章彙譯編簡化，時間精力人力有限，歡迎支援加入社群。版權聲明：科普文章僅供學習研究，公開資料©版權歸原作者，請勿用于商業非法目的。秦隴紀2018資料簡化DataSimp綜合彙譯編，投稿合作、轉載授權/侵權、原文引文錯誤等請聯系[email protected]溝通。社群媒體：“資料簡化DataSimp、科學Sciences、知識簡化”新媒體聚集專業領域一線研究員；研究技術時也傳播知識、專業視角解釋和普及科學現象和原理，展現自然社會生活之科學面。秦隴紀發起，期待您參與各領域；歡迎分享、贊賞、支援科普~~
Appx(1236字).資料簡化DataSimp社群簡介
資訊社會之資料、資訊、知識、理論持續累積，遠超個人認知學習的時間、精力和能力。必須行動起來，解決這個問題。應對大資料時代的資料爆炸、資訊爆炸、知識爆炸，解決之道重在資料簡化(Data Simplification)：簡化減少知識、媒體、社交資料，使資訊、資料、知識越來越簡單，符合人與裝置的負荷。(秦隴紀，2010)
資料簡化DataSimp年度會議(DS2010-2019)，聚焦資料簡化技術(Data Simplification Techniques)：對各類資料從采集、處理、存儲、閱讀、分析、邏輯、形式等方面做簡化，應用于資訊及資料系統、知識工程、各類資料庫、實體空間表征、生物醫學資料，數學統計、自然語言處理、機器學習技術、人工智能等領域。歡迎資料科學技術、簡化執行個體相關論文投稿加入資料簡化社群，參加會議出版專著。請投會員郵箱[email protected]，詳情通路社群網站www.datasimp.org。填寫申請表加入資料簡化DataSimp社群成員，應至少有一篇資料智能、程式設計開發IT文章：①原創資料智能科技論文；②資料智能工程技術開源程式代碼；③翻譯美歐資料智能科技論文；④社群網站發帖人管理者版主志願者義工；⑤完善黑白靜态和三彩色動态社群S圈型LOGO圖示。DataSimplification/Sciences/Knowledge Simplification Public Accounts——[email protected], 2018.12.12Wed,Xi'an, Shaanxi, China.
LIFE
Lifebegins at the end of your comfort zone.——Neale Donald Walsch
THEDAY
Thestrength of purpose and the clarity of your vision，alongwith the tenacity to pursue it，is your underlying driver ofsuccess.——Ragy Tomas
投稿QQ群223518938資料簡化DataSimp社群；技術公衆号“資料簡化DataSimp”留言，或(備注：姓名/機關-職務/學校-專業/手機号)加微信賬号QinlongGEcai，進“資料簡化DataSimp社群”投稿群或“科學Sciences學術文獻”讀者群等群聊。關注如下三個公衆号(搜名稱也行)，關注後底部菜單有文章分類頁連結。
資料技術公衆号“資料簡化DataSimp”：
科普公衆号“科學Sciences”：
社會教育知識公衆号“知識簡化”：
(轉載請寫出處：©資料簡化DataSimp2010-2018彙譯編，歡迎技術、傳媒夥伴投稿、加入資料簡化社群！“資料簡化DataSimp、科學Sciences、知識簡化”投稿回報郵箱[email protected]。)
普及科學知識，分享到朋友圈
轉發/留言/打賞後“閱讀原文”下載下傳PDF
閱讀原文
微信掃一掃
關注該公衆号