Xgboost 논문 리뷰 및 코드를 작성한 내용입니다. 논문의 전체를 리뷰하진 않고 특정 부분만 했습니다

부스팅
- 라운드가 지날수록 모델의 에러를 줄이는 과정
- 어떤 모델이 유효한지, 적절한지를 찾아내는 과정
- 약한 예측 모형들을 결합해 강한 예측 모형을 만드는 알고리즘
- 배깅과 유사하게 초기 샘플 데이터로 다수의 분류기를 만들지만 배깅과 다르게 순차적
- 무작위성이 없으며 강력한 사전 가지치기 사용

XGBoost Paper

Abstract

Tree boosting은 매우 효과적이고 머신러닝 방법에서 많이 사용됨
유연하고 end-to-end tree bootsting 시스템인 XGBoost
sparse한 data를 위한novel sparsity-aware algorithm과 approximate tree learning를 위한 weighted quantile sketch를 제안
cache access 패턴, data compression, sharding에 대한 인사이트 제공

Keywords

Large-scale Machine Learning

1. Introduction

성공적인 어플리케이션의 2가지 중요한 요인
- 효과적인 통계적인 모델 사용
- 유연한 learning 시스템
XGBoost의 가장 중요한 요인 : 모든 시나리오에 대한 확장성
- 단일 시스템에서 사용한 기존 일반적 솔루션보다 10배 이상 빠르게 실행
- 분산 또는 메모리가 제한된 상황에서도 수십억 가지의 예제로 확장
XGBoost의 확장성은 여러 중요한 시스템과 알고리즘 최적화로 구성됩니다
- Sparse data를 handling하기 위한 novel tree learning algorithms
- qunatitle sketch procedure를 사용해 approximate tree learning에서 인스턴스 가중치를 처리할 수 있음
- 병렬 및 분산 컴퓨팅으로 학습 속도가 빨라져 model ex-ploration이 빨라짐
- out-of-core(core를 벗어난? 넘어선?) 계산을 이용하고 데이터 과학자가 데스크탑에서 수억개의 예시를 처리할 수 있게함
본 논문의 핵심
- We design and build a highly scalable end-to-end tree boosting system : 확장성이 뛰어닌 end-to-end 부스팅 시스템 설계
- We propose a theoretically justified weighted quantile sketch for efficient proposal calculation : 효율적인 proposal 계산을 위한 weighted quantitle sketch 제안
- We introduce a novel sparsity-aware algorithm for parallel tree learning : 병렬 트리 학습을 위한 novel sparsity-aware 알고리즘 소개
- We propose an effective cache-aware block structure for out-of-core tree learning : 코어를 넘어선 트리를 학습하기 위한 효율적 캐시 인식 블록 구조 제안

2. Tree Boosting in a nutshell

review gradient tree boosting algorithms

2.1 Regularized Learning Objective

Leaf 노드 하나에 대해서만 Decision Value를 갖는 Decision tree와 달리, 모든 regression tree는 연속적인 점수를 포함
이 방식은 CART 방식으로, 모든 리프들이 모델의 최종 스코어에 연관되어있다는 뜻
CART는 모델끼리 모델의 우위를 비교할 수 있음
i번째 잎의 점수를 \(w_{i}\)로 표현

\(L(\emptyset) = \sum_{i}l(\hat{y_{i}}, y_{i}) + \sum_{k}\Omega(f_{k})\) \(where\quad \Omega(f_{k})=\gamma T+\frac{1}{2}\lambda ||w||^{2}\)

\(l\) : differentiable convex loss function
\(\Omega\) : 모델의 복잡성 패널티 계수
- 최종 학습된 가중치를 부드럽게할 때 도움
RGF(Regulized greedy forest) 모델에서도 비슷한 정규화 방법 사용
\(\gamma T\) : Number of leaves
\(\gamma T+\frac{1}{2}\lambda \lVert w\rVert^{2}\) : L2 norm of leaf scores
리프 스코어와 리프 갯수가 모델의 복잡도를 결정

2.2 Gradient Tree Boosting

t번째 iteration에서 i번째 인스턴스의 예측을 \(\hat{y_{i}}^{(t)}\)라 하고 \(f_{t}\)를 추가해 다음과 같은 목적 함수를 최소화

\[L^{t} \simeq \sum_{i}^{n}[l(y_{i},\hat{y}^{(t-1)}) + g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^2(x_{i})] + \Omega(f_{t})\]

목적 함수를 단순히 하기 위해 상수항을 제거

\[\tilde{L}^{(t)} = \sum_{i=1}^{n}[g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{i})]+\Omega(f_{t})\qquad(3)\]

\(\Omega\)를 풀면

\[\tilde{L}^{(t)} = \sum_{i=1}^{n}[g_{i}f_{t}(x_{i})+\frac{1}{2}h_{i}f_{t}^{2}(x_{i})]+\gamma T+\frac{1}{2}\lambda\sum_{j=1}^{T}w_{j}^{2}\] \[= \sum_{j=1}^{T}[(\sum_{i \in I_{j}}g_{i})w_{j}+\frac{1}{2}(\sum_{i\in I_{j}} h_{i}+\lambda)w_{j}^{2}]+\gamma T \qquad(4)\]

\(q(x)\)가 fixed structure라서 leaf j의 optimal weight \(w_{j}^*\)를 계산할 수 있음

\[w_{j}^{*}=-\frac{\Sigma_{i\in I_{j}}g_{i}}{\Sigma_{i \in I_{j}} h_{i}+\lambda} + \gamma T \quad(5)\] \[\tilde{L^{(t)}}(q)=-\frac{1}{2}\sum_{j=1}^{T} \frac{(\Sigma_{i\in I_{j}}g_{i})^{2}}{\Sigma_{i \in I_{j}} h_{i}+\lambda} + \gamma T \quad(6)\]

(6)은 tree 구조 q의 scoring function으로 사용될 수 있음

2.3 Shinkage and Column Subsampling

오버피팅을 방지하기 위해 사용된 기술
- 1) Shrinkage : tree boosting 후 각 step후에 새로 추가된 weights
- 2) Column(feature) subsampling : column subsampling을 통해 오버피팅 방지하고 병렬적으로 학습 속도를 높일 때 사용됨 (전통적인 subsampling은 row 기반이었음)

3. Split finding algorithms

3.1 Basic Exact Greedy Algorithm

Exact Greedy Algorithm : 모든 feature의 가능한 split point를 나눠서 탐색 => 계산 오래 걸림

3.2 Approximate Algorithm

feature 분포의 percentile에 기반해 bucket으로 매핑

인터넷을 통해 공부한 내용

Boosting
- 기존 모델이 잘 못맞춘 데이터를 간단한 추가 모델을 이용해 보완. 이런 과정으로 모델의 표현력을 높임
- weight에 기반하면 Adaboost(못 맞추는 것에 대한 weight), error를 미분한 gradient에 기반하면 gradient boost가 됨
Feature Importance : tree 계열의 알고리즘에서 각 attribute가 얼마나 유용한지를 판단하는 feature importance를 계산할 수 있음. 하나의 decision tree에서 각각의 attribute로 이루어진 split point에 의해 얼마나 트리의 성능이 올라가는지를 계산함. instance가 split point에 의해 영향을 받는지 숫자만큼 가중치를 두어 성능 향상치를 계산함. 앙상블 모델(RF)은 모든 decision tree에 대해 구하고 평균을 냄. 성능 측정은 지니계수 또는 information gain을 사용
욕심쟁이 알고리즘을 사용해 분류 모델 M, G, H를 발견하고 분산처리를 통해 적합한 비중 파라미터를 찾음!
분류기는 Regression Score를 사용해 정확도 스코어를 측정하고 각 순서에 따라 강한 분류기부터 약한 분류기까지 랜덤하게 생성! => 분류기가 트리임
xgboost를 tree를 만들 때 CART라 불리는 앙상블 모델을 사용. 모든 리프들이 모델의 최종 스코어와 연관되어 있어서 같은 분류 결과를 갖는 모델끼리도 모델의 우위를 비교할 수 있음
트리 가지를 나누는 시점에서 information gain을 순차적으로 계산한 후, 점수가 마이너스일 때 가지를 잘라냄
xgboost가 빠른 이유는 폭 방향으로 성장하기 때문. 각 레벨에서 한번만 정렬, traverse 가능
- 또한 sorted features는 cache

파라미터

2-1. 일반 파라미터

booster : 어떤 부스터 구조를 쓸지. gbtree, gblinear, dart
n_jobs : 몇 개의 쓰레드를 동시에 처리. default는 많이
num_feature : feature 차원의 숫자를 정해야 할 경우. default는 많이

2-2. 부스팅 파라미터

eta : learning rate로 boosting step마다 weight를 줘서 부스팅 과정에 오버피팅이 일어나지 않도록 함
gamma : infromation gain에서 r로 표현한 값. 이 값이 커지면 트리 깊이가 줄어들어 보수적인 모델이 됨
max_depth : 한 트리의 maximum depth. 커질수록 모델의 복잡도가 커짐. default는 6이고 이 경우 리프 노드의 개수는 최대 2^6
lambda(l2 reg-form) : l2의 weight로 숫자가 클수록 보수적인 모델
alpha(l1 reg-form) : l1의 weight로 숫자가 클수록 보수적인 모델

2-3. 학습 과정 파라미터

objective : 목적함수로 reg:linear, binary:logistic, count:poisson 등 다양함
eval_metric : 모델의 평가 함수, rmse, logloss, map 등
seed : 시드값 고정

2-4. 커맨드 라인 파라미터

num_rounds : boosting 라운드를 결정. 이 수가 적당히 큰게 좋음. epoch 옵션과 동일

XGBoost 설치

Mac

brew install gcc
git clone --recursive https://github.com/dmlc/xgboost.git
cd xgboost; cp make/config.mk ./config.mk;

vi config.mk
// 아래 2개 주석 처리된 것 풀기
export CC = gcc-7
export CXX = g++-7
Esc:+q

make -j4
sudo pip3 install -e python-package

Test

import xgboost as xgb
import numpy as np
data = np.random.rand(5, 10)
label = np.random.randint(2, size=5)
dtrain = xgb.DMatrix(data, label=label)
model = xgb.XGBClassifier(n_estimators=5, nthread=-1, seed=8888)

Reference

카일스쿨 유튜브 채널을 만들었습니다. 데이터 사이언스, 성장, 리더십, BigQuery 등을 이야기할 예정이니, 관심 있으시면 구독 부탁드립니다 :)

PM을 위한 데이터 리터러시 강의를 만들었습니다. 문제 정의, 지표, 실험 설계, 문화 만들기, 로그 설계, 회고 등을 담은 강의입니다

이 글이 도움이 되셨거나 다양한 의견이 있다면 댓글 부탁드립니다 :)

Buy me a coffee