XGBoost: A Scalable Tree Boosting System

Tianqi Chen; Carlos Guestrin

Source-linked AI summary

XGBoost: A Scalable Tree Boosting System

Tianqi Chen, Carlos Guestrin

arXiv:1603.02754v32016년 3월 9일cs.LG

TL;DR

기존 tree-boosting 시스템은 실제 대규모 학습을 위한 확장성 기법을 end-to-end 방식으로 결합하지 못했다. 이 논문은 sparsity-aware learning, weighted quantile sketching, 시스템 최적화를 적용한 XGBoost를 제시하며, 더 적은 자원으로 수십억 개 example까지 확장하면서 다양한 문제에서 state-of-the-art 결과를 달성한다.

문제
기존 연구는 out-of-core computation, cache-aware learning, sparsity-aware learning을 end-to-end tree-boosting system에 결합하지 못했다.
방법
XGBoost는 확장 가능한 end-to-end tree boosting에 sparsity-aware learning, weighted quantile sketching, cache-conscious 시스템 최적화를 결합한다.
결과
2015년 Kaggle challenge 우승 해법 29개 중 17개가 XGBoost를 사용했으며, XGBoost는 광범위한 문제에서 state-of-the-art 결과를 달성했다.
시사점 및 한계
XGBoost는 cache access patterns, data compression, sharding이 확장 가능한 end-to-end tree boosting의 essential elements임을 보여준다.

Abstract

from arXiv · show

Tree boosting is a highly effective and widely used machine learning method. In this paper, we describe a scalable end-to-end tree boosting system called XGBoost, which is used widely by data scientists to achieve state-of-the-art results on many machine learning challenges. We propose a novel sparsity-aware algorithm for sparse data and weighted quantile sketch for approximate tree learning. More importantly, we provide insights on cache access patterns, data compression and sharding to build a scalable tree boosting system. By combining these insights, XGBoost scales beyond billions of examples using far fewer resources than existing systems.

1. 서론

XGBoost는 gradient tree boosting 과 그 변형 의 뛰어난 실용적 성능을 바탕으로 제안된 확장 가능한 end-to-end tree boosting system이다. 이 시스템의 성공은 대규모 dataset 전반에서 폭넓은 state-of-the-art 성능과 scalability를 제공하는 algorithmic 및 systems innovation에 기인한다.

1. 서론: Gradient tree boosting은 실제 현장에서 널리 사용되며, classification benchmark 에서 state-of-the-art 결과를 달성하고, LambdaMART 를 통한 ranking task, ad click-through-rate prediction, Netflix prize 와 같은 ensemble application에 적용된다.이 논문은 XGBoost를 tree boosting method의 이러한 광범위한 성공 맥락에 위치시킨다.
1. 서론: XGBoost는 2015년에 발표된 29개의 Kaggle challenge 우승 solution 중 17개에 사용되었으며, 그중 eight solution은 XGBoost만 사용했다.이 solution들은 sales prediction, event classification, text classification, customer behavior prediction, ad click-through-rate prediction을 비롯한 다양한 task를 다뤘다.
1. 서론: 이 system은 기존의 널리 사용되는 single-machine solution보다 more than ten times faster하게 실행되며, distributed 또는 memory-limited 환경에서 billions of examples까지 확장된다.이 scalability는 desktop에서 hundreds of millions of examples를 처리하고, 더 적은 cluster resource로 더 큰 dataset을 처리할 수 있게 한다.
1. 서론: 이 논문의 main contribution은 real-world use를 위해 algorithmic 및 systems optimization을 결합한 highly scalable end-to-end tree boosting system이다.저자들은 out-of-core, cache-aware, sparsity-aware learning을 결합함으로써 새로운 end-to-end solution을 제공한다고 강조한다.
1. 서론: 제안된 learning innovation은 효율적인 proposal calculation을 위한 이론적으로 정당화된 weighted quantile sketch와 parallel tree learning을 위한 novel sparsity-aware algorithm이다.이 방법들은 효율적인 split proposal과 sparse-data tree learning을 다룬다.
1. 서론: XGBoost는 또한 out-of-core tree learning을 위한 cache-aware block structure를 도입하여 scalability를 in-memory computation 이상으로 확장한다.system-level design은 cache-aware computation을 out-of-core processing 및 data sharding 또는 compression optimization과 결합한다.

2. TREE BOOSTING 한눈에 보기

이 절에서는 regularized objective를 최소화해 학습하는 regression tree의 additive ensemble으로서 gradient tree boosting을 제시한다. 또한 일반화 성능과 효율을 높이기 위한 second-order greedy optimization, shrinkage, feature subsampling을 설명한다.

Tree ensemble model: XGBoost는 K개의 regression tree에서 연속적인 leaf score를 합산해 예측하며, 각 tree는 example을 leaf index에 매핑한다.이 ensemble은 서로 독립적인 tree structure와 leaf weight를 사용하고, 최종 예측에서는 대응하는 score를 합산한다.
Regularized objective: 이 model은 미분 가능한 loss와 tree-complexity regularization의 합을 최소화하며, 이를 통해 학습된 weight를 매끄럽게 하고 단순한 predictive function을 선호하게 한다.tree function은 일반적인 Euclidean parameter가 아니므로 regularized objective는 additive manner로 최적화된다.
Tree construction: Second-order gradient statistics는 greedy tree construction을 가능하게 한다. leaf sum은 structure score를 결정하고, candidate split은 loss reduction으로 평가된다.이 structure score는 decision-tree impurity scoring을 더 다양한 objective function으로 일반화한다.
Overfitting prevention: Shrinkage는 새로 추가되는 각 tree의 weight를 η로 조정해 개별 tree의 영향력을 줄이고, 이후 tree가 model을 개선할 여지를 남긴다.이 기법은 overfitting을 방지하는 추가 수단으로 regularized objective와 함께 도입된다.
Overfitting prevention: 사용자 피드백에 따르면 Column subsampling은 기존의 row subsampling보다 overfitting을 더 효과적으로 방지하며, 이후의 parallel algorithm을 가속한다.해당 부분에서는 Column subsampling이 TreeNet [13]에 구현되었고 기존 open-source package에는 없었다고 설명한다.

3. 분할 탐색 알고리즘

XGBoost는 단일 머신에서 exact greedy split finding을 지원하며, 메모리를 초과하거나 분산된 데이터에는 approximate split finding을 지원한다. approximate framework는 percentile 기반 proposal을 사용하고, weighted quantile sketching과 sparsity-aware default가 weighted data와 missing entry를 처리한다.

분할 탐색 framework: XGBoost는 단일 머신 데이터에 exact greedy split finding을, 모든 설정에서 local 및 global proposal을 사용하는 approximate split finding을 지원한다.사용자는 필요에 따라 두 방법 중 하나를 선택할 수 있다.
Approximate split finding: approximate algorithm은 percentile 기반 candidate split을 제안하고, continuous feature를 bucket으로 매핑하며, 통계량을 집계한 뒤 가장 우수한 proposed split을 선택한다.global proposal은 한 번만 생성되는 반면 local proposal은 각 split 이후에 정교화된다. global method는 proposal 단계가 더 적게 필요하지만 일반적으로 candidate가 더 많다.
Weighted quantile sketch: distributed weighted quantile sketch는 merge 및 prune operation을 통해 정확도를 보존하면서 provable theoretical guarantees와 함께 weighted data를 처리한다.second-order gradient statistic이 instance weight로 작용하므로 weighted candidate가 필요하며, 기존의 unweighted sketch로는 이 문제를 해결할 수 없다.
Sparsity-aware split finding: sparsity-aware algorithm은 missing 또는 absent value에 대한 default direction을 학습하면서 non-missing entry만 열거한다.일관된 해로 열거를 제한하면 사용자가 지정한 non-presence value도 처리할 수 있다.
Sparsity-aware split finding: sparsity-aware algorithm은 50배 이상 빠르며, sparse Allstate-10K dataset에서 naive implementation보다 우수한 성능을 보인다.이 방법의 계산량은 non-missing entry 수에 선형이며 sparsity pattern을 균일하게 처리한다.

4. 시스템 설계

XGBoost의 시스템 설계는 정렬·압축된 데이터를 재사용 가능한 블록으로 구성해 split 탐색 비용을 줄이고, 확장 가능한 exact, approximate, parallel, out-of-core 연산을 지원한다. Cache-aware 접근과 블록 크기 선택은 memory-access 및 병렬화 병목도 완화한다.

Approximate algorithms: Approximate algorithms에서는 여러 row-partitioned block이 분산 또는 디스크 기반 저장을 지원하고, 정렬된 column을 사용하면 quantile을 linear scan으로 찾을 수 있다.이는 각 branch에서 후보를 빈번하게 생성하는 local proposal algorithms에 특히 유용하다.
리소스 활용: 블록 레이아웃은 split-statistics 수집의 병렬화와 간단한 column subsampling을 가능하게 하며, 독립적으로 prefetching하는 여러 disk-resident block은 out-of-core computation을 지원한다.독립적인 thread가 block을 main-memory buffer로 prefetch하므로 디스크 읽기와 computation을 동시에 진행할 수 있다.
블록 구조와 복잡도: 블록 구조는 exact greedy boosting의 복잡도를 O(Kd∥x∥0 log n)에서 O(Kd∥x∥0 + ∥x∥0 log n)로 줄이며, preprocessing 비용은 iteration 간 amortized된다.데이터는 정렬된 feature value를 포함하는 compressed-column block에 한 번 저장되므로 이후 training iteration에서 재사용할 수 있다.
Cache-aware computation: 비연속적인 gradient-statistics 접근은 cache 관련 stall을 발생시키지만, cache-aware prefetching을 사용하면 대규모 dataset에서 exact greedy algorithm이 naive version보다 twice as fast가 된다.이 방법은 statistics를 thread별 buffer로 가져온 뒤 mini-batch 단위로 누적하며, 보고된 비교는 Higgs 및 Allstate dataset을 대상으로 한다.
블록 크기 선택: 블록당 216 examples를 선택하면 cache capacity와 병렬화 사이의 균형을 맞출 수 있다. 블록이 지나치게 작으면 thread workload가 줄고, 지나치게 크면 cache miss가 발생하기 때문이다.블록 크기는 block당 최대 example 수로 정의되며, gradient statistics의 cache storage cost를 반영한다.

5. 관련 연구

XGBoost는 gradient tree boosting과 regularization을 기반으로 하면서 시스템 기법을 활용해 병렬 tree learning을 확장한다. weighted quantile sketch는 저자들이 아는 한 이전에 해결되지 않았던 weighted-data quantile 문제를 다룬다.

Gradient boosting과 regularization: XGBoost는 gradient boosting 을 구현하며, regularization을 통한 과적합 방지로 classification, learning to rank, structured prediction 에서 gradient tree boosting의 활용을 확장한다.regularized model은 regularized greedy forests 와 유사하지만, 병렬화를 위해 objective와 algorithm을 단순화한다.
Parallel tree learning: 기존 parallel tree-learning methods 는 대부분 이 논문의 approximate framework를 사용하지만, XGBoost는 exact greedy algorithm [23]을 이용한 column-wise partitioning도 지원한다.Cache-aware prefetching은 이 column-partitioned approach의 성능을 높일 수 있으며, 선행 연구의 algorithmic focus를 보완한다.
Weighted quantile sketch: weighted quantile sketch는 저자들이 아는 한 weighted data에서 quantile을 찾는 최초의 방법으로 제시된다.기존의 unweighted quantile summaries 와 달리, 이 일반화는 다른 data-science 및 machine-learning applications에도 도움이 될 수 있다.

6. 엔드투엔드 평가

End-to-end 평가 결과, XGBoost는 데이터 과학 생태계 전반에서 이식성이 높고 단일 머신 learning-to-rank workload부터 out-of-core 및 분산 처리에 이르기까지 1.7십억 개 예제로 확장된다. Compression, disk sharding, out-of-core computation이 성능과 확장성의 핵심이다.

구현: 오픈소스 XGBoost 패키지는 weighted classification, ranking, user-defined objectives, 여러 programming language, 데이터 과학 pipeline과의 native integration을 지원한다.분산 버전은 allreduce를 위해 Rabit library 위에 구축된다.
실험 설정: 평가에는 Allstate, Higgs, Yahoo! learning-to-rank, Criteo dataset을 사용하며, 앞의 세 dataset은 단일 머신 실험에, Criteo는 distributed 및 out-of-core 설정에 할당한다.Allstate와 Higgs는 무작위로 선택한 10M-instance training set을 사용하고, Yahoo!는 공식 train-test split을 사용한다.
Learning-to-rank 평가: Yahoo! learning-to-rank data에서 XGBoost는 pGBRT 보다 더 빠르게 실행되며, column subsampling은 실행 시간을 추가로 줄이고 성능을 소폭 향상한다.XGBoost는 exact greedy algorithm을 사용하는 반면, pGBRT는 approximate algorithm만 지원한다.
Out-of-core 평가: Compression은 3x speedup을 제공하며, 두 disk에 걸친 sharding은 out-of-core Criteo 실험에서 2x speedup을 추가한다.실험에는 32 vcore, 320 GB SSD 2개, 60 GB RAM을 갖춘 AWS c3.8xlarge machine 1대를 사용한다.
분산 평가: XGBoost는 Spark MLLib [18]와 H2O보다 빠르게 실행되고, 전체 1.7십억 개 예제로 원활하게 확장되며, 메모리가 부족할 때 out-of-core computation을 사용한다.32 EC2 노드에서 비교는 다양한 Criteo 입력 크기를 사용하며, Spark는 메모리 부족 상태로 실행될 때 급격한 slowdown을 겪는다.

7. 결론

이 논문은 XGBoost를 널리 사용되며 다양한 문제에서 state-of-the-art 결과를 달성하는 scalable tree boosting 시스템으로 제시한다. 또한 sparse 및 approximate learning을 위한 방법을 제안하고 scalability를 위한 핵심 시스템 고려사항을 규명한다.

XGBoost는 data scientist들이 널리 사용하며 다양한 문제에서 state-of-the-art 결과를 제공하는 scalable tree boosting 시스템이다.
이 논문은 sparse data를 처리하기 위한 novel sparsity-aware algorithm을 제안한다.
또한 approximate learning을 위한 이론적으로 정당화된 weighted quantile sketch를 도입한다.
저자들은 scalable end-to-end 시스템 구축을 위한 필수 요소로 cache access patterns, data compression, sharding을 규명한다.

부록 · A. 가중 분위수 스케치

이 절에서는 가중 데이터에 대한 근사 트리 부스팅을 위해 가중 분위수 스케치를 도입하며, merge와 prune 연산을 기반으로 구축된 분위수 요약 방법을 확장한다. 제안한 요약은 가중 분위수를 지원하면서 GK framework의 보장을 유지한다.

A. 가중 분위수 스케치: 분위수 요약은 ϵ의 상대 정확도로 분위수 질의에 답하며, 분산 및 스트리밍 분위수 계산의 기반을 이룬다.이 절에서는 GK algorithm [14]과 GK 기반 확장 을 고전적 접근법으로 제시한다.
A. 가중 분위수 스케치: merge 연산은 오차가 ϵ1과 ϵ2인 요약을 결합하여 근사 오차가 max(ϵ1, ϵ2)인 요약을 만든다.이 연산은 두 가지 기본 분위수 요약 연산 중 하나다.
A. 가중 분위수 스케치: prune 연산은 요약을 b+1개 원소로 줄이고 근사 오차를 ϵ에서 ϵ + 1로 변경한다.이 연산은 절에서 설명한 요약 크기 축소를 제공한다.
A. 가중 분위수 스케치: 가중 분위수 스케치는 근사 트리 부스팅을 위해 가중 데이터에서 분위수를 계산해야 하는 문제를 해결하며, 기존 algorithm은 이를 지원하지 않는다.이보다 일반적인 문제를 위해 가중 분위수 요약 구조를 제공한다.
A. 가중 분위수 스케치: 새로운 가중 요약은 GK 요약과 동일한 보장으로 merge와 prune 연산을 포함한다.이는 기존 요약 framework와 관련된 보장을 유지한다.
A. 가중 분위수 스케치: 이러한 연산과 보장을 유지하므로 가중 요약은 GK 요약을 구성 요소로 사용하는 framework에 그대로 적용할 수 있다.merge와 prune 연산을 갖는 분위수 요약은 분산 및 스트리밍 분위수 algorithm을 지원한다 [24].

A.1 형식화와 정의

이 절에서는 total order 아래 point rank를 추정하기 위한 weighted multiset, rank function, quantile summary를 형식화한다. 저장된 point를 넘어 summary function을 확장하고, 이후 증명에 사용되는 approximation framework를 정의한다.

Weighted data: 입력은 정렬된 point의 weighted multiset이며, 동일한 position과 weight를 갖는 중복 record를 허용한다.각 point는 음이 아닌 weight를 가지며, multiset weight는 모든 point weight의 합이다.
Quantile summary: weighted quantile summary는 approximate rank function과 weight function을 저장된 input point의 ordered subset과 함께 저장하면서 minimum point와 maximum point를 보존한다.function은 저장된 subset에서만 정의되므로, 이 summary에는 저장된 point가 k개일 때 4k개의 record가 필요하다.
Function extension: summary function은 추가 storage를 요구하지 않고 저장된 point보다 아래, 위 또는 그 사이에 있는 point를 처리하여 모든 position으로 확장된다.이 확장은 저장된 subset에 대한 ground-case definition을 기반으로 한다.
Approximation guarantee: ϵ-approximate summary는 rank-estimation error를 최대 ϵω(D)로 제한하며, 저장된 function과 확장된 function에 대해 동등한 constraint를 둔다.이 등가성은 이후 증명에서 확장된 function에 대한 constraint를 사용할 수 있게 한다.

A.2 초기 Summary 구성

작은 multiset D에 대해, 이 방법은 D의 값으로부터 초기 summary Q(D)를 구성한다. 이 summary는 0-approximate하며 모든 query에 정확히 답하고, 이후 연산을 지원할 수 있다.

초기 summary Q(D)는 작은 multiset D로부터 구성된다.
Q(D)는 D에 나타나는 모든 값의 집합 S를 포함한다.
구성된 summary는 모든 query에 정확히 답하므로 0-approximate하다.
이 summary는 이후 연산에 사용될 수 있다.

A.3 Merge Operation · A.4 Prune Operation

Merge operation은 두 quantile summary를 결합해 유효한 summary를 만들며, 이때 approximation error는 두 입력 error 중 더 큰 값이다. Prune operation은 유효성을 유지하면서 memory budget에 맞도록 기존 summary를 질의하며, approximation guarantee는 Theorem A.2로 특성화된다.

A.3 Merge Operation: 결합된 summary는 S1 또는 S2의 점으로 point set을 구성하고 두 입력 summary에서 대응하는 weight를 더한다.결합된 support의 x_i에 대해 ˜ω_D(x_i) = ˜ω_D1(x_i) + ˜ω_D2(x_i)이다.
A.3 Merge Operation: Merge construction은 Definition A.1의 모든 제약을 만족하므로 Q(D)는 valid quantile summary다.이 construction은 D = D1 ∪ D2에 대한 summary를 결합한다.
A.3 Merge Operation: Q(D1)과 Q(D2)가 각각 ϵ1- 및 ϵ2-approximate summary라면, 이들의 결합된 summary는 max(ϵ1, ϵ2)-approximate다.결합된 summary의 유효성은 rank와 weight quantity의 가법적 성질 및 확장된 제약 특성을 사용해 증명된다.
A.4 Prune Operation: query function g(Q, d)는 요청된 rank에 가까운 data value를 반환한다.이는 pruning에 앞서 도입되며 Algorithm 4에서 정의된다.
A.4 Prune Operation: summary와 memory budget b가 주어지면, pruning은 원래 summary를 질의해 새 summary Q′(D)에 유지할 항목을 최대 b+1개 선택한다.유지되는 항목 x′_i는 원래 summary를 질의해 선택되며, 새 summary는 원래 domain을 S′로 제한한다.
A.4 Prune Operation: Pruning은 Q′가 제한된 domain에서 Q의 rank와 weight 정보를 복사하고 중복된 유지 항목을 안전하게 제거할 수 있으므로 valid quantile summary를 보존한다.Q′의 모든 원소는 Q에서 오므로 Definition A.1의 제약을 검증할 수 있다.
A.4 Prune Operation: Theorem A.2는 memory budget b에서 ϵ-approximate summary를 pruning할 때의 approximation guarantee를 특성화한다.제공된 본문은 pruned summary가 bounded-error approximation이라고 서술하지만, 표시된 bound는 잘려 있다.