[4-3] Adaptive Boosting, GBM, XGBoost

Adaptive Boosting

Stump Tree 와 같은 Weak Model 이 Boosting 을 사용하여서 성능이 개선될 수 있다. Weak Model 이란 Random Guessing 보다 조금 더 잘하는 모델이다. 예를 들어 0.5, 0.5 확률에서 0.6, 0.4 확률로 맞춘다면 약한 모델이라 할 수 있다.

Bagging vs Adaptive Boosting

Bagging : 복원 추출은 병렬적으로 수행이 가능함.
Adaptive Boosting : 순차적으로 수행이 가능함(병렬 수행이 불가능). 이전 모델이 수행된 후, 분류하기 어려운 데이터 셋에 가중치를 높게 주어 다음 모델에 들어갈 데이터들을 샘플링함. (Execute First Model -> Re-weight Training Data -> Resample) 병렬 수행이 불가능하지만, Bagging이 워낙 복잡한 모델을 사용할 경우, 수행속도가 빠를때도 있음.

위 그림은 카카오친구들이 퀴즈쇼에 나가기 위해 일주 전부터 AdaBoosting 기법으로 공부중이다.

일단, 우리가 퀴즈쇼에 나가기 위해 책을 사서 열심히 공부해보자! 근데 어떤 책을 사지? 어피치 너 일단 책 풀어봐! 어피치는 과학 영역을 잘하고, 나머지 과목은 잘 못하네 ~ 튜브 너가 풀어봐 ! 튜브는 예술영역은 만점인데 다른건 다 빵점이야, 다음은 무지가 풀어볼게! 무지는 수학을 잘하구나! 프로도는 역사, 네오는 식품, 제이지는 음악을 잘하니깐, 각자 잘 하는 영역의 책을 사서 공부해와!

반면, Bagging 기법으로 공부한 팀은 서점에서 랜덤한 6개의 문제집을 사서 각자 맡아서 학습하는 방식이다.

AdaBoost Pseudo Code

$T$ : Base Learner 의 수이다. (ex. 50~100)
이범주 분류는 {1, -1} 로 정의한다. 수식계산을 위해서이다. 로지스틱 회귀에서는 {0, 1} 로 정의한다.
$D_t(i) : i$ 번째 데이터 셋이 t 시점에서 선택될 확률, 초기에는 균등분포(uniform distribution)임
$h_t :$ 모델, Stump Tree 를 Base Learner 로 사용한다. Stump 는 기둥이란 뜻으로 한 번의 분류만을 사용하는 것을 의미한다. 즉 한번의 분류이므로 약한 모델이라 할 수 있다.
$\epsilon_t : D_t$ 를 $h_t$ 에 학습하였을 시, 오분류한 확률을 의미한다. 10 개중 3개를 틀렸으면, 0.3 이다. 만약 이 $\epsilon_t$ 가 0.5보다 클 경우 랜덤 추측보다 못하였으므로 반복문을 break 한다.
$\alpha_t :$ 위 $\epsilon_t$ 가 0.5보다 크므로 항상 양수값을 갖는다. 오답율이 클경우, 0과 가까워지며, 오답률이 적을 수록 무한대로 수렴한다. 즉, 모델의 신뢰도를 의미한다.

\alpha_t = \frac{1}{2} ln(\frac{1-\epsilon_t}{\epsilon_t})

\alpha_t =\begin{cases} 0 & \frac{1}{2}ln(\frac{1-0.5}{0.5}) = 0 \\ \infty & \frac{1}{2}ln(\frac{1-0}{0}) = \infty \end{cases}

$D_{t+1}(i)$
- 오답이면, 지수함수 $e^x$ 의 $x$ 가 양수임. -> 샘플링 확률이 증가함.
- 오답이 아니면, $x$ 가 음수임 -> 샘플링 확률이 감소함.
- $\alpha_t$ 가 증가할수록 (Strong model) 일수록 샘플링 증폭이 커짐.

\frac{D_{t}(i) exp(-\alpha_t y_ih_t(x_i))}{Z_t}

복잡한 분류 경계면을 만들 수 있음.

최종 분류기의 값 H(x) 는 각 앙상블 모델의 예측값에 모델 신뢰도를 가중한 합이라고 볼 수 있다.

H(x')=sign(\sum_{t=1}^T\alpha_th_t(x'))

GBM (Gradient Boosting Machine)

GBM 의 특징

Regression, Classification, Ranking 모든 분야에 사용할 수 있지만, Regression 방법으로 해야 이해하기 쉽다.
현실에서 일어날 수 있는 노이즈조차도 학습을 통해 외운다는 알고리즘이기 때문에 과적합의 단점이 있다.

GBM Pseudo Code

$f_0(x) :$ 원래 데이터 $y$ 에 회기시키는 첫번째 모형을 만든다.
$m :$ 모델 수이다.
1. $i:$ 데이터의 수이다.
2. $r_{im}:$ $y_i-f(x_i)$ 이전 모델과 실제 값의 에러 (음의 그라디언트)
3. $\gamma_{jm} :$ 위 차이를 회귀시키는 모델을 만듦
4. $f_m(x) = f_{m-1}(x) +\sum_{j=1}^{J_m}\gamma_{jm}I(x \in R_{jm})$ 이전 모델과 에러의 합이다.
5. 최종 예측값은 마지막 모델의 예측값이다.

Why Gradient Boosting 인가?

GBM 의 원리를 보면 앞선 모델이 맞추지 못한 그 에러 차이 $y_i-f(x_i)$ 만큼을 학습시키는 모델을 만든다. 최소자승법을 오차함수로 정의할때, 오차함수를 최소화시키기 위해 $f(x)$ 에 대한 오차함수의 미분값은 0이 되어야 하기 때문에 이를 풀어보면, 모델이 추정하고자 하는 오차는 negative gradient 와 같다.

g^t(x, y):= \frac{\partial L(y,s)}{\partial s}|_{s=F^{t-1}(x)}

gradient 가 0 이면 종료되지만, 0이 아니면, gradient 의 음의 방향만큼 이동한다.

min L = \frac{1}{2} \sum_{i=1}^{n}(y_i-f(x_i))^2

\frac{\partial L}{\partial f(x_i)} = f(x_i)-y_i

y_i-f(x_i) = -\frac{\partial L}{\partial f(x_i)}

Loss Function

Regression

Squared Loss
Absolute Loss
Huber Loss
Quantile Loss

Classification

$y \in \{-1, 1\}$ 를 사용한다.

Bernoulli Loss
Adaboost Loss

-1~1지점을 살펴보면, Adaboost (B)를 사용하였을때, 극단적인 분포로 표현된다.

How to prevent overfitting of GBM

Subsampling (Regularization) : 훈련 데이터셋의 랜덤으로 복원/비복원 추출된 80% 의 데이터만을 가지고 지속적 학습함.
Shrinkage (Regularization) : 뒤에 만들어지는 모델의 영향력을 줄여준다.
Early Stopping : Validation Data 정확도가 증가할경우 일찍 줄여준다.

GBM Variable Importance

Influence_j(T) = \sum_{i=1}^{L-1}(IG_i*(S_i=j))

GBM vs Random Forest

GBM

Performance

Good

Variable Importance

Yes

XGBoost

2016년 A Scalable Tree Boosting System 논문에 발표된 알고리즘이다. Boosting 계열의 기법 모델을 정리하면 아래와 같다.

Decision Tree, Bagging, Random Forest, AdaBoost, Gradient Boost, 그리고 이번 장에서 이야기할 XGBoost 이다.

XGBoost 도 GBM 이다. 다만, 효율성을 높인 GBM 이라고 할 수 있다. XGBoost 는 다음 6가지 방법을 통해서 효율성을 높이었다.

Split Finding Algorithm

의사결정트리에서 모든 속성들을 분류기준으로 Split 해보면서, 엔트로피를 낮게 하는 속성을 찾는다. 전역적 탐색인 것이다.

Exact Greedy Algorithm for Split Finding 의 장점은 Global Optimal Solution 을 찾을 수 있는 것이고, 하지만 대용량의 전체 데이터가 메모리에 로딩되지 않을 경우, 즉 분산 처리 환경에서 수행할 수 없는 알고리즘이다. 따라서 이를 근사하는 알고리즘이 존재한다.
Approximate Algorithm for Split Finding 의 원리는 그림과 같다. 그리고 per tree(global) 방식과 per split(local) 방식으로 구분된다.