原創 Synced 機器之心
機器之心專欄
作者：王林楠、田淵棟
布朗大學在讀博士王林楠在本文中介紹了他與 Facebook 田淵棟團隊合作，在 2020 年 NeurIPS 取得亮眼表現的新算法，以及其在神經網絡結構搜索中的應用。
現實世界的大多數系統是沒有辦法給出一個確切的函數定義，比如機器學習模型中的調參，大規模數據中心的冷藏策略等問題。這類問題統統被定義為黑盒優化。黑盒優化是在沒辦法求解梯度的情況下，通過觀察輸入和輸出，去猜測優化變量的最優解。在過去的幾十年發展中，遺傳算法和貝葉斯優化一直是黑盒優化最熱門的方法。不同於主流算法，本文介紹一個基於蒙特卡洛樹搜索（MCTS）的全新黑盒優化算法，隱動作集蒙特卡洛樹搜索 (LA-MCTS)。LA-MCTS 發表在 2020 年的 NeurIPS，僅僅在文章公開幾個月後，就被來自俄羅斯 JetBrains 和韓國的 KAIST 的隊伍獨立復現，並用來參加 2020 年 NeurIPS 的黑盒優化挑戰，分別取得了第三名和第八名的好成績 [10][11]。
論文連結：https://arxiv.org/pdf/2007.00708.pdf
Github 地址：https://github.com/facebookresearch/LaMCTS
黑盒優化的回顧
黑盒優化是一個已經發展了幾十年的領域了，在跟很多人交流我們工作的時候，我被問到最多的問題就是，我們算法和遺傳算法以及貝葉斯優化有什麼優勢？為了更好的理解這個問題，首先讓我們來看看遺傳算法和貝葉斯優化是如何工作的。
遺傳算法：遺傳算法有很多變種，但是大體上是這圖上這 3 類。
1) Evolution: 首先是用一個固定的 multi-variate gaussian 來建模下一步從哪兒去採樣（如上圖的 Evolution）。在當下的 iteration 撒一堆點，然後找出這堆點當下最優的解，然後把這個 multi-variate gaussian 的均值重新放到這個最優解。由於不變，所以下一個 iteration 做採樣的時候那個 region 的樣子也不變。
這裡我們給出了一個優化 2 維 Rastrigin 的例子。Rastrigin 函數如下圖，
下圖呈現了 Evolution 算法的優化過程。由於 σ 不變，每次採樣出來的藍色的點的分布在每個 iteration 都是差不多的。並且當下 iteration 中，採樣分布所用的 μ，是上一個 iteration 中採樣出來的最好的點，即圖中紅色的點。
2) Genetic: 這個核心思想就是抽取一個 pool 來追蹤當下樣本中的 top 10%（可以設置的超參變量），然後在這個 pool 裡進行變異。同樣下圖可視化了該算法在 2 維 Rastrigin 的優化過程。圖中綠色的點就是當下 top samples，在下一個 iteration 中的藍色 samples 都是由上一個 iteration 中的綠色的 samples 變異而來。
3）CMA-ES: 和 Evolution 相比，它不光變 μ，而且同時變 σ 。其核心思想是同樣追蹤當下 top samples，然後用 top samples 來更新 μ 和 σ，而不是像 evolution 裡只把 μ 改到了當下最優的 sample 上。所以這裡的採樣區間會動態的變化，特別是 top samples 分布比較分散的話，採樣區間就會很大。當 top samples 收斂到一個最優解附近時候，採樣空間就自動減小了，因為 top samples 之間的 variance 小了。
同樣我們可視化了 CMA-ES 在優化二維 Rastrigin 函數的過程。一開始採樣區域迅速增大，那是因為 top samples (圖中紫色的點) 的分布越來越散，導致用來採樣的 gaussian 的 σ 增大，所以採樣區域不過往最優解附近靠近(通過更新 μ ), 而且採樣空間也迅速增大。但是到了後期採樣，由於紫色的點慢慢靠攏，所以 σ 減小，同時也導致採樣空間縮小。
遺傳算法的問題：由此可以看出，遺傳算法並不是特別適合 NAS，因為他每個 iteration 需要撒很多的神經網絡來更新採樣分布。然而來評估一個神經是非常耗時的，無論是重頭訓練一遍，還是用 supernet。
貝葉斯優化：同樣貝葉斯優化有很多變種，但是大體上算法可以歸為下來幾步。
1) Surrogate Model: 這一步利用一個函數擬合器，根據當下現有的採樣，來 fit 一個黑盒函數。
2) Acquisition Function: 這一步就是貝葉斯優化的探索（exploration）和利用 (exploitation) 機制。他利用 Surrogate Model 和當下採樣的分布，來選擇下一個採樣的位置。
同樣是優化二維的 Rastrigin 函數，貝葉斯優化的採樣效率會比遺傳算法好很多，如下圖。圖中的每一個點都對應的一個採樣，紅色的點代表最優解。因為貝葉斯優化裡利用了一個 Surrogate Model 去猜那裡比較好，所以採樣效率會高很多。
貝葉斯優化的問題：但是在高緯問題中，貝葉斯優化會過度的探索邊界，導致大量的樣本被浪費[8][9]。為了理解這個問題，我們來看下面優化一個一維函數的例子。左圖中的 x 是從 iteration 1-> iteration3 的採樣，右圖是 acquisition function，最高的地方即是採樣點。可以看出前幾個 iteration 基本在探索那些附近沒有樣本的區域。
因為我們這裡看到的只是一維問題，當問題緯度擴展到 20d+，這個時候貝葉斯優化一開始就需要非常多的點來探索搜索空間。這也就是為什麼很多人會觀測到，在高緯度問題中，貝葉斯優化在少量樣本下，會跟隨機搜索差不多。
而這些一開始作為探索的樣本，一般都會落在搜索空間的邊界。至於為什麼會是邊界，這個跟歐幾裡得空間有關。簡單來說，一個立方體，靠近邊界部分的體積會遠大與內核部分的體積。以此類推，在一個 n 維立方體裡，大部分的搜索空間都在邊界，所以探索一開始會探索邊界。
Latent Action Monte Carlo Tree Search(LA-MCTS)
為了解決貝葉斯優化在高維空間過渡探索的問題，我們的解決方案是，去學習切割搜索空間。這裡的核心動機如下圖。當我們切分搜索空間後，把原問題劃分為更小的子問題，然後用貝葉斯優化來解。雖然在子問題也會出現過度探索，但是這個時候的樣本落點和原問題的樣本落點很不一樣，如下圖。所以劃分子空間後，可以從某種程度上減輕過度探索的問題。
LA-MCTS 的核心思想就是，我們希望學習一些邊界去劃分搜索空間。這些邊界還能夠自動去適應函數值的變化。當我們在劃分出來的好的空間去採樣的時候，出來的樣本也期望是好的，同理在壞的空間，採樣出來的樣本也相對較差。
上圖是我們算法的一個大體框架。在每一個樹的節點上，我們想學到一個邊界，根據當下的採樣點（既 x 和 f(x)），能夠把搜索空間分為一個好的子空間（左節點），和一個壞的子空間（右節點），如上圖。而這裡的隱動作集 (Latent Action) 就是，從當下節點選擇去左 / 右孩子。至於動作的選擇，在每個節點是根據 UCT 公式來決定。因為每個節點對應一個搜索空間，這個搜索空間上有相應的樣本。每個孩子上對應搜索空間的樣本的個數就是 UCT 裡的 n，而這些樣本性能的平均值就是 UCT 裡的 v。當我們對搜索空間建立這樣的一個搜索樹，隨著樹深度的增加，在搜索空間找到好的區域也越來越精確。
根據上述的定義，Latent Action 是把一個空間分成一個好的子空間，和一個壞的子空間。假設在任何一個節點上，我們首先學習一個 regressor 來把當下節點上的樣本分為好樣本和壞樣本，然後我們通過 SVM 來學習出一個邊界來把當下節點的搜索空間分為兩個部分，一個好的搜索空間和一個壞的搜索空間。因為處在 regressor 上的樣本 f(x)更高，所以分出來的空間是好空間。然後這兩個子空間被兩個子節點所代表，並且相應子空間上的樣本也去相對應的節點。這就構成了我們整個樹模型的最基本的單元。
有了這個最基本的模型，下來介紹下算法的 3 個基本步驟。
1）Learning and split: 在每個 iteration 開始，因為上個 iteration 有新的樣本，我們需要重新構建一個樹來分割搜索空間。同樣，一開始的 root 節點包含所有的樣本，同時並代表了整個搜索空間。我們這樣遞歸的利用 latent action 來把一個節點分成兩個節點，直到樹上的葉子結點內，包含不超過 20（超參可以調）個樣本。所以樹的樣子完全由樣本決定的。下圖描述了這個過程。
2) Select: 從樹的根開始，我們計算出每個節點的 UCB 數值。訪問次數就是當下 node 裡有多少 samples，均值就是當下 node 裡樣本的均值，即 f(x)的均值。然後我們從跟節點到葉子，一直選 UCB 最大的。這個過程如下圖。
3）Sampling: 根據我們選出來的一條路徑，這個路徑上的 SVM 就包裹出了一個子搜索空間，如下圖的
。然後，我們只在這個子空間上進行貝葉斯優化即可。
最後我們很快的來看一下 LA-MCTS 應用在貝葉斯優化的效果。更多的數據，請參考我們的文章。
其實早在 2011 年，Rémi Munos (DeepMind) 提出利用 MCTS 來分割搜索空間用來優化一個黑盒函數 [4]，然後，劍橋大學和 MIT，有很多工作把這種切分搜索空間的思想用在了高維貝葉斯優化 [5][6]。但是這些工作一般都會採用一個 k-ary 區塊切分（如下圖）。2020 年，MIT 的 Beomjoon Kim 在[7] 展示出利用沃羅諾伊圖（Voronoi Graph）去切分搜索空間，結果會更好。我們的工作，LA-MCTS，則是利用了 learning 的法則，根據當下樣本來學習分割方法，來提高搜索效率。
LA-MCTS 的一些有待改善的地方：目前我們觀測到 UCB 中的 exploration 變量 c 對結果影響比較大，畢竟 Cp=0 的時候 LA-MCTS 就變成了一個 random 算法，而 Cp=1 的時候，就是一個純 greedy 的算法了。目前我們發現大多數把 Cp = 0.1*max f(x) 工作的比較好，這裡的 max f(x) 是猜測出來的函數最大值。當然在實際使用中，可以在 search space 先大概跑一跑，看什麼樣的 Cp 下降的比較快。如果大家在使用 LA-MCTS 感覺效果不太好，很可能是這裡出了問題。
其次，SVM 在有些時候不是很穩定，比如 kernel type 的選擇。還有，目前我們採樣還是基於 sampling 的方法，未來可以考慮通過 LBFGS 來解一個 constrained optimization 問題，這裡的 constrains 是 SVM 的邊界。總而言之，未來還有很多需要解決的問題。
LA-MCTS 在 NeurIPS-2020 黑盒優化挑戰的表現
當然文章裡的數據是漂亮啦，但是要其他人復現出來同樣說好那才好。在今年 NeurIPS-2020 中，Facebook, Twitter, SigOPT, 第四範式等活躍在黑盒優化領域內的公司，發起了一個黑盒優化挑戰賽，試圖去尋找當下最優的黑盒優化器。該挑戰利用各個參賽團隊提交的優化器，去解決 216 個不同領域的黑盒優化問題。當然，每個優化器在不同的問題上也是跑了很多次去取平均，來保證比賽的公正。更多這個比賽的詳情，大家可以參照這裡 https://bbochallenge.com/virtualroom。
下圖是這次比賽的 leaderboard。
總結一下，LA-MCTS 在這次比賽分別被第三名的 JetBrains 和第八名的 KAIST 團隊獨立復現我們的算法（因為當時還沒有放出原始碼），並參加這次比賽。值得一提的是，第一名和第二名的隊伍均採用 ensemble 不同 solver 的方法（比如不同的 acquisition），而第三名只使用一種 solver。所以我個人認為未來探索 ensemble 和 learning search space partition 會是一個比較有意思的問題。最後，我個人很喜歡的一個黑盒優化算法 TuRBO，在前十名隊伍中，被六個隊伍所廣泛採用。
更值得一提的是，在 NAS 方面發表出的很多 search 算法，比如用神經網絡或者圖神經網絡做 predictor，或者 RL，SGD (finite difference 類)，並沒有在這次比賽中表現出非常優秀的成績。
把 LA-MCTS 應用在神經網絡結構搜索（NAS）
我們同時也把 LA-MCTS 應用在神經網絡結構搜索給 CIFAR-10，ImageNet，Detection 等。下面是我們搜索出來的網絡的結果。
我們在 NAS 探索的一個簡介
1. 起源：應用蒙特卡洛樹搜索在神經網絡結構搜索。
2017 年初，我的導師從美國國防高級研究計劃局的 D3M 項目拿到了一筆項目資金，開啟了我們的 AutoML 研究。而我被分配的子任務，就是神經網絡結構搜索 (NAS)。當時 NAS 研究的 2 篇文章，都是利用強化學習（谷歌的 policy gradients 和 MIT 的 Q-learning）。我們發現 Q-learning 的 epsilon greedy 非常簡單的同等對待了所有的狀態(states)，並不考慮每個 states 過去探索了多少次，所以並不能很好的去平衡利用(exploitation) 和探索 (exploration)。從這點出發，我們考慮對每個狀態去建模，來更好的平衡利用和探索，來提高搜索效率。而蒙特卡洛樹搜索(MCTS) 正是對每一個狀態建模，利用 UCT 來動態的平衡利用和探索。同時，AlphaGo 的成功證實 MCTS 在大規模狀態空間下效果非常好。在這樣的背景下，我們開發第一個基於 MCTS 的 NAS 算法，並命名為 AlphaX。
AlphaX 構建網絡和 MIT 的 Q-learning 算法相似。從一個空網絡開始，根據動作集，比如添加一個 conv 或者 pooling，逐層構建一個網絡架構（s→a→s』）。因為訓練一個網絡非常慢，AlphaX 提出利用一個價值函數預測器（value function predictor）來預測當下狀態下的子網絡們的性能。這個價值函數器輸入就是一個網絡架構，輸出就是預測的該網絡的精度。同時我們驗證了，NAS 能夠提升很多下遊的視覺應用，比如風格遷移，目標檢測等。詳情請見[1]。
2. 學習蒙特卡洛樹裡的動作集，從 LaNAS 到 LA-MCTS。
基於 AlphaX，我 FB 的導師田淵棟洞察到動作集在 AlphaX 對搜索效率有著顯著的影響。為了證實這個想法，我們設計了動作集 sequential 和 global。動作集 sequential 就是按照逐層構建網絡的思路，一步步的增加 conv 或者 pooling，並指定每層的參數；而動作集 global 則首先劃定網絡的深度，比如 10 層網絡。然後同時給這 10 層網絡指定每層的種類，參數等。我們發現動作集 global 的搜索效率顯著高於動作集 sequential，並且可視化了狀態空間，如下圖。
直觀上而言，狀態空間在 global 的動作集下，好的狀態（深色）和差的狀態（淺色）區分的很好，不像 sequential 混雜在一起。這樣搜索算法可以很快找到一個好的區域，所以效率更高。基於這個觀察，促使我們去給 MCTS 學習動作集，並提出了 Latent Action Monte Carlo Tree Search (LA-MCTS)。
我們最初把這個想法應用在了 NAS，並構建了一個 NAS 系統命名為 LaNAS[2]。對比貝葉斯優化和進化算法，LaNAS 在 NAS 的基準數據集 NASBench-101 上取得了顯著的提升。所以我們又擴展了 LaNAS 成為了 LA-MCTS 去做應用更廣的黑盒優化。從 LaNAS 到 LA-MCTS，核心更新有：1）LA-MCTS 把 LaNAS 裡的邊界擴展成一個非線性邊界，2）LA-MCTS 在採樣的時候利用貝葉斯優化來選擇樣本。最後，LA-MCTS 在各種測試函數和 MuJoCo 上取得了顯著的提升，詳見[3]。
搜索是否對 NAS 重要
我認為是重要的。以下是我觀測到的一些趨勢及我的思考。
1）最近有些文章展示隨機搜索都可以達到很好的結果，那麼是不是意味著搜索不重要了？
首先這些文章是說隨機搜索得到的結果還不錯，是一個非常強的對比基準。這個往往因為目前的搜索空間的設計，導致大部分網絡結果都很好，比如下圖所呈現的 NASBench-101 中 42 萬個網絡的分布（橫軸是精度，縱軸是這個精度下有多少網絡 log scale）。所以找出一個工作還不錯的網絡並不難。
2) 既然搜索空間的設計影響很大，那麼是不是更應該把注意力放在設計搜索空間，而不是搜索？
我覺得這個問題應該站在不同的角度。首先，近幾年神經網絡的高速發展讓我們在設計搜索空間的時候有了很多先驗經驗，所以設計出來的搜索域裡的網絡都不會太差。在一些傳統的視覺應用，搜索的貢獻可能就不如加各種 tricks 或者調參數在工程中來的更實際一些。但是如果當我們遇到一個新的任務，比如設計一個神經網絡去調度網絡節點。由於先驗經驗很少，這個時候搜索就可以極大的加速我們設計網絡的速度。並且搜索可以提供很多的經驗去讓我們改進搜索空間。
3）基於搜索方法的 NAS 和 DARTS 類算法的對比。
以 DARTS 為代表的 one-shot NAS 方法跑的很快，是因為利用了一個超級網絡 (Supernet) 去近似每個網絡的性能。在這個過程中，Supernet 相當提供一個網絡性能的預測，然後利用 SGD 在 Supernet 上去找一個比較好的結果。這裡 Supernet 和 Search 也是可以分開，而且分開後更易分別提高這兩個部分。所以只需要把 Supernet 的概念應用在傳統搜索方法上，也是可以很快得到結果。SGD 的問題是很容易卡在一個局部最優，而且目前 SoTA 的結果基本都是利用傳統搜索方法直接，或者利用一個 supernet 搜索出來的。
Github 地址：https://github.com/facebookresearch/LaMCTS
下面是這個開源項目一覽：
Neural Architecture Search，全網最全的神經網絡結構搜索 pipeline。
開源 LaNAS on NASBench101：無需訓練網絡，在你筆記本上快速評估 LaNAS。
開源 LaNAS 搜索出的模型「LaNet」：在 CIFAR-10 和 ImageNet 上都取得 SoTA 結果。
開源 one-shot/few-shots LaNAS：只需幾個 GPU，快速並且高效完成神經網絡結構搜索。含搜索，訓練，整套 pipeline。
分布式 LaNAS：讓我們用上百個 GPU 來超過最先進的模型。整套 pipeline。
Bag of tricks 模型訓練的那些黑科技：我們列出當下訓練模型的一些提升點數黑招數。
Black-box optimizations，黑盒優化
1 分鐘的對比：只需 1 分鐘，評測 LA-MCTS，和貝葉斯優化及進化算法。
MuJoCo Tasks：應用 LA-MCTS 在機器人，強化學習，並可視化你學出來的策略。
作者介紹
王林楠是布朗大學第四年博士生，他的研究方向為人工智慧和超級計算。他的目標就是讓人工智慧全民化，能夠讓任何人，任何公司只需要點擊幾次滑鼠就能設計，部署一個可行的人工智慧系統。為了實現這個目標，他一直致力於建立一個基於蒙特卡洛樹搜索的人工智慧，來設計不同的人工智慧給大眾。通過四年的努力，他們已經圍繞蒙特卡洛樹搜索建立了一個完整的神經網絡結構搜索系統去實現這個目標。
田淵棟博士，臉書（Facebook）人工智慧研究院研究員及經理，研究方向為深度強化學習，多智能體學習，及其在遊戲中的應用，和深度學習模型的理論分析。圍棋開源項目 DarkForest 及 ELF OpenGo 項目中研究及工程負責人和第一作者。2013-2014 年在 Google 無人駕駛團隊任軟體工程師。2005 年及 08 年於上海交通大學獲本碩學位，2013 年於美國卡耐基梅隆大學機器人研究所獲博士學位。曾獲得 2013 年國際計算機視覺大會（ICCV）馬爾獎提名（Marr Prize Honorable Mentions）。
[1] Neural Architecture Search using Deep Neural Networks and Monte Carlo Tree Search, AAAI-2020.
[2] Sample-Efficient Neural Architecture Search by Learning Action Space, 2019
[3] Learning Search Space Partition for Black-box Optimization using Monte Carlo Tree Search, NeurIPS 2020.
[4] Optimistic optimization of a deterministic function without the knowledge of its smoothness, NeurIPS 2011.
[5] Batched Large-scale Bayesian Optimization in High-dimensional Spaces, AISTATS 2018.
[6] Heteroscedastic Treed Bayesian Optimisation, 2014.
[7] Monte Carlo Tree Search in continuous spaces using Voronoi optimistic optimization with regret bounds, AAAI-2020.
[8] Bock: Bayesian optimization with cylindrical kernels
[9] Correcting boundary over-exploration deficiencies in Bayesian optimization with virtual derivative sign observations
[10] Solving Black-Box Optimization Challenge via Learning Search Space Partition for Local Bayesian Optimization
[11] Adaptive Local Bayesian Optimization Over Multiple Discrete Variables
© THE END
轉載請聯繫本公眾號獲得授權
投稿或尋求報導：content@jiqizhixin.com
原標題：《專欄 | 蒙特卡洛樹搜索在黑盒優化和神經網絡結構搜索中的應用》
閱讀原文