7.9 AdaBoost example.

In this exercise we consider a concrete example that consists of eight training points and eight weak classiers.

(a) Dene an mn matrix M where Mij = yihj(xi), i.e., Mij = +1 if training example i is classied correctly by weak classier hj , and ????1 otherwise. Let dt;t 2 Rn, kdtk1 = 1 and dt;i (respectively t;i) equal the ith component of dt (respectively t). Now, consider AdaBoost as described in gure 7.7 and dene M as below with eight training points and eight weak classiers.
M = 0 BBBBBBBBBBBBBB@
????1 1 1 1 1 ????1 ????1 1 ????1 1 1 ????1 ????1 1 1 1 1 ????1 1 1 1 ????1 1 1 1 ????1 1 1 ????1 1 1 1 1 ????1 1 ????1 1 1 1 ????1 1 1 ????1 1 1 1 1 ????1 1 1 ????1 1 1 1 ????1 1 1 1 1 1 ????1 ????1 1 ????1 1 CCCCCCCCCCCCCCA Assume that we start with the following initial distribution over the datapoints:
d1 = 
3 ???? p5 8 ;
3 ???? p5 8 ;
1 6 ;
1 6 ;
1 6 ;
p5 ???? 1 8 ;
p5 ???? 1 8 ; 0 
>
Compute the rst few steps of the AdaBoost algorithm using M, d1, and tmax = 7. What weak classier is picked at each round of boosting? Do you notice any pattern?

(b) What is the L1 norm margin produced by AdaBoost for this example?

(c) Instead of using AdaBoost, imagine we combined our classiers using the following coecients: [2; 3; 4; 1; 2; 2; 1; 1]  1 16 . What is the margin in this case? Does AdaBoost maximize the margin?