AdaBoost에서 XGBoost까지 — Boosting은 하나의 수식이다

지수손실 최소화라는 단일 프레임으로 AdaBoost의 가중치 공식부터 XGBoost의 closed-form leaf 값, LightGBM의 histogram 최적화, margin theory의 과적합 저항성까지 추적한다.

AdaBoost의 가중치 공식 $\alpha_t = \frac{1}{2}\log\frac{1-\epsilon_t}{\epsilon_t}$ 는 왜 하필 그 형태인가? XGBoost의 leaf 값 $w^* = -G/(H+\lambda)$ 는 어디서 왔나? 이 공식들은 서로 다른 알고리즘의 독립적 발명처럼 보이지만, 모두 하나의 구조에서 나온다. 볼록 손실 + 그리디 최적화. 이 다섯 챕터를 관통하는 통일 주제를 추적한다.

공식들의 공통 기원

Friedman, Hastie, Tibshirani (2000)는 AdaBoost를 재해석했다. 알고리즘이 아니라 목적함수 + 최적화로.

손실 $L(y, f) = e^{-yf}$ 를 Forward Stagewise Additive Modeling(FSAM)으로 최소화한다고 하자. 매 단계 새 learner $h_t$ 를 추가해 $\sum_i e^{-y_i F_t(x_i)}$ 를 줄인다. 이 과정에서 $\alpha_t$ 와 $w_i^{(t+1)}$ 이 자동으로 유도된다.

명제 1 · AdaBoost의 최적 α

지수손실 FSAM에서 $h_t$ 고정 시 손실을 최소화하는 $\alpha_t^*$ :

$\alpha_t^* = \frac{1}{2}\log\frac{1-\epsilon_t}{\epsilon_t}$

여기서 $\epsilon_t = \sum_i w_i^{(t)} \mathbb{1}[y_i \neq h_t(x_i)]$ 는 weighted error rate다.

▷ 증명

$h$ 가 $\{-1, +1\}$ -valued이므로 단계별 손실은 $e^{-\alpha}(W - W_e) + e^{+\alpha} W_e$ . $\frac{d}{d\alpha} = 0$ 으로 놓으면 $e^{2\alpha} = (W - W_e)/W_e$ . 따라서 $\alpha = \frac{1}{2}\log\frac{W - W_e}{W_e} = \frac{1}{2}\log\frac{1-\epsilon}{\epsilon}$ . $\square$

∎

가중치 업데이트 $w_i^{(t+1)} \propto w_i^{(t)} \exp(\alpha_t \mathbb{1}[y_i \neq h_t(x_i)])$ 역시 같은 유도의 귀결이다. “틀린 샘플에 집중”이라는 직관이 사실 지수함수의 분리 성질에서 나온다.

함수공간에서의 경사하강법

AdaBoost를 일반화한 Gradient Boosting (Friedman 2001)은 이 프레임을 임의의 미분 가능 손실로 확장한다. 핵심 관찰은 단순하다 — 유한차원 경사하강법 $\theta \leftarrow \theta - \eta \nabla L$ 을 함수공간으로 옮기면 무엇이 되는가.

각 훈련 점 $x_i$ 에서 $-\partial L(y_i, F(x_i))/\partial F(x_i)$ 를 계산하면 “이 점에서 $F$ 가 어느 방향으로 바뀌어야 하는가”를 알 수 있다. 이것이 pseudo-residual $r_{it}$ 다. 이 값들에 tree를 fit하면 훈련 점 밖의 $x$ 로도 일반화되는 gradient 근사를 얻는다.

$F_t = F_{t-1} + \eta h_t, \quad h_t \approx -\nabla_f L(y, F_{t-1})$

MSE에서는 $r_i = y_i - F_{t-1}(x_i)$ — 잔차. 지수손실에서는 $r_i = y_i w_i^{(t)}$ — AdaBoost의 가중 라벨. AdaBoost는 GBM의 지수손실 특수 사례다.

✎ 손실별 pseudo-residual

손실	pseudo-residual	특성
MSE	$y - F$	잔차
MAE	$\text{sign}(y - F)$	부호만
Exponential	$y \cdot e^{-yF}$ (AdaBoost 가중치)	noise 민감
Binomial deviance	$2y / (1 + e^{2yF})$	logistic 형태

Newton 한 스텝 — XGBoost의 기여

GBM이 1차 Taylor 근사라면, XGBoost (Chen & Guestrin 2016)는 2차까지 사용한다.

$L(y_i, F_{t-1} + f_t) \approx L(y_i, F_{t-1}) + g_i f_t + \frac{1}{2} h_i f_t^2$

여기서 $g_i = \partial L / \partial f$ , $h_i = \partial^2 L / \partial f^2$ . 정규화항 $\gamma T + \frac{1}{2}\lambda \sum_j w_j^2$ 을 더하고 leaf별로 최소화하면 closed-form이 나온다.

명제 2 · XGBoost leaf 값

Tree 구조 고정 시 leaf $j$ 의 최적 값:

$w_j^* = -\frac{G_j}{H_j + \lambda}, \quad G_j = \sum_{i \in I_j} g_i,\; H_j = \sum_{i \in I_j} h_i$

▷ 증명

Leaf $j$ 에 대한 손실: $G_j w_j + \frac{1}{2}(H_j + \lambda) w_j^2$ . $\partial/\partial w_j = 0$ 으로 놓으면 $w_j = -G_j/(H_j + \lambda)$ . $H_j + \lambda > 0$ 이므로 convex, 유일 최소. $\square$

∎

이는 tree 형식의 Newton-Raphson 한 스텝이다. 단일 샘플의 Newton step $-g/h$ 를 leaf 내 샘플들에 대해 가중 평균한 것이 $-G/H$ 이고, $\lambda$ 는 numerical damping이다. Logistic loss를 넣으면 $w_j^* = \sum(y_i - p_i) / (\sum p_i(1-p_i) + \lambda)$ — Ch2의 IRLS와 정확히 같은 구조다.

Split 여부는 Gain 공식으로 결정된다:

$\text{Gain} = \frac{1}{2}\left[\frac{G_L^2}{H_L+\lambda} + \frac{G_R^2}{H_R+\lambda} - \frac{(G_L+G_R)^2}{H_L+H_R+\lambda}\right] - \gamma$

$\gamma > 0$ 이면 이득이 충분하지 않은 split은 하지 않는다 — 수식 안에 regularization이 내재된다.

공학적 가속 — LightGBM의 세 가지 결정

LightGBM (Ke et al. 2017)은 알고리즘을 바꾸지 않는다. 같은 수식을 더 빠르게 계산하는 세 가지 공학적 결정을 내린다.

Histogram binning: 연속 feature를 $B$ 개 bucket으로 이산화한다. Split 후보가 $n-1$ 개에서 $B-1$ 개로 줄어든다. $n = 10^7$ , $B = 255$ 에서 약 40,000배 차이. 정확도 손실은 bin 수가 충분하면 무시할 수준이다.

GOSS (Gradient-based One-Side Sampling): gradient 큰 샘플 — 아직 잘 예측 못 한 샘플 — 은 전부 보존하고, gradient 작은 샘플은 $b$ %만 subsample한다. 작은 gradient 샘플의 기여분을 $(1-a)/b$ 로 scale up해 unbiased estimator를 유지한다. 기본값 $a=0.2, b=0.1$ 에서 30%만 사용하면서 거의 같은 정확도를 낸다.

EFB (Exclusive Feature Bundling): sparse feature들 중 동시에 비영인 샘플이 드문 pair를 묶는다. 최적 bundling은 그래프 컬러링의 NP-hard 문제로 환원되지만, greedy heuristic으로 충분히 좋은 근사를 얻는다.

과적합 저항성 — Margin Theory

Schapire et al. (1998)는 반직관적 현상을 보고했다. AdaBoost가 train error 0에 도달한 이후에도 boosting을 계속하면 test error가 계속 감소한다. VC bound로는 설명이 안 된다 — $T$ 증가 → VC dim 증가 → bound 커짐.

답은 margin distribution에 있다. normalized margin $m(x, y) = y \cdot F(x) / \sum_t |\alpha_t|$ 가 $T$ 증가에 따라 우측으로 이동한다. 작은 margin 샘플의 비율이 감소한다.

$\Pr_{\text{test}}[m < 0] \leq \Pr_{\text{train}}[m < \theta] + O\!\left(\sqrt{\frac{d}{n\theta^2}}\right)$

이 bound에는 $T$ 가 없다. $T$ 를 늘려도 complexity 항이 커지지 않는다. 단지 첫 항 $\Pr_{\text{train}}[m < \theta]$ 이 $T$ 와 함께 감소하면서 전체 bound가 tight해진다.

⚠ 트레이드오프: noise와 margin의 충돌

Label noise가 많은 데이터에서 AdaBoost는 위험하다. noise 샘플의 gradient가 큰 채로 유지되면 weight가 폭발하고 margin theory의 보장이 깨진다. 이 경우 지수손실 대신 logistic loss (GBM의 log_loss)를 사용하면 noise 샘플의 gradient가 cap되어 robust해진다. noise rate 30%에서 AdaBoost test accuracy 68% vs GBM(log loss) 71%의 차이가 이 메커니즘을 보여준다.

또한 $T \to \infty$ 극한에서 max-margin solution으로 수렴하는 self-regularization 현상은 clean data에서만 작동한다. 이 특성은 NN의 double descent, SGD implicit bias와 같은 정신이지만, AdaBoost가 이를 이론적으로 가장 먼저 분석한 사례다.

정리

AdaBoost의 $\alpha$ 공식과 가중치 업데이트는 “직관”이 아니라 지수손실 FSAM의 closed-form 최적화 결과다.
Gradient Boosting은 이 프레임을 임의의 미분 가능 손실로 확장한다. AdaBoost는 그 특수 사례다.
XGBoost는 2차 Taylor 근사로 tree를 Newton step으로 만들고, $\gamma$ 와 $\lambda$ 를 수식 안에 내재시킨다.
LightGBM은 같은 수식을 histogram, GOSS, EFB로 대규모 데이터에서 실용적으로 만든다.
Margin theory는 “train error 0 이후에도 test error 감소”를 $T$ 독립 bound로 설명한다. 이 통찰은 modern NN의 over-parameterization 이론으로 직