틀린 것만 다시 배우는 부스팅, AdaBoost와 Gradient Boosting

배깅(Bagging)은 트리 수백 그루를 서로 모르는 채로 학습시킨 뒤 투표로 합친다. 어느 트리도 다른 트리가 무엇을 틀렸는지 모른다. 그래서 트리마다 제각각인 들쭉날쭉함은 평균에 깎여 사라지지만, 모든 트리가 공통으로 못 맞추는 부분은 그대로 남는다. 분산은 줄고 편향은 안 준다.

부스팅(Boosting)은 반대로 간다. 트리를 하나씩 순서대로 만들되, 새 트리는 앞선 모델이 남긴 오차만 겨냥한다. 혼자서는 찍기보다 조금 나은 수준인 약한 학습기(Weak Learner)라도 앞사람의 실수를 이어받으며 쌓이면 편향(Bias)이 낮은 모델이 된다.

배깅과 부스팅은 목표가 다르다

순서의 차이는 학습 시간에 그대로 나타난다. 배깅은 트리 100그루를 코어 여러 개에 흩어 동시에 학습시킬 수 있지만, 부스팅은 앞 트리의 예측이 있어야 다음 트리의 타겟이 정해지므로 트리 사이를 병렬화할 방법이 없다. 같은 100그루라도 부스팅 쪽이 몇 배 오래 걸린다.

노이즈가 많은 데이터, 학습을 병렬로 돌려야 하는 상황이면 배깅이 안전하다. 데이터가 비교적 깨끗하고 마지막 몇 퍼센트를 짜내야 하면 부스팅이다.

AdaBoost

1995년 Freund와 Schapire가 제안한, 이론적 보장을 갖춘 첫 부스팅 알고리즘이다. “앞 모델이 틀린 것을 다음 모델이 맡는다”를 샘플 가중치로 구현한다. 오분류된 샘플의 가중치를 키워두면, 다음 분류기는 그 샘플을 틀렸을 때 손해가 크므로 자연히 거기에 집중한다.

기본 약한 학습기는 깊이 1짜리 결정 트리인 결정 그루터기(Decision Stump)다. 특성 하나와 임계값 하나로 “특성 A가 $\theta$ 이상이면 클래스 1”이라는 규칙만 만든다.

절차는 다섯 줄이다.

1. 모든 샘플에 같은 가중치 $w_i = 1/N$ 을 준다.
2. 그 가중치로 약한 분류기 $h_t$ 를 학습한다.
3. 가중 오류율 $\epsilon_t = \sum_i w_i \mathbf{1}[h_t(x_i) \neq y_i]$ 를 잰다.
4. 분류기 가중치 $\alpha_t$ 를 정하고, 오분류한 샘플은 $w_i$ 를 $e^{\alpha_t}$ 배로 키우고 맞춘 샘플은 $e^{-\alpha_t}$ 배로 줄인 뒤 합이 1이 되게 정규화한다.
5. 2번으로 돌아간다.

최종 예측은 분류기들의 가중 투표다.

$H(x) = \operatorname{sign}\left(\sum_{t=1}^{T} \alpha_t h_t(x)\right), \qquad \alpha_t = \frac{1}{2}\ln\frac{1-\epsilon_t}{\epsilon_t}$

$\alpha_t$ 하나가 두 가지 일을 동시에 한다. 잘 맞춘 분류기일수록 최종 투표에서 큰 지분을 갖고, 같은 값이 그 분류기가 틀린 샘플의 가중치를 밀어 올리는 폭도 정한다.

오류율이 0.5를 넘으면 $\alpha_t$ 가 음수가 되어, 수식상으로는 그 분류기의 예측을 뒤집어 쓰는 것과 같아진다. 다만 실제 구현은 이런 분류기를 만나면 그 라운드에서 버리거나 부스팅을 멈추는 쪽을 택한다.

샘플 20개로 두 라운드만 돌려보면 가중치가 이렇게 움직인다.

처음에는 스무 개가 모두 1/20이다. 첫 분류기가 다섯 개를 틀리면 $\epsilon_1 = 0.25$, $\alpha_1 = 0.55$ 이고, 정규화까지 마치면 틀린 다섯 개는 0.1로 오르고 나머지 열다섯 개는 0.033으로 내려간다. 두 번째 분류기가 그중 4번과 17번을 또 틀리면 $\epsilon_2 = 0.2$, $\alpha_2 = 0.69$ 라서 두 샘플의 가중치가 0.25까지 뛴다. 두 라운드 만에 출발점의 다섯 배다. 반대로 한 번도 틀리지 않은 열다섯 개는 0.021까지 내려가, 이제 세 번째 분류기가 보는 데이터는 사실상 4번과 17번이다.

from sklearn.ensemble import AdaBoostClassifier
from sklearn.datasets import load_breast_cancer
from sklearn.model_selection import train_test_split

X_train, X_test, y_train, y_test = train_test_split(
    *load_breast_cancer(return_X_y=True), test_size=0.2, random_state=42
)

# 기본 학습기는 max_depth=1 결정 그루터기
ada = AdaBoostClassifier(n_estimators=100, learning_rate=1.0, random_state=42)
ada.fit(X_train, y_train)
print(ada.score(X_test, y_test))

0.9737

Gradient Boosting

2001년 Friedman이 제안한 쪽은 접근이 다르다. AdaBoost가 샘플 가중치를 바꾸며 나아간다면, Gradient Boosting은 다음 트리에게 아예 다른 타겟을 준다. 원래 정답 $y$ 대신, 지금까지 만든 모델이 남긴 오차를 맞추라고 시킨다.

목표가 $y = 100$ 인 샘플 하나를 따라가 보자. 첫 모델이 70을 내놓으면 잔차(Residual)는 30이다. 두 번째 트리는 이 30을 타겟으로 학습하고, 학습률 0.1만큼만 반영해서 예측을 73으로 옮긴다. 이제 남은 잔차는 27이고, 세 번째 트리가 그 27을 맡는다.

한 단계의 업데이트는 이렇게 쓴다.

$F_m(x) = F_{m-1}(x) + \eta \, h_m(x)$

여기서 $h_m$ 이 학습하는 타겟이 정확히 무엇이냐가 이 방법의 핵심이다. 잔차가 아니라 손실 함수의 음의 그래디언트다.

$r_{im} = -\left. \frac{\partial L(y_i, F(x_i))}{\partial F(x_i)} \right|_{F = F_{m-1}}$

제곱 오차 $L = \frac{1}{2}(y - F)^2$ 를 쓰면 이 값이 $y_i - F_{m-1}(x_i)$, 즉 잔차와 정확히 같아진다. “잔차를 학습한다”는 직관이 성립하는 건 이 손실에서다. 분류에 쓰는 로그 손실이라면 타겟이 $y_i - p_i$ 형태로 바뀌지만 절차는 한 글자도 달라지지 않는다. 손실 함수를 갈아 끼워도 부스팅이 그대로 돌아가는 이유가 여기 있다.

트리를 늘릴수록 훈련 오차는 0을 향해 계속 내려간다. 반면 검증 오차는 초반 수십 그루에서 이득을 거의 다 가져가고 그 뒤로는 평평해지며, 두 곡선 사이에 벌어지는 간격이 과적합의 크기다. 조기 종료(Early Stopping)는 이 평평해지는 지점을 자동으로 찾아 학습을 멈추는 장치다.

학습률과 트리 수는 함께 움직인다

Gradient Boosting에서 손댈 파라미터가 하나뿐이라면 learning_rate, 둘이라면 n_estimators까지다. 그리고 이 둘은 따로 정할 수 없다. 학습률은 트리 한 그루의 기여를 얼마나 줄일지 정하므로, 낮추면 같은 지점에 도달하는 데 더 많은 트리가 필요하다. 대략 learning_rate × n_estimators 가 총 학습량이라고 보면 된다.

n_estimators=200, max_depth=3 으로 고정하고 학습률만 바꿔본 결과다(Breast Cancer, test_size=0.25).

0.001은 200그루를 다 쓰고도 출발점에서 거의 못 벗어났다. 트리가 한참 더 필요하다는 뜻이다. 0.01과 0.1은 같은 테스트 정확도에 도달했는데, 200그루라는 예산 안에서는 둘 다 충분히 수렴했다는 신호다. 1.0은 오히려 가장 낮다. 트리 한 그루가 잔차를 통째로 삼켜버려서, 앙상블이라기보다 초반 몇 그루에 끌려가는 모델이 된다.

실무에서는 학습률을 0.05 근처로 낮게 잡고 n_estimators를 넉넉히 준 다음, 멈추는 시점은 조기 종료에 맡기는 쪽이 편하다.

from sklearn.ensemble import GradientBoostingClassifier

gb = GradientBoostingClassifier(
    n_estimators=500,
    learning_rate=0.05,
    max_depth=3,
    validation_fraction=0.1,   # 훈련 데이터의 10%를 검증용으로 뗀다
    n_iter_no_change=20,       # 20라운드 개선이 없으면 중단
    tol=1e-4,
    random_state=42,
)
gb.fit(X_train, y_train)
print(gb.n_estimators_, gb.score(X_test, y_test))

75 0.9473684210526315

500그루를 지정했지만 75그루에서 멈췄다. 다만 이 설정의 테스트 정확도는 같은 학습률로 100그루를 끝까지 학습시킨 0.9561보다 낮다. 조기 종료가 찾아주는 건 최고 성능 지점이 아니라 검증 손실이 더 이상 줄지 않는 지점이다. 검증용으로 떼어낸 10%가 작을수록 이 판단은 흔들리므로, 데이터가 작다면 n_iter_no_change를 넉넉히 주는 편이 안전하다.

약한 학습기는 약해야 한다

튜닝에서 가장 자주 어긋나는 손잡이는 max_depth다.

# 각 트리가 너무 강해진다
gb = GradientBoostingClassifier(n_estimators=100, max_depth=8)

# 부스팅의 권장 범위는 3에서 5 사이다
gb = GradientBoostingClassifier(n_estimators=100, max_depth=3)

깊은 트리는 혼자서도 훈련 데이터를 거의 맞춘다. 그러면 두세 번째 트리가 학습할 잔차가 노이즈밖에 남지 않아, 오차를 나눠 갖는 부스팅의 구조 자체가 무너진다. 랜덤 포레스트가 트리를 끝까지 키우는 것을 기본값으로 두는 것과 정확히 반대다. 배깅은 강한 모델의 분산을 평균으로 깎아내는 쪽이고, 부스팅은 약한 모델의 편향을 누적으로 메우는 쪽이기 때문이다.

마치며

부스팅의 정체는 오차를 다음 사람에게 넘기는 릴레이다. AdaBoost는 넘기는 방식이 샘플 가중치였고, Gradient Boosting은 타겟 자체를 오차로 바꿔치기했다. 후자가 살아남은 건 성능 때문이라기보다 손실 함수를 자유롭게 고를 수 있어서다. 회귀든 분류든 순위 학습이든 미분 가능한 손실만 있으면 같은 절차가 돌아간다.

그래서 튜닝에서 신경 쓸 것도 둘로 좁혀진다. 각 트리를 충분히 약하게 유지하는 것(max_depth 3에서 5), 그리고 학습률과 트리 수를 한 쌍으로 다루는 것이다. 나머지는 조기 종료가 대신 판단해준다.

다만 sklearn의 GradientBoostingClassifier 는 분할점 후보를 특성 값 전부에서 찾기 때문에, 데이터가 커지면 감당이 안 될 만큼 느려진다. 이 병목을 정면으로 뜯어고친 것이 XGBoost와 LightGBM이고, 두 라이브러리가 갈라진 지점이 다음 이야기다.

함께 보면 좋은 글

• 앙상블과 배깅 : 모델을 병렬로 쌓아 분산을 줄이는 반대편 전략
• 편향-분산 트레이드오프 : 부스팅이 줄이는 편향이 무엇인지
• XGBoost와 LightGBM : 같은 원리를 실전 속도로 끌어올린 구현체

참고자료

• Freund & Schapire (1997), A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting
• Friedman (2001), Greedy Function Approximation: A Gradient Boosting Machine
• scikit-learn, Ensemble methods
• XGBoost, Introduction to Boosted Trees