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