XGBoost, 극한의 가성비
Ensemble
XGBoost까지의 흐름
Decision Trees를 Bagging이라는 앙상블기법을 이용하여 성능을 높였고, 여기에 Random성을 부여하여 Random Forest를 만들었습니다. 이 후에는 Stumps Tree를 베이스로하는 Adaptive Boosting이 있었고, Gradient를 이용해서 Boosting을 하는 법을 알아보았습니다. 이번 포스트에서는 XGBoost(eXtreme Gradient Boosting)에대해 알아보겠습니다. XGBoost는 Gradient의 방법을 따라가지만, 더 많은 데이터를 한번에 다룰 수 있고 더 빠르게 처리할 수 있습니다.
Ada Boost와 Gradient Boosting에대해 잘 모르시는 분은 아래 포스트를 참고하시면 좋습니다.
[Ensemble] Ada Boost, 모델의 오답노트
Ada Boost, 모델의 오답노트 Ensemble 지금까지 앙상블 기법에서 배깅에대해 다루어 보았습니다. 이제 Boost에대해 알아보겠습니다. Bagging이 데이터셋을 새롭게하면서 다양성을 부여했다면, 부스트는
exupery-1.tistory.com
[Ensemble] Gradient Boosting, 차근차근
Gradient Boosting, 차근차근 Ensemble Gradient Boost는 앙상블과 AdaBoost, 선형회귀에서의 Gradient Desent의 개념을 알고 있으면 쉽게 이해하고 사용할 수 있습니다. 이 포스트는 앞서 작성된 포스트를 기반으..
exupery-1.tistory.com
1. Introduction
Among the 29 challenge winning solutions 3 published at Kaggle’s blog during 2015, 17 solutions used XGBoost. Among these solutions, eight solely used XGBoost to train the model, while most others combined XGBoost with neural nets in ensembles. For comparison, the second most popular method, deep neural nets, was used in 11 solutions.
- XGBoost: A Scalable Tree Boosting System, Tianqi Chen, Carlos Guestrin (KDD2016)
XGBoost의 논문에서는 29개 대회중에서 17개가 XGBoost가 우승을 거머쥐었다고합니다. 나머지는 deep neural net이 11개를 차지했습니다. 성능하나는 확실히 좋은 것 처럼 보입니다. 어떻게 이렇게 좋은 성능을 낼 수 있었는지 논문과 함께 살펴보겠습니다. 논문과 함께 보고싶은 분은 여기를 클릭하세요.
Scalability
The most important factor behind the success of XGBoost is its scalability in all scenarios.
XGBoost가 성공적이었던 이유는 Scalability라고 말합니다. 이는 확장성을 의미합니다. 이 기술이 쓰일 수 있는 것이 매우 다양한 분야에 걸쳐 있다고 생각하면 될 것 같습니다. 저자는 예로 다음과 같이 들었습니다.
store sales prediction 매장 매출 예측
high energy physics event classification 고에너지 물리 이벤트 분류
web text classification 웹 텍스트 분류
customer behavior prediction 고객 행동 예측
motion detection 동작 감지
ad click through rate prediction 광고 클릭 속도 예측
malware classification 악성 프로그램 분류
product categorization 제품 분류
hazard risk prediction 위험 예측
massive online course dropout rate prediction 대규모 온라인 코스 중퇴율 예측
Innovation
XGBoost의 Scalability는 시스템과 알고리즘 최적화에서 시작됩니다. 저자는 section 2에서 Tree Boosting을, Section 3에서는 Split Fininding Algorithms 이야기하며 알고리즘을 최적화는 것에대해 설명하고, Section 4 System Design에서 시스템에서의 Innovation을 말합니다. 크게 알고리즘과 시스템에대한 내용입니다. 이 포스트에서는 수학적 증명보다는 개념에대한 이해에 중점을 두고 접근합니다. (Section 2는 앞의 포스트와 매우 밀접한 연관이 있고, 같은 설명을 되풀이 하는 것이라 생각하시면 됩니다.)
2. Tree Boosting In a Nutshell
1. Regularized Learning Objective
Base Learner는 CART(Classification And Regression Trees)를 사용합니다. (이전포스트 참조)
간략히 예시를 통해 살펴 보면, 각 input(할아버지 할머니 외 3명)들은 CART로 먼저 분류하고 (수식에서 $q$)
가중치를 더해줍니다. (수식에서 $w$)
수식을 조금만 더 살펴 보자면, $F=\{f(x)=w_{q(x)}\}$에서, $f(x)$는 트리 자체를 의미하고, $q(x)$는 각 트리의 structure를 의미하는 것 입니다. $q(x)$에 $x$라는 수를 넣어서 나오는 노드의 weight가 $w$입니다. 여기서 남자아이는 첫번 째 트리에서 가중치를 +2를 받고, 두번째 트리에서 +0.9를받아서 총 +2.9를 받았습니다. $w$와 $q$는 Loss Function을 최소로 만들어 줌으로써 알아낼 수 있습니다.
2. Gradient Tree Boosting
Gradient Boosting을 사용합니다.(이전포스트 참조)
테일러정리를 통해 식을 전개하는데, 이는 생략하도록 하겠습니다.
결론만 보면, 최적의 가중치는 (5)가 되고, Tree q의 구조적인 점수는 (6)이 됩니다. 식(6)은 트리가 잘 만들어졌는지 평가하기위한 식으로 활용할 수 있습니다. (g는 gradient를 의미하고 h는 hessian입니다.)
여기서 $I$는 관측치를 의미하고 , $g_i$와 $h_i$는 Loss Function에서 1차, 2차 편미분을 한 값입니다. 15세 미만인가, 남자인가에대한 대답이 모두 yes인 관측치는 1번 남자아이였습니다. 1차미분을 한 값은 $g_1$(gradient)이고, 2차 편미분을 한 값은 $h_1$(hessian)이 됩니다. 각 관측치에서 g와 h는 모두 합쳐지게됩니다. 그리고 Obj($q$,식(6))를 통하여 트리구조에대해 스코어링을 하게됩니다.
다만 만들 수 있는 모든 트리를 만들어내는 것은 불가능합니다. 대신에 Greedy Algorithm으로 트리를 하나씩 더해갑니다. 마지막에 만들어진 트리와 split되기 이전에 만들어진 트리의 차이를 구해주는(Gain을 계산하는) 방법입니다.
Information Gain을 계산하는 법은, Split을 한 뒤에 왼쪽 Leaf의 Score와 오른쪽 Leaf의 Score를 더하고 부모노드의 점수를 빼는 것으로 구합니다. 이를 통해서 Split이후에 Loss가 더 적어지는 쪽을 선택합니다.
$\gamma$(감마)
무한히 분기(split)하면 Overfitting됩니다. 그렇기에 가지(branch)를 만들지 말지에 대한 기준을 세웁니다. 감마는 그 기준이 됩니다. Information Gain이 감마보다 작다면, 가지는 제거됩니다. 즉, 먼저 가지를 만들고 나서 (Information Gain - $\gamma$)가 음수이면 가지를 제거하고, 양수이면 가지를 놔둡니다.
$\lambda$(람다)
Regularization 파라미터입니다. 람다의 역할은 위 $Obj$(Score)식 안에 분모에 위치합니다. 다시 말해 람다의 값이 크면 전체 score를 줄여준다는 뜻입니다. 예를들어 만약 $\gamma$(감마)가 100으로 정해져있다면, split을 했을 때 Information Gain이 100이상이어야 가지를 유지할 것입니다. 람다가 크면 클 수록 값이 작아질 테니 100이 되지 않는 가지가 많아지고 제거되는 가지가 많아질 것입니다. 가지를 제거함으로써 Overfitting을 방지합니다.
3. Shrinkage and Column Subsampling
Gradient Boosting에서 Regularization 때 잠깐 다뤘던 주제입니다.
Shrinkage는 트리에대한 가중치를 다르게 주는 것입니다. 마치 Stochastic optimization에서 Learning Rate를 조정했던 것과 같이 각 트리의 개별적인 영향을 줄여줍니다. 나중에 만들어질 트리에게 기회를 주는 것이죠 !
Column subsampling은 랜덤포레스트에서처럼 칼럼을 다 뽑지 않음으로써 다양성을 부여하고 Overfitting을 방지합니다.
3. Split Finding Algorithms
XGBoost는 Gradient Boost와 eXtreme이 합쳐진 단어입니다. Gradient Boost이지만, 보다 빠르게 처리하고자하는데 그 목적이 있습니다. 이 목적을 위해서 논문에서는 다음 네 가지를 소개합니다.
1. Basic Exact Greedy Algorithm
알고리즘에서 for문안에 for문에서 모든 경우의 수를 탐색하는 것을 볼 수 있습니다. 기존의 트리모델처럼 feature를 split을 하기 위해서 모든 경우의 수를 파악합니다. 문자 그대로 Exact Greedy합니다. 항상 Optimal Solution이 될 것입니다. 하지만 데이터가 한꺼번에 로딩되지 않으면 알고리즘 실행자체가 불가합니다. 또한 한번에 처리를 해야하니 분산환경 (distributed setting)에서 처리가 될 수 없어 병렬처리가 불가하다는 단점이 있습니다. 시간도 오래걸리겠죠
2. Approximate Algorithm
Exact greedy algorithm에서 있었던 데이터 로딩문제와 분산환경에서의 처리문제를 극복하기 위한 대안으로 Approximate Algorithm가 있습니다. 데이터를 먼저 퍼센타일(Percentiles)로 나눕니다($l$개 만큼). 퍼센타일은 feature의 분포를 통해서, 나누는 방법입니다. 순서대로 정렬하는 것은 시간이 오래 걸리므로 100개의 Quantile로 나누는 방법입니다(Quantile은 아래에서 설명합니다). 하이퍼 파라미터 $\epsilon$을 조정하여 얼마나 잘게 나눌지 결정합니다. 버킷은 일반적으로 $\frac{1}{\epsilon}$만큼 만들어집니다. 이 과정에서 $l$개 만큼의 Bucket이 만들어 집니다.
exact greedy는 모든 split에대해서 계산했다면, approximate는 bucket안에서의 split만 계산합니다. 예를들어 9개의 데이터가 있으면, 1과 2~9, 1~2와 3~9, 1~3과 4~9,... 이런식으로 나누는 것이 아니라, 123/456/789로 먼저 버킷에 세 개씩 담은 후에 각 버킷별로 split합니다.
첫번째 버킷에서는 1과 23, 12와 3으로 두번에 끝나게 될 것이고, 두번째 버킷은 4와 56, 45와 6으로, 세번째도 마찬가지입니다. 첫번째 방법으로 split한다면 총 8번이 수행될 것입니다. 버킷으로 수행한다면, 6번(2*3)실행되어 찾을 수 있습니다. 또한 각 버킷은 다른 스레드로 태워서 계산할 수 있어 병렬처리가 가능합니다. 그리고 각 버킷에서 split했을 때 가장 information gain이 큰 버킷에서 split이 이루어지게 됩니다.
Split을 하고 난 뒤에서는 Global variant로 하는 법과 Lovcal variant로 하는 법이 있습니다. 위 그림은 Global입니다. 가장 Information gain이 컸던 bucket에서의 split point를 기준으로 나누었습니다. 처음에는 10개의 버킷으로 나누었지만, 다음 단계에서는 각각 5개, 6개의 버킷으로 나누어져 있습니다. 짤린 부분을 제외하곤 버킷이 늘지않습니다. 굳이 새롭게 버킷을 다시 담지 않는 것입니다.
처음에 10개의 버킷으로 나누었다면, split된 이후에도 10개의 버킷으로 새롭게 담을 수도 있습니다. 이러한 방법이 Local variant입니다. depth가 깊어질 수록 버킷의 수는 유지가 되니 그 속에 담긴 데이터의 수는 점점 줄어들게 되겠죠. 점점 더 세분화될 것 입니다.
Global과 Local의 차입니다. eps는 입실론을 의미합니다. 입실론이 같다면, Global보다는 Local이 훨씬 더 정확합니다. 그렇다하더라도 입실론을 충분히 적게해주면 exact greedy와 거의 같은 성능을 낼 수 있다는 점도 확인할 수 있습니다.
3. Weighted Quantile Sketch
Weighted Quantile Sketch를 다루기위해서 하나씩 뜯어보겠습니다. 먼저 Sketch 알고리즘은 통계에서 표본집단으로 모집단을 추론하는 것과 유사한 개념입니다. Quantile Sketch 알고리즘에서 Quantile이 의미하는 것은 어떤 집단에서의 class입니다. 예를들어 소득분위를 10분위로 나누었을 때 한 분위가 한 Quantile이 됩니다. (Percentile은 어떤 집단을 100개로 나눈 것입니다. 쉽게말하면 Percentile은 100개로 나눈 Quantile입니다.) 여기까지가 Quantile Sketch에대한 내용이었습니다.
Quantile은 보통 같은 개수로 나눕니다. 각 Quantile에는 같은 개수의 관측치가 존재합니다. Weighted Quantile에서 Weight가 의미하는 바는 Loss funciton에서 두번째 편미분한 값이며 Hessian($h_i$)이라고 부르는 값입니다. 이렇게 각 관측치에 weight를 구합니다. 그리고 그 weight의 합이 각 quantile에서 같습니다. 즉, weight의 합이 동일한 quantile로 구성한 것이 Weighted Quantile Sketch입니다.
Regression에서는 Weight가 모두 1입니다. 다시말하면 Normal Quantile과 다를바가 없다는 뜻입니다. 반면 Classification에서는 weight는 Previous Probability$_i\times$ (1-Previous Probability$_i$)이기 때문에 각 관측치마다 천차만별입니다.
정리하자면, 대용량의 데이터를 처리할 때 Approximate Greedy Algorithm을 통해서 Parallel하게 계산을 하고, 다시 합쳐 approximate histogram을 만듭니다. 그리고 weight의 합이 동일한 Quantile로 구성합니다. 데이터가 적은경우 1번 알고리즘을 사용하고 끝나겠죠
4. Sparsity-aware Split Finding
데이터에 결측치가 없으면 좋겠지만, 현실에서는 그러기란 쉽지 않습니다. 혹은 0값이 많거나 Onehot encoding을 하는경우 굉장히 sparse하게 됩니다. XGBoost는 이러한 부분도 커버하는 아주 훌륭한 부스팅기법입니다. Scalability가 아주 뛰어난 것이죠 ! Sparsity-Aware Split Finding이라는 단어에서도 알 수 있듯이, sparse한 경우 aware하고 split을 하기위한 finding을 하는 것입니다.
missing value가 있거나 혹은 0이 너무 많이 나타나는 데이터에서 쉽게 처리할 수 있는 방법입니다. 알고리즘을 보면 for문 안에 첫번째 for문에서 enumerate missing value goto right가 보입니다. 모든 missing value를 오른쪽으로 미는 것 입니다. 그리고 가장 score가 높은 데에서 split을 합니다. 그리고 두번째에서는 missing value를 왼쪽으로 밀어버립니다. 똑같이 split을 하고 점수를 냅니다. 이 두개를 비교해서 default 값을 정합니다.
예를 들어서 missing value가 오른쪽으로 밀어 점수를 낸 것이 왼쪽보다 높다면, 이후에 새로운 데이터를 예측 할 때 오른쪽으로 밀었을 때의 상황으로 보내버리는 것입니다.
위 자료는 이에대해 나타내는 그림입니다. 빨간색으로 default값이 정해져있죠? age가 missing value인경우 Y가 default가되고 is male?에대한 답이 missing이라면 N이 default가 됩니다.
속도를 비교한 그림입니다. Default를 정해놓은 것이 속도에서 큰 차이를 내고있습니다.
4. SYSTEM DESIGN
사실 데이터가 커지면 커질 수록 시간을 많이 잡아먹는 데에는 정렬(sorting)하는데에 있습니다. 아무리 효율적으로 sorting을 시키더라도 $O(n\log{n})$만큼의 시간이 걸립니다.(BigO notation에대한 설명은 이전포스트 참조)
1. Column Block for Parallel Learning
데이터를 Row로 취급하는 것이 아닌 Columns으로 취급합니다. 일반적으로 데이터셋을 보면 각각의 관측치는 row에 따라서 저장이 됩니다. 이를 컬럼 별로 저장하는 것입니다. 각각의 컬럼들은 훈련하기 전에 정렬시켜서 계산한 값을 저장하고 사용하기 위함입니다. 각각의 컬럼에서는 index가 달라지게 됩니다.
위 그림을 보면, 각 컬럼을 먼저 정렬을 시킵니다. pointer도 같이 저장이 되는 것입니다(index가 같이 저장되는 것). 이렇게 각 컬럼들을 저장합니다. 이 때 Missing value는 compressed되어 저장이 되지 않습니다. 원래 데이터는 12개였는데 10개만 저장되는 것입니다. 이렇게 저장되는 방식을 CSC(the Compressed Column)format이라고 합니다. 각 컬럼에서는 선형탐색(Linear Scan)을 통해서 Split points를 찾습니다. 컬럼별로 나뉘어있으니 parallel한 탐색을 할 수가 있습니다.
앞서 대용량일 때 Approximate algorithms를 사용한다고 하였는데, 이 때 Block structure가 사용됩니다. 하나의 블럭에 데이터를 넣는 것이 아닌 여러개의 블록에 subsample을 해서 각 블록별로 Statistics를 계산하는 것입니다. 블록별로 계산 된 Statistics을 선형탐색함으로써(Linear Scan over sorted columns) parallel하면서도 전체 데이터를 확인하여 컬럼을 결정할 수 있는 방법입니다.
2. Cash-aware access
CPU가 계산을 할 때 Cashe가 가장 빠르고, 다음으로 메인메모리가 빠르며, 디스크가 가장 느립니다. 다시말하면 자주쓰이는 연산을 캐쉬로 하면 메인메모리에 있을 때 보다 훨씬 빠른 연산을 할 수 있겠다라는 데서 출발합니다. XGBoost에서는 가장 많이 쓰이는 gradient와 hessian을 캐쉬에 넣습니다.
데이터가 많을 수록 속도차이가 많이 나는 것을 확인할 수 있습니다.
3. Blocks for Out-of-core Computation
XGBoost는 이에 그치지 않습니다. 논문에서도 One goal of our system is to fully utilize a machine’s resources to achieve scalable learning이라고 말합니다. 정말 extreme합니다.
데이터셋이 너무 커서 메인 메모리에 다 로드를 하지 못할 때 하드드라이브도 사용해야할 것입니다. 하지만 위에서 알아 보았듯이 하드드라이브는 느립니다. 하드드라이브에 엑세스하는데 시간을 많이 소비할 수도 있다는 뜻이 됩니다.
이를 Block Compression(압축)하는 방법을 사용합니다. 여러 압축방법을 사용하여 대략 26~29%가 압축됩니다. 두번 째로는 Block Sharding(조각)이라는 방법을 사용하는데, 이는 데이터셋을 여러개로 나누고 그 데이터에 동시에 접근하는 것입니다.
5. RELATED WORKS
여러 프레임워크에서 제공하는 트리 부스팅 시스템을 비교해놓은 표입니다. 쓰면서도 매우 자랑스러웠을 것 같습니다. 논문에서도 문제를 해결하기 위해서 많은 고민을 한 것이 보이는 것 같습니다.
XGBoost는 Gradient Boosting기반입니다.
Overfitting을 막기위해 Regularization합니다.
Random Forest에서 차용한 Column Sampling을 사용합니다.
Sparsity-aware learing을 통해서 default를 지정해줍니다.
Parallelizing tree learing이 가능하고,
Cash-aware 같은 System적인 요소들도 있었습니다.
Open Source Package이며,
Python과 R, Julia같은 언어를 지원하고,
하둡과같은 분산환경에서 작동할 수 있습니다.
참고자료
XGBoost Algorithm: Long May She Reign!
The new queen of Machine Learning algorithms taking over the world…
towardsdatascience.com
Introduction to Boosted Trees — xgboost 1.4.0-SNAPSHOT documentation
Introduction to Boosted Trees XGBoost stands for “Extreme Gradient Boosting”, where the term “Gradient Boosting” originates from the paper Greedy Function Approximation: A Gradient Boosting Machine, by Friedman. The gradient boosted trees has been
xgboost.readthedocs.io
pilsung-kang/Business-Analytics-IME654-
Course homepage for "Business Analytics (IME654)" @Korea University - pilsung-kang/Business-Analytics-IME654-
github.com
'인공지능 > 앙상블' 카테고리의 다른 글
| 뭣이 중헌디! 특성의 중요도 (4) | 2021.02.25 |
|---|---|
| [Ensemble] Light GBM, 마이크로소프트의 부스팅 (0) | 2021.02.14 |
| [Ensemble] Gradient Boosting, 차근차근 (0) | 2021.02.12 |
| [Ensemble] Ada Boost, 모델의 오답노트 (0) | 2021.02.11 |
| [Ensemble] 랜덤 포레스트, 나무가 이루는 숲 (0) | 2021.02.11 |
댓글