Bayesian Optimization

Bayesian Optimization

Bayesian Optimization은 Black-Box 함수로 Global 최적화를 위한 sequential design strategy.

Objective function이 정해져있지 않다면, Random function으로 취급하고,

Practical Bayesian Optimization of Machine Learning Algorithms

https://papers.nips.cc/paper/4522-practical-bayesian-optimization-of-machine-learning-algorithms.pdf

Machine Learning 모델에서 HyperParameter(Random Forest의 Decision Tree개수, Neural Network의 Layer 개수, Learning rate 등) 튜닝을 위해 많은 시간을 투자한다.

Hyper Parameter Tuning 문제를 해결하기 위해 Bayesian Optimization을 사용한다. 알려지지 않은 “Black-box” function을 Optimization 할 때 많이 사용된다.

Grid Search, Random Search

보통 Hyperparameter를 찾기 위해 사용되는 방법으로 Grid Search, Random Search 등이 있다.

XGBoost에서 사용하는 Hyper-parameter로는 다음과 같다.

max_depth(int, default: 3): 기본 학습자를 위한 최대 트리 깊이

learning_rate(float, default: 0.1) : Boosting 학습률

n_estimators(int, default: 100) : fit하기 위한 Boosted tree의 수

silent(boolean, default: True : Boosting을 실행하는 동안 메시지를 print할지 여부

objective(string or callable, default:’reg:linear’) : 학습할 Objective Function 사용

booster(string, default: ‘gbtree’): Booster가 사용할 모드 gbtree, gblinear, dart

nthread(int, default: ‘None’): xgboost를 실행하는데 사용할 병렬 스레드 수

- xgboost.XGBClassifier(nthread=20)

n_jobs(int, default: 1): xgboost를 실행하는데 사용할 병렬 스레드 수

gamma(float, default: 0): 트리의 leaf 노드에 추가 파티션(partition)을 만들때 최소 손실 감소(Minimum loss reduction)가 필요하다.

min_child_weight(int, default: 1): Child 노드에 필요한 instance weight(hessian) 최소 합계

max_delta_step(int): 각 Tree의 가중치(Weight) 추정을 허용하는 최대 Delta 단계

subsample(float): 학습(Training) Instance의 Subsample 비율

colsample_bytree(float): 각 Tree를 구성할 때 column의 Subsample 비율

colsample_bylevel(float): 각 Tree의 Level에서 분할(split)에 대한 column의 Subsample 비율

reg_alpha(float): Weight에 대한 L1 정규화(regularization)

reg_lambda(float): Weight에 대한 L2 정규화(regularization)

scales_pos_weight(float): 양의 클래스와 음의 클래스에 대한 균형

base_score: 모든 Instance의 초기 예측 점수(prediction score)

seed(int): 난수 (Random) seed값 (random_state를 사용할 것)

random_state(int): seed와 동일

missing(float, defualt np.nan): 누락된 값(Missing Value)으로 존재하는 데이터를 처리할 값.

우리가 찾고 싶은 HyperParameter의 조합을

EXPLORE_HYPER_PARAMETER = {

   'max_depth_': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],

   'learning_rate_': [0.01, 0.02, 0.03, 0.04, 0.05, 0.06, 0.07, 0.08, 0.09, 0.999, 0.1],

   'n_estimators_' : [1, 50, 100, 150, 200, 250, 300, 350, 400, 450, 500],

   'gridValue': [0.001, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.999],

   'gamma_': [0.001, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.999],

   'min_child_weight_': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],

   'reg_alpha_': [0.001, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.999],

   'reg_lambda_': [0.001, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.999],

   'scale_pos_weight_': [0.001, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.999],

   'seed_': [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

}

이라고 가정한다.

먼저 Grid search는 모든 parameter의 경우의 수에 대해 cross-validation 결과가 가장 좋은 parameter를 고르는 방법이다. 즉, 위에 나열된 hyperparameter의 모든 가능한 경우의 수는 11^10개이다. 모든 11^10개의 parameter에 대해서 training data를 90:10으로 나누어 90을 train을 하고 10을 validation을 했을 때, validation 결과가 제일 좋은 parameter를 고르는 것이다.

이 방법은, 주어진 공간 내에서 가장 좋은 결과를 얻을 수 있다는 장점이 있지만, 시간이 정말 오래 걸린다는 단점이 존재한다. 또한 parameter의 candidate를 늘릴 때(N개)마다 탐색 개수(M개) 만큼 M^N으로 시간이 증가한다는 것이다.

이런 단점을 피하기 위해 나온 방법이 random search이다. Random Search는 모든 grid를 전부 search 하는 대신 random하게 일부의 parameter 들만 관측한 후, 그 중에서 가장 좋은 parameter를 고른다.

Grid Search는Unimportant parameter와 Important Parameter를 동일하게 관측해야하기 때문에 정작 Important Parameter를 다양하게 시도해볼 수 있는 기회가 적지만, Random Search는 grid로 제한되지 않기 때문에 확률적으로 Important Parameter를 더 살펴볼 수 있는 기회를 받게 된다.

http://scikit-learn.org/stable/modules/grid_search.html

Bayesian Optimization for “Black-box” Function

Bayesian Optimization은 다음의 수식과 같다.

이 때, X는 bounded domain이고, f(x)는 input을 넣었을 때, output이 무엇인지 모르는 black-box function이라고 가정한다.

Bayesian Optimization은 다음과 같은 방식으로 작동한다.

- 1. 지금까지 관측된 데이터 D = [(x1, f(x1)), (x2, f(x2)) … (xn, f(xn))]을 통해, Gaussian process prior로 function f(x)를 Estimation한다.

- 2. Function f(x)를 다음으로 관측할 지점 (xn+1, f(xn+1))으로 Acquisition Function(decision rule)으로 선택하여 이동한다.

- 3. 새로 관측한 (xn+1, f(xn+1))을 D에 추가하고, 적절한 stopping criteria에 도달할 때 까지 1로 반복한다.

위의 빨간색 점선은 우리가 찾으려고 하는 unknown black box function f(x)를 나타내고,

검정색 선은 지금까지 관측한 데이터를 바탕으로 우리가 예측한 estimated function ^f(x)의 expectation을 의미한다.

검정색 선 주변에 있는 회색 영역은, function f(x)가 존재할 confidence bound(function의 variance),

밑에 있는 EI(x)는 위에서 언급한 acquisition function을 의미한다.

위에서 acquisition function 값이 컸던 지점의 function 값을 관측하고 estimation을 update한 모습이다.

함수의 회색 영역이 크게 줄어들며, 좌측 부분와 우측 부분의 uncertainty를 줄이기 위해, 다음 관측할 point를 acquisition function을 통해 설정한다.

계속 update를 진행한 결과 estimation과 실제 fuction 흡사해진다. 관측한 지점 중 best point을 argmin f(x)로 선택한다.

Acquisition Function : https://www.google.co.kr/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0ahUKEwi_zZq2kJrXAhVJHJQKHbvzCbQQFgglMAA&url=https%3A%2F%2Fwww.cse.wustl.edu%2F~garnett%2Fcse515t%2Fspring_2015%2Ffiles%2Flecture_notes%2F12.pdf&usg=AOvVaw2lGhpENySb7Uiwhd81hD5o

http://www.smc2017.org/SMC2017_Papers/media/files/0819.pdf

Python

from xgboost import XGBClassifier

from bayes_opt import BayesianOptimization

def getObjective(max_depth_, learning_rate_, n_estimators_, gridValue, gamma_, min_child_weight_, reg_alpha_, reg_lambda_, scale_pos_weight_, seed_):

       if np.var(train_y) == 0.0:

           return -100.0

       

       max_depth_ = int(max_depth_)

       n_estimators_ = int(n_estimators_)

       seed_ = int(seed_)

       

       W_Updated = np.asarray([W[j]*(gridValue if (train_y[j]==1) else (1-gridValue)) for j in range(len(W))])

       learning_rate_ = 0.1

       

           classifier = XGBClassifier(n_estimators=n_estimators_, max_depth=max_depth_, learning_rate = learning_rate_, gamma=gamma_, min_child_weight=min_child_weight_, reg_alpha=reg_alpha_,

                                      reg_lambda=reg_lambda_, scale_pos_weight=scale_pos_weight_, seed=seed_,

                                      nthread=40)

       model = classifier.fit(train_x, train_y, sample_weight=W_Updated)

       predictions = model.predict(test_x)

       probabilityScores = np.asarray(model.predict_proba(test_x))[:,1]

       accuracy = accuracy_score(test_label_y, predictions)

       precision = precision_score(test_label_y, predictions)

       recall = recall_score(test_label_y, predictions)

       f1 = f1_score(test_label_y, predictions)

       return f1

   

bo = BayesianOptimization(getObjective, HYPER_PARMETER)

bo.explore(EXPLORE_HYPER_PARAMETER)

bo.maximize(n_iter=10)

print bo.res['max']

Reference

http://ieeexplore.ieee.org/abstract/document/7840827/

http://www.jmlr.org/papers/volume13/bergstra12a/bergstra12a.pdf

http://www.iro.umontreal.ca/~bengioy/cifar/NCAP2014-summerschool/slides/Ryan_adams_140814_bayesopt_ncap.pdf