Adaboost

 

회색 바닥 위에 검은색 점과 흰색 점들이 흩어져 있다고 하자. 이 점들을 몇 단계의 간단한 linear classifier만을 이용하여 분류하는 방법을 생각해 보자.

먼저 바닥에 하나의 직선을 긋고, 직선의 방향벡터를 기준으로 오른쪽에 있는 점은 흰색, 왼쪽에 있는 점은 검은색으로 분류하는 규칙을 정한다. 하나의 직선만으로 이루어진 이러한 분류기를 weak classifier라고 한다.

물론 하나의 직선만으로는 모든 점을 정확히 분류할 수 없다. 직선의 오른쪽에 검은색 점이 있거나 왼쪽에 흰색 점이 있으면 잘못 분류가 이루어진다. 따라서 여러 개의 직선을 후보로 놓고, 분류 오류율이 가장 작은 직선을 첫 번째 분류기로 선택한다. 이러한 약한 분류기는 대부분의 경우 무작위로 흰색과 검은색을 선택하는 것(오류율 약 50%)보다 조금 더 나은 성능을 보인다. AdaBoost는 바로 이러한 오류율이 50%보다 작은 약한 분류기를 여러 개 결합하여 강력한 분류기를 만드는 알고리즘이다.

두 번째 분류기를 만들 때는 첫 번째 분류기의 결과를 그대로 반복해서는 안 된다. 첫 번째 분류기에서 올바르게 분류된 점들의 가중치는 줄이고, 잘못 분류된 점들의 가중치는 증가시킨다. 이렇게 하면 다음 분류기는 이전 단계에서 잘못 분류된 점들에 더 많은 관심을 기울이게 된다. 직관적으로 말하면, 이미 맞게 분류된 점들은 약간 흐리게 표시하고 잘못 분류된 점들은 더욱 진하게 표시하여 다음 직선을 그릴 때 어려운 점들이 더 눈에 띄도록 만드는 것과 같다. 실제 AdaBoost에서는 이러한 효과를 각 샘플에 부여된 weight를 조정함으로써 구현한다.

가중치가 변경된 데이터에 대해 다시 여러 직선을 시도하여 가중 분류오차(weighted classification error)가 가장 작은 직선을 두 번째 분류기로 선택한다. 이후에도 같은 과정을 반복하면 각각 서로 다른 샘플에 집중하여 학습한 여러 개의 약한 분류기를 얻게 된다.

마지막 단계에서는 이 약한 분류기들을 하나로 결합하여 최종 분류기를 만든다. 이때 모든 분류기가 동일한 비중을 갖는 것은 아니다. 분류 성능이 좋은 분류기일수록 더 큰 가중치를 부여하고, 성능이 좋지 않은 분류기일수록 작은 가중치를 부여한다. AdaBoost에서는 분류기의 가중 분류오차를 \(\varepsilon\)이라 할 때, 해당 분류기의 가중치를\[\alpha=\frac12\log\frac{1-\varepsilon}{\varepsilon}\]

로 정한다. 따라서 오류율이 작은 분류기는 큰 가중치를 받아 최종 결정에 더 큰 영향을 미치고, 오류율이 50%에 가까운 분류기는 거의 영향을 미치지 못한다.

최종 분류기는 각 약한 분류기의 출력을 이 가중치만큼 더한 가중합으로 구성되며,

\[F(x)=\sum_{t=1}^{T}\alpha_t h_t(x),\]

최종 분류 결과는

\[H(x)=\operatorname{sign}(F(x))\]

로 결정된다. 이처럼 각각의 약한 분류기는 단독으로는 성능이 높지 않지만, 적절한 가중치를 두어 결합하면 개별 분류기보다 훨씬 높은 정확도를 갖는 strong classifier를 얻을 수 있다.