AdaBoost

1. 개요[편집]

AdaBoost Adaptive Boosting
제안	Freund & Schapire — EuroCOLT 1995, JCSS 1997
수상	괴델상 (2003)
가중치 갱신	$D_{t+1}(i)\propto D_t(i)e^{-\alpha_t y_i h_t(x_i)}$
결합 계수	$\alpha_t=\tfrac12\ln\frac{1-\epsilon_t}{\epsilon_t}$
훈련오차	$\le\exp(-2\sum_t\gamma_t^2)$, $\gamma_t=\tfrac12-\epsilon_t$
통계적 정체	지수손실의 전진 단계적 가법 모형
대표 응용	비올라-존스 얼굴 검출 캐스케이드 (2001)
치명적 약점	잡음 라벨

AdaBoost(Adaptive Boosting)는 동전 던지기보다 조금만 나은 약한 학습기를 순차적으로 학습시키되, 매 라운드 직전까지 틀린 표본의 가중치를 키워 다음 학습기가 어려운 표본에 집중하게 만들고, 그렇게 얻은 가설들을 정확도에 비례한 가중치로 투표시키는 앙상블 알고리즘이다. 프로인트와 샤파이어가 1995년 EuroCOLT에서 발표하고 1997년 JCSS 에 정식 게재했으며, 2003년 괴델상을 받았다.

이 알고리즘의 역사적 무게는 성능보다 질문에 답했다는 데 있다. 칸스와 발리언트가 1988년에 던진 물음 — “약한 학습 가능성(weak learnability)과 강한 학습 가능성(strong learnability)은 같은가”, 즉 겨우 51% 맞히는 알고리즘만 있어도 99.9% 맞히는 분류기를 만들 수 있는가 — 에 샤파이어(1990)가 원리적으로 “그렇다”고 답했고, AdaBoost가 그 답을 실제로 돌아가는 세 줄짜리 알고리즘으로 바꿨다. 약한 학습기의 오차율 $\epsilon_t$ 를 미리 알 필요 없이 라운드마다 적응(adaptive)한다는 것이 이름의 유래이자 앞선 부스팅 시도들과의 결정적 차이다.

같은 논문의 전반부가 헤지 알고리즘이고, 둘은 역할을 뒤집은 한 몸이다 — 전문가 자리에 훈련 표본이 앉는 쌍대 관계와 그 통일된 증명은 그쪽 문서에 있으니 여기서는 알고리즘 자체와 통계·응용 쪽을 본다.

2. 알고리즘[편집]

훈련집합 $\{(x_i,y_i)\}_{i=1}^m$, $y_i \in \{-1,+1\}$ 에 대해 표본 분포 $D_1(i) = 1/m$ 에서 출발한다. $t = 1,\dots,T$ 에 대해:

1. $D_t$ 로 약한 학습기를 학습시켜 $h_t: \mathcal{X}\to\{-1,+1\}$ 를 얻는다.
2. 가중 오차 $\epsilon_t = \sum_{i: h_t(x_i)\neq y_i} D_t(i)$ 를 잰다.
3. $\alpha_t = \frac12\ln\frac{1-\epsilon_t}{\epsilon_t}$ 로 둔다.
4. $D_{t+1}(i) = D_t(i)\exp(-\alpha_t y_i h_t(x_i))/Z_t$ 로 갱신한다($Z_t$ 는 정규화 상수).

최종 가설은 $H(x) = \mathrm{sign}\bigl(F(x)\bigr)$, $F(x) = \sum_t \alpha_t h_t(x)$.

갱신식의 지수 안쪽 $y_i h_t(x_i)$ 는 맞히면 $+1$, 틀리면 $-1$ 이다. 그러니 맞힌 표본은 $e^{-\alpha_t}$ 배로 깎이고 틀린 표본은 $e^{\alpha_t}$ 배로 부풀려진다. $\epsilon_t < 1/2$ 이면 $\alpha_t > 0$ 이므로 방향이 늘 옳고, $\epsilon_t \to 0$ 이면 $\alpha_t \to \infty$ 로 그 가설에 표를 몰아준다.

한 줄 더 얹으면 갱신 후 성질이 재밌다. $D_{t+1}$ 하에서 $h_t$ 의 가중 오차는 정확히 $1/2$ 가 된다. 즉 방금 쓴 가설이 완전히 쓸모없어지는 지점까지 표본 분포를 밀어 놓는 것이며, 그래서 다음 라운드는 반드시 새로운 정보를 가져오는 방향으로 간다.

3. $\alpha_t$ 는 어디서 나오는가[편집]

마법의 상수처럼 보이지만 유도는 두 줄이다. 정규화 상수를 $\alpha$ 의 함수로 쓰면

$$Z_t(\alpha) = \sum_i D_t(i)\,e^{-\alpha y_i h_t(x_i)} = (1-\epsilon_t)e^{-\alpha} + \epsilon_t e^{\alpha}$$

이고 (뒤에 볼) 훈련오차 상한이 $\prod_t Z_t$ 이므로, 라운드마다 $Z_t$ 를 최소화하는 것이 탐욕적으로 옳다. 미분해서 0으로 두면

$$-(1-\epsilon_t)e^{-\alpha} + \epsilon_t e^{\alpha} = 0 \;\Longrightarrow\; e^{2\alpha} = \frac{1-\epsilon_t}{\epsilon_t} \;\Longrightarrow\; \alpha_t = \frac12\ln\frac{1-\epsilon_t}{\epsilon_t}$$

이 값에서 $Z_t = 2\sqrt{\epsilon_t(1-\epsilon_t)}$ 다. 형태를 보면 $\alpha_t$ 는 오즈비의 로그의 절반 — 이 관찰이 뒤에 나올 통계적 해석의 예고편이다.

4. 훈련오차의 지수 감소[편집]

$D_{t+1}$ 의 재귀를 풀면 $D_{T+1}(i) = \frac{1}{m}\exp(-y_i F(x_i))/\prod_t Z_t$ 이고, $\sum_i D_{T+1}(i) = 1$ 이므로

$$\frac1m\sum_i e^{-y_i F(x_i)} = \prod_{t=1}^T Z_t$$

한편 $H(x_i)\neq y_i$ 이면 $y_iF(x_i)\le 0$ 이라 $e^{-y_iF(x_i)}\ge 1$ 이므로 0-1 손실은 지수손실에 눌린다. 따라서

$$\widehat{\mathrm{err}}(H) \;\le\; \prod_t Z_t = \prod_t 2\sqrt{\epsilon_t(1-\epsilon_t)} = \prod_t\sqrt{1-4\gamma_t^2} \;\le\; \exp\Bigl(-2\sum_t \gamma_t^2\Bigr)$$

여기서 $\gamma_t = \frac12 - \epsilon_t$ 는 약한 학습기가 동전 던지기보다 나은 정도(edge)다. 모든 라운드에서 $\gamma_t \ge \gamma > 0$ 만 보장되면 훈련오차가 $e^{-2\gamma^2 T}$ 로 지수적으로 죽는다¹ — 이것이 약한 학습 가능성이 곧 강한 학습 가능성이라는 정리의 구성적 증명이다. 각 $\gamma_t$ 를 알 필요가 없다는 점, 그리고 좋은 라운드가 나쁜 라운드를 벌충한다는 점이 “적응적”의 실질적 내용이다.

5. 통계학의 재해석 — 지수손실의 전진 단계적 가법 모형[편집]

프리드먼·해스티·팁시라니(2000)의 재해석은 AdaBoost를 학습이론에서 통계 모형의 세계로 옮겨 놓았다. 요지는 이렇다. AdaBoost는 지수손실

$$\mathcal{L}(F) = \mathbb{E}\bigl[e^{-y F(x)}\bigr]$$

을 가법 모형 $F(x) = \sum_t \alpha_t h_t(x)$ 에 대해 전진 단계적(forward stagewise)으로 최소화하는 절차와 정확히 같다. $t$ 단계에서 이미 만든 $F_{t-1}$ 은 고정하고 새 항 $(\alpha,h)$ 만 최적화하면

$$(\alpha_t,h_t) = \arg\min_{\alpha,h}\sum_i w_i^{(t)}\,e^{-\alpha y_i h(x_i)}, \qquad w_i^{(t)} = e^{-y_i F_{t-1}(x_i)}$$

인데, 이 $w_i^{(t)}$ 가 정규화만 다를 뿐 AdaBoost의 $D_t(i)$ 그 자체다. $\alpha$ 에 대한 최소화가 앞 절의 두 줄 유도이고. 즉 “가중치를 왜 지수로 갱신하는가”의 답은 손실이 지수함수라서다.

여기서 두 가지가 따라 나온다.

• AdaBoost가 추정하는 양이 무엇인가. 지수손실의 모집단 최소해는 $$F^*(x) = \frac12\ln\frac{P(y=+1\mid x)}{P(y=-1\mid x)}$$ 로, 로그 오즈의 절반이다. 따라서 $p(x) = 1/(1+e^{-2F(x)})$ 로 확률을 되뽑을 수 있다. 라운드마다의 $\alpha_t$ 가 오즈비 로그의 절반이었던 것도 같은 이야기의 국소판이다. 다만 실제 $F$ 가 부호만 맞으면 되는 쪽으로 커지기 때문에, 이 확률 추정은 심하게 과확신하는 경향이 있어 보정(calibration)이 필요하다.
• 손실을 갈아 끼울 수 있다. 지수손실을 로지스틱 손실로 바꾸고 뉴턴 스텝을 밟으면 LogitBoost, 스텝을 온건하게 잡으면 GentleBoost가 된다. 임의의 미분 가능한 손실에 대해 “음의 함수 기울기에 약한 학습기를 적합”시키는 일반형으로 밀면 프리드먼(2001)의 그래디언트 부스팅이고, 오늘날 정형 데이터 대회를 쓸어 담는 XGBoost·LightGBM 계열이 그 자손이다. AdaBoost는 그 계보의 첫 항이자, 손실을 지수로 고른 특수한 사례로 자리매김한다.

6. 마진 이론과 과적합 저항[편집]

AdaBoost의 가장 유명한 관찰은 훈련오차가 0이 된 뒤에도 라운드를 계속 늘리면 시험오차가 더 떨어진다는 것이다. 편향-분산의 소박한 그림(편향-분산 분해 참고)으로는 모델 복잡도가 계속 늘어나니 과적합이 나야 정상인데, 실측은 반대로 나온다.

샤파이어·프로인트·바틀렛·리(1998)의 설명이 마진 이론이다. 정규화된 마진을

$$\mathrm{margin}(x,y) = \frac{y\sum_t \alpha_t h_t(x)}{\sum_t \alpha_t}\;\in\;[-1,1]$$

로 정의하면, 일반화 오차 상한이 마진 분포와 약한 학습기 부류의 복잡도만으로 쓰이고 라운드 수 $T$ 가 들어가지 않는다. 그리고 훈련오차가 0이 된 뒤에도 AdaBoost는 마진 분포를 계속 오른쪽으로 밀기 때문에, 상한이 계속 줄어든다. 직관적으로는 “맞히기만 하는 것”에서 “여유 있게 맞히는 것”으로 목표가 옮겨 간다는 뜻이며, 서포트 벡터 머신의 마진 최대화와 정신은 같다(다만 AdaBoost가 크게 만드는 마진은 가중치의 $\ell_1$ 노름 기준이고 SVM은 $\ell_2$ 기준이라, 결과로 나오는 분류기는 다르다).

이 설명이 만장일치는 아니다. 브라이만(1999)이 최소 마진을 더 크게 만드는 arc-gv 를 만들었더니 오히려 일반화가 나빠진다는 반례를 제시했고, 레이진과 샤파이어(2006)가 arc-gv 실험에서 약한 학습기의 트리 깊이가 함께 커져 복잡도가 통제되지 않았음을 지적하며 재반박했다. 이후 최소 마진이 아니라 마진 분포 전체(예컨대 $k$ 번째 마진)를 보는 상한들로 정리가 다듬어졌다. 정리하면 — 마진 이론은 “왜 T를 늘려도 되는가”를 설명하는 현재의 표준 언어지만, 최소 마진 하나를 키우면 무조건 좋다는 단순한 처방은 성립하지 않는다.

한 가지는 분명히 해 두자. AdaBoost가 과적합을 안 한다는 말은 거짓이다. 저항력이 있을 뿐이고, 약한 학습기가 너무 강하거나 라운드를 무한정 늘리면 결국 과적합한다. 그리고 다음 절의 조건에서는 아주 빠르게, 아주 심하게 한다.

7. 잡음 라벨이라는 아킬레스건[편집]

지수손실은 마진이 음수인 표본에 지수적으로 벌점을 준다. 라벨이 잘못 붙은 표본은 어떤 가설로도 못 맞히므로 라운드마다 가중치가 계속 부풀고, 결국 몇 개의 잘못된 표본이 분포 $D_t$ 를 통째로 독차지한다. 그러면 이후의 모든 약한 학습기가 오타를 학습한다.

이건 튜닝으로 피해 갈 수 있는 정도의 문제가 아니다. 롱과 서베디오(2010)는 볼록 퍼텐셜을 최소화하는 모든 부스팅 알고리즘(AdaBoost, LogitBoost 등 사실상 전부)이 무작위 라벨 잡음 아래에서 실패하는 문제 사례를 구성했다 — 잡음률이 몇 퍼센트에 불과하고 데이터가 무한히 많으며 잡음 없는 완벽한 분류기가 가설 부류 안에 존재하는데도, 볼록 부스터의 정확도는 동전 던지기 수준으로 떨어진다. 볼록성이라는 편리한 성질에 대해 치르는 대가라는 것이 결론이다.

현실적 대응은 다음 정도다.

• 비볼록 손실로 간다. BrownBoost·RobustBoost(프로인트)는 어려운 표본을 어느 시점에 포기하는 메커니즘을 갖는다. 잡음 표본을 붙들지 않으니 강건하지만 하이퍼파라미터가 늘어난다.
• 가중치에 상한을 둔다. MadaBoost 계열, 혹은 그냥 $D_t(i)$ 를 잘라 내는 실무적 처방.
• 일찍 멈춘다. 검증셋으로 $T$ 를 고르는 것이 가장 싸고 자주 통한다. 축소 계수 $\nu$ (라운드마다 $\nu\alpha_t$ 만 더하기)를 곁들이면 더 완만해진다.
• 애초에 라벨을 고친다. 가중치 상위 표본 몇십 개를 눈으로 보면 대부분 라벨 오류다. 이걸 잡음 탐지기로 쓰는 것이 AdaBoost의 의외의 부업이다.²

8. 비올라-존스 — AdaBoost가 세상을 만난 순간[편집]

AdaBoost의 산업적 성공 사례는 압도적으로 하나, 비올라와 존스의 실시간 얼굴 검출기(2001)다. 세 아이디어의 결합인데 그중 둘이 AdaBoost다.

• 하르 유사 특징 + 적분 영상. 인접한 사각 영역의 밝기 합의 차이를 특징으로 쓰고, 누적합 영상을 미리 만들어 두면 임의 크기 사각 영역의 합을 네 번의 참조로 얻는다. 특징 하나의 계산이 상수 시간.
• AdaBoost를 특징 선택기로. $24\times24$ 창에서 뽑히는 하르 특징이 18만 개쯤 되는데, 약한 학습기를 “특징 하나 + 임계값 하나” 로 제한하면 각 라운드가 곧 “가장 유용한 특징 하나 고르기”가 된다. 분류기 학습과 특징 선택이 같은 절차로 처리되는 이 발상이 논문의 핵심 기여다.
• 주의 캐스케이드(attentional cascade). 배경 창이 압도적으로 많다는 점을 이용해, 부스팅 분류기를 여러 단계로 늘어놓고 각 단계를 검출률 거의 100%·오검출률 40~50% 로 맞춘다. 앞 단계에서 떨어진 창은 즉시 버린다. 첫 단계는 특징 두 개만으로 배경 창의 절반가량을 쳐 내므로, 대부분의 창이 연산 몇 번 만에 종료된다. 최종 검출기는 38단계·총 6061개 특징이었고, $384\times288$ 영상을 700MHz 펜티엄 III에서 초당 15프레임으로 처리했다.

캐스케이드의 요지는 평균 비용을 최적화한 것이지 정확도를 올린 것이 아니다. 확률이 낮은 사건(얼굴)을 찾을 때는 흔한 경우를 싸게 기각하는 구조가 이긴다 — 중요도 표본추출이나 충돌 검사의 브로드페이즈와 정신이 같다. 2000년대 내내 디지털 카메라의 얼굴 인식 네모 상자는 사실상 전부 이 알고리즘이었고, 딥러닝 검출기에 자리를 내주기 전까지 OpenCV의 대표 기능이었다.³

9. 변형과 실무 감각[편집]

• Real AdaBoost / 신뢰도 부여 예측(샤파이어 & 싱어 1999). 약한 학습기가 $\pm1$ 대신 실수값을 내놓게 하면 $\alpha_t$ 를 따로 두지 않고 학습기 출력 자체에 크기를 실을 수 있다. 실무 구현의 기본형에 가깝다.
• 다중 클래스. 원조 AdaBoost.M1은 $\epsilon_t < 1/2$ 를 요구하는데, 클래스가 $K$ 개면 무작위 추측의 오차가 $1-1/K$ 라 이 조건이 지나치게 빡세다. 대응이 AdaBoost.MH(다중 라벨 이진 문제로 환원)와 SAMME(주 외 2009)이며, 후자는 $\alpha_t = \ln\frac{1-\epsilon_t}{\epsilon_t} + \ln(K-1)$ 로 요구 조건을 $\epsilon_t < 1 - 1/K$ 까지 완화한다.
• 약한 학습기 선택. 결정 그루터기(깊이 1 결정 트리)가 표준이다. 깊이를 올리면 상호작용을 잡을 수 있지만 잡음 취약성과 과적합이 함께 커진다. “약한 학습기는 약해야 한다” 는 조언은 농담이 아니다.
• 하이퍼파라미터가 사실상 하나. 라운드 수 $T$ (와 축소 계수 $\nu$)뿐이라는 점이 실무에서 큰 미덕이다. 랜덤 포레스트가 병렬로 분산을 줄이는 배깅 계열이라면 AdaBoost는 순차적으로 편향을 줄이는 계열이고, 그래서 병렬화가 어렵다는 대가도 같이 온다.
• $\epsilon_t = 0$ 처리. 어떤 약한 학습기가 가중 오차 0을 내면 $\alpha_t$ 가 발산한다. 구현체는 보통 여기서 학습을 멈추거나 $\epsilon_t$ 를 작은 값으로 클리핑한다. 데이터가 작을 때 흔히 만나는 상황.
• 전처리에 둔감하다. 트리 기반 약한 학습기를 쓰면 특징 스케일링이 필요 없고 결측값 처리도 트리에 맡길 수 있다. 정형 데이터에서 부스팅 계열이 오래 살아남은 실용적 이유의 절반은 이 귀찮음의 부재다.⁴

10. 관련 문서[편집]

• 헤지 알고리즘 · 온라인 볼록 최적화 · 미러 하강
• 그래디언트 부스팅 · 결정 트리 · 랜덤 포레스트
• 편향-분산 분해 · 교차검증 · 과적합
• 심층 학습 · 합성곱 신경망 · 지식 증류
• 중요도 표본추출 · 게임 이론

11. Footnotes[편집]

1. “약한 학습기”의 하한이 정확히 어디인지도 재밌는 질문이다. $\gamma_t$ 가 0으로 너무 빨리 수렴하면 $\sum\gamma_t^2$ 가 발산하지 않아 상한이 무의미해진다. 즉 “동전 던지기보다 조금만 나으면 된다”는 문구의 진짜 조건은 모든 라운드에서 균일하게 조금 나아야 한다는 것이다. 논문 초록만 읽고 아무 약한 학습기나 꽂으면 이 지점에서 배신당한다. ↩

2. 실제로 부스팅을 몇백 라운드 돌린 뒤 $D_t$ 상위 표본을 뽑아 보면 “이건 사람이 봐도 개인지 늑대인지 모르겠는데” 같은 것들이 줄줄이 나온다. 알고리즘이 데이터셋의 오타를 대신 찾아 주는 셈인데, 정작 그 표본들 때문에 모델은 망가지고 있으니 웃을 일만은 아니다. ↩

3. 비올라-존스 논문이 실린 CVPR 2001 당시 “실시간”의 기준은 700MHz 싱글 코어였다. 지금 스마트폰에서 같은 알고리즘을 돌리면 초당 수백 프레임이 나오는데, 정작 아무도 안 쓴다. 20년 사이에 하드웨어보다 알고리즘이 더 빨리 갈아치워진 드문 사례. ↩

4. 정형 데이터 대회에서 “일단 부스팅 돌려”가 국룰이 된 지 10년이 넘었다. 딥러닝이 이미지·언어를 다 가져갔지만 엑셀 표 앞에서는 여전히 그래디언트 부스팅이 최강자라는 사실은, 이 계보의 첫 항인 AdaBoost 입장에서 꽤 명예로운 노후다. ↩