原文鏈接：貝葉斯優化(Bayesian Optimization)深入理解

目前在研究Automated Machine Learning,其中有一個子領域是實現網路超參數自動化搜索，而常見的搜索方法有Grid Search、Random Search以及貝葉斯優化搜索。前兩者很好理解，這裡不會詳細介紹。本文將主要解釋什麼是體統(沉迷延禧攻略2333)，不對應該解釋到底什麼是貝葉斯優化。

I Grid Search & Random Search

我們都知道神經網路訓練是由許多超參數決定的，例如網路深度，學習率，卷積核大小等等。所以為了找到一個最好的超參數組合，最直觀的的想法就是Grid Search，其實也就是窮舉搜索，示意圖如下。

但是我們都知道機器學習訓練模型是一個非常耗時的過程，而且現如今隨著網路越來越複雜，超參數也越來越多，以如今計算力而言要想將每種可能的超參數組合都實驗一遍(即Grid Search)明顯不現實，所以一般就是事先限定若干種可能，但是這樣搜索仍然不高效。

所以為了提高搜索效率，人們提出隨機搜索，示意圖如下。雖然隨機搜索得到的結果互相之間差異較大，但是實驗證明隨機搜索的確比網格搜索效果要好。

II Bayesian Optimization

假設一組超參數組合是X=x1,x2,...,xn(xn表示某一個超參數的值)，而這組超參數與最後我們需要優化的損失函數存在一個函數關係，我們假設是f(X)。而目前機器學習其實是一個黑盒子(black box),即我們只知道input和output，所以上面的函數f很難確定。所以我們需要將注意力轉移到一個我們可以解決的函數上去，下面開始正式介紹貝葉斯優化。假設我們有一個函數f:X→R,我們需要在 Xsubseteqcal{X} 內找到 x^?=argmin_{x∈X}f(x) ag{1} 當f是凸函數且定義域X也是凸的時候，我們可以通過已被廣泛研究的凸優化來處理，但是ff並不一定是凸的，而且在機器學習中f通常是expensive black-box function，即計算一次需要花費大量資源。那麼貝葉斯優化是如何處理這一問題的呢？1. 詳細演算法

Sequential model-based optimization (SMBO) 是貝葉斯優化的最簡形式，其演算法思路如下：

下面詳細介紹一下上圖中的演算法：

1. Input:
  • f: 就是那個所謂的黑盒子
  • X:是輸入數據，例如圖像、語音等。
  • S:是Acquisition Function(採集函數)，這個函數的作用是用來選擇公式(1)中的xx，後面會詳細介紹這個函數。
  • M:是基於輸入數據假設的模型，即已知的輸入數據xx都是在這個模型上的，可以用來假設的模型有很多種，例如隨機森林，Tree Parzen Estimators(想要了解這兩種的可以閱讀參考文獻[1])等，但是本文主要介紹高斯模型。

2. InitSamples(f,x)→D

這一步驟就是初始化獲取數據集D=(X1,Y1),...,(Xn,Yn)，其中Yi=f(Xi)Yi=f(Xi),這些都是已知的。3. 循環選參數T次因為每次選出參數xx後都需要計算f(x)f(x),而正如前面介紹的沒計算一次函數ff，都會消耗大量資源，所以一般需要固定選參次數(或者是函數評估次數)。
  • p(y|x,D)←FITMODEL(M,D)

首先我們預先假設了模型M服從高斯分布，且已知了數據集D，所以可以通過計算得出具體的模型具體函數表示。假設下圖中的綠色實現就是基於數據集D經過計算後的服從高斯分布模型。可以看到Each additional band of green is another half standard deviation on the output distribution.

那麼高斯分布是如何計算的呢？

因為我們已經假設f~GP(μ,K)。 (GP:高斯過程，μ:均值 K:協方差kernel,)。所以預測也是服從正態分布的，即有p(y|x,D)=N(y|μ^,σ^2)

  • x_i←argmax_{x∈X}S(X,p(y|X,D))

現在已經將假設的模型計算出來了，那麼下一步我們需要基於假設模型的基礎上選擇滿足公式(1)的參數了，也就是選擇XX，那麼如何選擇呢？這就涉及到了Acquisition Function，為了讓文章篇幅更易閱讀，想了解Acquisition Function移步到文末。

  • yi←f(xi)

既然參數選出來了，那麼當然就是要計算咯。例如我們通過上述步驟已經選出了一組超參數xi，那麼我們下一步就是將超參數帶入網路中去進行訓練，最後得到輸出yi。這一步驟雖然expensive，但是沒辦法還是得走啊。

  • D←D?(xi,yi)

更新數據集。

2. Acquisition FunctionAcquisition Function的選擇可以有很多種，下面將分別介紹不同的AC function。1） Probability of improvement假設f′=minf,這個f′表示目前已知的ff的最小值。

然後定義utility function如下：

u(x) = egin{cases} o, & ext{if $f(x)>f$} \ 1, & ext{if $f(x)≤f$ } end{cases} 其實也可以把上面的u(x)u(x)理解成一個reward函數，如果f(x)不大於f就有獎勵，反之沒有。probability of improvement acquisition function定義為the expected utility as a function of x: egin{align} a_{PI}(x)=E[u(x)|x,D] & = int_{-∞}^{f}cal{N}(f;μ(x),K(x,x))df otag{} \ & = cal{Phi}(f;μ(x),K(x,x)) otag{} end{align} 之後只需要求出a(x)的最大值即可求出基於高斯分布的滿足要求的xx。2) Excepted improvement上面的AC function有個缺點就是找到的xx可能是局部最優點，所以有了Excepted improvement。f′的定義和上面一樣，即f′=minf。utility function定義如下:u(x)=max(0,f′?f(x))因為我們最初的目的是找到使得f(x)最小的x，所以這個utility function的含義很好理解，即接下來找到的f(x)f(x)比已知最小的f′f′越小越好，然後選出小的程度最大的那個f(x)f(x)和f′f′之間的差距的絕對值作為獎勵，如果沒有更小的那麼獎勵則為0.

AC function定義如下：

egin{align} a_{EI}(x)=E[u(x)|x,D] & = int_{-∞}^{f}(f-f)cal{N}(f;μ(x),K(x,x))df otag{} \ & = (f-μ(x))cal{Phi}(f;μ(x),K(x,x)) , + , K(x,x)cal{N}(f;μ(x),K(x,x)) otag{} end{align} 通過計算使得 a_{EI} 值最大的點即為最優點。上式中有兩個組成部分。要使得上式值最大則需要同時優化左右兩個部分：
  • 左邊需要儘可能的減少μ(x)
  • 右邊需要儘可能的增大方差(或協方差)K(x,x)

但是二者並不同能是滿足，所以這是一個exploitation-exploration tradeoff。

3) Entropy search

4） Upper confidence bound

Reference

  • [1] Sigopt.com. Bayesian Optimization Primer (2018). [online] Available at: sigopt.com/static/pdf/S [Accessed 26 Oct. 2018].
  • [2] Cse.wustl.edu. Bayesian Optimization (2018). [online] Available at: cse.wustl.edu/~garnett/ [Accessed 26 Oct. 2018].
  • [3] Anon,How does Bayesian optimization work? (2018). [online] Available at: quora.com/How-does-Baye [Accessed 26 Oct. 2018].

MARSGGBO?原創2018-10-28
推薦閱讀：
相关文章