Exercise about Boosting in postscript and pdf format.

Here are the two graphs and some clarification:

Figure 1: Boosting with minimum weighted error to select h_t
Figure 2: Boosting with weighted info-gain (by Vivek).

I have implemented adaboost with stumps myself, here are some clarifications:

• I did not actually use the information gain criterion: you can simply check the (weighted by D) training error for each possible stump
• stumps *will* be repeated many times. In the example I ran *20* rounds of boosting, and there are only 4 attributes
• 3 rounds of boosting won't actually reduce the error on the training set at all in the example I gave you
• the figures above shows the combined classifier training error (green), the weak classifier errors (black), and the theoretical bound (red). Green should be, in theory, always below red.
• the weak classifier errors will actually never be zero, and we will never have infinite weight: they simply can't fit the training data. The *combined* classifier error should go to zero, though.
• this is *way* simpler to implement than decision trees. I have one matlab script with about 60 lines of code. Evaluating a stump is 10 lines of code.

Anyway, I gained a lot more insight into boosting by actually implementing
it and plotting this graph.