0
雷鋒網(wǎng)按：本文原作者袁洋，原載于知乎專欄理論與機器學習。雷鋒網(wǎng)已獲得作者授權(quán)。
本文主要介紹作者與 Elad Hazan, Adam Klivans 合作的最新論文: Hyperparameter Optimization: A Spectral Approach
那么，在介紹具體算法之前，我們先要理解一個很重要的問題：
因為它非常有用。 調(diào)參數(shù)是指這么個問題：你有 n 個參數(shù)，每個參數(shù)需要賦一個值。賦完值之后，你用這些參數(shù)做一個實驗，可以看到一個結(jié)果。根據(jù)這個結(jié)果，你可以修改你的參數(shù)，然后接著做實驗，看結(jié)果，改參數(shù)…… 最后你希望得到一個非常好的結(jié)果。
這個框架適用于幾乎一切場景。比如說，它可以用來指導你做飯。每次放多少鹽？多少糖？火開多大？開多久放料？先放什么再放什么？各放多少？ 平底鍋還是炒鍋？油放多少？要不要放胡椒粉？等等。
Jasper Snoek 就在一次報告中講述如何用調(diào)參數(shù)方法（貝葉斯優(yōu)化）炒雞蛋。他只花了大概 30 個雞蛋就得到了一個很好的菜譜。當然了，調(diào)參數(shù)方法還可以用來炒蝦米，炒豬肉，燉茄子，烤羊腿，或者釀酒，和面，撒農(nóng)藥，養(yǎng)雞養(yǎng)鴨，做生物化學實驗，基因優(yōu)化，空氣動力學結(jié)構(gòu)設(shè)計，機器人參數(shù)優(yōu)化等等，不一而足。只要你獨具慧眼，其實生活中太多的問題可以用這一類方法來解決。
--------------- 我是分割線 ------------------
在機器學習里面，這個問題尤其重要。比如說，你哪天想要拿神經(jīng)網(wǎng)絡來做個什么，應該怎么弄？有些同學可能知道，神經(jīng)網(wǎng)絡，作為一個高科技的東東，其實還是相當復雜的。它需要用戶做很多決策。而對于初學者來說，這些決策往往令人望而生畏。例如：
網(wǎng)絡有多深？
網(wǎng)絡有多寬？
每一層是要用什么結(jié)構(gòu)？線性層還是卷積層？
層與層之間應該如何連接？
應該使用什么樣的 Activation？
應該使用什么樣的優(yōu)化算法？
優(yōu)化算法的初始步長是多少？
初始步長在訓練過程中應該如何下降？
應該使用什么樣的初始化？
是否需要使用 Momentum 算法？如果是，具體速率是多少？
卷積層里面是否要加入常數(shù)項？
是否需要使用 Dropout？
是否需要使用 Batch norm？是否需要自動調(diào)整 Batch norm 的參數(shù)？
是否需要使用 Weight decay？
Weight decay 速度是多少？
Mini batch 的大小是多少？
這些問題，有些是重要的，有些是不那么重要的。有些如果設(shè)錯了沒有什么關(guān)系，有些設(shè)錯了會導致神經(jīng)網(wǎng)絡直接就沒用了。尤其是對于一個新的應用場景而言，找到那些對它最關(guān)鍵的問題并給予正確的答案，至關(guān)重要。
好了，講到這里，大家應該都理解了，這是一個非常有意義的問題。那么，
現(xiàn)在大家都用 GSS 算法，全稱是 Graduate Student Search 算法。翻譯成中文就是博士生人肉搜索算法，又稱煉丹算法。
圖文無關(guān)！ [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 算法，等等，其實都是一些很優(yōu)美的算法。那么，既然之前提到貝葉斯算法可以用來炒雞蛋，為什么現(xiàn)在大家仍然使用博士生人肉搜索這種原始的方法做調(diào)參數(shù)問題呢？
答案是來自高維度的詛咒。當需要考慮的參數(shù)個數(shù)過多的時候，可能性就會呈指數(shù)級別增長，而已有的算法卻沒有很好的機制來處理這個問題。對于調(diào)參數(shù)的問題來說，每一次實驗的代價都很大（想想炒雞蛋，每次實驗都會要犧牲一個雞蛋），因此一旦需要做的實驗數(shù)量隨著參數(shù)個數(shù)指數(shù)增長之后，算法就會失效。一般來說，已有的算法只能夠處理不到 20 個參數(shù)的問題。
而博士生人肉搜索則不然。像小蜜蜂一樣的博士生們通過辛勤的勞動，往往能夠從眾多參數(shù)中找到若干最重要的 10 個 20 個參數(shù)，然后再把它們?nèi)揭延兴惴ɡ锩孀詣诱{(diào)一調(diào)，往往就能夠得到很好的結(jié)果。
有沒有辦法把人肉搜索這一步自動化呢？這就是我們論文的主要貢獻：
[在介紹算法之前，我想要提一下，我們的算法適用于離散參數(shù)的情況。對于連續(xù)參數(shù)，可以使用賭博機 (Multi-armed Bandit)+ 最速下降法 (Gradient Descent) 方法，或者把它們離散化成為離散參數(shù)。由于離散參數(shù)都可以轉(zhuǎn)化為布爾參數(shù)，以下我們只考慮參數(shù)是布爾的情況。但是其實一切的實際問題都可以轉(zhuǎn)換成這個情況，并不只是一個理論上的簡化。]
我們先簡單談談拉鎖（Lasso）算法。
拉鎖算法是一個非常常用、非常簡單、非?；镜木€性回歸的算法。問題大致是這樣的：已知，已知向量
, 已知矩陣
，想要求
。
我們考慮的情況很特殊，矩陣往往是一個很 “扁” 的矩陣。舉個例子，
的大小往往是 100 行 10000 列，也就是說
有 100 個數(shù)，
呢有 10000 個數(shù)。這就導致滿足要求的解可能并不唯一。
這個時候，如果我們加了一個額外的假設(shè)，說雖然非常長，但是它很稀疏，大部分位置都是 0，只有少數(shù)的幾個是非 0 的。加了這個假設(shè)之后，可以用壓縮感知（Compressed Sensing）的方法證明，拉鎖算法（的某個變種）可以找到這個
，即所謂的稀疏復原（Sparse Recovery）。
這個東西和我們的問題有什么關(guān)系呢？在我們這個問題里，矩陣可以看做是測量矩陣，有 100 行的話，就表示我們嘗試了 100 個不同的參數(shù)組合。有 10000 列的話，就表示每個參數(shù)組合呢，可以觀察到有 10000 個特征。向量
可以看做是不同的參數(shù)組合得到的調(diào)參數(shù)的結(jié)果，所以有 100 個數(shù)。而我們要求的向量
，則是不同的特征對于最后調(diào)參數(shù)的結(jié)果的影響有多大。我們假設(shè)
是稀疏的，即只有少數(shù)幾個特征非常重要，其他的都不重要。
小結(jié)一下。我們引入線性回歸的想法，就是想要找到一些有用的特征，并且假設(shè)這些特征的線性疊加可以很好地近似最后調(diào)參數(shù)的結(jié)果。換句話說，我們認為我們需要優(yōu)化的這個參數(shù)函數(shù)，本質(zhì)是一個線性函數(shù)，更加確切地說，是一個稀疏的線性函數(shù)。
有些同學肯定就要開噴了，這個顯然不是線性的啊，參數(shù)函數(shù)甚至都不是凸的啊，你們這些搞理論的這么總是指鹿為馬啊，blabla……
嗯是的，參數(shù)函數(shù)幾乎一定不是參數(shù)的線性疊加，但是它一定可以寫成某些特征的線性疊加。例如，深度神經(jīng)網(wǎng)絡對圖像分類的時候，從某個角度來說，可以看做是它的前 n-1 層對圖片的像素進行了特征提取，得到了最后一層的特征向量。然后最后一層再做一個線性疊加（linear layer），得到了最后的答案。從這個角度來看，其實神經(jīng)網(wǎng)絡也假設(shè)圖片分類的函數(shù)是一個線性函數(shù)，不過線性函數(shù)的特征向量是神經(jīng)網(wǎng)絡自己學出來的罷了。
那么言歸正傳，我們這里用到的特征是什么呢？ 使用調(diào)和分析（Harmonic Analysis，或者 Boolean Functional Analysis）的知識，我們可以知道，任何的基于 n 個布爾參數(shù)的參數(shù)函數(shù)，都可以寫成基于個傅里葉基函數(shù)（Fourier Basis）的線性疊加，其中每一個基函數(shù)就是若干個布爾參數(shù)相乘得到的多項式而已。（如果看到傅里葉基函數(shù)這樣的東西嚇壞了，千萬不要擔心。本文不會涉及什么泛函分析的具體內(nèi)容；你把它想成是線性代數(shù)里面的基就可以。）
換句話說，在剛才的線性回歸的式子里，如果我們把想成是長度為
的關(guān)于參數(shù)函數(shù)的傅里葉基的權(quán)重分布，一切就說得通了。任何的參數(shù)函數(shù)都一定對應著這么一個
。如果
恰巧是一個比較稀疏的向量的話，使用拉鎖算法（的某個變種）就一定能夠找到
。
說到這里，算法的框架已經(jīng)比較清楚了。但其實仍然有兩個非常實際的問題需要解決。
第一個問題：如果 n 比較大，比如有 60，那么顯然是我們無法承受的。怎么辦？解決方法很簡單，我們只考慮所謂的低度數(shù)傅里葉基（Low degree Fourier Basis），即那些最多只包含
個參數(shù)相乘的基函數(shù)。這樣的基函數(shù)仍然是相互垂直的，而且它們的線性疊加可以表示一切參數(shù)之間相關(guān)性最多為
度的參數(shù)函數(shù)（即，最多只有
個參數(shù)兩兩相關(guān)）。我們在論文里還證明了，如果已知的參數(shù)函數(shù)可以用一個較小的決策樹來表示，那么它也一定可以用低度數(shù)傅里葉基的線性疊加來近似?？偠灾兀瑢τ趯嶋H問題而言，其實只需要使用低度數(shù)傅里葉基也就夠了。這樣一共有多少個特征呢？只有
個特征。我們一般也就取
，實際上效果就很好了。
第二個問題更加嚴重。就算我們現(xiàn)在只用了個特征，拉鎖算法能夠找到
的前提是
是一個稀疏向量。但是，實際上
根本就不是一個稀疏向量！一方面，有些特征確實比較重要；另一方面，其他特征的貢獻卻也遠遠大于 0，不能夠簡單忽略。
如何解決這個問題呢？我們的算法的巧妙之處在于，使用了多層拉鎖！注意到，對于調(diào)參數(shù)問題，我們并不在意真的去把復原出來；我們只是想要找到一組參數(shù)，使得這組參數(shù)能夠?qū)容^好的結(jié)果而已。所以我們先跑一次拉鎖，得到了一部分重要的特征。基于這些特征，我們知道一部分相關(guān)的參數(shù)，以及它們應該如何賦值才能夠得到這些特征的線性疊加的最小值。于是，我們就可以固定這些參數(shù)。
這些參數(shù)固定之后，其實個數(shù)往往不多，一般也就 5、6 個。我們還剩下大量的參數(shù)的值沒有確定。如果這個時候停止的話，相當于就默認這些參數(shù)對最后的函數(shù)完全不起任何作用（當然是不對的）。我們做的就是，在固定已有的 5、6 個參數(shù)的情況下，對剩下的參數(shù)重新進行隨機采樣，然后跑拉鎖。這樣我們又會得到若干個重要的參數(shù)，于是又可以重新采樣跑拉鎖，如此循環(huán)多次之后，即可得到一大堆重要的參數(shù)和它們的賦值。
至此，我們的算法就介紹完了。
--------------- 我是分割線 ------------------
小結(jié)一下，所謂的 Harmonica 算法大體是在做如下的事情：
在參數(shù)空間中，隨機采樣（比如）100 個點
對每個點計算低度數(shù)傅里葉基的特征向量，捕捉參數(shù)之間的相關(guān)性
對于計算好的 100 個特征向量，跑拉鎖算法，得到（比如） 5 個重要的特征，以及這些特征對應的參數(shù)
固定這些參數(shù)的值，得到了新的調(diào)參數(shù)問題（參數(shù)個數(shù)減少，搜索空間降低）?；氐降谝徊健?/p>
如此重復若干輪之后，固定了很多參數(shù)的值，其實已經(jīng)得到了一個很好的解。剩下的參數(shù)基本上和白噪聲差不多，可以調(diào)用一些已有的算法（hyperband 之類） 進行微調(diào)即可。
Harmonica 的幾個優(yōu)點：
對參數(shù)個數(shù)的增長不敏感
優(yōu)化速度極快（跑跑拉鎖即可）
非常容易并行
可以自動高效地提取重要的特征
雖然我們的算法很簡單，但是正如我之前提到的那樣，其實它背后有很強的理論支持。在論文中，我們使用了調(diào)和分析和壓縮感知的方法證明它的正確性與有效性。在證明的過程中，我們還順便解決了一個存在了 20 多年的關(guān)于決策樹的理論問題 。但是一來大家可能對這方面并不感興趣，二來理解了確實也沒什么用，我便把這部分可恥地略去了 -__-
其實我們就跑了一個神經(jīng)網(wǎng)絡實驗，在 Cifar10 上面跑 resnet。這個實驗我選了 39 個各式各樣的參數(shù)，涵蓋了我能想到的一切需要手調(diào)的參數(shù)，外加 21 個無用參數(shù)（用于加大問題難度）。我們跑了 3 層的拉鎖算法，使用了度數(shù)為 3 的特征向量，現(xiàn)在一個小的 8 層的網(wǎng)絡上跑，得到了重要的參數(shù)們之后，將這些信息用到大的 56 層的網(wǎng)絡上微調(diào)，得到了很好的結(jié)果。如下圖：
可以看到，Harmonica 得到的結(jié)果比別的算法（Random Search, Hyperband, Spearmint）都好很多，而總的時間卻用得很少。其中，Harmonica 跑 10 天（我們用了 10 臺機器并行，因此實際只花了 1 天）就能夠得到和博士生們極為接近的結(jié)果。而 Harmonica 跑 3 天就能夠得到比別的算法跑 17 天 20 天還要好很多的結(jié)果。除此之外，Harmonica 找到的特征與人們的經(jīng)驗是十分吻合的。比如 batch normalization， activation， learning rate 就是它找到的最重要的 3 個特征。詳見論文。
這篇論文大概就是這樣了。作為第一篇對調(diào)參數(shù)問題做特征提取的論文，我覺得這個方向仍然有很多可以挖掘的地方。我們把 python 版本的代碼放在了 github上，有興趣的同學可以試試看。
雷峰網(wǎng)版權(quán)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
