《Foundation of Machine Learning [Part06]》.pdf

Foundations of Machine Learning Lecture 6 Mehryar Mohri Courant Institute and Google Research mohri@cims.nyu.edu Boosting Mehryar Mohri - Foundations of Machine Learning page 2 Weak Learning (Kearns and Valiant, 1994) Definition: concept class C is weakly PAC-learnable if there exists a (weak) learning algorithm L and γ 0 such that: • for all c ∈ C, 0, δ 0, and all distributions D, 1 Pr R(hS ) ≤ − γ ≥ 1 − δ, S∼D 2 • for samples S of size m =poly (1/δ) for a fixed polynomial. Mehryar Mohri - Foundations of Machine Learning page 3 Boosting Ideas Main idea: use weak learner to create strong learner. Ensemble method: combine base classifiers returned by weak learner. Finding simple relatively accurate base classifiers often not hard. But, how should base classifiers be combined? Mehryar Mohri - Foundations of Machine Learning page 4 AdaBoost (Freund and Schapire, 1997) H ⊆ {−1, +1}X . AdaBoost(S =((x , y ), . . . , (x , y ))) 1 1 m m 1 for i ← 1 to m do 2 D1 (i) ← 1 m 3 for t ← 1 to T do 4 h ← base classifier in H with small error =Pr [h (x ) = y ] t t Dt t i i 5 αt ← 1 log 1−t 2 t 1 6 Z ← 2[ (1 − )] 2 normalization