Bayesian Optimization (1)
( 참고 내용 : http://research.sualab.com/introduction/practice/2019/02/19/bayesian-optimization-overview-1.html , http://sanghyukchun.github.io/99/)
1. Introduction
Hyperparamter Tuning, 즉 최적의 하이퍼 파라미터값을 찾는 방법 중 대표적인 2가지로 Grid Search와 Random Search가 있다. (https://towardsdatascience.com/random-search-vs-grid-search-for-hyperparameter-optimization-345e1422899d 참고)
이 두 방법보다 효율적으로 탐색을 하는 알고리즘 중 하나가 바로 “Bayesian Optimization”이다. 이 방식에 대해 간단히 설명하자면, Bayesian Optimization은 objective function \(f(x)\) 를 최대화하는 최적의 \(x\)를 찾는 것을 목표로 한다.
이 알고리즘에 대해 이해 하기 위해, 다음의 두 가지에 대한 이해가 필요하다.
- 1 ) Surrogate Model
- 2 ) Acquisition Function
이 둘을 iterative한 방식으로 활용해서 최적의 값을 찾아나간다. 우선, (1) 지금 까지의 input ( \((x_1,f(x_1))\) ~ \((x_t,f(x_t)\) )들에 대한 surrogate model을 찾는다. 즉, objective function \(f(x)\)의 형태에 대해 (확률적) 추정을 한다. 그런 뒤, (2) 이 추정을 바탕으로 acquisition function을 maximize하는 다음의 input \(x_{t+1}\)을 찾는다. 그 다음에는 이 \(x_{t+1}\)를 포함하여 다시 (1) surrogate model을 찾고, 앞의 과정을 계속 반복한다 (1)->(2)->(1)-> .. (iterative way).
방금 간략히 설명한 내용을 보다 자세히 알아보자.
2. Surrogate Model
Surrogate Model : 현재까지 조사된 \((x,f(x))\)를 바탕으로, objective function의 형태에 대해 확률적 추정을 하는 모델 ( 주로 Gaussian Process를 확률 모델로 사용한다 )
직관적인 이해
아래 그림을 통해 보다 자세히 알아보자.
위 그림에서, 각 선/점은 다음을 의미한다.
- 검은 점선 : 실제 목적 함수
- 검은 실선 : 추정된 평균 함수
- 초록 실선 : acquisition function
- 파란색 영역 : 추정된 표준편차
- 검은색 점들 : 지금 까지의 input \((x,f(x))\)들
세 개의 그래프는 밑으로 갈 수록 iteration이 진행됨을 의미한다 ( 맨 위 : t=2 ~ 맨 밑 : t=4 )
우선 t=2 시점에서, 2 개의 input을 사용하여 surrogate model을 만들었다. 따라서 두 input과 거리가 멀어질 수록, 추정의 불확실정도, 즉 추정된 표준편차가 크다는 것을 확인할 수 있다 ( 파란색 면적이 점점 커진다 ) 하지만 밑으로 진행 될 수록 ( input이 많아질 수록 ), 그 불확실성이 줄어들어들게 되면서 실제의 목적함수와 가까워지는 것을 확인할 수 있다. 그러다 보면 최적의 input \(x^{*}\)을 찾을 수 있게 될 가능성이 높아질 것이다.
수식적인 이해 ( Gaussian Process )
위의 surrogate model이 어떻게 만들어지는지 알기 위해서, GP (Gaussian Process)에 대해 알아야 한다. GP는 x와 y의 관계를 나타내는 함수에 대한 확률적인 분포 ( \(p(f)\) )를 구한다. ( “함수”의 분포라는 점에서 낯설게 느껴질 수 있다. ) 우리가 이 분포를 구한 뒤, 새로운 input x에 대한 이 함수에 대한 분포의 평균(mean)을 구하면 이 값이 곧 우리가 추정하고자 하는 y값이다!
GP는 구하고자 하는 함수의 분포 \(p(f)\)가 multi-variate Gaussian Distribution을 가진다고 가정한다. GP를 정의하기 위해서는 우선 다음의 두 개의 함수를 먼저 정의해야 한다.
- mean function
- kernel function
Mean function \(m(x)\) 는 말 그대로 input x에서의 mean값을 반환하는 함수이다. Kernel Function은, input으로 들어온 x들 사이의 관계를 정의해주는 함수이다 ( 어떠한 covariance matrix를 가지는지 결정한다 ) kernel을 어떻게 설정하냐에 따라 다양한 방법이 있지만, 가장 간단한 squared-exponential kernel function은 다음과 같은 형태를 띈다.
이를 사용하여 우리는 다음과 같은 covariance matrix를 정의할 수 있다.
\(K =\) \(\bigl(\begin{smallmatrix} k_{1,1} & .. & & & & & .. &k_{1,n} \\ .. & & & & & & &.. \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ & & & & & & & \\ .. & & & & & & & ..\\ k_{n,1} & & & & & &.. & k_{n,n} \end{smallmatrix}\bigr)\)
( 여기서 \(k_{ij} := k(x_i,x_j)\) 이다)
그리고 Gaussain noise를 추가하고 나면, 우리는 y를 다음과 같이 표현할 수 있다.
\(y_i\) ~ \(N(f(x_i)\), ν\()\)
( ν : noise의 정도를 나타내는 hyper parameter )
3. Acquisition Function
Acquisition Function : Surrogate Model이 추정한 결과를 바탕으로, 다음에 함수 값에 조사할 x를 추천해주는 함수 ( EI (Expected Improvement)를 많이 사용한다 )
다음 input으로 어떠한 값을 추천해줘야 잘 추천해줬다고 할 수 있을까?
</br>
http://research.sualab.com/assets/images/bayesian-optimization-overview-1/bayesian-optimization-procedure-example-teq2.png
이 그림을 보면, 2개의 input이 있다는 것을 확인할 수 있다. 이 두 점 중, 오른쪽 점에서의 함수값이 더 크다는 것을 확인할 수 있다. 이는 곧 두개의 점 중 오른쪽 점 부근에서 더 나은 x값이 있을 확률이 높다는 것을 의미한다. 그래서 우리는 오른쪽 점의 약간 왼쪽 부근에서 acquisition function이 최대화된다는 것을 확인할 수 있다. 그 점이 바로 우리가 다음 input으로 추천해줄 x값이다. 이것을 우리는 exploitation이라고 한다. 강화학습에서도 배운 적 있듯, 지금 까지 주어진 정보로 최적의 선택을 하는 경우를 exploitation이라고 한다.
하지만 이 값이 항상 낫다고 할 수는 없다. 왜냐하면, 위 그림에서도 알 수 있듯 불확실한 구간 (파란색 영역이 넓은 구간)이 있기 때문이다. 그래서 우리는 항상 acquisition function이 maximize되는 점만을 고를 것이 아니라, 새로운 곳을 탐색, 즉 exploration을 할 필요도 있다.
이 둘의 균형은 매우 중요하다. 이 둘을 모두 잘 할수있도록 설계된 것이 바로 EI (Expected Improvement) 이다.
Expected Improvement
EI는 다음과 같이 두 가지를 고려한다.
- a) 새로운 input이, 지금까지 들어왔던 input들 보다 더 큰 output을 낼 확률은 얼마나 되는가?
- b) 더 큰 output을 낸다면, 그 “더 큰 정도”는 얼마나 되는가?
그림을 통해 알아보자.
</br>
( http://research.sualab.com/assets/images/bayesian-optimization-overview-1/probability-of-improvement-in-gaussian-process-example.png )
지금 까지의 input 중, 가장 큰 output을 냈던 input은 \(x^{+}\)였다. 그 다음 번 input이 될 \(x_3\) 이, 이전까지의 input들 중 가장 큰 output을 냈던 output값인 \(f(x^{+})\) 보다 클 확률은 “초록색으로 색칠된 넓이” 만큼이다. ( 위의 a)에 해당 )
새로운 input \(x_3\)가 내는 output의 평균 \(\mu(x_3)\) 와, 이전까지의 최대의 output이었던 \(f(x^{+})\)간의 차이도 함께 고려한다. ( 위의 b)에 해당 )
이 두 내용을 반영한 수식은 다음과 같다.
\[EI(x) = E[max(f(x)-f(x^{+}),0)]\] \[= \left\{\begin{matrix} (\mu(x)-f(x^{t})-\xi )\Phi(Z) + \sigma(x)\phi(Z) \;\;\;\;\;\;\;if \;\; \sigma (x)>0\\ 0 \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;if \;\; \sigma (x) =0 \end{matrix}\right.\]위 식에서 \(\xi\)는 exploration과 exploitation을 조절해주는 hyperparamter이다