[XGBoost: A Scalable Tree Boosting System] 논문 정리

이앙앙·2025년 2월 10일

ML XGBoost

논문 정리

목록 보기

1/23

📝 XGBoost: A Scalable Tree Boosting System

Abstract

tree boosting은 머신러닝에서 효율적이고 널리 쓰임
XGBoost라는 최첨단 결과를 이끌어내기 위해 많은 데이터 사이언티스트들이 사용함
XGBoost는 기존 시스템보다 휠씬 적은 리소스를 사용 가능, 확장성이 좋음

1 Introduction

머신러닝과 데이터 기반 접근법은 많은 분야에서 매우 중요
확장성은 XGBoost의 성공적인 핵심 요소
XGBoost의 확장성은 여러 중요한 시스템과 알고리즘 최적화 덕분

2 TREE BOOSTING

CatBoost는 gradient boosting을 구현한 라이브러리로, 기본 예측기로 이진 의사결정 나무를 사용
특정 공간을 재귀적으로 분할하여 최적의 예측값을 생성
CatBoost는 회귀 및 분류 문제에서 높은 성능을 발휘

2.1 Regularized Learning Objective

예제 $n$ 개와 특징 $m$ 개를 가진 데이터셋 $D = \{ (x_i, y_i) \mid |D| = n, \, x_i \in \mathbb{R}^m, \, y_i \in \mathbb{R} \}$ 에서 트리 앙상블 모델은 $K$ 개의 덧셈 함수들을 사용하여 출력을 예측한다.

\hat{y}_i = \phi(x_i) = \sum_{k=1}^{K} f_k(x_i), \; f_k \in F \quad (1)

여기서 $F = \{ f(x) = w q(x) \mid q : \mathbb{R}^m \to T, \; w \in \mathbb{R}^T \}$ 는 회귀 트리 공간(CART로도 알려져 있음)을 나타낸다. 여기서 $q$ 는 예제를 해당 잎 노드로 매핑하는 각 트리의 구조를 나타낸다. $T$ 는 트리의 잎 노드 수다. 각 $f_k$ 는 독립적인 트리 구조 $q$ 와 잎 가중치 $w$ 에 해당한다. 결정 트리와 달리 각 회귀 트리는 잎마다 연속적인 점수를 포함하며, 잎 $i$ 의 점수를 $w_i$ 로 표현한다. 주어진 예제에 대해, 트리의 결정 규칙( $q$ 로 제공됨)을 사용하여 잎에 분류하고, 해당 잎의 점수( $w$ )를 합산하여 최종 예측값을 계산한다.

모델에서 사용하는 함수 집합을 학습하기 위해 아래의 정규화된 목적을 최소화한다.

L(\phi) = \sum_{i} l(\hat{y}_i, y_i) + \sum_{k} \Omega(f_k) \quad (2)

\Omega(f) = \gamma T + \frac{1}{2} \lambda \|w\|^2

여기서 $l$ 은 예측값 $\hat{y}_i$ 와 목표값 $y_i$ 간 차이를 측정하는 미분 가능한 볼록 손실 함수다. 두 번째 항 Ω는 모델의 복잡도(즉, 회귀 트리 함수들)를 페널티한다. 추가 정규화 항은 최종 학습된 가중치를 부드럽게 하여 과적합을 방지하는 데 도움이 된다. 직관적으로 정규화된 목적은 단순하고 예측 가능한 함수를 사용하는 모델을 선택하려는 경향이 있다. 비슷한 정규화 기법이 Regularized Greedy Forest(RGF) [25] 모델에 사용되었다. 우리의 목적 함수와 해당 학습 알고리즘은 RGF보다 더 단순하며 병렬화하기 쉽다. 정규화 매개변수를 0으로 설정하면 목적 함수는 기존의 그래디언트 트리 부스팅으로 돌아간다.

2.2 Gradient Tree Boosting

식 (2)의 트리 앙상블 모델은 함수들을 매개변수로 포함하고 있어, 유클리드 공간에서 전통적인 최적화 방법을 사용할 수 없다. 대신, 이 모델은 덧셈 방식으로 훈련된다.

정식으로는, $t-$ 번째 반복에서 $i-$ 번째 인스턴스의 예측값을 $\hat{y}_i^{(t)}$ 라 할 때, 다음 목적을 최소화하기 위해 $f_t$ 를 추가해야 한다.

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

이는 식 (2)에 따라 모델을 가장 많이 개선하는 $f_t$ 를 탐욕적으로 추가함을 의미한다. 일반적인 설정에서 목적을 빠르게 최적화하기 위해 2차 근사를 사용할 수 있다.

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

여기서 $g_i = \partial_{\hat{y}_i^{(t-1)}} l(y_i, \hat{y}_i^{(t-1)})$ 와 $h_i = \partial^2_{\hat{y}_i^{(t-1)}} l(y_i, \hat{y}_i^{(t-1)})$ 는 손실 함수에 대한 1차 및 2차 그래디언트 통계다. 상수 항들을 제거하면 $t-$ 번째 단계에서 다음과 같이 단순화된 목적을 얻을 수 있다.

\tilde{L}^{(t)} = \sum_{i=1}^{n} \left[ g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \Omega(f_t). \quad (3)

우리는 식 (3)을 $Ω$ 를 확장하여 다음과 같이 다시 작성할 수 있다.

\tilde{L}^{(t)} = \sum_{i=1}^{n} \left[ g_i f_t(x_i) + \frac{1}{2} h_i f_t^2(x_i) \right] + \gamma T + \frac{1}{2} \lambda \sum_{j=1}^{T} w_j^2

이를 다시 다음과 같이 표현할 수 있다.

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

고정된 구조 $q(x)$ 에 대해 잎 $j$ 의 최적 가중치 $w_j^*$ 를 다음과 같이 계산할 수 있다.

w_j^* = -\frac{\sum_{i \in I_j} g_i}{\sum_{i \in I_j} h_i + \lambda} \quad (5)

그리고 다음과 같이 해당 최적값을 계산할 수 있다.

\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 \quad (6)

식 (6)은 트리 구조 $q$ 의 품질을 측정하기 위한 스코어링 함수로 사용할 수 있다. 이 스코어는 의사결정 트리의 불순도 점수와 유사하지만, 더 넓은 범위의 목적 함수에 대해 도출된 값이다.
보통 가능한 모든 트리 구조 $q$ 를 열거하는 것은 불가능하지만, 하나의 잎에서 시작하여 트리에 분기를 점진적으로 추가하는 탐욕적 알고리즘이 사용된다.
왼쪽과 오른쪽 노드의 인스턴스 집합을 각각 $I_L$ 과 $I_R$ 라고 가정하고, $I = I_L \cup I_R$ 라고 할 때, 분할 후 손실 감소는 다음과 같이 정의된다.

L_{\text{split}} = \frac{1}{2} \left[ \frac{\left( \sum_{i \in I_L} g_i \right)^2}{\sum_{i \in I_L} h_i + \lambda} + \frac{\left( \sum_{i \in I_R} g_i \right)^2}{\sum_{i \in I_R} h_i + \lambda} - \frac{\left( \sum_{i \in I} g_i \right)^2}{\sum_{i \in I} h_i + \lambda} \right] - \gamma \quad (7)

2.3 Shrinkage and Column Subsampling

2.1절에서 언급된 정규화된 목적 외에도, 과적합을 방지하기 위해 추가적인 두 가지 기법이 사용된다.

첫 번째 기법은 Friedman이 도입한 Shrinkage(수축)이다. Shrinkage는 트리 부스팅의 각 단계 후에 새로 추가된 가중치를 계수 $η$ 로 조정한다. 이는 확률적 최적화에서의 학습률과 비슷한 역할을 하며, 개별 트리의 영향을 줄이고, 향후 추가될 트리가 모델을 개선할 여지를 남긴다.

두 번째 기법은 컬럼 샘플링이다. 이 기법은 RandomForest에서 사용된 방법과 유사하다.

3 SPLIT FINDING ALGORITHMS

3.1 Basic Exact Greedy Algorithm

정확한 탐욕적 알고리즘은 모든 가능한 분할을 탐색하며, 높은 계산 비용이 필요하지만 가장 정확한 분할을 제공한다.

데이터를 정렬하고 그래디언트를 누적해 효율성을 높인다.

3.2 Approximate Algorithm

사적 알고리즘의 두 가지 변형:
- 글로벌(Global) 방식: 트리 생성 초기 단계에서 모든 후보 분할 지점을 제안하고, 트리의 모든 레벨에서 동일한 후보를 사용한다.
  - 제안 단계가 로컬 방식보다 적지만, 각 분할 후 후보가 세밀화되지 않기 때문에 더 많은 후보 지점이 필요하다.
- 로컬(Local) 방식: 각 분할 후에 후보를 재설정한다.
  - 각 분할 후 후보 지점을 세밀화하기 때문에 더 깊은 트리에 적합할 수 있다.
Higgs 보손 데이터셋에서 알고리즘 비교:
- 그림 3은 Higgs 보손 데이터셋에서 다양한 알고리즘의 성능을 비교한 결과를 보여준다.
  결과적으로 로컬 방식이 더 적은 후보 지점을 필요로 하지만, 충분한 후보 지점이 주어질 경우 글로벌 방식도 로컬 방식만큼 정확해질 수 있음을 보여준다.
근사적 알고리즘의 특징:
- 분산된 트리 학습을 위한 대부분의 기존 근사적 알고리즘도 이 프레임워크를 따른다.
  그래디언트 통계의 근사적 히스토그램을 직접 구성하거나, 백분위수 대신 다른 버킷(bin) 전략을 사용할 수 있다.
  백분위수 전략은 분산 처리 가능성과 재계산 가능성이라는 장점이 있어 널리 사용된다.

3.3 Weighted Quantile Sketch

가중된 백분위수 스케치는 특징 값의 분포를 기반으로 후보 분할 지점을 제안하며, 대규모 데이터에서도 효율적이고 정확하게 작동한다.

3.4 Sparsity-aware Split Finding

실제 문제에서는 입력 $x$ 가 희소(sparse)한 경우가 매우 흔하다. 희소성이 발생하는 이유는 다음과 같다.

데이터에서 누락된 값(missing values)이 존재.
통계에서 빈번한 $0$ 항목(zero entries)이 발생.
원-핫 인코딩과 같은 특징 엔지니어링의 결과.
이 알고리즘은 데이터의 희소성 패턴을 인지하도록 설계됨.

이를 위해 각 트리 노드에 기본 방향을 추가하는 방식을 제안한다.

이앙앙

다음 포스트