XGBoost 뿌수기!

본 포스트는 XGBoost: A Scalable Tree Boosting System 논문의 요약을 담고있습니다.

Scalable ML

What is Scalablity in ML?

Scalabity는 한국어로 흔히 확장성 또는 범위성으로 번역합니다. Scalability의 포괄적인 정의는 가용한 자원에 따라 성능이 크게 떨어지지 않으면서 시스템에 맞게 돌아갈 수 있는 능력입니다. 다시말해 성능이 아주 좋은 서버에서나 저와 같은 학부생이 사용하는 작고 귀여운 노트북에서나 성능의 큰 손실없이 잘 작동하는 능력이라고 할 수 있겠습니다. ML 분야에서 Scalability는 주로 알고리즘 상 더욱 효율적인 구조를 찾거나 원본 알고리즘에 근사한 성능을 내면서 훨씬 효율적으로 계산이 가능한 방법을 찾는다는 의미로 사용됩니다. 그러므로 Scalable하다는 것은 Data의 양과 상관없이 사용이 가능하면서 계산 자원(e.g. memory)을 과도하게 요구하지 않는것이라고 정리할 수 있겠습니다.¹

How to achieve scalability

XGBoost의 경우 single machine에서 여타 인기있는 솔루션보다 많게는 10배이상 빠르며 분산 또는 메모리 제한 환경에서도 수십억개의 예시들을 다룰 수 있다고 합니다. XGBoost는 다음 몇가지 시스템 그리고 알고리즘 상의 최적화를 통해 Scalability를 이루었습니다.

Highly scalable end-to-end tree boosting system
Weighted quantile sketch for efficient proposal calculation
Novel sparsity-aware algorithm for parallel tree leaning
Effective cache-aware block structure for out-of-core tree learning

How good is XGB?

성질이 급하신 분들이라면 이쯤에서 그래서 XGB가 얼마나 잘났다는건데? 라는 생각이 드실텐데요. 원 논문에 따르면 2015년 Kaggle blog에 발표된 우승 솔루션 29개 중 17개의 솔루션에서 사용된 XGB가 가장 많이 사용된 알고리즘이였고 2위는 11개 솔루션에서 사용된 Deep Neural Net이였습니다. 5년이 지난 현재까지도 Kaggle의 수많은 챌린지를 휩쓸었다고 할 수 있을만큼 많이 사용되었고 뛰어난 성능을 보여준 알고리즘입니다.

How does XGB work?

XGBoost는 eXtream Gradient Boosting의 약자로 XGB를 알기 위해서는 Gradient Boosting을 알아야합니다.

TREE BOOSTING IN A NUTSHELL

Regularized Learning Objective

기본적인 트리 앙상블 모델은 K개의 트리를 이용해 구한 weight들을 모두 더하는 방식으로 결과값을 예측합니다.

그림 1. Tree Ensemble Model

각 트리들을 학습하기 위해 다음 regularized objective를 minimize 합니다.

그림 2. Original Loss Function

여기서 $l$은 예측값 $\hat{y_i}$과 타겟값 $y_i$ 사이의 거리를 나타내는 differentiable convex loss function입니다. $\Omega$는 모델(regression tree functions)의 complexity를 penalize해주어 overfitting을 막고 예측력을 높여줍니다.

Gradient Tree Boosting

그림 3. Loss Function for GTB

Gradient Tree Boosting에서는 새로운 상첨자가 등장합니다. $\hat{y_i}^{(t)}$는 t번째 iteration에서의 예측값입니다. GTB에서는 Eq.(2)에 따라 모델을 가장 많이 개선시키는 $f_t$를 greedy하게 추가해 나갑니다. 이 과정에서 Second-order approximation을 이용해 빠르게 목적함수를 최적화할 수 있습니다.

그림 4. Approximate Loss Function for GTB

$g_i$와 $h_i$는 각각 loss function $l$에 대한 first, second gradient statistics입니다. 위 식에서 상수항을 제거하고 나면 다음과 같은 simplified objective를 얻을 수 있습니다.

그림 5. Simplified Loss Function for GTB

이 식에서 $\Omega$를 전개하고 나면 다음과 같이 $j$ leaf에서의 optimal weight $w_j^*$ 와 tree stucture $q(\textbf{x})$에 대한 optimal value를 구할 수 있습니다.

그림 5. Simplified Loss Function for GTB

식 (6)번은 tree structure $q$의 quality를 측정하는 scoring function으로 사용되는데 figure2를 보면 이 평가가 어떻게 이뤄지는지 알 수 있습니다.

그림 6. Structure Score Calculation

보통의 경우 모든 가능한 $q$에 대해서 이 quality score를 구하는 것은 불가능합니다. greedy 알고리즘의 경우 하나의 잎에서 시작해 반복적으로 가지를 추가해 나가는 방식을 대신 사용합니다. split이 되고 난 후 Instance set$(I)$이 $I_L \cup I_R = I$로 나누어진다면 loss는 다음 식과 같이 주어지게 되고 이 공식을 이용해 split candidates를 평가하게 됩니다.

그림 7. Loss for Split Candidates

Shrinkage and Column Subsampling

Objective function 외적으로 over-fitting을 막기 위해서 Shringkage와 Column Subsampling 이 두가지 테크닉을 사용합니다. Shrinkage는 새롭게 더해진 weight에 tree boosting의 매 스텝마다 $\eta$를 곱해 learning rate와 비슷한 역할을 해줍니다. Shrinkage는 개별 tree의 영향력을 줄여 미래의 tree들이 모델을 개선할 수 있도록 해줍니다. Column(feature) Subsampling은 RandomForest에서 사용된 방식으로 전통적인 row subsampling보다 over-fitting을 잘 막아주고 병렬 알고리즘의 계산을 빠르게 해주지만 상업용 프로그램(TreeNet)에만 구현해두고 저희가 이번 프로젝트에서 사용한 opensource package에는 적용되지 않았다고 하네요. 치사하게…

SPLIT FINDING ALGORITHMS

여기서부터가 이 논문의 재미있는(?) 파트입니다. 그들이 말하는 scalability는 이 approximation 알고리즘들의 영향이 클 겁니다.. 아마도.. 아님말고…

Basic Exact Greedy Algorithm

위에서 머리아픈 수식들을 살펴봤던 것은 모두 식 (7)번을 얻기 위함이였습니다. Tree learning에서 가장 중요한 과제는 이 식에 나타나는 것과 같은 Best split을 어떻게 찾느냐 하는 것이기 때문입니다. Exact greedy algorithm은 모든 feature의 가능한 모든 split을 다 해봅니다. 그러나 continuous한 feature를 다룰 때 이런 방식은 계산적으로 부담이 매우 크기 때문에 먼저 data를 feature value에 따라 정렬한뒤 정렬된 순서에 따라 data에 접근해 gradient statistics를 축적해 나갑니다.

Approximate Algorithm

하지만 이 방식조차 Data가 컴퓨터의 memory안에 다 들어가지 않을 만큼 크다면 사용할 수가 없고 분산컴퓨팅환경에서도 비슷한 문제가 발생합니다. 이를 해결하기 위해 원 논문에서는 다음 approximate framework를 제시합니다. 알고리즘은 먼저 feature의 분포에 따라 candidate splitting point를 제안합니다. 이 candidate point들에 따라 나뉘어진 bucket들에 continuous한 feature들을 할당하고 통계량들을 합산에 이 값에따라 가장 좋은 solution를 찾게됩니다. 이 알고리즘은 바로 이 후보군이 언제 제안되느냐에 따라 두가지 변형이 가능합니다. Global variant는 모든 후보군을 초기 tree 구성단계에서 제안하고 같은 후보값을 모든 단계에서 재사용합니다. Local variant의 경우에는 매 split마다 다음 split값을 다시 제안합니다. local proposal은 매 split마다 후보군을 정제하기 때문에 깊은 트리에 적합하고 global proposal은 local만큼 정확해지기 위해서는 충분히 많은 후보군이 제안되어야한다는 특징이 있습니다.

Weighted Quantile Sketch

이 approximate algorithm에서 중요한 파트는 바로 이 candidate split point를 어떻게 제안할 것이냐 하는 문제입니다. 보통 feature의 percentile을 사용해 data에 후보군이 균일하게 분포할 수 있도록 제안합니다.

식 (3)번을 정리하면 다음과 같이 표현할 수 있습니다.

그림 8. Weight Quantile Sketch

바뀐 표현은 $h_i$를 weight로, $g_i/h_i$를 label로 갖는 weighted squared loss로 해석할 수 있습니다.

모든 instance들이 같은 weight를 갖는 경우에는 quantile sketch라는 알고리즘을 이용하여 문제를 해결할 수 있지만 weighted data set의 경우에는 문제를 해결할 수 있는 quantile sketch가 존재하지 않습니다. 이러한 문제를 해결하기 위해서 원 논문에서는 novel distributed weighted quantile sketch algorithm을 제시합니다. 이 알고리즘을 통해 증명이 가능한 이론적 보증하에서 weighted data를 다룰 수 있습니다. 이 알고리즘은 일정수준의 정확도를 유지하는 merge와 prune 연산을 지원하는 data structure를 제안하고 있습니다.

Sparsity-aware Split Finding

현실 문제에서는 input $\textbf{x}$가 sparse한 경우가 빈번하게 나타납니다. Data가 희소(sparse)하다는 것은 데이터의 차원수에 비해 실제 값을 담고 있는 공간이 매우 협소한 데이터를 의미합니다. 저희 팀에서 이번 프로젝트때 진행한 NLP에서의 CountVectorizer가 좋은 예시입니다. 예를 들어 corpus에 다음과 같은 두 문장이 있다고 해봅시다.

corpus = ['The quick brown fox.', 'Jumps over the lazy dog!']  

CountVectorizer를 이용해 corpus를 matrix로 변환하게 되면 다음과 같은 결과를 얻습니다. ²

표 1. CountVectorizer의 출력값

corpus에 다양한 단어들이 등장할수록 실제로 값을 담고 있는 entry보다 0을 담고있는 entry가 많아지고 data가 희소해질 가능성이 높아지는 것입니다.

이런 데이터들을 다루기 위해서는 알고리즘이 데이터의 희소 패턴을 인지할 수 있도록 하는 과정이 필요한데 각 tree node에 default direction을 더해주는 것이 바로 그것입니다.

그림 9. Default Directions

이 default direction을 어느 방향으로 지정할 것인지는 두가지 선택지(Y or N)가 있습니다. 두 선택지 중 optimal direction은 데이터로부터 학습됩니다. 다시말해, xgb는 non-missing entry들만 방문하고 non-presence value들은 missing value로 취급하며 이 missing value를 다루기 가장 좋은 default direction을 data로부터 학습한다는 뜻입니다. 이를 통해 XGBoost에서는 sparse data set도 별도의 전처리 과정없이 여타 dense data들과 동일한 방식으로 다룰 수 있습니다. one-hot encoding으로 이루어진 Allstate dataset에서 sparsity를 염두에 두지 않는 naive한 알고리즘보다 50배이상 빠른 모습을 볼 수 있습니다.

그림 10. naive한 알고리즘과 sparsity aware 알고리즘의 수행속도 차이

System Design

Column Block for Parallel Learning

Tree learning에서 시간을 가장 많이 잡아먹는 파트는 데이터를 정렬(sort)하는 단계입니다. 이 sorting 단계에서 계산 비용을 줄이기 위해 원 논문에서는 block이라는 in-memory unit에 데이터를 저장하는 것을 제안합니다. 각 블록 안에는 feature값에 따라 정렬된 data들이 Compressed column format으로 저장됩니다. 이 과정은 training 전단계에서 한번만 이루어지고 이후 iteration에서는 저장되어있는 블록을 재사용하게 됩니다. approximate algorithm을 사용하는 경우에는 각 column의 통계량을 뽑는 과정을 병렬화 하여 가용한 계산자원을 더욱 효율적으로 사용할 수 있습니다. 각 데이터들을 block으로 바꾸는 과정은 다음 fig6에 나타나있습니다.

그림 11. 데이터를 블록화하는 과정

Cache-aware Access

non-continuous memory access는 gredient statistics가 CPU cache에 맞지 않고 cache miss가 일어나는 경우 split finding을 느리게 만듭니다. greedy 알고리즘을 사용하는 경우, 이 문제를 해결하기 위해 cache-aware prefetching algorithm이 등장합니다. 각 쓰레드에 internal buffer를 배정하고 gradient statistics를 저장했다가 mini-batch 방식으로 축적을 진행합니다. 이 방식은 direct read/write dependency를 longer dependency로 바꿔 데이터의 크기가 클 때 런타임을 줄여줍니다. 그림 7번을 보면 dataset의 크기가 10M일경우 basic algorithm에 비해 속도가 많이 빨라진 모습을 볼 수 있습니다.

그림 12. Basic 알고리즘과 Cache-aware 알고리즘의 수행속도 차이

approximation 알고리즘을 사용하는 경우에는 적절한 block size를 고르는 방식으로 해결합니다. 여기서 block size는 한 block안에 담겨있는 데이터의 갯수를 의미합니다. 너무 작은 block size를 고를 경우에는 각 쓰레드에 너무 작은 workload가 주어져 비효율적인 병렬화로 이어지고 너무 큰 block size는 gradient statistics가 CPU cache에 들어가지 않아 cache miss로 이어집니다. 저자들은 여러 가지 선택지를 실험하여 $2^{16}$ examples per block을 가장 이상적인 값으로 선택하였습니다.

Blocks for Out-of-core Computation

Out-of-core Computation은 컴퓨터의 메인메모리에 들어가지 않을 정도로 큰 데이터를 다루는 것을 말합니다. 앞서 큰 데이터를 여러 블록으로 나누어 저장하는 방식을 소개했습니다. disk에 저장되어있는 데이터를 불러옴과 동시에 계산을 진행할 수 있도록 구조를 설계하는 것이 중요한데 이를 위해 Block Compression과 Block Sharding이라는 두가지 테크닉을 사용합니다. 각 블록은 열(col)에 따라 압축되어있다가 메인 메모리에서 불러올때 독립된 쓰레드에서 압축해제됩니다. Block Sharding은 데이터를 여러 디스크로 조각내는 것으로 pre-fetcher 쓰레드가 각 disk에 배정되어 in-memory buffer로 data를 fetch하는 역할을 수행합니다.

References

¹_{https://dzone.com/articles/what-scalable-machine-learning}

²_{https://towardsdatascience.com/hacking-scikit-learns-vectorizers-9ef26a7170af}

Written by 정은기