Adaboost

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 2 august 2019; verificările necesită 3 modificări .

AdaBoost (prescurtare de la Adaptive Boosting ) este un algoritm de învățare automată propus de Yoav Freund și Robert Shapire . Acest algoritm poate fi utilizat împreună cu mai mulți algoritmi de clasificare pentru a le îmbunătăți performanța. Algoritmul întărește clasificatorii combinându-i într-un „comitet” ( ansamblu ). AdaBoost este adaptativ în sensul că fiecare comitet de clasificare următor este construit pe obiecte care au fost clasificate incorect de comitetele anterioare. AdaBoost este sensibil la zgomotul datelor și valorile aberante . Cu toate acestea, este mai puțin predispus la supraadaptare în comparație cu alți algoritmi de învățare automată.

AdaBoost numește clasificatorii slabi într-o buclă . După fiecare apel, distribuția greutăților este actualizată , care corespund importanței fiecăruia dintre obiectele din setul de antrenament pentru clasificare. La fiecare iterație, ponderile fiecărui obiect clasificat greșit sunt crescute, astfel încât noul comitet de clasificare „își concentrează atenția” asupra acestor obiecte. $t=1,\ldots ,T$ $D_{{t}}$

Algoritm pentru problema construirii unui clasificator binar

Dat: unde $(x_{{1}},y_{{1}}),\ldots ,(x_{{m}},y_{{m}})$ $x_{{i}}\în X,\,y_{{i}}\în Y=\{-1,+1\}$

Inițializați $D_{{1}}(i)={\frac {1}{m}},i=1,\ldots ,m.$

Pentru fiecare : $t=1,\ldots ,T$

Găsiți un clasificator care minimizează eroarea de clasificare ponderată: , unde $h_{{t}}:X\la \{-1,+1\}$ $h_{{t}}=\arg \min _{{h_{{j}}\in {\mathcal {H}}}}\epsilon _{{j}}$ $\epsilon _{{j}}=\sum _{{i=1}}^{{m}}D_{{t}}(i)[y_{i}\neq h_{{j}}(x_{ {i}})]$
Dacă valoarea este , atunci ne oprim. $\epsilon_{{t}}\geqslant 0,5$
Alegem , de obicei, unde este eroarea ponderată a clasificatorului . $\alpha _{{t}}\in {\mathbf {R}}$ $\alpha _{{t))={\frac {1}{2}}{\textrm {ln}}{\frac {1-\epsilon _{{t}}}{\epsilon _{{t}} }}$ $\epsilon_{{t}}$ $h_{{t}}$
Actualizați:

D_{{t+1}}(i)={\frac {D_{{t}}(i)\,e^{{-\alpha _{{t}}y_{{i}}h_{{t }}(x_{{i}})}}}{Z_{{t}}}}

unde este un parametru de normalizare (ales să fie o distribuție de probabilitate , adică ).

Z_{{t}}

D_{{t+1}}

\sum _{{i=1}}^{{m}}D_{{t+1}}(i)=1

Construim clasificatorul rezultat:

H(x)={\textrm {semn}}\left(\sum _{{t=1}}^{{T}}\alpha _{{t}}h_{{t}}(x)\right )

Expresia de actualizare a distribuției trebuie să fie construită în așa fel încât următoarea condiție să fie adevărată: $D_{{t}}$

e^{{-\alpha _{{t}}y_{{i}}h_{{t}}(x_{{i}})))}{\begin{cases}<1,&y(i)= h_ {{t}}(x_{{i}})\\>1,&y(i)\neq h_{{t}}(x_{{i}})\end{cases}}

Astfel, după alegerea clasificatorului optim pentru distribuție , obiectele , pe care clasificatorul le identifică corect, au ponderi mai mici decât cele care sunt identificate incorect. Prin urmare, atunci când algoritmul testează clasificatorii pe distribuție , va alege clasificatorul care este mai bun la identificarea obiectelor recunoscute greșit de clasificatorul anterior. $h_{{t}}$ $D_{{t}}$ $x_{i}$ $h_{{t}}$ $D_{{t+1}}$

Link -uri

AdaBoost (engleză) Prezentare dedicată Adaboost.
O scurtă introducere în stimularea Introducere în Adaboost , Freund și Schapire, 1999
O generalizare teoretică a deciziei a învățării on-line și o aplicație pentru stimularea Jurnalului de Științe Calculatoare și Sisteme , nr. 55. 1997 (engleză) (Lucrare originală de Yoav Freund și Robert E.Schapire, unde Adaboost a fost propus pentru prima dată.)
Un applet care demonstrează AdaBoost
Ensemble Based Systems in Decision Making, R. Polikar, IEEE Circuits and Systems Magazine, vol.6, nr.3, pp. 21-45, 2006 (link indisponibil) (ing.) Tutorial care oferă o privire de ansamblu asupra AdaBoost, inclusiv pseudocod, diagrame de algoritm, probleme de implementare și alți algoritmi de recunoaștere a modelelor .
O implementare Matlab a AdaBoost
Regresia logistică aditivă: o viziune statistică a stimulării. Jerome Friedman, Trevor Hastie, Robert Tibshirani Discută aspecte probabilistice ale AdaBoost, descrie GentleBoost.
Boosting - Îmbunătățirea clasificatorilor simpli. Alexander Vejneveți, Vladimir Vejneveți. Grafică pe computer și multimedia . Numărul nr. 2(12)/2006.

Învățare automată și extragerea datelor
Sarcini	Problema de clasificare Învățați fără profesor Învățare asistată de profesor Analiza regresiei AutoML Regulile de asociere Extragerea caracteristicilor Antrenamentul trăsăturilor Antrenament de clasare Derivarea gramaticală Învățare online
Învățarea cu un profesor	metoda k-cel mai apropiat vecin Clasificator naiv Bayes arborele de decizie Suport mașină vectorială Regresie liniara Regresie logistică perceptron Ansambluri de modele Bagare stimularea pădure la întâmplare Metoda vectorială relevantă
analiza grupului	metoda k-means Metoda de grupare fuzzy Gruparea ierarhică algoritmul EM MESTEACĂN VINDECA DBSCAN OPTICA Schimbare medie
Reducerea dimensionalității	Analiza factorilor Metoda componentei principale CCA ICA LDA Expansiunea nenegativă a matricei t-SNE
Prognoza structurală	Modelul probabilistic grafic Rețeaua bayesiană Modelul Markov ascuns CRF
Detectarea anomaliilor	metoda k-cel mai apropiat vecin Nivelul de emisie local
Modele grafice probabilistice	Rețeaua bayesiană Rețeaua Markov Modelul Markov ascuns
Rețele neuronale	Mașină Boltzmann limitată hartă de auto-organizare Funcția de activare Sigmoid softmax Funcția de bază radială Metoda de propagare înapoi Invatare profunda Perceptron multistrat Rețea neuronală recurentă memorie pe termen lung și scurt Bloc recurent controlat Rețeaua neuronală convoluțională U-Net Autoencoder
Consolidarea învățării	procesul Markov Ecuația Bellman Algoritmul lacom Q-learning SARSA Diferența temporală (TD)
Teorie	Teoria Vapnik-Chervonenkis Dilema părtinire-dispersie Teoria învățării computaționale Minimizarea riscului empiric Occam învață Învățarea PAC Teoria învăţării statistice
Reviste și conferințe	NeurIPS ICML ML JMLR ArXiv:cs.LG