理解貝葉斯優化

1 黑盒優化問題

絕大多數機器學習算法都有超參數。這些超參數可以分爲兩種類型，定義模型及結構本身的參數，目標函數與優化算法（求解器）所需的參數。前者用於訓練和預測階段，後者只用於訓練階段。在訓練時需要人工設定它們的值，通過反覆試驗獲得好的結果，整個過程會耗費大量的時間和人力成本。因此如何自動確定超參數的值是AutoML中一個重要的問題。問題的核心是自動搜索出最優超參數值以最大化預期目標。因此可抽象爲函數極值問題，優化變量爲超參數，函數值爲機器學習模型的性能指標如準確率、預測速度。

黑盒優化問題目標函數的表達式未知，只能根據離散的自變量取值得到對應的目標函數值。超參數優化屬於黑盒優化問題，在優化過程中只能得到函數的輸入和輸出，不能獲取優化目標函數的表達式和梯度信息，這一特點給超參數優化帶來了困難。對於某些機器學習模型，超參數數量較大，是高維優化問題。對模型進行評估即計算目標函數的值在很多情況下成本高昂，因爲這意味着要以某種超參數配置訓練機器學習模型，並在驗證集上計算精度等指標。常用的超參數優化方法有網格搜索（Grid search），隨機搜索（Random search），遺傳算法，貝葉斯優化（Bayesian Optimization）等，接下來分別進行介紹。

1.1網格搜索

網格搜索是最簡單的做法，它搜索一組離散的取值情況，得到最優參數值。對於連續型的超參數，對其可行域進行網格劃分，選取一些典型值進行計算。假設需要確定的超參數有2個，第1個的取值爲[0,1]之間的實數，第2個的取值爲[1,2]之間的實數。則可以按照如下的方案得到若干離散的取值，以這些值運行算法：

將第1個參數均勻的取3個典型值，將第2個參數均勻的取3個典型值。對於所有的取值組合運行算法，將性能最優的取值作爲超參數的最終取值。這種方法如圖1所示。

圖1 網格搜索的原理

網格搜索隨着參數數量的增加呈指數級增長，因此對於超參數較多的情況，該方法面臨性能上的問題。著名的支持向量機開源庫libsvm使用了網格搜索算法確定SVM的超參數。

1.2隨機搜索

隨機搜索做法是將超參數隨機地取某些值，比較各種取值時算法的性能，得到最優超參數值，其原理如圖2所示。

圖2 隨機搜索的原理

對於如何生成隨機取值，有多種不同的策略。通常的做法是用均勻分佈的隨機數進行搜索，也可以使用更復雜的啓發式搜索策略。

1.3貝葉斯優化

網格搜索和隨機搜索沒有利用已搜索點的信息，使用這些信息指導搜索過程可以提高結果的質量以及搜索的速度。貝葉斯優化（Bayesian optimization algorithm，簡稱BOA）利用之前已搜索點的信息確定下一個搜索點，用於求解維數不高的黑盒優化問題。

算法的思路是首先生成一個初始候選解集合，然後根據這些點尋找下一個有可能是極值的點，將該點加入集合中，重複這一步驟，直至迭代終止。最後從這些點中找出極值點作爲問題的解。

這裏的關鍵問題是如何根據已經搜索的點確定下一個搜索點。貝葉斯優化根據已經搜索的點的函數值估計真實目標函數值的均值和方差（即波動範圍），如圖3所示。上圖中紅色的曲線爲估計出的目標函數值即在每一點出處的目標函數值的均值。現在有3個已經搜索的點，用黑色實心點表示。兩條虛線所夾區域爲在每一點處函數值的變動範圍，在以均值即紅色曲線爲中心，與標準差成正比的區間內波動。在搜索點處，紅色曲線經過搜索點，且方差最小，在遠離搜索點處方差更大，這也符合我們的直觀認識，遠離採樣點處的函數值估計的更不可靠。

根據均值和方差可以構造出採集函數（acquisition function），即對每一點是函數極值點的可能性的估計，反映了每一個點值得搜索的程度，該函數的極值點是下一個搜索點，如圖3的下圖所示。下圖中的矩形框所表示的點是採集函數的極大值點，也是下一個搜索點。

算法的核心由兩部分構成：對目標函數進行建模即計算每一點處的函數值的均值和方差，通常用高斯過程迴歸實現；構造採集函數，用於決定本次迭代時在哪個點處進行採樣。

圖3 貝葉斯優化的原理

2 高斯過程迴歸

2.1 高斯過程

多維高斯分佈具有諸多優良的性質。高斯過程（Gaussian Process，GP）用於對一組隨着時間增長的隨機向量進行建模，在任意時刻隨機向量的所有子向量均服從高斯分佈。假設有連續型隨機變量序列 ，如果該序列中任意數量的隨機變量構成的向量

均服從多維正態分佈，則稱此隨機變量序列爲高斯過程。特別地，假設當前有k個隨機變量 ，它們服從k維正態分佈 。 其中均值向量 ，協方差矩陣 。 加入一個新的隨機變量 之後，隨機向量 服從k+1維正態分佈 。 其中均值向量 ，協方差矩陣 。 由於正態分佈的積分能得到解析解，因此可以方便地得到邊緣概率與條件概率。 均值向量與協方差矩陣的計算將在稍後講述。

2.2 高斯過程迴歸

在機器學習中，算法通常情況下是根據輸入值x預測出一個最佳輸出值y，用於分類或迴歸任務。這種情況將y看作普通的變量。某些情況下我們需要的不是預測出一個函數值，而是給出這個函數值的後驗概率分佈p(y丨x)。此時將函數值看作隨機變量。對於實際應用問題，一般是給定一組樣本點 ，根據它們擬合出一個假設函數 ，給定輸入值x，預測其標籤值y或者其後驗概率p(y 丨 x)。 高斯過程迴歸對應的是第二種方法。

高斯過程迴歸（Gaussian Process Regression，GPR）對錶達式未知的函數（黑盒函數）的一組函數值進行貝葉斯建模，給出函數值的概率分佈。假設有黑盒函數f(x)實現如下映射

高斯過程迴歸可以根據某些點 以及在這些點處的函數值 得到一個模型，擬合此黑盒函數。 對於任意給定的輸入值x可以預測出f(x)，並給出預測結果的置信度。 事實上模型給出的是f(x)的概率分佈。

高斯過程迴歸假設黑盒函數在各個點處的函數值f(x)都是隨機變量，它們構成的隨機向量服從多維正態分佈。對於函數f(x)，x有若干個採樣點 ，在這些點處的函數值構成向量

是高斯分佈的均值向量

是協方差矩陣

問題的核心是如何根據樣本值計算出正態分佈的均值向量和協方差矩陣。均值向量通過使用均值函數μ（x）根據每個採樣點x計算而構造。協方差通過核函數 根據樣本點對 計算得到，也稱爲協方差函數。 核函數需要滿足下面的要求。

1. 距離相近的樣本點x和 之間有更大的正協方差值，因爲相近的兩個點的函數值也相似，有更強的相關性；

2. 保證協方差矩陣是對稱半正定矩陣。根據任意一組樣本點計算出的協方差矩陣都必須是對稱半正定矩陣。

通常使用的是高斯核與Matern核。高斯覈定義爲

爲核函數的參數。顯然該核函數滿足上面的要求。高斯核在支持向量機等其他機器算法中也有應用。

Matern覈定 義爲

其中 是伽馬函數， 是貝塞爾函數（Bessel function）， 是人工設定的正參數。 用核函數計算任意兩點之間的核函數值，得到核函數矩陣K作爲協方差矩陣的估計值。

接下來介紹均值函數的實現。可以使用下面的常數函數

最簡單的可以將均值統一設置爲0

即使將均值統一設置爲常數，因爲有方差的作用，依然能夠對數據進行有效建模。如果知道目標函數f(x)的結構，也可以使用更復雜的函數。

在計算出均值向量與協方差矩陣之後，可以根據此多維正態分佈來預測f(x)在任意點處函數值的概率分佈。假設已經得到了一組樣本值 以及其對應的函數值 ，接下來要預測新的點x的函數值f(x)的數學期望μ(x)和方差 。 如果令

加入該點之後 服從t+1 維 正態正態分佈。 將均值 向 和協方差矩陣進行分塊，可以寫成

在這裏 服從t維正態正態分佈，其均值向量爲 ，協方差矩陣爲 K ，它們可以利用樣本集 根據均值函數和協方差函數算出。 t維列向量 k 根據 與 使用核函數計算

多維正態分佈的條件分佈仍爲正態分佈。可以計算出在已知 的情況下 所服從的條件分佈，根據多維正態分佈的性質，它服從一維正態分佈

對於前面介紹的均值向量和協方差矩陣分塊方案，根據多維正態分佈條件分佈的計算公式，可以計算出此條件分佈的均值和方差。計算公式爲

計算均值時利用了已有采樣點處的函數值 。 μ的值是 與根據已有的採樣點數據所計算出的值 之和，與 有關。 而方差 只與核函數所計算出的協方差值有關，與 無關。

下面用一個例子說明高斯過程迴歸的原理，如圖4所示。這裏要預測的黑盒函數爲

其圖像是圖4中的紅色虛線。在這裏我們並不知道該函數的表達式，只有它在5個採樣點處的函數值，爲圖中的紅色圓點。高斯過程迴歸根據這5個點處的函數值預測出了在[0,10]區間內任意點處的函數值f(x)的概率分佈。圖中的藍色實線是高斯過程預測出的這些點處的均值μ。藍色帶狀區域是預測出的這些點處的95%置信區間，根據該點處的均值μ和方差 計算得到。

圖4一個函數的高斯過程迴歸預測結果

3 貝葉斯優化

貝葉斯優化的思路是首先生成一個初始候選解集合，然後根據這些點尋找下一個最有可能是極值的點，將該點加入集合中，重複這一步驟，直至迭代終止。最後從這些點中找出函數值最大的點作爲問題的解。由於求解過程中利用之前已搜索點的信息，因此比網格搜索和隨機搜索更爲有效。

這裏的關鍵問題是如何根據已經搜索的點確定下一個搜索點，通過高斯過程迴歸和採集函數實現。高斯過程迴歸根據已經搜索的點估計其他點處目標函數值的均值和方差，如圖5所示。圖5中藍色實線爲真實的目標函數曲線，黑色虛線爲算法估計出的在每一點處的目標函數值。圖中有7個已經搜索的點，用紅色點表示。藍色帶狀區域爲在每一點處函數值的置信區間。函數值在以均值，即黑色虛線爲中心，與標準差成正比的區間內波動。圖5的下圖爲採集函數曲線，下一個採樣點爲採集函數的極大值點，以五角星表示。

在已搜索點處，黑色虛線經過這些點，且方差最小；在遠離搜索點處方差更大。這也符合我們的直觀認識，遠離採樣點處的函數值估計的更不可靠。根據均值和方差構造出採集函數，是對每一點是函數極值可能性的估計，反映了該點值得搜索的程度。該函數的極值點即爲下一個搜索點。貝葉斯優化算法的流程如下所示。

其核心由兩部分構成：

1. 高斯過程迴歸。計算每一點處函數值的均值和方差；

2. 根據均值和方差構造採集函數，用於決定本次迭代時在哪個點處進行採樣。

算法首先初始化 個候選解，通常在整個可行域內均勻地選取一些點。 然後開始循環，每次增加一個點，直至找到N個候選解。 每次尋找下一個點時，用已經找到的n個候選解建立高斯迴歸模型，得到任意點處的函數值的後驗概率。 然後根據後驗概率構造採集函數，尋找函數的極大值點作爲下一個搜索點。 接下來計算在下一個搜索點處的函數值。 算法最後返回N個候選解的極大值作爲最優解。

圖5貝葉斯優化的原理

用已有采樣點預測任意點處函數值的後驗概率分佈的方法在前面已經介紹，這裏重點介紹採集函數的構造。採集函數用於確定在何處採集下一個樣本點，它需要滿足下面的條件。

1. 在已有的採樣點處採集函數的值更小，因爲這些點已經被探索過，再在這些點處計算函數值對解決問題沒有什麼用；

2. 在置信區間更寬的點處採集函數的值更大，因爲這些點具有更大的不確定性，更值得探索；

3. 在函數均值更大的點處採集函數的值更大，因爲均值是對該點處函數值的估計值，這些點更可能在極值點附近。

f(x)是一個隨機變量，直接用它的數學期望μ(x)作爲採集函數並不是好的選擇，因爲沒有考慮方差的影響。常用的採集函數有期望改進（expected improvement），知識梯度（knowledge gradient）等，下面以期望改進爲例進行說明。假設已經搜索了n個點，這些點中的函數極大值記爲

現在考慮下一個搜索點x，我們將計算該點處的函數值f(x)。如果 則這n+1個點處的函數極大值爲f(x)，否則爲 。 對於第一種情況，加入這個新的點之後，函數值的改進爲下面的正值 ，對於第二種情況，則爲0。 藉助於下面的 截斷 函數

我們可以將加入新的點之後的改進值寫成

現在的目標是找到使得上面的改進值最大的x，但該點處的函數值f(x)在我們找到這個點x並進行函數值計算之前又是未知的。由於我們知道f(x)的概率分佈，因此我們可以計算所有x處的改進值的數學期望。並選擇數學期望最大的x作爲下一個探索點。因此可以定義下面的期望改進（expected improvement）函數

其中 表示根據前面n個採樣點 以及這些點處的函數值 計算出的條件期望值。 計算這個數學期望所採用的概率分佈由高斯過程迴歸定義，是f(x)的條件概率。

由於高斯過程迴歸假設f(x)服從正態分佈，可以得到數學期望的解析表達式。假設在x點處的均值爲μ=μ（x），方差爲 。 令z=f(x)，根據數學期望的定義有

使用定積分的換元法，可以得到

其中 爲標準正態分佈的概率密度函數， 是標準正態分佈的分佈函數。 如果令 ，則有

是x的函數，因此EI也是x的函數。

具體的推導過程可以閱讀2020年7-8月將在人民郵電出版社出版的《機器學習的數學》一書的第7章。

期望改進將每個點處的期望改進表示爲該點的函數，下一步是求期望改進函數的極值以得到下一個採樣點

這個問題易於求解。由於可以得到目標函數的一階和二階導數，因此梯度下降法和L-BFGS算法都可以解決此問題 。

本文爲SIGAI原創

如需轉載，歡迎發消息到本訂閱號

全文PDF見http://www.tensorinfinity.com/paper_231.html

記得點擊右下角“ 好看 ”

相關文章