Bayesian optimization，即貝葉斯最佳化。

原文傳送門

Frazier， Peter I。 “A tutorial on bayesian optimization。” arXiv preprint arXiv：1807。02811 （2018）。

Introduction to Bayesian Optimization （slides）

特色

最近有做離子阱實驗的同學涉及到一些實驗引數的調參問題，其中主要需要用到貝葉斯最佳化。同時，我自己在想的一些問題也可能會用到貝葉斯最佳化。

過程

1。 問題設定

貝葉斯最佳化主要解決一個最佳化問題，即

【演算法】Bayesian Optimization

該待最佳化函式

f

具有如下特點：

Expensive to evaluate：每次給定一個

x

來獲取

f(x)

數值都有一定的成本，因此目標是儘可能少地去取樣而找到一個好的解。

Black box：它不具有一些特殊的結構性質，比如 convexity、linearity 等，因此有一些能夠針對這些結構特性來加速最佳化的方法不能被使用；

Derivative-free：無法獲得它的導數，即不能使用一些基於導數來加速最佳化的方法；

（Maybe） noisy：對於函式

f

的一次取樣得到的數值可能包含一個均值為零的噪聲，因此即使在某一個點上也不能完全相信取樣得到的數值；

該設定有著廣泛的應用。比如在離子阱的實驗中，需要調節鐳射器的各種引數，從而形成一個由電磁波產生的“陷阱”從而“困住”離子，而實驗的目標是需要讓鐳射形成一個足夠好的“陷阱”使得被困住的離子的溫度（能量）能夠足夠低。該系統中

x

就是相應的鐳射器引數，

f(x)

就是相應引數下形成離子阱的溫度。每組實驗測試需要花費幾十分鐘的時間（expensive to evaluate），因此不能測試很多引數；該過程涉及到非常多的物理過程而幾乎無法解析地求解，因此只能把它當做一個黑盒子來最佳化（black box）。

對於該類問題，有一些比較 naive 的解法，比如使用先驗知識來確定引數（玄學）、使用 grid search（維度爆炸）、使用 random search（效率低）。因此，我們需要使用貝葉斯最佳化的方法來有效地最佳化這類問題。

2。 貝葉斯最佳化的基本成分

考慮如下一個例子，希望在

[0,1]

區間上找到使得函式

f(x)

取最小值的位置，函式

f(x)

是 L-Lipschitz 的，並且是可導的；而所有的資訊只有四個位置上的

f(x)

值，如下圖所示。

【演算法】Bayesian Optimization

最簡單的想法，就是把對於所有滿足約束條件的函式進行取樣，然後分別找出這些函式的最小值位置，把最常出現位置作為預測的最小值位置。如下圖所示。

【演算法】Bayesian Optimization

貝葉斯最佳化主要包括如下部分

Prior： 確定函式

f(x)

的先驗分佈

Initial space-filling experimental design： 在函式的定義域上找一些儘可能分佈均勻的初始點，並且得到它們相應的函式值；

Posterior：透過一些機率模型（statistical model）根據已有的資料點來確定函式

f(x)

的後驗分佈；

Acquisition function：根據求得的後驗分佈來確定下一個（或者下一批）實驗點。

以上過程可以概括為如下演算法框架。

【演算法】Bayesian Optimization

下面就這幾個部分來具體講解。

3。 Statistical model

機率模型最常用的還是高斯過程（Gaussian process），當然也有其他的模型，比如 random forest、t-student process。這裡只講高斯過程。

考慮

k=n+1

個樣本點，它們的先驗分佈為

【演算法】Bayesian Optimization

假設已經知道了前

n

個樣本點的函式值

f(x_{1:n})

，可以得到第

n+1

個點

x=x_{n+1}

的後驗分佈：

【演算法】Bayesian Optimization

具體計算的過程可以參考 ［1］。

一般來說，先驗 mean function 取為常數就好，即，

\mu_0(x)=\mu

。先驗 kernel function 一般需要滿足空間上相近的點關聯性更強，比較常用的比如 power exponential / Gaussian kernel：

【演算法】Bayesian Optimization

或者 Matern kernel：

【演算法】Bayesian Optimization

這裡面的若干係數可以作為演算法的超引數。

4。 Acquisition functions

透過選定的 statistical model，可以得到任意一個點

x

的後驗分佈，記該分佈為

\mathcal{N}(\mu(x;\theta, \mathcal{D}), \sigma(x;\theta, \mathcal{D}))

，其中

\theta

表示先驗分佈相關的超引數，

\mathcal{D}

表示已有的樣本資料。下面需要透過得到的後驗分佈來確定下一個試驗點。下一個試驗點可以透過 acquisition function 來得到，它是一個關於

x

的實值函式

\alpha(x)

，選擇一個使得

\alpha(x)

取值最大的

x

作為下一個需要試驗的點。

Expected Improvement（EI）

EI 是最為常用的 acquisition function 之一。考慮當我們最後需要從已有的取樣點中選取一個點作為問題的解，考慮到每次取樣是沒有噪聲的，因此截止

n

個樣本時的最優解為

y_{best} = \min_{m\le n} f(x_m)

。如果還有一次機會來多做一次取樣，如果這一次取樣得到的數值

y

比

y_{best}

還好，那麼最終的結果就會由於這一次取樣而有所改善。改善的數值可以記為

\max(0, y_{best} - y)

。

因此，選擇下一個試驗點，使得該改善的期望最大。據此寫出相應的 acquisition function

【演算法】Bayesian Optimization

結合高斯模型，可以化簡該函式的表示式

【演算法】Bayesian Optimization

其中

\Phi(\cdot)

為高斯分佈的 CDF，

\psi

是一個 explorative parameter，鼓勵探索性地選擇試驗點。

【演算法】Bayesian Optimization

Maximum probability of improvement（MPI）

這是最早被提出的一種 acquisition function。和前一種不同的是，它最大化的是下一個取樣點能夠產生非零 improvement 的機率，即

【演算法】Bayesian Optimization

同樣，可以加上一個常數

\psi

鼓勵其探索。

【演算法】Bayesian Optimization

【演算法】Bayesian Optimization

Lower confidence band（LCB）

其 acquisition function 如下

【演算法】Bayesian Optimization

【演算法】Bayesian Optimization

Knowledge gradient（KG）

在 EI 中考慮在已有的樣本點的值作為最後的解，這裡考慮在估計的後驗分佈均值中找一個最優的值作為最後的解，即

【演算法】Bayesian Optimization

這樣相應的 acquisition function 可以寫為

\alpha_{KG}(x) = \mathbb{E}[\mu_n^* - \mu_{n+1}^*|x_{n+1} = x, \mathcal{D}]

該函式的求解計算比較複雜，具體見第一篇文獻。

Entropy search（ES）

其思想是希望找到一個樣本點，使得得到改樣本點的函式值之後，能夠最大程度地更容易確定最優值的位置。即

【演算法】Bayesian Optimization

其缺點是上述公式不能夠直接計算，需要透過取樣的方式來近似計算。

【演算法】Bayesian Optimization

Predictive entropy search（PES）

\alpha_{PES}(x) = H(p(y|\theta, \mathcal{D})) - \mathbb{E}_{x^*}[H(p(y|\theta, \mathcal{D}, x^*))]

其第一項是一個高斯分佈的 entropy，能直接算；第二項仍然需要取樣來近似。

5。 Initial space-filling experimental design

最開始需要選擇一些樣本點，作為演算法的初始樣本資料，這部分資料選擇的目標是儘可能“均勻”地分佈在感興趣的區域內。

有如下一些方法

【演算法】Bayesian Optimization

前兩種方法比較 naive，沒啥好解釋的。

Latin design

主要是希望每一行（不同的樣本）每一列（不同的維度）上的數值都儘可能散開。形象地來說就是下面這樣

【演算法】Bayesian Optimization

具體的實現可以參考 pyDOE： Randomized Designs。

Halton sequences

透過下面的這種規律來生成樣本點，使得生成的點更為均勻地分佈在空間中。

【演算法】Bayesian Optimization

【演算法】Bayesian Optimization

Determinantal point processes

沒太看明白，只放一張示意圖吧。

【演算法】Bayesian Optimization

6。 最佳化方法

前面定義了各種 acquisition function

\alpha(x)

，這些函式都能夠透過各種方式計算或者近似（而不需要再對

f

進行取樣）。但是我們的目標是找到一個

x

使得

\alpha(x)

最大，因此這中間還需要用到各種最佳化的方法來輔助我們找到下一個試驗點。主要的方法總結如下。

【演算法】Bayesian Optimization

需要注意的是有些 acquisition function 能夠提供導數，而有些不可以。

7。 貝葉斯最佳化的推廣

以下幾方面的擴充套件也是目前貝葉斯最佳化研究比較多的方向：

Noisy evaluation：主要考慮到每次取樣得到的函式值可能帶有一定的噪聲，第一篇文獻裡面提到說 EI 沒有考慮到該問題，但是可以做一個比較自然地拓展，即仍然考慮在已有的樣本點上選取一個最優的值作為最後的解，但是考慮選取已有樣本點上最優的後驗均值函式值，即

\mu^{**}_n = \max_{m<n} \mu_n(x_m)

。

Parallel evaluation：前面考慮的是每次給出一個試驗點，然後做實驗得到該試驗點是函式值；現在考慮每次給出一批試驗點，然後得到這一批試驗點的函式值。這樣做的好處是，在實際中，可以並行地對多個試驗點進行試驗以提高效率。在此情況下，很容易對 EI 做一定的拓展，即

【演算法】Bayesian Optimization

Multi-fidelity and multi-information source evaluation：考慮到實際中可能對於函式

f

的估計會有一些替代的方案。比如在神經網路超參調節上，可以在整個驗證集上進行 evaluate，這樣得到的估計比較準確，但是代價會比較大；也可以在部分驗證集上進行 evaluate，這樣估計的方差可能比較大，但是速度會比較快。該設定在我同學的離子阱實驗中也存在，比如可以透過 CCD 拍到的照片大致判斷溫度的好壞（比如照片上有沒有形成類似晶格的結構），也可以透過進一步的實驗來直接確定離子阱的溫度，但這樣實驗就會更復雜。這一類拓展就是在研究這個問題，在給出下一個試驗點的同時，也希望給出一個方案，告訴我們下一個試驗點使用怎樣的實驗條件來測量。

Random environmental conditions and multi-task Bayesian optimization：有時候我們希望最佳化在各種實驗條件下的平均效能，即

【演算法】Bayesian Optimization

注意到其中

\omega

為控制不同實驗環境的引數。這種情況下，其實可以對於每個試驗引數

x

都在不同的環境下測試，然後求和作為

f(x)

，但是這樣效率顯然不夠高。這種拓展條件下，會研究更有效率的方法。

［1］ Bishop， Christopher M。

Pattern recognition and machine learning

。 springer， 2006。 Chapter 6。4 Gaussian Process