📊 statistics

Taking the GP Out of the Loop

본 논문은 베이지안 최적화에서 가우시안 프로세스를 대체하여 피팅 및 획득 모두에 대해 선형 $\mathcal{O}(N)$ 스케일링을 달성함으로써 최대 50,000 개의 관측치를 가진 시나리오에서 제안 시간을 1~2 차수만큼 단축시키는 경량 대리 모델인 인식적 최근접 이웃 (ENN) 을 소개합니다.

원저자: Mehul Bafna, Siddhant anand Jadhav, David Sweet

게시일 2026-05-06

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Mehul Bafna, Siddhant anand Jadhav, David Sweet

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

최고의 케이크 레시피를 찾으려 하지만 요리책이 없다고 상상해 보세요. 케이크를 굽고, 맛을 보고, 그 결과에서 배워야 합니다. 이것이 베이지안 최적화 (BO) 가 하는 일입니다. 이는 다양한 옵션을 테스트하고 그 결과에서 배워 "최고의" 해결책 (완벽한 케이크와 같은) 을 찾으려는 지능형 탐색 알고리즘입니다.

문제: "느린 셰프"

과거에는 이러한 "베이킹" 실험이 매우 비싸고 느렸습니다 (화학 반응을 기다리는 데 며칠이 걸리는 것처럼). 따라서 알고리즘은 매우 신중하게 설계되어 몇 개의 케이크만 굽도록 고안되었습니다. 이미 구운 케이크들을 바탕으로 다음 케이크의 맛을 추측하기 위해 가우시안 프로세스 (GP) 라는 복잡한 수학적 도구를 사용했습니다.

그러나 GP 도구는 생각이 너무 많고 느린 셰프와 같습니다. 역사에 새로운 케이크를 추가할 때마다, 셰프는 추측을 업데이트하기 위해 처음부터 전체 역사를 다시 계산해야 합니다.

케이크가 10 개라면 빠릅니다.
케이크가 1,000 개라면 시간이 오래 걸립니다.
케이크가 50,000 개라면 (현대적인 빠른 컴퓨터로는 쉽게 가능한 일), 셰프는 계산에 너무 매몰되어 전체 과정이 멈추게 됩니다.

이 논문은 이러한 상황을 BOMO(Many Observations 가 있는 베이지안 최적화) 라고 부릅니다. 기존 방법은 현대 시뮬레이션의 속도를 따라갈 수 없었습니다.

해결책: "이웃 감시"

저자들인 메훌 바프나 (Mehul Bafna), 시드하트 아난드 자드하브 (Siddhant Anand Jadhav), 데이비드 스위트 (David Sweet) 는 TuRBO-ENN이라는 새로운 방법을 제안합니다. 느리고 생각이 많은 GP 셰프 대신, 인지적 최근접 이웃 (Epistemic Nearest Neighbors, ENN) 이라는 훨씬 더 간단하고 빠른 접근법을 사용합니다.

ENN 을 이웃 감시나 지역 소문 네트워크로 생각하세요:

작동 방식: "이 새로운 케이크는 어떤 맛일까?"라고 물을 때, ENN 은 50,000 개의 케이크에 대한 전체 역사를 다시 읽지 않습니다. 대신 이미 구운 가장 유사한 케이크들인 K 개의 가장 가까운 이웃만 살펴봅니다.
수학: 소수의 이웃들의 평균 맛을 취해 새로운 맛을 추측합니다. 또한 새로운 케이크가 그 이웃들로부터 얼마나 멀리 떨어져 있는지에 기반하여 얼마나 불확실한지 (불확실성) 도 추정합니다.
속도: 소수의 이웃만 살펴보기 때문에 케이크가 10 개든 50,000 개든 상관없습니다. 추측을 만드는 데 걸리는 시간은 거의 일정하게 유지됩니다. 이는 선형적으로 확장되므로, 방대한 양의 데이터가 있더라도 놀라울 정도로 빠릅니다.

두 가지 모드

이 논문은 이 새로운 방법이 두 가지 다른 시나리오에서 작동함을 보여줍니다:

노이즈가 있는 세계 (실제 생활): 때로는 같은 레시피로 두 번 구워도 오븐 온도가 변동하는 등 결과가 약간씩 다를 수 있습니다. 이 경우 TuRBO-ENN 은 데이터에 포함된 "노이즈"가 얼마나 되는지 빠르게 계산한 후, UCB(새로운 것을 시도하는 것과 작동하는 것에 머무르는 것 사이의 균형을 맞추는) 라는 간단한 공식을 사용하여 다음에 구울 최고의 케이크를 선택합니다.
완벽한 세계 (시뮬레이션): 때로는 컴퓨터 시뮬레이션이 완벽하여 매번 동일한 결과를 제공합니다. 이 경우 TuRBO-ENN 은 더욱 빨라집니다. "노이즈 추측" 단계를 완전히 건너뛰고 최고의 옵션을 찾기 위해 옵션들을 정렬하기만 하여 시간을 더 절약합니다.

결과

저자들은 가상 우주선 착륙부터 로봇 움직임 최적화에 이르기까지 다양한 문제에서 이 새로운 방법을 기존 "느린 셰프"(GP 를 사용한 TuRBO) 와 비교 테스트했습니다.

속도: TuRBO-ENN 은 의사결정을 내리는 속도가 기존 방법보다 10 배에서 100 배 더 빠릅니다.
품질: 훨씬 더 빠르고 간단함에도 불구하고, 느리고 복잡한 방법과 동등한 품질의 해결책을 찾았습니다.
확장성: 기존 방법이 단일 의사결정을 내리는 데만 붕괴되거나 몇 시간이 걸렸다면, 이 방법은 50,000 개의 관측치까지 속도를 늦추지 않고 성공적으로 처리했습니다.

결론

이 논문은 본질적으로 다음과 같이 말합니다: "우리는 무겁고 느린 수학을 루프에서 제거하는 방법을 찾았습니다." 복잡하고 전역적인 모델을 단순하고 지역적인 "이웃을 살펴보라"는 접근법으로 대체함으로써, 품질을 잃지 않고 훨씬 더 빠르게 최적화할 수 있습니다. 그들은 이 도구를 다른 사람들이 사용할 수 있도록 무료 소프트웨어 패키지로 제공하기도 했습니다.

기술 요약: GP 를 루프에서 제거하기

문제 정의

베이지안 최적화 (BO) 는 전통적으로 함수 평가 비용이 높아 관측치 ( $N$ ) 가 적은 블랙박스 문제에 사용되어 왔습니다. 그러나 **많은 관측치를 가진 베이지안 최적화 (BOMO)**라고 명명된 문제의 한 부류가 증가하고 있는데, 이는 대규모 시뮬레이션과 같은 빠르고 병렬화 가능한 평가를 포함하며, 여기서 $N$ 은 수만 개에 달할 수 있습니다.

BOMO 영역에서 표준 BO 방법은 확장성 병목 현상에 직면합니다. 전통적인 접근법은 가우시안 프로세스 (GP) 대리 모델을 의존합니다. 현대적인 구현이 획득 시간 복잡도를 $O(N^3)$ 에서 약 $O(N^2)$ 로 줄였음에도 불구하고, 매 반복마다 GP 하이퍼파라미터를 적합 (fitting) 해야 한다는 요구 사항은 여전히 상당한 계산 부담을 초래합니다. 이 적합 과정은 종종 커널 행렬의 재구성을 수반하며, $N$ 에 따라 성능이 저하되어 거대한 관측치 수를 가진 문제에 BO 를 적용하는 것을 방해합니다.

방법론

저자들은 TuRBO-ENN을 제안합니다. 이는 신뢰 영역 베이지안 최적화 (TuRBO) 프레임워크 내의 GP 대리 모델을 **인지적 최인접 이웃 (Epistemic Nearest Neighbors, ENN)**이라는 경량 대안으로 대체하는 방법입니다.

1. 인지적 최인접 이웃 (ENN)

ENN 은 함수 값과 불확실성 (인지적 및 우연적) 을 모두 선형 스케일로 추정하도록 설계된 K-최인접 이웃 (KNN) 기반 대리 모델입니다.

대리 모델 구성: 쿼리 점 $x$ 에 대해 ENN 은 관측 집합 $D$ 에서 $K$ 개의 최인접 이웃을 식별합니다. 각 이웃을 함수 값의 독립적인 추정치로 간주합니다.
불확실성 정량화:
- 우연적 분산 ( $\sigma_a^2$ ): 기본 노이즈 수준 ( $s_0^2$ ) 과 특정 관측치의 노이즈 스케일 ( $s_m^2$ ) 의 합으로 모델링됩니다.
- 인지적 분산 ( $\sigma_e^2$ ): 쿼리 점과 이웃 사이의 유클리드 거리의 제곱 ( $c_e d^2(x, x_m)$ ) 에 비례하도록 모델링됩니다.
집계: 최종 평균 추정치 $\mu(x)$ 와 분산 추정치는 $K$ 개의 이웃에 대한 정밀도 가중 평균 (역분산 가중) 을 사용하여 계산됩니다. 이는 GP 에서 요구되는 $O(N^2)$ 쌍별 공분산 계산을 피합니다.
복잡도: 최대 힙 또는 Faiss 라이브러리를 사용하여 $K$ 개의 최인접 이웃을 찾는 데는 쿼리당 $O(N \ln K)$ 가 소요됩니다. 하이퍼파라미터 ( $s_0, c_e$ ) 적합은 고정 크기 부분 표본을 사용하여 $O(N)$ 스케일을 유지하도록 근사화된 Leave-One-Out 교차 검증 (LOOCV) 의사가능도 (pseudolikelihood) 를 통한 제 2 형 최대가능도 추정 (MLE) 으로 수행됩니다.

2. TuRBO-ENN 통합

이 방법은 신뢰 영역을 사용하여 검색 노력을 집중시키는 TuRBO 알고리즘에 ENN 을 통합합니다.

노이즈가 있는 목적 함수: 노이즈가 있는 문제의 경우, 이 방법은 ENN 하이퍼파라미터를 적합하고 상한 신뢰 구간 (UCB) 획득 함수를 사용합니다: $UCB(x) = \mu(x) + \sigma(x)$ .
노이즈가 없는 목적 함수: 결정론적 문제의 경우, 저자들은 **적합 없는 변형 (fitting-free variant)**을 제안합니다. 노이즈가 0 임이 알려진 경우 하이퍼파라미터 적합이 불필요하므로, 이 방법은 $(\mu(x), \sigma(x))$ 쌍에 대한 **비우세 정렬 (Non-Dominated Sorting, NDS)**을 통해 후보를 선택합니다. 이는 적합 단계를 완전히 제거하여 제안 시간을 더욱 단축합니다.
의사 베이지안 최적화 (PBO): 저자들은 TuRBO-ENN 이 Chen & Lam, 2025 의 의사 베이지안 최적화 조건을 만족함을 검증하여 이론적 수렴 보장을 확보했습니다.

주요 기여

ENN 대리 모델: $O(N)$ 적합 및 쿼리 시간으로 함수 값과 불확실성을 추정하는 경량 KNN 대리 모델 도입. 이는 GP 의 $O(N^2)$ 또는 $O(N^3)$ 스케일링과 대조됩니다.
TuRBO-ENN 알고리즘: TuRBO 의 GP 와 톰슨 샘플링을 ENN 과 UCB(또는 노이즈 없는 경우 NDS) 로 대체하는 BO 방법 개발.
실증적 검증: 최대 50,000 개의 관측치를 가진 문제에서 TuRBO-ENN 이 TuRBO-GP 대비 제안 시간 (적합 + 획득) 을 1~2 차수 단축시키면서도 해의 품질을 희생하지 않음을 입증.
이론적 보장: TuRBO-ENN 이 PBO 방법으로 자격을 갖추어 수렴 보장을 계승함을 검증.
오픈 소스: ennbo Python 패키지 공개.

실험 결과

저자들은 TuRBO-ENN 을 5 가지 시뮬레이션 작업 (LunarLander, Hopper, BipedalWalker, Push) 과 차원이 12 에서 180 까지인 하이퍼파라미터 최적화 작업 (LASSO-DNA) 에서 최첨단 방법 (TuRBO-GP, Optuna, SMAC, CMA-ES, DNGO, Vecchia GP) 과 비교 벤치마크했습니다.

스케일링: GP 기반 방법 (예: turbo-one, ucb) 은 제안 시간에서 약 $O(N^2)$ 스케일링을 보인 반면, TuRBO-ENN 은 선형 ( $O(N)$ ) 으로 스케일링되었습니다.
가속: TuRBO-ENN 은 TuRBO-GP 대비 8.5 배에서 151 배까지의 속도 향상을 달성했으며, 관측치 수 ( $N$ ) 가 높을수록 그리고 하이퍼파라미터 적합이 생략된 고정 노이즈 (노이즈 없는) 설정에서 더 큰 이득이 관찰되었습니다.
해의 품질: TuRBO-ENN 은 모든 테스트된 작업에서 TuRBO-GP 와 동등한 최적화 성능 (해의 품질) 을 달성했습니다.
적합 작업: 순수 회귀 작업 (합성 데이터) 에서 ENN 은 Exact GP, SVGP, 신경망 대리 모델에 비해 적합 속도가 수백 배에서 수천 배 빨랐으며, 경쟁력 있는 테스트 세트 로그 가능도를 유지했습니다.

중요성 및 주장

이 논문은 시뮬레이션 능력이 성장함에 따라 베이지안 최적화의 병목 현상이 함수 평가 비용에서 최적화 알고리즘 자체의 계산 비용 (제안 시간) 으로 이동한다고 주장합니다. GP 를 루프에서 제거함으로써 TuRBO-ENN 은 전통적인 방법들이 계산적으로 불가능해지는 수만 개의 관측치를 가진 영역까지 BO 가 확장되도록 합니다.

저자들은 겸손하게도 이 방법이 BOMO 문제를 위한 실용적이고 확장 가능한 대안을 제공하며, 결정론적 시뮬레이션에는 "적합 없는" 옵션을, 노이즈가 있는 경우에는 선형 스케일링 옵션을 제공한다고 주장합니다. 이는 모두 베이지안 최적화의 이론적 수렴 속성을 유지합니다. 그들은 PBO 공리를 통해 수렴 보장을 달성하지만 특정 후회 (regret) 경계를 제공하지는 않는다고 지적합니다. 향후 연구 방향으로는 $O(\ln N)$ 스케일링을 위해 ENN 을 근사 최인접 이웃 알고리즘에 적용하고, 거리 척도에서 차원별 가중치를 탐색하는 것이 제안됩니다.