Adaboost AlgorithmGiven: N samples {x, yi,i = 1, ..., N, where yi = {+1, -1]),andsomewayofconstructingweak(orbase)classifiersInitialize weights wi(i) = for every training sampleFor t = 1 to T1.Train a weak classifier ht(x)using current weights Wt(i), byminimizingtheweightedclassificationerror1Wt(i)I[yi + ht(xi)]Et =1Et2.Computecontributionforthisclassifierβt =in2Et3.Updateweights ontraining pointsWt+1(i) α Wt(i)e-βtyiht(xi)and normalize them such that Z; Wt+1(i) = 19/22/2026PATTERNRECOGNITION6
Adaboost Algorithm Given: N samples 𝑥𝑖 , 𝑦𝑖 , 𝑖 = 1,. , 𝑁, where 𝑦𝑖 = {+1,−1}, and some way of constructing weak (or base) classifiers Initialize weights 𝑤1 𝑖 = 1 𝑁 for every training sample For t = 1 to T 1. Train a weak classifier ℎ𝑡 (𝒙) using current weights 𝑤𝑡 (𝑖), by minimizing the weighted classification error 2. Compute contribution for this classifier 3. Update weights on training points and normalize them such that σ𝑖𝑤𝑡+1 (𝑖) = 1 9/22/2026 PATTERN RECOGNITION 6 𝜖𝑡 = 𝑖 𝑤𝑡 𝑖 𝕀[𝑦𝑖 ≠ ℎ𝑡 (𝑥𝑖 )] 𝛽𝑡 = 1 2 ln 1 − 𝜖𝑡 𝜖𝑡 𝑤𝑡+1 𝑖 ∝ 𝑤𝑡 𝑖 𝑒 −𝛽𝑡𝑦𝑖ℎ𝑡(𝒙𝑖)
Adaboost AlgorithmOutputthefinal classifierTKβtht(x)h[x] = signt=19/22/2026PATTERNRECOGNITION
Adaboost Algorithm Output the final classifier 9/22/2026 PATTERN RECOGNITION 7 ℎ 𝒙 = 𝑠𝑖𝑔𝑛 𝑡=1 𝑇 𝛽𝑡ℎ𝑡 (𝒙)
ExampleD10datapointsand2features+++++ThedatapointsareclearlynotlinearseparableInthebeginning,all datapointshaveequalweights(thesizeofthedata markers“+" or"_")Baseclassifierh():eitherhorizontalorverticallinesoThese'decision stumps'are justtrees witha singleinternal node,i.e.,theyclassifyingdatabasedonasingleattribute9/22/2026PATTERNRECOGNITION0
Example 10 data points and 2 features The data points are clearly not linear separable In the beginning, all data points have equal weights (the size of the data markers “+” or “-”) Base classifier ℎ(⋅): either horizontal or vertical lines ◦ These ‘decision stumps’ are just trees with a single internal node, i.e., they classifying data based on a single attribute 9/22/2026 PATTERN RECOGNITION 8
ExampleRound 1: t = 1十+3misclassified(withcircles):E1.=0.3→β=0.42Weightsrecomputed;the3 misclassifieddatapointsreceivelarger weights9/22/2026PATTERNRECOGNITION
Example Round 1: t = 1 3 misclassified (with circles): 𝜖1 = 0.3 → 𝛽1 = 0.42 Weights recomputed; the 3 misclassified data points receive larger weights 9/22/2026 PATTERN RECOGNITION 9
ExampleRound2:t=2++++3 misclassified (with circles):E2= 0.21→β2=0.65Note that E2± 0.3as those3data points have weights less than 1/103misclassifieddata pointsget largerweightsDatapoints classifiedcorrectlyinbothroundshave smallweights9/22/202610PATTERNRECOGNITION
Example Round 2: t = 2 3 misclassified (with circles): 𝜖2 = 0.21 → 𝛽2 = 0.65 ◦ Note that 𝜖2 ≠ 0.3 as those 3 data points have weights less than 1/10 3 misclassified data points get larger weights Data points classified correctly in both rounds have small weights 9/22/2026 PATTERN RECOGNITION 10