A decision-theoretic generalization of on-line learning and an application to boosting

논문제목: A decision-theoretic generalization of on-line learning and an application to boosting

 

본 논문에서 저자는 각 weak learner들에게서 나온 prediction을 통해 효율적인 boosting을 제안 한다. 각각의 prediction의 가치를 어느 정도로 두느냐에 초점을 맞춘다. On-line Allocation of Resources라는 모델을 가지고 문제 정의를 한다. Online Allocation model에는 agent와 strategy, options, time step, distribution over strategies, 그리고 loss로 이루어져 있다. 기본적으로 각 learner에게 독립적인 가중치를 주기 위해서 Hedge 알고리즘을 도입한다. 각 time step 마다 normalized weight을 probability로 사용한다. 각 strategy는 각각의 loss를 계산하고, 이는 가중합 되어 업데이트에 사용된다. 이때 함수 U에 loss를 넣어 가중합을 하는데, 여기서 U는 [0,1] -> [0,1] 를 만족시키는 아무 함수를 써도 무방하다. 기존의 boosting 방식들은 기존에 지정해주어야 할 hyperparameter가 너무 많고, 가장 성능이 좋지 않은 prediction에 의존하여 성능 향상이 이루어 진다는 단점이 있었다. 이를 해결하기 위해, 본 논문에서는 Adaboost를 제안하였다. 각 learner는 각각의 베타의 반비례하는 가중을 가지며, 이는 error와 비례한다. 만약 error가 0.5라면, 이는 랜 덤 추측과 같은 확률을 가지며, time step이 쓰이지 않는다. Error가 0.5보다 작다면, error에 비례하 게 가중합을 하고, weight는 error와 반비례하게 vote한다. 0.5보다 크다면, inverse vote를 가진다. Majority boosting과 다르게, Adaboost는 각 weak learner의 probabilistic prediction을 가지고 학습 한다.