XGBoost

 

Introduction

• 먼저 XGBoost의 역사를 살펴보겠습니다.

• 처음에는 단일 의사결정 나무에서 시작하였고, 이것에 대한 ensemble 기법인 bagging이 등장하였습니다.
  그 bagging에서 split하는 데 있어서 변수를 random하게 선택하는 random forest 기법이 제안되었습니다.
• 다음으로 stump tree를 base learner로 하는 boosting이 등장하였고, 그거를 다시 gradient를 이용해서 boosting하는게 gradient boosting입니다.
• 마지막은 xgboost입니다. xgboost는 gradient boosting을 기반으로 하였고,
  여기서 좀 더 빠르게 연산을 수행하고 대용량 데이터에 대해서도 처리하기 위해 고안된 기법입니다.

• 위 그림은 xgboost의 성능을 높이기 위해 필요한 장치들입니다.
• xgboost는 gbm의 성능, 스케일, 속도를 최적화하기 위해 극한으로 빠르게 연산을 수행합니다.
  • 약간의 성능 저하도 발생하지만, xgboost가 가진 장점으로 커버 가능합니다.
• xgboost는 하나의 머신에서 데이터를 더 많이 사용할 수 있게 하고, 병렬 처리도 가능합니다.

 

• xgboost는 gradient boosting machine의 일종으로, 보다 빠른 연산을 위해 approximation solution을 찾습니다.
• xgboost를 알고리즘 측면에서 살펴보겠습니다.

Split Finding Algorithm

• 보통 decision tree는 최적의 split point를 찾기 위해 exact greedy algorithm을 사용합니다. (모든 변수를 탐색하는 것을 의미합니다.)
• 따라서 항상 optimal solution을 찾아줍니다.
• 하지만, 데이터가 메모리에 다 담기지 않는다면 greedy algorithm을 수행하기 어렵습니다.
• 또한, 모든 경우의 수를 다 탐색해야 하기 때문에 병렬 처리가 불가능합니다.
• $for\ j\ in\ sorted(I,\ by\ \mathbf{x}_{jk})\ do$ : 위의 pseudo code에서 이 부분이 모든 경우의 수를 탐색하는 것을 의미합니다.
• 앞선 두 가지의 단점 때문에 이 과정을 approximation하는 알고리즘이 존재합니다.

• 이제 approximiation하는 알고리즘에 대해 설명하겠습니다.
• 첫 번째 단계는 전체 데이터가 갖고 있는 영역을 percentile에 따라 분할합니다.
  • 여기서 small k는 변수의 index입니다.
• 각각의 변수들에 대해서 학습 training data를 정렬시켜놓고,정렬된 데이터에서 percentile을 보고 일정한 갯수만큼 분할을 합니다.
  • 이때 사용되는 hyperparameter는 $\epsilon$ 입니다.
• 분할된 덩어리들은 bucket이라고 합니다. 현재 위에서 보이는 바와 같이 l개의 bucket이 존재합니다.
  • 이 bucket들에 대해서 따로따로 split point를 찾습니다. -> 이는 뒤에서 예시를 통해 설명하겠습니다.

• 예시를 들어 설명하겠습니다.
• 먼저 data를 오름차순 크기 순으로 정렬합니다.
• exact greedy algorithm이라면 핑크색 네모 단위로 split해서, 각각의 bucket에서의 처음부터 마지막까지 gradient를 계산합니다. 
• 이렇게 되면 총 39개의 candidate split이 생깁니다.
• 여기서 gradient가 가장 큰 방향으로 best split point를 정합니다.

 

• 한편, approximation algorithm에서는, 빨간색 선처럼 bucket을 나눕니다.
  • 여기서 핵심은, 각각의 bucket에 대해서 gradient를 따로따로 계산한다는 점입니다.
  • 구체적으로, 1번(초록색)에서는 3개의 gradient를 계산할 수 있습니다.
  • 따라서 1번 bucket에서의 candidate split은 총 3개입니다. 여기서 best split을 찾습니다.
  • 이와 같이, 2번, 3번, ... , 10번 bucket에 대해서 마찬가지로 진행합니다.
• 현재 best split point가 있는 bucket말고 나머지 9개 bucket에서는 gradient를 통해 얻을 수 있는 정보가 없습니다.
  • 모든 bucket에 있는 label이 전부 같기 때문입니다.
• 반면, 가운데(보라색) bucket에서, 저 지점(보라색 선)에서 split했을 때 얻을 수 있는 정보량이 최대가 됩니다.
  • 따라서 best split point는 저 지점으로 정해집니다.

 

• 앞선 내용을 산술적으로 살펴보겠습니다.
• exact greedy algorithm은 총 39번의 candidate split에 대한 gradient를 계산해야 합니다.
• 반면 approximation algorithm은 각 bucket마다 3번씩 gradient를 계산하면 됩니다.
  • 10*3 = 30, 총 30번의 계산을 수행합니다.
• 그리고 이는 병렬 처리가 가능합니다.
  • 1번 bucket(초록색)은 thread1에 태워서 gradient를 계산하고, 2번 bucket(노란색)은 thread2에 태워서 계산하고, ... 이런식으로 총 10개의 bucket에 대해서 동시에 계산하는 병렬처리가 가능합니다.
  • 이는 계산 시간을 더 단축시켜주는 요소입니다.
• 앞선 예시는 약간 극단적인 케이스로, approximation algorithm으로 best split을 찾지 못하는 경우도 있습니다.

 

• 이전 예시를 갖고 계속 설명하겠습니다. 버킷을 위에 보이는 것처럼 빨간색 선으로 구분하였습니다.
• approximation 하는 데 있어서 트리 별(per tree)로 할 수 있고, split 별(per split)로 할 수도 있습니다.
  • global variant = per tree / local variant = per split 
• per tree 관점에서, best split point를 찾았기 때문에 left child와 right child로 구분됩니다.
• 이렇게 구분된 상황에서 다시 partitioning을 해야 합니다.
  • 여기서 global variant는 처음에 만들어놓은 bucket 기준을 그대로 사용합니다.
• 원래 첫번째 parent node에는 bucket 10개가 있었는데, global variant를 쓰는 순간, left child node에서 탐색할 수 있는 bucket이 5개가 나옵니다. (right child node는 6개입니다.)
• global variant는 tree가 깊어질수록 탐색해야 할 bucket의 수가 줄어듭니다.
• bucket 내부에 있는 example들의 size는, (bucket이 잘린 경우를 제외하고는) parent node에서 leaf node에 이르기까지 동일하게 유지됩니다.

• 한편, local variant에도 parent node에 bucket 10개가 있습니다.
  여기서 left child node와 right child node로 split 했을 때,
  각각의 child node에 대해서도 동일한 bucket size를 유지합니다.
• 즉, 왼쪽과 오른쪽 각각의 bucket size는 10개입니다.

 

• 이런식으로 계속 진행되면 local variant는 split이 계속되어도 bucket size는 항상 동일하게 유지됩니다.
• 즉, 하나의 bucket에 들어가는 example의 수는 depth가 깊어질수록 수가 점점 감소할 가능성이 높아집니다.
• 이런식으로 두 개의 split finding을 통해서 실제 split candidate도 줄이고 병렬 계산도 수행할 수 있습니다.
• 쉽게 말하면, global variant는 node가 깊어져도 parent node에서 한 bucket에 들어가는 example들의 size를 유지하는 것이고, 반면 local variant는 node가 깊어져도 parent node의 bucket size를 유지하는 것입니다.

 

• 위 그림은 exact greedy algorithm과 local variant & global variant algorithm의 성능을 비교한 그래프입니다.
• 여기서 $\epsilon$으로 표시한 게 hyper-parameter이고,
  보통은 $\frac{1}{\epsilon}$개의 bucket이 만들어집니다.
  • $\epsilon$이 0.3일 경우 대략 3~4개가 만들어지고, 0.05이면 20개 정도가 만들어집니다.
• 여기서 핵심은, approximation algorithm을 사용해도 성능이 그리 나쁘지 않다는 것입니다.

Sparsity-Aware Split Finding

• 다음으로 approximation을 위한 xgboost의 두번째 장치를 설명하겠습니다.
  • 왼쪽은 알고리즘이고 오른쪽은 쉽게 설명한 예시 그림입니다.
• 여기서 목적은 missing value (결측치)를 효율적으로 처리하는 것입니다.
• 그래서 이 경우에는 각각의 split마다 default direction을 학습 과정에서 찾아냅니다.
  • 그런 다음, new data가 들어왔을 때 어떤 value가 missing이면 처음에 정의했던 default direction으로 보냅니다.
• 오른쪽 그림을 살펴보겠습니다.
• 여기서 "value"는 실제로 특정 변수의 값이고, "class"는 정답 범주를 의미합니다.

$//\ enumerate\ missing\ value\ goto\ right$

$//\ enumerate\ missing\ value\ goto\ left$

• 즉, 두 가지 경우를 각각 비교한 다음에 더 좋은 direction을 찾습니다.
• 구체적으로 설명하겠습니다. 예를 들어, $//\ enumerate\ missing\ value\ goto\ right$ 에 따라 missing value를 전부 오른쪽으로 보내겠습니다.
• 이렇게 보낸 다음에, candidate split을 찾습니다. -> 빨간색 선
• left에 대해서도 동일하게 진행합니다. -> 파란색 선
  • 위의 결과로, missing value를 right direction으로 보냈을 때와 left direction으로 보냈을 때의 candidate split이 정해졌고, 그에 따른 성능을 알 수 있습니다.
• left일 때와 right일 때를 비교했을 때 left가 성능이 더 좋습니다.
  • 그러면 이 변수에 대해서는 new data가 들어왔을 때 missing value라면 left로 보내지는 것입니다.

• 왼쪽은 앞선 default direction 설명에 따른 예시입니다. (따로 설명은 하지 않겠습니다.)
• 오른쪽은 sparsity aware algorithm을 사용했을 때 computation 시간이 상당히 줄어드는 것을 보여줍니다.

System Design for Efficient Computing

• 다음은 tree에 대한 병렬화 파트입니다.
• tree를 학습시키는데 있어서 가장 시간이 많이 걸리는 부분들은, 각각의 변수에 대해서 sorting을 합니다.
  • 가장 효율적으로 sorting을 하더라도 $O(nlogn)$ 만큼의 시간이 필요합니다.
  • data가 커지면 data*$logn$ 만큼 커집니다.
• 따라서 xgboost는 data를 row-wise로 보지 않고, column-wise 포맷으로 data를 저장합니다.
• 구체적으로, 사전에 각각의 column들을 sorting해 놓습니다.
• 각 column들이 미리 sorting이 되어 있으니까, 해당하는 feature column들에 대한 index들이 달라집니다.
  • 이 과정은 tree를 학습시키기 전에 한 번만 미리 만들어 놓으면 됩니다.
  • 따라서 중간에 sorting 하는 과정이 생략되기 때문에 효과적인 연산이 가능합니다.

 

[출처]: https://www.youtube.com/watch?v=VHky3d_qZ_E&list=PLetSlH8YjIfWMdw9AuLR5ybkVvGcoG2EW&index=27