논문제목: 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} $$

  •  

'4. 논문리뷰 > Hyperparameter Optimization' 카테고리의 다른 글

HPO 정리  (0) 2022.10.20

Hyperparameter ?

  • ML 모델의 파라미터 또는 DL에서 신경망의 학습가능한 파라미터와 달리 설계자에 의해 learning rate, batchsize 등 학습초기에 고정되는 값

Hyperparameter Optimization

  • ML, DL 모델이 최고의 성능을 보여주는 하이퍼파라미터 값을 찾아내기 위해 수행하는 검색과정
  • 여러가지 방법들이 제안되었지만 AutoML: A Survey of the State-of-the-Art 에서는 3가지 방법을 소개했다.

1. Grid Search & Random Search

  • 하이퍼파라미터의 적용범위를 미리 지정해두고 그 안에서 최적의 값을 찾아가는 검색방법
  • Grid search
    • 하이퍼파라미터를 균일한 간격으로 분배하여 하나하나 적용&학습 후에 최적의 값을 찾아가는 방법
    • 매우 간단하지만 환경에 따라 자원소모가 매우 심해질 수 있다.
    • 이를 보완하기 위해 coarse-to-fine grid search 알고리즘이 제안되었다.
      • 이름 그대로 우선 grid를 coarse하게 나누어 가장 값이 좋은 위치를 대략적으로 찾아낸 후에 그 지점 인근에서 좀 더 세밀한 grid search를 수행하는 방법이다.
    • 또 다른 알고리즘으로 contracting GS algorithm 이 제안되었다.
      • coarse-to-fine grid search 와 원리는 유사한데 likelihood 값을 사용해 검색할 grid를 설정한다.
  • Random search
    • 하이퍼파라미터 공간 내에서 랜덤하게 검색을 수행하는 방법
  • AutoML: A Survey of the State-of-the-Art 저자에 의하면 아래와 같은 경우 때문에 RS가 더 좋은 방법이라고 한다. 하지만 RS, GS 모두 최적의 값을 찾아내기 위해선 많은 시간과 자원소모는 필수적이다.

  • 자원, 시간 소모를 해결하기 위해 제안된 방법이 Hyperband: A Novel Bandit-Based Approach to Hyperparameter Optimization 에서 제안한 Hyberband 알고리즘이다.

Hyperband

  • 기본적으로 Hyperband 알고리즘은 Successive Halving Algorithm(SHA) 를 기초로 한 RS이며 SHA의 단점을 보완한 알고리즘이다.

Successive Halving Algorithm(SHA)

  • Hyperparameter optimization 을 위한 알고리즘으로 동작과정은 아래와 같다.

  • Budget(B)는 모델 학습에 사용하게 될 자원의 양을 나타내며 epoch, data 등 학습에 투여될 모든 자원을 뜻한다. n 은 초기에 검색을 수행할 하이퍼파라미터 세팅의 개수를 의미한다. r 은 각 수행마다 사용할 자원의 양을 뜻하는 것 같다.
  • 위 2개의 값을 설정해주면 알고리즘이 반복수행하며 최적의 조건을 찾아내준다.
  • 반복수행 시마다 사용하게 될 파라미터 세팅과 Budget의 수는 매번 달라진다.

ex)

B = 64, n = 16

  1. 첫 수행에서는 r = 1의 자원으로 n = 16 개의 세팅을 검사한다. 그 중에서 상위 8개를 선별한다.
  2. 두번째 수행에서는 r = 2 의 자원으로 선별된 n = 8 개의 세팅을 검사한다. 다시 상위 4개를 선별한다.
  3. 세번째 수행에서는 r = 4 의 자원으로 선별된 n = 4 개의 세팅을 검사한다. 다시 상위 2개를 선별한다.
  4. 네번째 수행에서는 r = 8 의 자원으로 선별된 n = 2 개의 세팅을 검사한다. 다시 상위 1개를 선별하고 종료한다.
  • 위와 같은 방법으로 자원량을 서서히 늘려가며 최적의 값을 찾아낸다.
  • 하지만, SHA는 B, n 이라는 또 다른 하이퍼파라미터에 의해 그 성능이 달라진다.
  • Hyperband 는 그것을 보완한 방법으로 다수의 SHA 의 병렬 연산이라고 볼 수 있다.

Hyperband

  • Hyperband 의 작동과정은 아래와 같다.

  • R 은 budget 과 유사한 개념으로 어떤 SHA 에서 사용할 수 있는 최대의 자원량을 의미한다. η 는 선별한 하이퍼파라미터 세팅의 감소비율을 뜻한다. SHA 에서는 이 값이 2 였다.
  • R, η 값에 의해서 수행할 SHA 의 개수(s_max)가 정해지고 각각의 SHA 를 여기서는 bracket이라고 표현했다.
  • 각 bracket에서는 SHA 가 따로 작동하며 초기값( n, r ) 은 R, η 에 의해 다르게 설정된다.

ex)

R = 81, η = 3

  • 4개의 brackets(s)이 동작하며 각각 다른 n, r 값을 가지며 감쇄율을 동일하게 3이 적용된다.

  • 결국 조금 더 다양한 조건의 SHA 를 수행한다고 볼 수 있다.

2. Bayesian Optimization

  • RS, GS는 기존의 검색결과가 이후 검색결과에 영향을 주지 않는다. BO는 기존의 결과를 바탕으로 업데이트를 하기 때문에 보다 효율적으로 검색이 가능하다.

  • Surrogate function
    • Gaussian Process
    $$ k(x_{i}, x_{j}) = \sigma_{f}^{2}exp {-1\over{2l^2}}\Vert x_{i}-x_{j} \Vert $$
  • Matern kernel

  • Others
    • Random Forest
    • Neural Network
  • Acquisition Functions
    • Surrogate function의 mean, variance 가 모두 큰 지점을 찾아내는 함수
    • Probability of improvement(PI)
      • 새로운 관측치의 평균값이 지금의 평균값보다 클 확률을 모두 살피는 것

  • Expected Improvement
    • PI 에 가중치를 더하여 acquisition을 수행한다.

3. Gradient-based Optimization

  • 위의 3가지 방법들은 BlackBox HPO 이다. 즉, 설계자는 모델에 대한 정확한 정보를 알 수 없고, 입력과 출력만을 바탕으로 하이퍼파라미터를 최적화해간다. Gradient-based Optimization은 HPO에 gradient를 적용한 방법으로 HPO의 효율성을 높인 방법이다.
  • 리뷰 논문 목록

3.1. Gradient-based Hyperparameter Optimization through Reversible Learning

Abstract

  • 일반적으로 Hyperparameter 튜닝이 어려운 이유는 미분이 불가능했기 때문이다.
    • 단순히 discrete vs continuous value 의 문제가 아닌 근본적으로 가능한가의 여부를 말하는 것으로 보인다.
  • 해당 논문은 수십에서 수백개까지의 하이퍼파라미터를 ML 모델 학습의 한 가지 과정으로 엮어버려서 reverse-mode로 최적화가 가능한 Hypergradient 를 제안했다.

Algorithm

  • 거의 모든 ML 학습에서 사용되는 SGD의 관점에서 Hypergradient 적용했으며 연산 과정은 아래와 같다.

  • Algorithm 1은 일반적인 SGD 과정이며 algorithm 2는 최종 Loss 의 미분값을 하이퍼파라미터 (w, r, a, v, theta) 의 관점에서 계산하는 과정이다.
    • 기존에는 이 과정이 불가능했으며 algorithm 2의 과정이 이 논문에서 제안하는 내용의 핵심인것 같다.
  • 추가적으로 논문에서는 algorithm 2의 8번째 줄 연산에서 r 값에 의해서 반드시 정보의 손실이 발생한다고 했다. 일반적으로 r 값은 1보다 작은 값으로 설정해야 하는데 이 경우에 bit 정보의 손실이 발생하며 이것을 해결하기 위해서는 별도의 추가 저장소가 필요하다고 논문에서는 언급했다.
  • 하지만 막연히 별도의 저장 bit를 지정하는 것은 메모리의 낭비로 이어지기 때문에 r 값에 따라 적절히 메모리를 조절하는 알고리즘은 제안했다.

  • 위의 과정으로 저자는 하이퍼파라미터를 ML 학습의 한 가지 과정으로서 최적화가 가능하다고 했다.

Experiment

  • 저자는 크게 5가지 하이퍼파라미터에 대한 실험을 진행했다.

Learning rate

  • 실험은 4개의 layer로 이루어진 모델을 사용했으며 최종적으로 선택된 hyperparameter(learning rate) 의 모델이 최초의 모델보다 학습 성능이 좋게 나왔음을 보여주고 있다.

Regularization

  • regularization은 모델의 일반화 성능에 많은 영향을 주며 저자는 수천개의 hyperparameter 에 대해 세부적인 최적화를 진행하는 것이 중요할 것이라고 판단했다.
  • 아래의 figure는 0 ~ 9 MNIST 데이터를 사용해서 최종적으로 출력된 regularization 값을 시각화한 것이다. 정확히 어떻게 해석해야 할지는 모르겠지만 아마 저자는 0 ~ 9의 각 값마다 regularization이 다르게 나타났다는 점에 주목한 것으로 보인다.

Training data

  • 저자는 preprocessing, augmentation 등 학습 데이터 또한 최적화의 대상이 될 수 있다고 판단했다.
  • 아래의 figure는 모델의 성능을 높여주는 데이터의 픽셀을 시각화한 것이다. 마찬가지로 각 숫자마다 시각화된 영역이 다르게 나타났다는 점에 주목한 것으로 보인다.

Initial parameters

  • 해당 실험은 parameter들의 초기값조차 SGD 학습에 포함시킬 수 있는지 확인한 실험으로 보인다.
  • 하지만 저자는 이러한 실험은 모델 자체의 learning 과 하이퍼 파라미터 meta-learning 간의 구분점을 없애는 행위이며 그에 따라 이 실험은 진행하지 않겠다고 했다.

Model architeture

  • 마지막 실험은 모델의 layer 구조 자체도 SGD 에 포함시키겠다는 것이다.
  • 실험에서 사용한 데이터는 Omniglot 데이터로 그 중에서 5개의 알파벳만을 사용해 원본 데이터와 90도 회전시킨 데이터를 만들어 총 10개의 글자를 구분하는 multi-task 환경을 만들었다.
  • 총 10개의 3-layer neural network를 사용하였고, 각 글자(task)마다 어떤 layer weight를 사용하는지 확인해서 layer weight를 공유하는 task가 있는지 확인했다고 한다.(어떤 구조로 실험을 진행한 것인지 정확히 이해하지는 못했음)
  • 아래 figure는 실험결과로 위에서부터 각 task마다 별도의 network를 사용 / 첫 부분만 고정 / SGD로 학습하도록 설정한 결과이다. 진한 색으로 표시된 경우가 layer weight를 공유한 것이다. 결과적으로 마지막 경우가 가장 좋은 성능을 보여주었고 input weights는 거의 모두 layer를 공유했으며, 마지막 layer에서는 글자를 회전시킨 쌍( ex. 0번째, 6번째) 끼리는 weight를 공유하는 것을 확인했다.

3.2. Hyperparameter optimization with approximate gradient

Abstract

  • 모든 데이터에 대해 gradient를 계산하는 것은 시간소요가 매우 크기 때문에 일부의 데이터만 사용해 대략적인 gradient를 계산하여 사용하는 방법을 제안했다.
  • 이 방법을 사용해도 충분히 stationary point를 찾을 수 있으며 그에 대한 조건과 증명을 담은 논문

3.3. Forward and Reverse Gradient-Based Hyperparameter Optimization

Abstract

  • 1번 논문의 후속 논문으로 reverse-mode 의 단점을 라그랑지안 관점에서 해결하였으며 나아가 forward-mode optimization 을 제안했다.

Algorithm

  • 논문에서는 어떤 시스템을 아래와 같이 표현했다.
    • s : state 벡터, lambda: hyperparameter 벡터

  • 그리고 우리가 해결하고자 하는 문제는 특정한 함수 f 에 대해서 최소값을 얻을 수 있는 hyperparameter 값을 구하는 것이다.

  • 이때, f 함수는 error function 이며 아래와 같이 표현할 수 있다.

Reverse-mode

  • 위와 같은 조건에서 reverse-hypergradient는 아래의 조건을 해결하는 문제로 볼 수 있다.

  • 위 식을 계산하기 위해 라그랑지안 방적식을 세우면 아래와 같다.

  • L 에 대해 편미분 방정식을 세워서 식을 정리하면 최종적으로 아래와 같은 결과를 얻을 수 있다. 그리고 첫번째 수식이 이후 계산할 forward-hypergradient 와 같다는 것이 이 논문에서 증명한 내용이며 forward-mode로 실시간 hyperparameter update 가 가능함을 제안했다.

Forward-mode

  • 이번엔 forward-mode 의 관점에서 f 함수의 gradient를 계산하면 아래와 같다.

  • $s_t = \phi_t(s_{t-1}, \lambda)$ 라는 점을 이용해 s_t를 lambda에 대해 미분하면 아래와 같은 식을 얻을 수 있다.

  • 위의 식을 정리하면 reverse-mode에서 정의했던 A,B와 함께 아래와 같이 표현할 수 있다.

  • 위의 식을 다시 f 함수에 대해 정리한다면 아래와 같이 표현할 수 있으며 (15)의 수식이 아까 reverse-mode 유도했던 식과 같다는 것을 확인할 수 있다.

 

3.4. Gradient Descent: The Ultimate Optimizer

Abstract

  • 저자는 기존의 방법들은 learning rate와 같은 학습 관련 hyperparameter 만을 업데이트할 수 있으며, 그로 인해서 또 다른 hyperparameter들을 사용해야 한다고 지적했다.
  • 이 논문은 Adam 과 같은 SGD의 다양한 변형 optimizer 그 자체에 포함된 하이퍼파라미터도 최적화에 포함시킨다는 내용을 소개했다.

Algorithm

  • 일반적으로 모델의 weight는 아래와 같이 업데이트된다. (alpha = step size or learning rate)

  • 여기서 저자는 고정된 step size가 아니라 학습과정에서 자동으로 업데이트되는 step size를 사용할 것을 제안했다.

  • f(w) 함수를 step size(alpha) 에 대해 미분하면 다음과 같이 정리된다. 저자는 아래의 식을 통해 step size를 업데이트할때는 바로 전 단계의 weight만 저장해두면 되기 때문에 메모리적으로도 큰 문제없이 작동할 수 있다고 했다.

  • 다만 위의 경우는 매우 간단한 케이스였으며, 실제로는 더 다양한 파라미터를 고려해야만 한다. 이후의 내용은 backward AD 를 사용하면 더 복잡한 경우에도 쉽게 미분을 계산할 수 있으며 그에 대한 증명 및 구현을 소개한다.

4. Manual Search

  • 설계자가 수작업으로 하이퍼파라미터를 검색하는 방법
  • 특별한 알고리즘도 없이 매우 간단하지만 매우 비효율적인 방법

참고논문

'4. 논문리뷰 > Hyperparameter Optimization' 카테고리의 다른 글

BOHB: Robust and Efficient Hyperparameter Optimization at Scale  (0) 2022.10.20

+ Recent posts

티스토리툴바