에이다부스트

에이다부스트(영어: AdaBoost: adaptive boosting의 줄임말, 아다부스트는 잘못된 발음)는 Yoav Freund와 Robert Schapire가 개발한 기계 학습 메타 알고리즘이으로 이들은 AdaBoost를 개발한 공로를 인정받아 2003년 괴델상을 받았다. AdaBoost는 성능을 향상시키기 위하여 다른 많은 형태의 학습 알고리즘과 결합하여 사용할 수 있다. 다른 학습 알고리즘(약한 학습기, weak learner)의 결과물들을 가중치를 두어 더하는 방법으로 가속화 분류기의 최종 결과물을 표현할 수 있다. AdaBoost는 이전의 분류기에 의해 잘못 분류된 것들을 이어지는 약한 학습기들이 수정해줄 수 있다는 점에서 다양한 상황에 적용할 수 있다(adaptive). 따라서 에이다 부스트는 잡음이 많은 데이터와 이상점(outlier)에 취약한 모습을 보인다. 그러나 또 다른 경우에는, 다른 학습 알고리즘보다 과적합(overfitting)에 덜 취약한 모습을 보이기도 한다. 개별 학습기들의 성능이 떨어지더라도, 각각의 성능이 무작위 추정보다 조금이라도 더 낫다면(이진 분류에서 에러율이 0.5보다 낮다면), 최종 모델은 강한 학습기로 수렴한다는 것을 증명할 수 있다.

모든 학습 알고리즘이 잘 적용될 수 있는 형태의 문제가 있고 그렇지 않은 문제가 있으며, 일반적으로 주어진 데이터 집합에 대한 최고의 성능을 얻기 위해서 많은 파라미터와 설정을 조절해야 하는 반면, (약한 학습기로서 결정 트리 학습법을 이용한) AdaBoost는 종종 최고의 발군의 분류기로 불린다. 결정 트리 학습법과 함께 사용되었을 때, AdaBoost 알고리즘의 각 단계에서 얻을 수 있는 각 훈련 샘플의 상대적 난이도에 대한 정보가 트리 성장 알고리즘에 반영되어 트리가 분류하기 더 어려운 경우에 집중되는 경향이 있다.

개요

기계학습의 문제들은 종종 차원수의 저주에 시달린다. 각 샘플은 아주 많은 숫자의 잠재적 특성(예를 들어, Viola-Jones 물체 탐지 체계에서 사용되는 하아 특징(Haar feature)의 경우 24x24픽셀 그림 윈도우에 162336개의 특성이 있을 수 있다.)들로 이루어질 수 있고, 모든 특성을 고려하는 것은 분류기의 훈련과 수행 속도를 늦출 뿐만 아니라 휴즈 효과(Hughes Effect)에 의해 예측 능력까지 떨어트리게 된다. 인공신경망이나 서포트 벡터 머신과는 다르게, AdaBoost 훈련 과정은 모델의 예측 능력을 향상시킬 것으로 생각되는 특성들만 선택하고, 이는 차원수를 줄이는 동시에 필요없는 특성들을 고려하지 않음으로써 잠재적으로 수행 시간을 개선시킨다.

훈련

AdaBoost는 가속화 분류기를 훈련시키는 한 방법을 이르는 말이다. 가속 분류기는 다음과 같은 형태로 표현된다.

$F_{T}(x)=\sum _{t=1}^{T}f_{t}(x)\,\!$

이 때, 각 $f_{t}$는 객체 $x$를 입력으로 받고, 그 객체가 속한 종류를 나타내는 실수를 돌려주는 약한 학습기이다. 약한 학습기 출력의 부호는 예측된 객체 분류를 나타내고 절대값은 그 분류의 신뢰도를 나타낸다. $T$번째 분류기는 샘플 분류가 양의 부호로 예상되면 양수를, 그렇지 않은 경우 음수를 반환한다.

각각의 약한 학습기는 훈련 집합의 각각의 샘플에 대해 가설 $h(x_{i})$를 출력으로 생성한다. 각각의 반복 단계$t$에서, 하나의 약한 학습기가 선택되고 최종적인 $t$-단계 가속 분류기의 훈련 오류의 합 $E_{t}$가 최소가 되도록 하는 계수 $\alpha _{t}$가 배정된다.

$E_{t}=\sum _{i}E[F_{t-1}(x_{i})+\alpha _{t}h(x_{i})]$

여기서 $F_{t-1}(x)$는 직전 훈련 단계까지 생성된 가속화 분류기이고, $E(F)$는 오류 함수이며 $f_{t}(x)=\alpha _{t}h(x)$는 최종 분류기에 더하기 위해 현재 고려하고 있는 약한 학습기이다.

가중치 설정

훈련 과정의 각 반복 단계에서 훈련 집합의 각각의 샘플에 대한 현재 오류 $E(F_{t-1}(x_{i}))$와 같은 값의 가중치가 그 샘플에 배정된다. 이러한 가중치는 약한 학습기의 훈련에 영향을 미칠 수 있는데, 예를 들어 결정 트리는 높은 가중치를 가진 샘플의 집합을 나누는 것을 선호하도록 성장할 수 있다.

유도 과정

$y_{i}\in \{-1,1\}$를 가지고 있는 데이터 집합 $\{(x_{1},y_{1}),\ldots ,(x_{N},y_{N})\}$과 각 분류기가 각 항목에 대한 분류$k_{j}(x_{i})\in \{-1,1\}$를 출력하는 약한 분류기의 집합 $\{k_{1},\ldots ,k_{L}\}$을 가지고 있다고 가정하자. $m-1$번째 반복 단계 이후 우리의 가속화 분류기는 다음과 같은 형태의 약한 분류기의 선형 결합(linear combination)으로 표현된다.

$C_{(m-1)}(x_{i})=\alpha _{1}k_{1}(x_{i})+\cdots +\alpha _{m-1}k_{m-1}(x_{i})$

$m$번째 반복 단계에서 우리는 하나의 약한 분류기에 특정 값을 곱한 후 이를 기존의 분류기에 더하여 더 나은 가속화 분류기로 확장하고자 한다.

$C_{m}(x_{i})=C_{(m-1)}(x_{i})+\alpha _{m}k_{m}(x_{i})$

그러면 어떤 약한 분류기가 $k_{m}$이 되는 데 가장 좋은 선택이고, 어떤 가중치$\alpha _{m}$를 부여해야 하는지 결정하는 문제가 남는다. 우리는 $C_{m}$의 총 오류 $E$를 각 데이터 포인트에 대한 지수 손실의 합으로 아래와 같이 정의한다.

$E=\sum _{i=1}^{N}e^{-y_{i}C_{m}(x_{i})}$

$m>1$에 대하여 $w_{i}^{(1)}=1$ , $w_{i}^{(m)}=e^{-y_{i}C_{m-1}(x_{i})}$ 라 두면, 아래와 같은 식을 얻는다.

$E=\sum _{i=1}^{N}w_{i}^{(m)}e^{-y_{i}\alpha _{m}k_{m}(x_{i})}$

우리는 이 식을 $k_{m}$에 의해 정확하게 분류된 데이터 포인트(즉, $y_{i}k_{m}(x_{i})=1$)와 잘못 분류된 데이터 포인트(즉, $y_{i}k_{m}(x_{i})=-1$)로 아래와 같이 나눌 수 있다.

$E=\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}e^{-\alpha _{m}}+\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}e^{\alpha _{m}}=\sum _{i=1}^{N}w_{i}^{(m)}e^{-\alpha _{m}}+\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}(e^{\alpha _{m}}-e^{-\alpha _{m}})$

이 식의 우변에서 $k_{m}$에 의존하는 부분은 $\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}$뿐이기 때문에, $E$를 최소화하는 $k_{m}$이 $\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}$도 최소한다는 것을 알 수 있다. 즉, $k_{m}$이 가중치를 고려한 가장 낮은 오류를 가진 약한 분류기(가중치 $w_{i}^{(m)}=e^{-y_{i}C_{m-1}(x_{i})}$를 가진 것)인 것이다.

조금 전에 결정한$k_{m}$를 가진 $E$를 최소화하는 가중치 $\alpha _{m}$를 결정하기 위하여 우리는 아래와 같은 미분을 수행한다.

${\frac {dE}{d\alpha _{m}}}=\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}e^{\alpha _{m}}-\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}e^{-\alpha _{m}}$

이를 0으로 놓고 $\alpha _{m}$에 대하여 풀면 다음과 같은 식이 된다.

$\alpha _{m}={\frac {1}{2}}\ln {\frac {\sum _{y_{i}=k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}}$

약한 분류기의 가중치가 고려된 오류율을 $\epsilon _{m}={\frac {\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{i=1}^{N}w_{i}^{(m)}}}$와 같이 계산할 수 있고, 따라서 다음 식이 성립한다.

$\alpha _{m}={\frac {1}{2}}\ln {\frac {1-\epsilon _{m}}{\epsilon _{m}}}$

이렇게 함으로써 우리는 AdaBoost 알고리즘을 유도하였다. 각 반복 단계에서, 가중치가 고려된 총 오류$\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}$를 최소화하는 분류기 $k_{m}$을 선택하고, 이를 오류율 $\epsilon _{m}={\frac {\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}{\sum _{i=1}^{N}w_{i}^{(m)}}}$를 계산하는데 이용하고, 이를 가중치$\alpha _{m}={\frac {1}{2}}\ln {\frac {1-\epsilon _{m}}{\epsilon _{m}}}$를 계산하는데 이용하며, 이를 마지막으로 가속화 분류기 $C_{m-1}$ to $C_{m}=C_{(m-1)}+\alpha _{m}k_{m}$를 개선하는데 이용한다.

가속화 개념에 대한 통계적 접근

가속화(Boosting)는 각 샘플 $x_{i}$의 특성이 어떤 약한 학습기 $h$의 $x_{i}$에 대한 결과값과 같은 선형회귀 형태를 가진다. 구체적으로, 모든 약한 학습기가 선험값(a priori)일 경우에 AdaBoost는 퇴각 적합화(backfitting) 알고리즘의 한 번의 반복단계와 같으며, 이 때 완곡화 스플라인(smoothing spline)은 $\sum _{i=1}^{n}e^{-Y_{i}{\hat {\mu }}(x_{i})}+\infty \int _{x_{1}}^{x_{n}}{\hat {\mu }}''(x)^{2}\,dx$의 최소점과 같다. (${\hat {\mu }}_{i}$는 측정값에 비례하는 지수비용함수를 나타낸다) 따라서 가속화는 선형회귀의 일종이라고 볼 수 있다.

회귀 방식에서는 최소자승오차(Least square error) $E(f)=(y(x)-f(x))^{2}$을 활용하여 $F(x)$를 일반성(generalization)을 잃지 않고 최대한 정확하게 $y(x)$에 맞추려고 하는 것이 일반적이다. 반면에, AdaBoost 오차함수 $E(f)=e^{-y(x)f(x)}$는 마지막 결과의 부호만이 사용된다는 점을 고려하기 때문에 오차의 증가 없이도 $|F(x)|$값이 1을 훨씬 웃돌 수 있다. 그러나, $-y(x_{i})f(x_{i})$의 증가에 따른 샘플 $x_{i}$ 오차의 기하급수적 증가는 이상점에 과도한 가중치를 부여하게 된다.

지수오차함수를 사용하면 최종적응모델의 오차는 $e^{\sum _{i}-y_{i}f(x_{i})}=\prod _{i}e^{-y_{i}f(x_{i})}$와 같이 각 단계에서의 오차의 곱과 같다. 따라서 AdaBoost 알고리즘에서 가중치 갱신은 각 단계 후에 $F_{t}(x)$의 오차를 재계산하는 것과 같다고 볼 수 있다.

손실함수(Loss function)은 유연하게 선택할 수 있다. 손실함수가 단조적이고 연속적으로 미분가능할 때, 분류기는 항상 알맞은 값(purer solution)에 근접한다. 장(Zhang,2004)은 최소자승을 기반으로하여 수정된 후버 손실함수(Huber loss function)을 제안하였다.

$\phi (y,f(x))={\begin{cases}-4yf(x)&{\mbox{if }}\,yf(x)<-1,\\(yf(x)-1)^{2}&{\mbox{if }}\,-1\leq yf(x)\leq 1,\\0&{\mbox{if }}\,yf(x)>1\end{cases}}$

이 함수는 $f(x)$가 1 또는 -1에 가까울 때 로지스틱 가속(LogitBoost)보다 잘 작동한다. 본래의 최소자승기법과는 달리 신뢰구간을 벗어난 예측(overconfident prediction, $yf(x)>1$)에는 페널티를 주지 않으며, 선형적으로 신뢰도(confidence)가 1보다 큰 잘못 분류된 샘플에 대해서만 페널티를 준다. 따라서 2차 또는 지수방식과는 달리 이상점에 덜 민감한 경향을 보인다.

기울기 하강(Gradient Descent)을 통한 가속화

가속화 과정은 함수의 볼록 집합(convex set)에 대한 볼록손실함수(convex loss function)의 최소화 과정으로 볼 수 있다. 구체적으로는, AdaBoost는 지수 함수 $\sum _{i}\phi (i,y,f)=\sum _{i}e^{-y_{i}f(x_{i})}$을 통해 손실을 최소화하며, 로지스틱 가속은 로그회귀(logistic regression) $\sum _{i}\phi (i,y,f)=\sum _{i}\ln \left(1+e^{-y_{i}f(x_{i})}\right)$를 통해 최소화를 수행한다.

기울기 하강 유추기법에서, 각 훈련값(training point)에 대한 분류기의 결과는 n차 공간에서의 점$\left(F_{t}(x_{1}),\dots ,F_{t}(x_{n})\right)$으로 간주되고, 각각의 축은 훈련샘플에, 각 약한 학습기 $h(x)$는 어떤 벡터의 고정된 방향과 길이에 대응되며, 최종 목적은 최소 반복을 통해 목표점 $(y_{1},\dots ,y_{n})$(혹은 손실함수값 $E_{T}(x_{1},\dots ,x_{n})$)이 근처 다른 점에서보다 작은 지점)에 도달하는 것이다. 따라서 AdaBoost 알고리즘은 훈련오차(training error)의 최적화를 위해 코시 기법(Cauchy, 실험오차를 최소화하는 $\alpha$를 통한 $h(x)$를 찾는 급경사(steepest gradient) 기법) 혹은 뉴턴 기법(Newton, 어떠한 목표점에 가장 가까운 $F_{t}$를 가지는 $\alpha h(x)$를 찾는 기법)을 수행하는 셈이다.

알고리즘 예시 (불연속적 AdaBoost)

다음과 같은 조건일 때:

• 샘플 $x_{1}\dots x_{n}$
• 목표 결과값 $y_{1}\dots y_{n},y\in \{-1,1\}$
• 초기 가중치 $w_{1,1}\dots w_{n,1}$는 ${\frac {1}{n}}$으로 설정
• 오차함수 $E(f(x),y,i)=e^{-y_{i}f(x_{i})}$
• 약한 학습기 $h\colon x\rightarrow [-1,1]$

$t=1\dots T$에 대하여:

• $f_{t}(x)$의 선택:
  • $\epsilon _{t}$을 최소화하는 약한 학습기 $h_{t}(x)$를 찾는다. 이 때 잘못 분류된 오차의 가중합은 다음과 같다. $\epsilon _{t}=\sum _{i}w_{i,t}E(h_{t}(x),y,i)$
  • $\alpha _{t}={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{t}}{\epsilon _{t}}}\right)$
• 총합에 추가:
  • $F_{t}(x)=F_{t-1}(x)+\alpha _{t}h_{t}(x)$
• 가중치 갱신:
  • $w_{i,t+1}=w_{i,t}e^{-y_{i}\alpha _{t}h_{t}(x_{i})}$ (모든 $i$에 대하여)
  • $w_{i,t+1}$의 재정규화 ($\sum _{i}w_{i,t+1}=1$)
  • (추가: 모든 단계에서 ${\frac {\sum _{h_{t+1}(x_{i})=y_{i}}w_{i,t+1}}{\sum _{h_{t+1}(x_{i})\neq y_{i}}w_{i,t+1}}}={\frac {\sum _{h_{t}(x_{i})=y_{i}}w_{i,t}}{\sum _{h_{t}(x_{i})\neq y_{i}}w_{i,t}}}$는 항상 성립하며, 이를 이용해 가중치 갱신과정을 간소화할 수 있다.)

가중치 α_t의 선택

α_t는 불연속적 AdaBoost에서 지수오차함수를 분석적으로(analytically) 최소화하는 값으로 정해진다.

$min\sum _{i}w_{i}e^{-y_{i}h_{i}\alpha _{t}}$

$\forall i,h_{i}\in [-1,1]$라 가정하였을 때, 지수함수의 볼록성(convexity)를 이용하면 다음과 같은 식을 만족한다.

${\begin{aligned}\sum _{i}w_{i}e^{-y_{i}h_{i}\alpha _{t}}&\leq \sum _{i}\left({\frac {1-y_{i}h_{i}}{2}}\right)w_{i}e^{\alpha _{t}}+\sum _{i}\left({\frac {1+y_{i}h_{i}}{2}}\right)w_{i}e^{-\alpha _{t}}\\&=\left({\frac {1+\epsilon _{t}}{2}}\right)e^{\alpha _{t}}+\left({\frac {1-\epsilon _{t}}{2}}\right)e^{-\alpha _{t}}\end{aligned}}$

위식을 $\alpha _{t}$에 대하여 미분하고 상한값의 최솟값을 구하기 위해 0으로 설정한다.

${\begin{aligned}\left({\frac {1+\epsilon _{t}}{2}}\right)e^{\alpha _{t}}-\left({\frac {1-\epsilon _{t}}{2}}\right)e^{-\alpha _{t}}&=0\\\alpha _{t}&={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{t}}{1+\epsilon _{t}}}\right)\end{aligned}}$

이러한 관계는 $h_{i}\in \{-1,1\}$일 때만 성립한다는 것에 주의해야하지만, 이외의 경우에도 좋은 초기추측이 될 수 있다. 예로, 약한 학습기가 편향되어있거나($h(x)\in \{a,b\},a\neq -b$), 여러 결과를 가지거나($h(x)\in \{a,b,\dots ,n\}$), 아니면 다른 어떤 함수일 경우($h(x)\in \mathbb {R}$)에도 활용할 수 있다. 이러한 경우 약한 학습기와 계수는 모든 가능한 $\alpha ,h$로부터 $f_{t}=\alpha _{t}h_{t}(x)$가 정해지는 단 한 번의 단계를 통해 선택될 수 있으며, 이 때의 $\alpha ,h$는 어떤 수치적인 탐색기법을 통해 $\sum _{i}w_{i,t}e^{-y_{i}f_{t}(x_{i})}$를 최소화하는 값으로 정해진다.

변형

실수형 에이다부스트(Real AdaBoost)

이산 AdaBoost에서 쓰이는 분류기는 그 결과를 $\{-1,1\}$ 의 형태로 나타낸다. 실수 AdaBoost에서는 분류의 결과를 각 클래스에 포함될 확률 $p(x)=P(y=1|x)$ 로서 나타낸다. 이는 $x$ 라는 원소가 $y$ 클래스에 포함될 확률을 나타낸다. Friedman, Hastie 그리고 Tibshirani는 고정된 $p(x)$에 대하여 $e^{-y\left(F_{t-1}(x)+f_{t}(p(x))\right)}$를 최소화하는 $f_{t}(p(x))$를 유도하였다(최소제곱법).

$f_{t}(x)={\frac {1}{2}}\ln \left({\frac {x}{1-x}}\right)$.

이를 이용하면 전체 트리에 대하여 연산을 하는 대신에 잎사귀 값들을 이전 값의 로지스틱 변환의 절반을 취하는 것으로 대체할 수 있다. 이산 AdaBoost와의 가장 큰 차이점은 이산 AdaBoost에서는 결과의 신뢰도를 따로 계산해야 하지만 실수 AdaBoost에서는 약한 분류기의 신뢰도가 확률로써 그대로 표현된다는 것에 있다.

로지스틱 부스트(LogitBoost)

로지스틱 회귀분석을 이용하여 AdaBoost을 실현하는 것이 로지스틱 가속이다. $y$ 의 에러를 직접 감소시키는 대신에 다음 식에서 $f_{t}(x)$를 최소화하는(최소제곱법) 약한 학습기를 사용한다:

$z_{t}={\frac {y^{*}-p_{t}(x)}{2p_{t}(x)(1-p_{t}(x))}}$

$p_{t}(x)={\frac {e^{F_{t-1}(x)}}{e^{F_{t-1}(x)}+e^{-F_{t-1}(x)}}}$

$w_{t}=p_{t}(x)(1-p_{t}(x))$

$y^{*}={\frac {y+1}{2}}$.

$z_{t}$는 뉴턴의 방법를 사용하여 $t$에 대한 로그 가능도의 오류를 최소화하는 항이다. 또한 $f_{t}$는 최소제곱법에 의해 $z_{t}$를 최소화하는 약한 학습기이다.

$p$의 값은 0이나 1에 근접하게 된다. 따라서 $p_{t}(x_{i})(1-p_{t}(x_{i}))$ 또한 매우 작은 값을 취하게 될 것이다. 만일 $z$ 항이 큰 값을 갖거나 안정적으로 수렴하지 않는다면 이는 샘플 $x$가 잘못 분류되었음을 의미하게 된다. 이러한 문제는 주로 소수점 연산의 부정확성에 의하여 발생할 수 있다. 이는 $z$의 절대값의 최댓값이나 $w$의 최솟값을 강제로 지정함으로써 피할 수 있다.

관대한 에이다부스트(Gentle AdaBoost)

이전의 가속 방법들은 각 반복 과정에서 오류를 최소화하는 $f_{t}$를 구하고 이를 이용해서 전체 오류를 최소화하였다 (탐욕 알고리즘). 반면에 부드러운 AdaBoost에서는 반복 횟수를 제한한다.

$f_{t}$는 $\sum _{i}w_{t,i}(y_{i}-f_{t}(x_{i}))^{2}$를 최소화하도록 정해진다. 여기서 다른 매개변수는 사용되지 않는다. 그렇기 때문에 약한 학습기가 완벽한 분류를 할 수 있는 상황에서 부드러운 AdaBoost은 정확한 $y$ 값을 구할 수 있다. 한편 기울기 기반의 알고리즘은 $f_{t}(x)=\alpha _{t}h_{t}(x)$의 $\alpha _{t}$를 무한대에 가깝게 정하게 되고 이는 분류의 정확도를 떨어뜨리게 된다. 관대한 에이다부스트(Gentle AdaBoost)은 이러한 측면에서 Schapire 와 Singer가 지적했듯이 $\alpha _{t}=\infty$의 경우에 발생할 수 있는 성능 저하를 보완할 수 있다.

빠른 종료(Early Termination)

가속화 분류기의 속도를 올리는 방법 중 하나는 분류 작업을 끝까지 진행하지 않고 일정 신뢰 구간을 확보한 시점에서 미리 종료하는 것이다. 이 방법은 Viola 와 Jones의 물체 인식 프레임워크에 소개되어 있다.에 소개되어있다. 여기서는 음성 판정의 결과가 양성 판정의 결과보다 현저하게 작아지면 음성 결과들을 제외하고 연산을 수행한다. 각 반복 단계에서 절반의 음성 샘플이 연산에서 제외된다면 전체 분류기에서 연산을 수행하는 항목들은 아주 적어질 것이다. 이를 일반화시키면 원하는 거짓 양성이나 거짓 음성 비율을 달성할 수 있도록 각 단계에서 음성 결과들을 제거하는 한계치를 정할 수 있다.

통계학에서 AdaBoost를 사용할 때에 빠른 종료 기법은 과적합(overfitting)을 방지하기 위해서 쓰인다. 훈련에 사용되는 데이터 이외에 검증을 위한 데이터를 따로 준비하고, 훈련이 진행됨에 따라 검증 데이터의 정확도를 같이 확인한다. 만일 과적화가 일어났다면 훈련 데이터에 대한 판별의 정확도는 더 좋아지지만 검증 데이터에 대한 정확도는 오히려 낮아지게 된다. 이 시점을 기준으로 빠른 종료를 하게 된다.

전체 보정형 알고리즘(Totally Corrective Algorithm)

가파른 경사를 사용하는 AdaBoost화 기법에서 $\alpha _{t}$는 각 계층 t에서 테스트 오류를 최소화하도록 정해진다. 그리고 그 다음 계층은 현재 계층과 최대한 독립적이다 라고 할 수 있다. 이 말인 즉슨 $\alpha _{t+1}$과 $\alpha _{t}$이 비슷할 확률이 낮다는 것을 의미한다. 하지만 $\alpha _{t+1}$이 그 전에 등장하였던 $\alpha _{t-1},\alpha _{t-2}...$ 들과 비슷할 수는 있다. LP부스트 등의 전체 보정형 알고리즘에서는 각 단계에서의 최적화 값이 그 전에 등장한 모든 단계의 결과와 독립이 되도록 최적화가 진행된다. 이는 퇴각 적합화(backfitting)이나 선형 계획법 등을 이용해서 이루어질 수 있다.

가지치기 (전지 작업, Pruning)

가지치기는 낮은 성능을 내는 약한 분류기를 미리 제거하는 것이다. 이는 가속화 분류기의 연산 속도 및 메모리 사용량을 줄여준다. 간단하게는 낮은- 가중치, 계수, 경계값, 정확도 - 들을 가지는 분류기를 제거할 수 있고, 이는 전체 보정형 알고리즘과 함께 했을 때 효율적일 수 있다. 이 외에도 분류 결과의 다양성이 가장 높은 분류기를 제거하는 방법이 Margineantu 와 Dietterich에 의하여 제시되었다. 또한 비슷한 결과를 내는 두 분류기가 있을 때 하나를 제거하고 계수를 다른 하나에 몰아주는 방법도 있다.

구현 예제

• AdaBoost 튜토리얼
• AdaBoost in C++ Antonio Gulli의 C++ 구현체.
• icsiboost Boostexter의 오픈소스 구현체.
• JBoost AdaBoost를 포함하는 분류 및 시각화 라이브러리.
• 실수형, 부드러운 AdaBoost를 포함하는 Matlab 구현체.
• AdaBoost의 Matlab 구현체 Archived 2019년 9월 19일 - 웨이백 머신
• 멀티 스레딩을 지원하는 Matlab 구현체 Archived 2014년 5월 22일 - 웨이백 머신
• milk Archived 2013년 9월 17일 - 웨이백 머신 의 파이선 구현체 AdaBoost.
• MPBoost++ 기본적인 AdaBoost에 기반한 C++ 구현체.
• multiboost Multi-class 학습기를 포함하는 빠른 속도의 C++ 구현체.
• NPatternRecognizer Archived 2013년 8월 20일 - 웨이백 머신 서포트 벡터 머신, 인공신경망, K-최근접 이웃 알고리즘 등을 포함하는 C# 구현체.
• OpenCV에 포함된 AdaBoost 구현체
• Into 다양한 AdaBoost 구현들을 포함하는 C++ 구현체 (오픈소스).
• Mallet 자바 구현체.
• adabag adabag: R 구현체.
• Scikit-learn 파이선 구현체.

외부 링크

• “A decision-theoretic generalization of on-line learning and an application to boosting”. 《Journal of Computer and System Sciences》 55. 1997. doi:10.1006/jcss.1997.1504. CiteSeerX: 10.1.1.32.8918:  original paper of Yoav Freund and Robert E.Schapire where AdaBoost is first introduced.
• “Boosting.org”:  a site on boosting and related ensemble learning methods
• “AdaBoost” (PDF):  presentation summarizing AdaBoost (see page 4 for an illustrated example of performance).
• “AdaBoost example”. 2016년 3월 4일에 원본 문서에서 보존된 문서. 2015년 4월 29일에 확인함:  presentation showing an AdaBoost example.
• Freund; Schapire (1999). “A Short Introduction to Boosting” (PDF):  introduction to AdaBoost
• “An applet demonstrating AdaBoost”. 2009년 3월 9일에 원본 문서에서 보존된 문서. 2015년 4월 29일에 확인함. 
• Polikar, R. (2006). “Ensemble Based Systems in Decision Making” (PDF). 《IEEE Circuits and Systems Magazine》 6 (3): 21–45:  a tutorial article on ensemble systems including pseudocode, block diagrams and implementation issues for AdaBoost and other ensemble learning algorithms.