Bayesian Optimization

Introduction

베이지안 최적화^{Bayesian Optimization, BayesOpt}는 함수의 최적화 문제를 해결하는 방법 중 하나, 목적함수 $f:\mathcal{X}\to\mathbb{R}$ 를 계산하는 비용이 클 때 사용할 수 있는 방법입니다. 함수의 계산비용이 클 경우 그래디언트를 계산하는 것 역시 큰 비용이 들기 때문에, 베이지안 최적화에서는 그래디언트 기반의 최적화 방법을 사용하지 않습니다. 이러한 방식의 최적화를 blackbox optimization이라고도 하는데, 베이지안 최적화는 이러한 blackbox optimization의 한 방법입니다.

BayesOpt

True function(oracle) $f$가 계산이 어렵기 때문에, 가능한 한 적은 횟수로 $f$를 계산하여 최적화를 수행하고자 합니다. 베이지안 최적화는 이러한 문제를 해결하기 위해 surrogate function과 acquisiton function이라는 개념을 이용합니다. 우선 베이지안 최적화의 전반적인 알고리즘을 살펴본 후, 이들에 대해 살펴보도록 하겠습니다.

베이지안 최적화는 Sequential Model-Based Optimization^SMBO의 한 방법입니다. 우선, 전반적인 최적화 알고리즘은 다음과 같습니다.

1. 랜덤한 쿼리 $x_i$들로부터 초기 데이터 $\mathcal{D}_0 = \lbrace (x_i, f(x_i))\rbrace _{i=1}^n$를 수집합니다.
2. 사후분포 모델 $p(f\vert \mathcal{D}_0)$을 초기화합니다.
3. $n=1,2,\ldots$에 대해 수렴할 때까지 다음 과정을 반복합니다.

   1. 다음 쿼리 $x_{n+1}$을 acquisition function을 사용하여 선택합니다.

      \[x_{n+1} = \arg\max_{x} \alpha(x\vert \mathcal{D}_n)\]
   2. $f(x_{n+1})$를 계산하고, \(\mathcal{D}_{n+1} = \mathcal{D}_n \cup \lbrace (x_{n+1}, f(x_{n+1}))\rbrace\)로 업데이트합니다.
   3. $p(f\vert \mathcal{D}_{n+1})$을 업데이트합니다.

이러한 방법을 sequential Bayesian optimization이라고도 하는데, 다음 그림과 같은 과정으로 나타낼 수 있습니다.

Source: K. P. Murphy, Probabilistic machine learning: advanced topics

위 그림에서 최적화 과정은 global maximum을 찾는 것입니다. 보라색 부분은 사후분포 평균의 신용구간^{credible interval}을 나타내며, 검은색 점은 각 단계에서 알고 있는 관측값들을 나타냅니다. 관측값이 직접 측정된 지점에서는 신용구간의 크기가 0임을 확인할 수 있습니다. 그림과 같이, 각 스텝에서는 acquisiton function $\alpha$를 최대로 하는 값(빨간색 삼각형)을 다음 쿼리 $x$로 선택합니다. 이 과정을 통해 함수에 대한 불확실성^uncertainty를 줄여나가며, 더 이상의 유의미한 탐색지점이 존재하지 않을 때 까지 이를 반복합니다.

Surrogate function

True function (Green) : $f=x\sin x$, 4 observed points

베이지안 최적화에서는 $f$를 직접적으로 이용하지 않습니다. 따라서, $f$를 어떤 형태로든 근사하는 방법이 요구됩니다. 이러한 관점에서 $f$를 대리^surrogate 한다는 의미를 담아 surrogate function 혹은 surrogate model을 정의합니다. Surrogate function은 현재 관측된 데이터 $\mathcal D$를 바탕으로 True function $f$에 대한 정보를 제공해줍니다. 따라서, 베이지안 관점에서 이는 목적함수의 사후분포

\[p(f|\mathcal D)\]

로 나타낼 수 있습니다. Surrogate function은 주어진 몇 개의 점만으로 함수의 모양을 추정해야 하기 때문에, 실제 함수를 모델링할 수 있게끔 유연(flexible)해야 합니다. 이러한 이유로, 가우시안 프로세스^{Gaussian Process}를 널리 사용합니다. 위 그림과 같이 가우시안 프로세스 회귀모형^GPR을 이용하여 $f$를 대리할 수 있습니다. 그림에서는 4 개의 데이터(빨간 점)만 존재할 때, 이를 바탕으로 $f$의 형태를 추론합니다. (가우시안 프로세스에 대한 자세한 내용은 이 글을 참고하세요.)

다만, 가우시안 프로세스 회귀모형은 $O(N^{3})$의 계산비용이 요구되기 때문에 (커널 행렬의 역행렬 연산), $N$이 커질 경우는 approximation이 필요합니다.

추가적으로, surrogate model을 MLP 구조로도 설정할 수 있습니다. Bayesian Neural Network을 이용하여 $p(f\vert \mathcal{D})$ 를 모델링 할 수 있습니다.

Acquisition function

Acquisition function은, 위 베이지안 최적화 알고리즘에서 새로운 점을 데이터셋에 포함시킬 때 해당 점의 효용성^utiliity를 정의하는 함수입니다. 정의는 다음과 같습니다.

\[\alpha(\mathbf{x}\mid \mathcal{D}_{n}) = \mathrm{E}_{p(y\mid x,\mathcal{D}_{n})}\left[U(\mathbf x ,y\; ;\mathcal{D_{n}})\right]\]

여기서 $U$는 기존 데이터셋 $\mathcal{D}_{n}$에 새로운 지점 $(x,y)$이 주어졌을 때의 효용을 나타내는 효용 함수^{Utility function}를 나타냅니다. 효용 함수를 정의하는 방식에 따라 몇 가지의 acquisition function이 정의되는데, 아래는 대표적인 몇 가지 acquisition function의 정의입니다.

PI : Probability of Improvement

베이지안 최적화의 각 단계에서 이전까지 관측된 데이터셋을 \(\mathcal{D}_{n}=(x_{i},y_{i})_{i=1}^{n}\) 라고 합시다. 그렇다면 목적함수의 최대화 관점에서 현재까지의 best value는 \(M_{n}=\max_{i=1}^{n}y_{i}\) 로 나타낼 수 있습니다. 이때 새로운 데이터가 현재까지의 best value보다 크다면, 해당 데이터는 높은 효용을 갖는다고 할 수 있을 것입니다. 이러한 관점에서 다음과 같이 효용함수를 정의할 수 있습니다.

\[U(x,y;\mathcal{D}_{n}) = \mathbb{I}(y > M_{n})\]

그렇다면, acquisition function은 다음과 같이 계산됩니다.

\[\alpha(x;\mathcal{D}_{n}) = \mathrm{E}\mathbb{I}(y>M_{n}) = p(f(\mathbf{x})>M_{n}\mid\mathcal{D}_{n})\]

이렇게 정의되는 확률을 probability of improvement^PI라고 합니다. 또한, 여기서 $f$에 가우시안 프로세스를 사용하는 이유가 등장하는데, \(p(f\mid\mathcal{D}_{n})\sim \mathcal{GP}(\mu_{n}(\mathbf{x}),\sigma_{n}(\mathbf{x}))\) 이면 위 확률은 다음과 같이 나타낼 수 있습니다. ($\mu_{n},\sigma_{n}$은 predicted mean, variance를 의미합니다)

\[\begin{align} \alpha_\mathrm{PI}(\mathbf{x};\mathcal{D}_{n}) &= \Phi(\gamma_{n}(\mathbf{x},M_{n}))\\ \gamma_{n}(\mathbf{x},\tau) &:= \frac{\mu_{n}(\mathbf{x})-\tau}{\sigma_{n}(\mathbf{x})} \end{align}\]

다음은 python으로 처음 살펴본 $f(x) = x\sin x$를 최적화하는 과정 (총 10 step)을 나타낸 애니메이션입니다. 주황색 선이 $\alpha_\mathrm{PI}$ 를 나타내며, 각 단계에서 $\alpha_\mathrm{PI}$가 최대화되는 지점이 새로운 데이터 포인트로 선택되는 것을 확인할 수 있습니다.

Baysian Optimization with PI

EI : Expected Improvement

앞서 살펴본 PI 방법은 직관적으로 말이 되는 것 같지만, 꽤나 치명적인 문제점을 가지고 있습니다. 바로, improvement가 이루어지기만 한다면 모든 점들이 전부 데이터셋에 포함될 수 있다는 것입니다. 함수에 따라서는 이것이 꽤나 큰 문제가 될 수 있습니다. 따라서 이를 해결하기 위해 개선의 정도를 고려하는 효용함수를 고려해보기로 합시다. 이는 앞서 indicator random variable에 개선의 정도를 곱한 형태로 정의할 수 있습니다.

\[U(\mathbf{x},y;\mathcal{D}_{n}) = (y-M_{n})\mathbb{I}(y>M_{n})\]

이 경우, acquisition function은 다음과 같이 주어지며, 이를 expected improvement^EI 라고 부릅니다.

\[\alpha_\mathrm{EI}(\mathbf{x};\mathcal{D}_{n}) := \mathrm{E}_{\mathcal{D}_{n}}\left[(f(\mathbf{x)}-M_{n})\mathbb{I}(f(\mathbf{x})>M_{n})\right]\]

마찬가지로, 가우시안 프로세스를 사용하는 경우에는 다음과 같은 closed form expression이 존재합니다.

\[\alpha_\mathrm{EI}(\mathbf{x};\mathcal{D}_{n}) = (\mu_{n}(\mathbf{x})-M_{n})\Phi(\gamma) + \sigma_{n}(\mathbf{x})\phi(\gamma) = \sigma_{n}(\mathbf{x})[\gamma_{n}\Phi(\gamma) +\phi(\gamma)]\]

여기서 $\gamma_{n} = \frac{\mu_{n}(\mathbf{x})-M_{n}}{\sigma_{n}(\mathbf{x})}$ 이며, $\Phi,\phi$는 표준정규분포의 누적분포함수와 확률밀도함수를 의미합니다. 위 식을 살펴보면, 첫번째 항은 예측 평균이 높은 지점을 선택하도록 하며(exploitation) 두번째 항은 예측 분산이 높은 지점을 선택하도록 합니다(exploration). 이를 통해, EI는 exploitation과 exploration을 모두 고려한 효용함수로 볼 수 있습니다. 즉, acquisition function을 최대화하는 과정에서 exploitation-exploitation trade-off를 고려할 수 있습니다.

다음 애니메이션은 위와 동일한 함수를 최적화하는 과정을 나타내며, 이번에는 EI를 사용하여 최적화를 수행합니다.

Baysian Optimization with EI

만일 예측 분산 $\sigma_{n}(\mathbf{x})$을 계산하기 어려운 경우에는 Monte Carlo 방법을 사용하여 $\sigma_{n}(\mathbf{x})$를 추정할 수 있습니다. 이는 다음과 같이 계산됩니다.

\[\alpha_\mathrm{EI}(\mathbf{x};\mathcal{D}_{n}) = \frac{1}{S}\sum_{i=1}^{S}\max(0,\mu_{n}^s(\mathbf{x})-M_{n})\]

UCB : Upper Confidence Bound

또 다른 방법으로는 Upper Confidence Bound^UCB 방법이 있습니다. UCB는 말 그대로 surrogate function의 신용구간을 이용합니다. 그 중 upper bound를 이용하며,

UCB는 다음과 같이 정의됩니다.

\[\alpha_\mathrm{UCB}(\mathbf{x};\mathcal{D}_{n}) = \mu_{n}(\mathbf{x}) + \beta\sigma_{n}(\mathbf{x})\]

대리함수로 GP를 이용하는 경우 이를 GP-UCB 라고도 합니다. $\beta$ 값은 exploration-exploitation trade-off를 조절하는 하이퍼파라미터로, $\beta >1$ 인 경우 exploration을 강조하고, $\beta <1$ 인 경우 exploitation을 강조합니다. 다음 애니메이션은 UCB를 사용하여 최적화를 수행하는 과정을 나타냅니다.

Baysian Optimization with UCB

KG : Knowledge Gradient

앞선 acquisition function들은, 주어진 surrogate function을 이용하여 다음 쿼리를 선택하는 방법이었습니다. 그러나, Knowledge Gradient^KG는 다음 쿼리를 직접 선택하는 것이 아닌, 다음 쿼리를 선택한 후의 효용을 고려합니다. 우선, 현재 데이터셋 $\mathcal{D}_{n}$에 한 개의 데이터 $(\mathbf{x},y)$ 를 추가했을 때 얻는 best value를 다음과 같이 정의합니다.

\[\begin{aligned} V_{n+1}(\mathbf{x},y) &= \max_{\mathbf{x}'}\mathbf{E}_{p(f\vert \mathbf{x},y,\mathcal{D}_{n})}[f(\mathbf{x'})] \\ V_{n+1}(\mathbf{x}) &= \mathrm{E}_{p(y\mid \mathbf{x},\mathcal{D}_{n})}\left[V_{n+1}(\mathbf{x},y)\right] \end{aligned}\]

\(p(f\mid \mathbf{x},y,\mathcal{D}_{n})\) 에 대해 기댓값을 취하므로 \(V_{n+1}(\mathbf{x})\) 는 새로운 데이터 포인트 $\mathbf{x}$에 대한 expected improvement를 나타냅니다. 이때, KG acquisition function는 다음과 같이 정의됩니다.

\[\alpha_\mathrm{KG}(\mathbf{x};\mathcal{D}_n) = \mathrm{E}_\mathcal{D_{n}} \left[(V_{n+1}(\mathbf{x}) - M_{n})\mathbb{I}(V_{n+1}(\mathbf{x}) > M_{n})\right]\]

EI 함수와 비교해보면, EI는 현재 단계에서 얻을 수 있는 best value를 사용하지만 KG는 다음 쿼리를 선택한 후의 효용을 고려한다는 점에서 차이가 있습니다.

다만, 관측값이 noise-free인 경우 (no $\epsilon$ term), KG 함수는 EI와 동일하게 나타납니다. 이는 noise-free인 경우, $V_{n+1}(\mathbf{x})$ 가 $f(\mathbf{x})$와 동일하기 때문입니다. 만일 noise가 존재한다면, $V$에 대한 직접적인 계산이 필요한데, 직접 계산할 수 없는 경우에는 Monte Carlo 방법을 사용하여 추정할 수 있습니다.

\[\alpha_\mathrm{KG}(\mathbf{x};\mathcal{D}_{n}) \approx \frac{1}{S}\sum_{i=1}^{S}\max(0,V_{n+1}^s(\mathbf{x})-M_{n})\]

여기서 $V_{n+1}^{s}$ 는 $y^{s}\sim p(y\mid \mathbf{x},\mathcal{D}_{n})$ 에서 샘플링하여 이를 데이터셋에 추가한 경우의 best value를 의미합니다.

Python 예시를 통해 acquisiton function들을 살펴보았는데, 공통적으로 최적화 목적함수 $f(x)=x\sin x$에 대한 정보를 사용하지 않았다는 점을 확인할 수 있습니다. 물론 여기서 다룬 목적함수는 매우 간단한 형태이지만, 최적화해야 할 대상이 매우 복잡한 경우에는 이러한 방법이 유용하게 사용될 수 있습니다. (e.g. Hyperparameter tuning in ML models)

References

• Agnihotri & Batra, “Exploring Bayesian Optimization”. Distill, 2020. Link
• K. P. Murphy, Probabilistic machine learning: advanced topics. in Adaptive computation and machine learning series. Cambridge, Massachusetts: The MIT Press, 2023.
• Python code on Here