Adaptive Boost (AdaBoost) Junhong Kim

AdaBoost(Adaptive Boosting) Weak learner , Strong learner Assumption  Target variable == binary value [+1, -1] A weak learner is defined to be a classifier which is only slightly correlated with the true classfier (it can label examples better than random guessing). In contrast, a strong learner is a classifier that is arbitrarily well-correlated with the true classifier. Can a set of weak learners create a single strong learner? Strong Learner Weak Learner Error rate 0.5 1

AdaBoost(Adaptive Boosting) Case 1 𝐻 𝑥 =𝑠𝑖𝑔𝑛( ℎ 1 (𝑥)+ ℎ 2 (𝑥)+ ℎ 3 (𝑥)) h1 Wrong h2 Wrong 𝑥 is Sample data In this case, If 3 classifier results aggregate using majority voting method, 𝐻 𝑥 is completely correlated true classifier. h3 Wrong Square space is sample data space

AdaBoost(Adaptive Boosting) Case 2 𝑥 is Sample data In this case, If 3 classifier results aggregate using majority voting method, 𝐻 𝑥 is not completely correlated true classifiers. Solution Idea  Wisdom of weighted crowd of experts 1. Data  ℎ 1 𝑥 2. Data exaggeration of ℎ 1 Errors  ℎ 2 𝑥 3. Data exaggeration of ℎ 2 Errors  ℎ 3 𝑥 Q : Boosting depends on decision tree stump? A : No, we can use any kinds of classifiers. (For example, ANN, k-NN, LR, SVM etc…) so, why are use decision tree stump? Because using for illustration, variable selection, overfitting. Square space is sample data space

AdaBoost(Adaptive Boosting) Case 2 Idea  Decision Tree Stump 1. Data  ℎ 1 𝑥 2. Data exaggeration of ℎ 1 Errors  ℎ 2 𝑥 3. Data exaggeration of ℎ 2 Errors  ℎ 3 𝑥 𝒂 𝒕 made by learner error(t) 𝑯 𝒙 =𝒔𝒊𝒈𝒏( 𝒂 𝟏 𝒉 𝟏 (𝒙) + 𝒂 𝟐 𝒉 𝟐 (𝒙) + 𝒂 𝟑 𝒉 𝟑 (𝒙)+…..) Wisdom of weighted crowd of experts 𝑤 3 𝑤 2 𝑤 1 Square space is sample data space Select one of eight decision line. (Decision Tree Stump)

AdaBoost(Adaptive Boosting) * Ensemble decision boundary is Green * Current base learner is dashed black line * Size of circle indicates weight assigned

AdaBoost(Adaptive Boosting) * We choose parameter T (ensemble size) If you choose large T, maybe ensemble model toward overfitting. Therefore T is important. First weight distribution 𝑫 𝟏 is uniform distribution 𝑫 𝟏 𝒊 = 𝟏 𝑵 (N is number of observation) First learner using decision tree stump model (you can use any kinds of classifiers) First learner symbol is 𝒉 𝟏 Calculate error rate by first learner predicted result First error rate symbol is 𝒆 𝟏 Pick 𝒉 𝟏 that minimize 𝒆 𝟏  pick 𝜶 𝟏 , 𝜶 is model weight. The premise was learner better than random guess.

AdaBoost(Adaptive Boosting) Let 𝑤(𝑖)= 1 𝑁 Samples(First step) * Demonstration 𝒛 𝒕 =𝟐 𝒆 𝒕 ∗(𝟏− 𝒆 𝒕 ) * Suppose 𝒘 𝒊 𝒕+𝟏 = 𝒘 𝒊 𝒕 𝒛 𝒕 𝒆 − 𝜶 𝒕 𝒉 𝒕 𝒙 𝒚(𝒙) , 𝜶 𝒕 =𝟎.𝟓 ∗𝒍𝒏( 𝟏− 𝒆 𝒕 𝒆 𝒕 ) 𝒘 𝒊 𝒕+𝟏 = 𝒘 𝒊 𝒕 𝒛 𝒕 * 𝒆 𝒕 𝟏−𝒆 𝒕 (𝒄𝒐𝒓𝒓𝒆𝒄𝒕) 𝟏− 𝒆 𝒕 𝒆 𝒕 (𝒘𝒓𝒐𝒏𝒈) 𝒆 𝒕 𝟏−𝒆 𝒕 𝑪𝒐𝒓𝒓𝒆𝒄𝒕 𝒘 𝒊 𝒕 + 𝟏− 𝒆 𝒕 𝒆 𝒕 𝑾𝒓𝒐𝒏𝒈 𝒘 𝒊 𝒕 = 𝒛 𝒕 𝑪𝒐𝒓𝒓𝒆𝒄𝒕 𝒘 𝒊 𝒕 = 𝟏−𝒆 𝒕 , 𝑾𝒓𝒐𝒏𝒈 𝒘 𝒊 𝒕 = 𝒆 𝒕 𝒆 𝒕 ∗ (𝟏−𝒆 𝒕 )∗ (𝟏−𝒆 𝒕 ) 𝟏−𝒆 𝒕 + 𝟏− 𝒆 𝒕 ∗ 𝒆 𝒕 ∗ 𝒆 𝒕 𝒆 𝒕 = 𝒛 𝒕 𝒕𝒉𝒆𝒓𝒆𝒇𝒐𝒓𝒆, 𝒛 𝒕 =𝟐 𝒆 𝒕 ∗(𝟏− 𝒆 𝒕 ) Pick ℎ 𝑡 that minimize 𝑒 𝑡 Pick 𝛼 𝑡 Calculate 𝑤 𝑡

AdaBoost(Adaptive Boosting) Adaboost Example (Decision Tree Stump) , calculation result in AdaptiveBoosting.R index 1 2 3 4 5 6 7 8 9 x value y value -1 Set ensemble size = 3 We start with the following probabilities (Uniform distribution) p0 p1 p2 p3 p4 p5 p6 p7 p8 p9 𝑤 𝑝𝑟𝑖𝑜𝑟 0.1 [Time = 1] The best threshold is between 2 and 3. 𝜀1 = 0.3 α1 = 0.423649 == 0.5*(log(0.7/0.3)) w1 = 1.52753 for wrong, 0.654654 for correct

AdaBoost(Adaptive Boosting) Adaboost Example (Decision Tree Stump) index 1 2 3 4 5 6 7 8 9 x value y value -1 𝑤 1 0.07143 0.16667 correct y n [Time = 2] The best threshold is between 8 and 9. 𝜀2 = 0.214 α2 = 0.6496 == 0.5*(log(0.786/0.214)) w1(correct) = 0.07143 h1(correct), h2(correct) (w2) round(0.07143/0.8206578*exp(-0.6496),digits=5) = 0.04546 h1(wrong) , h2(wrong) (w2) round(0.07143/0.8206578*exp(0.6496),digits=5) = 0.16666 w1(wrong) = 0.07143 h1(correct) , h2(correct) (w2) round(0.16667/0.8206578*exp(-0.6496),digits=5) = 0.10607 h1(wrong) , h2(wrong) (w2) round(0.16667/0.8206578*exp(0.6496),digits=5) = 0.38888

AdaBoost(Adaptive Boosting) Adaboost Example (Decision Tree Stump) index 1 2 3 4 5 6 7 8 9 x value y value -1 𝑤 2 0.045 0.167 0.106 correct y n [Time = 3] The best threshold is between 5 and 6. 𝜀3 = 0.1818 α3 = 0.7520 == 0.5*(log(0.8182/0.1818)) w3 results h1(correct), h2(correct),h3(correct) = 0.125 h1(correct), h2(correct),h3(wrong) = 0.02778 h1(wrong) , h2(wrong),h3(correct) = 0.45828 h1(wrong) , h2(wrong),h3(wrong) = 0.10185 h1(correct) , h2(correct) ,h3(correct) = 0.29167 h1(correct) , h2(correct) ,h3(wrong) = 0.06482 w2 results h1(correct), h2(correct) = 0.04546 h1(wrong) , h2(wrong) = 0.16666 h1(correct) , h2(correct) = 0.10607 Except h1(wrong) , h2(wrong) = 0.38888 why  not applicable

AdaBoost(Adaptive Boosting) Adaboost Example (Decision Tree Stump) index 1 2 3 4 5 6 7 8 9 x value y value -1 𝑤 3 0.125 0.102 0.064 correct n y Previously, we set ensemble size = 3 [Finish]

AdaBoost(Adaptive Boosting) Adaboost Example (Decision Tree Stump) Result index 1 2 3 4 5 6 7 8 9 𝑤 1 0.07143 0.16667 𝑤 2 0.045 0.167 0.106 𝑤 3 0.125 0.102 0.064 y value -1 α1 = 0.423649 ,α2 = 0.6496 ,α3 = 0.7520 𝐻 𝑥 ′ =𝑠𝑖𝑔𝑛 𝑡=1 𝑇 𝛼 𝑡 ℎ 𝑡 𝑥 ′ Therefore , H(x) = 0.423649* ℎ 1 + 0.6496* ℎ 2 + 0.752* ℎ 3

AdaBoost(Adaptive Boosting) Reference Adaboost MIT OpenCourseWare https://www.youtube.com/watch?v=UHBmv7qCey4 Adaboost Example http://www.csie.ntu.edu.tw/~b92109/course/Machine%20Learning/AdaBoostExample.pdf http://www.csie.ntu.edu.tw/~b92109/course/Machine%20Learning/AdaBoostExample2.pdf http://www.csie.ntu.edu.tw/~b92109/course/Machine%20Learning/AdaBoosting2.pdf http://www.csie.ntu.edu.tw/~b92109/course/Machine%20Learning/AdaBoosting.pdf http://math.mit.edu/~rothvoss/18.304.3PM/Presentations/1-Eric-Boosting304FinalRpdf.pdf (p13 Z(t) function) Adaboost R package 1.‘adabag’ https://cran.r-project.org/web/packages/adabag/adabag.pdf 2.’ada’ https://cran.r-project.org/web/packages/ada/ada.pdf

Haar-like Feature Haar-like Features 는 비올라(Viola)와 존스(Jones)가 얼굴검출에 적용한 것으로 ‘단순 합’ 이미지를 이용하여 특징값을 표현한 것이다. 따라서 합으로 특징이 이루어져 있기 때문에 연산 속도도 빠르며, 이를 이용한 분산처리 (ex)GPU computing도 가능하다. 책에서는 Harr-like feature를 4가지로 정의 했지만, 특징은 더 많은 경우의 수를 사용할 수 있다. 특징 값은 그림으로 보았을 경우 밝은 값과 어두운 값의 합의 차로 구한다. https://www.youtube.com/watch?v=hPCTwxF0qf4

Haar-like Feature 비올라와 존스는 얼굴 검출을 위한 서브 윈도우의 기본 크기를 24*24로 하고 있다. (크기는 상황에 따라 달라질 수 있다. 보통 최소값과 최대값을 정해서 쓰는 것을 볼 수 있다.) 이 뜻은 24*24(pixel)안에서 Haar-like 특징 집합의 가능한 모양과 크기의 모든 변수를 사용한다는 것이다. 경우의 수를 나타내어 보면 4개의 특징을 8*8 pixel을 최소크기로 최대 24*24 pixel까지 1pixel씩 증가 시키면서 feature를 만든다고 한다면 총 feature의 경우의 수는 93,636가지 이다. 𝑓=( 𝑖=8 24 24−𝑖+1 )∗( 𝑗=8 24 24−𝑖+1 ) * 4 = 93,636 서브 윈도우 기본 크기 24*24(Pixel) Haar-like 특징 집합

Integral Image 이렇게 합의 형식으로 feature를 생성하기 때문에 적분 영상(Integral Image)으로 변환 후 이용하면 그 특징값을 빠르게 얻을 수 있다. 𝑖𝑖 𝑥,𝑦 = 𝑥 ′ ≤𝑥,𝑦′≤𝑦 𝑖( 𝑥 ′ , 𝑦 ′ ) 𝑖𝑖 𝑥,𝑦 는 적분영상이고 𝑖 𝑥′,𝑦′ 는 원영상의 밝기 값이다. 이를 응용하면 만약 아래 그림에서 D의 구간에 대한 밝기를 구하고 싶다면 적분값으로 Point(4+1-2-3)을 하면 된다. (A+B+C+D)+A-(A+B)-(A+C) = D Weak Learner Description ℎ 𝑗 𝑥 = 1 𝑝 𝑗 𝑓 𝑗 𝑥 < 𝑝 𝑗 𝜃 𝑗 −1 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 (x,y) A B 1 2 C D 3 4

Pseudo Code 비올라(Viola)와 존스(Jones)가 제안한 Adaboost 알고리즘 (0) Ensemble size ‘T’를 정의한다. (1) 학습이미지 샘플 ( 𝑥 1 , 𝑦 1 ), … , ( 𝑥 𝑛 , 𝑦 𝑛 ) n개가 있다. ※ 𝑦 𝑖 = 0,1은 얼굴(Positive data), 비얼굴(Negative data)로 정의한다. (2) 𝑦 𝑖 = 0,1에 대해서 Uniform distribution으로 초기 가중치를 구한다. 𝑤 𝑖 , i = 1 2𝑚 , 1 2𝑙 ※ m은 Positive data의 개수 l은 Negative data의 개수 (3) For t = 1,…,T [ 3-1 ] 𝑤 𝑡 가 확률 분포가 되도록 가중치를 정규화 한다. 𝑤 𝑖,𝑗 = 𝑤 𝑖,𝑗 𝑗=1 𝑛 𝑤 𝑖,𝑗 [ 3-2 ] 각 특징(Haar-like feature) j에 대하여 단일 특징을 사용하는 것으로 제약 되는 분류기 ℎ 𝑗 를 학습한다. ※ 오차는 𝑤 𝑡 에 따라 다음 식으로 계산된다. 𝜖 𝑗 = 𝑖 𝑤 𝑖 | ℎ 𝑗 𝑥 𝑖 − 𝑦 𝑖 | [ 3-3 ] 최소 오차 𝜖 𝑗 를 가진 분류기 ℎ 𝑡 를 선택한다. [ 3-4 ] 가중치를 갱신한다. 𝑤 𝑡+1 (i) = 𝑤 𝑡 (i), 𝛽 𝑡 1− 𝜖 𝑖 ※ 만약 샘플 𝑥 𝑖 가 옳게 분류되었으면 , 𝜖 𝑖 =0, 그렇지 않으면 𝜖 𝑖 =1 , 그리고 𝛽 𝑡 = 𝜖 𝑡 1− 𝜖 𝑡 (4) 최종 Strong learner ℎ 𝑥 = 1 𝑡=1 𝑇 𝛼 𝑡 ℎ 𝑡 𝑥 ≥0.5 ∗ 𝑡=1 𝑇 𝛼 𝑡 0 𝑂𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 ※ 𝛼 𝑡 = 𝑙𝑜𝑔 1 𝛽 𝑡 Correct(observation)의 경우 weight가 감소 안 되는것 처럼 보여도 Normalization factor에서 감소 되게 된다.

Attentional cascade 얼굴 검출 시 연산 속도를 향상하기 위해 Adaboost 구조를 단계 구조로 만들어 사용한다. 단계 구조는 여러 개의 스테이지(stage)를 나누고 스테이지 별로 약한 분류기의 수를 다르게 하여 수행하는 방법이다. 아이디어는 얼굴이 아닌 이미지는 초기에 걸러내고 해볼만한 복잡한 영상에 대한 분류에 집중할 수 있도록 고안한 것이다. 이 경우 초기 스테이지에서의 false positive rate는 감수해야 한다는 단점이 있다. K를 분류기의 수, 𝑓 𝑖 는 i번째 분류기의 FPR이라 하면 단계 검사된 분류기의 Total FPR은 F = 𝑖=1 𝐾 𝑓 𝑖 이며 Total Detection rate는 D = 𝑖=1 𝐾 𝑑 𝑖 이다. ※ 𝑑 𝑖 는 i번째 분류기 에서의 검지율

Attentional cascade 단계 검사 분류기를 위해서는 3가지 파라미터가 필요하다. 총 분류기(또는 단계)의 수 각 단계의 특징들의 수 : 𝑛 𝑖 각 단계의 임계값 : 𝜃 𝑖 생각해보면, 계산 시간을 최소로 유지하면서 최적의 파라미터를 찾는 것은 복잡하다. 간단한 방법은 특징들의 수와 단계의 수를 원하는 결과를 이룰 때까지 증가 시키는 것이다. 단계에서 허용되는 FPR을 𝑓 𝑖 , 검지율을 𝑑 𝑖 라고 했을 때, 𝑑 𝑖 는 Adaboost 임계값 𝜃 𝑖 를 감소시킴으로써 얻을 수 있다. 물론 FPR도 영향을 받게 된다.

Haar cascade method Pseudo code 단계 검사 분류기의 학습에 대한 일반적 방법 (0) 사용자가 각 단계예서 최대 허용 거짓 긍정률 𝑓와 사용자가 각 단계에서 최소 허용 검지율 𝑑를 선택한다. 사용자가 타겟 전체 거짓 긍정률( 𝐹 𝑡𝑎𝑟𝑔𝑒𝑡 )을 설정한다. P = Positive sample set , N = Negative sample set (3) 𝐹 0 = 1.0 , 𝐷 0 = 1.0 (4) I = 0 , while ( 𝐹 𝑖 > 𝐹 𝑡𝑎𝑟𝑔𝑒𝑡 ) { #start while loop1 [4-1] i <- +1 [4-2] 𝑛 𝑖 = 0; 𝐹 𝑖 = 𝐹 𝑖−1 [4-3] 𝑤ℎ𝑖𝑙𝑒 𝐹 𝑖 > 𝑓 * 𝐹 𝑖−1 { #start while loop2 [4-3-a] 𝑛 𝑖 <- i + 1 [4-3-b] P와 N으로 Adaboost를 이용하여 𝑛 𝑖 feature가 있는 분류기를 학습한다. [4-3-c] 𝐹 𝑖 와 𝐷 𝑖 를 결정하기 위하여 검정 샘플 집합으로 현재 단계 분류기를 평가한다. [4-3-d] 현재 단계 분류기가 최소한 d * 𝐷 𝑖−1 의 검지율을 보일 때까지 i번째 분류기에 대하여 임계값을 감소시킨다. } #end while loop2 (이는 𝐹 𝑖 에도 영향을 준다.) [4-3-e] N <- 0 [4-3-f ] 만약 𝐹 𝑖 > 𝐹 𝑇𝑎𝑟𝑔𝑒𝑡 이면, 비얼굴 이미지 집합에서 현재 단계 검지기를 평가하고, 잘못 검지된 것들을 집합 N으로 옮긴다. } #end while loop1

In conclusion Reference 이번 스터디에서는 영상처리에서 전처리를 해야 할 밝기 (사진 밝기에 대한 전처리) Robust Real-Time Face Detection( PAUL VIOLA, MICHAEL J. JONES, 2004 ) http://www.vision.caltech.edu/html-files/EE148-2005-Spring/pprs/viola04ijcv.pdf 이번 스터디에서는 영상처리에서 전처리를 해야 할 밝기 (사진 밝기에 대한 전처리) 기울기 (2차원 회전, 3차원 옆모습) 피부톤 (백인과 흑인의 피부톤에 대한 전처리) 등등을 다루지 않았다. 이 부분에 대해서는 이 과의 범위를 넘어가므로 다루지 않는다. OpenCV (Face Detection using Haar Cascades) http://docs.opencv.org/master/d7/d8b/tutorial_py_face_detection.html#gsc.tab=0 http://docs.opencv.org/doc/user_guide/ug_traincascade.html

Thank You