에이다부스트 문서 원본 보기

{{위키데이터 속성 추적}}
{{기계 학습}}

'''에이다부스트'''({{llang|en|'''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는 가속화 분류기를 훈련시키는 한 방법을 이르는 말이다. 가속 분류기는 다음과 같은 형태로 표현된다.

:<math>F_T(x) = \sum_{t=1}^T f_t(x)\,\!</math>

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

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

:<math>E_t = \sum_i E[F_{t-1}(x_i) + \alpha_t h(x_i)]</math>

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

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

==유도 과정==
<math>y_i \in \{-1, 1\}</math>를 가지고 있는 데이터 집합 <math>\{(x_1, y_1), \ldots, (x_N, y_N)\}</math>과 각 분류기가 각 항목에 대한 분류<math>k_j(x_i) \in \{-1, 1\}</math>를 출력하는 약한 분류기의 집합 <math>\{k_1, \ldots, k_L\}</math>을 가지고 있다고 가정하자. <math>m-1</math>번째 반복 단계 이후 우리의 가속화 분류기는 다음과 같은 형태의 약한 분류기의
[[선형결합|선형 결합]](linear combination)으로 표현된다.

:<math>C_{(m-1)}(x_i) = \alpha_1k_1(x_i) + \cdots + \alpha_{m-1}k_{m-1}(x_i)</math>

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

:<math>C_{m}(x_i) = C_{(m-1)}(x_i) + \alpha_m k_m(x_i)</math>

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

:<math>E = \sum_{i=1}^N e^{-y_i C_m(x_i)}</math>

<math>m > 1</math>에 대하여 <math>w_i^{(1)} = 1</math> , <math>w_i^{(m)} = e^{-y_i C_{m-1}(x_i)}</math> 라 두면, 아래와 같은 식을 얻는다.

:<math>E = \sum_{i=1}^N w_i^{(m)}e^{-y_i\alpha_m k_m(x_i)}</math>

우리는 이 식을 <math>k_m</math>에 의해 정확하게 분류된 데이터 포인트(즉, <math>y_i k_m(x_i) = 1</math>)와 잘못 분류된 데이터 포인트(즉, <math>y_i k_m(x_i) = -1</math>)로 아래와 같이 나눌 수 있다.

:<math>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})</math>

이 식의 우변에서 <math>k_m</math>에 의존하는 부분은 <math>\sum_{y_i \neq k_m(x_i)} w_i^{(m)}</math>뿐이기 때문에, <math>E</math>를 최소화하는 <math>k_m</math>이 <math>\sum_{y_i \neq k_m(x_i)} w_i^{(m)}</math>도 최소한다는 것을 알 수 있다. 즉, <math>k_m</math>이 가중치를 고려한 가장 낮은 오류를 가진 약한 분류기(가중치 <math>w_i^{(m)} = e^{-y_i C_{m-1}(x_i)}</math>를 가진 것)인 것이다.

조금 전에 결정한<math>k_m</math>를 가진 <math>E</math>를 최소화하는 가중치 <math>\alpha_m</math>를 결정하기 위하여 우리는 아래와 같은 미분을 수행한다.

:<math>\frac{d E}{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}</math>

이를 0으로 놓고 <math>\alpha_m</math>에 대하여 풀면 다음과 같은 식이 된다.

:<math>\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)}}</math>

약한 분류기의 가중치가 고려된 오류율을 <math>\epsilon_m = \frac{\sum_{y_i \neq k_m(x_i)} w_i^{(m)}} {\sum_{i=1}^N w_i^{(m)}}</math>와 같이 계산할 수 있고, 따라서 다음 식이 성립한다.

:<math>\alpha_m = \frac{1}{2}\ln \frac{1 - \epsilon_m}{\epsilon_m}</math>

이렇게 함으로써 우리는 AdaBoost 알고리즘을 유도하였다. 각 반복 단계에서, 가중치가 고려된 총 오류<math>\sum_{y_i \neq k_m(x_i)} w_i^{(m)}</math>를 최소화하는 분류기 <math>k_m</math>을 선택하고, 이를 오류율 <math>\epsilon_m = \frac {\sum_{y_i \neq k_m(x_i)} w_i^{(m)}} {\sum_{i=1}^N w_i^{(m)}}</math>를 계산하는데 이용하고, 이를 가중치<math>\alpha_m = \frac{1}{2}\ln \frac{1 - \epsilon_m}{\epsilon_m}</math>를 계산하는데 이용하며, 이를 마지막으로 가속화 분류기 <math>C_{m-1}</math> to <math>C_{m} = C_{(m-1)} + \alpha_m k_m</math>를 개선하는데 이용한다.

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

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

지수오차함수를 사용하면 최종적응모델의 오차는 <math>e^{\sum_i -y_i f(x_i)} = \prod_i e^{-y_i f(x_i)}</math>와 같이 각 단계에서의 오차의 곱과 같다. 따라서 AdaBoost 알고리즘에서 가중치 갱신은 각 단계 후에 <math>F_t(x)</math>의 오차를 재계산하는 것과 같다고 볼 수 있다.

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

:<math>\phi(y,f(x)) = \begin{cases}
-4y f(x)  & \mbox{if } \, y f(x) < -1, \\
(y f(x) - 1)^2 &\mbox{if } \, -1 \le y f(x) \le 1, \\
0 &\mbox{if } \, y f(x) > 1
\end{cases}</math>

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

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

가속화 과정은 함수의 [[볼록 집합]](convex set)에 대한 볼록손실함수(convex loss function)의 최소화 과정으로 볼 수 있다.<ref>T. Zhang, "Statistical behavior and consistency of classification methods based on convex risk minimization", Annals of Statistics 32 (1), pp. 56-85, 2004.</ref> 구체적으로는, AdaBoost는 지수 함수 <math>\sum_i \phi(i,y,f) = \sum_i e^{-y_i f(x_i)}</math>을 통해 손실을 최소화하며, 로지스틱 가속은 [[로지스틱 회귀|로그회귀]](logistic regression) <math>\sum_i \phi(i,y,f) = \sum_i \ln\left(1+e^{-y_i f(x_i)}\right)</math>를 통해 최소화를 수행한다.

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

==알고리즘 예시 (불연속적 AdaBoost)==
다음과 같은 조건일 때:
* 샘플 <math>x_1 \dots x_n</math>
* 목표 결과값 <math>y_1 \dots y_n, y \in \{-1, 1\}</math>
* 초기 가중치 <math>w_{1,1} \dots w_{n,1}</math>는 <math>\frac{1}{n}</math>으로 설정
* 오차함수 <math>E(f(x), y, i) = e^{-y_i f(x_i)}</math>
* 약한 학습기 <math>h\colon x \rightarrow [-1, 1]</math>
<math>t=1 \dots T</math>에 대하여:
* <math>f_t(x)</math>의 선택:
** <math>\epsilon_t</math>을 최소화하는 약한 학습기 <math>h_t(x)</math>를 찾는다. 이 때 잘못 분류된 오차의 가중합은 다음과 같다. <math>\epsilon_t = \sum_i w_{i,t}E(h_t(x), y, i) </math>
** <math>\alpha_t = \frac{1}{2} \ln \left(\frac{1-\epsilon_t}{\epsilon_t}\right)</math>
* 총합에 추가:
** <math>F_t(x) = F_{t-1}(x) + \alpha_t h_t(x)</math>
* 가중치 갱신:
** <math>w_{i,t+1} = w_{i,t} e^{-y_i \alpha_t h_t(x_i)}</math> (모든 <math>i</math>에 대하여)
** <math>w_{i,t+1}</math>의 재정규화 (<math>\sum_i w_{i,t+1} = 1</math>)
** (추가: 모든 단계에서 <math>\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}}</math>는 항상 성립하며, 이를 이용해 가중치 갱신과정을 간소화할 수 있다.)

===가중치 {{수학|''&alpha;<sub>t</sub>''}}의 선택===
{{수학|''&alpha;<sub>t</sub>''}}는 불연속적 AdaBoost에서 지수오차함수를 분석적으로(analytically) 최소화하는 값으로 정해진다.<ref name="ss">{{저널 인용 | id = {{citeseerx|10.1.1.33.4002}} | title = Improved Boosting Algorithms Using Confidence-rated Predictions | first1 = Robert | last1 = Schapire | first2 = Yoram | last2 = Singer | year = 1999}}</ref>

<math>min \sum_i w_i e^{-y_i h_i \alpha_t}</math>

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

<math>
\begin{align}
\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{align}
</math>

위식을 <math>\alpha_t</math>에 대하여 미분하고 상한값의 최솟값을 구하기 위해 0으로 설정한다.

<math>
\begin{align}
\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{align}
</math>

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

==변형==

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

이산 AdaBoost에서 쓰이는 분류기는 그 결과를 <math>\{-1, 1\}</math> 의 형태로 나타낸다. 실수 AdaBoost에서는 분류의 결과를 각 클래스에 포함될 확률  <math>p(x) = P(y=1 | x)</math> 로서 나타낸다. 이는 <math>x</math> 라는 원소가 <math>y</math> 클래스에 포함될 확률을 나타낸다<ref name="fht">{{저널 인용 | id = {{citeseerx|10.1.1.51.9525}} | title = Additive Logistic Regression: A Statistical View of Boosting | first1 = Jerome | last1 = Friedman | first2 = Trevor | last2 = Hastie | first3 = Robert | last3 = Tibshirani | year = 1998}}</ref>. Friedman, Hastie 그리고 Tibshirani는 고정된 <math>p(x)</math>에 대하여 <math>e^{-y\left(F_{t-1}(x)+f_t(p(x))\right)}</math>를 최소화하는 <math>f_t(p(x))</math>를 유도하였다(최소제곱법).

:<math>f_t(x) = \frac{1}{2} \ln\left(\frac{x}{1-x}\right)</math>.

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

===로지스틱 부스트(LogitBoost)===

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

:<math>z_t = \frac{y^* - p_t(x)}{2 p_t(x)(1 - p_t(x))}</math>

:<math>p_t(x) = \frac{e^{F_{t-1}(x)}}{e^{F_{t-1}(x)}+e^{-F_{t-1}(x)}}</math>

:<math>w_{t} = p_t(x)(1 - p_t(x))</math>

:<math>y^* = \frac{y+1}{2}</math>.

<math>z_t</math>는 [[뉴턴의 방법]]를 사용하여 <math>t</math>에 대한 [[가능도|로그 가능도]]의 오류를 최소화하는 항이다.
또한 <math>f_t</math>는 최소제곱법에 의해 <math>z_t</math>를 최소화하는 약한 학습기이다.

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

===관대한 에이다부스트(Gentle AdaBoost)===
이전의 가속 방법들은 각 반복 과정에서 오류를 최소화하는 <math>f_t</math>를 구하고 이를 이용해서 전체 오류를 최소화하였다 ([[탐욕 알고리즘]]).
반면에 부드러운 AdaBoost에서는 반복 횟수를 제한한다.

<math>f_t</math>는 <math>\sum_i w_{t,i} (y_i-f_t(x_i))^2</math>를 최소화하도록 정해진다. 여기서 다른 매개변수는 사용되지 않는다. 그렇기 때문에 약한 학습기가 완벽한 분류를 할 수 있는 상황에서 부드러운 AdaBoost은 정확한 <math>y</math> 값을 구할 수 있다. 한편 기울기 기반의 알고리즘은 <math>f_t(x) = \alpha_t h_t(x)</math>의 <math>\alpha_t</math>를 무한대에 가깝게 정하게 되고 이는 분류의 정확도를 떨어뜨리게 된다. 관대한 에이다부스트(Gentle AdaBoost)은 이러한 측면에서 Schapire 와 Singer가 지적했듯이 <math>\alpha_t = \infty</math>의 경우에 발생할 수 있는 성능 저하를 보완할 수 있다.<ref name="ss"/><ref name="fs">{{웹 인용| url = http://www.site.uottawa.ca/~stan/csi5387/boost-tut-ppr.pdf | title = A Short Introduction to Boosting | last1 = Freund | last2 = Schapire | year = 1999 | postscript = : }}</ref>

===빠른 종료(Early Termination)===
가속화 분류기의 속도를 올리는 방법 중 하나는 분류 작업을 끝까지 진행하지 않고 일정 신뢰 구간을 확보한 시점에서 미리 종료하는 것이다. 이 방법은 Viola 와 Jones의 물체 인식 프레임워크에 소개되어 있다.<ref>{{저널 인용 | id = {{citeseerx|10.1.1.10.6807}} | title = Rapid Object Detection Using a Boosted Cascade of Simple Features | first1 = Paul | last1 = Viola | first2 = Robert | last2 = Jones | year = 2001}}</ref>에 소개되어있다. 여기서는 음성 판정의 결과가 양성 판정의 결과보다 현저하게 작아지면 음성 결과들을 제외하고 연산을 수행한다. 각 반복 단계에서 절반의 음성 샘플이 연산에서 제외된다면 전체 분류기에서 연산을 수행하는 항목들은 아주 적어질 것이다. 이를 일반화시키면 원하는 [[거짓 양성]]이나 [[거짓 음성]] 비율을 달성할 수 있도록 각 단계에서 음성 결과들을 제거하는 한계치를 정할 수 있다.<ref>{{저널 인용 | title = Optimizing cascade classifiers. | last1 = McCane | first1 = Brendan | first2 = Kevin | last2 = Novins | first3 = Michael | last3 = Albert | year = 2005}}</ref>

통계학에서 AdaBoost를 사용할 때에 빠른 종료 기법은 과적합(overfitting)을 방지하기 위해서 쓰인다.<ref>{{서적 인용|author=Trevor Hastie, Robert Tibshirani, Jerome|title=The Elements of Statistical Learning: Data Mining, Inference, and Prediction|year=2009|publisher=Springer|location=New York|isbn=978-0-387-84858-7|url=http://statweb.stanford.edu/~tibs/ElemStatLearn/download.html|edition=2nd|확인날짜=2015-04-29|보존url=https://web.archive.org/web/20150313093720/http://statweb.stanford.edu/~tibs/ElemStatLearn/download.html|보존날짜=2015-03-13|url-status=dead}}</ref>
훈련에 사용되는 데이터 이외에 검증을 위한 데이터를 따로 준비하고, 훈련이 진행됨에 따라 검증 데이터의 정확도를 같이 확인한다. 만일 과적화가 일어났다면 훈련 데이터에 대한 판별의 정확도는 더 좋아지지만 검증 데이터에 대한 정확도는 오히려 낮아지게 된다. 이 시점을 기준으로 빠른 종료를 하게 된다.

===전체 보정형 알고리즘(Totally Corrective Algorithm)===
가파른 경사를 사용하는 AdaBoost화 기법에서 <math>\alpha_t</math>는 각 계층 ''t''에서 테스트 오류를 최소화하도록 정해진다. 그리고 그 다음 계층은 현재 계층과 ''최대한'' [[독립 (확률론)|독립]]적이다 라고 할 수 있다<ref>{{저널 인용 | title = Adaboost with Totally Corrective Updates for Fast Face Detection | first1 = Jan | last1 = Šochman | first2 = Jiří | last2 = Matas | isbn=0-7695-2122-3 | year = 2004}}</ref>. 이 말인 즉슨 <math>\alpha_{t+1}</math>과 <math>\alpha_t</math>이 비슷할 확률이 낮다는 것을 의미한다. 하지만 <math>\alpha_{t+1}</math>이 그 전에 등장하였던 <math>\alpha_{t-1}, \alpha_{t-2} ...</math> 들과 비슷할 수는 있다. LP부스트 등의 전체 보정형 알고리즘에서는 각 단계에서의 최적화 값이 그 전에 등장한 모든 단계의 결과와 독립이 되도록 최적화가 진행된다. 이는 퇴각 적합화(backfitting)이나 [[선형 계획법]] 등을 이용해서 이루어질 수 있다.

===가지치기 (전지 작업, Pruning)===
가지치기는 낮은 성능을 내는 약한 분류기를 미리 제거하는 것이다. 이는 가속화 분류기의 연산 속도 및 메모리 사용량을 줄여준다. 간단하게는 낮은- 가중치, 계수, 경계값, 정확도 - 들을 가지는 분류기를 제거할 수 있고, 이는 전체 보정형 알고리즘과 함께 했을 때 효율적일 수 있다. 이 외에도 분류 결과의 다양성이 가장 높은 분류기를 제거하는 방법이 Margineantu 와 Dietterich에 의하여 제시되었다<ref>{{저널 인용 | id = {{citeseerx|10.1.1.38.7017}} | title = Pruning Adaptive Boosting | first1 = Dragos | last1 = Margineantu | first2 = Thomas | last2 = Dietterich | year = 1997}}</ref>. 또한 비슷한 결과를 내는 두 분류기가 있을 때 하나를 제거하고 계수를 다른 하나에 몰아주는 방법도 있다<ref>{{저널 인용 | title = On the Boosting Pruning Problem | first1 = Christino | last1 = Tamon | first2 = Jie | last2 = Xiang | year = 2000}}</ref>.

== 같이 보기 ==
* [[배깅]]
* [[그라디언트 부스팅]]
== 각주 ==
{{각주}}

==구현 예제==
* [http://www.inf.fu-berlin.de/inst/ag-ki/adaboost4.pdf AdaBoost 튜토리얼]
* [http://codingplayground.blogspot.com/2009/03/adaboost-improve-your-performance.html AdaBoost in C++] Antonio Gulli의 C++ 구현체.
* [http://code.google.com/p/icsiboost/ icsiboost] Boostexter의 오픈소스 구현체.
* [http://jboost.sourceforge.net JBoost] AdaBoost를 포함하는 분류 및 시각화 라이브러리.
* [https://web.archive.org/web/20110817114237/http://graphics.cs.msu.ru/en/science/research/machinelearning/adaboosttoolbox 실수형, 부드러운 AdaBoost를 포함하는 Matlab 구현체.]
* [http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=21317&objectType=file AdaBoost의 Matlab 구현체] {{웹아카이브|url=https://web.archive.org/web/20190919023724/http://www.mathworks.com/matlabcentral/fileexchange/loadFile.do?objectId=21317&objectType=file}}
* [https://sites.google.com/site/carlosbecker/resources/gradient-boosting-boosted-trees 멀티 스레딩을 지원하는 Matlab 구현체] {{웹아카이브|url=https://web.archive.org/web/20140522125421/https://sites.google.com/site/carlosbecker/resources/gradient-boosting-boosted-trees}}
* [http://luispedro.org/software/milk milk] {{웹아카이브|url=https://web.archive.org/web/20130917063455/http://luispedro.org/software/milk}} 의 파이선 구현체 [https://web.archive.org/web/20120711210335/http://packages.python.org/milk/adaboost.html AdaBoost].
* [https://web.archive.org/web/20110604124807/http://www.esuli.it/mpboost MPBoost++] 기본적인 AdaBoost에 기반한 C++ 구현체.
* [https://web.archive.org/web/20150419050429/http://www.multiboost.org/ multiboost] Multi-class 학습기를 포함하는 빠른 속도의  C++ 구현체.
* [http://npatternrecognizer.codeplex.com/ NPatternRecognizer ] {{웹아카이브|url=https://web.archive.org/web/20130820072633/http://npatternrecognizer.codeplex.com/}} [[서포트 벡터 머신]], [[인공신경망]], [[K-최근접 이웃 알고리즘]] 등을 포함하는 C# 구현체.
* [https://web.archive.org/web/20150319154944/http://docs.opencv.org/modules/ml/doc/boosting.html OpenCV에 포함된 AdaBoost 구현체]
* [https://github.com/topiolli/into Into] 다양한 AdaBoost 구현들을 포함하는 C++ 구현체 (오픈소스).
* [http://mallet.cs.umass.edu/ Mallet] 자바 구현체.
* [https://web.archive.org/web/20150505023754/http://cran.r-project.org/web/packages/adabag/ adabag] adabag: R 구현체.
* [https://web.archive.org/web/20150426104718/http://scikit-learn.org/dev/modules/ensemble.html#AdaBoost Scikit-learn] 파이선 구현체.

== 외부 링크 ==
* {{저널 인용| id = {{citeseerx|10.1.1.32.8918}} | title = A decision-theoretic generalization of on-line learning and an application to boosting | journal = Journal of Computer and System Sciences | volume = 55 | year = 1997 | postscript = : | doi = 10.1006/jcss.1997.1504 }} original paper of Yoav Freund and Robert E.Schapire where AdaBoost is first introduced.
* {{웹 인용| url = http://www.boosting.org | title = Boosting.org | postscript = : }} a site on boosting and related ensemble learning methods
* {{웹 인용| url = http://cmp.felk.cvut.cz/~sochmj1/adaboost_talk.pdf | title = AdaBoost | postscript = : }} presentation summarizing AdaBoost (see page 4 for an illustrated example of performance).
* {{웹 인용 | url = https://www.flll.jku.at/sites/default/files/Adaboost.odp | title = AdaBoost example | postscript = : | 확인날짜 = 2015-04-29 | 보존url = https://web.archive.org/web/20160304060802/https://www.flll.jku.at/sites/default/files/Adaboost.odp | 보존날짜 = 2016-03-04 | url-status = dead }} presentation showing an AdaBoost example.
* {{웹 인용| url = http://www.site.uottawa.ca/~stan/csi5387/boost-tut-ppr.pdf | title = A Short Introduction to Boosting | last1 = Freund | last2 = Schapire | year = 1999 | postscript = : }} introduction to AdaBoost
* {{웹 인용 | url = http://www.cs.ucsd.edu/~yfreund/AdaBoost/index.html | title = An applet demonstrating AdaBoost | 확인날짜 = 2015-04-29 | 보존url = https://web.archive.org/web/20090309101436/http://cs.ucsd.edu/~yfreund/adaboost/index.html# | 보존날짜 = 2009-03-09 | url-status = dead }}
* {{저널 인용 | url = http://engineering.rowan.edu/~polikar/RESEARCH/PUBLICATIONS/csm06.pdf | title = Ensemble Based Systems in Decision Making | first = R. | last = Polikar | work = IEEE Circuits and Systems Magazine | volume = 6 | issue = 3 | pages = 21–45 | year = 2006 | postscript = : }}{{깨진 링크|url=http://engineering.rowan.edu/~polikar/RESEARCH/PUBLICATIONS/csm06.pdf }} a tutorial article on ensemble systems including pseudocode, block diagrams and implementation issues for AdaBoost and other ensemble learning algorithms.

[[분류:알고리즘]]
[[분류:기계 학습]]