[科普]如何使用高大上的方法調參數

[本文主要介紹我與Elad Hazan, Adam Klivans 合作的最新論文: Hyperparameter Optimization: A Spectral Approach]

那麼，在介紹具體演算法之前，我們先要理解一個很重要的問題：

調參數這個東西，關我x事？

因為它非常有用。 調參數是指這麼個問題：你有n個參數，每個參數需要賦一個值。賦完值之後，你用這些參數做一個實驗，可以看到一個結果。根據這個結果，你可以修改你的參數，然後接著做實驗，看結果，改參數……最後你希望得到一個非常好的結果。

這個框架適用於幾乎一切場景。比如說，它可以用來指導你做飯。每次放多少鹽？多少糖？火開多大？開多久放料？先放什麼再放什麼？各放多少？ 平底鍋還是炒鍋？油放多少？要不要放胡椒粉？等等。

Jasper Snoek就在一次報告中講述如何用調參數方法（貝葉斯優化）炒雞蛋。他只花了大概30個雞蛋就得到了一個很好的菜譜。當然了，調參數方法還可以用來炒蝦米，炒豬肉，燉茄子，烤羊腿，或者釀酒，和面，撒農藥，養雞養鴨，做生物化學實驗，基因優化，空氣動力學結構設計，機器人蔘數優化等等，不一而足。只要你獨具慧眼，其實生活中太多的問題可以用這一類方法來解決。

---------------我是分割線------------------

在機器學習裡面，這個問題尤其重要。比如說，你哪天想要拿神經網路來做個什麼，應該怎麼弄？有些同學可能知道，神經網路，作為一個高科技的東東，其實還是相當複雜的。它需要用戶做很多決策。而對於初學者來說，這些決策往往令人望而生畏。例如：

• 網路有多深？
• 網路有多寬？
• 每一層是要用什麼結構？線性層還是卷積層？
• 層與層之間應該如何連接？
• 應該使用什麼樣的Activation？
• 應該使用什麼樣的優化演算法？
• 優化演算法的初始步長是多少？
• 初始步長在訓練過程中應該如何下降？
• 應該使用什麼樣的初始化？
• 是否需要使用Momentum演算法？如果是，具體速率是多少？
• 卷積層裡面是否要加入常數項？
• 是否需要使用Dropout？
• 是否需要使用Batch norm？是否需要自動調整Batch norm的參數？

• 是否需要使用Weight decay？
• Weight decay速度是多少？
• Mini batch的大小是多少？

這些問題，有些是重要的，有些是不那麼重要的。有些如果設錯了沒有什麼關係，有些設錯了會導致神經網路直接就沒用了。尤其是對於一個新的應用場景而言，找到那些對它最關鍵的問題並給予正確的答案，至關重要。

好了，講到這裡，大家應該都理解了，這是一個非常有意義的問題。那麼，

現在大家是怎麼調參數的呢？

現在大家都用GSS演算法，全稱是Graduate Student Search演算法。翻譯成中文就是博士生人肉搜索演算法，又稱煉丹演算法。

圖文無關！ [Andy Greenspon, a PhD student in Applied Physics at Harvard, aligns a green laser for characterizing optical properties of diamond. (Photo by David Bracher) ]

好吧，其實除了GSS演算法，我們也有一些別的演算法，比如之前提到的貝葉斯演算法（Bayesian Optimization），還有Hyperband演算法，等等，其實都是一些很優美的演算法。那麼，既然之前提到貝葉斯演算法可以用來炒雞蛋，為什麼現在大家仍然使用博士生人肉搜索這種原始的方法做調參數問題呢？

答案是來自高維度的詛咒。當需要考慮的參數個數過多的時候，可能性就會呈指數級別增長，而已有的演算法卻沒有很好的機制來處理這個問題。對於調參數的問題來說，每一次實驗的代價都很大（想想炒雞蛋，每次實驗都會要犧牲一個雞蛋），因此一旦需要做的實驗數量隨著參數個數指數增長之後，演算法就會失效。一般來說，已有的演算法只能夠處理不到20個參數的問題。

而博士生人肉搜索則不然。像小蜜蜂一樣的博士生們通過辛勤的勞動，往往能夠從眾多參數中找到若干最重要的10個20個參數，然後再把它們塞到已有演算法裡面自動調一調，往往就能夠得到很好的結果。

有沒有辦法把人肉搜索這一步自動化呢？這就是我們論文的主要貢獻：

Harmonica —— 我們的演算法

[在介紹演算法之前，我想要提一下，我們的演算法適用於離散參數的情況。對於連續參數，可以使用賭博機(Multi-armed Bandit)+最速下降法(Gradient Descent)方法，或者把它們離散化成為離散參數。由於離散參數都可以轉化為布爾參數，以下我們只考慮參數是布爾的情況。但是其實一切的實際問題都可以轉換成這個情況，並不只是一個理論上的簡化。]

我們先簡單談談拉鎖（Lasso）演算法。

拉鎖演算法是一個非常常用、非常簡單、非常基本的線性回歸的演算法。問題大致是這樣的：已知，已知向量, 已知矩陣 ，想要求。

我們考慮的情況很特殊，矩陣往往是一個很「扁」的矩陣。舉個例子，的大小往往是100行10000列，也就是說有100個數，呢有10000個數。這就導致滿足要求的解可能並不唯一。

這個時候，如果我們加了一個額外的假設，說雖然非常長，但是它很稀疏，大部分位置都是0，只有少數的幾個是非0的。加了這個假設之後，可以用壓縮感知（Compressed Sensing）的方法證明，拉鎖演算法（的某個變種）可以找到這個，即所謂的稀疏復原（Sparse Recovery）。

這個東西和我們的問題有什麼關係呢？在我們這個問題里，矩陣可以看做是測量矩陣，有100行的話，就表示我們嘗試了100個不同的參數組合。有10000列的話，就表示每個參數組合呢，可以觀察到有10000個特徵。向量可以看做是不同的參數組合得到的調參數的結果，所以有100個數。而我們要求的向量，則是不同的特徵對於最後調參數的結果的影響有多大。我們假設是稀疏的，即只有少數幾個特徵非常重要，其他的都不重要。

小結一下。我們引入線性回歸的想法，就是想要找到一些有用的特徵，並且假設這些特徵的線性疊加可以很好地近似最後調參數的結果。換句話說，我們認為我們需要優化的這個參數函數，本質是一個線性函數，更加確切地說，是一個稀疏的線性函數。

有些同學肯定就要開噴了，這個顯然不是線性的啊，參數函數甚至都不是凸的啊，你們這些搞理論的這麼總是指鹿為馬啊，blabla……

嗯是的，參數函數幾乎一定不是參數的線性疊加，但是它一定可以寫成某些特徵的線性疊加。例如，深度神經網路對圖像分類的時候，從某個角度來說，可以看做是它的前n-1層對圖片的像素進行了特徵提取，得到了最後一層的特徵向量。然後最後一層再做一個線性疊加（linear layer），得到了最後的答案。從這個角度來看，其實神經網路也假設圖片分類的函數是一個線性函數，不過線性函數的特徵向量是神經網路自己學出來的罷了。

那麼言歸正傳，我們這裡用到的特徵是什麼呢？ 使用調和分析（Harmonic Analysis，或者Boolean Functional Analysis）的知識，我們可以知道，任何的基於n個布爾參數的參數函數，都可以寫成基於個傅里葉基函數（Fourier Basis）的線性疊加，其中每一個基函數就是若干個布爾參數相乘得到的多項式而已。（如果看到傅里葉基函數這樣的東西嚇壞了，千萬不要擔心。本文不會涉及什麼泛函分析的具體內容；你把它想成是線性代數裡面的基就可以。）

換句話說，在剛才的線性回歸的式子里，如果我們把想成是長度為的關於參數函數的傅里葉基的權重分布，一切就說得通了。任何的參數函數都一定對應著這麼一個。如果恰巧是一個比較稀疏的向量的話，使用拉鎖演算法（的某個變種）就一定能夠找到。

說到這裡，演算法的框架已經比較清楚了。但其實仍然有兩個非常實際的問題需要解決。

第一個問題：如果n比較大，比如有60，那麼顯然是我們無法承受的。怎麼辦？解決方法很簡單，我們只考慮所謂的低度數傅里葉基（Low degree Fourier Basis），即那些最多只包含個參數相乘的基函數。這樣的基函數仍然是相互垂直的，而且它們的線性疊加可以表示一切參數之間相關性最多為度的參數函數（即，最多只有個參數兩兩相關）。我們在論文里還證明了，如果已知的參數函數可以用一個較小的決策樹來表示，那麼它也一定可以用低度數傅里葉基的線性疊加來近似。總而言之呢，對於實際問題而言，其實只需要使用低度數傅里葉基也就夠了。這樣一共有多少個特徵呢？只有個特徵。我們一般也就取，實際上效果就很好了。

第二個問題更加嚴重。就算我們現在只用了個特徵，拉鎖演算法能夠找到的前提是是一個稀疏向量。但是，實際上根本就不是一個稀疏向量！一方面，有些特徵確實比較重要；另一方面，其他特徵的貢獻卻也遠遠大於0，不能夠簡單忽略。

如何解決這個問題呢？我們的演算法的巧妙之處在於，使用了多層拉鎖！注意到，對於調參數問題，我們並不在意真的去把復原出來；我們只是想要找到一組參數，使得這組參數能夠對應比較好的結果而已。所以我們先跑一次拉鎖，得到了一部分重要的特徵。基於這些特徵，我們知道一部分相關的參數，以及它們應該如何賦值才能夠得到這些特徵的線性疊加的最小值。於是，我們就可以固定這些參數。

這些參數固定之後，其實個數往往不多，一般也就5、6個。我們還剩下大量的參數的值沒有確定。如果這個時候停止的話，相當於就默認這些參數對最後的函數完全不起任何作用（當然是不對的）。我們做的就是，在固定已有的5、6個參數的情況下，對剩下的參數重新進行隨機採樣，然後跑拉鎖。這樣我們又會得到若干個重要的參數，於是又可以重新採樣跑拉鎖，如此循環多次之後，即可得到一大堆重要的參數和它們的賦值。

至此，我們的演算法就介紹完了。

---------------我是分割線------------------

小結一下，所謂的Harmonica演算法大體是在做如下的事情：

1. 在參數空間中，隨機採樣（比如）100個點
2. 對每個點計算低度數傅里葉基的特徵向量，捕捉參數之間的相關性
3. 對於計算好的100個特徵向量，跑拉鎖演算法，得到（比如） 5個重要的特徵，以及這些特徵對應的參數
4. 固定這些參數的值，得到了新的調參數問題（參數個數減少，搜索空間降低）。回到第一步。

如此重複若干輪之後，固定了很多參數的值，其實已經得到了一個很好的解。剩下的參數基本上和白雜訊差不多，可以調用一些已有的演算法（hyperband之類） 進行微調即可。

Harmonica的幾個優點：

• 對參數個數的增長不敏感
• 優化速度極快（跑跑拉鎖即可）
• 非常容易並行
• 可以自動高效地提取重要的特徵

理論解釋

雖然我們的演算法很簡單，但是正如我之前提到的那樣，其實它背後有很強的理論支持。在論文中，我們使用了調和分析和壓縮感知的方法證明它的正確性與有效性。在證明的過程中，我們還順便解決了一個存在了20多年的關於決策樹的理論問題 。但是一來大家可能對這方面並不感興趣，二來理解了確實也沒什麼用，我便把這部分可恥地略去了 -__-

實驗結果

其實我們就跑了一個神經網路實驗，在Cifar10上面跑resnet。這個實驗我選了39個各式各樣的參數，涵蓋了我能想到的一切需要手調的參數，外加21個無用參數（用於加大問題難度）。我們跑了3層的拉鎖演算法，使用了度數為3的特徵向量，現在一個小的8層的網路上跑，得到了重要的參數們之後，將這些信息用到大的56層的網路上微調，得到了很好的結果。如下圖：

可以看到，Harmonica得到的結果比別的演算法（Random Search, Hyperband, Spearmint）都好很多，而總的時間卻用得很少。其中，Harmonica跑10天（我們用了10台機器並行，因此實際只花了1天）就能夠得到和博士生們極為接近的結果。而Harmonica跑3天就能夠得到比別的演算法跑17天20天還要好很多的結果。除此之外，Harmonica找到的特徵與人們的經驗是十分吻合的。比如batch normalization， activation， learning rate就是它找到的最重要的3個特徵。詳見論文。

這篇論文大概就是這樣了。作為第一篇對調參數問題做特徵提取的論文，我覺得這個方向仍然有很多可以挖掘的地方。我們把python版本的代碼放在了github上，有興趣的同學可以試試看。

推薦閱讀：