0
雷鋒網按：本文原作者袁洋，原載于知乎專欄理論與機器學習。雷鋒網已獲得作者授權。
本文主要介紹作者與 Elad Hazan, Adam Klivans 合作的最新論文: Hyperparameter Optimization: A Spectral Approach
那么，在介紹具體算法之前，我們先要理解一個很重要的問題：
因為它非常有用。 調參數是指這么個問題：你有 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 個參數，然后再把它們塞到已有算法里面自動調一調，往往就能夠得到很好的結果。
有沒有辦法把人肉搜索這一步自動化呢？這就是我們論文的主要貢獻：
[在介紹算法之前，我想要提一下，我們的算法適用于離散參數的情況。對于連續參數，可以使用賭博機 (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 算法大體是在做如下的事情：
在參數空間中，隨機采樣（比如）100 個點
對每個點計算低度數傅里葉基的特征向量，捕捉參數之間的相關性
對于計算好的 100 個特征向量，跑拉鎖算法，得到（比如） 5 個重要的特征，以及這些特征對應的參數
固定這些參數的值，得到了新的調參數問題（參數個數減少，搜索空間降低）。回到第一步。
如此重復若干輪之后，固定了很多參數的值，其實已經得到了一個很好的解。剩下的參數基本上和白噪聲差不多，可以調用一些已有的算法（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上，有興趣的同學可以試試看。
雷峰網版權文章，未經授權禁止轉載。詳情見轉載須知。
