GBM(XGB, LightGBM, Catboost)

GBM(Gradient Boosting Model) : Tree 기반의 모델.

- Gradient Descent(경사하강법)을 사용한 boosting(앙상블 알고리즘) 기법

- Adaboost는 오 분류에 대해 weight를 조절하여 bootstrap을 생성했다면 GBM은 전체적인 residual(잔차)에 대해 minimize하는 방식으로 진행.

 

Gradient Descent(=negative gradient)

- 즉 gradient(기울기)가 감소하는 방향(-)으로 학습을 진행하므로 negative라는 말을 씀.

- loss function이 MSE라고 일 때 negative gradient를 구해보자.

gradient(기울기)를 구하기 위해서 f(x)에 대해서 미분을 진행.

 

Gradient Desent가 결국 residual과 식이 똑같다..!(=결국 loss를 표현한 것)

- 결국 이를 목적식으로 하여 학습을 진행하다보면 그 다음모델은 residual을 줄이는 방향으로 학습하게 된다.

- GBM 알고리즘은 tree를 단계적으로 하나씩 결합해 나가는데 Sequential하게 각 tree의 예측 결과를 합산해 나간다. 

 

pseudo-code

1. initialize model F(x) with a random parameters.

 

for m=1 to M(number of iterations)

    2. compute pseudo-residuals (error)

    3. fit F(x) to error → training set (x, error) → called model h(x)

    4. compute multiplier(learning rate) a

    5. update F(x) = F(x) + a * h(x)

 

output: F(x)

 

GBM pseudo-code

 

 

1. XGB(GBM + regularization + parallelism)

- GBM의 과적합 문제 해결(by similarity score) + 학습속도 개선(parallelism)

 

similarity score : (잔차의 합)**2 / N(데이터 개수)

    - 잔차의 합이 0에 가까워질수록 모델의 성능이 좋음. 

 

모델을 생성할 때 similarity score를 활용하여 Similarity(parent) - Similarity(child) > threhold 일 때 분기 진행.

    - 둘의 차이가 유의미할 때만 분기를 진행. 즉 overfitting 방지.

 

parallelism : cache-aware block structure 사용

    - CPU cache miss가 발생(=병목 현상) greedy search 속도 저하를 방지하기 위해 개별 thread마다 internal buffer 배정하는 구조

    - 데이터 정렬 연산을 최소화하기 위해 block이라는 in-memory unit을 활용하여 연산 결과를 block 단위 재사용.

 

 

2. LightGBM

- XGB. but leaf-wise tree.

- 특징: GOSS(Gradient based One-Sided Sampling), EFB(Exclusive Feature Bunding)

 

GOSS(Gradient based One-Sided Sampling)

- 큰 gradient를 가지는 관측치는 유지하고 작은 gradient를 가지는 관측치는 random drop 진행.

- 즉 상대적으로 중요하지 않은 관측치는 크게 고려하지 않음.

 

EFB(Exclusive Feature Bunding)

- 상호 배타적인 변수는 묶음 처리.

- if feature1 : [1,3,4,0,0,0], feature2 : [0,0,0,18,13,20] → feature:[1,3,4,18,13,20]

 

**정확성에서 GBM에 크게 밀리지 않으며 학습 속도는 매우 빠르다.

 

3. Catboost

- XGB + 범주형 변수 자체 처리 기능 추가(ordered-target encoding)

- categorical feature combinations: 자체적 feature selection 진행.

- random permutation: 데이터셋 shuffle

- ordered boosting : 예측 & 잔차 계산 및 모델 업데이트를 매 row마다 진행.

** 기본 파라미터가 최적화로 잘 되어있어서, 파라미터 튜닝에 크게 신경쓰지 않아도 된다.

    - but sparse matrix 안됨.

    -  수치형 변수가 대부분일 경우 오래걸림.