BONSAI: 자연스러운 단순성과 해석 가능성을 갖춘 베이즈 최적화
BONSAI: Bayesian Optimization with Natural Simplicity and Interpretability
한국어 초록
베이즈 최적화(Bayesian optimization, BO)는 블랙박스 함수의 표본 효율적 최적화(sample-efficient optimization)를 위해 널리 사용되는 기법입니다. 많은 응용 분야에서 튜닝 대상 파라미터는 정교하게 설계된 기본 설정(default configuration)과 함께 제공되며, 실무자들은 꼭 필요한 경우에만 이 기본값에서 벗어나기를 원합니다. 그러나 표준 BO는 기본값으로부터의 편차를 최소화하는 것을 목표로 하지 않으며, 실제로는 중요도가 낮은 파라미터를 탐색 공간의 경계로 밀어내는 경우가 많습니다. 이는 중요 변경사항과 무의미한 변경사항을 구분하기 어렵게 만들고, 최적화 목적함수에 관련 운영 고려사항이 누락되었을 때 추천된 설정을 검토하는 부담을 가중시킵니다. 본 논문에서는 획득 가치(acquisition value)의 손실(loss)을 명시적으로 제어하면서 기본 설정 대비 영향력이 적은 편차를 가지치기(pruning)하는 기본값 인식(default-aware) BO 정책인 BONSAI를 소개합니다. BONSAI는 기대 개선량(expected improvement)과 상한 신뢰 구간(GP-UCB)을 포함한 다양한 획득 함수(acquisition function)와 호환됩니다. 우리는 BONSAI에 의해 발생하는 후회(regret)의 이론적 상계를 제시하여, 적절한 조건 하에서 기본 GP-UCB의 무후회(no-regret) 특성을 유지하면서 무관한 변경사항을 제거함을 증명합니다. 다양한 실제 응용 전반에 걸쳐, BONSAI가 실행 시간(wall time)에 거의 영향을 주지 않으면서 경쟁력 있는 최적화 성능을 유지함과 동시에 추천 설정에서 기본값이 아닌 파라미터의 수를 실질적으로 줄임을 실험적으로 확인했습니다. BONSAI의 후보 생성 비용은 표준 BO 대비 평균 1.5배에 불과하여, 기존 희소(sparse) BO 기법들의 7~34배와 대비됩니다.
원문 초록
Bayesian optimization (BO) is a popular technique for sample-efficient optimization of black-box functions. In many applications, the parameters being tuned come with a carefully engineered default configuration, and practitioners only want to deviate from this default when necessary. Standard BO, however, does not aim to minimize deviation from the default and, in practice, often pushes weakly relevant parameters to the boundary of the search space. This makes it difficult to distinguish between important and spurious changes and increases the burden of vetting recommendations when the optimization objective omits relevant operational considerations. We introduce BONSAI, a default-aware BO policy that prunes low-impact deviations from a default configuration while explicitly controlling the loss in acquisition value. BONSAI is compatible with a variety of acquisition functions, including expected improvement and upper confidence bound (GP-UCB). We theoretically bound the regret incurred by BONSAI, showing that, under appropriate conditions, it retains the no-regret property of vanilla GP-UCB and removes irrelevant changes. Across many real-world applications, we empirically find that BONSAI substantially reduces the number of non-default parameters in recommended configurations while maintaining competitive optimization performance with little effect on wall time. Its candidate-generation cost averages only $1.5\times$ that of standard BO, compared with $7$-$34\times$ for prior sparse-BO methods.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
커널 밴딧(Kernel Bandits)에 대한 일반적인 $\widetildeΩ(\sqrt{Tγ_T})$ 하한
A General $\widetildeΩ(\sqrt{T γ_T})$ Lower Bound for Kernel Bandits
커널 밴딧(kernel bandit) 문제는 주어진 재생 커널 힐베르트 공간(Reproducing Kernel Hilbert Space, RKHS)에서 유계 노름(bounded norm)을 갖는 미지의 함수를 잡음이 있는 피드백(noisy feedback)을 통해 순차적으로 최적화하는 문제이다. 커널 밴딧의 후회(regret) 분석에서 중심이 되는 양은 최대 정보 획득량(maximum information gain) $γ_T$이다. 특히, 기존에 알려진 가장 좋은 상한(upper bound)은 로그 항(log factor)을 제외하면 $\sqrt{Tγ_T}$로 스케일링되며, 제곱 지수(squared exponential) 커널과 마테른(Matérn) 커널과 같은 특정 커널에 대해서는 이와 거의 일치하는 하한(lower bound)이 도출되어 왔다. 그러나 일반적인 커널에 대한 하한은 부족하여, 어느 정도의 일반성에서 상한이 근사 최적(near-optimal)인지가 불분명하다. 본 논문에서는 콤팩트 정의역(compact domain) 상의 비상수 연속 커널(non-constant continuous kernel)에 대해 일반적인 $Ω(\sqrt{Tγ_T/\log T})$ 미니맥스 후회 하한을 수립하여, 매우 일반적인 의미에서 (로그 항 범위 내에서의) 근사 최적성을 입증한다. 우리는 이 하한에 나타나는 로그 항이 일반적으로는 피할 수 없음을 보이지만, 특정 조건 하에서는 이를 제거할 수 있음을 보인다. 특히 우리의 결과는 $ν\in (0,2)$인 마테른-$ν$(Matérn-$ν$) 커널, $γ\in (0,2)$인 $γ$-지수(γ-exponential) 커널, 그리고 특정 조각별 다항식(piecewise-polynomial) 커널에 대해 미니맥스 최적 스케일링이 (상수 인자 범위 내에서) 정확히 $Θ(\sqrt{Tγ_T})$임을 함의한다.
1단계 룩어헤드 베이지안 최적화의 리그렛 보장을 향하여
Towards Regret Guarantees for One-Step Lookahead Bayesian Optimization
본 논문에서는 1단계 룩어헤드(one-step lookahead) 베이지안 최적화(BO) 기법의 이론적 보장을 연구한다. 엔트로피 탐색(entropy search)과 같은 1단계 룩어헤드 BO 기법들의 실증적 유효성은 광범위하게 연구되어 왔으나, 이러한 기법들은 계산적으로 다루기 힘든 근사에 의존하는 경우가 많으며 리그렛(regret) 보장은 여전히 충분히 개발되지 않은 상태이다. 이에 따라 본 논문에서는 사후 표본추출(posterior sampling)과 몬테카를로 근사만을 필요로 하는 1단계 룩어헤드 BO 기법인 최적점 분산 감소(OVR)를 분석한다. 연구진은 획득 함수(acquisition function) 계산 시 입력 도메인 전반에 대한 균일한 몬테카를로 추정 오차 한계를 도출한다. 나아가 탐험을 촉진하도록 약간 수정한 정규화된 OVR이 점근적으로 0으로 수렴하는 베이지안 기대 단순 리그렛 상한을 달성함을 보인다. 마지막으로 수치 실험을 통해 OVR 및 정규화된 OVR의 성능을 검증한다.
Balancing Expressivity and Learnability in Quantum Kernel Bandit Optimization
베이지안 최적화를 위한 톰슨 샘플링의 후회 경계에 대하여
On Regret Bounds of Thompson Sampling for Bayesian Optimization
우리는 목적 함수가 GP(가우시안 프로세스)의 샘플 경로라는 가정 하에 널리 사용되는 베이지안 최적화 방법인 가우시안 프로세스 톰슨 샘플링(GP-TS)을 연구합니다. 고확률 및 기대 후회 경계가 확립된 GP 상위 신뢰 구간(GP-UCB)과 비교할 때, GP-TS에 대한 대부분의 분석은 기대 후회로 제한되어 있습니다. 또한, 관대한 후회(Lenient regret)와 개선된 누적 후회 상한에 대한 GP-UCB의 최근 분석이 GP-TS에 적용될 수 있는지 여부는 여전히 불분명합니다. 이러한 공백을 메우기 위해, 본 논문은 다음과 같은 여러 후회 경계를 제시합니다: (i) GP-TS가 확률 $δ$로 $1/δ$에 대한 다항식 의존성을 겪는다는 것을 시사하는 GP-TS의 후회 하한, (ii) $δ$에 대한 개선된 후회 상한을 직접적으로 시사하는 누적 후회의 2차 모멘트 상한, (iii) 기대 관대한 후회 상한, 그리고 (iv) 시간 지평 $T$에 대한 개선된 누적 후회 상한. 아울러, 우리는 $T$에 대한 개선된 후회 상한을 얻기 위해 최근 분석의 필요 조건을 완화한 것을 포함하여 여러 유용한 보조정리를 제공합니다.
노이즈가 있는 1차원 함수의 전역 최솟값 원샷 위치 추정: 세트 트랜스포머 및 고전적 추정량과 비교한 반복 신경망 최소화기
One-Shot Localisation of the Global Minimum of a Noisy One-Dimensional Function: An Iterative Neural Minimizer Compared with Set Transformers and Classical Estimators
본 연구에서는 수동적 형태의 전역 최적화(global optimisation)를 다룹니다. 즉, 미지의 1차원 함수에서 노이즈가 포함된 20개의 샘플만 주어졌을 때, 추가적인 쿼리 없이 전역 최솟값의 위치를 예측하는 문제입니다. 우리는 정의역 전반에 걸쳐 위치를 이동하며 매 단계마다 해당 위치 근처의 샘플을 읽고 전체 20개 샘플 모두에 어텐션을 적용하는 반복 모델인 신경망 함수 최소화기(NFM, Neural Function Minimizer)를 소개합니다. 그리고 동일한 데이터로 학습된 동일한 크기의 두 가지 세트 트랜스포머(단일 점으로 답하는 모델 및 후보 위치들의 혼합으로 답하는 모델) 및 고전적인 제로 쿼리 추정량들과 학습 모델당 3개의 학습 시드에 걸쳐 비교합니다. 학습 계열에서 제외된 홀드아웃 사례에서 세 학습 모델은 위치 오차 면에서 동률을 이루었으며, 각각은 평균적으로 모든 고전적 추정량보다 더 정확했습니다. 가우스 과정(Gaussian process) 사후 argmin과 비교했을 때 NFM의 오차는 정의역 기준 1.3포인트 더 낮았습니다. 또한 NFM은 단일 점 세트 트랜스포머보다 후회(regret)가 낮았고, 사례별 불확실성은 해당 모델보다 더 나은 가능도를 보였으며 혼합 모델보다 오차 기준 사례 순위 매김을 더 잘 수행했습니다. 가우스 과정과 혼합 모델은 더 낮은 후회를 보였으며, 학습 계열 외부의 함수에서는 가우스 과정이 가장 정확한 추정량이었습니다. 두 골짜기의 깊이가 동일한 경우, 추정량의 구조가 아닌 응답 형태가 특정 골짜기를 선택할지 아니면 골짜기 사이의 값을 답할지를 결정합니다. 즉, 학습 모델이든 스플라인 기반이든 거리에 맞춰 단일 점을 반환하는 모든 추정량은 정확히 동률인 경우의 5분의 1에서 거의 3분의 1 수준에서 양다리를 걸치는(hedge) 경향을 보인 반면, 최빈값(mode)을 제시하는 추정량은 확실히 선택을 내렸으며, 가우스 과정 사후분포는 중앙값으로 요약되는지 최빈값으로 요약되는지에 따라 두 동작을 모두 보였습니다. 우리는 벤치마크와 자체 검증 하네스를 공개할 예정이며, 테스트 사례는 서로 다른 머신에서도 동일하고 결과는 반올림 수준까지 일치합니다.
베이지안 최적화에서의 직접적인 후회 최소화 최적화
Direct Regret Optimization in Bayesian Optimization
베이지안 최적화(Bayesian optimization, BO)는 비용이 많이 드는 블랙박스 함수를 최적화하기 위한 강력한 패러다임입니다. 전통적인 BO 방법은 일반적으로 기저 함수에 대해 수작업으로 설계된 별도의 획득 함수(acquisition function)와 대리 모델(surrogate model)에 의존하며, 흔히 근시안적인(myopic) 방식으로 작동합니다. 본 논문에서는 후보 모델과 획득 함수 집합으로부터 지식을 증류(distilling)하여 최적의 모델과 비근시안적 획득 방식을 공동으로 학습하고, 다단계 후회(multi-step regret) 최소화를 명시적인 목표로 하는 새로운 직접 후회 최적화(direct regret optimization) 접근법을 제안합니다. 제안하는 프레임워크는 서로 다른 하이퍼파라미터를 가진 가우시안 프로세스(Gaussian Processes, GP) 앙상블을 활용하여 시뮬레이션된 BO 궤적을 생성하며, 각 궤적은 기존 선택지 풀에서 추출된 획득 함수를 따르고 베이지안 조기 종료 기준에 의해 종료됩니다. 이러한 궤적들은 궁극적인 목적 함수를 개선하도록 다음 쿼리를 선택하는 엔드투엔드 의사결정 트랜스포머(Decision Transformer)를 학습시키며, 이는 조밀한 학습 희소성 학습(dense training sparse learning) 패러다임을 따릅니다. 즉, 트랜스포머는 풍부한 시뮬레이션 데이터로 학습되는 반면, 제한된 수의 실제 평가를 통해 온라인으로 GP를 개선합니다. 합성 데이터 및 실제 벤치마크에서 본 연구의 방법은 표준, 룩어헤드(lookahead), 신뢰 영역(trust-region), 분할 상환(amortized) BO 베이스라인 대비 최고 또는 최고에 가까운 최종 단순 후회(simple regret) 성능을 달성하며, 특히 고차원 환경에서 가장 큰 성능 향상을 보입니다. 절제 연구(ablation study)에 따르면 이러한 성능 향상은 관심 영역 필터링과 학습된 정책의 결합에 기인하며, 동일 예산 조건에서 명시적인 2단계 룩어헤드 획득 방식과 비교했을 때 이러한 이점이 룩어헤드만으로는 얻어지지 않음을 보여줍니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.
저자 비고
arXiv Comments
32 pages