BrownBoost

BrownBoost är en förstärkningsalgoritm som kan vara robust mot bullriga datamängder. BrownBoost är en adaptiv version av boost by majoritetsalgoritmen. Som är sant för alla förstärkningsalgoritmer , används BrownBoost i kombination med andra maskininlärningsmetoder . BrownBoost introducerades av Yoav Freund 2001.

Motivering

AdaBoost fungerar bra på en mängd olika datauppsättningar; det kan dock visas att AdaBoost inte fungerar bra på bullriga datamängder. Detta är ett resultat av AdaBoosts fokus på exempel som upprepade gånger felklassificeras. Däremot "ger BrownBoost upp" på exempel som upprepade gånger felklassificeras. Kärnantagandet för BrownBoost är att bullriga exempel upprepade gånger kommer att felmärkas av de svaga hypoteserna och icke-bullriga exempel kommer att korrekt märkas tillräckligt ofta för att inte "ge upp". Således kommer endast bullriga exempel att "avstås", medan icke-brusande exempel kommer att bidra till den slutliga klassificeraren. I sin tur, om den slutliga klassificeraren lärs från de icke-brusiga exemplen, generaliseringsfelet för den slutliga klassificeraren vara mycket bättre än om den lärs från brusiga och icke-brusiga exempel.

Användaren av algoritmen kan ställa in mängden fel som ska tolereras i träningsuppsättningen. Således, om träningssetet är bullrigt (säg att 10 % av alla exempel antas vara felmärkta), kan boostern uppmanas att acceptera en felfrekvens på 10 %. Eftersom de bullriga exemplen kan ignoreras, kommer bara de sanna exemplen att bidra till inlärningsprocessen.

Algoritmbeskrivning

BrownBoost använder en icke-konvex potentiell förlustfunktion, så den passar inte in i AdaBoost- ramverket. Den icke-konvexa optimeringen ger en metod för att undvika att överanpassa bullriga datamängder. Men i motsats till förstärkningsalgoritmer som analytiskt minimerar en konvex förlustfunktion (t.ex. AdaBoost och LogitBoost ), löser BrownBoost ett system med två ekvationer och två okända med vanliga numeriska metoder.

Den enda parametern för BrownBoost ( $c$ i algoritmen) är "tiden" som algoritmen körs. Teorin om BrownBoost säger att varje hypotes tar en variabel tid ( $t$ i algoritmen) som är direkt relaterad till vikten som ges till hypotesen $\alpha$ . Tidsparametern i BrownBoost är analog med antalet iterationer $T$ i AdaBoost.

Ett högre värde på $c$ innebär att BrownBoost kommer att behandla data som om de vore mindre brusiga och därför kommer att ge upp färre exempel. Omvänt betyder ett mindre värde på $c$ att BrownBoost kommer att behandla data som mer bullriga och ge upp på fler exempel.

Under varje iteration av algoritmen väljs en hypotes med viss fördel framför slumpmässig gissning. Vikten av denna hypotes $\alpha$ och "mängden tid som gått" $t$ under iterationen löses samtidigt i ett system av två icke-linjära ekvationer ( 1. okorrelerad hypotes med exempelvikter och 2. håll potentialkonstanten) med två okända (hypotesens vikt $\alpha$ och tiden som gått $t$ ). Detta kan lösas genom tvåsektion (som implementerat i JBoost-programpaketet) eller Newtons metod (som beskrivs i den ursprungliga artikeln av Freund). När dessa ekvationer är lösta uppdateras marginalerna för varje exempel ( $r_{i}(x_{j})$ algoritmen) och mängden återstående tid $s$ på lämpligt sätt. Denna process upprepas tills det inte finns någon tid kvar.

Den initiala potentialen definieras till ${\frac {1}{m}}\sum _{j=1}^{ m}1-{\mbox{erf}}({\sqrt {c}})=1-{\mbox{erf}}({\sqrt {c}})$ . Eftersom en begränsning för varje iteration är att potentialen hålls konstant är den slutliga potentialen ${\ frac {1}{m}}\sum _{j=1}^{m}1-{\mbox{erf}}(r_{i}(x_{j})/{\sqrt {c}})= 1-{\mbox{erf}}({\sqrt {c}})$ . Det slutliga felet är alltså troligtvis nära $1-{\mbox{erf}}({\sqrt {c}})$ . Den slutliga potentiella funktionen är dock inte 0-1 förlustfelfunktionen. För att det slutliga felet ska vara exakt ${\displaystyle 1-{\mbox{erf}}({\sqrt {c}})} ,$ måste variansen för förlustfunktionen minska linjärt med tiden för att bilda 0-1 förlustfunktion i slutet av förstärkande iterationer. Detta har ännu inte diskuterats i litteraturen och ingår inte i definitionen av algoritmen nedan.

Den slutliga klassificeraren är en linjär kombination av svaga hypoteser och utvärderas på samma sätt som de flesta andra förstärkningsalgoritmer.

BrownBoost inlärningsalgoritm definition

Inmatning:

$m$ träningsexempel $(x_{1},y_{1}),\ldots ,(x_{m},y_ {m})$ där $x_{j}\in X,\,y_{j}\in Y=\{-1,+ 1\}$
Parametern $c$

Initiera:

$s=c$ . (Värdet på $s$ är hur lång tid som återstår i spelet)
$r_{i}(x_{j})=0$ $\forall j$ . Värdet på $r_{i}(x_{j})$ är marginalen vid iteration $i$ till exempel $x_{j}$ .

Medan $s>0$ :

Ställ in vikterna för varje exempel: ${\displaystyle W_{i}(x_{j})=e^{-{\frac { (r_{i}(x_{j})+s)^{2}}{c}}}} ,$ där $r_{i}(x_{j})$ är marginalen av exempel $x_{j}$
Hitta en klassificerare $h_{i}:X\to \{-1,+1\}$ så att $\sum _{j}W_{i}(x_{j})h_{i}(x_{j})y_{j}>0$
Hitta värden $\alpha ,t$ som uppfyller ekvationen: $\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$ . (Observera att detta liknar villkoret $E_{W_{i+1}}[h_{i}(x_{j})y_{j }]=0$ som anges av Schapire och Singer. I den här inställningen hittar vi numeriskt $W_{i+1}=\exp \left({\frac {\cdots }{\cdots }}\right)$ så att $E_{W_{i+1}}[h_{i}(x_ {j})y_{j}]=0$ .) ${\displaystyle \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} , där$ uppdatering är föremål för begränsningen Φ ( $displaystyle \Phi (z )=1-{\mbox{erf}}(z/{\sqrt {c}})}$ är den potentiella förlusten för en punkt med marginal $r_{i}(x_{j} )$
Uppdatera marginalerna för varje exempel: $r_{i+1}(x_{j})=r_{i }(x_{j})+\alpha h(x_{j})y_{j}$
Uppdatera den återstående tiden: $s=st$

Utdata: $H(x)={\textrm {tecken}}\left(\sum _{i}\alpha _{i}h_ {i}(x)\höger)$

Empiriska resultat

I preliminära experimentella resultat med bullriga datauppsättningar överträffade BrownBoost AdaBoosts generaliseringsfel; dock LogitBoost lika bra som BrownBoost. En implementering av BrownBoost finns i programvaran med öppen källkod JBoost .

Se även

externa länkar

JBoost