베이즈 최적화 알고리즘

알고리즘 개요

베이즈 최적화 알고리즘은 유계 정의역에서 x에 대한 스칼라 목적 함수 f(x)를 최소화하려고 합니다. 이 함수는 동일한 지점 x에서 계산할 때 다른 결과를 반환할 수 있는 확률적 함수이거나 결정적 함수일 수 있습니다. x의 성분은 연속 실수, 정수 또는 범주형(이름으로 구성된 이산 집합)일 수 있습니다.

참고

이 설명에서 D는 x의 성분 수를 나타냅니다.

최소화의 핵심 요소는 다음과 같습니다.

• f(x)의 가우스 과정 모델.

• f(x)를 새로 계산할 때마다 가우스 과정 모델을 수정하기 위한 베이즈 업데이트 절차.

• 다음번 계산 지점 x를 결정하기 위해 최대화하는 획득 함수 a(x)(f의 가우스 과정 모델 기반). 자세한 내용은 획득 함수 유형 및 획득 함수 최대화 항목을 참조하십시오.

알고리즘 개요:

• 변수 범위 내에서 임의로 취한 NumSeedPoints 점 x_i에 대해 y_i = f(x_i)를 계산합니다. NumSeedPoints는 bayesopt 설정입니다. 계산 오류가 있는 경우, NumSeedPoints 계산에 성공할 때까지 임의의 점을 더 많이 취합니다. 각 성분의 확률 분포는 optimizableVariable의 Transform 값에 따라 균일하거나 로그 스케일입니다.

이어서 다음 단계를 반복합니다.

1. 함수 Q(f|x_i, y_i for i = 1,...,t)에 대한 사후분포를 얻기 위해 f(x)의 가우스 과정 모델을 업데이트합니다. (내부적으로, bayesopt는 가우스 과정 모델을 데이터에 피팅하기 위해 fitrgp를 사용합니다.)

2. 획득 함수 a(x)를 최대화하는 새 점 x를 찾습니다.

다음 중 하나에 도달하면 알고리즘이 중지됩니다.

• 정해진 반복 횟수(디폴트 값 30).

• 정해진 시간(디폴트 값은 시간 제한 없음).

• Bayesian Optimization Output Functions 또는 Bayesian Optimization Plot Functions에서 지정한 중지 기준.

병렬 실행되는 알고리즘의 차이에 대해서는 Parallel Bayesian Algorithm 항목을 참조하십시오.

모델 피팅을 위한 가우스 과정 회귀

목적 함수 f에 대한 기본 확률적 모델은 관찰값에 가우스 잡음을 추가한 가우스 과정 사전분포입니다. 따라서 f(x)의 사전분포는 평균 μ(x;θ) 및 공분산 커널 함수 k(x,x′;θ)를 가지는 가우스 과정입니다. 여기서, θ는 커널 모수의 벡터입니다. 특정 커널 함수 bayesopt 사용에 대해서는 커널 함수 항목을 참조하십시오.

좀 더 자세히 설명하자면, 점으로 구성된 집합 X = x_i와 함께 관련 목적 함수 값 F = f_i를 표시합니다. 함수 값 F의 사전 결합 분포는 평균 μ(X) 및 공분산 행렬 K(X,X)를 가지는 다변량 정규 분포이며 여기서 K_ij = k(x_i,x_j)입니다.

일반성의 손실 없이 사전 평균은 0으로 지정됩니다.

또한, 분산이 σ²인 가우스 잡음이 관측값에 추가된 것으로 가정합니다. 따라서 사전분포는 공분산 K(X,X;θ) + σ²I를 가집니다.

가우스 과정 회귀 모델을 관측값에 피팅하려면 잡음 분산 σ² 값과 커널 모수 θ 값을 찾아야 합니다. 이 피팅은 계산량이 많은 과정이며 fitrgp로 수행합니다.

가우스 과정을 관측값에 피팅하는 방법에 대한 자세한 내용은 가우스 과정 회귀 항목을 참조하십시오.

커널 함수

커널 함수 k(x,x′;θ)는 가우스 과정 회귀의 품질에 상당한 영향을 미칠 수 있습니다. bayesopt는 Kernel (Covariance) Function Options에 정의된 ARD Matérn 5/2 커널을 사용합니다.

Snoek, Larochelle과 Adams의 문헌 [3]을 참조하십시오.

획득 함수 유형

bayesopt에 대해 여섯 가지 획득 함수를 선택하여 사용할 수 있습니다. 기본 유형은 세 가지이고, expected-improvement를 per-second 또는 plus로 수정할 수도 있습니다.

• 'expected-improvement-per-second-plus'(디폴트 값)

• 'expected-improvement'

• 'expected-improvement-plus'

• 'expected-improvement-per-second'

• 'lower-confidence-bound'

• 'probability-of-improvement'

획득 함수는 사후분포 함수 Q를 기반으로 점 x의 “적합도”를 평가합니다. 오류 제약 조건(Objective Function Errors 참조)을 비롯하여 연결된 제약 조건이 있는 경우, 모든 획득 함수는 Gelbart, Snoek 및 Adams의 제안[2]에 따라 “적합도” 추정을 수정합니다. 획득 함수에 도달하려면 “적합도”에 제약 조건을 만족하는 확률 추정값을 곱합니다.

• EI(예상 개선값)

• POI(개선 확률)

• 신뢰 하한

• per-second

• plus

EI(예상 개선값)

'expected-improvement' 획득 함수군은 목적 함수에서 증가를 초래하는 값은 무시하고 목적 함수에서 예상되는 개선값을 평가합니다. 다시 말해, 다음을 정의합니다.

• x_best를 사후 평균 최저값의 위치로 정의합니다.

• μ_Q(x_best)를 사후 평균의 최저값으로 정의합니다.

그러면 예상 개선값은 다음과 같이 됩니다.

$$EI\left(x,Q\right)=E_Q\left[\max \left(0,{\mu }_Q\left(x_{\text{best}}\right)-f\left(x\right)\right)\right].$$

POI(개선 확률)

'probability-of-improvement' 획득 함수는 'expected-improvement'와 비슷하지만 더 간단한 계산을 수행합니다. 두 경우 모두 bayesopt는 먼저 x_best와 μ_Q(x_best)를 계산합니다. 그런 다음 'probability-of-improvement'를 구하기 위해 bayesopt는 새 점 x에서 더 나은 목적 함수 값이 도출될 확률 PI를 계산하고 이를 “마진” 모수 m으로 수정합니다.

$$PI\left(x,Q\right)=P_Q\left(f\left(x\right)<{\mu }_Q\left(x_{\text{best}}\right)-m\right).$$

bayesopt는 m을 추정된 잡음 표준편차로 취합니다. bayesopt는 이 확률을 다음과 같이 평가합니다.

$$PI=\Phi \left({\nu }_Q\left(x\right)\right),$$

여기서

$${\nu }_Q\left(x\right)=\frac{{\mu }_Q\left(x_{\text{best}}\right)-m-{\mu }_Q\left(x\right)}{{\sigma }_Q\left(x\right)}.$$

이때 Φ(·)는 단위 법선 CDF이고 σ_Q는 x에서 가우스 과정의 사후 표준편차입니다.

신뢰 하한

'lower-confidence-bound' 획득 함수는 각 점에서 사후 평균 미만인 곡선 G의 두 표준편차를 찾습니다.

$$G\left(x\right)={\mu }_Q\left(x\right)-2{\sigma }_Q\left(x\right).$$

G(x)는 목적 함수 모델의 2σ_Q 신뢰 하한 포락선입니다. 그런 다음 bayesopt는 음의 G를 최대화합니다.

$$LCB=2{\sigma }_Q\left(x\right)-{\mu }_Q\left(x\right).$$

per-second

목적 함수의 계산 시간이 영역에 따라 달라지는 경우가 있습니다. 예를 들어, 많은 서포트 벡터 머신은 특정한 점 범위에 대해 계산 시간에 큰 차이를 보입니다. 그렇다면 bayesopt는 획득 함수에 시간 가중치를 사용함으로써 초당 더 나은 개선값을 얻을 수 있습니다. 비용 가중 획득 함수는 이름에 per-second라는 문구가 있습니다.

이러한 획득 함수는 다음과 같이 작동합니다. 목적 함수를 계산하는 동안, bayesopt는 또 다른 베이즈 모델의 목적 함수 계산 시간을 위치 x의 함수로 유지합니다. 획득 함수가 사용하는 초당 예상 개선값은 다음과 같습니다.

$$EIpS\left(x\right)=\frac{E{I}_Q\left(x\right)}{{\mu }_S\left(x\right)},$$

여기서 μ_S(x)는 시간적 가우스 과정 모델의 사후 평균입니다.

plus

로컬 목적 함수의 최소값을 피하기 위해, 이름에 plus가 들어간 획득 함수는 영역을 과다 사용한다고 추정되면 동작을 수정합니다. 과다 사용을 이해하기 위해 σ_F(x)가 x에서 사후 목적 함수의 표준편차가 되도록 합니다. σ를 가산성 잡음의 사후 표준편차로 하여 다음 식을 만듭니다.

σ_Q²(x) = σ_F²(x) + σ².

t_σ를 ExplorationRatio 옵션의 양수 값으로 정의합니다. 각 반복 후 bayesopt plus 획득 함수는 다음번 점 x가 다음을 만족하는지 평가합니다.

σ_F(x) < t_σσ.

만족하면 알고리즘은 x가 과다 사용되고 있다고 선언합니다. 그런 다음, 획득 함수는 Bull[1]이 제안한 대로 θ에 반복 횟수를 곱해 커널 함수를 수정합니다. 이렇게 수정하면 관측값 사이의 점에 대한 분산 σ_Q가 증가합니다. 그런 다음 새로 피팅된 커널 함수를 기반으로 새로운 점을 생성합니다. 새로운 점 x가 다시 과다 사용되면 획득 함수는 θ에 인자 10을 추가로 곱하고 다시 시도합니다. 과다 사용되지 않는 점 x를 생성하기 위해 이런 식으로 최대 5회까지 계속 시도합니다. 알고리즘은 새로 생성된 x를 다음 점으로 받아들입니다.

따라서 ExplorationRatio는 더 나은 전역 해를 구하기 위해 새로운 점을 찾는 방법과 이미 조사된 가까운 점에 집중하는 방법 사이에서 절충합니다.

획득 함수 최대화

내부적으로, bayesopt는 다음과 같은 일반적인 단계를 사용하여 획득 함수를 최대화합니다.

1. 'probability-of-improvement' 및 'expected-improvement'로 시작하는 알고리즘의 경우, bayesopt는 변수 범위 내에서 수천 개의 점을 추출하고 그중에서 최상의(낮은 평균값) 실현가능점을 여러 개 취한 다음 로컬 탐색으로 이를 개선하여 표면적으로 가장 적합한 실현가능점을 찾아냄으로써 사후분포 μ_Q(x_best)의 실현가능한 최소 평균을 추정합니다. 실현가능점이란 제약 조건을 만족하는 점을 의미합니다(Constraints in Bayesian Optimization 참조).

2. bayesopt는 모든 알고리즘에 대해 변수 범위 내에서 수천 개의 점을 추출하고 그중에서 최상의(높은 획득 함수) 실현가능점을 여러 개 취한 다음 로컬 탐색으로 이를 개선하여 표면적으로 가장 적합한 실현가능점을 찾습니다. 획득 함수 값은 목적 함수의 표본이 아니라 모델링된 사후분포에 따라 달라지므로 빠르게 계산할 수 있습니다.

참고 문헌

[1] Bull, A. D. Convergence rates of efficient global optimization algorithms. https://arxiv.org/abs/1101.3501v3, 2011.

[2] Gelbart, M., J. Snoek, R. P. Adams. Bayesian Optimization with Unknown Constraints. https://arxiv.org/abs/1403.5607, 2014.

[3] Snoek, J., H. Larochelle, R. P. Adams. Practical Bayesian Optimization of Machine Learning Algorithms. https://arxiv.org/abs/1206.2944, 2012.

참고 항목

bayesopt | BayesianOptimization

관련 항목

• Bayesian Optimization Workflow
• bayesopt를 사용하여 교차 검증된 분류기 최적화하기
• 베이즈 최적화를 사용하여 분류기 피팅 최적화하기
• Optimize a Boosted Regression Ensemble
• Bayesian Optimization Output Function
• Bayesian Optimization with Coupled Constraints
• Bayesian Optimization with Tall Arrays