Ensemble Learning - Gradient Boosting Machine

July 07, 2022

2022   ·   machine-learning  

Contents

  • Gradient Boosting Machine: GBM
  • The Gradient
  • Regularization of GBM
    • Subsampling
    • Shrinkage
    • Early Stopping
  • Variable Importance in Tree-based GBM

해당 포스트는 2021년 1학기 고려대학교 강필성 교수님의 ‘다변량분석’ 강의를 참고하여 작성되었습니다.

이미지는 강필성 교수님의 강의 슬라이드에서 발췌하였습니다.

A+ 감사했습니다 교수님

Gradient Boosting Machine: GBM

앙상블 기법은 크게 병렬처리가 가능한 bagging, 그리고 불가능한 boosting 방법론들로 나뉜다. Gradient Boosting Machine (GBM) 은 이름에서 알 수 있듯이 Boosting 방법론 중 하나이며, weak model 을 guide 로 학습을 진행한다. Boosting 방법론들 중 shortcomings 라는 단어가 쓰이는데, 이는 Boosting 모델이 이전 단계에서 효과적으로 학습을 진행하지 못했기에 가중치로 삼을 객체를 의미한다. 예시로, AdaBoost 의 shortcomings 는 분류를 잘 못한 샘플 \(i\) 에 대한 가중합이다. GBM 은 shortcomings 를 이름에서 알 수 있듯이 gradient, 즉 경사를 사용한다.

GBM 은 머신러닝의 대표적인 3가지 task 인 regression, classificaiton, ranking 에 전부 적용 할 수 있다. 하지만 Gradient, 즉 손실함수에 대한 1차도함수를 계산하는 과정이 있기 때문에 base model 의 손실함수를 미분할 때의 computational complexity 에 따라 difficulty 를 매기기도 한다. 일반적으론 Regression < Classification < Ranking 의 Difficulty 를 가진다.

GBM 의 기본 개념은 (Regression 모델을 예시로 두었을 때) 잔차에서 비롯된다. 먼저 설명변수와 종속변수를 잘 설명하는 회귀식을 구축 한 다음, 각 샘플에 대한 잔차를 계산한다. Boosting 방법론이기 때문에 그 다음 모델을 학습하는데, 이때 다음 모델의 종속변수로 이전 단계의 모델의 잔차를 사용한다. 즉, 다음 단계의 모델은 이전 단계의 모델의 에러를 예측하는 모델을 구축하는 것이다.

The Gradient

GBM 에서의 Gradient 라는 워딩은 경사하강법과 연결된다. 예시로, 다중선형회귀분석의 손실함수로 OLS 를 사용한다.

\[\textbf{min}\ L = {1 \over 2} \sum ^n_{i=1} (y_i - f(\mathbf{x}_i))^2\]

이때 \(\mathbf{x_i}\) 에 대한 손실함수의 1차도함수는 다음과 같다.

\[{\partial L \over \partial f(\mathbf{x}_i)} = f(\mathbf{x}_i) - y_i\]

이를 잔차에 대해 정리를 하면 다음과 같다.

\[y_i - f(\mathbf{x}_i) = - {\partial L \over \partial f(\mathbf{x}_i)}\]

즉, 잔차를 손실함수의 negative gradient 로 표현 할 수 있다. 그렇기에 GBM 의 모델들을 학습시킬 때 종속변수를 각 샘플에 대한 이전 단계의 모델의 negative gradient 로 설정하는 것이 잔차로 설정하는 것과 동일한 효과를 낸다. 결국 GBM 은 매 iteration 마다 전 단계의 gradient 만큼만 학습시키는 것이다.

위 예시는 base learner 을 regression stump tree 로 사용한 GBM 모델이다. Regression stump tree 는 split 을 기준으로 해당 영역의 샘플들의 평균으로 예측을 해주는 모델이다. 첫째 모델은 하나의 split 을 보이며, 이에 따른 잔차들을 기준으로 두번째 모델을 학습시킨다. Iteration 을 거듭할 수록 값들을 잘 예측하는 것을 볼 수 있으며, 최종 모델의 잔차들은 거의 0에 수렴하는 것을 볼 수 있다.

Regularization of GBM

GBM 의 알고리즘은 위와 같다. AdaBoost 와는 달리, 마지막에 학습된 모든 모델을 aggregate 하지 않고 마지막 iteration \(M\) 에서 구한 모델을 최종 모델로 사용한다. GBM 은 사용하는 손실함수에 따라 알고리즘의 차이가 날 수 있다.

Regression 을 위한 GBM 에서는 대표적으로 \(L_1\) Loss, \(L_2\) Loss, Huber Loss, Quantile Loss 를 사용하며,

Classification 을 위한 GBM 에서는 대표적으로 Bernoulli Loss, AdaBoost Loss 를 사용한다. 이때 주어진 task 가 Binary classification 이면 AdaBoost 와 동일하게 초기 정답라벨을 \(y \in \{-1,1\}\) 로 사용한다.

GBM 은 이전 단계 모델의 잔차를 이용한 학습을 한다는 특징이 있기 때문에, 과적합의 고질적인 문제가 있다. 실제 모델엔 어쩔 수 없는 noise 인 \(\epsilon\) 이 포함되있길 마련인데, 잔차에 이런 noise 가 포함되어있을 확률이 높기 때문이다. 그렇기에 GBM 에선 여러가지 정규화 방법론이 쓰인다.

1. Subsampling

첫번째 정규화 방법론은 subsampling 이다. AdaBoost 에선 각 샘플이 뽑힐 확률을 높혀주는 가중치를 통한 복원추출로 데이터셋을 만들지만, 기본적인 GBM 모델은 모든 샘플을 그대로 사용한다. 하지만 모든 샘플을 사용하면 과적합의 위험이 있기에, 각 iteration 마다 데이터셋의 subset 만 사용하는 것이 subsampling 이다. 이때 GBM 에서 사용되는 subsampling 의 특징은 AdaBoost, Bagging 과는 다른 비복원추출이라는 점이다.

만약 샘플률을 80%라고 가정하면 매 iteration 마다 샘플의 수가 줄어드는 것이라고 생각할 수 있지만, 아니다.

10개의 샘플을 가진 기존 데이터셋에서 두번째 데이터셋을 만들 때 8개가 랜덤추출되며, 8개의 샘플에 대한 잔차가 두번째 모델을 학습시키기 위한 정답라벨이 된다. 이후 세번째 데이터셋은 기존 데이터셋에서의 80% 인 8개를 추출하며, 이 8개의 샘플에 대해 첫번째 모델과 두번째 모델을 합친 모델에서의 잔차를 계산하여 세번째 모델의 학습에 사용된다.

2. Shrinkage

이전에 살펴본 Shrinkage methods 와 동일한 맥락으로, 특정 객체의 impact 를 줄여주는 가중치를 추가하는 방법론이다. 기본 GBM 에선 매 iteration 마다 만들어지는 모델의 가중치가 동일하다면, Shrinkage method 를 사용한 GBM 은 factor \(\lambda\) 를 추가하여 나중에 만들어지는 모델의 영향력을 감소시킨다.

3. Early Stopping

다른 인공신경망 모델들에서 사용되는 동일한 방법론으로, Validation Error 을 통해 급격히 증가할것같은 구간에서 알고리즘을 미리 종료하는 방법론이다.

Variable Importance in Tree-based GBM

Kaggle 에서 진행되는 대회들을 보면, 상위권엔 항상 앙상블 방법론들이 있다. 이중 Random Forest 와 GBM 이 압도적으로 쌍벽을 이루는 경우가 많은데, 이 두 알고리즘은 모델의 성능을 향상시켜줄 뿐만 아니라 변수의 중요도 또한 산출하기 때문이다. RF 와 동일하게 base learner 를 Decision tree (혹은 stump tree) 를 사용 할 시, Influence 를 계산하여 최종 모델을 구축하는데 있어 각 변수의 중요도를 계산할 수 있다.

\[Influence_j(T) = \sum^{L-1}_{i=1}(IG_i \times \mathbf{1}(S_i=j))\]

\(Influence_j(T)\) 는 단일 tree \(T\) 에서 사용된 변수 \(j\) 에 대한 중요도의 계산식이다.

해당 tree \(T\) 에 \(L\) 개의 leaf node 가 있으면, split 의 개수는 \(L-1\) 이다.

\(IG_i\) 는 Information gain, 즉 혼잡도의 감소를 나타내며 \(\mathbf{1}(S_i=j)\) 는 단순히 해당 split \(i\) 에서 변수 \(j\) 를 사용했다면 1을 반환해주는 함수다.

즉, 단일 tree 에 대한 변수 \(j\) 의 중요도는 해당 tree 에서 해당 변수가 사용되었을 때 Information Gain 의 합이다.

\[Influence_j = {1\over M}\sum^M_{k=1}Influence_j(T_k)\]

전체 GBM 모델에 대한 변수 \(j\) 의 중요도는 위 식으로 구할 수 있다. 단순히 모든 Tree 에 대한 \(j\) 의 중요도의 평균이다.