Re: [心得] 圍棋AI AlphaGo 之我見

看板GO作者kafai (豬仔包 PigSonBow)時間8年前 (2016/03/14 13:17)推噓9(9推 0噓 59→)

留言68則, 11人參與討論串3/6 (看更多)

感謝f大的發文，我也是長知識了我得再次承認我對NN的理解太膚淺，這是我做得不好的一方面是因為我是做RFIC的，我沒那個能力時間把 NN 和 MCTS 的結合寫得精確 (我就只是在一月ASP-DAC做了 turorial 的 chair 聽了一整天NN，和看了那份 Nature 寫這篇也參考了那個台大資工教授的文章) 另一方面是由於我所寫的出發點是在，我希望借助我有的圍棋知識和我比較熟知的 MCS 還有一些對於 AyaBot 的經驗，去推估 AlphaGo(AG) 的可能弱點而不是要告訴人 NN 如何在 AG 發揮作用，所以引出你這篇好文啊 XD 只是我不能同意 NN 是 AG 強的關鍵，因為 NN 和 MCTS 是一起配合的，只有一方的情況下，過去的經驗會告訴你它會弱很多只有 NN 的話可以想像有可能發生，在第一局第7手下出未見過的佈局， AG 下一手就開始不會下，然後脆敗我知道 NN 是協助 MCTS 更有效率地找出最佳解 (類似 MC 跟 MCMC 的分別) 用圍棋的話來說，NN 相當於一個形勢判斷 + 一個不強的算路 (相當於棋手第一感) MCTS 就是在 NN 的協助下加強算路的能力，其實跟棋手的思維模式是很接近的那麼我將 NN 的助益完全算進 MCTS 的 sims 數提高，去估算 AG 的算路深度是合理的第四盤我看完圍棋TV張東岳的講法，我會說如果 78手是勝著，那麼 35手虎就是敗著，沒有虎而是黏，後面就不會有78了也就是我上篇估計的三四十手算路當然由於它有 MCTS 的關係，它在沒改 code 的情況下，遇到同樣的 78手，它有可能會平安運轉我的看法是 Google 太小看李世石，如果1000台 server 增到2000台，說不定就夠了有人可能說 distributed 版跟單機版的勝率才77%，但從十番棋的角度3勝1敗已經接近把對方打降級了) 從兩個現象看來，你不能抹殺 MCTS 的作用 1. 第二局的那個五路肩衝，那大概不是 NN 提供的優先選擇吧，非得 MCTS 掃出來當然五路肩衝在職業譜也不會沒有，我記憶中武宮有五五肩衝星位的棋吧，那更是對兩邊來說都是五路肩衝，最近的棋也好像有吧，不過沒有在佈局的那麼早段下而是其他很多地方都定型後再肩衝五路的場合下法但樣本數少到單用 NN 是不可能建議你去下這種棋的，但那個小機率權重讓它能在 MCTS 中脫穎而出 2. 昨天敗定後，AG 下出很多到無禮程度的業餘下法，那也是 MCTS 的「功勞」它相當於下出很俗的打將式絕對先手，然後期望對方氣合脫先，從而得益這在機率上就說得通了，但在下得很業餘這個點上，它就變成丟下 NN 的 AI 了 ------- 至於你驚訝 ML 會輸給人類的話，正如我上面所講，Google 太小看李世石了而且你可能有點陷入 optimal 的迷思了那些 LS、LMS(MMSE) 或是你想用 SVD 去除掉一些 sigular value 很小的 mode 那樣的 optimum point，我的看法是出來會是 training sequence 的(加權)平均不可能會最好，更不可能更好大學專題玩過用 Kalman filter 去預估汐止那邊的車流，就是這種感覺 ※ 引述《fallcolor (秋天走了)》之銘言： : 想透過這篇文章順著介紹一下這次讓圍棋AI效能躍升的關鍵：機器學習(machine : learning)技術。當然現在大家對alphago的演算法背景都大致了解了，簡單說是類神經網 : 路(neural network)與蒙的卡羅樹狀搜尋(monte carlo tree search)的組合。不過如同 : 一些圍棋AI專家提到的，MCTS從2006就被應用於開發圍棋AI了，雖然帶來搜尋策略的大躍 : 進，卻還是有些盤面(例如打劫)難於處理。NN為alphago帶來的最大效益就是搜尋深度/廣 : 度/順序的優化，使MCTS得以在有限時間內對勝率較高的目標手展開樹狀預測。從這點來 : 看，理解alphago成功的關鍵是NN而不是MCTS，要如何破解alphago的關鍵也應該在此處。 : 而NN就是ML技術的其中一種，所以我想提供一點對ML的基礎認知。 : ML的廣義目的是從輸入資料中學習出有意義的pattern，要實現此目的的演算法種類很多 : ，但我想介紹的是比較主流的deterministic algorithm。這類演算法應用於ML上可以用 : 清楚的數學模型表達： : y = f(x; theta) ……(1) : 其中x是輸入資料，f()是需要事先定義的模型函數，theta是f()函數中的參數，y是你希 : 望f()函數輸出的預測值。當中theta是未知的，演算法目的就是希望根據給定的輸入資料 : x與輸出資料y自動決定theta，實踐的手段則是透過最小化模型預測結果與預期輸出之間 : 的誤差值: : Minimize | y – f(x;theta) |^2 …… (2) : 這個例子中選擇的誤差函數只是簡單的平方運算，此函數稱為目標函數，也是可以選擇的 : 。到此為止，機器學習其實只是一道數學問題，解決公式(2)需要用到的是數值最佳化 : (numerical optimization)技巧，但我也不打算從這個方向介紹下去。要理解ML的優缺點 : 應該從對數學的直觀理解出發。這麼說吧，先把公式(2)想像成一個簡單的聯立方程式求 : 解問題，如果我們有三組(x,y)資料(並且不是線性相依)，而未知數theta個數也是3，基 : 礎數學告訴我們恰好有唯一解。若未知數theta個數小於3，此時找不到任何解滿足三組方 : 程式了，但我們可以找到一個使誤差值最小的解。若未知數大於3，我們則可以找到無限 : 多解。 : 為什麼要複習這麼簡單的數學概念呢？因為這裡面其實解釋了ML的所有困難與迷人之處。 : 如果你對資料假設的ML模型很簡單，也就是說theta個數少，換言之f()函數無法滿足太大 : 資料量，我們就會說這模型對資料的泛化(generalization)能力差。若相反，f()函數很 : 複雜，theta個數多到比輸入資料多，意味著你可以找到無限多theta滿足所有訓練資料。 : 但很不幸它們對演算法而言又都一樣，此時就容易掉進local optimum，我們就會說這模 : 型過度擬合(overfitting)了。 : 到此為止，大家可以思考看看如果你是一個ML的研究者，你會傾向選擇一個簡單但泛化能 : 力普通的模型還是一個複雜卻容易找到wrong optimum的模型呢？相信有志氣的各位一定 : 是選擇後者吧。但現實情況是，十年以前的這個領域人們寧願選擇前者搭配其他技術當作 : ML的補丁。這當然有許多因素，包括以前的學術研究通常是在規模較小的資料庫上做驗證 : 就可以發論文了，也包括過去處理的ML問題並不複雜，最關鍵的或許是過去的最佳化技術 : 還沒成長到可以解決複雜模型下的最佳化問題，而對簡單模型卻幾乎保證可以找到 : global optimum。種種原因造成當時的學界有另外一種研究面向叫做特徵工程(feature : engineering)，它關注的是如何表示輸入資料x。這一派的研究者相信，透過domain : knowledge先對輸入資料設計比較好的特徵表示，而不是把原始資料赤裸裸地丟近模型裡 : 進行訓練，相當於很大的模型複雜度在這個步驟就解決掉了。基於這個理念十年前的ML其 : 實比較像feature extraction + model prediction的組合技，前者衍生出降維 : (dimension reduction)、特徵子(feature descriptor)等技巧，後者更是百家爭鳴，包 : 括logistic regression、support vector machine、decision tree、adaboosting，有 : 時候我贏你一點點，過陣子你又贏我一點點，不變的是誰也不能統一天下。除了以上還有 : 個比較特殊的派別叫做kernel machine，它的理念有點像是把兩步驟再次合二為一：假設 : x可以經過一個mapping轉換到無限維度，此時就可以把這個新表示法塞進模型裡並且以核 : 函數(kernel function)取代。……再往下說就離題了，不過因為kernel machine這概念 : 可以塞進許多ML模型，當時簡直掀起一波洗論文的熱潮，很有趣。 : 說了這麼多，可能有人想問，那尊爵不凡的NN呢？難道還沒被提出嗎？ : 其實正好相反，作為幾乎是最早的幾種ML模型之一，NN早在1980左右就被提出來了。雖然 : 我沒能躬逢其盛，但聽說1990初的ML領域幾乎是NN一統天下的時代，直到1995有位叫 : Vapnik的研究者提出SVM後才迅速沒落。NN的好處在於它的模型複雜度可以設計到非常高 : ，而對模型參數做最佳化的數學公式經過Hinton等人推導後也變得非常簡潔。然而它的缺 : 點同時出現：即使有了漂亮的最佳化公式，仍無法解決一旦模型複雜度過高就掉入local : optimum的問題，而且這個local optimum還通常很糟。於是，當SVM挾著「我有global : optimum」的口號橫空出世之後，NN就慢慢被喜新厭舊的研究者們淡忘了。所幸固執的 : Hinton沒有放棄，經過十年沉潛，在2006提出pre-training的技巧首次在工程意義上解決 : NN會overfitting的問題。或許為了重新出發，他這次為NN的學習技巧下了一個叫deep : learning的口號，甚至嗆聲與NN相比，那些SVM、boosting、tree什麼有的沒的模型都只 : 是shallow learning(…膚淺學習)。後面的事大家就比較熟悉了，學界捲起一股DL旋風， : google/FB/IBM/百度……等大公司紛紛投入可觀的資源研究，ML瞬間成為實現AI的希望， : 諸如此類。 : 當然NN在技術層面的故事並不只到此為止。過沒多久研究者就發現，原來只要灌大數據加 : 上對NN模型有一些合理的規範限制，連pre-training都不用做就可以升天啦。灌大數據這 : 件事在過去是難以想像的，然而仰賴計算機硬體效能一日千里總算可以實現；而對NN模型 : 採取合理規範這個概念，造就了convolutional NN、recursive NN等新式模型的興起，其 : 中CNN就是這次alphago使用的機器學習模型。另外研究者也對NN的最佳化演算法進行一些 : 工程方面的改良，使訓練過程更穩定、更不會掉到奇怪的解，也更可以提高模型的複雜度 : 。 : 看上去NN完美無瑕了，不過其中很重要的一點是，這些改良都是透過實驗數據的提升來支 : 持的，背後仍然缺乏優美的數學理論。也就是說，NN會掉到local optimum這件事是它與 : 身俱來的原罪，不管灌再大的數據、做各式各樣演算法補強，這件事永遠可能發生。於是 : 有些腦筋不正常的研究者開始找NN麻煩，他們試圖透過另外一套演算法找出一種輸入雜訊 : n，使得 : x ~= x+n (~=：約等於) : y != f(x+n) (!=：不等於) : 這個研究的目標當然也可以從善意的一面來理解：分析NN模型究竟會在何時預測失效，並 : 以此進行改良。相關資料我曾提供於之前的討論文章中，這邊就不重複了。於是我們終於 : 可以回到圍棋AI的問題，在介紹一堆ML的基礎認知後，人究竟要如何理解alphago前所未 : 有的成功呢？ : Alphago這次訓練出來的類神經網路模型，可以看待成是一個複雜度非常高、泛化能力強 : 、預測又穩定的數學函數f()。裡面的所有參數theta都是根據餵進去的棋譜以及相對應的 : 棋局勝負一筆一筆學習出來。這樣的模型可能已經非常接近完美了，但是請記住，回歸數 : 學本質時，它一定是不完美的。因為NN註定就是會在訓練過程中掉進local optimum，而 : 這個local optimum因為沒有完美地擬合圍棋遊戲這個決策的超平面(hyper-plane)，就必 : 然會在某一種輸入資料中發生預測失準的問題。經常看到板上有人質疑，是否alphago沒 : 看過的棋步它就無法應付？這句話從ML的角度來看是不對的，因為就算這個棋步alphago : 沒看過，若參數的泛化能力強到可以「合成」這一步棋，就還在模型的表示範圍之內。直 : 觀一點理解或許可以想像成函數的內插，即使輸入資料不在取樣資料內，但計算出來的函 : 數上的每一點都是可以透過取樣資料參數化後內插得到的。反之，若是需要外插才能表示 : 的資料點，就可能造成函數的預測錯誤。 : 所以今天李世石九段的勝利──神之一手78，從數學意義上來說可以簡單理解為製造了一 : 個模型函數的外插點，或是說製造了一筆想搞砸NN模型的研究者朝思暮想的x+n的資料， : 使得alphago終於無法泛化。在之前的文章中我很悲觀地認為這個n一定是得靠另外一套演 : 算法才能破解得到的。也就是說以一位ML愛好者而言，我認為只有ML演算法才能破解ML演 : 算法，沒有機會透過人類的智識歸納。想不到李九段今天立刻狠狠地打我的臉，心情實在 : 是很激動啊。坦白說對這次比賽的關心是很失敬的，因為我甚至不會下圍棋，只是對ML抱 : 著興趣就忍不住當了幾日棋迷，簡直有點蔑視圍棋了。然而這四場比賽下來對於李世石的 : 表現卻是真的打從心底十分動容，於是決定寫這篇文章。希望透過這篇介紹能讓喜歡圍棋 : 的人對ML稍有認識。ML並不神奇，說到底就是資料堆積出來的一個數學模型，因為它仍然 : 缺乏人最重要的邏輯思維與創作才華(我認為這不同於模型的泛化能力)，至少在現階段它 : 是遠遠不需要恐懼的，而是需要與人類的智慧互相參考與提升，一起進步下去。 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 161.64.208.174 ※ 文章網址: https://www.ptt.cc/bbs/GO/M.1457932651.A.322.html

推

AmibaGelos

03/14 13:22, , 1^F

03/14 13:22, 1^F

→

AmibaGelos

03/14 13:25, , 2^F

03/14 13:25, 2^F

推

aaaba

03/14 14:00, , 3^F

03/14 14:00, 3^F