[Boosting] 4. XGBoost, Light GBM

[사전정리]

1) GBM : 반복 수행을 통해 오류를 최소화 할 수 있도록 가중치의 업데이트 값을 도출하는 기법

 

2) XGBoost : GBM에 기반하지만, GBM의 단점인 느린 수행 시간 및 과적합 규제 부재 등의 문제를

해결하여 각광받고 있는 알고리즘

 

3) Light GBM : 리프 중심 트리 분할로 더 빠른 학습 & 예측 수행 시간과 적은 메모리 사용량의 장점을

지님

 

 

[XGBoost]

 XGBoost (eXtra Gradient Boost)는 GBM에 기반한, 트리 기반의 앙상블 알고리즘이다. XGBoost의 대표적인 특징들은 다음과 같다.

 

- 병렬 CPU 환경에서 병렬 학습이 가능해 기존 GBM 보다 빠르게 학습 완료

- 과적합 규제 가능

- Tree pruning (나무 가지치기)

- 조기 종료 기능 내재

- 결측값 자체 처리

 

 GBM은 residual을 계속 줄이기 때문에 과적합이 된다는 문제가 존재한다. GBM의 과적합을 해결하기 위해 GBM에 regularization term을 추가한 것이 XGBoost 알고리즘이다.

 

 XGBoost는 CART (Classification And Regression Trees) 앙상블 모델을 사용한다. 리프 노드 하나에 대해만 값을 갖는 의사결정나무와 달리, CART는 모든 리프들이 최종 스코어에 연관이 있다. 즉, 의사결정트리가 분류를 제대로 했는지 초점을 맞춘다면 CART는 최종스코어를 비교하는 것이다.

 

 

 

[LGBM]

 전통적인 GBM은 모든 객체들 및 변수에 대해 스캔을 쭉 하고 gradient를 측정한다. (여기서 XGBoost는 모든 객체에 대해 스캔하는 부분을 완화시킨 것이다.) 앞의 두 부분을 줄이기 위해 Light GBM은 2가지 방법을 채택한다.

 

1. Gradient-based one-Side Sampling (GOSS)

-> 각 객체는 서로 다른 gradient를 가지고 있음

-> Large gradient는 keep 하고 작은 gradient는 랜덤하게 드롭 (필요없다고 생각하는 부분은 랜덤하게

드롭)

 

2. Exclusive Feature Bundling(EFB)

-> 모든 변수를 전부 탐색하는 비효율성을 줄임

 

Light GBM의 트리 분할 방식을 살펴보자. '다른 GBM 계열 트리 분할 방식'은 Level-Wise로 수평적으로 확장한다. 그러나 'LightGBM의 트리 분할 방식'은 Leaf-Wise로 수직적으로 확장한다.

 

분할 방식 차이

 

 tree가 수평적으로 확장하는 경우에는 균형을 잡아주기에 depth가 줄어든다. 이는 과적합에 강한 구조이다. 그러나 균형을 잡아주는 과정에서 연산이 추가적으로 들어가서 소요되는 시간이 늘어난다.

 

 tree가 수직적으로 확장하는 경우에는 max delta loss를 가진 leaf를 선택해서 분할한다. 이는 비대칭적이고 깊은 tree가 생성되게 한다. 또한 예측 오류 손실을 최소화한다. 

 

 

Light GBM에는 여러 장점이 있다.

- 더 빠른 학습과 예측 시간

- 더 적은 메모리 사용

- 범주형 피처의 자동 변환과 최적 분할 (원핫인코딩을 사용하지 않고도 범주형 피처를 최적으로 변환하고 이에 따른 노드 분할 수행)

 

Light GBM은 적은 데이터 세트에 사용할 경우 과적합이 발생할 가능성이 높다. 여기서 적은 데이터 세트란 10000개 이하의 관측치를 의미한다.

 

 

 

https://github.com/rch1025/Algorithm

rch1025/Algorithm