Ch 6: Adaboost for buildin robust classifiers KH Wong Adaboost, Vga
Ch. 6: Adaboost for building robust classifiers KH Wong Adaboost , V9a 1
Overview Objectives of ada boost Solve 2-class classification problems Will discuss Training Detection Examples Adaboost, Vga
Overview • Objectives of AdaBoost • Solve 2-class classification problems • Will discuss – Training – Detection – Examples Adaboost , V9a 2
Obiective automatically classify inputs into different categories of similar features Example Spam mail detection and filtering Face detection: find the faces in the input image Vision based gesture recognition [chen2007] 3」sp
Objective • Automatically classify inputs into different categories of similar features • Example – Spam mail detection and filtering – Face detection: • find the faces in the input image – Vision based gesture recognition [Chen 2007] Adaboost , V9a 3
Different detection problems Two-class problem will be discussed here E.g. face detection In a picture are there any faces or no face? Multi-class problems(not discussed here Adaboost can be extended to handle multi class problems In a picture are there any faces of men women, children (Still an unsolved problem Adaboost, Vga
Different detection problems • Two-class problem (will be discussed here) – E.g. face detection • In a picture, are there any faces or no face? • Multi-class problems (Not discussed here) – Adaboost can be extended to handle multi class problems • In a picture, are there any faces of men , women, children ? (Still an unsolved problem) Adaboost , V9a 4
Define a 2-class classifier its method and procedures Supervised training Show many positive samples(face) to the system Show many negative samples(non- face) to the system Learn the parameters and construct the final strong classifier. Detection Given an unknown input image the system can tell if there are faces or not Adaboost, Vga
Define a 2-class classifier :its method and procedures • Supervised training – Show many positive samples (face) to the system – Show many negative samples (non-face) to the system. – Learn the parameters and construct the final strong classifier. • Detection – Given an unknown input image, the system can tell if there are faces or not. Adaboost , V9a 5
We will learn Training procedures Give +ve and -ve examples to the system then the system will learn to classify an unknown input E. g. give pictures of faces( +ve examples and non-faces (ve examples to train the system Detection procedures Input an unknown(e.g. an image), the system will tell you it is a face or not Adaboost, Vga ace non-face 6
We will learn • Training procedures – Give +ve and –ve examples to the system, then the system will learn to classify an unknown input. • E.g. give pictures of faces (+ve examples) and non-faces (-ve examples) to train the system. • Detection procedures – Input an unknown (e.g. an image) , the system will tell you it is a face or not. Adaboost , V9a Face non 6 -face
A line y=mX+c Exercise 1 a linear m=3,c=2 (a) When x=1y=3*x+2=5.50 programming example when y=5.5, is x,y 因 Figure bovell/below[ii the line? File Edit Yiew Insert Tools Desktop Window Help 口白命气气← Answer:[]or[ⅲ]? =mx+c, m=3, C=2, X1,y=5 (a) When x=0,y=3*x+2=2.S0 y-mxC when y"=1.5, is(x,y") axIs above[l/below[ii] the line? Answer [i]or [i]? X=0,y=2 y=mxc y-mXmX+c if a(x,y is below and on the right side X-axis of the line y=mx+c, y<mx+c Adaboost, Vga
Exercise 1 :A linear programming example • A line y=mx+c • m=3, c=2 • (a) When x=1, y=3*x+2=5. So when y’=5.5, is (x,y’) above[i]/below[ii] the line? • Answer: [i] or [ii]?________ • (a) When x=0, y=3*x+2=2. So when y”=1.5, is (x,y”) above[i]/below[ii] the line? • Answer: [i] or [ii]?________ • Conclusion, – if a point (x,y) is above and on the left of the line y=mx+c, y>mx+c – if a (x,y) is below and on the right side of the line y=mx+c, yc y-mx<c
A line y=mX+c ANSWER 1: Alinear m=3,c=2 (a) When x=1y=3*x+2=5.50 programming example when y=5.5, is x,y 因 Figure bovell/below[ii the line? File Edit Yiew Insert Tools Desktop Window Help Answer: i or [ii? i above =mx+c, m=3, C=2, X1,y=5 (a) When x=0,y=3*x+2=2.S0 y-mxC when y"=1.5, is(,y axIs above[il /below[ii] the line? Answer: [i or [ii? ii below X=0,y=2 y=mxc y-mXmX+c if a(x,y is below and on the right side X-axis of the line y=mx+c, y<mx+c Adaboost, Vga
ANSWER 1 :A linear programming example • A line y=mx+c • m=3, c=2 • (a) When x=1, y=3*x+2=5. So when y’=5.5, is (x,y’) above[i]/below[ii] the line? • Answer: [i] or [ii]?_i above • (a) When x=0, y=3*x+2=2. So when y”=1.5, is (x,y”) above[i]/below[ii] the line? • Answer: [i] or [ii]?_ii below • Conclusion, – if a point (x,y) is above and on the left of the line y=mx+c, y>mx+c – if a (x,y) is below and on the right side of the line y=mx+c, yc y-mx<c
First let us learn what is a weak classifier h( -Case 1 If a point(x=lu, v Dis in the "gray area, h(x)=+I For this weak classifier p, m, c otherwise h(x=u, vD=-1. It can be written as are constants defining the classifier, variables h(r)=+I if v-muC At timet, combine case l and 2 together to become equation(() V-muc 1 otherwise Adaboost, vga
First let us learn what is a weak classifier h( ) • ( ) 1 otherwise 1 if ( ) , ( ) becomes where are constants, are variables. is the function :( ( [ , ]) ,) and where polarity { 1or -1}, ( ) 1 otherwise 1 if ( ) ( ) and use polarity to control which case you want to use. --At time , combine case1and 2 together to become equation 1 otherwise 1 where , are given constants ( ) otherwise [ ] 1.It can be written as: If a point ( [ , ])isin the "white" area , 1 --Case2--1 otherwise 1 if ,where , are given constants ( ) otherwise [ ] 1.It can be written as: If a point ( [ ])isin the "gray"area , 1 --Case1-- ii p v mu p c h x p v mu p c equation i m,c u,v f f x u v v mu c p i p f x p h x p t (i) if -(v-mu) c , m,x h x h(x u,v ) x u v h(x) v-mu c m,x h x h(x u,v ) x u,v h(x) t t t t t t t t t t t t t − − − − − − − − − − + − = − = − = = + − − − − − − − − − − + = − + − = = = − = = + − + = = = − = = + 9 Adaboost , V9a v=mu+c or v-mu=c •m,c are used to define the line •Any points in the gray area satisfy v-muc v c Gradient m (0,0) v-muc u For this weak classifier pt ,m,c are constants defining the classifier. Variables u,v are inputs. If u,v is here , h(x=[u,v])=1 If u,v is here , h(x=[u,v])=-1
The weak classifier( a summary) Function f is a straight line V=mutC By definition a weak classifier or should be slightly better than a V-mu=c random choice(probability of correct classifcation =0.5) Gradient ml Otherwise you should use a dice! In lu, v]space, the decision V-mu>c function f: (v-mu =c is a straight V-mu<c line defined by m, c 0,0)u1 Adaboost, Vga
The weak classifier (a summary) • By definition a weak classifier should be slightly better than a random choice (probability of correct classifcation =0.5) . Otherwise you should use a dice! • In [u,v] space, the decision function f : (v-mu)=c is a straight line defined by m,c. Adaboost , V9a 10 Function f is a straight line v c Gradient m (0,0) v-muc u v=mu+c or v-mu=c