베이지안 최적화(Bayesian Optimization)
5 min read

베이지안 최적화(Bayesian Optimization)

Bayesian Optimization

  • Bayesian Optimization은 Training을 통해 파악하게 되는 Parameter와 별개로, 사전에 사람이 직접 입력해야 하는 HyperParameter를 최적화하기 위한 방법으로 아래와 같은 식과 같이 임의의 함수 $f(x)$를 가정하고, 이 $f(x)$를 최대화하는 $x$를 찾아 나가는 방식으로 최적의 Hyperparameter를 찾는다
  • "Bayesian"이라는 단어가 의미하는 바처럼 이전 정보를 최대한 활용하는데 초점을 맞추고 있다.

$$x^* = \arg \min\limits_{x \in X}f(x)$$

  • 이때 $f(x)$는 Black box Function으로 내부 Logic을 알 수 없고, 입력과 출력을 통해서만 $f(x)$를 평가할 수 있다. 그리고 미분이 가능하지 않다.
  • 이 때 Bayesian Optimization은 크게 두 가지의 Function으로 나눠져 있는데, 하나는 Surrogate Function이고 하나는 Acquisition Function이다.

Surrogate Function & Acquisition Function

  • Surrogate Function은 이름이 의미하는 바처럼 현재 관측된 $x_n$과 $f(x_n)$ 값들을 바탕으로 $f(x)$를 추정하는 Probabilistic Function으로 Gaussian Process Regression을 활용할 수 있다.
    • 쉽게 생각하면 Surrogate Function은 Hyperparameter Set과 Performance간의 관계를 Function으로 나타낸 것이다.
    • (사족이지만 이 것을 보면서 LIME이 갑자기 등장한 것은 아니겠다 싶었다.
  • Acquisition Function은 Surrogate Function에서의 결과를 가지고 최적의 값을 찾아나가기 위한 Input Candidate를 결정해주는 Function이다.이 때 최적의 값은 Surrogate Function의 값이 큰 값으로 이 값을 이용(Exploitation)할지, 아니면 새로운 값을 더 찾아볼지(Exploration) 을 결정을 한다.
    • Acquisition Function에는 Prbability of Improvement(PI), Expected Improvement(EI), GP Upper Con dence Bound(GP-UCB) 등이 있다.

image

  • 위 이미지를 보면 우리가 알고 싶어하는 $f(x)$가 파란색선이라고 할 때, 현재까지 관측된 데이터를 바탕으로 Surrogate Function을 계산한 값이다. 이 때 Surrogate Function은 Probabilistic Model로 나올 수 있는 값들의 Variance를 보여주고 빨간 점은 이미 데이터가 확보된 곳으로 불확실성이 없기 때문에 Variance가 없다.
  • 아래쪽에 있는 EI(Expected improvement) Function는 Acquisition Function으로 값이 높게 나온 곳은 이제 추가 데이터 확보가 필요한 곳으로 해당 데이터를 이제 Surrogate Function에 해당 값을 넣어서 업데이트를 한다. 이런 식으로 반복해나가면서 최종 HyperParameter값을 찾아 나간다.
  • 이걸 단계별로 보면 다음과 같다.$t=2$시점 부터 보면 Acquisition function의 결과값이 max가 되는 지점은 $t=3$ 시점에 new observation으로 포함이 되어서 Surrogate Model이 업데이트 되고 이제 업데이트된 값을 바탕으로 Acquisition function은 다음 값을 찾아나선다. 그 결과가 $t=4$ 시점의결과이다. 이런 식으로 Variance를 줄여나가면서 최적의 Parameter를 찾아나선다.
    image

Code from Scratch

  • 해당 코드는 다음 에서 가지고 왔다.
  • 기존 Acquisition Function은PI(Probability of Improvment)를 이용하였으나 PoI를 개선해서 가장 많이 쓰이고 있는 EI(Expected Improvement)로 바꾸었다.
# example of bayesian optimization for a 1d function from scratch
from math import sin
from math import pi
from numpy import arange
from numpy import vstack
from numpy import argmax
from numpy import asarray
from numpy.random import normal
from numpy.random import random
from scipy.stats import norm
from sklearn.gaussian_process import GaussianProcessRegressor
from warnings import catch_warnings
from warnings import simplefilter
from matplotlib import pyplot
 
# objective function
def objective(x, noise=0.1):
	noise = normal(loc=0, scale=noise)
	return (x**2 * sin(5 * pi * x)**6.0) + noise
 
# surrogate or approximation for the objective function
def surrogate(model, X):
	# catch any warning generated when making a prediction
	with catch_warnings():
		# ignore generated warnings
		simplefilter("ignore")
		return model.predict(X, return_std=True)
 
# probability of improvement acquisition function
def acquisition(X, Xsamples, model):
  # calculate the best surrogate score found so far
  yhat, _ = surrogate(model, X)
  best = max(yhat)
	# calculate mean and stdev via surrogate function
  mu, std = surrogate(model, Xsamples)
  mu = mu[:, 0]
	# calculate the probability of improvement
  z = (mu - best) / (std+1E-9)
  probs = (mu -best) * norm.cdf(z) + std * norm.pdf(z)
	#probs = norm.cdf((mu - best) / (std+1E-9)) #PI
  
  return probs
 
# optimize the acquisition function
def opt_acquisition(X, y, model):
	# random search, generate random samples
	Xsamples = random(100)
	Xsamples = Xsamples.reshape(len(Xsamples), 1)
	# calculate the acquisition function for each sample
	scores = acquisition(X, Xsamples, model)
	# locate the index of the largest scores
	ix = argmax(scores)
	return Xsamples[ix, 0]
 
# plot real observations vs surrogate function
def plot(X, y, model):
	# scatter plot of inputs and real objective function
	pyplot.scatter(X, y)
	# line plot of surrogate function across domain
	Xsamples = asarray(arange(0, 1, 0.001))
	Xsamples = Xsamples.reshape(len(Xsamples), 1)
	ysamples, _ = surrogate(model, Xsamples)
	pyplot.plot(Xsamples, ysamples)
	# show the plot
	pyplot.show()
 
# sample the domain sparsely with noise
X = random(100)
y = asarray([objective(x) for x in X])
# reshape into rows and cols
X = X.reshape(len(X), 1)
y = y.reshape(len(y), 1)
# define the model
model = GaussianProcessRegressor()
# fit the model
model.fit(X, y)
# plot before hand
plot(X, y, model)
# perform the optimization process
for i in range(100):
	# select the next point to sample
	x = opt_acquisition(X, y, model)
	# sample the point
	actual = objective(x)
	# summarize the finding
	est, _ = surrogate(model, [[x]])
	print('>x=%.3f, f()=%3f, actual=%.3f' % (x, est, actual))
	# add the data to the dataset
	X = vstack((X, [[x]]))
	y = vstack((y, [[actual]]))
	# update the model
	model.fit(X, y)
 
# plot all samples and the final surrogate function
plot(X, y, model)
# best result
ix = argmax(y)
print('Best Result: x=%.3f, y=%.3f' % (X[ix], y[ix]))
image

References