GAMBLE 알고리즘

Efficient Multiclass Boosting Classification with Active Learning
- Jian Huang, Seyda Ertekin, Yang Song, Hongyuan Zha, C.Lee Giles

GABMLE - Gentle Adaptive Multiclass Boosting Learning algorithm

Features
- K-class Classification 문제를 여러개의 binary class classification문제로 바꾸는 게 아니라 그대로 적용하여 다룬다.
- 각 iteration마다 오직 하나의 regression function이 fit 되는 것.
- 기본적으로 outlier에 덜 예민하고, unseen data에 강하다는 것.
- Active sample selection을 통해, 더 빠르고 효과적인 prediction이 가능하다.
- 알고리즘 구조가 간결하고 명확하며 쉽다.

기존연구
- 기존에 multiclass classification 을 위해 먼저 제안된 것은 AdaBoost.M1 algorithm.
이것은 기존 AdaBoost의 Indicator function에서의 hk를 바꾼것으로 기존것의 연장선상에 있다. 그리고 AdaBoost.Discrete에서 사용한 binary 용 loss function을 그대로 사용하였기 때문에 AdaBoost.M1은 샘플의 절반이상에서 Misclassification 된다는 단점이 발생하였다. error rate이 1/2보다 커지면 종료되므로 사용 불가. 부적합

- 그뒤에 나온 것이 AdaBoost.M2. Pairwise 전략을 사용해서 multiclass problem을 해결한다. 하지만 weak learner의 설계를 복잡하게 한다는 단점 존재.

- AdaBoost.MH는 M2 대체용으로 등장, 이건 one-against-all 방식으로 k class classification 문제를 k binary classification 문제로 변환하여 사용. Correcting output code를 사용하는 AdaBoost.MO도 존재.

- SAMME와 같은 AdaBoost에 multiclass exponential loss function을 적용한 파생 부스트 알고리즘이 존재하는데, 샘플에 outlier가 많다면, 그것들에 overemphasize하여 결국 inferior한 결과를 끌어내기도 한다는 단점 존재. 그것을 위해 Gentle AdaBoost와 같은 방법이 제안되었지만 이것은 여전히 one-against-all과 가은 전략을 사용한다는 게 단점으로 지적되고 있다.

-Active learning기법을 위해, Query By Committee, QBC가 active learning method로 잘 알려지고 사용되고 있다. 그리하여 QBC와 AdaBoost를 결합한 QBoost가 있는데 이 논문해서는 해당 기법에서의 active sample selection method를 그대로 이용하고, 이를 multiclass로 확장한다.