CoBoostowanie

CoBoost to częściowo nadzorowany algorytm szkoleniowy zaproponowany przez Collinsa i Singera w 1999 r. Pierwotnym zastosowaniem algorytmu było zadanie klasyfikacji nazwanych jednostek przy użyciu bardzo słabych uczniów. Może być używany do przeprowadzania uczenia częściowo nadzorowanego w przypadkach, w których występuje redundancja funkcji.

Można to postrzegać jako połączenie współtrenowania i wzmacniania . Każdy przykład jest dostępny w dwóch widokach (podsekcjach zestawu funkcji), a wzmacnianie jest stosowane iteracyjnie na przemian z każdym widokiem przy użyciu przewidywanych etykiet utworzonych w alternatywnym widoku w poprzedniej iteracji. CoBoosting nie jest prawidłowym algorytmem wzmacniającym w uczenia się PAC .

Motywacja

CoBoosting był próbą Collinsa i Singera ulepszenia poprzednich prób wykorzystania redundancji funkcji do szkolenia klasyfikatorów w sposób częściowo nadzorowany. Wykazano, że CoTraining, przełomowa praca Bluma i Mitchella, jest potężną platformą do uczenia się klasyfikatorów, biorąc pod uwagę niewielką liczbę przykładów nasion, poprzez iteracyjne wprowadzanie reguł na liście decyzyjnej. Zaletą CoBoosting do CoTraining jest to, że uogólnia wzorzec CoTraining, dzięki czemu można go używać z dowolnym klasyfikatorem. CoBoosting dokonuje tego wyczynu, zapożyczając koncepcje od AdaBoost .

Zarówno w CoTrain, jak i CoBoost przykładowe zestawy szkoleniowe i testowe muszą mieć dwie właściwości. Po pierwsze, przestrzeń cech przykładów można podzielić na dwie przestrzenie cech (lub widoki), tak że każdy widok jest wystarczająco wyrazisty, aby można go było sklasyfikować. $}$ istnieją dwie funkcje takie że dla $Displaystyle$$x = (x_ {1}, x_ {2})}$ Displaystyle , ${\ Displaystyle f_{1}(x_{1})=f_{2}(x_{2})=f(x)}$ . Choć idealne, to ograniczenie jest w rzeczywistości zbyt silne ze względu na szum i inne czynniki, a zamiast tego oba algorytmy dążą do maksymalizacji zgodności między dwiema funkcjami. Druga właściwość polega na tym, że te dwa widoki nie mogą być silnie skorelowane.

Algorytm

wejście: ${\ Displaystyle \ {(x_ {1, i}, x_ {2, i}) \} _ {i = 1} ^ {n }}$ , ${\ Displaystyle \ {y_ {i} \} _ {i = 1} ^ {m}}$

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

dla ${\ Displaystyle t = 1, ..., T}$ i dla $\ Displaystyle j = 1,2}$ :

Ustaw pseudoetykiety:

${\ Displaystyle {\ kapelusz {y_ {i }}}=\left\{{\begin{array}{ll}y_{i},1\równoważnik i\równoważnik m\\sign(g_{3-j}^{t-1}({\boldsymbol { x_{3-j,i}}})),m<i\równoważnik n\koniec{tablica}}\prawo.}$

Ustaw wirtualny rozkład: ${\ Displaystyle D_ {t} ^ {j} (i) = {\ Frac { 1}{Z_{t}^{j}}}e^{-{\kapelusz {y_{i}}}g_{j}^{t-1}({\boldsymbol {x_{j,i}}} )}}$

gdzie $\ Displaystyle Z_ {t} ^ {j} = \ suma _ {i = 1} ^ {n} e^{-{\kapelusz {y_{i}}}g_{j}^{t-1}({\boldsymbol {x_{j,i}}})}}$

Znajdź słabą hipotezę $,$ .

Wybierz wartość dla $rozszerzony$ błąd szkolenia.

Zaktualizuj wartość dla obecnego silnego klasyfikatora bezprogowego:

${\ Displaystyle \ 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}}})}$

Ostateczny wynik silnego klasyfikatora to

${\ Displaystyle f ({\ pogrubiony symbol {x}}) = znak \ lewo (\ suma _ {j = 1} ^ {2}g_{j}^{T}({\boldsymbol {x_{j}}})\right)}$

Konfigurowanie AdaBoost

CoBoosting opiera się na algorytmie AdaBoost , który daje CoBoosting zdolność uogólniania, ponieważ AdaBoost może być używany w połączeniu z wieloma innymi algorytmami uczenia się. Ta kompilacja zakłada zadanie klasyfikacji w dwóch klasach, chociaż można ją dostosować do klasyfikacji w wielu klasach. W ramach AdaBoost słabe klasyfikatory są generowane szeregowo, a także rozkład na przykłady w zbiorze uczącym. Każdemu słabemu klasyfikatorowi przypisuje się wagę, a ostateczny silny klasyfikator definiuje się jako znak sumy słabych klasyfikatorów ważonych przypisaną im wagą. (Zobacz stronę Wikipedii AdaBoost dla notacji). W ramach AdaBoost Schapire i Singer wykazali, że błąd szkolenia jest ograniczony następującym równaniem:

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

gdzie $1}}$ współczynnikiem normalizującym dla rozkładu $T$ . Z ${\ displaystyle Z_ {t}}$ w równaniu dla otrzymujemy: $D_ {t} (i)}$

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

Gdzie $cechą$ w obecnej słabej hipotezie. Zdefiniowano trzy równania opisujące sumę rozkładów, dla których obecna hipoteza wybrała poprawną lub błędną etykietę. Należy zauważyć, że klasyfikator może powstrzymać się od wybrania etykiety dla przykładu, w którym podana etykieta to 0. Dwie etykiety są wybierane jako -1 lub 1.

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

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

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

Schapire i Singer wykazali, że wartość $Z_$${t}}$ (a tym samym błąd szkolenia), wybierając następującą wartość:

${\ Displaystyle \ alfa _ {t} = {\ Frac {1} {2}} \ ln \ lewo ({\ Frac {W_ {+}} {W_ { -}}}\Prawidłowy)}$

Zapewnienie wartości ufności dla obecnego hipotetycznego klasyfikatora na podstawie liczby poprawnie sklasyfikowanych przykładów w porównaniu z liczbą błędnie sklasyfikowanych przykładów ważonych rozkładem na przykłady. To równanie można wygładzić $,$ aby zrekompensować przypadki, w których małe. Wyprowadzając z tego równania otrzymujemy: ${\ displaystyle Z_ {t}}$

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

W ten sposób błąd uczenia jest minimalizowany przez wybranie słabej hipotezy w każdej iteracji, która minimalizuje poprzednie równanie.

AdaBoost z dwoma widokami

CoBoosting rozszerza te ramy w przypadku, gdy mamy oznaczony zestaw treningowy (przykłady z ${$ i nieoznaczony zestaw treningowy (z $m_ {$ ), a także spełniać warunki redundancji cech w postaci ${\ Displaystyle x_ {i} = (x_ {1, i},x_{2,i})}$ . Algorytm trenuje dwa klasyfikatory w taki sam sposób, jak AdaBoost , które zgadzają się co do oznaczonych zestawów treningowych z poprawnymi etykietami i maksymalizuje zgodność między dwoma klasyfikatorami w nieoznakowanym zbiorze treningowym. Ostateczny klasyfikator jest znakiem sumy dwóch silnych klasyfikatorów. ${\ displaystyle Z_ {CO}$ rozszerzony w następujący sposób, gdzie jest rozszerzeniem ${\ displaystyle Z_ {t}}:$ }

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

Gdzie $widoku$ sumą wagi hipotez według ich wartości ufności dla $lub$ 2). ${\ displaystyle f_ {j}}$ jest znakiem $\ displaystyle g_ {j}}$ . Przy każdej iteracji CoBoost oba klasyfikatory są iteracyjnie aktualizowane. sol $}$$}$${\ displaystyle t -1}$ silnym wyjściem klasyfikatora dla widoku do iteracji możemy ustawić pseudoetykiety dla j -tej aktualizacji na:

${\ Displaystyle {\ kapelusz {y_ {i}} }=\left\{{\begin{tablica}{ll}y_{i}1\równoważnik i\równoważnik m\\sign(g_{3-j}^{t-1}({\boldsymbol {x_{3 -j,i}}}))m<i\leq n\end{tablica}}\right.}$

W którym $inny$ widok niż aktualnie ${\ Displaystyle Z_ {CO}}$ jest podzielony na dwie części tak, że ${\ Displaystyle Z_ {CO} = Z_ {CO} ^ {1} + Z_ {CO} }^{2}}$ . Gdzie

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

Rozkład na przykłady dla każdego widoku $t$ iteracji jest zdefiniowany w następujący sposób: $\ displaystyle t}$

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

${\ displaystyle Z_ {CO} ^ {j}}$ jot można przepisać

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

Co jest identyczne z równaniem w AdaBoost. W ten sposób ten $Displaystyle {\ hat {y_ {i$ proces może być użyty do aktualizacji wartości, jak w przypadku AdaBoost przy użyciu $}$ i re $t} ^ {j}}$ . Zmieniając to, minimalizacja i ${2}}$$Displaystyle$ w ten sposób $} ^ {1}}$ { jest minimalizowane w zachłanny sposób.