[논문 리딩] XGBoost: A scalable Tree Boosting System

XGBoost: A scalable Tree Boosting System
T. Chen, C.Guestrin, 2016

Abstract

Tree Boosting은 아주 효율적이고 널리 쓰이는 머신러닝 기법이다.

본 논문에서는 종단간 기계학습이자 scalable한 학습법인 XGBoost를 소개한다.

 

* 종단간 학습(end-to-end learning): 데이터에서 목표한 결과를 사람의 개입 없이 얻는 것 

* scalable machine learning: 어떤 양의 데이터에도 많은 양의 리소스(메모리 등)을 사용하지 않고 대응할 수 있는 알고리즘

 

1 Introduction

논문의 주요 contribution:

• We design and build a highly scalable end-to-end tree boosting system.
• We propose a theoretically justified weighted quantile sketch for efficient proposal calculation.
• We introduce a novel sparsity-aware algorithm for parallel tree learning.
• We propose an effective cache-aware block structure for out-of-core tree learning.

2 Tree Boosting in a Nutshell

2.1 Regularized Learning Objective

다음과 같은 데이터셋이 주어졌다고 하자.

 

• $D = \left\{ (x_i, y_i )\right\}$
• $|D| = n$
• $x_i \in \mathbb{R}^{m}, y_i \in \mathbb{R}$

 

K개의 함수를 앙상블해 결과를 예측하는 Tree ensemble model은 다음과 같이 정의된다.

 

$\hat{y_i} = \phi(x_i) = \sum_{k=1}^K f_k(x_i)$, where $f_k \in \mathcal{F}$

이 때,

• $\mathcal{F} = \left\{ f(x) = w_{q(x)} \right\} (q: \mathbb{R}^m \rightarrow T, w \in \mathbb{R}^T)$ :회귀 나무의(regression tree) 집합
• $q$: 각 데이터를 tree의 leaf번호에 매핑하는 구조
• $T$: 나무의 leaf 노드 개수

각 $f_k$는 독립적인 트리 구조 $q$와 리프 노드의 가중치 $w$에 대응한다.

의사결정나무와 달리 각 회귀 나무는 리프 노드들에 대한 연속적인 점수를 가지고 있다. ($w_i$: $i$번째 노드의 점수)

$q$에 의해 주어진 decision rule을 통해 주어진 샘플을 리프 노드들에 할당하고, 해당되는 리프 노드들의 점수의 합계를 구함으로써 최종 예측값을 얻는다.

 

그림1. 앙상블 모델

 

앙상블 모델에 사용되는 각 함수를 학습하기 위해서 다음과 같이 주어지는 regularized 목적함수를 최소화한다.

 

$\mathcal{L}(\phi) = \sum_{i} l(\hat{y_i}, y_i) + \sum_k \Omega (f_k)$ 

 

where $\Omega (f) = \gamma T + \frac{1}{2} \lambda \lVert w \rVert ^2$

 

여기에서 $l$은 미분가능한 convex 손실함수로, 예측치와 목표치의 차이를 측정한다.

 

* convex function: 다음을 만족하는 함수 $f$를 convex function이라고 한다.

    1. domain이 convex set

    2. $\forall x_1, x_2 \in X, \forall t \in [0, 1]$, $f(tx_1 + (1-t)x_2) \le tf(x_1) + (1-t)f(x_2)$

* convex set: $\forall x, y \in C$, $\forall t \in [0, 1]$, $(1-t)x + y \in C$ 일 때 $C$가 convex set이다.

 

두 번째 항인 $\Omega$는 모델의 복잡도가 지나치게 높아지지 않게 페널티를 준다.

추가적인 정규화 항은 최종적으로 학습되는 가중치를 smooth하게 만듬으로써 오버피팅을 방지한다.

 

직관적으로, 정규화된 목적함수는 단순하면서 결과치를 예측할 수 있는 함수를 선택하게 될 것이다.

 

2.2 Gradient Tree Boosting

2-1에서 본 앙상블 모델은 함수를 파라미터로 가지고 있기 때문에 유클리디언 공간에서의 전통적인 최적화 기법으로 최적화할 수 없다.

대신, 이 모델은 additive한 방식을 통해 학습된다.

 

$\hat{y_i}^{(t)}$를 $t$번째 반복(iteration)에서의 예측 결과의 $i$번째 항이라고 하자. 

그렇다면 $f_t$ 를 학습할 때 최소화해야 할 목적 함수는 다음과 같다.

 

$\mathcal{L}^{(t)} = \sum_{i=1}^n l(y_i, \hat{y}_i^{(t-1)} + f_t(x_i)) + \Omega(f_t)$

 

일반적으로 2차 근차를 이용해 목적 함수를 빠르게 최적화할 수 있다.

 

$\mathcal{L}^{(t)} \approx \sum_{i=1}^{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)$,

 

where $g_i = \partial_{\hat{y}^{(t-1)}} l(y_i, \hat{y}^{(t-1)})$, $h_i = \partial_{\hat{y}^{(t-1)}}^2 l(y_i, \hat{y}^{(t-1)})$

 

여기에서 $g_i$, $h_i$는 loss 함수에 대한 첫 번째와 두 번째 order gradient statistics 이다.

상수항인 $l(y_i, \hat{y}^{(t-1)})$을 없앰으로서 다음과 같이 쓸 수 있다.

 

$\begin{align}\tilde{\mathcal{L}} = \sum_{i=1}^n[g_i f_t(x_i) + \frac{1}{2}h_i f_t^2(x_i)] + \Omega(f_t)\end{align}$

 

각 리프 노드 $j$에 대해서  $I_j = \left\{ q(x_i) = j\right\}$와 같이 instance set을 정의한다.

그러면 $\Omega$를 풀어 쓰며 위 식을 다음과 같이 쓸 수 있다.

 

$\begin{align}\tilde{\mathcal{L}} &= \sum_{j=1}^T [(\sum_{i \in I_j}g_i)w_j + \frac{1}{2}(\sum_{i \in I_j}h_i)w_j^2] + \gamma T + \frac{1}{2}\lambda \sum_{j=1}^T w_j^2\\&= \sum_{j=1}^T [(\sum_{i \in \_j} g_i) w_j + \frac{1}{2}(\sum_{i \in I_j} h_i + \lambda)w_j^2] + \gamma T\end{align}$

 

그러면 어떤 고정된 구조 $q(x)$에 대해 리프 j에 대한 최적 가중치는 다음과 같이 주어진다

 

$w_j^* = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda }$

 

각각의 최적 가중치를 적용한 구조 $q$의 최적의 loss 값은 다음과 같다.

 

$\tilde{\mathcal{L}}(q) = -\frac{1}{2}\sum_{j=1}^T \frac{(\sum_{i \in I_j} g_i)^2}{\sum_{i \in I_j} h_i + \lambda} + \gamma T$

 

위 식은 트리 구조 $q$의 적절성을 검증하기 위해 사용될 수 있지만, 현실적으로 가능한 모든 트리 구조를 테스트해 보는 것은 불가능하다.

따라서 하나의 leaf 노드에서 출발해 가지를 더해가는 방법이 대신 사용된다.

 

$I_R$ 과 $I_L$이 리프 노드 $I$를 분할한 후의 오른쪽, 왼쪽 노드라고 할 때, 분할 후의 loss 감소량은 다음과 같다.

 

$\mathcal{L}_{split} = \frac{1}{2}[\frac{(\sum_{i \in I_L}g_i)^2}{\sum_{i \in I_L} h_i + \lambda } + \frac{(\sum_{i \in I_R}g_i)^2}{\sum_{i \in I_R}h_i + \lambda } - \frac{(\sum_{i \in I})^2}{\sum_{i \in I}h_i + \lambda}] - \gamma T$

 

2.3 Shrinkage and Column Splitting

Shrinkage:  Tree boosting의 각 단계 후에 새로 추가된 가중치들을 팩터 $\eta$를 통해 스케일링한다.

Column Splitting: Random forest에 사용, 오버피팅을 방지하기 위해 각 단계에서 컬럼을 sub-sampling하여 학습

 

3. Split Finding Algorithms

3.1 Basic Exact Greedy Algorithm

exact greedy algorithm: 모든 feature에 대해 모든 가능한 split을 탐색하는 방법

효율적으로 수행하기 위해 데이터 소팅이 필요함.

 

Input: $I$, instance set of current node Input: $d$, feature dimensions score $\leftarrow 0$ $G \leftarrow \sum_{i \in I} g_i$, $H \leftarrow \sum_{i \in I} h_i$ for $k=1$ to $m$:     $G_L \leftarrow 0$, $H_L \leftarrow 0$     for $j$ in sorted($I$, by $x_{jk}$):         $G_L \leftarrow G_L + g_j$, $H_L \leftarrow H_L + h_j$         $G_R \leftarrow G - G_L$, $H_R \leftarrow H - H_L$          score $\leftarrow \textit{max}(score, \frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{G}{H + \lambda})$  Output: split with maximum score

 

3.2 Approximate Algorithm

데이터가 메모리에 모두 적재되지 않을 경우 효율적으로 exact greedy algorithm을 수행할 수 없다.

이 경우 approximate 알고리즘이 필요하다.

for $k=1$ to $m$:     feature $k$에 대한 $l$ 분위수를 이용해 다음을  계산한다. $S_k = \left\{ s_{k1}, \ldots, s_{kl} \right\}$     $S_k$는 전역으로(전체 트리에 대해서) 상정될수도, 지역으로(split에 대해서) 상정될수도 있다 for $k=1$ to $m$:     $G_{kv} \leftarrow \sum_{j \in \left\{ j | s_{k, v} \ge x_{jk} > s_{k, v-1}\right\}} g_j$     $G_{kv} \leftarrow \sum_{j \in \left\{ j | s_{k, v} \ge x_{jk} > s_{k, v-1}\right\}} h_j$

 

3.3 Weighted Quantile Sketch

Approximate 알고리즘에서 가장 중요한 단계는 $S_k$를 정하는 것이다.

주로 $n$분위수를 이용해 데이터가 고루 분할되도록 한다.

 

멀티셋 $\mathcal{D_k} = \left\{ (x_{1k}, h_1), \ldots (x_{nk}, h_n)\right\}$이 $k$ 번째 feature 값과 second order gradient statistics을 나타낸다고 할 때, 다음과 같은 rank 함수를 정의할 수 있다.

 

$r_k: \mathbb{R} \rightarrow [0, +\infty)$

$r_k(z) = \frac{1}{\sum_{(x, h) \in \mathcal{D}_k} h} \sum_{(x, h) \in \mathcal{D}_k, x<z} h$

 

이 rank함수는 feature $k$의 값이 $z$보다 작은 데이터들의 비율을 의미한다.

여기서의 목표는 다음을 만족하는 후보 분할 $\left \{ s_{k1}, \ldots, s_{kl}\right \}$을 찾는 것이다.

 

$|r_k (s_{k, j}) - r_k(s_{k, j+1})| < \epsilon$

$s_{k1} = \textit{min}_i x_{ik}$

$s_{kl} = \textit{max}_i x_{ik}$

 

여기서 $\epsilon$은 수학에서 주로 쓰는 아주 작은 값을 가리키는 것이 아니라, approximation factor를 의미한다.

따라서 $l$ 이 대략 $\frac{1}{\epsilon}$정도가 될 것이라고 추측할 수 있다.

 

랭크 함수를 보면 각 데이터포인트의 가중치가 $h_i$로 매겨져 있는데, 그 이유는 다음과 같다.

 

2-2에서 등장했던 다음 식을 살펴보자.

 

$\begin{align}\tilde{\mathcal{L}} = \sum_{i=1}^n[g_i f_t(x_i) + \frac{1}{2}h_i f_t^2(x_i)] + \Omega(f_t)\end{align}$

  

위 식을 다음과 같이 묶을 수 있다.

 

$\tilde{\mathcal{L}} = \sum_{i=1}^n \frac{1}{2} h_i (f_t(x_i) - \frac{g_i}{h_i})^2 + \Omega(f_t) + constant$

 

즉, $g_i/h_i$라는 목표값으로 가지고 $h_i$를 가중치로 가지는 squared loss 함수와 같다.

 

3.4 Sparsity-aware Split Finding

현실 데이터셋에서 인풋 $x$가 sparse한 것은 흔하게 일어나는 일이다.

그 이유로는 1) missing value의 존재, 2) 0의 빈번한 출현, 3) one-hot 인코딩과 같은 feature engineering의 결과 를 들 수 있다.

알고리즘이 이러한 sparse 구조를 인식하도록 하기 위해서, 논문에서는 각 노드에 방향 기본값을 더한다.

만약 sparse matrix $x$에서 값이 존재하지 않을 경우, 데이터는 기본 방향으로 분류된다.

각 노드에 가능한 기본 방향은 두 개가 있으며, 최적의 기본 방향은 데이터로부터 학습된다.

 

Input: $l$, 현재 노드의 instance set Input: $I_k = \left\{ i \in I | x_{ik} \neq missing \right\}$ Input: $d$, feature 차원 gain $\leftarrow 0$ $G \leftarrow \sum_{i \in I}g_i$ $H \leftarrow \sum_{i \in I}h_i$ for $k=1$ to $m$:     $G_L \leftarrow 0$, $H_L \leftarrow 0$         for $j=1$ in sorted($I_k, \textit{ ascent order by } x_{jk}$):         $G_L \leftarrow G_L + g_i$, $H_L \leftarrow H_L + h_j$         $G_R \leftarrow G - G_L$, $H_R \leftarrow H - H_L$         score $\leftarrow $ max(score, $\frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{G^2}{H + \lambda}$)         $G_R \leftarrow 0$, $H_R \leftarrow 0$          for $j=1$ in sorted($I_k, \textit{ ascent order by } x_{jk}$):         $G_R \leftarrow G_R + g_i$, $H_R \leftarrow H_R + h_j$         $G_L \leftarrow G - G_R$, $H_L \leftarrow H - H_R$         score $\leftarrow $ max(score, $\frac{G_L^2}{H_L + \lambda} + \frac{G_R^2}{H_R + \lambda} - \frac{G^2}{H + \lambda}$) Output: gain을 최대화하는 방향으로 분할 및 기본 방향 설정