넓고 얕은 베이지안 최적화(Bayesian Optimization) 설명

MLOps, AutoML의 시대가 도래하고 있다. 시대의 흐름에 맞춰 Hyperparameter를 튜닝하는데 Bayesiain Optimization를 사용해 보았다. 논문[1]을 기반으로 베이지안 옵티마이제이션에 대해 '넓고 얉게' 살펴보자.

키워드

Hyperparameter Tuning, Hyperparameter Optimization, Bayesiain Optimization, Gaussian Process, Expected Improvement

목차

* Hyperparmeter Optimization

* Bayesian Optimization

    * Gaussian Process

    * Acquisition Function

* 후기 및 잡담

 

Hyperparmeter Optimization

Bayesian Optimization을 알아보기 앞서 Hyperparmeter Optimization 문제가 무엇인지 알아보자.

 

$$
\max_{x \in A}f(x)
$$
$x: Hyperparameter(x \in \mathbb{R}^{d})$
$A: Feasible\ hyperparmeter\ set\ (ex. hyper\ rectangle: \{x \in \mathbb{R}^{d} : a_{i} \leq x_{i} \leq b_{i}\})$
$f(x): Objective\ function$

 

Hyperparmeter Optimization 문제는 "가능한 여러 hyperparameter 값들($A$)중에 모델의 평가 Metric($f(x)$)이 최대인(or 최소인) hyperparameter($x$)를 찾는 문제"이다. 전통적으로 가장 많이 쓰이는 대표 알고리즘으로 휴리스틱 방식으로 작동하는 Grid Search, Random Search 등이 있다. 하지만 휴리스틱은 방식은 '해본 것중에 가장 좋은 게 정답'과 같은 메커니즘으로 동작하기 때문에 Local optimum이라는 한계점이 존재한다. 이 문제를 해결하기 위해, 즉 Global optimum을 찾기위해 Bayesian Optimization이 등장한다.

Bayesian Optimization

Bayesian Optimization(BO)는 이름에서부터 알 수 있듯이 'Bayesian' 방식으로 프로세스는 아래와 같다.

 

Basic pseudo-code for Bayesian optimization [1]

(0) f를 Gaussian 분포라 가정
(1) f의 Posterior 확률분포를 추정/업데이트 (Gaussian Process)
(2) (1)에서 계산한 f의 Posterior 분포을 이용하여, Acquisition function을 최대화하는 x 탐색
(3) (2)에서 찾은 x로 f(x)를 계산 -> (1)에서 (x, f(x))를 사용
(4) (1)~(3) 과정을 N번 반복

 

BO에서는 두 가지 핵심 개념이 존재한다. Gaussian Process와 Acquisition Function이다. 프로세스 (0),(1)은 Gaussian Process가, (2)는 Acquisition Function가 담당한다. BO에서의 Gaussian Process는 "$f(x)$를 Gaussian (or Normal) 분포로 approximation하여 $f(x)$의 Posterior Distribution을 추정하는 과정"이다. $f(x)$를 직접 추정하는게 아닌, 분포로 approximation한다고 해서 Surrogate Model이라고 불리기도 한다. 그리고 Acquisition Function은 "새롭게 찾은 $f$의 Posterior 분포를 통해 가장 큰 $f(x)$를 갖는 $x$를 얻을 수 있고, 이렇게 얻은 x가 대해서 진짜 '최적'의 값인지 평가(Evaluation)하는 Function"이다.

 

BO의 다른 특징으로 'derivative-free'가 있다. 1차 미분, 2차 미분을 이용하는 방법론(ex. Gradient descent, Newton’s method)이 아니라는 것을 의미한다. BO에서 필요한건 Gaussian Process를 위한 $(x, f(x))$ 뿐이다.

 

그럼 아래에서 Gaussian Process와 Acquisition Function에 대해 자세히 살펴보자.

 

Gaussian Process

GP regression is a Bayesian statistical approach for modeling functions [1]

Gaussian Process(GP)는 Posterior probability distribution을 추정하는 기법으로 GP Regression이라 불리기도 한다. $f$에 GP를 적용하기 위해서는 "$f(x)$는 continious" 라는 가정을 만족해야한다. 이는 $f$를 gaussian 분포로 모델링하기 위해 필요한 가정이다.

 

GP를 더 풀어서 설명하면 "과거 iteration에서의 $(x, f(x))$가 'given' 되었을때, '새로운 $f(x)$'이 뽑힐 확률분포를 gassuian으로 가정 및 베이지안 방법론에 기반한여 추론하는 모델링"이다. '새로운 $f(x)$'이 뽑힐 확률분포는 $f$의 Posterior distribution 의미한다. 수식으로 표현하면 아래와 같다.

 

$$
f(x)|f(x_{1:n}) \sim Normal( \mu_{n}(x), \sigma_{n}^{2}(x) ) \\ \mu_{n}(x) = \Sigma_{0}(x,x_{1:n})\Sigma_{0}(x_{1:n},x_{1:n})^{-1}( f(x_{1:n}) - \mu_{0}(x_{1:n}) ) + \mu_{0}(x) \\ \sigma^{2}_{n}(x) = \Sigma_{0}(x,x) - \Sigma_{0}(x,x_{1:n})\Sigma_{0}(x_{1:n},x_{1:n})^{-1}\Sigma_{0}(x_{1:n},x)
$$

 

$x_{1:k} = x_{1}, ..., x_{k}$
$f(x_{1:k}) = [f(x_{1}),...,f(x_{k})]$
$\mu_{0}(x_{1:k}) = [\mu_{0}(x_{1}),...,\mu_{0}(x_{k})]$
$\Sigma_{0}(x_{1:k},x_{1:k}) = [\Sigma_{0}(x_{1},x_{1}),...,\Sigma_{0}(x_{1},x_{k});...;\Sigma_{0}(x_{k},x_{1}),...,\Sigma_{0}(x_{k},x_{k})]$
$\mu_n(x)$: Posterior Mean. A weighted average between the prior $\mu_0(x)$ and an estimate based on th data $f(x_{1:n})$
$\sigma^{2}_{n}(x)$: Posterior Variance. Prior covariance $\Sigma_{0}(x,x)$ less a term that corresponds to the variance removed by observing $f(x_{1:n})$

 

GP에서 가정한 $f$의 분포 gaussian은 prior와 posterior가 같은 Conjugate Prior[2]이다. Conjugate Prior는 posterior 계산을 쉽게 만든다는 장점이 있다. (베이지안을 들어본 분이시라면 $Posterior = Prior * Likelihood$라는 것을 알고 계실 것 이다.) 이 장점 때문에 posterior 분포가 '위 수식'으로 간단히(?) 정의가 된다. 이 수식에 $x$만 대입을 하면 $\mu_{n}(x)$, $\sigma_{n}^{2}(x)$를 구할 수 있고, 이를 통해 posterior $f$인 gaussian 분포를 구할 수 있게 된다. $\mu_{0}$는 상수, $\Sigma_{0}$는 Gaussian kernel, Matern kernel을 주로 사용한다고 한다. 수식에 대해 더 깊게 이해하고 싶은 신 분은 논문[1]의 본문과 GP Regression 증명[3]를 참고 바란다. 참고로 GP의 input인 ($x$, $f(x)$) 중 $f(x)$는 $f$를 계산된 값으로 'observable'하다. (ex.주어진 파라미터($x$)로 모델 학습 후 metric($f$)을 계산)

Acquisition Function

Acquisition Function은 "BO에서 $f$의 Posterior 분포가 주어졌을 떄, 어떤 x를 뽑는 것이 가장 좋은지"를 결정하는 함수이다. BO에서 사용하기 위한 가정으로 'noise-free'가 있다. noise-free는 Iteration을 통해 추정하는 여러 $f$들이 서로 독립이고 분산이 상수임을 의미하는 가정이다. 이 가정을 통해 $f(x)$만을 고려하여 Acquisition Function을 계산할 수 있다.

 

Acquisition Function으로 여러 함수들이 있는데, 가장 사용하기 쉬운 함수는 Expected Improvement이라고 한다. 아래에서 자세히 살펴보자.

 

Expected Improvement

$$
\mathrm{EI}_{n}(x) := E\big[ [ f(x) - f^{*}_{n} ]^{+} \big] \\ x_{n+1} = argmaxEI_{n}(x)
$$

• $n$: the number of times we have evaluated $f$
• $x_n$: the point sampled at iteration $n$
• $y_n$: the observed value$
• $f^{*}_{n} = max_{m≤n}f(x_{m})$
• $[a]+ = max(a, 0)$
• $E_{n}[.] = E[.|x_{1:n},y_{1:n}]$: the expectation taken under the posterior distribution given evaluations of $f$ at $x_{1},...,x_{n}$

 

Expected Improvement(EI)는 $f(x)$가 이전 iteration n에서의 최적값($f^{*}_{n}$)보다 얼마나 더 좋은지를 평가한다. 이제 우리는 "어떤 x가 optimal x인지"를 EI 통해 정할 수 있다. 참고로 EI는 closed form으로 L-BFGS-B라는 quasi-Newton 기법을 통해 최적해를 찾을 수 있다 한다. 자세한 수식은 논문[1]을 참고 바란다.

후기 및 잡담

하이퍼파라미터 튜닝에서의 BO 프로세스를 요약하면 아래와 같다.

 

x: 하이퍼파라미터, f(x): 모델의 metric
(0) (x_1, f(x_1)), ..., (x_n, f(x_n))가 주어지면
(1) GP를 통해 f의 gaussian 분포 추정 or 업데이트
(2) posterior f의 EI를 최대화하는 x 탐색
(3) (2)에서 얻은 x로 f(x) 계산(=모델 학습 및 metric 계산)
(4) (0)~(3) 과정을 n번 반복 후, 가장 큰 f(x)를 갖는 x를 optimal x로 선택

 

첫번째 느낀 점은 'BO는 더 좋은 Random search'라는 것이다. 데이터 크기가 클 경우, 시간이 오래걸린다는 근본적인 practical 문제는 BO로 해결할 수 없었다.  $f(x)$를 구하기 위해 모델을 학습하고 metric를 계산하는데 시간이 오래걸리기 떄문이다. 제한된 시간하에서는 iteration을 적게 줄 수 밖에 없어, GP가 제대로 학습되기까지 시간이 부족한 것이 문제인 것 같다. 하지만 BO는 처음부터 끝까지 랜덤인 random search와 달리 GP라는 베이지안 접근을 통해 iteration이 길어질수록 성능이 좋았던 하이퍼파라미터들을 찾아준다는 장점이 있었다. (학습이 어려운 문제들은 초반 iteration에서 최적값이 나오기도 했는데, 이건 어쩔 수 없는 것 같다.)

 

두번째 느낀 점은 "모델의 성능을 최고로 끌어올려야 하는 상황이 아니라면, BO로도 충분할 것 같다"는 것이다. 옛날에는 모델에 대한 감을 잡을 겸 Grid search로 하이퍼파라미터의 범위를 바꿔가며 한땀한땀 튜닝을 하는 것을 선호했었다. 하지만 튜닝에 들이는 시간을 줄이고 그 시간에 피쳐 엔지니어링과 같이 모델의 성능에 더 큰 영향을 주는 작업이나, 모델링 이후의 필요한 작업들을 하는 것이 생산성 관점에서 더 좋을 수도 있을 것 같다.

 

정형 데이터를 주로 다루는 업무 특성상 Gradient Boosting Tree를 주로 사용하는데, 이는 10개 안쪽의 파라미터로 BO를 적용할 수 있었다. 하지만 '아키텍쳐' 자체가 핵심이자 튜닝 대상인 딥러닝이라면 파라미터 수가 한도 끝도 없을 것이다. 그래도 컴퓨팅 파워의 발전으로 인해 딥러닝이 가능해졌던 것 처럼, 언젠가 딥러닝도 '쉽고 빠르게' AutoML이 가능한 시대가 오긴 할 것 같다.

Reference

[1] Frazier, P. I. (2018). A tutorial on Bayesian optimization. arXiv preprint arXiv:1807.02811.
[2] https://en.wikipedia.org/wiki/Conjugate_prior
[3] https://nzer0.github.io/From-LR-to-GP.html