기술 요약: BAXUS – 중첩 부분공간 내의 적응형 베이지안 최적화

문제 제기

고차원 베이지안 최적화 (HDBO) 는 수십 개에서 수백 개의 입력 차원을 가진 평가 비용이 높은 블랙박스 함수를 최적화하는 것을 목표로 합니다. 최근의 발전으로 베이지안 최적화 (BO) 의 범위가 생명과학, 신경 구조 탐색, 로봇공학 등의 분야로 확장되었지만, 차원이 증가함에 따라 최첨단 방법론들은 심각한 한계에 직면합니다.

기존 접근 방식은 일반적으로 두 가지 범주로 나뉘며, 둘 다 치명적인 단점이 있습니다:

1. 신뢰 영역 방법 (예: TURBO): 이들은 전체 입력 공간 내의 국소적 경계 영역 (신뢰 영역) 에서 최적화를 수행합니다. 중간 정도의 차원에서는 효과적이지만, 신뢰 영역이 문제의 전체 차원성을 유지하기 때문에 차원의 저주로 인해 매우 높은 차원에서는 성능이 저하됩니다.
2. 선형 임베딩 방법 (예: REMBO, HESBO, ALEBO): 이들은 저차원 "활성 부분공간"의 존재를 가정하고 고차원 입력 공간을 더 낮은 차원의 목표 공간으로 투영합니다. 그러나 이러한 방법들은 사용자가 활성 부분공간의 유효 차원 ($d_e$) 을 "추측"해야 합니다. 선택된 목표 차원 ($d$) 이 너무 작으면 부분공간이 전역 최적점을 표현할 수 없으며, $d$가 너무 크면 차원의 저주로 인해 최적화가 느려집니다. 또한 HESBO 와 같은 방법은 다른 임베딩에 비해 최적점을 포함할 수 있는 최악의 경우 보장이 낮은 무작위 해싱에 의존합니다.

핵심적인 과제는 활성 부분공간의 차원에 대한 사전 지식 없이 전역 최적점을 신뢰성 있게 찾으면서, 고차원 검색 공간과 관련된 성능 저하를 피하는 HDBO 방법을 개발하는 것입니다.

방법론: BAXUS

저자들은 최적화 공간의 차원을 동적으로 조정하는 이론적으로 근거를 둔 접근법인 BAXUS(적응형 확장 부분공간을 통한 베이지안 최적화) 를 제안합니다.

1. 적응형 중첩 부분공간

BAXUS 는 목표 차원을 고정하는 대신 중첩된 무작위 부분공간 계열에서 작동합니다. 알고리즘은 저차원 목표 공간 ($d_{init}$) 으로 시작하여 더 많은 데이터를 수집함에 따라 점진적으로 차원을 증가시킵니다.

• 초기화: BAXUS 는 작은 목표 차원 $d_0$로 시작합니다.
• 확장: 최적화가 진행됨에 따라 기존 목표 차원을 "분할"하여 목표 차원을 증가시킵니다. 이 과정은 목표 차원이 입력 차원 $D$와 대략 같아지거나 평가 예산이 소진될 때까지 계속됩니다.
• 관측치 유지: BAXUS 의 중요한 특징은 더 높은 차원으로 확장할 때 저차원 공간에서의 관측치를 유지할 수 있다는 점입니다. 목표 차원이 분할될 때, 기여하는 입력 차원들은 원래 차원과 새로운 구간 (bins) 에 재할당됩니다. 함수 값 (관측치) 은 새로운 차원으로 복사되어 저차원 단계에서 수집된 데이터가 고차원 단계에서도 유효하도록 보장합니다.

2. 희소 BAXUS 임베딩

BAXUS 는 목표 공간 $Y \in \mathbb{R}^d$를 입력 공간 $X \in \mathbb{R}^D$로 매핑하기 위해 새로운 희소 선형 임베딩을 활용합니다.

• 구조: 임베딩 행렬 $S^\top \in \{0, \pm 1\}^{d \times D}$는 희소하며, 각 열 (입력 차원) 은 정확히 하나의 0 이 아닌 항목을 가집니다.
• 구간 균형: 입력 차원을 목표 차원에 균일하게 무작위로 할당하여 가변적인 구간 크기를 초래하는 HESBO 와 달리, BAXUS 는 각 목표 차원당 기여하는 입력 차원의 수 (구간 크기) 가 최대 1 만큼만 다르도록 강제합니다. 이러한 "균형 잡힌" 할당은 입력 차원을 순열하고 $d$개의 구간으로 분할함으로써 달성됩니다.
• 이론적 이점: 저자들은 이 균형 잡힌 희소 임베딩이 유한한 입력 차원에 대해 HESBO 임베딩보다 엄격하게 더 높은 최악의 경우 성공 확률(목표 공간이 전역 최적점을 포함할 확률) 을 제공함을 증명했습니다. $D \to \infty$로 갈 때, BAXUS 의 성공 확률은 HESBO 의 성공 확률로 수렴합니다.

3. 신뢰 영역 및 분할 전략

BAXUS 는 TURBO 와 유사한 신뢰 영역 (TR) 접근법과 임베딩 확장을 통합합니다:

• 신뢰 영역: 최적화는 GP 길이 척도에 의해 스케일링된 목표 공간 내의 초직사각형 신뢰 영역 내에서 수행됩니다.
• 확장 트리거: 신뢰 영역의 기본 변 길이가 최소 임계값 아래로 떨어질 때 (현재 영역이 너무 작거나 알고리즘이 갇혔음을 나타냄) 목표 차원이 증가합니다.
• 실패 제어: 분할이 발생하기 전에 허용되는 "실패" (개선 없이 연속된 반복) 의 수는 현재 목표 차원에 따라 축소됩니다. 이는 알고리즘이 고정된 평가 예산 내에서 고차원에 도달할 수 있도록 보장합니다.
• 수렴: 알고리즘은 전역 수렴을 달성함이 증명되었습니다. 목표 차원이 입력 차원 $D$에 도달하면, BAXUS 는 전역 수렴이 알려진 TURBO 와 같은 행동을 합니다.

주요 기여

1. 알고리즘 개발: 저자들은 광범위한 고차원 작업에서 우수한 성과를 reliably 달성하고 현재 최첨단 방법론들을 능가하는 BAXUS 를 소개합니다.
2. 새로운 임베딩 이론: 그들은 세 가지 주요 특성을 가진 중첩 무작위 임베딩의 새로운 계열을 제시합니다:
   • HESBO 임베딩에 비해 전역 최적점을 포함할 수 있는 더 큰 최악의 경우 보장을 제공합니다.
   • 최적 희소 임베딩입니다. 즉, 동일한 입력, 목표 및 유효 차원에 대해 더 높은 최악의 경우 성공 확률을 가진 다른 희소 임베딩은 존재하지 않습니다.
   • 최적점을 포함할 확률은 입력 차원 $D \to \infty$로 갈 때 HESBO 확률로 수렴합니다.
3. 종합적 평가: 이 논문은 다양한 벤치마크에서 TURBO, SAASBO, ALEBO, HESBO, CMA-ES 및 무작위 탐색에 비해 BAXUS 의 우수성을 입증하는 광범위한 경험적 증거를 제공합니다.

실험 결과

저자들은 388 차원 하이퍼파라미터 최적화 작업, 124 차원 설계 문제, 그리고 알려진 활성 부분공간을 가진 벤치마크 (LASSO, MOPTA08, BRANIN, HARTMANN) 에서 BAXUS 를 평가했습니다.

• 성능: BAXUS 는 일관되게 최첨단 방법론들을 능가했습니다. 388 차원 SVM 벤치마크에서 BAXUS 는 적절한 목표 차원에 적응하여 TURBO 와 CMA-ES 보다 더 빠른 속도로 더 나은 해를 찾았습니다. 1000 차원 LASSO-HARD 벤치마크에서 BAXUS 는 활성 부분공간 구조에 의존하는 방법들 (SAASBO, ALEBO, HESBO) 을 포함한 모든 경쟁자들보다 훨씬 더 나은 해를 달성했으며, 이러한 방법들은 활성 부분공간 구조의 이점을 얻지 못했습니다.
• 강건성: BAXUS 는 관측 노이즈에 대한 강건성을 보여주었으며, SAASBO 와 CMA-ES 와 같은 경쟁자들이 성능이 크게 저하된 벤치마크의 노이즈 변형에서도 강력한 성능을 유지했습니다.
• 절대 연구: BAXUS 임베딩을 중첩 HESBO 임베딩으로 대체하면 성능이 현저히 저하되어 균형 잡힌 구간 할당 전략이 성공의 주요 동인임을 확인했습니다.
• 고정 임베딩과의 비교: BAXUS 는 고정된 목표 차원으로 TURBO 를 실행하는 것보다 우수한 성과를 보여주어, 적응형 확장 전략이 $d$의 정적 선택보다 우월함을 입증했습니다.

중요성 및 주장

이 논문은 BAXUS 가 실무자가 문제의 유효 차원을 "추측"할 필요가 없게 함으로써 현재 HDBO 방법론의 치명적인 한계를 해결한다고 주장합니다. 검색 공간을 적응적으로 확장함으로써 BAXUS 는 저차원 최적화의 효율성을 활용하면서도 검색 공간이 결국 전체 입력 공간을 커버하도록 보장하여 전역 최적점에 도달할 수 있음을 보장합니다.

저자들은 BAXUS 가 문제 구조에 대한 특정 가정 (예: 축 정렬 활성 부분공간 등) 을 요구하지 않고 다양한 고차원 작업에서 강건한 성능을 달성하는 "바로 사용 가능한 (out-of-the-box)" 최적화기라고 주장합니다. 이 연구는 조정 가능한 매개변수의 수가 많고 그 유효 차원이 알려지지 않은 과학 및 산업 응용 분야에서 고차원 베이지안 최적화를 더 접근하기 쉽고 신뢰할 수 있도록 만드는 것을 목표로 합니다.