XGBoost, LightGBM, CatBoost 정리 및 비교

 도입

Kaggle을 비롯한 데이터 경진대회 플랫폼에서 항상 상위권을 차지하는 알고리즘 XGBoost, LightGBM, CatBoost에 대해 정리하고 차이점을 비교해보고자 합니다. 세 알고리즘은 모두 Gradient Boosting기반의 Machine Learning 기법으로,

XGBoost(2014년), LightGBM(2016년), CatBoost(2017년)에 Inital release되었습니다. 물론 initial release시기가 이럴 뿐 실제로 사람들이 많이 사용하기 시작한 시기는 알고리즘 모두 Initial release 기준으로 살짝 뒤로 밀려있다고 보여집니다.

 

알고리즘을 하나씩 정리하면서 차이점을 비교분석 해보겠습니다!

---

XGBoost

XGBoost는 기본적으로 GBM과 같이 decision Tree의 앙상블 모형입니다.  GBM을 더 발전시킨 모형이라고 생각하시면 됩니다. Image나 Text와 같은 비정형데이터에서는 Nerual Network 모델이 압도적인 성능을 보이고 있지만, 정형데이터에서는 XGBoost와 같은 tree based 알고리즘이 현재까지는 가장 좋은 알고리즘으로 평가받습니다.

 

출처 : https://towardsdatascience.com/https-medium-com-vishalmorde-xgboost-algorithm-long-she-may-rein-edd9f99be63d

Decision Tree 기반의 알고리즘의 발전과정

 

그렇다면 GBM과 어떤 차이를 두었기에 XGBoost는 그렇게 좋은 성능을 낼 수 있을까요?

정답은 딱 두가지 입니다. Optimization and alorithmic 즉, 최적화와 알고리즘입니다.

출처 : https://towardsdatascience.com/https-medium-com-vishalmorde-xgboost-algorithm-long-she-may-rein-edd9f99be63d

이미지 - GBM과 비교한 XGBoost의 장점

 

System Optimization

 

- Parallelization(병렬 처리) : XGBoost는 병렬 처리를 지원합니다. 단순하게 2중 loop 문을 생각해보면, 기존에는 inner loop를 처리해야만 outer loop가 돌아가는 구조였다면 XGBoost에서는 실행 속도를 개선하기 위해서 모든 인스턴스의 글로벌 검색을 통한 초기화와 Parallel thread를 사용한 정렬을 통해서 루프 순서를 상호 변경할 수 있게 했습니다.(저 또한 이 말을 이해하기 어렵지만, 실행 속도 개선을 위한 병렬 처리를 위해 학습모델의 구조를 바꿨다고 이해하면 될 것 같습니다). 이러한 변화가 컴퓨팅계산에 있어 overheads를 상쇄시킴으로써 성능을 향상시킵니다.

 

개인적으로 Parallelization을 이해하기 어려웠는데 아래 블로그에서 잘 정리 되어있어서 참고해주시면 될것 같습니다.

 

m.blog.naver.com/nicolechae0627/221811579005

[내가 공부하려고 정리하는 머신러닝] XGBoost vs GBM

 

- Tree Pruning(가지치기) : XGBoost는 criterion first 방식 대신에 'max_depth' 파라미터를 정해줍니다. 이러한 'depth-first' 방식은 계산상의 이득을 상당히 많이 가져와주었습니다.

 

- Hardware Optimization(하드웨어 최적화) : XGBoost는 하드웨어 자원을 효율적으로 이용할 수 있도록 디자인 하였습니다. gradient 통계값을 저장하기 위해 캐쉬 메모리의 기억 저장소를 이용하여 internal buffer에 각 스레드를 할당 하였습니다. out-of-core컴퓨팅과 같은 향상된 기능은 메모리에 맞지 않는 빅데이터프레임도 처리하면서 Disk 공간을 최적화 합니다.

 

Algorithmic Enhancements

 

1. Regularization : Lasso(L1)와 Ridge(L2) 규제를 통해서 모델에 penalty를 부여합니다. 이러한 방법은 Overfitting을 잡을 수 있습니다. L1 L2규제와 관련된 내용은 제가 예전에 포스팅 했던 statinknu.tistory.com/23?category=930853

DNN(Deep Neural Net)의 전체적인 Flow

에 간단하게 정리 되어있습니다.

 

2. Sparsity Awareness : XGBoost는 Training loss에 따라 최상의 결측값을 자동으로 학습함으로써 Sparsity를 인정하고 다양한 데이터 유형의 Sparse pattern을 효율적으로 처리합니다. 

 

3. Weighted Quantile Sketch : XGBoost는 "distributed weighted Quatile sketch" 알고리즘을 사용하여 최적의 분기점을 효율적으로 찾아냅니다.

 

4. Cross-validation : Cross validation이 빌트인 되어있습니다.  

 

XGBoost는 짧지만 한 시대를 휩쓴 알고리즘입니다. 한 동안 Kaggle 경진대회마다 상위권은 XGBoost알고리즘이 독차지 했었던 역사가 있었습니다. 현재는 좀 더 빠르고 좋은 성능의 알고리즘이 출시되고있지만 머신러닝을 활용할 때 빼놓을 수 없는 방법론입니다.

 

LightGBM과 CatBoost는 각 차이점을 비교하면서 정리하겠습니다.

 

---

LightGBM

LightGBM의 메인 기술은 GOSS(Gradient-based One-Side Sampling)입니다. GOSS는 Information gain을 계산할 때 기울기가 작은(가중치가 작은)개체에 승수 상수를 적용하여 데이터를 증폭시킵니다. 이렇게 함으로써 데이터 분포를 많이 변경하지 안혹도 훈련이 덜 된 개체에 초점을 보다 잘 맞출 수 있습니다.

이러한 방법은 LightGBM이 XGBoost보다 속도와 성능면에서 모두 좋은 퍼포먼스를 가질 수 있게 했습니다. (특히 속도)

 

출처 ; https://datascience.stackexchange.com/questions/26699/decision-trees-leaf-wise-best-first-and-level-wise-tree-traverse

출처 : https://datascience.stackexchange.com/questions/26699/decision-trees-leaf-wise-best-first-and-level-wise-tree-traverse

일반 GBM 계열의 트리는 level-wise(균형 트리 분할) 방식을 채택합니다. 그림을 보시면 알겠지만 항상 균형을 이루며 2진 분할을 하고 있습니다.

반면 LightGBM에서 채택한 leaf-wise(리프 중심 트리 분할)은 트리가 깊어지면서 소요되는 시간과 메모리 모두를 절약 할 수 있었습니다.

 

LightGBM은 위와 같은 방법을 통해서 굉장히 가벼운 알고리즘이면서도 좋은 성능을 낼 수 있었는데요, 단점은 없을까요?

공식문서에서는 적은 데이터에 대한 Overfitting이 일어나기 쉽다고 말하고있습니다. 여기서 '적다'의 기준은 약 10000건 으로 보고있습니다.

 

---

CatBoost

CatBoost의 약자는 Categorical Boosting 입니다. 이름 그대로 Catergorical feature를 처리하는데 중점을 둔 알고리즘입니다. 기존 GBM기반 알고리즘들이 가지고 있는 target leakage 문제와 범주형 변수 처리 문제를 ordering principle과 새로운 범주형 변수 처리 방법으로 해결하고자 나왔습니다.

 

범주형 변수는 이산적인 값을 가지며 서로 비교할 수 없는 변수이기 때문에 기존에 one-hot encoding을 할용해서 해결 했었습니다. One-hot encoding을 해보신 분들은 아시겠지만, one-hot encoding은 변수의 수를 급격하게 증가 시킬 수 있습니다. 이러한 문제를 해결하고자 몇개의 클러스터로 묶고 one-hot encoding을 하거나 범주의 Target Statistics(TS)를 추정하여 사용하는 방법이 있습니다.

 

- 기존 LightGBM은 매번 boosting round에서 범주형 변수를 gradient statistics를 활용해서 변환하여 계산시간과 메모리를 많이 잡아 먹었던 것과는 비교되는 부분입니다. -

 

Greedy TS는 각 범주 특성의 y 평균값으로 추정하는데 이때 target leakage가 동일하게 발생하고 overfitting이 될 위험이 있습니다.

Hold-out TS는 이를 개선하여 train data를 나누어 한 데이터셋은 TS 추정에, 다른 하나는 학습에 사용하여 overfitting을 줄일 수 있습니다. 하지만 이런 방법은 학습 데이터의 양이 줄어든다는 단점이 있습니다.

그래서 CatBoost는 ordering principle을 적용한 Orderd TS를 제안합니다.

Ordered TS는 TS 추정치를 observed history에서만 구하는 방식입니다. 현 시점을 기준으로 과거 데이터로만 TS를 추정하기 위해서 무작위 순열(인공적인 시간)을 도입합니다. 하나의 무작위 순열만으로 TS를 추정하면 과거 TS추정치는 이후 추정치보다 분산이 높을 것이기 때문에 각 단계마다 다른 무작위 순열을 활용합니다.

 

또한 Target leakage, Predcition Shift로 인한 overfitting에 대한 해결 방법으로 ordering principle을 제안합니다. 매 boosting round마다 같은 데이터를 이용하여 잔차를 구하고 학습하기 때문에 Overfitting이 일어나는데 이를 해결하기 위해 ordered TS와 마찬가지로 무작위 순열을 사용합니다. i번째 샘플에 대한 잔차를 구하기 위해서 i-1번쨰 까지 사용한 데이터로 학습한 모델을 사용합니다.

즉, 동일한 데이터로 계속 학습한 모델로 잔차를 갱신하는 것이 아니라 다른 데이터로 학습한 모델로 잔차를 갱신하는 것입니다. 

 

그외 oblivious decision Tree와 feature combination과 같은 방법론도 사용되었습니다.

Olivious descision Tree(망각 결정 트리)는 트리를 분할할 때 동일한 분할 기준이 전체 트리 레벨에서 적용되는 것입니다. 이는 균형적인 트리를 만들 수 있고 overfitting을 막을 수 있습니다.

 

feature combination은 말그대로 범주형 변수의 조합으로 새로운 변수조합을 만드는 것입니다. Greedy 방식으로 이러한 조합을 만들어 트리를 분할할때 이전에 사용된 데이터에서 조합을 찾아내고 TS로 변환하는 방식입니다.

 

그럼 CatBoost는 다른 알고리즘에 비해 어떤 단점이 있을까요?

데이터 대부분이 수치형일 경우 위와같은 알고리즘이 큰 효과를 내기가 어렵습니다. 또한 lightgbm에 비해 학습 속도가 느립니다. 하지만, 큰 크기의 데이터 프레임에서 categorical feature가 포함되어 있지 않은 경우는 거의 보지 못한 것같습니다. 항상 feature engineering 단계에서도 categorical feature의 처리가 큰 이슈중 하나였는데 catboost는 이에 큰 강점을 가지고 있습니다. 

 

 

---

아직까지 "무적의 머신러닝 알고리즘"은 없습니다. 그 효율성과 성능을 판단해서 활용 가능범위 안에서 다양한 알고리즘을 시도해보는것이 최선이라고 생각합니다. 특히, 머신러닝 알고리즘 적용후 blending 이나 stacking과 같은 방법으로 모델을 더욱 고도화 할 수 있습니다(물론 모델이 매우매우 복잡해지긴 합니다)

 

참고

blog.naver.com/PostView.nhn?blogId=winddori2002&logNo=221931868686&categoryNo=17&parentCategoryNo=0&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView

[바람돌이/머신러닝] 앙상블(Ensemble Learning)(4) - 부스팅(Boosting), XGBoost, CatBoost, LightGBM 이론

towardsdatascience.com/catboost-vs-light-gbm-vs-xgboost-5f93620723db

CatBoost vs. Light GBM vs. XGBoost

towardsdatascience.com/https-medium-com-vishalmorde-xgboost-algorithm-long-she-may-rein-edd9f99be63d

XGBoost Algorithm: Long May She Reign!