이전 글 : [Tree Based Models/Boosting] - XGBoost_1_트리만들기, Similarity Score, Gain, Pruning(Gamma)

이제 각 Leaf의 Output Value에 대하여 공부해보자. 

$${Output\,Value} = { Sum\,of\,Residuals \over {Number\,of\,Residuals + \lambda} }$$

$${Similarity\,Score} = { Sum\,of\,Residuals,\,Squared \over {Number\,of\,Residuals + \lambda} }$$

분자(잔차 합)의 제곱을 하느냐 마느냐 차이가 있다.

Output Value에서 $\lambda$값이 커진다는것은 Output Value가 작아지는것을 의미하고, 이는 Prediction값을 줄인다는 뜻이다. 

다른 Gradient Boost처럼, XGBoost도 값을 예측하는데에 Initial Prediction (Default = 0.5) 와  Learning Rate , 그리고 해당 리프의Output Value를 사용한다.

$ Prediction = Initial\, Prediction + Learning\,Rate * Output\,Value$

Learning Rate를 eta라고 하는데, 각 Output Value에 이를 곱하여 사용한다. 

Prediction

시리즈 1번에서의 예시자료를 그대로 사용하면,

이로써, 초기의 예측 0.5에서 -2.65로 한층 더 가까워졌다. 

나머지 값들도 예측을 진행

2,3,4번의 값들도 각각의 Leaf에 맞는 output Value를 사용하여 새로운 예측을 하였고, 이로써 Initial Prediction보다 좀 더 나아졌다. 

이제 이렇게 만들어진 Prediction을 통하여 또 잔차를 계산, 그 잔차들을 통해 Root에 넣고, SS계산
Max_Depth가 허용하는 만큼 or leaf에 하나남을때 까지 Split 지점을 찾아서 (최대 Gain을 기준으로) Split 진행, 
최종 Split 후 Gamma 값에 따라서 Gain과 비교하여 Pruning진행, 
Pruning 까지 진행한 후 Output Value를 계산,
Initial Prediction부터 이전 트리까지의 Output Value와 Learning Rate를 사용하여 새로운 Prediction 을 한다.

위 과정을 Maximum Number에 닿을때 까지 or 더이상 진전이 없을때 까지 반복하면 점차점차 각각의 값들에 맞는 Tree들이 만들어지고, 그렇게 모델이 학습된다! 

아래는 StatQuest의 XGBoost Mathmatical Detail을 들으며,,,, 열심히 정리하며 이해하려 노력한 흔적이다!

테일러 근사를 통해 Loss Function을 쉽게 근사하고, Gradient와 Gession을 통해 식을 편하게 바꾸고나서 풀고 정리하고 풀고 정리하면, 
어떻게 Output Value 식이 만들어졌는지 알 수 있다.!

출처 :
XGBoost: A Scalable Tree Boosting System / Tianqi Chen , University of Washington
www.youtube.com/watch?v=ZVFeW798-2I&list=RDCMUCtYLUTtgS3k1Fg4y5tAhLbw&start_radio=1&t=900 

Ensemble 모델 중 Boosting의 Gradient 부스팅의 상위호환버전과도 같은 XGBOOST이다. 

강력한 성능을 가진 XGBoost의 논문과, StatQuest의 강의를 열심히 공부하여 아래와 같이 정리해본다. 

초기 prediction 을 만들고 (default=0.5) 시작하는 것은 기존의 부스팅과 동일하다. 그러고 나서 잔차를 먼저 하나의 리프에 넣어준다. 

그리고, 해당 leaf의 Similarity Score를 계산하는데,

$$ {Similarity.Score} = { Sum. of. Residuals, Squared \over{Number. of. Residuals + \lambda }} = { (\Sigma_{i=1}^{n}{Residual})^2 \over { n +\lambda}  }$$
n=해당 leaf의 Residual 수

여기서 $\lambda$는 Regularization Parameter로 우리가 지정해주는 것이다. 
StatQuest에서는 간단하게 설명하기위해 4개의 row를 가진 데이터를 예를 들었다.

최 상위 4개가 들어있을때의 SS는 $(-10.5+6.5+7.5-7.5)\over{4 + \lambda}$이고, 람다를 0이라 가정했을때 (계산을 간편히하기위해)
SS=4이다. 

SS(Similarity Score) 계산이 끝나면 이제 이 리프를 분기시켜서 트리를 만들어본다.
4개의 데이터 사이에 분기점을 만들면 총 3개를 만들 수 있고, 이렇게 분기되는 때마다 SS를 계산하여, Gain을 계산한다.
각 트리를 만들때마다 왼쪽, 오른쪽 리프의 SS계산을 하여 기록하면 이제 분기 전후에 대한 비교가 가능해진다. 
분기 전에는 7.5와 -7.5가 서로 상쇄시켜서 ss가 낮았던 반면, 분기 후엔, 왼쪽 오른쪽 리프들 각각 상쇄작용이 약해서 ss점수가 더 크다. 

이제 각 분기점에 대한 Gain을 계산하는데, Gain의 식은 이러하다. $$Gain = Left_{Similarity} + Right_{Similarity} - ROOT_{Similarity}$$

분기점을 1번과 2번데이터 사이(Dosage < 15)로 했을때 Gain은 120.33이다.

22.5를 기준으로 분기하면 왼쪽에 잔차는 -10.5 , 6.5 이고, 오른쪽 잔차는 7.5 , -7.5로

$\lambda=0$으로 설정하였으니 각각의 SS는 $왼쪽 = {{(-10.5 + 6.5)}^2 \over {2 + \lambda}}= {4^2 \over {2}} = 8$ , $오른쪽 = {({7.5-7.5})^2 \over{2+\lambda}}=0$에서 왼쪽이 8 오른쪽이 0이고, Gain은 $8+0 -4 = 4$ 이다.

이제 분기점을 3,4번 데이터 사이 (Dosage < 30)으로 했을 때를 계산하면 

더이상 관측치 사이에 Split 할 것이 없다. 따라서 각 분기점의 Gain을 비교하면, 1,2번 사이의 Gain (120.33)이 가장 크므로, Dosage < 15을 선택.
왼쪽 리프에는 -10.5 하나만 들어와있고, 오른쪽엔 6.5, 7.5, -7.5가 들어와있다. 

이제 오른쪽 리프에 3개를 분할해보는데, 맨 처음 루트에서 SS와 각각 split지점에 대한 SS, Gain을 계산했던 것과 동일하게 진행한다.
2,3번 사이에 split을 하면, 아래 그림과 같이 나눠지고

그때의 SS와 Gain은 
$SS_{(Dosage<22.5)} = {  {(6.5+7.5-7.5)^2}\over{3+0} } = 14.08  $, $SS_{left}= {{(6.5)^2}\over{1+0} }= 42.25$ , $SS_{right}= { { (7.5-7.5)^2 } \over {2+0} } = 0$이고,
${Gain} = { SS_{left} + SS_{right} - SS_{ROOT} } = {42.25 +0 - 14.08} = 28.17$ 이다.

이후, 

3,4번 사이에 split을 하면, 아래 그림과 같은 분기가 이루어지고, 이 떄의 SS를 계산하면 각각 
$SS_{(Dosage<30)} = {  {(6.5+7.5-7.5)^2}\over{3+0} } = 14.08  $ ,  $SS_{left}= {{(6.5+7.5)^2}\over{2+0} }= 98$ , $SS_{right}= { { (-7.5)^2 } \over {2+0} } = 56.25$이고, 
${Gain} = { SS_{left} + SS_{right} - SS_{ROOT} } = {98 + 56.25 - 14.08} = 140.17$ 이다. 

22.5로 나눴을 때 보다, 30으로 나눴을 때 더욱 Gain이 크므로, Dosage < 30 을 선택한다. 
이후, max_depth (default = 6) 이 허용하는 만큼 한번 더 왼쪽 리프를 분기할 수 있지만, 계산을 간편히 하기위해 max_depth = 2로 제한하여 분기종료. 

이로써, SS Score와 Gain 을 통하여 트리를 만들었다. 
이제 트리를 Prune해야한다. Prune에서는 Gamma($\gamma$)를 사용한다. 
Gain보다 $\gamma$가 크면 가지친것을 삭제하는 것이다.

$\gamma = 130$이라면, 오른쪽 분기점의 Gain ( 140.17 )이 더 크므로 오른쪽 brunch가 살아남는다, 이에따라, 루트도 함께 살아남게된다.

만약 $\gamma=150$이라면?

먼저 오른쪽 brunch의 gain이 150보다 작으므로, 삭제하고, 루트또한 gain이 120.33으로 150보다 작으므로 이번에 만든 트리 자체를 날려버리는 것이다. 

$\lambda$의 역할은?

람다가 어떤 정규화 파라미터로 작용한다는 것은 앞서 설명했다. 하지만 어떻게 작용하길래 정규화 파라미터역할을 하는 것일까?
이는 Similarity Score를 확인하면 알 수 있다.

$$ {Similarity Score} = { { { Sum.Of.Residuals  }^2} \over {Num.Of.Residuals + \lambda }  }$$

$${Gain} = { SS_{left} + SS_{right} - SS_{ROOT} } $$

에서, $\lambda$가 커질수록, SS는 작아지고, 이에따라 Gain도 같이 작아지게된다. XGBoost에서 Gain에 따라 Pruning을 진행하는데, $\gamma$값보다 Gain이 작으면, 그 트리(or Brunch)를 삭제하므로, 트리가 자주 지워지게되고, 이는 결국 Overfitting을 방지하는 역할을 하게된다!

λ 값에 따른 Gain의 차이가 위와같다. SS를 계산할 때,  λ가 분모에 들어있으므로,  λ가 커지면 -> SS가 작아지고, 이에따라 Gain도 작아지는 것이다.

하나의 리프 내 샘플의 수에 따라서 λ가 어떤 영향을 주는가? 

SS와 Gain 모두 Number of Residual로, 한 리프에 몇개의 샘플(잔차)이 들어있는지에 영향을 받는다.
λ는 모두 분모에 있으며, 이에 대한 영향은 λ가 1만큼 커짐에 따라, Residual이 1개있는 리프는 SS가 $1\over2$만큼 작아진다.
2개있을경우 분모가 2->3으로 변화하므로 한 leaf에 잔차 수가 많으면 많을 수록 λ의 영향이 작다는것이고, 이는 한 leaf의 샘플 수가 많을 수록 λ의 영향이 적어지므로, 향후 파라미터 튜닝에서 λ의 값과, min_samples_leaf를 함께 생각해야 할 것이며 이 둘의 상호 영향또한 염려해야한다는 것으로 이해된다.

위의 내용에 대한 정리

$$ {Similarity.Score} = { Sum. of. Residuals, Squared \over{Number. of. Residuals + \lambda }} = { (\Sigma_{i=1}^{n}{Residual})^2 \over { n +\lambda}  }$$
$${Gain} = { SS_{left} + SS_{right} - SS_{ROOT} } $$
n=해당 leaf의 Residual 수
λ가 0보다 커진다 = Gain이 작아진다 = Leaves를 Prune하기 쉬워진다 = OverFitting을 방지한다 
$\gamma$가 커진다 = Gain-$\gamma$가 음수가 될 확률이 높아진다 =  Brunch를 Prune하기 쉬워진다 = OverFitting을 방지한다.

Motivation
Random Forest 가 병렬적으로 무지 많은 Decision Tree를 만든다면, 부스팅에서는 Decision Tree를 점진적으로 발전시킨 후 이를 통합하는 과정을 한다.
AdaBoost와 같이, 중요한 데이터에 대해 weight를 주는방식 vs GBDT와 같이 딮러닝의 loss function 마냥 정답지와 오답지간의 차이를 다음번 훈련에 다시 투입시켜서 gradient를 적극적으로 활용, 모델을 개선하는 방식이 있는데, XGBoost, LightGBM이 이에(후자) 속한다.

LightGBM에서 (GOSS와 EFB방식을 통해) 번들을 구성, 데이터 feature를 줄여서 학습한다

Conventional GBM need to, for every feature, scam all data instances to estimate the information gain of all the possible split points.

GOSS (Gradient-based One-Side Sampling)

1. Data instances with different gradients play different roles in the computation of information gain
2. Keep instances with large gradients and randomly drop instances with small gradients

1. 각 데이터들은 서로다른 gradient를 가지며, 이에대한 information gain이 다르다 -> 어느지점을 습득하는지에 따라 다른 역할을 수행하게된다.
2. large gradient한 데이터(instances)는 갖고가고, small gradient한 데이터에서 랜덤선택한다. -> 상위몇개를 고정, 하위몇개 중 랜덤하게 골라서 학습한다.

GBDT에서 모든 feature에 대해 스캔을 쭉 해서 가능한 split point를 찾아, information gain을 측정하는데, LightGBM에서는 모든 feature를 스캔하지않기위해, gradient-based One-Side Sampling 를 한다. (GOSS)

GBDT에는 weight는 없지만, gradient가 있다. 따라서 데이터의 개수를 내부적으로 줄여서 계산할 때, 큰 gradient를 가진 데이터는 그대로 사용하고, 낮은 gradient를 랜덤하게 drop하고 데이터를 가져와서, 샘플링을 해준다. gradient가 적다고 버리면 데이터 분포 자체가 왜곡될 수 있기에, 이대로 훈련하면 정확도가 낮아진다.

이를 방지하기위해 가져온 낮은 gradient 데이터에 대하여 ${1-a}\over{b}$ 만큼 뻥튀기 해준다.
(a: 큰 gradient데이터 비율, b: 작은 gradient 데이터 비율)

낮은 gradient를 가진 데이터만 drop하므로, One-Side Sampling이라고한다.
이렇게 feature를 줄여서 학습하는 것이다.

topN = a * len(I) ,전체 데이터의 a만큼 index (ex. 100개 중 a=0.2라면 topN=20)
randN = b* len(I) ,topN과 비슷하게 b만큼 index

1. 모델로 일단 예측
2. 실제값과의 error로 loss를 계산, weight를 계산하여 저장
3. loss대로 정렬 -> sorted에 저장. sorted[1:topN] 만큼 Loss 상위 데이터들 topSet에 저장 (ex. 전체 100개 중 a=0.2라면 20개)
4. 나머지 80개 중 randN개 만큼 랜덤샘플링하여 randSet에 저장 (ex. 나머지 80개 중 b=0.2라면 16개 데이터)
5. UsedSet에 topSet과 randSet을 저장
6. small gradient data에 fact(=${1-a}\over {b}$)만큼 weight를 부여해줌
7. weak learner를 만들어서 새로운 모델로 부여 , weak leaner에는 샘플링된 데이터(UsedSet = topSet + fact assigned randSet)와 loss와 weight가 들어감
8. 모델 저장

EFB (Exclusive Feature Bundling)

1. In a sparse feature space, many features are (almost) exclusive, i,e., they rarely take nonzero values simultaneously (ex. one-hot encoding)
2. Bundling these exclusive features does not degenerate the performance

1. 하나의 객체(feature)에 대해 특정 두개의 변수가 Non-Zero값을 갖는 경우가 드물다.
2. 그리하여 exclusive한 변수들을 번들링해도 성능저하가 거의 없다.

Greedy Bundling에서는 지금 현재 존재하는 feature set들에 대해서 어떠한 feature들을 하나의 번들로 묶을지 결정

Merge Exclusive Features에서는 번들링되어야하는 변수들을 이용, 하나의 변수로 값을 표현(Merge해줌)

예를들어 이러한 데이터셋(x1~x5) 먼저 각각의 conflict를 Edge로 하는 Graph를 생성한다 (오른쪽 위)
여기서 conflict는 서로 상충하는 데이터 개수(동시에 0이 아닌 데이터 개수)이다.
이를 바탕으로 오른쪽 아래의 Degree를 계산할 수 있고, 이를통해 시작점을 계산한다. 위의 그림에서는 x5부터 시작.

이렇게 그래프에서 x5부터 시작하며, 각각의 edge는 상충하는 데이터 개수(conflict)이다.
여기서 cut-off가 등장하는데, 이를 기준으로, 번들링에서 cut-off만큼 이상의 conflict라면, 하나의 번들로 묶지않는것이다.
위의 데이터에서는 10개 중 cut-off = 0.2로, 2개 이상 conflict 등장하면 엣지날림.
x5는 동떨어지게되므로 그대로가고,
x1을 계산할 때, x1과 x2는 6의 conflict로 날리고 x3도 날리면, ... x1,x4가 하나의 번들로 묶이게된다.
x2를 계산할 때, 이미 번들링된것을 제외하고, x3과 번들로 묶임. 더이상 묶을게 없으므로 종료.

이제 이렇게 묶은 번들에 대하여 Merge Exclusive Features를 진행한다.

각각 column(feature)에 대해 cardinality처럼 최대와 최소값을 기록하고, 기준이 되는 feature에 함께묶인 feature와 merge를 해주는것이다.
이때, 기준값이 있다면 그대로 기준값을 사용하고, 기준값이 없다면, 기준feature의 최대값 + 묶인녀석의 값을 해서 넣게된다.
conflict한 경우(둘다 값이 있을 때 or 둘다 0일때) 기준값을 사용한다. (빨강 박스)

사용 예

사이킷런 사용

import lightgbm
lgbm = lightgbm.LGBMClassifier(n_estimators=1500, n_jobs=-1, 
                            #    scale_pos_weight=(0.888/0.111)  # Unbalanced한 데이터
                                is_unbalance=True # Unbalanced한 데이터
                               )
eval_set=[(X_train,y_train),(X_val,y_val)]
lgbm.fit(X_train,y_train, eval_set=eval_set,eval_metric='f1',verbose=50 ,early_stopping_rounds=100)
lgbpred = lgbm.predict(X_val)

print(confusion_matrix(y_val, lgbpred))
print('Accuracy Score : ',accuracy_score(y_val, lgbpred))
print('F1 Score : ',f1_score(y_val, lgbpred))
print('\nRandomForest Regression Matrix\n' , classification_report(y_val, lgbpred))

Parameter Tunning

BayesianOptimization

!pip install bayesian-optimization
from bayes_opt import BayesianOptimization

def bayesian_param_opt_lgb(X,y,init_round=15,opt_round=25,n_folds=5,random_seed=42,n_estimators=10000,learning_rate=0.05, output_process=False):
    train_data=lightgbm.Dataset(data=X_train, label=y)
    def lgb_eval(num_leaves, feature_fraction, bagging_fraction, max_depth, min_split_gain, min_child_weight):
        params={'application':'binary','num_iterations': n_estimators, 'learning_rate':learning_rate,'early_stopping_round':100,'metric':'auc'}
        params['num_leaves'] = int(round(num_leaves))
        params['feature_fraction'] = max(min(feature_fraction,1),0)
        params['bagging_fraction'] = max(min(bagging_fraction,1),0)
        params['max_depth'] = int(round(max_depth))
        params['min_split_gain'] = min_split_gain
        params['min_child_weight'] = min_child_weight
        cv_result=lightgbm.cv(params, train_data, nfold=n_folds,seed=random_seed, stratified=True, verbose_eval=200, metrics=['auc'])
        return max(cv_result['auc-mean'])
    lgbBO=BayesianOptimization(lgb_eval, {'num_leaves':(24,45),
                                          'feature_fraction':(0.1,0.9),
                                          'bagging_fraction':(0.8,1),
                                          'max_depth':(5,9),
                                          'min_split_gain':(0.001,0.1),
                                          'min_child_weight':(5,50)}, random_state=42)
    lgbBO.maximize(init_points=init_round, n_iter=opt_round)
    return lgbBO
opt_params=bayesian_param_opt_lgb(X_train,y_train)##,init_round=5, opt_round=10, n_folds=3, random_seed=42, n_estimators=100,learning_rate=0.05)

Featrue Importance를 확인해볼 수 있는 모듈을 제공한다.

from lightgbm import plot_importance
plot_importance(lgb_model)

또한, eli5를 통해 Permutation Importance를 볼 수 있고, pdpbox의 pdp_plot, shap으로도 feature_importance를 볼 수 있다.

핵심 파라미터

max_depth : Tree의 최대 깊이를 말합니다. 이 파라미터는 모델 과적합을 다룰 때 사용됩니다. 만약 여러분의 모델이 과적합된 것 같다고 느끼신다면 제 조언은 max_depth 값을 줄이라는 것입니다.

min_data_in_leaf : Leaf가 가지고 있는 최소한의 레코드 수입니다. 디폴트값은 20으로 최적 값입니다. 과적합을 해결할 때 사용되는 파라미터입니다.

feature_fraction : Boosting (나중에 다뤄질 것입니다) 이 랜덤 포레스트일 경우 사용합니다. 0.8 feature_fraction의 의미는 Light GBM이 Tree를 만들 때 매번 각각의 iteration 반복에서 파라미터 중에서 80%를 랜덤하게 선택하는 것을 의미합니다.

bagging_fraction : 매번 iteration을 돌 때 사용되는 데이터의 일부를 선택하는데 트레이닝 속도를 높이고 과적합을 방지할 때 주로 사용됩니다.

early_stopping_round : 이 파라미터는 분석 속도를 높이는데 도움이 됩니다. 모델은 만약 어떤 validation 데이터 중 하나의 지표가 지난 early_stopping_round 라운드에서 향상되지 않았다면 학습을 중단합니다. 이는 지나친 iteration을 줄이는데 도움이 됩니다.

lambda : lambda 값은 regularization 정규화를 합니다. 일반적인 값의 범위는 0 에서 1 사이입니다.

min_gain_to_split : 이 파라미터는 분기하기 위해 필요한 최소한의 gain을 의미합니다. Tree에서 유용한 분기의 수를 컨트롤하는데 사용됩니다.

max_cat_group : 카테고리 수가 클 때, 과적합을 방지하는 분기 포인트를 찾습니다. 그래서 Light GBM 알고리즘이 카테고리 그룹을 max_cat_group 그룹으로 합치고 그룹 경계선에서 분기 포인트를 찾습니다. 디폴트 값은 64 입니다.

출처 :
LightGBM
Go Lab
고려대 일반대학원 산업경영공학과 비즈니스 애널리틱스 강의 (Pilsung Kang교수님)
파라미터튜닝
https://lsjsj92.tistory.com/548?category=853217
https://lightgbm.readthedocs.io/en/latest/Python-Intro.html#setting-parameters
http://machinelearningkorea.com/2019/09/25/lightgbm의-핵심이해/