XGBoost: 확장 가능한 트리 부스팅

XGBoost: 확장 가능한 트리 부스팅

작은 결정 트리를 하나씩 더해 가는 '그래디언트 트리 부스팅'을, 정규화된 목적 함수 · 빈값 처리 · 가중 분위수 근사 · 캐시와 디스크까지 고려한 시스템 설계로 다시 만든 논문입니다. 표 형태 데이터(엑셀 · DB 테이블)에서는 지금도 가장 먼저 꺼내는 모델입니다.

들어가기 전에

이 해설은 아래 내용을 안다고 보고 씁니다. 처음이라면 먼저 읽고 오면 수식과 손계산을 훨씬 쉽게 따라올 수 있습니다.

• 앙상블: 배깅 · 랜덤 포레스트 · 그래디언트 부스팅 — 부트스트랩 · OOB · 랜덤 포레스트 · 그래디언트 부스팅을 손계산으로 익히는 앙상블 수업
• 스탠퍼드 CS229 머신러닝 강의 노트 — CS229 노트로 정규 방정식, 로지스틱 회귀 기울기 유도, 편향-분산을 손계산하는 수업
• 모델 평가와 과적합: 데이터 나누기 · 혼동 행렬 · 정규화 — 데이터 나누기 · 혼동 행렬 · 정밀도/재현율 · ROC-AUC · L2 정규화 · 조기 종료를 손계산으로

한눈에 보기

• 그래디언트 부스팅이 "앞 트리들이 틀린 만큼을 다음 트리가 메우는" 방식이라는 것을 수식 수준에서 이해합니다.
• 손실을 2차까지 근사하면 잎(leaf) 점수와 분기 이득이 $G$, $H$ 두 합만으로 닫힌 식이 된다는 것을 손으로 계산해 봅니다.
• 빈값(결측)을 따로 채우지 않고 "기본 방향"을 배워서 처리하는 방법을 압니다.
• 데이터가 메모리에 다 안 들어갈 때 후보 분기점을 고르는 가중 분위수 스케치의 아이디어를 압니다.
• 알고리즘만큼 시스템 설계(정렬된 열 블록 · 캐시 · 압축 · 샤딩)가 속도를 좌우한다는 것을 논문 수치로 확인합니다.

초록 (번역)

트리 부스팅은 매우 효과적이고 널리 쓰이는 머신러닝 방법입니다. 이 논문은 XGBoost라는 확장 가능한 엔드투엔드 트리 부스팅 시스템을 소개합니다. XGBoost는 데이터 과학자들이 여러 머신러닝 대회에서 최고 수준의 결과를 내는 데 널리 쓰고 있습니다. 저자들은 희소 데이터를 위한 새로운 희소성 인식(sparsity-aware) 알고리즘과, 근사 트리 학습을 위한 가중 분위수 스케치(weighted quantile sketch)를 제안합니다. 더 중요하게는, 확장 가능한 트리 부스팅 시스템을 만들기 위한 캐시 접근 패턴 · 데이터 압축 · 샤딩에 관한 통찰을 제시합니다. 이 통찰들을 결합해, XGBoost는 기존 시스템보다 훨씬 적은 자원으로 수십억 개가 넘는 예제까지 확장됩니다.

무엇을 풀었나

그래디언트 트리 부스팅(GBM · GBRT라고도 부름)은 이미 분류 · 랭킹 · 광고 클릭률 예측에서 좋은 성적을 내던 방법이었습니다. 문제는 규모였습니다.

1. 정렬 비용이 큽니다. 트리를 키울 때마다 "어느 특성의 어느 값에서 자를까"를 찾으려면 특성값 순서대로 데이터를 훑어야 합니다. 매번 정렬하면 느립니다.
2. 메모리에 다 안 들어가는 데이터. 모든 분기점을 다 보는 정확한 탐욕 알고리즘은 데이터가 메모리 밖에 있거나 여러 기계에 나뉘어 있으면 효율적으로 돌릴 수 없습니다.
3. 희소 데이터. 실제 데이터에는 빈값, 0이 많은 통계, 원-핫 인코딩으로 생긴 0이 가득합니다. 기존 구현은 대부분 밀집 데이터에 맞춰져 있었습니다.
4. 가중치가 있는 분위수. 근사 알고리즘은 후보 분기점을 분위수로 고르는데, 데이터마다 가중치가 다를 때 이론적 보장이 있는 방법이 없었습니다.

논문은 여기에 "정규화된 목적 함수"를 더해, 정확도와 확장성을 함께 잡는 시스템을 내놓습니다.

핵심 아이디어

1. 트리를 더해서 예측하기 (트리 앙상블)

직관: 여러 명의 감정사가 각자 점수를 매기고, 그 점수를 모두 더해 최종 가격을 정하는 것과 비슷합니다(해설용 비유). 각 감정사 = 회귀 트리 하나입니다.

단계:

1. 예제 $x_i$를 첫 번째 트리에 넣으면, 분기 규칙을 따라 어떤 잎에 도착하고 그 잎의 점수를 받습니다.
2. 두 번째, 세 번째 트리도 똑같이 점수를 줍니다.
3. $K$개 트리의 점수를 모두 더한 것이 예측값입니다.

2. 정규화된 목적 함수

직관: 맞히기만 하면 되는 게 아니라 "단순하게 맞혀라"는 벌점을 함께 줍니다. 잎이 많거나 잎 점수가 크면 벌점이 커집니다.

• $l$: 미분 가능한 볼록 손실(예측과 정답의 차이)
• $\gamma T$: 잎 하나 늘릴 때마다 내는 벌점
• $\tfrac12 \lambda \lVert w\rVert^2$: 잎 점수를 0 쪽으로 당기는 L2 벌점

왜 이렇게 했나: 논문은 비슷한 정규화를 쓰는 정규화 탐욕 숲(RGF)보다 목적 함수와 알고리즘이 단순해 병렬화가 쉽다고 설명합니다. 정규화 계수를 0으로 두면 전통적인 그래디언트 트리 부스팅과 같아집니다.

3. 한 그루씩 더하기와 2차 근사 — g, h

트리는 함수라서 보통의 경사 하강으로 한꺼번에 최적화할 수 없습니다. 그래서 한 단계에 트리 하나씩 더합니다. $t$번째 단계에서는 이미 만든 예측 $\hat{y}_i^{(t-1)}$에 새 트리 $f_t$를 더했을 때 손실이 가장 줄어드는 $f_t$를 찾습니다.

손실을 2차까지 테일러 전개하고 상수를 버리면 다음 식이 됩니다.

직관: 1차 미분만 쓰면 방향만 알고 보폭은 모릅니다. 2차 미분까지 쓰면 "이 정도 가면 바닥"이라는 보폭까지 알 수 있습니다(뉴턴 방법과 같은 생각). 이 2차 방법은 Friedman 등의 기존 연구에서 왔다고 논문이 밝힙니다.

숫자로 해 보기(해설용 예): 손실이 제곱 오차 $l = \tfrac12 (y - \hat{y})^2$이면 $g_i = \hat{y}_i - y_i$, $h_i = 1$입니다. 정답 $y=3$, 지금 예측 $\hat{y}=2.5$면 $g = -0.5$(예측을 올려야 함), $h = 1$입니다. (로지스틱 손실이면 $g = p - y$, $h = p(1-p)$로 계산됩니다 — 이 손실별 식은 해설용으로 덧붙인 표준 미분 결과입니다.)

4. 잎 점수와 구조 점수 — G와 H만 있으면 된다

잎 $j$에 떨어진 예제 집합을 $I_j$라 하고 $G_j = \sum_{i\in I_j} g_i$, $H_j = \sum_{i \in I_j} h_i$라 두면, 트리 구조가 고정됐을 때 가장 좋은 잎 점수와 그때의 목적 함수 값이 닫힌 식으로 나옵니다.

(논문은 $\sum_{i\in I_j} g_i$를 그대로 쓰고, 분기 알고리즘에서 $G$, $H$ 기호를 씁니다. 여기서는 읽기 쉽게 $G_j$, $H_j$로 묶었습니다.)

• 두 번째 식은 트리 구조 $q$의 품질 점수입니다. 결정 트리의 불순도(지니 · 엔트로피)와 같은 역할인데, 더 넓은 손실 함수에 대해 유도된 것이라고 논문은 설명합니다.

왜 $\lambda$가 분모에 있나: 예제가 적은 잎은 $H_j$가 작아서 점수가 크게 튈 수 있습니다. $\lambda$를 더하면 그런 잎의 점수가 0 쪽으로 줄어 과적합을 막습니다.

5. 분기 이득 — 어디서 자를까

가능한 모든 트리 구조를 다 볼 수는 없으므로, 잎 하나에서 시작해 가지를 하나씩 더하는 탐욕(greedy) 방식을 씁니다. 노드의 예제 집합 $I$를 왼쪽 $I_L$, 오른쪽 $I_R$로 나눌 때 손실이 줄어드는 양은 다음과 같습니다.

단계 (정확한 탐욕 알고리즘):

1. 노드 전체의 $G$, $H$를 구합니다.
2. 특성 하나를 골라 값 순서대로 예제를 훑으며 $G_L$, $H_L$을 누적합니다. $G_R = G - G_L$, $H_R = H - H_L$입니다.
3. 위치마다 이득을 계산해 최댓값을 기억합니다.
4. 모든 특성에 대해 반복하고, 이득이 가장 큰 분기를 고릅니다.

숫자로 해 보기(해설용 예): 예제 4개, 정답 $y = (3, 4, 1, 2)$, 첫 예측은 평균 $2.5$, 제곱 오차, $\lambda = 1$, $\gamma = 0$으로 둡니다.

• 노드 전체: $G = 0$, $H = 4$ → $\frac{0^2}{4+1} = 0$
• 분기 ① {A, B} / {C, D}: $G_L = -2, H_L = 2$, $G_R = 2, H_R = 2$ → 이득 $= \frac12\left[\frac{4}{3} + \frac{4}{3} - 0\right] \approx 1.33$
• 분기 ② {A} / {B, C, D}: $G_L = -0.5, H_L = 1$, $G_R = 0.5, H_R = 3$ → 이득 $= \frac12\left[\frac{0.25}{2} + \frac{0.25}{4} - 0\right] \approx 0.09$

분기 ①을 고릅니다. 잎 점수는 $w_L = -\frac{-2}{2+1} \approx 0.67$, $w_R \approx -0.67$입니다. 만약 $\lambda = 0$이면 $w_L = 1$로, 왼쪽 두 예제의 평균 잔차(0.5와 1.5의 평균)와 같습니다. $\lambda$가 잎 점수를 그만큼 줄여 준 것입니다.

6. 축소와 열 샘플링

• 축소(shrinkage): 새 트리의 잎 점수에 $\eta$를 곱해 더합니다. 경사 하강의 학습률처럼, 한 트리의 영향을 줄여 뒤의 트리가 고칠 여지를 남깁니다. (위 예에서 $\eta = 0.5$라 하면 A · B의 예측은 $2.5 + 0.5 \times 0.67 \approx 2.83$이 됩니다 — 해설용 숫자.)
• 열(특성) 샘플링: 트리마다 특성 일부만 씁니다. 랜덤 포레스트에서 빌려 온 기법으로, 논문은 사용자 피드백상 행 샘플링보다 과적합을 더 잘 막고, 병렬 알고리즘 계산도 빨라진다고 씁니다.

7. 근사 알고리즘과 가중 분위수 스케치

직관: 키 순서로 줄 선 1,000명 사이 999곳을 다 재 보는 대신, "10% · 20% · …" 지점 몇 곳만 후보로 놓고 재 보는 것입니다(해설용 비유).

단계 (근사 알고리즘):

1. 특성마다 분포의 백분위로 후보 분기점 $S_k = \{s_{k1}, \dots, s_{kl}\}$을 정합니다.
2. 연속값을 이 후보점으로 나눈 구간(버킷)에 넣고, 구간별로 $g$, $h$를 합칩니다.
3. 후보점에서만 분기 이득을 계산해 가장 좋은 것을 고릅니다.

후보를 정하는 시점에 따라 두 가지가 있습니다. 전역(global) 방식은 트리를 만들기 전에 한 번 정하고 모든 깊이에서 재사용합니다. 지역(local) 방식은 분기할 때마다 다시 정합니다. 전역은 후보 계산 횟수가 적지만 후보가 더 많이 필요하고, 지역은 분기마다 후보를 다듬어 깊은 트리에 더 맞을 수 있습니다.

왜 '가중' 분위수인가: 2차 근사 식을 다시 쓰면

꼴이 됩니다. 즉 라벨이 $-g_i/h_i$이고 가중치가 $h_i$인 가중 제곱 오차입니다. (원문 식은 $g_i/h_i$로 표기되어 있으나, 전개하면 부호가 위와 같아야 맞습니다. 핵심인 '가중치 = $h_i$'는 같습니다.) 그래서 후보점도 예제 개수가 아니라 $h$ 합 기준으로 고르게 나눠야 합니다.

• $r_k(z)$: 특성 $k$ 값이 $z$보다 작은 예제들의 $h$ 비율
• $\epsilon$: 근사 정도. 후보점이 대략 $1/\epsilon$개가 됩니다.

숫자로 해 보기(해설용 예): 특성값 $x = (1, 2, 3, 4)$, $h = (0.1, 0.1, 0.4, 0.4)$이면 $r(3) = \frac{0.1 + 0.1}{1.0} = 0.2$, $r(4) = 0.6$입니다. 개수로는 3이 가운데쯤이지만, $h$ 무게로는 3과 4 사이가 중간입니다. 손실이 많이 휘는(=$h$가 큰) 예제 쪽에 후보점을 촘촘히 두는 셈입니다.

기존 분위수 스케치(GK 등)는 가중치가 같은 데이터만 다뤘습니다. 논문은 병합(merge)과 가지치기(prune) 연산을 지원하고 각 연산의 정확도를 증명한 가중 분위수 스케치를 새로 제안하고, 증명은 부록에 둡니다.

8. 희소성 인식 분기 — 빈값의 기본 방향

직관: 설문 문항에 답이 비어 있으면, 그 사람을 "답이 빈 사람들은 보통 어느 쪽과 비슷했나"를 보고 한쪽으로 보내는 것입니다(해설용 비유).

단계:

1. 노드마다 기본 방향(default direction)을 둡니다. 값이 없으면 그 방향으로 보냅니다.
2. 분기점을 찾을 때 값이 있는 예제 $I_k$만 정렬해 훑습니다.
3. "빈값을 모두 오른쪽으로" 보낸 경우와 "모두 왼쪽으로" 보낸 경우를 각각 계산합니다($G$, $H$에서 값이 있는 쪽 합을 빼면 빈값 쪽 합이 나옵니다).
4. 이득이 더 큰 쪽을 그 노드의 기본 방향으로 배웁니다.

왜 이렇게 했나: 빈값 · 0 · 원-핫 인코딩을 따로따로 처리하지 않고 한 가지 방법으로 다룹니다. 그리고 계산량이 값이 있는 항목 수에 비례하게 됩니다. 논문은 이것이 모든 종류의 희소 패턴을 다루는 첫 통합 방법이라고 주장합니다.

9. 시스템 설계 — 열 블록 · 캐시 · 압축 · 샤딩

• 열 블록(column block): 트리 학습에서 가장 오래 걸리는 일은 정렬입니다. 데이터를 압축 열(CSC) 형식의 블록에 담고, 열마다 특성값 순서로 학습 전에 한 번만 정렬해 둡니다. 이후 분기 탐색은 정렬된 열을 한 번 훑는 일이 되고, 열마다 병렬로 처리할 수 있습니다.
• 복잡도: 트리 최대 깊이 $d$, 트리 수 $K$, 빈값이 아닌 항목 수 $\lVert x\rVert_0$일 때, 정확한 탐욕 알고리즘은 $O(Kd\lVert x\rVert_0 \log n)$에서 $O(Kd\lVert x\rVert_0 + \lVert x\rVert_0 \log n)$으로 줄어듭니다. 뒤의 $\log n$ 항은 한 번만 내는 전처리 비용입니다.
• 캐시 인식 접근: 정렬된 열 순서로 기울기 통계를 읽으면 메모리를 띄엄띄엄 읽게 되어 캐시 미스가 납니다. 스레드마다 버퍼를 두고 통계를 미리 가져와(prefetch) 작은 묶음으로 누적합니다. 근사 알고리즘에서는 블록 크기를 알맞게 고릅니다.
• 디스크 밖 계산(out-of-core): 메모리보다 큰 데이터를 블록으로 나눠 디스크에 두고, 별도 스레드가 미리 읽어 옵니다. 블록을 열 단위로 압축하고(행 번호는 블록 시작점 기준 16비트 오프셋), 여러 디스크에 번갈아 나눠 담아(샤딩) 읽기 처리량을 늘립니다.

왜 이렇게 했나: 기존 병렬 트리 연구는 주로 알고리즘 쪽을 다뤘습니다. 논문은 디스크 밖 계산과 캐시 인식 학습이라는, 시스템 쪽에서 덜 다뤄진 방향을 더해 적은 자원으로 큰 문제를 풀 수 있게 했다고 설명합니다.

전체 흐름

123456789101112flowchart TD
  A[학습 데이터] --> B[열 블록으로 저장 · 특성값 순서로 한 번 정렬]
  B --> C[현재 예측으로 예제별 g · h 계산]
  C --> D{분기 탐색 방식}
  D -->|정확| E[정렬된 열을 훑으며 G_L · H_L 누적]
  D -->|근사| F[가중 분위수로 후보점 · 구간별 g · h 합]
  E --> G[분기 이득 최대 지점 선택 · 빈값 기본 방향 학습]
  F --> G
  G --> H[잎 점수 w = -G / H+λ]
  H --> I[축소 η 곱해 예측에 더함]
  I --> C
  I --> J[트리 K개의 합 = 최종 예측]

결과

아래 수치는 모두 논문에 보고된 것입니다.

실제 대회에서의 쓰임 (서론)

• 2015년 Kaggle 블로그에 공개된 우승 솔루션 29개 중 17개가 XGBoost를 썼고, 그중 8개는 XGBoost만으로 학습했습니다. 두 번째로 많이 쓰인 심층 신경망은 11개였습니다.
• KDDCup 2015에서는 상위 10위 안의 모든 팀이 XGBoost를 썼습니다.

실험 데이터셋

공통 설정은 최대 깊이 8, 축소 0.1, 열 샘플링 없음(따로 밝힌 경우 제외)입니다.

단일 기계 분류 (Higgs-1M, 트리 500개, 정확한 탐욕 알고리즘)

XGBoost는 scikit-learn보다 10배 넘게 빨랐습니다. 이 데이터에서는 열 샘플링이 약간 더 나빴는데, 중요한 특성이 적어서일 수 있다고 논문은 해석합니다.

랭킹 학습 (Yahoo LTRC, 트리 500개)

여기서는 열 샘플링이 시간도 줄이고 성능도 조금 올렸습니다.

시스템 최적화 효과

• 희소성 인식 알고리즘: Allstate-10K에서 단순 구현보다 50배 넘게 빠름
• 캐시 인식 프리페치: 큰 데이터(1,000만 예제)에서 약 2배 빠름
• 근사 알고리즘 블록 크기: 블록당 $2^{16}$ 예제가 캐시와 병렬화의 균형점
• 블록 압축률: 시험한 대부분 데이터에서 약 26%~29%

디스크 밖 계산 (Criteo, AWS c3.8xlarge 1대: 32 vcore · 320GB SSD 2개 · 60GB RAM)

• 기본 방법은 2억 예제까지만 처리, 압축으로 3배, 디스크 2개 샤딩으로 다시 2배 빨라짐
• 최종 방법은 17억 예제를 기계 한 대에서 처리

분산 (EC2 m3.2xlarge 32대, Criteo)

• 반복당 Spark MLLib보다 10배 넘게, H2O 최적화 버전보다 2.2배 빠름
• 주어진 자원에서 17억 예제 전체로 매끄럽게 확장. 기계 4대만으로도 전체 데이터 처리

왜 중요한가 · 이후 영향

• 표 데이터의 기본 모델: 매출 예측 · 이탈 예측 · 사기 탐지처럼 행과 열로 된 업무 데이터에서는 지금도 딥러닝보다 그래디언트 부스팅 트리가 먼저 시도됩니다. 논문 서론의 대회 통계가 그 출발점을 보여 줍니다.
• "$g$, $h$만 주면 된다"는 설계: 손실의 1 · 2차 미분만 있으면 어떤 손실이든 같은 코드로 학습할 수 있습니다. 논문도 사용자 정의 목적 함수를 지원한다고 밝힙니다.
• 시스템 관점의 모범: 알고리즘이 같아도 메모리 배치 · 캐시 · 디스크 읽기를 어떻게 설계하느냐가 속도를 좌우한다는 점을 보여 줬습니다. 이후 GPU 위의 어텐션 계산을 메모리 계층에 맞게 다시 짠 플래시어텐션과 같은 결의 생각입니다(해설자의 비교).
• 생태계: 파이썬 · R · 줄리아에서 쓸 수 있고 scikit-learn과 어울리며, 하둡 · MPI · Spark · Flink 위에서 분산으로 돈다고 논문이 소개합니다.

한계 · 주의할 점

• 탐욕 분기: 한 단계씩 가장 좋은 분기를 고르므로 전체적으로 최적인 트리를 보장하지 않습니다.
• 근사의 정도는 사용자가 고릅니다. 후보점이 너무 적으면 정확도가 떨어질 수 있습니다. 논문 그림에서도 전역 방식은 후보가 충분해야 지역 방식만큼 정확했습니다.
• 열 샘플링 효과는 데이터마다 다릅니다. Higgs에서는 약간 나빠졌고 Yahoo LTRC에서는 좋아졌습니다.
• 비교 시점: 비교 대상(scikit-learn · R gbm · Spark MLLib · H2O · pGBRT)은 2016년 당시 버전입니다. 이후 다른 부스팅 라이브러리들도 히스토그램 기반 근사 등으로 크게 빨라졌으므로, 지금의 속도 순위를 이 논문 수치로 판단하면 안 됩니다.
• 원문 표기: 부록의 가중 분위수 스케치 증명은 이론 보장의 핵심이지만 이 글에서는 다루지 않았습니다. 또 2차 근사를 가중 제곱 오차로 다시 쓰는 식의 라벨 부호는 위에서 밝힌 대로 원문 표기와 다르게 적었습니다.

이어서 읽을 것

• 같은 '경사로 고치기'의 출발점: 오차 역전파로 표현 학습하기 — 신경망 쪽에서 기울기를 계산하는 방법
• 과적합을 막는 무작위 부분 사용: 드롭아웃 — 열 샘플링과 비교해 읽기 좋습니다
• 학습률 · 보폭 조절의 다른 접근: Adam
• 메모리 계층을 의식한 시스템 설계: 플래시어텐션

용어 정리

스스로 점검

1. XGBoost가 잎 점수를 계산할 때 필요한 값은 무엇인가?

   — 그 잎에 떨어진 예제들의 1차 기울기 합 $G$와 2차 기울기 합 $H$, 그리고 정규화 계수 $\lambda$입니다. $w^* = -G/(H+\lambda)$입니다.

2. 분기 이득 식의 맨 끝 $-\gamma$는 어떤 역할을 하나?

   — 잎이 하나 늘어나는 비용입니다. 나눠서 얻는 손실 감소가 $\gamma$보다 작으면 이득이 음수가 되어 나누지 않는 쪽이 낫게 됩니다.

3. 근사 알고리즘에서 후보 분기점을 왜 예제 개수가 아니라 $h$ 합으로 고르게 나누나?

   — 2차 근사 목적 함수가 $h_i$를 가중치로 하는 가중 제곱 오차와 같기 때문입니다. 손실에 더 큰 영향을 주는 예제 쪽에 후보를 촘촘히 두는 것이 맞습니다.

다음에 볼 것

이 글을 이해했다면 이어서 보면 좋은 항목입니다.

• 군집화: k-평균 · 가우시안 혼합 · EM 알고리즘 — 라벨 없는 데이터로 넘어가 k-평균 · GMM · EM · DBSCAN을 배웁니다
• 퍼셉트론: 뇌의 정보 저장과 조직에 관한 확률 모델 — 무작위로 연결된 켜짐/꺼짐 단위가 강화만으로 자극을 구별·일반화함을 확률로 분석한 신경망의 원점
• 신경망과 딥러닝 — 시그모이드 뉴런부터 역전파 네 방정식 · 교차 엔트로피까지 손계산으로 배우는 수업

출처

• 원문: arxiv.org/abs/1603.02754 (2016 · Tianqi Chen 외)