BOHB - Robust and Efficient Hyperparameter Optimization at Scale

📄 Falkner, Stefan, Aaron Klein, and Frank Hutter. “BOHB: Robust and efficient hyperparameter optimization at scale.” International Conference on Machine Learning. PMLR, 2018.

들어가며

하이퍼파라미터 최적화 (HPO) 문제는 모델의 규모가 커지면 커질수록 그 중요성도 역시 커집니다. 이전에 포스팅한 Bayesian Optimization, Successive Halving Algorithm, Hyperband 모두 그 맥락에서 중요한 역할을 하는 알고리즘들을 다루고 있습니다. 이번 포스팅은 앞서 언급한 세 가지 알고리즘을 모두 결합하여 최근 가장 좋은 성능을 보이는 방법론인 BOHB에 대해서 다룹니다.

저자들은 HPO 문제를 해결하는 방법들은 다음의 요구 사항을 만족해야 말합니다.

1. 💪 Strong Anytime Performance (언제든 높은 성능)
   • 최근에 등장하는 모델들은 모두 큰 규모를 자랑합니다. 이 말인즉슨 한 번의 학습에도 긴 시간이 필요하다는 의미인데요. 따라서 적은 시간에도 랜덤 서치같은 방법 이상의 성능을 보여줘야 합니다.
2. 🏁 Strong Final Performance (최종 성능)
   • 이러나저러나 결국 모델을 배포할 때의 마지막 성능이 중요합니다. 랜덤 서치는 긴 시간을 들이더라도 큰 폭의 성능 향상이 어려운 만큼 좋은 HPO 방법은 높은 최종 성능을 보여야 합니다.
3. 🛤️ Effective Use of Parallel Resources (효율적인 병렬 처리)
   • 최근 대부분의 환경이 병렬 처리를 지원하는 만큼 효율적인 병렬 처리를 수행할 수 있어야 합니다.
4. 🚜 Scalability (확장성)
   • 최근 많은 모델들은 매우 많은 하이퍼파라미터를 갖고 있습니다. 모델의 구조, 최적화, 정규화 등 여러 범주의 하이퍼파라미터가 있습니다. 따라서 유용한 HPO 방법이라면 수십개의 하이퍼파라미터를 쉽게 다룰 수 있어야 합니다.
5. 🛠️ Robustness & Flexibility (강건성과 유연성)
   • 기본적으로 다양한 ML 문제에 적용 가능한 것이 당연한 일이지만 그렇게 쉬운 일은 아닙니다. 어떤 모델은 하이퍼파라미터에 민감한 반면, 어떤 모델은 일부 하이퍼파라미터만이 성능에 영향을 미칩니다. 따라서 유용한 HPO 기법이라면 어떤 상황에서도 좋은 성능을 내야 합니다. 또한 범주형, 정수형, 연속형 등 다양한 종류의 하이퍼파라미터를 효과적으로 처리할 수 있어야 합니다.

많은 HPO 기법들은 각각의 장단점을 갖고 있지만 위 요구 사항을 모두 만족하진 못했습니다. 저자들은 이 논문을 통해 이미 알려진 몇몇 기법을 결합해 위 요구사항을 모두 만족하는 방법을 제안합니다. 이 방법은 Bayesian Optimization보다 빠르게 좋은 솔루션을 찾고, 그 수렴 속도는 Hyperband 보다 빠릅니다.

Figure 1. 서로 다른 HPO 기법으로 신경망에 사용한 여섯 개의 하이퍼파라미터를 최적화한 결과입니다. Hyperband는 대부분의 시간대에서 높은 성능을 보이지만, 많은 시간이 지났을 때 성능 향상이 눈에 띄지 않습니다. 반대로 Bayesian optimization은 처음 결과가 나오기까지 많은 시간이 걸리지만 충분한 시간이 주어졌을 때 Hyperband보다 좋은 성능을 냅니다. 논문에서 제안하는 방법인 BOHB는 각 알고리즘의 장점을 결합한 결과를 보여줍니다.

Model-Based Hyperband

BOHB는 TPE와 Hyperband를 결합한 방식입니다. 논문에서는 각각의 방법을 자세하게 설명하고 있지만, 본 포스트는 이전에 포스팅한 내용으로 갈음합니다.

Hyperband는 위에서 언급한 다섯 가지의 요구사항 중 대부분을 만족합니다. 정확하게는 (1) 언제든 높은 성능, (4) 확장성, (5) 강건성과 유연성을 만족하죠. Bayesian Optimization은 (2) 최종 성능을 만족합니다. 저자들은 여기에 하나 남은 (3) 효율적인 병렬 처리를 가미합니다. 게다가 다음의 두 가지 특징도 곁들였습니다.

1. 🚅 Simplicity (단순성)
   • 단순할수록 검증하기 쉽고 다시 구현하기도 쉽다는 점에서 단순성은 그 자체로 중요합니다. Hyperband는 단순한 알고리즘이지만 Gaussian process 기반의 Bayesian optimization은 그렇지 못합니다. 하이퍼파라미터 집합에 대해 복잡한 MCMC 샘플링을 수행해야 하고, 데이터에 맞는 커널 함수 선택이 까다롭기 때문입니다.
2. 💻 Computational Efficiency (계산 효율성)
   • Hyperband는 적은 시간에도 많은 함수 계산이 가능하므로 일반적인 GP의 계산뿐만 아니라 복잡도가 조금 더 낮은 근사 GP에 대한 계산도 문제가 될 수 있습니다.
     • 일반적인 GP는 시간 복잡도가 $O(n^3)$에 달합니다.
   • 또한 복잡한 획득 함수 (acquisition function)을 계산하기 위한 복잡도 역시 병목 현상을 일으킬 수 있습니다. 이렇게 되면 병렬 처리의 효율성이 급감하게 됩니다.

이런 이유에서 BOHB의 Bayesian optimization은 GP가 아닌 TPE에 기반을 두고 있습니다.

알고리즘 상세

BOHB는 어떤 주어진 예산에 대해 몇 개의 하이퍼파라미터 설정의 성능을 계산할지 Hyperband를 이용합니다. 하지만 Hyperband와 다른 점은 SHA를 수행하기 전 최초 하이퍼파라미터 설정을 랜덤 샘플링이 아니라 모델 기반으로 탐색한다는 점입니다. 여기서 말하는 모델이 바로 Bayesian optimization입니다.

BOHB에서의 Bayesian optimization은 TPE와 매우 유사하지만 하나의 차이점이 있습니다. 원래 TPE는 하이퍼파라미터 설정이 몇 개이든지 1차원 커널 분포 추정 (KDE)을 하지만 BOHB에서는 하나의 다차원 커널 분포 추정을 합니다. 다차원 커널 분포 추정을 하는 이유는 여러 개의 하이퍼파라미터간의 상호 작용을 고려하기 위함입니다.

Algorithm 2. Pseudocode for sampling in BOHB

TPE는 성능이 좋은 하이퍼파라미터의 분포와 성능이 나쁜 하이퍼파라미터의 분포를 추정합니다. 이 분포 추정을 위해 사용할 최소한의 데이터 수 $N_\text{min}$ 을 설정합니다. 이때 하이퍼파라미터 수 $d$ 에 대해 $N_\text{min} = d+1$ 로 설정합니다. 또한 예산 $b$ 가 주어졌을 때 관측할 하이퍼파라미터 집합의 개수 $N_b = |D_b|$ 에 대해서 $q \cdot N_b \geq N_\min$ 만 만족하면 바로 분포 추정을 하도록 설정하였습니다. 여기서 $q$는 사전에 정한 percentile 값입니다. 정리하자면 좋은 분포와 나쁜 분포 $\ell(x)$와 $g(x)$의 분포를 추정하기 위한 최소한의 데이터 수는 다음과 같습니다.

\[\begin{aligned} N_{b, \ell} &= \max(N_\text{min}, q \cdot N_b) \\ N_{b, g} &= \max(N_\text{min}, N_b - N_{b, \ell}) \end{aligned}\]

Algorithm 2에서 두 번째 줄에서 알 수 있듯이 최적화 과정에서 BOHB는 항상 하이퍼파라미터 집합에 대해 관측한 성능 결과가 충분할 때의 가장 큰 예산 값에 대한 모델을 사용합니다.

\[b = \arg \max \{ D_b : |D_b| \geq N_\text{min} + 2 \}.\]

두 개의 분포에 대한 추정을 마쳤다면 EI를 최적화해야 하는데, $\ell^\prime(x)$ 라는 분포에서 $N_s$ 만큼의 데이터를 샘플링합니다. $\ell^\prime(x)$는 $\ell(x)$에서 bandwidth에 $b_w$를 곱한 분포가 됩니다. 따라서 분포의 smoothness가 높아지고 알고리즘이 더 많은 탐색을 하게 됩니다. 저자들은 bandwidth를 높임으로써 최적화 후반부에 수렴성이 높아지는 것을 확인했다고 합니다.

🤔 Bandwidth에 $b_w$를 곱하면?

커널 $K : \mathbb{R}^n \to \mathbb{R}^+$와 bandwidth $h > 0$에 대해서 kernel density estimator는 다음과 같습니다.

\[\hat{f}_h(x) = \frac{1}{n}\sum^n_{i=1} K_h(x - x_i) = \frac{1}{nh} \sum^n_{i=1} K \left( \frac{x - x_i}{h} \right).\]

이때 $h$ 값의 변화에 따른 추정 분포의 형태는 아래 이미지와 같습니다.

회색은 실제 분포, 빨간색은 h=0.05일 때의 KDE,
검은색은 h=0.337일 때의 KDE, 마지막으로 초록색은 h=2일 때의 KDE

이미지에서도 볼 수 있다시피 bandwidth가 클 수록 추정되는 분포가 넓게 퍼지는 것을 알 수 있습니다. TPE는 $\ell(x)/g(x)$ 가 가장 큰 점을 다음 탐색 후보로 두는데, bandwidth가 커짐에 따라 $\ell(x)$가 넓게 퍼지고 탐색할 후보의 폭이 넓어집니다. 즉 더 많은 탐색을 하게 되는거죠.

마지막으로 Hyperband의 이론적 보장을 위해 특정 확률 $\rho$로 임의의 랜덤 하이퍼파라미터 설정을 샘플링합니다. 이는 최악의 경우 랜덤 서치보다 $\rho$배 느릴 수 있지만 결국 알고리즘의 수렴을 보장하게 됩니다. 실제로는 Hyperband와 BOHB가 랜덤 서치보다 현저히 높은 성능을 보여줍니다.

병렬 처리

BOHB는 TPE와 Hyperband의 특성을 이용하여 병렬 처리를 합니다. TPE는 병렬 처리를 위해 EI를 최적화할 때 샘플 수를 제한하고, 다양한 결과를 위해서 완벽하게 최적화한 결과를 반환하지 않습니다. Hyperband는 동시에 다른 bracket에 대해 Successive Halving을 수행하고, 각 SH를 수행할 때 동시에 다른 하이퍼파라미터를 평가합니다.

BOHB는 우선 순차적인 Hyperband에서 가장 작은 예산이 필요한 SH부터 최적화를 시작합니다. 이때 (a) 모든 worker가 작업 중이거나 (b) SH로부터 충분한 수의 하이퍼파라미터가 샘플링 될 때까지 위 Algorithm 2를 수행합니다.

• (a)의 경우 worker의 작업이 끝날 때까지 기다려서 새로운 하이퍼파라미터를 샘플링합니다.
• (b)의 경우 병렬로 다음 SH를 수행합니다. 이때 관측 결과 $D$는 모든 SH 시행에 공유됩니다. BOHB는 각 시점에서 최고의 성능을 내는 하이퍼파라미터 구성을 추적하는 상시 알고리즘 (anytime algorithm)이기 때문입니다.