KSOS-BO: Improving Sampling in Bayesian Optimization via Kernel Sum of Squares

기술 요약: KSOS-BO: 커널 제곱합을 통한 베이지안 최적화의 샘플링 개선

문제 제기
베이지안 최적화 (BO) 는 고비용 블랙박스 함수의 전역 최적화를 위한 표준 프레임워크로, 하이퍼파라미터 튜닝, 로봇공학, 과학적 설계 등에서 널리 사용됩니다. BO 절차는 두 단계로 구성됩니다. 먼저 대리 모델 (일반적으로 가우시안 프로세스) 을 적합시키고, 다음 쿼리 지점을 선택하기 위해 획득 함수 (acquisition function) 를 최적화합니다. 상당한 연구가 대리 모델 개선과 획득 함수 설계에 집중되어 왔으나, 획득 함수 자체의 최적화는 여전히 중요한 병목 현상으로 남아 있습니다. 실제로 이 내부 최적화 문제는 종종 비볼록, 다중 극값, 고차원적인 특성을 가집니다. 기존 무도함수 최적화기 (예: 차분 진화, CMA-ES, Sobol 탐색) 는 이를 일반적인 블랙박스 문제로 취급하여 획득 함수 지형의 구조적 특성을 명시적으로 활용하지 못합니다. 결과적으로 이러한 방법은 지역 최적점에 갇히거나 고품질 후보를 찾기 위해 과도한 평가를 요구하여 BO 과정의 전체 효율성을 제한합니다.

방법론: KSOS-BO
저자들은 획득 함수를 최적화하기 위해 고안된 커널 기반 무도함수 프레임워크인 KSOS-BO를 제안합니다. 이 방법은 BO 설정에 커널 제곱합 (Kernel Sum-of-Squares, KernelSOS) 접근법을 적용합니다.

1. 수식화: 핵심 아이디어는 획득 함수 $\alpha(x)$의 최소화를 도메인 내 모든 $x$에 대해 $\alpha(x) - c \geq 0$이 되도록 하는 가장 큰 하한 $c$를 찾는 전역 최적화 문제로 재형성하는 것입니다.
2. 커널 완화: 다항식 목적 함수로 제한된 고전적인 제곱합 (SOS) 방법과 달리, KSOS-BO 는 재생 커널 힐베르트 공간 (RKHS) 을 활용합니다. 유한 차원 다항식 기저를 커널 함수로 대체합니다. 비음수 제약 조건은 유한 개수의 샘플링 점으로부터 유도된 커널 행렬 $K$를 포함하는 반양정 계획법 (SDP) 으로 완화됩니다.
3. 최적화 및 복원: 알고리즘은 이동된 획득 함수의 커널 기반 대리 표현을 찾기 위해 SDP 를 풉니다. 입력 공간에서 직접 최적화하는 대신, 샘플링 점들의 가중치 조합으로 연속적인 후보 점 $x^*$를 복원합니다. 이를 통해 이 방법은 함수 평가만을 사용하여 구조화된 전역 탐색을 수행할 수 있습니다.
4. 통합: 각 BO 반복에서 KSOS-BO 는 현재 획득 함수를 평가하기 위해 점들을 샘플링하고, KernelSOS 대리 모델을 구성하며, 다음 후보를 찾기 위해 SDP 를 풀고, BO 모델을 업데이트합니다.

주요 기여

• 구조화된 전역 탐색: 이 논문은 획득 최적화에 KernelSOS 를 적용하는 새로운 방식을 소개하여, 가우시안 프로세스 대리 모델이 유도하는 획득 함수 지형의 매끄럽고 구조적인 특성을 활용하기 위해 일반적인 블랙박스 탐색을 넘어섭니다.
• 무도함수 프레임워크: 이 방법은 기울기를 요구하지 않으므로 표준 무도함수 설정과 호환되며, 휴리스틱 기반 집단 탐색에 대한 원칙적인 대안을 제공합니다.
• 성능 향상: 저자들은 SDP 단계로 인해 반복당 계산 비용이 더 높음에도 불구하고, KSOS-BO 가 고품질 해에 도달하기 위해 필요한 획득 평가 횟수를 줄여 실제 시간 (wall-clock time) 에서 더 빠른 수렴을 달성함을 입증했습니다.

실험 결과
저자들은 10 차원에서 다양한 지형 특성 (다중 극값, 그릇 모양, 계곡 모양, 평평한 모양, 급격한 하강) 을 가진 15 개의 벤치마크 함수에 대해 KSOS-BO 를 세 가지 무도함수 기준 (Sobol 탐색, 차분 진화, CMA-ES) 과 비교 평가했습니다.

• 후회 (Regret) 개선: KSOS-BO 는 15 개 벤치마크 중 10 개에서 최고의 성능을 보였습니다. 이러한 최상위 성능을 보인 함수들에서, 두 번째로 좋은 최적화기 대비 평균 후회 개선률은 **81.16%**였습니다.
• 실시간 효율성: KSOS-BO 는 반복당 더 높은 계산 오버헤드를 발생시키지만, 실제 시간에는 더 빠르게 수렴했습니다. 1 순위였던 10 개 벤치마크에서 평균 실시간 개선률은 **93.55%**였으며, 이는 기준선과 동일한 정확도에 도달하는 데 필요한 시간을 효과적으로 절반으로 줄인 것입니다.
• 지형 민감도: 이 방법은 고도로 다중 극값을 가진 함수 (예: Ackley, Rastrigin, Griewank) 와 매끄러운 단일 극값 함수 (예: Rosenbrock, Dixon Price) 에서 탁월한 성능을 발휘했습니다. 그러나 급격한 하강이나 평평한 고원 영역을 가진 함수 (예: Michalewicz, Zakharov, Styblinski Tang) 에서는 커널 기반 표현이 충분하지 않아 성능이 저하되었습니다.
• 강건성: 제거 실험 (ablation studies) 은 KSOS-BO 가 초기 설계 크기, 평가 예산, 커널 선택 (가우시안 대 라플라스) 의 변화에 대해 강건함을 나타냈으며, 대부분의 테스트 사례에서 일관되게 기준선보다 우수한 성능을 보였습니다.

의의 및 주장
이 논문은 획득 최적화 단계만 강화해도 전체 베이지안 최적화 성능에 측정 가능한 개선을 가져온다고 주장합니다. 주요 의의는 획득 최적화를 KernelSOS 완화를 통해 해결 가능한 구조화된 문제로 취급하는 것이 일반적인 블랙박스 문제로 취급하는 것보다 우월함을 입증한 데 있습니다.

저자들은 KSOS-BO 가 다양한 지형 구조에 효과적이지만 만능 해결책은 아니며, 급격한 하강이나 평평한 고원 같은 특정 기하학적 특징에서는 어려움을 겪는다고 겸손하게 지적합니다. 또한, 이 방법은 계산적 트레이드오프를 도입합니다. SDP 단계는 표준 진화 전략보다 비용이 더 들지만, 최적 해를 찾기 위해 필요한 고비용 함수 평가 횟수를 줄임으로써 이 비용은 정당화됩니다. 이 연구는 향후 방향이 KSOS-BO 의 확장성 개선, 지역 정제 (local refinement) 와의 하이브리드 전략 탐구, 그리고 고차원 또는 제약 조건이 있는 설정에서의 테스트에 초점을 맞춰야 함을 시사합니다.