BOHB: Robust and Efficient Hyperparameter Optimization at Scale

논문제목: BOHB: Robust and Efficient Hyperparameter Optimization at Scale

https://arxiv.org/pdf/1807.01774.pdf

Abstract

• 다양한 HPO 기법들 (GS, RS, BO, HB) 등이 나왔는데 BO, HB가 성능적으로 가장 우수하다는 평가를 받고 있다.
• BO는 최적의 솔루션을 찾아내지만 시간과 자원소모가 많고, HB는 효율적이지만 최적의 솔루션을 찾아준다는 보장이 없다.
• 그래서 2가지 방법의 장점들을 결합한 BOHB 기법을 소개한다.
• 2021년 HPO survey 논문을 기준으로 BOHB가 유일한 open source 기법이라고 한다.

Background

• BOHB는 기본적으로는 BO의 방법을 따르며 평가단계에서 HB를 사용하는 기법이라고 생각할 수 있다.

Bayesian Optimization

• BO는 이미 관측된 데이터 $D = \{(x_0,y_0), ... , (x_i,y_i)\}$ 를 사용해서 확률모델 $p(f|D)$ 을 사용해서 $f$ 함수를 근사시키는 문제라고 생각할 수 있다.
• 이때 목적함수 $f$ 를 근사시키는 surrogate model과 surrogate model을 목적함수에 근사시킬 수 있는 최적의 데이터를 선별하는 acquisition function을 사용한다.
• BO의 전반적인 과정은 아래와 같다.
• 그리고 이때 surrogate model은 GP, acquisition function은 EI를 주로 사용한다.

$$\begin{align}&(1) \ x_{new} = argmax_{x\in \mathcal{X}}a(x) \text { 를 만족하는 데이터 x를 찾아낸다.} \\&(2) \ \text{새로운 데이터 } y_{new} = f(x_{new}) + \epsilon \text{ 를 찾아낸다.} \\&(3) \ \text{surrogate model를 최적화시킬 새로운 데이터를 추가한다. } \\ &D \leftarrow D \cup (x_{new}, y_{new})\end{align}$$

 

Tree Parzen Estimator

• BO는 surrogate(GP), acquisition(EI)를 주로 사용하는데 이때 GP로 확률모델을 가정하는 것이 아닌 Parzen Window Density Estimation 기법을 사용한 방법이다.
  • Kernel Density Estimation 기법인데 Parzen Density Estimation 이 KDE의 한 기법이라는 말도 있고, 그저 KDE의 다른 명칭이라는 말도 있다.
• 또한 기존의 BO는 목적함수 $f$ 를 모델링하기 위해 $p(f|D)$ 를 직접적으로 사용했다. 하지만 TPE는 $l(x) / g(x)$ 라는 비율을 사용하여 새로운 데이터를 찾아내며 이때 임계값을 기준으로 데이터 성능값들을 나누고 그 후에 $l(x), g(x)$ 를 그리는 방법이 Parzen Window Density Estimation이다.

• TPE는 확률모델이 달라진만큼 EI도 다르게 계산해야 하는데, 식을 정리하면 결국 $l(x) / g(x)$ 에 비례하게 되서 이 비율만 계산하면 된다.

• 아래는 TPE의 과정을 대략적으로 담은 그림이다.

Hyperband

• Random Search 의 한 기법으로 multi-armed bandit 전략 중에 하나이다.
• 우리에게 주어진 자원을 모두 활용해서 각 모델을 학습시키는 것은 매우 비효율적이기 때문에 자원을 효율적으로 활용하고 검색도 다양하게 수행할 수 있는 방법이다.
• SuccessiveHalving 기법을 병렬적으로 수행하는 방법이라고 볼 수 있다.

Algorithm

BOHB

• BOHB의 샘플링 과정은 아래와 같다.

• BOHB는 KDE(TPE) 기법을 사용하기 때문에 기본적으로 최소한의 데이터 포인트($N_{min}$)가 필요하다. 논문에서는 이것을 $d$ 라는 하이퍼파라미터의 개수.로 설정했으며 $N_{min} = d+1$ 로 두었다.
• 또한 $l(x), g(x)$ 에 모두 충분한 데이터 포인트를 할당하기 위해 아래와 같이 설정했다.

$$ \begin{align} &N_{b,l} = max(N_{min}, q \cdot N_{b}) \\ &N_{b,g} = max(N_{min}, N_{b} - N_{b,l}) \\ &N_b: \text{Number of observations for budget} \ b \end{align} $$

• 이렇게 구한 데이터 포인터를 사용해서 EI를 최적화하고 새로운 데이터 포인트를 찾아내는 과정의 반복이 BOHB이다.
• 논문만으로는 정확한 과정을 이해하기 어려워서 소스 코드를 살펴봐야 할 것으로 보인다.
  • BOHB 기법을 구현해놓은 라이브러리: https://automl.github.io/HpBandSter/build/html/_modules/hpbandster/optimizers/bohb.html#BOHB

•