Simpler AdaBoost - 2

AdaBoost and the Super Bowl of Classifiers

A Tutorial Introduction to Adaptive Boosting

 

Raúl Rojas

Computer Science Department

Freie Universität Berlin

Christmas 2009

 

Abstract

This note provides a gentle introduction to the AdaBoost algorithm

used for generating strong classifiers out of weak classifiers. The mathe-

matical derivation of the algorithm has been reduced to the bare essentials.

 

So, what can we glean from the above formula? C(x_i) is the collective opinion of eleven experts on x_i. For an input vector x_i, each classifier outputs its opinion of either ‘-1’ or ‘1’.  Each expert’s opinion is multiplied by the corresponding ‘α’. At this point it is unclear what α will be like.  The formula says it’s the weight(importance), so it is likely that it’s a positive number. But it can also be a negative. For instance, if the expert number two (k₂) reliably makes wrong decisions, then its weight can be significant negative value.  Also we do not know if the α’s will remain constant for different input patterns x_j, ( j≠i). 

Let’s assume all the classifiers have the same weight of ‘1’. Then C(x_i) can be any odd integer between ‘-11’ to ‘11’.  Since ‘0’ is not possible, there can’t be a tie and so collective decision of whether “yes”(+1) or “no” (-1) can always be determined by Sign(C(x_i)).   

Strong classifiers are the reliable ones, and the weak classifiers are those that classifiy a little better than a guess. So, the AdaBoost algorithm will show us how to reach more reliable classification decision from collective(ensemble) decisions of many but individually not-so-reliable weak classifiers. Here, we talk about a case where we can have only a finite number (L) of classifiers. We may think that the more classifiers we muster, the better the overall classification. That isn’t so. A runaway “collective intelligence” isn’t happening here.