저널클럽 BO | Expected Improvement, Deriving the Closed-Form Expression

Expected Improvement

Expected Improvement는 acquisition function 중 하나이다.

현재까지 관측된 값 중 최대값 $f_n^*$을 기준으로 새로운 샘플링 지점을 선택할 때 얼마나 더 나은 성과를 기대할 수 있는지 계산한다.

새롭게 얻은 데이터셋 $\mathcal{D}_{n+1}$에서 얻은 utility는 다음과 같다:

 

$$ u(\mathcal{D}_{n+1}) = \max \{ f_n^{*}, f_{n+1} \} $$

 

이에 따라, 현재까지의 utility $u(\mathcal{D}_n) = f_n^{*}$ 에서의 개선량(improvement)는 다음과 같다: 

 

$$ u(\mathcal{D}_{n+1}) - u(\mathcal{D}_n) = \max \{ f_{n+1} - f_n^{*} \} - f^*_n=\max \{ f_{n+1} - f_n^{*}, 0 \} $$

 

expectation operator를 도입하여 적분하면 다음과 같이 expectation improvement acquisition function이 나온다. 

$$ \begin{align*} \alpha_{\text{EI}}(x_{n+1}; \mathcal{D}_n) &= \mathbb{E} \left[ u(\mathcal{D}_{n+1}) -u(\mathcal{D}_n) \mid x_{n+1}, \mathcal{D}_n \right] \\ &= \int \max \{ f_{n+1} - f_n^{*}, 0 \} p(f_{n+1} \mid x_{n+1},\mathcal{D}_n) df_{n+1} \end{align*} $$

 

 

Deriving the Closed-Form Expression

closed form 표현으로 바꾸면 계산 속도를 크게 향상시킬 수 있기에 expected improvement의 acquisition function을 closed form 표현으로 나타내보면 다음과 같다:

$$
\begin{align*}
\alpha_{\text{EI}}(x_{n+1}, \mathcal{D}_n) &= \int_{-\infty}^{\infty} \max(f_{n+1} - f_n^*, 0) p(f_{n+1}\mid x_{n+1}, \mathcal{D}_n) df_{n+1} \\
&= \int_{\frac{f_n^* - \mu_{n+1}}{\sigma_{n+1}}}^{\infty} (\mu_{n+1}+ \sigma_{n+1} \epsilon - f_n^*) \phi(\epsilon) d\epsilon \\
&= (\mu - f^*) \int_{\frac{f^* - \mu}{\sigma}}^{\infty}\phi(\epsilon) d\epsilon + \frac{1}{\sqrt{2\pi}} \int_{\frac{f^* - \mu}{\sigma}}^{\infty} e^{-\frac{\epsilon^2}{2}} \epsilon d\epsilon \\
&= (\mu - f^*) \Phi \left( \frac{\mu - f^*}{\sigma} \right) + \sigma \phi \left(\frac{\mu - f^*}{\sigma} \right)
\end{align*}
$$

 

여기서 $\Phi(x)$는 표준 정규분포의 누적 분포 함수(CDF)이며, $\phi(x)$는 표준 정규분포의 밀도 함수(PDF)이다.

여기서 $p(f_{n+1} \mid x_{n+1}, \mathcal{D}_n) df_{n+1}$ 가 $\phi(\epsilon) d\epsilon $ 로 바뀌는 과정.

$f$ 와 $\epsilon$ 사이의 distribution transform을 적용

https://pbr-book.org/3ed-2018/Monte_Carlo_Integration/Transforming_between_Distributions

Transforming between Distributions

 

 

$f = \mu + \sigma\epsilon$ 에서 $\frac{df}{d\epsilon} = \sigma$ 이므로

$p(f)\sigma = p(\epsilon)$ 이 성립하는데, 표준화 식과 GP에 따라 $f,e$는 각각 다음과 같은 분포를 따르므로,

$$ f \sim N(\mu,\sigma^2), \epsilon \sim N(0,1^2) $$

$$
\begin{align*}
p(f_{n+1} \mid x_{n+1}, \mathcal{D}_n) df_{n+1} &=  p(f_{n+1} \mid x_{n+1}, \mathcal{D}_n) \sigma d\epsilon \\
&= \phi(\epsilon) d\epsilon
\end{align*}
$$

 

EI의 posterior mean $\mu_{n+1}$과 posterior std $\sigma_{n+1}$의 partial derivative가 모두 양수임을 통해 posterior의 mean, variance가 증가하면 EI 가 증가함을 기대할 수 있다.

즉, 다음 sampling 위치를 EI는 mean(예측한 objective function값 = exploitation), variance(함수값들이 존재할 수 있는 범위 = exploration)가 높은 곳을 보고 자동으로 고르게 된다.

$$ \frac{\partial}{\partial \mu_{n+1}} \alpha_{\text{EI}}(x_{n+1}; \mathcal{D}_n) = \Phi\left( \frac{\mu_{n+1} - f_n^*}{\sigma_{n+1}} \right) > 0 $$

$$ \frac{\partial}{\partial \sigma_{n+1}} \alpha_{\text{EI}}(x_{n+1}; \mathcal{D}_n) = \phi\left( \frac{\mu_{n+1} - f_n^*}{\sigma_{n+1}} \right) > 0 $$

 

최종적으로, EI의 closed-form expression(의미가 다양하지만 유한개의 항으로 이뤄진 표현이 좋을 것 같다. i.e 극한, 미분, 적분 등을 제외한 항들) 다음과 같다. 

$$
\begin{align*}
\alpha_{\text{EI}}(x_{n+1}; \mathcal{D}_n) = 
\begin{cases} 
(\mu_{n+1} - f_n^* - \xi) \Phi(z_{n+1}) + \sigma_{n+1} \phi(z_{n+1}), & \sigma_{n+1} > 0 \\
0, & \sigma_{n+1} = 0
\end{cases}
\end{align*}
$$

 

$$
\text{where} \quad z_{n+1} = 
\begin{cases} 
\frac{\mu_{n+1} - f_n^* - \xi}{\sigma_{n+1}}, & \sigma_{n+1} > 0 \\
0, & \sigma_{n+1} = 0
\end{cases}
$$

 

 

 

@book{liu2023bayesian,
  title={Bayesian Optimization: Theory and Practice Using Python},
  author={Liu, Peng},
  publisher={Springer}
}