[Ensemble] Basic Concept of Ensemble Methods, Bagging, Boosting

Ensemble Methods

하나의 classifier가 아니라 여러개의 classifier를 학습한 후, prediction을 aggregate하여 class label을 예측하는 방법이다.

 

General Idea of Ensembel Methods

Why Majority Voting Works?

간단히 생각하기 위해 (uncorrelated) 25개의 classifier가 모두 error rate가 $\epsilon=0.35$라고 하자.

ensemble classifier가 잘못된 분류를 내릴 확률(13개 이상의 classifier가 잘못됨)을 계산해보자. 

\[ P(X \ge 13) = \sum_{i=13}^{25} \dbinom{25}{i} \epsilon^i (1 - \epsilon)^{25-i} \approx 0.06 \]

각 분류기의 error rate가 꽤 높지만, 앙상블 분류기가 잘못된 분류를 내릴 확률은 6%정도로 매우 낮다.

Comparing Ensemble Error

Bagging

앙상블에 있는 각 모델의 가중치는 동일하다.

training set에서 랜덤하게 고른 subset을 이용하여 각 모델을 학습한다.

Random Forests가 대표적인 bagging이다. 

Bagging trainingset sampling and training

Boosting

새로운 모델은 이전 모델의 misclassified instance에 더 가중치를 준다.

bagging보다 더 좋은 accuracy를 갖지만, bagging보다 overfitting의 경향이 더 높다.

AdaBoost가 대표적인 boosting이다.

AdaBoost. Sequential training with instance weight updates

Bagging vs Boosting

위 간단한 설명을 보면 알겠지만, 모델 학습 순서에 차이가 있다.

Bagging은 각 모델이 독립적으로 학습한다.

 

Boosting은 iterative, successive하다. 이전 모델(predecessor)에 영향을 받는다. previous classifier에 따라서 다음 iteration에 어디에 더 focus를 가질지 결정된다.

Boosting은 각 iteration에서 모든 training data를 학습한다. (but with different weights). difficult example에는 더 큰 weight를 갖게된다.