Brownboost

BrownBoost är en förstärkningsalgoritm som har visat sig vara effektiv på bullriga datamängder. Som alla förstärkningsalgoritmer används BrownBoost tillsammans med andra maskininlärningsalgoritmer . BrownBoost-algoritmen föreslogs av Yoav Freund ( sv:Yoav Freund ) [1] .

Motivation

AdaBoost-algoritmen har visat sin effektivitet på en mängd olika datamängder. Det kan dock visas att AdaBoost inte är effektiv på bullriga datamängder [2] . Detta är en konsekvens av att AdaBoost fokuserar på delar av träningsprovet som upprepade gånger felklassificeras. Däremot ger BrownBoost helt enkelt upp sådana element. BrownBoost är baserad på antagandet att bullriga element upprepade gånger kommer att felklassificeras av basklassificerarna, och icke-brusiga element kommer att klassificeras korrekt ganska ofta. Detta kommer att förkasta de brusiga elementen, och de icke-brusiga elementen kommer att bidra till den slutliga klassificeraren. Den slutliga klassificeraren kommer alltså att tränas på icke-bullriga delar av träningsprovet, så dess generaliseringsförmåga kan vara bättre än AdaBoosts när man tränar på ett träningsprov med brus.

Beskrivning av algoritmen

BrownBoost använder en icke-konvex förlustfunktion , så den faller inte in i AnyBoost- familjen av algoritmer . Icke-konvex optimering undviker överanpassning på bullriga datauppsättningar. Till skillnad från förstärkningsalgoritmer (som AdaBoost och LogitBoost ) som minimerar en konvex förlustfunktion, löser BrownBoost ett system med 2 ekvationer i 2 okända med vanliga numeriska metoder.

Den enda parametern för BrownBoost-algoritmen är "tiden" som algoritmen körs. Varje svag klassificerare får en tid , som är direkt relaterad till klassificerarens vikt. $c$ $t$

Ett stort värde innebär att BrownBoost kommer att anse att data är mindre bullriga och kommer att kassera färre delar av träningsuppsättningen. Följaktligen betyder ett litet värde att BrownBoost kommer att betrakta data som bullrigare och kassera fler delar av träningsuppsättningen. Vid varje steg väljer algoritmen en basklassificerare något bättre än bara slumpmässigt. Vikten av denna klassificerare och mängden tid som förflutit under iterationen ges genom att lösa ett system med 2 olinjära ekvationer (1. okorrelation hos basklassificeraren och vikterna av elementen i träningsprovet; 2. invarians av potentialen) med 2 okända. Detta system kan lösas med dikotomimetoden , som implementerad i JBoost- paketet , eller med Newton-metoden , som i den ursprungliga författarens artikel. Efter att ha löst ekvationerna räknas om vikterna av elementen i träningsprovet och mängden återstående tid. Denna procedur upprepas tills hela tiden är över. $c$ $c$ $\alfa$ $t$ $r_{i}(x_{j})$

Den initiala potentialen definieras som . Eftersom varje steg i algoritmen inte ändrar potentialen är jämlikheten sann . Därför är det slutliga felet förmodligen nära . Den slutliga potentiella funktionen är dock inte en binär förlustfunktion. ${\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}({\sqrt {c}})=1-{\mbox{ erf))({\sqrt {c)))$ ${\frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}(r_{i}(x_{j})/{\sqrt { c)))=1-{\mbox{erf))({\sqrt {c)))$ $1-{\mbox{erf))({\sqrt {c)))$

För att den slutliga förlustfunktionen ska vara exakt måste variansen minska linjärt med tiden för att bilda en binär förlustfunktion efter slutet av förstärkningsupprepningarna. Denna punkt har ännu inte beskrivits i litteraturen och saknas i definitionen av algoritmen nedan. $1-{\mbox{erf))({\sqrt {c)))$

Den slutliga klassificeraren är en linjär kombination av basklassificerarna, och dess kvalitet kan utvärderas på samma sätt som i de flesta andra förstärkningsalgoritmer.

Algoritm

Ingång:

$m$ träningsprov var $(x_{{1}},y_{{1}}),\ldots ,(x_{{m}},y_{{m}})$ ${\displaystyle x_{j}\in X,\,y_{j}\in Y=\{-1,+1\))$
parameter $c$

Initiering:

$s=c$ . Värdet är den tid som återstår för algoritmen att köras. $s$
$r_{i}(x_{j})=0$ $\forall j$ . Värdena är iterationsvikterna för träningsprovelementet . $r_{i}(x_{j})$ $i$ $x_{j}$

Hejdå : $s>0$

Ställ in vikten för varje element i träningsprovet: , här vikten av elementet ${\displaystyle W_{i}(x_{j})=e^{-{\frac {(r_{i}(x_{j})+s)^{2}}{c))))$ $r_{i}(x_{j})$ $x_{j}$
Hitta en basklassificerare sådan att $h_{i}:X\to \{-1,+1\}$ $\sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0$
Hitta värden som uppfyller ekvationen: . (Observera att detta liknar villkoret [3] .) Vid denna punkt finner vi numeriskt sådana att .) Denna förändring måste följa begränsningen , här den potentiella förlusten för en punkt med vikt $\alpha ,t$
$\sum _{j}h_{i}(x_{j})y_{j}e^{-{\frac {(r_{i}(x_{j})+\alpha h_{i}( x_{j})y_{j}+st)^{2}}{c}}}=0$
$E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$ $W_{i+1}=\exp({\frac {\ldots }{\ldots )))$ $E_{W_{i+1}}[h_{i}(x_{j})y_{j}]=0$

$\sum \left(\Phi \left(r_{i}(x_{j})+\alpha h(x_{j})y_{j}+st\right)-\Phi \left(r_{ i}(x_{j})+s\right)\right)=0$
$\Phi (z)=1-{\mbox{erf))(z/{\sqrt {c)))$ $r_{i}(x_{j})$
Uppdatera vikterna för varje del av träningsprovet: ${\displaystyle r_{i+1}(x_{j})=r_{i}(x_{j})+\alpha h(x_{j})y_{j))$
Uppdatera återstående tid: $s=st$

Utgång: $H(x)={\textrm {tecken}}\left(\summa _{i}\alpha _{i}h_{i}(x)\right)$

Empiriska resultat

I preliminära experiment har BrownBoost ett mindre generaliseringsfel jämfört med AdaBoost och har liknande resultat som LogitBoost. [4] En implementering av BrownBoos finns i JBoost- paketet med öppen källkod .

Anteckningar

↑ Yoav Freund. En adaptiv version av boost by majoritetsalgoritmen. Machine Learning, 43(3):293-318, juni 2001.
↑ Dietterich, T.G., (2000). En experimentell jämförelse av tre metoder för att konstruera ensembler av beslutsträd: Bagging, boosting och randomisering. Machine Learning, 40(2) 139-158.
↑ Robert Schapire och Yoram Singer. Förbättrad boosting med förtroendeklassade förutsägelser. Journal of Machine Learning, Vol 37(3), sid 297-336. 1999
↑ Ross A. McDonald, David J. Hand, Idris A. Eckley. En empirisk jämförelse av tre förstärkande algoritmer på verkliga datamängder med artificiellt klassbrus. Multiple Classifier Systems, In Series Lecture Notes in Computer Science, sidorna 35-44, 2003.

Se även

Maskininlärning och datautvinning
Uppgifter	Klassificeringsproblem Lärande utan lärare Lärarassisterat lärande Regressionsanalys AutoML Föreningens regler Särdragsextraktion Egenskapsträning Ranking utbildning Grammatisk härledning Online lärande
Att lära sig med en lärare	k-närmaste granne metod Naiv Bayes klassificerare beslutsträd Stöd vektor maskin Linjär regression Logistisk tillbakagång perceptron Ensembler av modeller Säckväv förstärkning slumpmässig skog Relevant vektormetod
klusteranalys	k-betyder metod Fuzzy klustringsmetod Hierarkisk klustring EM algoritm BJÖRK BOTA DBSCAN OPTIK Genomsnittlig förskjutning
Dimensionalitetsreduktion	Faktoranalys Huvudkomponentmetoden CCA ICA LDA Icke-negativ matrisexpansion t-SNE
Strukturell prognos	Graph probabilistisk modell Bayesiskt nätverk Dold Markov-modell CRF
Anomali upptäckt	k-närmaste granne metod Lokal utsläppsnivå
Grafisk probabilistiska modeller	Bayesiskt nätverk Markov nätverk Dold Markov-modell
Neurala nätverk	Begränsad Boltzmann-maskin självorganiserande karta Aktiveringsfunktion Sigmoid softmax Radiell basfunktion Ryggförökningsmetod Djup lärning Flerskiktsperceptron Återkommande neurala nätverk långtidsminne Kontrollerat återkommande block Konvolutionellt neuralt nätverk U-Net Autokodare
Förstärkningsinlärning	Markov process Bellmans ekvation Girig algoritm Q-lärande SARSA Temporell skillnad (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beräkningslärandeteori Empirisk riskminimering Occam lär sig PAC-inlärning Statistisk inlärningsteori
Tidskrifter och konferenser	NeurIPS ICML ML JMLR ArXiv:cs.LG