Podręcznik: Techniki tworzenia silnych rozwiązań na bazie słabych predyktorów

1. Zespoły klasyfikatorów

1.3. Techniki tworzenia silnych rozwiązań na bazie słabych predyktorów

Interesującą techniką poprawy zdolności generalizacyjnych w uczeniu maszynowym jest tworzenie silnych predyktorów (klasyfikatorów bądź układów regresyjnych o podwyższonej dokładności) poprzez zastosowanie zespołów zbudowanych na bazie słabych rozwiązań predyktorów (mało dokładnych), na przykład lasu drzew decyzyjnych, nieoptymalnie dobranych struktur sieci neuronowych RBF lub MLP, itp. Klasyczne techniki tworzenia zespołu poprzez zastosowanie wielu równoległych rozwiązań indywidualnych predyktorów tego samego typu, ale trenowanych na losowo wybranych danych uczących (tzw. bagging), stosowane na przykład w lesie losowym drzew decyzyjnych [3] nie zawsze prowadzą do optymalnego wyniku pod względem generalizacji. Pojawiło się wiele ulepszonych rozwiązań tego typu zespołów. Do najbardziej znanych należą systemy wzmacniana (tzw. boosting), które wpływają na działanie zespołu już na etapie ich tworzenia, ingerując silnie w algorytm uczący. W tym punkcie przedstawione zostaną dwie techniki tworzenia takiego zespołu słabych predyktorów: wzmacnianie adaptacyjne (tzw. adaptive boosting) zwane w skrócie AdaBoost, oraz wzmacnianie gradientowe, zwane w skrócie gradient boosting.

11.3.1 AdaBoost

W technice AdaBoost każdy nowo dodawany członek zespołu (np. nowe drzewo decyzyjne czy klasyfikator MLP) jest trenowany na losowo wybranym zestawie danych uczących, przy czym każda próbka ucząca podlegająca losowaniu ma przypisaną wagę, której wartość jest uzależniona od aktualnego statystycznego błędu dla danej obserwacji przez aktualny stan zespołu [73]. Na starcie wszystkie obserwacje uczące mają identyczne wartości przypisanych wag, stąd prawdopodobieństwo ich wylosowania do zbioru uczącego danego członka zespołu jest identyczne. W wyniku ewaluacji danych przez aktualnie wytrenowany zespół następuje zwiększenie wagi dla obserwacji trudnych w testowaniu oraz zmniejszenie wagi dla danych, które dobrze wypadły na etapie ewaluacji. W efekcie obserwacje o większej wartości wagi mają zwiększone prawdopodobieństwo wylosowania do zbioru uczącego następnego członka zespołu (np. dodawanego drzewa decyzyjnego). Nowy członek zespołu w procesie uczenia specjalizuje się więc w rozpoznaniu przypadków trudniejszych. Każdy następny dodawany członek zespołu poddawany jest trenowaniu na zbiorze uczącym zawierającym coraz trudniejsze przypadki danych, źle rozpoznawane przez istniejących członków zespołu. Wynik działania tak powstałego zespołu jest sumą wagową wskazań poszczególnych członków, przy czym waga jest związana z wartością wagi przypisaną poszczególnym obserwacjom, dobraną wcześniej w procesie dodawania nowych członków zespołu. Jest to zasadnicza różnica w stosunku do klasycznej metody zwykłego głosowania większościowego, stosowanego w technice bagging [73].

Załóżmy, że dany jest zbiór par danych uczących klasyfikatora (x_i, d_i) dla i=1, 2, …, p, gdzie x_ijest wektorem wejściowym a d_i oznacza klasę kodowana na przykład w postaci binarnej (1, -1). Załóżmy, że zespół składa się z M słabych klasyfikatorów generujących wynik y_i przynależności klasowej 1 lub -1 dla każdego wektora wejściowego x_i. W wyniku (m-1) cykli tworzenia nowego członka powstanie zespół, którego werdykt przy pobudzeniu wektorem x_i będzie sumą wagową wskazań wszystkich członków [73]

$F_{m-1}\left(\mathbf{x}_i\right)=\alpha_1 y_1\left(\mathbf{x}_i\right)+\alpha_2 y_2\left(\mathbf{x}_i\right)+\cdots+\alpha_{m-1} y_{m-1}\left(\mathbf{x}_i\right)$

(11.11)

Po dodaniu $m$ -tego słabego predyktora wynik działania zespołu można przedstawić w postaci

$F_m\left(\mathbf{x}_i\right)=F_{m-1}\left(\mathbf{x}_i\right)+\alpha_m y_m\left(\mathbf{x}_i\right)$

(11.12)

Zadanie polega na doborze takiej wartości wagi $\alpha_m$ oraz wyniku $y_m\left(\mathbf{x}_i\right)$ sklasyfikowania wektora $\mathbf{x}_i$ przez $m$ -ty klasyfikator aby polepszyć działanie całego zespołu. Funkcję błędu (ang. loss function) definiuje się w postaci wykładniczej dla wszystkich wektorów $\mathbf{x}_i$ biorących udział w procesie uczenia

$E=\sum_{i=1}^p e^{-d_i F_m\left(\mathbf{x}_i\right)}=\sum_{i=1}^p e^{-d_i F_{m-1}\left(\mathbf{x}_i\right)} e^{-d_i \alpha_m y_m\left(\mathbf{x}_i\right)}$

(11.13)

Wprowadźmy oznaczenia wagowe w powyższym wzorze

w pierwszym cyklu tworzenia zespołu $w_i^{(1)}$
w $m$ -tym ( $m > 1$ cyklu $w_i^{(m)}=e^{-d_i F_{m-1}\left(\mathbf{x}_i\right)}$

Wówczas wyrażenie na funkcję błędu przyjmie postać

$E=\sum_{i=1}^p w_i^{(m)} e^{-d_i \alpha_m y_m\left(\mathbf{x}_i\right)}$

(11.14)

Rozdzielając to wyrażenie na dwa składniki:

jeden prawidłowo sklasyfikowany dla którego $d_i y_m\left(\mathbf{x}_i\right)=1$
drugi sklasyfikowany z błędem dla którego $d_i y_m\left(\mathbf{x}_i\right)=-1$

otrzymuje się wyrażenie na funkcję błędu w postaci

$E=\sum_{d_i=y\left(x_i\right)} w_i^{(m)} e^{-\alpha_m}+\sum_{d_i \neq y\left(x_i\right)} w_i^{(m)} e^{\alpha_m}=\sum_{i=1}^p w_i^{(m)} e^{-\alpha_m}+\sum_{d_i \neq y\left(x_i\right)} w_i^{(m)}\left(e^{\alpha_m}-e^{-\alpha_m}\right)$

(11.15)

Analiza powyższego wzoru wskazuje, że wartość błędu $E$ zależy jedynie od czynnika $\sum_{y\left(x_i\right) \neq d_i} w_i^{(m)} e^{\alpha_m}$ , gdzie $w_i^{(m)}=e^{-d_i F_{m-1}\left(\mathbf{x}_i\right)}$ . Minimalizacja błędu wymaga aby pochodna funkcji błędu względem $\alpha_m$ była równa zeru, co oznacza

$\frac{d E}{d \alpha_m}=\frac{d\left(\sum_{y\left(x_i\right)=d_i} w_i^{(m)} e^{-\alpha_m}+\sum_{y\left(x_i\right) \neq d_i} w_i^{(m)} e^{\alpha_m}\right)}{d \alpha_m}=0$

(11.16)

Rozwiązanie powyższej zależności określa optymalną wartość $\alpha_m$ w postaci

$\alpha_m=\frac{1}{2} \ln \left(\frac{\sum_{y\left(x_i\right)=d_i} w_i^{(m)}}{\sum_{y\left(x_i\right) \neq d_i} w_i^{(m)}}\right)$

(11.17)

Oznaczając względny błąd $m$ -tego klasyfikatora jako $\varepsilon_m$ , przy czym

$\boldsymbol{\varepsilon}_m=\left(\frac{\sum_{y\left(x_i\right) \neq d_i} w_i^{(m)}}{\sum_{i=1}^p w_i^{(m)}}\right)$

(11.18)

wzór na wartość wagi $\alpha_m$ przyjmie ostatecznąpostać

$\alpha_m=\frac{1}{2} \ln \left(\frac{1-\varepsilon_m}{\varepsilon_m}\right)$

(11.19)

Wartość ta będzie użyta w $m$ -tym kroku przy dodaniu następnego klasyfikatora do zespołu. Wynik klasyfikacji tak rozszerzonego zespołu dla wektora wejściowego $\mathbf{x}_i$ określa wówczas wzór

$F_m\left(\mathbf{x}_i\right)=\alpha_1 y_1\left(\mathbf{x}_i\right)+\alpha_2 y_2\left(\mathbf{x}_i\right)+\ldots+\alpha_m y_m\left(\mathbf{x}_i\right)$

(11.20)

gdzie $y_i$ $(i=1,2, \ldots, m)$ oznacza wskazanie klasy przez kolejnych członków zespołu, a współczynnik $\alpha_m$ wagę z jaka to wskazanie jest brane pod uwagę.

11.3.2 Gradient boosting

Technika zwana gradient boosting stosuje inne rozwiązanie tworzenia i trenowania zespołu słabych predyktorów [2,55]. W odróżnieniu od metody AdaBoost stosującej wagi przypisane obserwacjom w zależności od skali trudności w ich rozpoznaniu technika gradient boosting koncentruje się na gradiencie funkcji strat $E(d_i, y_i)$ przy czym funkcja strat może być rozumiana tradycyjnie jako różnica między wartościami aktualnymi i pożądanymi albo koncentrować się jedynie na określeniu jakości modelu, definiowanej dowolnie przez użytkownika. Kolejni członkowie są dodawani wybierając kierunek ujemnego gradientu funkcji strat, nie zmieniając przy tym parametrów dotychczasowych członków zespołu.

Podobnie jak w metodzie AdaBoost dany jest zbiór par danych uczących klasyfikatora $(\mathbf{x}_i, d_i)$ dla $(i=1,2, \ldots, p)$ , gdzie $\mathbf{x}_i$ jest wektorem wejściowym a $d_i$ oznacza klasę kodowana na przykład w postaci binarnej $(1, -1)$ . Załóżmy, że zespół składa się z $M$ słabych klasyfikatorów generujących wynik $y_i$ przynależności klasowej $1$ lub $-1$ dla każdego wektora wejściowego $\mathbf{x}_i$ . Celem jest stworzenie zespołu, którego działanie na zbiorze uczącym minimalizuje wartość średnią błędu. Wynik działania zespołu $M$ predyktorów przy pobudzeniu wektorem $\mathbf{x}_i$ będzie składał się z sumy wagowej wskazań poszczególnych jego członków

$F(\mathbf{x})=\sum_{i=1}^M \alpha_i y_i(\mathbf{x})+\mathrm{const}$

(11.21)

Dodanie $m$ -tego członka zespołu powinno zmienić wynik działania w kierunku minimalizacji wartości funkcji strat. Działanie zespołu złożonego teraz z $m$ członków można zapisać w postaci

$F_m(\mathbf{x})=F_{m-1}(\mathbf{x})+\underset{y_m}{\arg \min }\left(\sum_{i=1}^p E\left(d_i, F_{m-1}\left(\mathbf{x}_i\right)\right)+y_m\left(\mathbf{x}_i\right)\right)$

(11.22)

Rozwiązanie zastosowane w metodzie gradient boosting wykorzystuje metodę optymalizacyjną największego spadku, przy czym równanie (11.21) zastępuje się liniową aproksymacją uwzględniającą jedynie czynnik gradientowy (metoda największego spadku)

$F_m(\mathbf{x})=F_{m-1}(\mathbf{x})-\eta \sum_{i=1}^p \nabla_{F_{m-1}} E\left(d_i, F_{m-1}\left(\mathbf{x}_i\right)\right)$

(11.23)

gdzie $\eta$ jest wielkością kroku w kierunku malejącej wartości gradientu funkcji strat $\nabla_{F_{m-1}} E\left(d_i, F_{m-1}\left(\mathbf{x}_i\right)\right)$ . Wartość $\eta$ może podlegać optymalizacji w taki sposób, aby uzyskać minimum funkcji strat $E$ w każdym cyklu dodawania członka zespołu.

$\eta_{o p t}=\underset{\eta}{\arg \min } \sum_{i=1}^p E\left[d_i, F_{m-1}\left(\mathbf{x}_i\right)-\eta \nabla_{F_{m-1}} E\left(d_i, F_{m-1}\left(\mathbf{x}_i\right)\right)\right]$

(11.24)

Po dodaniu $m$ -tego członka wynik działania zespołu przy pobudzeniu wektorem $\mathbf{x}$ określa zmodyfikowany model

$F_m(\mathbf{x})=F_{m-1}(\mathbf{x})+\eta y_m(\mathbf{x})$

(11.25)

Technika gradient boosting jest najczęściej stosowana przy użyciu drzew decyzyjnych jako słabych predyktorów. Badania tego algorytmu pokazały, że najlepsze rezultaty uzyskuje się przy zastosowaniu liczby poziomów decyzyjnych od 4 do 8. W praktyce stosuje się dodatkowo inne metody regularyzacji.

Jednym z nich jest ograniczenie liczby drzew biorących udział w zespole. Wprawdzie zwiększenie ich liczby redukuje zwykle błąd uczenia, ale może prowadzić do „przeuczenia” pogarszając zdolność generalizacji (działanie modelu na danych nie uczestniczących w procesie uczenia). Zwykle obserwuje się zwiększoną efektywność działania zespołu jedynie do określonego poziomu populacji. Po uzyskaniu etapu stagnacji należy zaprzestać dodawania nowych członków.

Inna metoda regularyzacji wprowadza zmniejszenie wartości kroku $\eta$ w procesie adaptacyjnym, zastępując wzór (11.25) określający działanie zespołu jego zmodyfikowaną wersją

$F_m(\mathbf{x})=F_{m-1}(\mathbf{x})+v \eta y_m(\mathbf{x})$

(11.26)

w której współczynnik $v$ jest ułamkiem. Typowa wartość to $v=0.1$ . Tym nie mniej należy zwrócić uwagę, że oznacza to zmniejszenie realnej wartości kroku uczenia, wydłużające cały proces adaptacji systemu.

Jeszcze innym podejściem jest zastosowanie w uczeniu kolejnych członków zespołu zredukowanej liczby obserwacji losowo wybieranych ze zbioru uczącego (tzw. dropout ratio). Przyspiesza to proces uczenia nie pogarszając zdolności generalizacyjnych (typowa regularyzacja typu niejawnego).

Jako czynnik regularyzacyjny stosuje się również wprowadzenie minimalnej liczby obserwacji dopuszczalnej w węzłach decyzyjnych zanim podział zbioru będzie możliwy. Stosuje się również karanie za zbyt dużą liczbę węzłów decyzyjnych oraz liści w drzewach. Istotnym parametrem działającym jako regularyzacja jest wprowadzenie ograniczenie czasu uczenia poprzez obserwacje postępu w kolejnych cyklach dodawania członków zespołu. Proces podlega zakończeniu, jeśli dodanie kolejnych członków nie poprawia działania zespołu powyżej założonego progu względnego. Zastosowanie wielu metod regularyzacyjnych na raz polepsza zdolności generalizacji zespołu pozwalając przy użyciu słabych predyktorów uzyskać bardzo dobre wyniki klasyfikacji całego zespołu.

W tworzeniu zespołu klasyfikatorów można łączyć ze sobą różnego rodzaju systemy: neuronowe, sieci głębokie CNN, drzewa decyzyjne czy klasyfikatory bayesowskie. W szczególności pojedyncze jednostki zespołu mogą zawierać wewnątrz inne podzespoły, na przykład zastosowanie lasu drzew decyzyjnych (typowy zespół klasyfikatorów) w zespole z pojedynczą siecią MLP, RBF czy SVM. Każde rozwiązanie prowadzące do polepszenia wyników klasyfikacji jest akceptowalne.