ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 넓고 얕은 베이지안 최적화(Bayesian Optimization) 설명
    Data Science 2022. 3. 7. 00:22

    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 ProcessAcquisition 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

    'Data Science' 카테고리의 다른 글

    Shapley value, SHAP, Tree SHAP 설명  (2) 2020.04.19

    댓글

MaIl: daehani.park@gmail.com