Bayesian Optimization에 대해서 알아보자!

---

이번 포스팅에서는 하이퍼 파라미터 튜닝에서 많이 사용되는 Bayesian Optimization에 대해서 살펴보고자 한다.

 

- 목차 -

1. Bayesian Optimization이란 무엇인가?

2. Bayesian Optimization 알고리즘

3. 장단점

 

---

   1. Bayesian Optimization이란 무엇인가?

1) 정의

Bayesian Optimization은 어떤 함수의 최적값을 찾아가는 하나의 방법으로 Acquisition 함수를 이용하여 최적 파라미터와 최적값을 업데이트 한다.

---

2) 파헤치기

다음과 같은 상황을 생각해보자. 먼저 $x$가 주어지면 출력값이 나오는 함수 $y=f(x)$가 있다고 하자(물론 정확한 함수식은 모르는 상황이다). 이때 아래 그림은 $x$값이 4개가 있고 그에 대응하는 $y=f(x)$ 값을 그린 것이다.

 

---

이때 $y=f(x)$의 최소값과 그에 대응하는 $x$는 어디일까?

---

BO는 위 질문에 대한 답을 2가지 과정을 통해 찾는다. 1) 주어진 $x$를 통해 $f(x)$의 모양을 파악하고 2) Acquisition 함수를 이용하여 최적점을 업데이트 하고 이 과정을 반복한다.

---

a. 함수의 모양 파악하기

함수의 최적값을 찾는데에는 (맨 땅에 헤딩하는 것 보다는) 대략적인 함수의 형태를 파악하는 것이 좋을 것이다.  함수의 모양을 찾는 데에는 여러가지 방법이 있을 수 있지만 대표적으로 Gaussian Process(GP)를 이용하여 찾는다.

 

GP는 상한과 하한의 형태로 관측되지 않는 영역에 대한 불확실성 정도를 나타낼 수 있다(GP에 대한 내용은 다음 포스팅에서 다루겠다).

이때 주의할 점은 GP를 이용하여 추정한 함수(또는 함수의 모양)은 우리가 최적화할 실제 함수는 아니다. 정확한 함수식을 모르기 때문에 GP가 추정한 함수와 실제 함수는 차이가 있다. 

 

우리가 최적화할 함수의 실제 모양은 알 수 없기 때문에 실제 함수를 최적화하는 대신 BO는 GP가 추정한 함수를 최적화한다(이때 GP가 추정한 함수를 최적화 하고자할 실제 함수를 대체한다고 하여 대체 함수(Surrogate Function)이라고 한다).

---

b. 최적점 업데이트하기

BO에서는 Acquisition 함수를 이용하여 최적점을 업데이트 한다. Acquisition 함수는 관측되지 않는 점들에 대해서 최적값이 될만한 지점인지를 점수화해주는 함수이다(사람들의 면상을 보고 점수를 매겨서 높은 점수를 가진 자를 왕으로 세우려고 하는 것과 비슷할까?). 그리하여 높은 점수를 획득하는 점이 다음 최적점으로 업데이트 된다.

 

대표적인 Acquisition 함수는 GP Lower Confidence Interval(GP-LCI)과 Expectation Improvement(EI)가 있다.

 

(1) GP-LCI

 

GP-LCI는 GP로 추정한 함수의 하한선을 이용한 방법으로 하한선에서 최저점을 다음 최적값으로 업데이트 한다. 우리는 지금 함수 $f(x)$의 최소값을 이용하므로 하한선을 이용한 것이다. 만약 최대값을 구하는 문제라면 하한선이 아닌 상한선을 Acquisition 함수로 이용할 수 있다.

(2) EI

EI는 지금까지 관측된 최소값보다 더 아래에 최소값이 있을 가능성을 판단하기 위해 다음과 같은 수식을 계산한다.

$$\int_{-\infty}^{\infty} \max (0, y_{best}-y)p(y|x)dy $$

다시말하면 EI는 지금의 최소값보다 더 아래에 있는 지점을 거리로 환산해서 이 거리의 평균을 최대화하는 점을 찾는 것이며 EI값이 큰 곳에서 $f$의 값이 가장 작을 것이라고 추측한 것이다.

---

(3) 함수 모양 업데이트

(2)를 통해 새로운 최적점이 추가되면 함수의 모양을 업데이트 시켜준다. 업데이트 방법은 GP에서 사후 확률 분포를 계산한다(이 내용은 추후 포스팅 하겠다).

---

   2. Bayesian Optimization 알고리즘

Bayesian Optimization 알고리즘은 다음과 같다.

---

Algorithm

 

1 단계) 예산(Budget)을 설정한다. 예) 반복 횟수

 

2 단계) 주어진 데이터에 대해서 GP를 이용하여 함수의 모양을 학습한다.

 

3 단계) Acquisition 함수를 이용하여 최적점을 업데이트 한다.

 

4 단계) 예산이 남아 있거나 종료조건( 최적점의 위치가 변화)을 만족하지 않으면 2 단계)로 돌아간다. 그렇지 않은 경우 5 단계)로 넘어간다.

 

5 단계) 최적값과 최적점을 반환한다.

---

---

   3. 장단점

- 장점 -

a. 관측되지 않은 영역에 대해서 최적점 후보를 탐색할 수 있다.

기존까지 관측된 최적점만을 이용(Exploitation)하는 것이 아니라 Acquisition 함수를 이용하여 관측되지 않은 영역에서도 최적값이 있는지를 자동으로 탐색한다.

b. 변동성이 심한 목적함수(Noisy Objective Function)에 대해서도 그럴듯한 최적값을 찾아준다(Robustness).

---

- 단점 -

a. 입력 벡터 $x$의 차원이 커지면 알고리즘 속도가 느려진다.

GP를 이용한 함수를 추정하는 계산 비용이 입력 벡터 차원의 3제곱이라는 것이 알려져있다.

b. 전역 최적값을 찾지 못할 위험이 있다.

점근적으로 전역 최적값 찾을 수 있다(입력 포인트가 많아지면 지금까지의 최적값과 전역 최적값 사이의 차이가 0으로 수렴하는 성질)는 것이 알려져있으나 목적 함수의 계산 비용, Acquistion 함수가 Multi Modal인 경우의 최적화 문제의 어려움 등으로 인하여 전역 최적값을 실제로 찾지 못할 경우도 발생한다.

---

 

 

---

참고자료

Taking the Human Out of the Loop: A Review of Bayesian Optimization : https://www.cs.ox.ac.uk/people/nando.defreitas/publications/BayesOptLoop.pdf

---