논문: Chen, Tianqi, and Carlos Guestrin. “Xgboost: A scalable tree boosting system.” In Proceedings of the 22nd acm sigkdd international conference on knowledge discovery and data mining, pp. 785-794. 2016.
부스팅트리는 매우 효과적이라 알려져있는 머신러닝 방법으로, 대회에서 성능을 올리기 위해 거의 필수적으로 사용되고 있다. 본 논문에서는 XGBoost 라는 Scalable End to End 부스팅 방법론을 설명한다. Sparse한 데이터에 대해 Sparsity-Aware Algorithm과 Weighted Quantile Sketch를 사용하였다. XGBoost는 K개의 함수를 앙상블하여 결과를 예측하는데, decision tree와 달리 regression의 경우 노드들에 대해 연속적인 점수를 가지고 있다. Mapping policy q를 이용하여 샘플을 노드에 할당하고, 각 노드들의 점수의 합을 구해서 최종 prediction을 진행한다. 해당 모델은 additive 방식을 통해 학습이 진행된다. Tree boosting의 각 단계 이후에 Shrinkage를 통해 스케일링을 진행한다. 또한 Split Finding Algorithm을 제안한다. 기존의 모든 가능한 split을 탐색하는 그리디 알고리즘은 데이터가 메모리에 모두 들어가지 않을 경우 매우 비효율적이다. 이를 해결하기 위해 weighted Quantile Sketch를 이용한다. 또한 알고리즘이 sparse structure을 인식하기 위해서 각 노드에 direction값을 더해준다. 이를 Sparsity-aware Split Finding이라 한다. 위의 알고리즘들을 이용하여 Sparse 데이터를 다룰 수 있는 새로운 Sparsity 알고리즘, XGBoost를 제안하였다.
XGBoost는 기존의 pGBRT 알고리즘 보다 시간과 메모리 측면에서 효율적임을 증명하였다.
