14. XGBoost

what?

• 부스팅 알고리즘으로 약한 예측모형을 결합하여 강한 예측모형을 만드는 알고리즘이다. Extreme Gradient Boosting의 약자로 Gradient Boosting의 개선 버전이다. 분류와 회귀에 모두 사용가능하다
• Gradient Boosting과 유사하지만 node별로 다른 코어를 사용하며, regularization term이 추가되었다.
• split 이전에 information gain을 미리 계산하여 음수가 되는 경우 split하지 않고 멈추는 pruning 방식을 사용한다. 즉 모든 feature에 대한 split을 진행하지 않아 모델 학습 속도가 빠르다. 이를 Leaf-wise growth라고 한다. 이를 위해 Taylor 급수를 통해 전개된 \(g_i, h_i\) 두 개의 gradient를 활용한다
• Gradient Boosting과 다르게 Early Stopping 기능이 있다. 기존 GB의 경우 반복을 멈출 수 없고 n_estimators에서 지정한 횟수를 완료해야 한다. 하지만 XGBoost는 조기 중단 기능이 있어 n_estimators를 전부 다 채울 필요가 없다. 예를 들어 n_estimators를 100으로 설정하고 조기 중단 파라미터를 50으로 설정하면 50회를 반복하는 동안 학습 오류가 더 이상 감소하지 않으면 더 이상 부스팅을 진행하지 않고 종료한다
• 최적의 split을 진행하기 위해 미리 feature별로 bins(구간)을 지정하여 데이터를 분할해둔다. 이를 Histogram based methods라고 한다. 이로 인해 모든 feature에 대해 모든 데이터의 최적의 split을 계산할 필요가 없게 된다.
• XGBoost는 일반적으로 tabular 데이터를 분석하는데 사용된다. 이는 데이터가 대부분이 0으로 구성된 sparse matrix 로 나타난다는 것을 의미한다. XGBoost에서는 불필요한 연산을 방지하기 위해 split을 진행할 때 0의 값을 가지는 데이터를 고려하지 않는다(Ignore sparse inputs).
• XGBoost는 missing value를 loss를 더 줄이는 split 기준으로 채운다.

why?

• 병렬 처리를 사용하여 학습과 분류가 빠르다
• regularization term이 추가되어 있어 overfitting을 효과적으로 방지한다
• missing values를 내부적으로 처리해준다
• 사용자가 loss function과 evaluation metrics를 지정할 수 있는 유연성이 있다
• 강력한 pruning을 사용하여 연산 속도가 빠르다

why not?

• 최적화시킬 파라미터의 수가 매우 많고 각 파라미터의 영향을 크게 받는다

how?

Input

1)Data{(\(x_i, y_i\))}, M rows(data) and N columns(features)
2) Model : \(\hat{y_i} = \sum_{k=1}^K f_k(x_i), f_k \in \mathcal{F}\)

• 기존 Gradient Boosting 과 같이 initial prediction에 residual를 예측한 결과를 더해가는 방식을 따른다
• K : number of trees
• \(f_k\) : function in the functional space \(\mathcal{F}\)
• \(\mathcal{F}\) : set of all possible trees
• \(f_t(x) = w_q(x)\), \(w\) : vector of scores on leaves

3) Object function : \(\sum_{i=1}^n l(y_i, \hat{y_i}) + \sum_{k=1}^K\Omega(f_k)\)

• first term = loss function, second term = regularization term

1. loss function을 범용적으로(logistic loss같이 한번에 연산하기 힘든 경우를 포함하여) 사용하기 위해서 loss function 부분을 Taylor 급수로 전개한다. \(\sum_{i=1}^n[l(y_i, \hat{y_i}) + g_if_t(x_i) + \frac 1 2 h_if_i^2(x_i)] + \sum_{k=1}^K\Omega(f_k)\)
   \((g_i = \partial \hat{y_{t-1}}l(y_i, \hat{y_i}), h_i = \partial^2 \hat{y_{t-1}}l(y_i, \hat{y_i}))\)

2. constant를 정리한 후
   \(\sum_{i=1}^n[g_if_t(x_i) + \frac 1 2 h_if_t^2(x_i)] + \sum_{k=1}^K\Omega(f_k)\)

3. 논문에서는 l2 regularization을 사용하고 있다. \(\sum_{k=1}^K\Omega(f_k) = \gamma T + \frac 1 2 \lambda\sum_{j=1}^Tw_j^2\)이므로

4. 위의 식을 정리하면 Object funtion : \(\sum_{i=1}^n[g_iw_q(x_i) \frac 1 2 h_iw_q(x_i)^2]+ \gamma T + \frac 1 2 \lambda\sum_{j=1}^Tw_j^2\)
   = \(\sum_{i=1}^T[(\sum_{i \in I_j}g_i)w_j + \frac 1 2 (\sum_{i \in I_j}(h_i + \lambda)w_j^2)] + \gamma T\) (\(I_j\) : set of indices of data points assgined to the j th leaf)

5. G, H로 식 축약하기
   \((G_j = \sum_{i \in I_j}g_i, H_j = \sum_{i \in I_j}h_i)\) Object function :
   \(obj^{(t)} = \sum_{j=1}^T[G_jw_j + \frac 1 2 (H_j + \lambda)w_j^2] + \gamma T\) (\(T\) : number of leaves )

6. \(w_j^* = -\frac {G_j} {H_j + \lambda}(=f_t)\), \(obj = - \frac 1 2 \sum_{j=1}^T \frac {G_j^2} {H_j + \lambda} + \gamma T\)

Step 1 Initialize model with constant value with sampled data and features

\(f_0(x) = \underset \gamma {argmin} \sum_{i=1}^n L(y_i, \hat{y_i})\)

• \(f_0(x)\) : initial predicted value(=average of all target values)

Step 2 for k=1 to K

1) compute \(g_i, h_i\) on each split \((g_i = \partial \hat{y_{t-1}}l(y_i, \hat{y_i}), h_i = \partial^2 \hat{y_{t-1}}l(y_i, \hat{y_i}))\)

2) until \(Gain < 0\), greedily grow the tree using object function \(obj = - \frac 1 2 \sum_{j=1}^T \frac {G_j^2} {H_j + \lambda} + \gamma T\) \(Gain = \frac 1 2 [\frac {G_L^2} {H_L + \lambda} + \frac {G_R^2} {H_R + \lambda} + \frac {(G_L + G_R)^2} {H_L + H_R + \lambda}] - \gamma\)

3) \(f_k(x_i) = w_k, w_k = -\frac {G_j} {H_j + \lambda}\)

4) Update \(f_K(x_i) = f_{(K-1)} + \nu f_k(x_i)\)

• \(\nu\) : learning rate

Step 3 output \(f_K(x)\)

Code usage

import xgboost as xgb
from xgboost import plot_importance
import pandas as pd
import numpy as np
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split
import warnings
warnings.filterwarnings('ignore')

dataset = load_breast_cancer()
X_features= dataset.data
y_label = dataset.target

cancer_df = pd.DataFrame(data=X_features, columns=dataset.feature_names)
cancer_df['target']= y_label
cancer_df.head(3)

X_train, X_test, y_train, y_test=train_test_split(X_features, y_label,
                                         test_size=0.2, random_state=156 )

dtrain = xgb.DMatrix(data=X_train , label=y_train)
dtest = xgb.DMatrix(data=X_test , label=y_test)


params = { 'max_depth':3,
           'eta': 0.1,
           'objective':'binary:logistic',
           'eval_metric':'logloss',
           'early_stoppings':100
        }
num_rounds = 400

wlist = [(dtrain,'train'),(dtest,'eval') ]
xgb_model = xgb.train(params = params , dtrain=dtrain , num_boost_round=num_rounds , evals=wlist )

pred_probs = xgb_model.predict(dtest)

Tips : XGBoost paramters

1. Parameter 종류

XGBoost에는 4 종류의 파라미터가 있다. 그 중에서 주요 파라미터만 살펴보도록 하겠다

1) general parameter : 일반적으로 실행 시 스레드의 개수나 silent 모드 등의 선택을 위한 파라미터로서 디폴트 파라미터 값을 바꾸는 경우는 거의 없다.

• booster : gbtree, gblinear 중에 선택(default=gbtree)
• silent : 출력 메시지 여부를 결정(default=0, 출력 메시지 나타냄)
• nthread : CPU 실행 스레드를 결정(default=CPU 전체 스레드 다 사용)

2) booster parameter : 트리 최적화, 부스팅, regularization 등과 관련된 파라미터

• eta : 학습률, 보통 0.01~0.2 사이의 값을 선호함(default=0.3)
• num_boost_round : 생성할 트리의 개수
• min_child_weight : 리프 노드에서 필요한 $H_i$의 최솟값, 과적합을 막기 위해 사용됨(default=1)
• gamma : 트리의 리프 노드를 추가적으로 나눌지를 결정할 최소 손실 감소 값. 해당 값보다 큰 손실이 있는 경우에만 리프 노드를 분리함. 값이 클수록 과적합 감소 효과가 있다(default=0)
• max_depth : 높아질수록 과적합 가능성이 높아지며 보통은 3~10 사이의 값을 적용함(default=6)
• sub_sample : 데이터를 샘플링하는 비율을 지정, 예를 들어 0.5로 지정하면 전체 데이터의 절반을 트리를 생성하는데 사용함. 일반적으로 0.5~1사이의 값을 사용(default=1)
• colsample_bytree : 트리 생성에 필요한 feature를 임의로 샘플링하는데 사용됨(default=1)
• lambda : l2 regularization의 적용값이다. feature 개수가 많을 경우 적용을 검토하며 값이 클수록 과적합 감소 효과가 있다(default=1)
• alpha : l1 regularization의 적용값이다. feature 개수가 많을 경우 적용을 검토하며 값이 클수록 과적합 감소 효과가 있다(default=1)
• scale_pos_weight : 비대칭한 클래스로 구성된 데이터 세트의 균형을 유지하기 위한 파라미터(default=1)

3) Learning task paramter : 학습 수행 시의 객체 함수, 평가를 위한 지표를 설정하는 파라미터

• objective : 최솟값을 가져야 할 loss function을 정의함.(binary:logistic:, multi:softmax:, multi:softprob: 등이 있음)
• eval_metric : 검증에 사용되는 함수 정의. 회귀인 경우 rmse, 분류인 경우 error가 default 값이다(rmse, mae, logloss, error, merror, mlogloss, auc 등이 있음) 4) Command line paramter : 콘솔에서 사용 시 옵션을 결정하는 파라미터

2. Tips for overfitting

overfitting이 발생할 시 다음과 같이 파라미터를 조정할 수 있다

• eta 값을 낮춘다. eta 값을 낮출 경우 num_rounds는 반대로 높혀줘야 함
• max_depth를 낮춘다
• min_child_weight 값을 높힌다
• gamma 값을 높힌다
• subsample, colsample_bytree를 조정한다

Reference

핸즈온 머신러닝
XGBoost 장단점 영상
XGBoost 설명
XGBoost 파라미터 설명
XGBoost 사용 예제