圍棋AI AlphaGo 之我見 - 圍棋

感謝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並不神奇，說到底就是資料堆積出來的一個數學模型，因為它仍然
: 缺乏人最重要的邏輯思維與創作才華(我認為這不同於模型的泛化能力)，至少在現階段它
: 是遠遠不需要恐懼的，而是需要與人類的智慧互相參考與提升，一起進步下去。

--