Adaboost

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 2. august 2019; checks kræver 3 redigeringer .

AdaBoost (forkortelse for Adaptive Boosting ) er en maskinlæringsalgoritme foreslået af Yoav Freund og Robert Shapire [ . Denne algoritme kan bruges sammen med flere klassifikationsalgoritmer for at forbedre deres ydeevne. Algoritmen styrker klassifikatorerne ved at kombinere dem til en "komité" ( ensemble ). AdaBoost er adaptiv i den forstand, at hver næste klassificeringskomité er bygget på objekter, der var forkert klassificeret af tidligere udvalg. AdaBoost er følsom over for datastøj og afvigelser . Den er dog mindre tilbøjelig til overfitting sammenlignet med andre maskinlæringsalgoritmer.

AdaBoost kalder svage klassifikatorer i en løkke . Efter hvert opkald opdateres fordelingen af vægte , som svarer til vigtigheden af hvert af objekterne i træningssættet for klassificering. Ved hver iteration øges vægten af hvert forkert klassificeret objekt, så den nye klassificeringskomité "fokuserer sin opmærksomhed" på disse objekter. $t=1,\ldots ,T$ $D_{{t}}$

Algoritme til problemet med at konstruere en binær klassifikator

Givet: hvor $(x_{{1}},y_{{1}}),\ldots ,(x_{{m}},y_{{m}})$ $x_{{i}}\i X,\,y_{{i}}\i Y=\{-1,+1\}$

Initialiser $D_{{1}}(i)={\frac {1}{m}},i=1,\ldots ,m.$

For hver : $t=1,\ldots ,T$

Find en klassifikator , der minimerer den vægtede klassifikationsfejl: , hvor $h_{{t}}:X\til \{-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_{ {jeg}})]$
Hvis værdien er , så stopper vi. $\epsilon_{{t}}\geqslant 0.5$
Vi vælger , normalt hvor er den vægtede klassifikationsfejl . $\alpha _{{t}}\in {\mathbf {R}}$ $\alpha _{{t))={\frac {1}{2}}{\textrm {ln}}{\frac {1-\epsilon _{{t}}}{\epsilon _{{t}} }}$ $\epsilon_{{t}}$ $h_{{t}}$
Opdatering:

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

hvor er en normaliserende parameter (valgt til at være en sandsynlighedsfordeling , dvs. ).

Z_{{t}}

D_{{t+1}}

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

Vi bygger den resulterende klassifikator:

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

Distributionsopdateringsudtrykket skal være konstrueret på en sådan måde, at følgende betingelse er sand: $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}}

Efter at have valgt den optimale klassifikator til fordelingen har objekter , som klassificereren korrekt identificerer, vægte mindre end dem, der er identificeret forkert. Derfor, når algoritmen tester klassifikatorer på distributionen , vil den vælge den klassifikator, der er bedre til at identificere objekter, der er forkert genkendt af den forrige klassifikator. $h_{{t}}$ $D_{{t}}$ $x_{i}$ $h_{{t}}$ $D_{{t+1}}$

Links

AdaBoost (engelsk) Præsentation dedikeret til Adaboost.
A Short Introduction to Boosting Introduktion til Adaboost , Freund og Schapire, 1999
En beslutningsteoretisk generalisering af online-læring og en anvendelse til at styrke Journal of Computer and System Sciences , nr. 55. 1997 (engelsk) (Originalt værk af Yoav Freund og Robert E. Schapire, hvor Adaboost først blev foreslået.)
En applet, der demonstrerer AdaBoost
Ensemble Based Systems in Decision Making, R. Polikar, IEEE Circuits and Systems Magazine, vol.6, nr.3, pp. 21-45, 2006 (utilgængeligt link) (eng.) Selvstudium giver et overblik over AdaBoost, inklusive pseudokode, algoritmediagrammer, implementeringsproblemer og andre mønstergenkendelsesalgoritmer .
En Matlab-implementering af AdaBoost
Additiv logistisk regression: et statistisk syn på boosting. Jerome Friedman, Trevor Hastie, Robert Tibshirani Diskuterer probabilistiske aspekter af AdaBoost, beskriver GentleBoost.
Boosting - Boosting af simple klassificeringer. Alexander Vezhnevets, Vladimir Vezhnevets. Computergrafik og multimedier . Udgave nr. 2(12)/2006.

Machine learning og data mining
Opgaver	Klassificeringsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG