기술적 요약: 베이지안 최적화에서의 탐색 탐구

문제 제기

베이지안 최적화 (BO) 는 확률적 대리 모델 (일반적으로 가우시안 프로세스) 을 순차적으로 구축하고 획득 함수 (AF) 를 통해 새로운 샘플링 지점을 선택함으로써 블랙박스 함수를 최대화하는 표준 방법입니다. 성공적인 BO 알고리즘의 핵심 구성 요소는 획득 함수가 탐색 (전역 최적점을 발견하기 위해 미탐사 영역을 검색) 과 활용 (잠재력 있는 영역에서 검색을 정교화) 사이의 균형을 잡는 능력입니다.

BO 커뮤니티는 서로 다른 AF 들이 다양한 정도의 탐색 선호도를 보인다는 점을 널리 인정하고 있지만, 이러한 특성을 정의하고 비교하기 위한 정량적 척도는 크게 부족합니다. 총 중심 거리 (TCD) 나 incumbent 거리와 같은 기존 지표는 다음과 같은 뚜렷한 단점을 겪고 있습니다: 초기 샘플이 최적점에 도달할 경우 실패할 수 있으며, 진동 행동을 포착하지 못하거나, 특정 지점으로부터의 거리를 진정한 탐색과 혼동할 수 있습니다. 또한, Upper Confidence Bound 와 같은 정보 이론적 방법과 같은 서로 다른 계열의 AF 들을 비교하는 것은 보편적인 척도 없이는 어렵습니다. 이러한 격차는 구체적인 실세계 문제에 대한 AF 의 체계적인 분석, 설계 및 선택을 방해합니다.

방법론

정량적 탐색 지표의 부재를 해결하기 위해, 저자들은 최적화 과정에서 선택된 관측치의 공간적 분포에 기반한 두 가지 새로운 접근법을 제안합니다:

1. 관측 이동 판매원 거리 (OTSD)

OTSD 는 검색 공간 내 모든 관측 지점을 연결하는 데 필요한 최소 유클리드 거리를 계산하여 탐색을 정량화하며, 이는 이동 판매원 문제 (TSP) 로 공식화됩니다.

• 정의: $t$개의 관측 지점 집합 $X_t$가 주어졌을 때, OTSD 는 각 지점을 정확히 한 번 방문하고 시작점으로 돌아오는 가장 짧은 경로의 총 길이입니다.
• 정규화: 원시 OTSD 는 관측 횟수에 따라 단조 증가하고 차원에 의존하므로, 저자들은 정규화된 OTSD를 도입합니다. 이는 원시 OTSD 를 차원 $d$와 점의 개수 $t$에 의존하는 이론적 상한선 $\Psi(d, t)$로 나누어 유도됩니다. 이 정규화는 서로 다른 문제 차원과 반복 횟수 간 비교를 가능하게 합니다.
• 계산: TSP 의 NP-hard 성질로 인해, 저자들은 $O(dT^2)$ 복잡도를 가진 삽입 휴리스틱 알고리즘을 사용하여 최적 경로 길이의 최대 두 배를 보장하는 경로를 생성합니다.

2. 관측 엔트로피 (OE)

OE 는 정보 이론을 사용하여 관측치의 데이터 분포의 균일성을 측정함으로써 탐색을 정량화합니다.

• 정의: OE 는 관측 지점을 확률 변수의 표본으로 간주하고 경험적 미분 엔트로피를 추정합니다. 더 높은 엔트로피 값은 점들의 더 균일한 분포를 나타내며, 이는 더 큰 탐색을 반영합니다.
• 추정: 저자들은 최근접 이웃 거리에 기반한 비모수적 Kozachenko-Leonenko (KL) 추정기를 활용합니다. 이 방법은 샘플 효율성과 중간 차원 공간 ($d \le 50$) 에서의 적용 가능성 때문에 선택되었습니다.
• 특성: OTSD 와 달리 OE 는 단조적이지 않으며 양수 또는 음수 값을 가질 수 있습니다. 반복에 따른 OE 의 증가는 AF 가 더 탐색적으로 변하고 있음을 시사하는 반면, 감소는 활용 쪽으로의 전환을 시사합니다.

주요 기여

1. 새로운 정량화 지표: 선택된 관측치에 기반하여 획득 함수의 탐색 행동을 특징짓는 최초의 전용 정량적 척도인 OTSD 와 OE 의 도입.
2. 실증 분류 체계: 획득 함수 탐색에 대한 최초의 실증 분류 체계의 생성. 다양한 벤치마크에 OTSD 와 OE 를 적용함으로써 저자들은 AF 들의 부분 순서를 확립합니다 (예: Random Search $\succeq$ UCB (높은 $\beta$) $\succeq$ 정보 이론적 $\approx$ KG $\succeq$ EI $\succeq$ PI $\succeq$ UCB (낮은 $\beta$) $\succ$ 결정적 선택).
3. 종합적 평가: 저차원에서 고차원까지 ($d=2$에서 $d=180$까지) 그리고 배치 평가, 신뢰 영역, RAASP 샘플링을 포함한 다양한 AF 변형에 대한 합성 및 실세계 벤치마크에 대한 광범위한 실험.
4. 이론적 경계: 제안된 추정기를 위한 통계적 기초를 제공하는 실제 OTSD 및 OE 값에 대한 이론적 상한선과 하한선의 유도.

결과

실험은 OTSD 와 OE 가 탐색 행동을 포착하는 데 효과적임을 검증합니다:

• 일관성: OTSD 와 OE 는 벤치마크 문제 전반에 걸쳐 강력하게 상관되어 신뢰성을 교차 검증합니다. 두 지표 모두 잘 알려진 탐색적 (예: Random Search, 높은 $\beta$의 UCB) 과 활용적 (예: PI, 결정적 선택) 전략을 성공적으로 구분합니다.
• 차원성 영향: 이 연구는 차원성이 탐색 행동에 상당한 영향을 미친다는 것을 밝혀냈습니다. 예를 들어, Thompson Sampling (TS) 은 저차원에서는 적당히 탐색적이지만 고차원에서는 과도하게 탐색적이 되어 종종 OTSD 에서 Random Search 를 능가합니다. 반면, Expected Improvement (EI) 는 저차원에서는 UCB 보다 더 탐색적이지만 고차원에서는 덜 탐색적이 됩니다.
• 기법의 영향:
  • 배치 처리: 더 큰 배치 크기가 다양한 점의 선택을 강제함에 따라 탐색을 증가시킵니다 (더 높은 OTSD/OE).
  • 신뢰 영역 (TRs) 과 RAASP: 일관되게 탐색을 감소시켜 더 활용적인 행동을 유도합니다.
• 성능 상관관계: 결과는 최상의 성능을 보이는 방법들은 일반적으로 극단적인 탐색량을 보이지 않는다는 것을 시사합니다. 대신, 균형 잡힌 탐색 - 활용 트레이드오프 (EETO) 를 유지합니다. 과도하게 탐색적인 방법 (고차원에서의 TS 등) 이나 과도하게 활용적인 방법은 종종 최적화 성능이 suboptimal 합니다.

중요성과 주장

이 논문은 이러한 새로운 척도들이 획득 함수의 설계를 더 원칙적이고 체계적인 방식으로 안내하는 기초를 제공한다고 주장합니다. 탐색을 정량화함으로써 실무자들은 다음과 같은 작업을 수행할 수 있습니다:

• AF 행동 진단: 특정 문제에 대해 AF 가 너무 탐색적 (예: 고차원에서의 TS) 이거나 너무 활용적인지 식별하여 경고 신호로 활용할 수 있습니다.
• 포트폴리오 구성: 필요한 탐색 수준에 따라 적절한 AF 나 조합 (예: 과도하게 탐색적인 AF 에 RAASP 추가) 을 선택합니다.
• 조기 종료: OTSD/OE 경향의 변화로 국소 최소값이 소진되었음을 감지하여 최적화 과정이 종료될 준비가 되었음을 시사합니다.

저자들은 결과가 실증적으로 견고하지만 연속 도메인으로 제한되며 현재 GP 하이퍼파라미터의 특정 효과를 고려하지는 않는다고 강조합니다. 향후 작업은 이러한 분류 체계를 비유클리드 도메인으로 확장하고 커널 및 가능도 하이퍼파라미터의 영향을 조사하는 것을 목표로 합니다.