XGBoost : A Scalable Tree Boosting System

---

이번 포스팅에서는 Boosting 계의 정점이라고 할 수 있는 XGBoost를 소개한 논문인 "A Scalable Tree Boosting System"을 읽고 정리해보려고 한다.

 

- 목차 -

1. Introduction

2. Tree Boosting In A Nutshell

3. Split Finding Algorithms

4. System Design

5. Related Works

6. End to End Evaluation

7. Conclusion

---

   1. Introduction

머신 러닝은 많은 분야에서 중요한 도구로써 활약하고 있다. 그 이유는 2가지가 있다. 첫 번째는 복잡한 패턴을 학습하는 효율적인 모형의 사용, 두 번째는 대용량 데이터에 대해서도 학습이 가능하도록 하는 확장성이다.

 

머신러닝 방법론 중에서 Gradient Tree Boosting은 많은 적용 분야에서 빛을 발하고 있다. 

 

여기서는 확장 가능한 Tree Boosting 학습 시스템 XGBoost에 대해서 설명한다. XGBoost는 머신러닝과 데이터마이닝 챌린지에서 우수한 성적을 나타내었다. Kaggle에서는 29개 우승자가 사용했던 알고리즘 중에 17개가 XGBoost였다고 한다. 

 

XGBoost의 가장 중요한 성공요인은 확장성이라고 한다. 속도는 기존 모델보다 10배 빠르고 메모리 제약 상황에서도 학습이 가능하게끔 설계되었다고 한다. 이러한 확장성은 Sparse 데이터를 다룰 수 있는 알고리즘, Weight Quantile Sketch,  병렬 분산 처리로 인해 가능하다.

 

논문의 공헌은 다음과 같다.

 

a. 확장성이 매우 높은 Tree Boosting System을 구축하고 디자인한다.

b. 분리 기준을 정하기 위한 이론적으로 정당화된 Weighted Quantile Sketch를 제안한다.

c. 병렬적으로 나무를 학습하기 위한 Sparsity-aware 알고리즘을 소개한다.

d. Out-of-core 나무 학습을 위한 효율적인 Cache-aware Block Structure를 제안한다.

---

   2. Tree Boosting In A Nutshell

여기서는 Gradient Tree Boosting을 리뷰한다. 여기서 소개하는 이차 근사 방법은 Friedman이 소개했다고 한다. 사실 XGBoost에서 이차 근사를 처음으로 시도한 줄 알았다.

2.1 Regularized Learning Objedtive

데이터 $(x_i, y_i), i=1, \ldots, n$가 있다. 여기서 $x_i$는 $m$차원 실수 벡터이고 $y_i$는 실수이다. 나무 앙상블 모형은 예측을 위해 $K$개의 함수를 사용한다.

$$\hat{y}_i = \phi (x_i) = \sum_{k=1}^n f_{k}(x_i), \;\; f_k \in \mathcal{F}\tag{1}$$

여기서 $\mathcal{F} = \{f : f(x) = w_{q(x)} \} (q : \mathbb{R}^m\rightarrow T, w \in \mathbb{R}^T)$로써 회귀 나무 공간이다. 여기서 $q$는 입력 벡터를 회귀 나무의 끝마디 인덱스를 매핑하는 함수이다. 그리고 $T$는 $f_k$의 끝마디 총개수이다. 각 회귀 나무에는 끝마디의 연속형 점수를 가지고 있다. 이 점수를 가지고 입력 벡터에 대해서 출력값을 계산하게 된다. 함수(회귀 나무)들의 집합을 학습하기 위하여 다음과 같은 정규화 목적함수를 최소화한다.

$$L(\phi) = \sum_{i}l(\hat{y}_i, y_i)+\sum_k\Omega (f_k), \;\; \text{where}\;\; \Omega(f)=\gamma T+\frac{1}{2}\lambda \| w\|^2 \tag{2}$$

여기서 $l$은 미분 가능한 convex 손실 함수, $\Omega$는 모형의 복잡도를 통제하는 벌점항이다.

---

2.2 Gradient Tree Boosting

식 (2)는 최적화할 파라미터가 어떤 값이 아닌 함수 $f_k$이므로 전통적인 최적화 방법을 적용할 수 없다. 대신 다음과 같이 계속 더해지는 방향으로 학습하는 방법을 생각하게 된다.

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

 

이때 $l$을 직접 최적화하는 것보다 2차 근사를 최적화하는 것이 더 빠르고 쉽다. 물론 정확도를 잃게 된다.

$$L^{(t)} \approx \sum_{i=1}^n\left [l(y_i, \hat{y}_i^{(t-1)}) +g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i) \right] +\Omega(f_t)$$

여기서 $g_i = \partial l(y_i, \hat{y}_i^{(t-1)}) / \partial \hat{y}_i^{(t-1)}$, $h_i = \partial^2 l(y_i, \hat{y}_i^{(t-1)})/ \partial \left( \hat{y}_i^{(t-1)}\right )^2$

 

이때 위에서 $f_t$와 상관없는 항을 빼면 다음과 같다.

$$\tilde{L}^{(t)} = \sum_{i=1}^n\left [ g_if_t(x_i)+\frac{1}{2}h_if_t^2(x_i) \right ]+\Omega(f_t)\tag{3}$$

 

$I_j = {i | q(x_i) =j}$를 $j$번째 끝마디의 데이터라 하고 $\Omega$를 바꿔 쓰면 다음과 같다.

$$\tilde{L}^{(t)} = \sum_{j=1}^T\left [ \left ( \sum_{i\in I_j} g_i \right )w_j+\frac{1}{2} \left (\sum_{i\in I_j}h_i \right )w_j^2 \right ]+\gamma T\tag{4}$$

 

주어진 $q(x)$에 대하여 $j$번째 끝마디에서 최적 $w_j$는 다음과 같다.

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

 

그리고 이를 식 (4)에 대입하여 최적 근사 로스 값 $\tilde{L}^{(t)}$을 계산하면 다음과 같다.

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

 

만약 특정 끝마디 $I_j$에서 임의로 분리를 했을 경우 즉, $I_{jR},I_{jL}$로 분리한 경우 최적 근사 로스의 손실분은 다음과 같다.

$$\Delta \tilde{L} = \frac{1}{2}\left [ \frac{\left(\sum_{i\in I_{jL}} g_i \right)^2}{\sum_{i\in I_{jL}}h_i+\lambda }+\frac{\left(\sum_{i\in I_{jR}} g_i \right)^2}{\sum_{i\in I_{jR}}h_i+\lambda }-\frac{\left(\sum_{i\in I_{j}} g_i \right)^2}{\sum_{i\in I_{j}}h_i+\lambda } \right ]-\gamma\tag{7}$$

 

분리 기준을 정할 때 (7)을 최대로 하는 것으로 정하면 된다는 것이다.

---

2.3 Shrinkage and Column Subsampling

여기서는 앞에서 다룬 과적한 방지 방법 이외에도 다른 방법을 소개하는데 학습률을 이용한 것과 랜덤포레스트에서 사용하는 변수 랜덤 추출법을 이용하는 방법이 있다고 한다.

---

   3. Split Finding Algorithms

3.1 Basic Exact Greedy Algorithm

이는 모든 변수에 대하여 모든 분리 후보를 모두 탐색한 다음 최적의 분리 기준을 고르는 방법이다. 이 방법은 계산량이 너무 많다.

3.2 Approximate Algorithm

Exact Greedy Algorithm이 좋긴 하지만 계산적으로 비효율적이라서 근사적인 방법이 필요하다. 여기서는 분위수를 이용하여 분리기준을 선정한다.

3.3 Weighted Quantile Sketche

분위수를 이용한 근사적 분리 기준을 찾는 방법을 넘어 가중치가 부여된 분위수를 이용하는 방법이다.

3.4 Sparsity-aware Split Finding

설명 변수에 결측이 섞인 경우 이를 처리하는 방식이 나온다. 대략적으로 설명하면 결측치가 포함된 행들을 모두 왼쪽 끝마디에 넣어 손실 감소분을 계산한다. 이번에는 오른쪽 끝마디에 넣고 손실 감소분을 계산한다. 이렇게 두 개의 손실 감소분 중에서 최대로 하는 마디에 결측치를 모두 옮기는 방식이다.

---

   4. System Design

4.1 Column Block for Parallel Learning

칼럼 단위로 병렬 처리를 통해 분리 기준을 찾아낸다는 것이다.

4.2 Cache-aware Access

캐시를 잘 활용하여 컴퓨터 자원을 효율적으로 사용하자는 거 같다.

4.3 Blocks for Out-of-core Computation

메인 메모리, 캐시, CPU 말고 하드 디스크도 계산에 활용될 수 있게끔하는 방법을 소개하는 거 같다.

---

   5. Related Works

Gradient Boosting이나 정규화된(Regularized) 앙상블 모형 중 하나인 Greedy Forest, 그리고 칼럼을 랜덤 샘플링하는 랜덤포레스트, Sparsity-aware 학습을 적용한 선형 모형 등 좋은 것들을 개별적으로 적용한 분야는 많지만 이들을 통합한 것은 XGBoost가 처음이라고 한다. 여기에 더해 Out-of-core Computation과 Cache-aware 학습까지 적용했다. 또한 논문 저자가 알기로는 분리기준을 찾는 데 있어서 Weighted Quantile Sketch를 적용한 것은 이 논문이 처음이라고 한다.

---

   6. End to End Evaluation

6.1 System Implementation

XGBoost를 사용할 수 있는 오픈 소스를 만들었다고 한다. 여기에는 가중치 분류 문제(weighted classification), 순위 목적 함수(rank objective function) 그리고 사용자 정의 목적 함수도 사용할 수 있다고 한다. 

6.2 Dataset and Setup

여기서는 실험을 위해 4개의 데이터셋을 사용했다. 나무의 깊이는 최대 8, 축소 파라미터(학습률)는 0.1을 사용했다고 하며 칼럼 랜덤 샘플링은 명시하지 않으면 안 한 거라고 한다.

6.3 Classification

여기서는 분류 문제에서 자기네들 XGBoost가 제일 좋았다고 한다. 성능도 좋고 속도도 빠르고. 이때 칼럼 랜덤 샘플링을 추가하니 속도는 조금 빨라졌지만 정확도는 조금 안 좋아졌다고 한다. 그 이유는 칼럼 랜덤 샘플링으로 인해 중요한 변수가 빠질 수 있어서 그런 듯하다고 얘기하고 있다.

6.4 Learning to Rank

이번엔 랭크를 매기는 문제에서 pGBRT 알고리즘과 비교해보았다고 한다. pGBRT가 속도는 가장 느렸지만 성능은 XGBoost보다 조금 더 좋았다. 이때 XGBoost에 칼럼 랜덤 샘플링을 추가하니 속도는 줄어들고 정확도는 오히려 증가했다고 한다. 아마도 과적합 방지 효과가 컸던 거 같다. 

6.5 Out-of-core Experimentation

Out-of-core에 효과를 검증하는 실험을 했다고 한다. 

6.6 Distributed Experiment

XGBoost의 대용량 분산처리를 제한된 자원에서 모두 처리할 수 있는지 확인해보는 실험 같다.

---

   7. Conclusion

이 논문에서는 결측치를 다루기 위한 Sparsity-aware 알고리즘을 제안했다. (비록 근사적인 방법이지만) 분리 기준을 좀 더 빠르게 찾기 위한 Weighted Quantile Sketch를 사용했다. 논문 저자의 경험으로 Cache-access 패턴, 데이터 압축, 샤딩(Sharding)이 확장 가능한 Tree Boosting을 만들기 위해 필수라고 생각한다고 한다. 여기서 얻은 교훈은 다른 머신러닝 시스템에 적용할 수 있다고 한다. 이러한 점으로 볼 때 XGBoost가 최소의 자원으로 현실에 존재하는 문제를 풀 수 있다고 주장하며 논문은 끝이 난다.

 

---