Example of AdaBoostingThe training data:index: 0 1 2 3 4 5 6 7 8 9x value: 0 1 2 3 4 5 6 7 8 9y value: 1 1 1 -1 -1 -1 1 1 1 -1The weak learner produces hypotheses of the form: x < v, or x > v. The threshold v isdetermined to minimize the probability of error over the entire data. (No sampling.)Running the algorithm.We start with the following probabilities:p0p1p2p3p4p5p6p7p8p90.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1t = 1. The best threshold is between 2 and 3.h1(x) = I(x < 2.5)1= 0.3α1= 0.423649qi= 1.52753 for wrong, 0.654654 for rightUpdating the probabilities:index: 0 1 2 3 4 5 6 7 8 9correct: y y y y y y n n n yold pi0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1pre-normalized pi.06547 .06547 .06547 .06547 .06547 .06547 .15 .15 .15 .06547Z1= 0.916515new pi.07143 .07143 .07143 .07143 .07143 .07143 .16667 .16667 .16667 .07143f1(x) = 0.423649 I(x < 2.5), 3 mistakest = 2. Now a threshold between 2 and 3 gives error of 0.5, the threshold between 5 and 6 gives0.28, the threshold between 8 and 9 gives 0.214, best.h2(x) = I(x < 8.5)2= 0.214α2= 0.6496Updating the probabilities:index: 0 1 2 3 4 5 6 7 8 9correct: y y y n n n y y y ypre-normalized pi.037 .037 .037 .137 .137 .137 .087 .087 .087 .037Z2= 0.82new pi.045 .045 .045 .167 .167 .167 .106 .106 .106 .045f2(x) = 0.423649 I(x < 2.5) + 0.6496 I(x < 8.5), 3 mistakest = 3. The best threshold is between 5 and 6.h3(x) = I(x > 5.5)3= 0.1818α3= 0.7520Updating the probabilities:index: 0 1 2 3 4 5 6 7 8 9correct: n n n y y y y y y npre-normalized pi.0964 .0964 .0964 .078 .078 .078 .05 .05 .05 .0964Z3= 0.77139new pi.125 .125 .125 .102 .102 .102 .064 .064 .064 .125f3(x) = 0.423649 I(x < 2.5) + 0.6496 I(x < 8.5) + 0.752 I(x > 5.5), 0
View Full Document