다양한 Hyperparameter Optimization 방법 리뷰

Machine Learning 알고리즘들은 강력한 성능을 보여주고 있다. 하지만 데이터가 커지면서 좋은 HyperParameter(HP)를 찾는 것은 점점 비용이 많이 드는 어려운 문제가 되었다. 보통 찾아야 하는 HP는 여러 개이고 그 범위가 클 수도 있기 때문에 좋은 HP 조합을 찾는 것은 어렵다. 이런 문제는 과거부터 있었고 다양한 방법이 제시되어왔다. 이에 대해 간단히 정리해본다.

 

1. Manual Search

Manual search는 사용하기 쉬운 방법이다. 사용자가 경험적으로 괜찮다고 여기는 HP 조합을 선정하여 tuning을 하는 방식이다. 경험이 부족하면 사용하기 어렵고 자동화된 알고리즘이 아니라 사용자의 시간을 많이 쓸 수 있다는 단점이 있다.

 

2. Grid Search

Grid search는 단순하지만 여전히 널리 사용되는 방법이다. 말 그대로 각각의 HP 구간을 정해놓고 일정 구간으로 잘라 모든 조합을 search 해보는 방식이다. 사용하기 쉬우면서도 좋은 성능을 보여 kaggle 같은 데이터 competition에서도 종종 사용되는 것으로 알고 있다. 

Figure 1. grid search ([1])

3. Random Search

Random search는 말 그대로 random 하게 HP를 뽑아 search 하는 방식이다. 이 방법은 HP의 개수, 구간이 클수록 성능이 저하되는 특징이 있다. 반대로 HP 개수가 적고 구간이 좁으면 괜찮은 성능을 보여준다. 하지만 성능이 guarantee 되지 않고 random 하다는 특성 때문에 많이 사용되지는 않는다.

 

4. Bayesian Optimization

Bayesian Optimization(BO)는 오래됐지만 좋은 성능을 내는 유명한 방법이다. 이 알고리즘은 black box model의 optimization을 위한 방법으로 HP search에서도 많아 사용된다. Black box model이란 실제로 evaluation 해보지 않으면 그 모델이 어떤 output을 낼지 모르는 모델을 말한다. 예를 들어 특정 HP(input)로 neural network를 학습시켰을 때 어떤 성능(output)을 낼지 실제 훈련해보지 않으면 모르는 경우가 이에 해당한다. 여기서 neural network 훈련이 evaluation 과정이고 한 번의 evaluation에 cost가 많이 들어가므로 이를 최대한 적게 하며 좋은 HP를 찾는 것이 목표이다. x가 input이고 black box model을 f(x)라고 할 때 $argmax_{x} f(x)$ (maximize 하므로 HP search에서는 f(x)가 학습이 끝난 모델의 valid accuracy 정도가 될 수 있다.)를 하는 과정이라고 생각하면 된다. 이를 위해 surrogate model과 acqusition function을 사용한다.

Surrogate model은 실제 evaluation 한 여러 (input, output) pair를 가지고 다른 지점에서의 성능을 예측하는 것을 담당한다(f(x)를 예측하는 모델을 찾는 것). 대표적으로 gaussian process나 bayesian neural network를 사용하여 posterior를 예측한다. Figure 2 위의 그림은 point 3개를 가지고 GP를 사용하여 예측한 모델이다. Posterior 이므로 mean(직선)과 variance(점선)를 함께 예측하여 나타내었다. 이미 evaluation 된 부분과 그 근처 영역은 variance(uncertainty)가 낮으며 멀리 떨어질수록 커지는 특징이 있다.

Acqusition function은 surrogate model로 추정한 전체 영역의 분포를 가지고 다음에 evaluation 할 point를 선택하는 역할을 한다. Figure 2 아래 그림을 보면 gp surrogate model에서 variance가 가장 큰 지점의 value가 가장 크게 나온 것을 볼 수 있다. 그 영역이 탐사해볼 만한 지점이니 다음에 evaluation 해보라는 것이다. 다만 항상 variance가 큰 지점을 선택하는 것은 아니고 acqusition function도 종류가 여러 개 있다. 보통 사용하는 방법은 Expected Improvement (EI)로 아래 식과 같이 나타낸다. $$ \int_{y*}^{\infty} (f(x)-y*) P(y|x) dy $$

y*은 여태까지 evaluation 한 f(x) 값 중 가장 최댓값(최적 값)을 나타내며 P(y|x)는 surrogate model로 예측한 posterior 분포이다. 식을 해석해보면 y*보다 큰 부분에 해당하는 영역이 크면서 mean값이 y*보다 클수록 expected improvement가 커진다. 그러므로 variance만 무조건 크다고 선택되는 것도 아니고 최적점 근처의 point만 선택되는 것도 아니게 된다. 이는 figure 3을 보면 알 수 있다. (Figure 3에서는 y*를 $f(x^{+})$로 표현하였으며 초록색 영역이 $ \int_{y*}^{\infty} p(y|x) dy $를 나타낸다.)

Figure 2. Surrogate model (GP) and Acquisition function ([2])

Figure 3. Expected Improvement([3])

전체적인 알고리즘은 Figure 4에 잘 나와있다. 이를 다시 써보면 아래와 같다.

1. Surrogate model을 사용하기 위해서는 evaluation 된 points가 필요하므로 random HP를 사용하여 evaluation 한다.
2. Evaluation된 point로 surrogate model f를 만든다. (GP 등을 사용하여)
3. Acqusition function을 maximize 하는 point(HP or x)를 고른다.
4. Evaluation 한다.
5. 2~4 과정을 충분히 반복한다.
6. 가장 좋은 성능의 모델을 return 한다.

Figure 4. BO algorithm ([2])

 

5. Hyperband

Bayesian Optimization 방법은 좋은 성능을 보여주지만 느리다는 단점이 있다. 게다가 sequential based 방법이라 parallelize도 어렵다. 한편 hyperband 방법은 매우 빠르며 좋은 성능을 보여준다. Hyperband는 Successive HAlving(SHA) 방법을 기반으로 한다.

SHA는 figure 5와 같은 방법으로 이루어진다. X축의 budget은 epoch이나 데이터 크기 등을 의미하는데 편의상 여기서는 epoch이라고 해보겠다. 그림처럼 처음 여러 개의 HP를 선택(random 하게 선택함)하여 evaluation 하되 모든 budget(R)을 사용하지 않고 일정 budget을 사용하여 평가하고 성능이 뒤떨어지는 비율($\eta$)을 정하여 제거해 나가는 알고리즘이다. 이는 모든 budget을 사용하지 않아도 최종 성능을 어느 정도 근사할 것이라는 가정을 한다. 다만 SHA 방법은 몇 개(n)의 HP로 시작하며, 어떤 구간(r)에서 줄여나갈지 정해 줘야 한다는 것이다. 이를 개선한 게 hyperband 알고리즘이다. 

Figure 5. successive halving ([5])

Hyperband 알고리즘은 최대 budget(R)과 step마다 줄어드는 비율($\eta$)을 주면 n과 r을 여러 개 만들어 SHA를 실행하게 된다. 예를 들어 R=81, $\eta$=3일 때 figure 6의 table처럼 여러 번의 SHA를 실행하는 것이다. SHA를 사용한 방법은 시간이 엄청나게 단축되며 parallelize가 가능(random sampling에 기반하므로)하다는 강력한 장점이 있다. 다만, 근본적으로 random sampling에 기반하기 때문에 HP search 범위가 넓으면 optimal 한 HP를 찾는 것은 어렵다는 것이 여러 논문에 나와있다([4], [5], [6]).

Figure 6. Example of hyperband ([4])

 

6. Bayesian Optimization Hyperband 

Bayesian Optimization Hyperband (BOHB) 방법은 Bayesian Optimization(BO)과 HyperBand(HB)의 장점을 합치며 단점을 개선한 방법이다. BO는 다른 방법보다 optimal solution을 찾는데 더 좋지만 시간이 오래 걸리고 parallelize가 불가하다는 단점이 있다. 반면 HB는 random sampling을 하므로 parallelize가 가능하며 시간이 덜 걸린다는 장점이 있지만 optimal solution을 찾는데 좋지 않다. 그러므로 surrogate model과 acquisition funciton을 사용하여 optimal solution을 찾는데 도움을 주며 evaluation을 할 때는 hyperband를 사용하여 BO와 HB의 장점을 살리고 단점을 극복하는 것이 BOHB의 핵심이다.

BOHB는 TPE([7]) 알고리즘을 사용한다. TPE는 기존 surrogate model에서 posterior(P(y|x))를 직접 예측했던 것과 달리 bayes rule을 사용하는 방법이다. Bayes rule은 $ P(y|x) = \frac {P(x|y) P(y)} {P(x)} $를 의미한다. 

P(x|y)는 figure 7, figure 8과 같이 y*를 기준으로 큰 값과 작은 값으로 나누고 해당 데이터들의 kernel density estimation을 통해 l(x), g(x)를 만들어 구한다. (kernel density estimation은 kernel을 사용하여 확률 밀도 함수를 만드는 것이다.([9]))

Figure 7. ([7])

Figure 8. ([8])

그리고 figure 9와 같이 Expected Improvement(EI)를 기존의 수식에서 P(y|x)를 bayes rule로 바꾸어 유도한다. 그러면 최종적으로 EI를 maximize 하는 것은 $\frac {l(x)} {g(x)}$를 maximize 하는 것과 같은 것이 된다(TPE, BOHB 논문에서는 위의 BO 설명과 다르게 $argmin_{x} f(x)$가 목적함수라서 EI식이 반대이다.). 즉 l(x)의 밀도가 높으면서 g(x)의 밀도가 낮은 영역(HP)을 찾는 것이 된다.

Figure 9. Expected Improvement in the TPE ([7])

BOHB는 evaluation시 HB를 사용하여 여러 개의 HP를 sampling 해와야 하는데 기존과 다르게 random sampling이 아니라 TPE를 사용하는 방법이다. 그런데 기존 BO는 EI가 maximize 되는 값 하나만 sampling 하여 evaluation 했기 때문에 여러 개를 sampling 하기 위해서는 다른 방법이 필요하다. 

1. y*보다 좋은 성능을 보이는 sample 중 몇 개($ N_{s} $)를 선택

2. bandwidth를 크게 하여 l'(x)를 구하고(bandwidth가 커질수록 다양성이 커짐) x를 하나 sampling.

3. $ N_{s} $개 중 $\frac {l(x)} {g(x)}$가 maximize 되는 값을 뽑는다.

이 과정을 반복하여 서로 겹치지 않는 HP를 여러개 sampling 하도록 만들었다. 이렇게 하면 parallelize도 가능하다는 장점이 있다. (사실 TPE를 쓰지 않고 Gaussian Process등의 posterior를 modeling하는 방법도 비슷하게 할 수 있을 것 같다.)

TPE modeling시 기존에는 full budget으로 이루어진 데이터들을 사용했다면 여기에서는 HB 알고리즘을 사용하므로 적은 budget의 데이터들로도 modeling이 가능하여 더 빠르게 surrogate model을 사용할 수 있다는 장점이 있다.

Figure 9. Results or BOHB ([6])

그 결과로 figure 9과 같이 BOHB는 HB만큼 빠르며 optimal solution까지 찾을 수 있는 좋은 결과를 얻었다.

 

Reference

[1] https://arxiv.org/abs/1912.06059

Grid Search, Random Search, Genetic Algorithm: A Big Comparison for NAS

[2] https://arxiv.org/abs/1807.02811

A Tutorial on Bayesian Optimization

[3] https://www.mdpi.com/2079-9292/8/11/1267/htm

An Approach to Hyperparameter Optimization for the Objective Function in Machine Learning

[4] https://arxiv.org/abs/1603.06560

Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization

[5] https://arxiv.org/abs/2003.05689

Hyper-Parameter Optimization: A Review of Algorithms and Applications

[6] https://arxiv.org/abs/1807.01774

BOHB: Robust and Efficient Hyperparameter Optimization at Scale

[7] https://proceedings.neurips.cc/paper/2011/file/86e8f7ab32cfd12577bc2619bc635690-Paper.pdf

[8] https://www.koreascience.or.kr/article/JAKO202025863869794.pdf

[9] https://darkpgmr.tistory.com/147

Kernel Density Estimation(커널밀도추정)에 대한 이해