XGBoost: A Scalable Tree Boosting System

XGBoost: A Scalable Tree Boosting System

 

 

 

1.  Introduction 

 

Gradient Boosting에 extreme한 요소들을 얹으면 XGBoost가 된다

 

Scalability를 얻기 위해 두가지 Innovation이 있음

 

이것은 알고리즘적 그리고 시스템적으로 나눠지는데

알고리즘적으로는 tree boosting , split finding algorithm  

-> 알고리즘적으로는 regularized gradient boosting 으로 크게 변화한 부분이 없지만

시스템 적으로는 많이 변화함  -> 이 논문에서는 알고리즘 적으로 많이 살펴볼 예정

 

2. TREE BOOSTING IN A NUTSHELL

 

y햇은 파이에 x를 인풋으로 넣었을 때 나오는 값인데 여기서 파이는(세타) 트리부스팅 전체를 의미하고

f_k 는 각기 개별적인 트리를 얘기해서 , 위에처럼 f1+f2+f3 ... 을 모두 더한 값이 트리 부스팅의 결과

 

* ada와 gbm 차이

 

ada는 잘못 예측한 값에 대해 가중치를 더 주는 것이고 gbm은 잘못 예측한 값(잔차)에 대해 에러를 예측함으로 

지속적으로 부족함을 메워가는 알고리즘

 

 

xg boost의 베이스러너 즉 개별적은 트리는 카트라는 트리를 사용함(분류,리그레션을 하는 트리)

위의 그림에서 인풋 5개가 먼저 카트에 들어가서 분류되고 도착한 노드에 웨이트들을 모두 sum한 값들이 그 하나의 데이터의 점수가 됨  

카트를 타고 오른쪽으로 가면 소녀은 점수 tree 1에서 2점 tree 2에서 0.9이므로 2.9가 됨

 

카트에서 w는 어떻게 구하고 트리를 제대로 구한게 맞는지 q에대한 평가는 어떻게 하는지 등은

LOSS FUNCTION으로 구할 수 있음 (w와 q)

 

새로운 함수 기준은 어떨까? -> 기존의 함수 집합에 더해졌을 때 LOSS FUNCTION이 최소가 되는 함수를 찾는 것

yi : 레이블 , y^i : 예측값  -> 이것 두개의 차이가 최소인 것을 찾아내는게 목적 + 함수에 대한 regularization 까지 얹는 것이

로스트 function

 

그런데 로스 함수를 보면 아쉽게도 파이 자체가 funtion 이라 -> 파라미터가 fuction 이라 -> numeric vecor 가 아니어서

유클리디언을 활용한 최적화가 불가능

결국 솔루션으로 boosting 자체가 additive training이 라는 것을 생각하여 식을 조금 바꿀 예정

부스팅 -> t-1 프레딕션에 t 시점에 새로 만들어진 함수를 더하는 것이 컨셉

 

로스 펑션에 상자 식을 대입하면 아래와 같이 나타남

여기서 이 함수를 발전시키기 위해 taylor expansion을 사용

테일러 expansion의 정의

미지의 함수f(x)를 다항함수로 근사 시키는 것 -> 표현식이 깔금하게 구성되는 대신 근사가 됨

이것을 xgboost에 사용하면 아래와 같은 식이 나타남

 

테일러 expansion 추가 설명

 

 

1차 미분  : g  , 2차 미분 : h

 

y와 y^ 의 차이는 일정한 상수라서 제거

두번째 식에서 sum이 두개가 있음 n과 T

결국 n과 t중 어떤 것을 기준으로 합쳐야하냐 했을 때 loss function에서의 기준은 파이임

트리의 관점에서 로스를 봐야해서 sum을 t로 규합 ->  n = 인스턴스 갯수  t= leaf 갯수

 

 

t에 대해서 sum을 규합하는 과정 , i는 j와 같지않아서 식이 서로 포함될 수 없는데

맨아래식은  i가 j에 대한식이 될 수 있도록 식을 바꾸는 과정

 

 

왼쪽식과 오른쪽 식이 같은 이유

1.각자 구하고 sum  , 2. 묶음별 sum을 sum

 

 

loss function을 최소화하는 x를 구하기 위해 미분 , 밑에식에서 x= w (웨이트)

 

 

 

 

1. 왼쪽에서 얻은 점수

2. 오른쪽에서 얻은 점수

3. 분할되기전의 점수

l_split은 split 이후 loss reduction을 나타내고 분할을 했을 때 감소폭이 큰 분할을 선택한다

 

 

새롭게 생긴 트리에 상수 n을 구해 각트리의 영향력을 그대로 반영하는게 아니라 영향력을 낮추는 것

 

 

3.split finding algorithms

 

 

- basic greedy algorithm

feature 에 대한 split을 찾는 과정

전부 다 iterate 하는 것은 비용이 너무 크기 때문에 효과적으로 진행하기 위해 sorting을 사용

모든 데이터 기준으로 split하고 비교하는게 비용이 많이듬

 

g의 1차미분 2차미분을 구하고 그것을 score와 비교하면서 max를 덮어씌우면

3.2 approximate algorithm

-> 해를 근사하여 시간을 감소

베이직 그리디 알고리즘은 -> 1~100까지 split을 다해보이는것  approximate 는 10,20,30 처럼 10분위로 짤라서 근사하는 것

 

0 ,1 ,2 파트하나를 bucket으로 두고 내부에서 통계량을 구하는 것 -> 그것을 통해 해당 split이 좋으냐 안좋으냐를 파악

-> 이렇게 하면 Paralleization이 가능

 

입실론 : 얼마나 퍼센트를 잘게 나눌지에 대한 파라미터

 

3.3 weighted quantile sketch

표본집단으로 모집단을 예측하는 것

weighted quantile -> 각 퀀틸의 sum of weights 가 같다 , hi 가 웨이트의 역할

 

3.4 Sparsity -aware Split finding

스파스한 데이터의 경우도 xgboost는 scalability를 통해 아우르겠다

 

 

 

 

I 미싱데이터를 모두 오른쪽으로 보내고 I_k를 분할하여 x를 고르고  이후에 I 미싱데이터를 왼쪽으로 보내고 반복

결국 왼쪽이나 오른쪽에서 맥스값이 나올텐데 맥스가 나오는 부근으로 보내주기

 

4. System DESIGN

 

4.1 Column Block for Parallel Learning

column orientedd :관심이 있는 컬럼만 뽑아서 비교 진행가능

sorting도 데이터가 매우 커지면 시간이 많이 들기에 데이터를 블록에 담아서 사용

 

리니어하게 찾아서 NAN 값을 없애고 9개만 보관 -> best split을 찾기

각 row를 모두 subsampling을해서 베스트 split을 찾고 베스트 split에 대한 리니엇 스캔 진행 하여 paralrel 하면서도 전체적으로도 확인 가능 

결국 DIstributed across machines 가 될 수 있음

 

4.2 CACHE _AWARE ACCESS

4.3 BLOCKS FOR OUT-OF-CORE COMPUTATION