AdaBoost

Udacity의 Machine Learning 강의 중 알고리즘을 스스로 공부하는 파트에서 AdaBoost를 공부하다가 Youtube 강의를 기반으로 해서 여러 글들을 보고 정리한 내용입니다.

 

유튜브 강의

 

Adaboost는 크게 세 가지 Concept로 설명할 수 있습니다. 영상에서는 이전에 했던 Decision Tree나 Random Forest와 비교하여 설명하고 있습니다.

 

첫번째는 Random Forest는 완전히 성장하고, 미리 정해진 깊이가 없는 의사결정나무를 만드는 반면,

AdaBoost는 하나의 Node와 두개의 Leaves를 갖는 Tree를 만듭니다. 이 Tree를 Stump라고 합니다.

AdaBoost는 Stump들로 이루어진 Forest입니다. 물론 개별 Stump들은 좋은 분류기는 아닙니다.

 

Decision Tree는 나무를 만들 때 모든 변수를 사용하지만, AdaBoost의 Stump들은 단 하나씩의 변수만을 사용합니다. 하나의 변수를 사용한 Stump이기 때문에 기술적으로는 약한 분류기(Weak Learner)입니다.

 

두번째로 Random Forest의 나무들은 최종 분류에서 모두가 같은 목소리를 냅니다. Decision Tree들이 내는 모든 결과가 최종 분류를 결정하는데 모두 동일한 영향을 미친다는 것입니다.

 

AdaBoost는 이와 다르게 어떤 Stump는 최종 결정에서 큰 영향을 미치고, 어떤 Stump는 비교적 작은 영향을 미칩니다.

 

세번째로 Random Forest를 구성하는 각각의 Decision Tree들은 독립적으로 생성됩니다. 생성된 순서가 크게 중요하지 않은 것입니다.

 

반면 AdaBoost에서 생성되는 Stump들은 생성순서가 중요합니다. Stump를 만들 때 직전의 Stump의 Error가 관여하기 때문입니다.

 

여기서 Sample Weight가 등장합니다.

처음에는 모든 Sample에 같은 Weight를 부여합니다. 여기서는 8개 Sample이기 때문에 Basic Sample Weight는 1/8.

First Stump가 만들어진 뒤로는 Sample Weight 값이 바뀌면서 다음 Stump가 만들어지는데 영향을 미칩니다.

 

먼저, 각 변수의 Gini Index를 계산합니다. 

 

가장 낮은 Gini Index를 갖는 Weight 변수가 첫번째 Stump를 만드는 변수가 됩니다.

우리는 Weight로 만든 Stump가 최종 Classification을 결정하는데 얼마나 많은 영향을 미칠지 결정해야 합니다.

 

이때 Amount of Say를 사용합니다. Total error를 전체 데이터 중 첫번째 Stump에서 오분류된 데이터의 수라고 하면,

$$Amount\_of\_Say = 1/2log_e(\frac{1-Total Error}{Total Error})$$

 

이렇게 Weight로 만든 첫번째 Stump가 완성됩니다.

 

다음 Stump를 만들기 전에 Sample Weight를 업데이트하고 데이터를 샘플링합니다.

오분류된 데이터의 Sample Weight는 증가시키고, 정분류된 데이터의 Sample Weight는 감소시킵니다.

$$New\_Sample\_Weight(Incorrectly\_Classified) = 1/8 * e^{amount\_of\_say}$$

$$New\_Sample\_Weight(correctly\_Classified) = 1/8 * e^{-amount\_of\_say}$$

 

이론적으로 Sample Weight로 Weighted Gini index를 계산해서 이전 Stump에서 오분류한 데이터를 강조하여 이번에는 제대로 분류하도록 할 수 있지만, 다른 방법을 사용합니다.

 

0-1 사이의 숫자를 랜덤하게 뽑고, Sample Weight들의 누적합 구간 중 우리가 뽑은 숫자가 위치하는 데이터를 뽑아서 새로운 데이터에 추가합니다. 이때 복원추출로 같은 데이터가 여러번 추출될 수 있습니다. 강의에서는 "Use Sample Weights like a distribution"이라고 표현합니다. Sample Weight가 크다면 다른 데이터보다 누적합의 구간이 크기 때문에 Sampling에서 선택될 확률이 높습니다.

 

그 다음 최종 Classification에 대한 이야기를 합니다.

분류 결과별로 Amounts of Say의 합을 비교해서, 더 큰 분류결과를 최종적으로 선택합니다.

 

정리하자면,

1. AdaBoost는 많은 "Weak Learners"를 합쳐서 분류에 사용합니다. 이들은 거의 Stump들이다.

2. 몇몇 Stump들은 다른 Stump들보다 분류에 더 큰 영향을 미친다.

3. 모든 Stump들은 이전에 만들어진 Stump들의 오류를 고려하여 만들어진다.