[HPO] TPE (Tree-structured Parzen Estimator)
GP 기반의 베이지안 최적화 vs TPE
TPE는 베이지안 최적화의 한 종류로, Surrogate Model을 구성하는 방식이 GP 기반 BO와 다른 알고리즘이다.
다만 두 방식은 Surrogate Model이 모델링하는 확률 분포의 방향이 서로 반대이다.
| GP 기반 BO | TPE | |
|---|---|---|
| Surrogate가 모델링하는 것 | $p(y \mid x)$ | $p(x \mid y)$ |
| Surrogate Model | Gaussian Process | 두 개의 KDE (Kernel Density Estimator) |
| Acquisition Function | EI, PI 등 | $l(x)/g(x)$ |
| 특징 | 저차원, 연속형 변수에 적합 | 고차원, 범주형/조건부 변수에 적합 |
즉, GP 기반 BO는 하이퍼파라미터 조합 $x$를 쓰면 성능 $y$가 어떻게 나올지를 모델링하고, TPE는 반대로 성능이 좋은 (또는 나쁜) 하이퍼파라미터 조합 $x$는 어떤 분포를 가질지를 모델링한다.
TPE 과정
1. Initialization
GP 기반 BO와 동일하게, 무작위로 선택한 초기 하이퍼파라미터 조합으로 몇 번의 Trial을 수행하여 관측 데이터를 확보한다.
이 초기 데이터는 이후 Surrogate Model을 만드는 데 사용된다.
2. Surrogate Model
TPE의 Surrogate Model은 관측된 Trial 결과들을 성능 기준으로 두 그룹으로 나눈 뒤, 각 그룹의 분포를 추정하는 방식으로 구성된다.
먼저, 일정한 분위수 (quantile) $\gamma$를 기준으로 관측 데이터를 두 그룹으로 분할한다. (보통 $\gamma = 0.15 \sim 0.25$를 사용)
좋은 그룹: 성능 상위 $\gamma$에 해당하는 $N_l$개의 Trial
\[\mathcal{D}_l=\lbrace x_i\mid y_i<y^*\rbrace \tag{1}\]나쁜 그룹: 나머지 $N_g$개의 Trial
\[\mathcal{D}_g=\lbrace x_i\mid y_i\geq y^*\rbrace \tag{2}\]
위 수식에서 $y^*$는 $\gamma$에 해당하는 성능의 임계값을 의미한다.
이렇게 나뉜 두 그룹에 대해, 각 그룹의 하이퍼파라미터 분포를 KDE (Kernel Density Estimation)로 추정한다.
\[p(x \mid y) = \begin{cases} l(x) & \text{if } y < y^* \\ g(x) & \text{if } y \geq y^* \end{cases} \tag{3}\]$l(x)$: 좋은 그룹의 하이퍼파라미터 분포
\[l(x)=\frac{1}{N_l}\sum_{x_i\in\mathcal{D}_l}\frac{1}{h\sqrt{2\pi}}\exp\left(-\frac{(x-x_i)^2}{2h^2}\right) \tag{4}\]$g(x)$: 나쁜 그룹의 하이퍼파라미터 분포
\[g(x)=\frac{1}{N_g}\sum_{x_i\in\mathcal{D}_g}\frac{1}{h\sqrt{2\pi}}\exp\left(-\frac{(x-x_i)^2}{2h^2}\right) \tag{5}\]
위 수식에서 볼 수 있듯, 각 그룹의 분포는 각 관측점을 중심으로 하고 표준편차가 $h$인 작은 가우시안을 모두 더해 평균을 낸 형태이다.
실제 구현에서는 모든 관측점에 동일한 $h$를 적용하지 않고, 데이터가 밀집한 곳에서는 좁은 가우시안을, 듬성한 곳에서는 넓은 가우시안을 사용하도록 관측점마다 서로 다른 $h_i$ 값을 적용한다.
결과적으로 $l(x)$는 성능이 좋게 나오는 하이퍼파라미터 조합이 분포하는 영역을, $g(x)$는 성능이 나쁘게 나오는 하이퍼파라미터 조합이 분포하는 영역을 나타낸다.
3. Acquisition Function
TPE의 Acquisition Function은 두 KDE의 비율 $l(x) / g(x)$이다.
직관적으로, $l(x)/g(x)$가 큰 지점은 좋은 그룹에 속할 확률은 높고, 나쁜 그룹에 속할 확률은 낮은 지점을 의미한다.
즉, 다음에 평가했을 때 좋은 성능이 나올 가능성이 높은 지점이다.
Bergstra et al. (2011)은 이 비율 $l(x)/g(x)$가 GP 기반 BO에서 사용하는 Expected Improvement (EI)에 비례함을 수학적으로 보였다.
따라서 TPE도 결국 EI를 최대화하는 지점을 다음 탐색지로 선택하는 것과 동등하며, 이 점에서 베이지안 최적화의 하위 개념으로 분류된다.
실제 구현에서는 다음과 같은 절차로 다음 탐색 지점을 선정한다.
- $l(x)$에서 여러 후보 지점을 샘플링
- 각 후보에 대해 $l(x)/g(x)$ 값을 계산
- 그 중 가장 큰 값을 갖는 지점을 다음 Trial로 선택
4. Evaluation
선정된 하이퍼파라미터 조합으로 실제 모델을 학습시켜 성능을 측정하고, 그 결과를 관측 데이터에 추가한다.
이후 다시 Surrogate Model 단계로 돌아가며 루프를 반복한다.
TPE 예시
현재 learning rate를 최적화하는 중이며, 탐색 범위는 $\text{lr} \in [0.001, 0.2]$ 라고 가정해보자.
그리고 지금까지 총 10번의 Trial을 수행했고, 결과는 다음과 같다고 해보자.
분위수 $\gamma = 0.25$를 사용한다고 하자. 즉, 성능 상위 25%를 좋은 그룹으로 분류한다.
loss 기준으로 정렬하면 다음과 같다.