Boosting 1 Implementation of AdaBoost The script ’adaboost.m’ contains an incomplete code for running AdaBoost on a synthetic example. It generates a training set (Xtrain, Ytrain) and a testing set (Xtest, Ytest) sampled from the same distribution, where X ∈ R 2 are the feature values and Y ∈ {−1, 1} are the labels. The goal of the exercise is to train a strong classifier from a family of weak classifiers using the AdaBoost algorithm on the dataset (Xtrain, Ytrain), in order to predict the labels of the testing set Xtest. The proposed weak classifiers are decision stumps, defined as f(x) = s(2[Xd θ] − 1), where d is the feature dimension along which the decision is taken, [·] is 1 if · is true and 0 otherwise, θ is the threshold applied along the dimension d, and s ∈ {−1, 1} is the polarity of the decision stump (i.e. which side of the threshold corresponds to which label). The AdaBoost algorithm iterates the following steps: • Find ˆf = arg minf ?(f), where ?(f) = P i wPi[yi6=f(xi)] i wt i . • Update the weights: wi ←− wi Z exp(−αyif(xi)), where α = 1 2 log 1−? ? . • Update the strong classifier: F ←− F + αf The optimization of the weak classifiers is already implemented, as well as the computation of the training and testing errors. Your tasks for this exercise are the following (see the ’TODO’ comments in the script ’adaboost.m’): 1. Compute the parameter α and the updated weights w within the boosting loop (second step of the algorithm above). 2. Plot the testing set Xtest, displaying the points with a different color for each label (e.g.red for Y = −1, blue for Y = +1). Use two different plots: one with the true labels Ytest, and one with the labels predicted by your boosted classifier (F), and compare the two plots. 3. Plot the evolution of the training error and testing error during 100 iterations and report what you observe. 1
