CoBoosting

CoBoost är en semi-övervakad träningsalgoritm som föreslagits av Collins och Singer 1999. Den ursprungliga applikationen för algoritmen var uppgiften för Named Entity Classification med mycket svaga elever. Den kan användas för att utföra semi-övervakad inlärning i fall där det finns redundans i funktioner.

Det kan ses som en kombination av samträning och boostning . Varje exempel är tillgängligt i två vyer (undersektioner av funktionsuppsättningen), och förstärkning tillämpas iterativt omväxlande med varje vy med förutspådda etiketter som producerats i den alternativa vyn på föregående iteration. CoBoosting är inte en giltig förstärkningsalgoritm i PAC-inlärningsbemärkelsen .

Motivering

CoBoosting var ett försök av Collins och Singer att förbättra tidigare försök att utnyttja redundans i funktioner för att träna klassificerare på ett semi-övervakat sätt. CoTraining, ett framträdande verk av Blum och Mitchell, visade sig vara ett kraftfullt ramverk för att lära sig klassificerare med tanke på ett litet antal fröexempel genom att iterativt inducera regler i en beslutslista. Fördelen med CoBoosting till CoTraining är att det generaliserar CoTraining-mönstret så att det kan användas med vilken klassificerare som helst. CoBoosting åstadkommer denna bedrift genom att låna koncept från AdaBoost .

I både CoTrain och CoBoost måste tränings- och testexempeluppsättningarna följa två egenskaper. Den första är att exemplens funktionsutrymme kan separeras i två funktionsutrymmen (eller vyer) så att varje vy är tillräckligt uttrycksfullt för klassificering. Formellt finns det två funktioner $f_{1}(x_{1})$ och $f_{2}(x_{2})$ så att för alla exempel $x=(x_{1},x_{2})$ , $f_{1}(x_{1})=f_{2}(x_{2})=f(x)$ . Även om den är idealisk är denna begränsning i själva verket för stark på grund av brus och andra faktorer, och båda algoritmerna försöker istället maximera överensstämmelsen mellan de två funktionerna. Den andra egenskapen är att de två vyerna inte får vara starkt korrelerade.

Algoritm

Inmatning: $\{(x_{1,i},x_{2,i})\}_{i=1}^{n }$ , $\{y_{i}\}_{i=1}^{m}$

Initiera: $\forall i,j:g_{j}^{0}({\boldsymbol {x_{i}}})=0$ .

För $t=1,...,T$ och för $j=1,2$ :

Ställ in pseudoetiketter:

${\hat {y_{i }}}=\left\{{\begin{array}{ll}y_{i},1\leq i\leq m\\sign(g_{3-j}^{t-1}({\boldsymbol { x_{3-j,i}}})),m<i\leq n\end{array}}\right.$

Ställ in virtuell distribution: $D_{t}^{j}(i)={\frac { 1}{Z_{t}^{j}}}e^{-{\hat {y_{i}}}g_{j}^{t-1}({\boldsymbol {x_{j,i}}} )}$

där $Z_{t}^{j}=\summa _{i=1}^{n} e^{-{\hat {y_{i}}}g_{j}^{t-1}({\boldsymbol {x_{j,i}}})}$

Hitta den svaga hypotesen $h_{t}^{j}$ som minimerar utökat träningsfel.

Välj värde för $\alpha _{t}$ som minimerar utökat träningsfel.

Uppdatera värdet för aktuell klassificerare utan tröskelvärde:

$\forall i:g_{j}^{t }({\boldsymbol {x_{j,i}}})=g_{j}^{t-1}({\boldsymbol {x_{j,i}}})+\alpha _{t}h_{t }^{j}({\boldsymbol {x_{j,i}}})$

Den slutliga starka klassificeringsutgången är

$f({\boldsymbol {x}})=tecken\left(\summa _{j=1}^ {2}g_{j}^{T}({\boldsymbol {x_{j}}})\right)$

Konfigurera AdaBoost

CoBoosting bygger på AdaBoost -algoritmen, vilket ger CoBoosting dess generaliseringsförmåga eftersom AdaBoost kan användas i kombination med många andra inlärningsalgoritmer. Denna uppbyggnad förutsätter en klassificeringsuppgift med två klasser, även om den kan anpassas till klassificering med flera klasser. I AdaBoost-ramverket genereras svaga klassificerare i serier samt en fördelning över exempel i träningsuppsättningen. Varje svag klassificerare ges en vikt och den slutliga starka klassificeraren definieras som tecknet på summan av de svaga klassificerarna viktade med deras tilldelade vikt. (Se AdaBoost Wikipedia för notation). I AdaBoost-ramverket har Schapire och Singer visat att träningsfelet begränsas av följande ekvation:

${\frac {1}{m}}\sum _{ i=1}^{m}e^{\left(-y_{i}\left(\summa _{t=1}^{T}\alpha _{t}h_{t}({\boldsymbol {x_ {i}}})\right)\right)}=\prod _{t}Z_{t}$

Där $Z_{t}$ är normaliseringsfaktorn för fördelningen $D_{t+1}$ . När vi löser $Z_{t}$ i ekvationen för $D_{t}(i)$ får vi:

$Z_{t}= \sum _{i:x_{t}\notin x_{i}}D_{t}(i)+\summa _{i:x_{t}\in x_{i}}D_{t}(i)e ^{-y_{i}\alpha _{i}h_{t}({\boldsymbol {x_{i}}})}$

Där $x_{t}$ är funktionen som valts i den aktuella svaga hypotesen. Tre ekvationer definieras som beskriver summan av fördelningarna för vilka den aktuella hypotesen har valt antingen korrekt eller felaktig etikett. Observera att det är möjligt för klassificeraren att avstå från att välja en etikett för ett exempel, där den angivna etiketten är 0. De två etiketterna är valda att vara antingen -1 eller 1.

$W_{0}=\summa _{i:h_{t}(x_{i})=0}D_{t}(i )$

$W_{+}=\summa _{i:h_{t}(x_{i})=y_{i}} D_{t}(i)$

$W_{-}=\summa _{i:h_{t}(x_{i})=-y_{i }}D_{t}(i)$

Schapire och Singer har visat att värdet $Z_{t}$ kan minimeras (och därmed träningsfelet) genom att välja $\alpha _{t}$ till följande:

$\alpha _{t}={\frac {1}{2}}\ln \left({\frac {W_{+}}{W_{ -}}}\höger)$

Tillhandahållande av konfidensvärden för den aktuella hypotesen baserad på antalet korrekt klassificerade kontra antalet felaktigt klassificerade exempel viktat av fördelningen över exempel. Denna ekvation kan jämnas ut för att kompensera för fall där $W_{-}$ är för liten. Om vi ​​härleder $Z_{t}$ från denna ekvation får vi:

$Z_{t}=W_{0}+2{\sqrt {W_{+}W_{-}}}$

Träningsfelet minimeras således genom att välja den svaga hypotesen vid varje iteration som minimerar föregående ekvation.

AdaBoost med två vyer

CoBoosting utökar detta ramverk i de fall där man har ett märkt träningsset (exempel från $1...m$ ) och ett omärkt träningsset (från ${\displaystyle m_$ ), samt uppfylla villkoren för redundans i funktioner i form av $x_{i}=(x_{1, i},x_{2,i})$ . Algoritmen tränar två klassificerare på samma sätt som AdaBoost som kommer överens om de märkta träningsuppsättningarna korrekta etiketter och maximerar överensstämmelsen mellan de två klassificerarna på den omärkta träningsuppsättningen. Den slutliga klassificeraren är tecknet på summan av de två starka klassificerarna. Det begränsade träningsfelet på CoBoost utökas enligt följande, där $\displaystyle Z_{CO}}$ är förlängningen av $Z_{t}$ :

$Z_{CO}=\ summa _{i=1}^{m}e^{-y_{i}g_{1}({\boldsymbol {x_{1,i}}})}+\summa _{i=1}^{m }e^{-y_{i}g_{2}({\boldsymbol {x_{2,i}}})}+\summa _{i=m+1}^{n}e^{-f_{2 }({\boldsymbol {x_{2,i}}})g_{1}({\boldsymbol {x_{1,i}}})}+\summa _{i=m+1}^{n}e ^{-f_{1}({\boldsymbol {x_{1,i}}})g_{2}({\boldsymbol {x_{2,i}}})}$

Där $g_{j}$ är summeringen av hypotesernas vikt med deras konfidensvärden för vyn $j^{th}$ (j = 1 eller 2). $f_{j}$ är tecknet för $g_{j}$ . Vid varje iteration av CoBoost uppdateras båda klassificerarna iterativt. Om $g_{j}^{t-1}$ är den starka klassificerarens utdata för ${\displaystyle j^{th}}-$ vyn upp till $t -1$ iteration kan vi ställa in pseudo-etiketterna för den j: e uppdateringen att vara:

${\hat {y_{i}} }=\left\{{\begin{array}{ll}y_{i}1\leq i\leq m\\sign(g_{3-j}^{t-1}({\boldsymbol {x_{3 -j,i}}}))m<i\leq n\end{array}}\right.$

I vilken $3-j$ väljer den andra vyn till den som för närvarande uppdateras. $Z_{CO}$ delas upp i två så att $Z_{CO}=Z_{CO}^{1}+Z_{CO }^{2}$ . Var

$Z_{CO}^{j} =\summa _{i=1}^{n}e^{-{\hat {y_{i}}}(g_{j}^{t-1}({\boldsymbol {x_{i}}}) +\alpha _{t}^{j}g_{t}^{j}({\boldsymbol {x_{j,i}}}))}$

Fördelningen över exempel för varje vy $j$ vid iteration $t$ definieras enligt följande:

$D_{t}^{j}(i)={\frac {1}{Z_ {t}^{j}}}e^{-{\hat {y_{i}}}g_{j}^{t-1}({\boldsymbol {x_{j,i}}})}$

Vid vilken punkt $Z_{CO}^{j}$ kan skrivas om som

$Z_{CO}^{j}=\summa _{i=1} ^{n}D_{t}^{j}e^{-{\hat {y_{i}}}\alpha _{t}^{j}g_{t}^{j}({\boldsymbol {x_ {j,i}}})}$

Vilket är identiskt med ekvationen i AdaBoost. Således kan samma process användas för att uppdatera värdena för $\alpha _{t}^{j}$ som i AdaBoost med ${\hat {y_{i}}}$ och $D_{t}^{j}$ . Genom att alternera detta, minimeras $Z_{CO}^{1}$ och $Z_{CO}^{2}$ på detta sätt $Z_ {CO}$ minimeras på ett girigt sätt.