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

看板GO作者時間8年前 (2016/03/13 21:53), 編輯推噓27(27推 0噓 32→)
留言59則, 30人參與, 最新討論串2/6 (看更多)
想透過這篇文章順著介紹一下這次讓圍棋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), 來自: 114.43.207.184 ※ 文章網址: https://www.ptt.cc/bbs/GO/M.1457877215.A.96C.html
推
03/13 21:54, , 1F
推～～
03/13 21:54, 1F
推
03/13 21:59, , 2F
推專業科普好文
03/13 21:59, 2F
推
03/13 22:02, , 3F
推科普好文! 概念超清楚! 但用字似乎仍有點難 XD
03/13 22:02, 3F
推
03/13 22:02, , 4F
專業推
03/13 22:02, 4F
→
03/13 22:03, , 5F
不知我是否可以這樣理解:
03/13 22:03, 5F
→
03/13 22:04, , 6F
以前的AI,是靠工程師在程式碼直接寫入接近正解的公式
03/13 22:04, 6F
推
03/13 22:04, , 7F
其實我感覺破解的重點不是NN，而是很弱的rollout policy
03/13 22:04, 7F
→
03/13 22:04, , 8F
但現在新的AI,則是靠程式自己去寫出那個接近正確的公式
03/13 22:04, 8F
→
03/13 22:05, , 9F
因此,重點不在我們是否知道那個正確公式的長相
03/13 22:05, 9F
→
03/13 22:06, , 10F
重點反而是在如何讓程式能自己寫出正確的公式
03/13 22:06, 10F
推
03/13 22:11, , 11F
推~
03/13 22:11, 11F
推
03/13 22:11, , 12F
學了很多 !
03/13 22:11, 12F
推
03/13 22:12, , 13F
棋譜就是座標，把無數棋譜fitting成一條方程式的fu吧
03/13 22:12, 13F
推
03/13 22:12, , 14F
推，圍棋九段的演算法除Bug能力真的很驚人，只是他靠的
03/13 22:12, 14F
→
03/13 22:13, , 15F
是過去對圍棋累積的經驗與那一點點的運氣
03/13 22:13, 15F
推
03/13 22:13, , 16F
推好文章,講local min.有點語病：有可能theta數量很少
03/13 22:13, 16F
→
03/13 22:14, , 17F
但f的形狀非常複雜(non-convex),使得opt alg沒辦法找到
03/13 22:14, 17F
→
03/13 22:14, , 18F
真正的最小值
03/13 22:14, 18F
→
03/13 22:14, , 19F
對於DL的成功有一說是在高維空間大多點都是saddle pt.
03/13 22:14, 19F
→
03/13 22:15, , 20F
所以SGD還是有辦法找到一個夠好的解
03/13 22:15, 20F
→
03/13 22:15, , 21F
從第一局就用了很多很多的試探法在看AlphaGO的表現
03/13 22:15, 21F
→
03/13 22:17, , 22F
說的對 除了參數個數 模型複雜度也跟f()形狀有關
03/13 22:17, 22F
推
03/13 22:20, , 23F
推
03/13 22:20, 23F
推
03/13 22:23, , 24F
推!
03/13 22:23, 24F
推
03/13 22:26, , 25F
推
03/13 22:26, 25F
→
03/13 22:27, , 26F
修正一下ANN的起始年代
03/13 22:27, 26F
→
03/13 22:28, , 27F
google一下Walter Pitts跟Warren McCulloch
03/13 22:28, 27F
→
03/13 22:29, , 28F
再來找 Marvin Minsky 跟 Seymour Papert
03/13 22:29, 28F
推
03/13 22:29, , 29F
越理解這些 就越會對小李這次表現敬佩啊
03/13 22:29, 29F
→
03/13 22:31, , 30F
ANN 1940s年代就有理論, 50, 60年代開始被實作
03/13 22:31, 30F
→
03/13 22:31, , 31F
70年代沒落，80年代第二復甦,
03/13 22:31, 31F
→
03/13 22:32, , 32F
2000s年代又沒落，這幾年是再次復興
03/13 22:32, 32F
推
03/13 22:32, , 33F
三點，1.梯度消失問題可用特殊半線性函數解決2.區域最
03/13 22:32, 33F
→
03/13 22:32, , 34F
佳解可用autoencoder解決，3。計算量問題可用分散式gpu
03/13 22:32, 34F
→
03/13 22:32, , 35F
解決。未來深度網路發展無可限量
03/13 22:32, 35F
→
03/13 22:34, , 36F
CNN RNN也是80年代就出現，並不新只是重新挖出來
03/13 22:34, 36F
→
03/13 22:39, , 37F
好科普
03/13 22:39, 37F
→
03/13 22:40, , 38F
ANN也不是ML的分支，自成一個領域。作為分類預測器只
03/13 22:40, 38F
→
03/13 22:40, , 39F
是它功能之一。
03/13 22:40, 39F
推
03/13 22:44, , 40F
感謝科普!~~
03/13 22:44, 40F
→
03/13 22:54, , 41F
說的對 因為ANN被提出時只有AI 沒有ML 他目的是仿生
03/13 22:54, 41F
→
03/13 22:55, , 42F
不過因為本篇是談ML 所以我從1980開始算 的確不精確
03/13 22:55, 42F
→
03/13 22:56, , 43F
Dialysis的問題我答案可能是NO 因為f()長什麼樣子
03/13 22:56, 43F
→
03/13 22:56, , 44F
還是由人定義
03/13 22:56, 44F
推
03/13 22:59, , 45F
太專業 可惜看不懂...QQ 我頂多理解一些原理
03/13 22:59, 45F
推
03/13 23:00, , 46F
應該說人要選定適合的f()，然後透過學習把適合的theta
03/13 23:00, 46F
→
03/13 23:00, , 47F
找出來
03/13 23:00, 47F
推
03/13 23:08, , 48F
推推
03/13 23:08, 48F
推
03/13 23:10, , 49F
多謝好文
03/13 23:10, 49F
推
03/13 23:19, , 50F
好文推~長知識了
03/13 23:19, 50F
推
03/13 23:20, , 51F
推
03/13 23:20, 51F
推
03/13 23:31, , 52F
概念很清楚
03/13 23:31, 52F
推
03/13 23:40, , 53F
推
03/13 23:40, 53F
→
03/14 00:39, , 54F
我覺得是人類在對局中成長了～
03/14 00:39, 54F
→
03/14 00:40, , 55F
李世石跟他下了三局　應該有感覺出電腦的一些弱著點
03/14 00:40, 55F
→
03/14 00:40, , 56F
這一步恰好逼了電腦發瘋而已XD
03/14 00:40, 56F
推
03/14 02:26, , 57F
03/14 02:26, 57F
推
03/14 09:57, , 58F
超級好文
03/14 09:57, 58F
推
03/14 10:14, , 59F
感謝科普!!!!
03/14 10:14, 59F
‣ 更多 fallcolor 的文章
文章代碼(AID): #1MvN3Vbi (GO)
‣ 更多 fallcolor 的文章
文章代碼(AID): #1MvN3Vbi (GO)