Zagadnienia

11.1 Metoda wzmacnienia klasyfikatorów (ang. Boosting)
- 11.1.1 Wstęp
- 11.1.2 AdaBoost - opis algorytmu

11. Metoda wzmacnienia klasyfikatorów (ang. Boosting)

11.1. Metoda wzmacnienia klasyfikatorów (ang. Boosting)

11.1.1. Wstęp

\block

Boosting jest ogólną metodą służącą zwiększeniu skuteczności dowolnego algorytmu uczenia. Idea Budowanie “mocnego i złożonego klasyfikatora” ze “słabych i prostych klasyfikatorów”. \pause\block

Leslie Valiant i Michael Kearns byli pierwszymi, którzy pokazali, że “słabe” algorytmy uczące, których skuteczność jest nawet niewiele lepsza niż losowe zgadywanie, mogą być wykorzystane do stworzenia dowolnie skutecznego “silnego” klasyfikatora.
Robert Schapire jako pierwszy przedstawił algorytm wzmacniania działający w czasie wielomianowym.

Yoav Freund zaproponował znacznie bardziej efektywny algorytm wzmacniania, który mimo tego, że był w pewnym sensie optymalny, miał pewne istotne w praktyce wady.
Pierwsze eksperymenty z tymi wczesnymi algorytmami wzmacniania zostały przeprowadzone przez zespół Drucker, Schapire, Simard i dotyczyły zadania OCR (ang. optical character recognition), w którym sieci neuronowe były użyte jako “proste” klasyfikatory.
Freund i Schapire przedstawili algorytm AdaBoost, który rozwiązał wiele praktycznych trudności wcześniejszych algorytmów wzmacniania.

11.1.2. AdaBoost - opis algorytmu

Algorytm na wejściu otrzymuje zbiór treningowy $(x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{m},y_{m})$ , gdzie każdy $x_{i}$ należy do pewnej dziedziny problemu $X$ , natomiast każda etykieta (decyzja) $y_{i}$ należy do pewnego zbioru $Y$ . Dla ułatwienia będziemy na razie zakładać, że $Y=\{-1,+1\}$ .
AdaBoost (Adaptive Boosting) wywołuje wybrany “słaby” algorytm uczący w serii T iteracji. Zakładamy, że błąd uzyskiwanych klasyfikatorów na zbiorze treningowym jest mniejszy niż $\frac{1}{2}$ .
Jedną z głównych idei algorytmu jest strojenie rozkładu (lub wag elementów) dla zbioru treningowego. Wagę $i$ -tego elementu ze zbioru treningowego w iteracji $t$ będziemy oznaczali przez $D_{t}(i)$ .

Początkowo wszystkie wagi są ustawione na równe wartości;
Po każdej iteracji, wagi elementów źle klasyfikowanych są zwiększane. Dzięki temu mamy możliwość skierowania uwagi “słabego” klasyfikatora na pewne elementy (trudne do wyuczenia) ze zbioru treningowego.
Zadaniem “słabego” algorytmu uczącego jest zbudowanie klasyfikatora (ang. hypothesis) $h_{t}:X\rightarrow Y$ odpowiedniego dla aktualnego rozkładu $D_{t}$ .
Skuteczność takiego klasyfikatora jest mierzona przez jego błąd (z uwzględnieniem rozkładu $D_{t}$ ):

$\varepsilon _{t}=Pr_{{D_{t}}}[h_{t}(x_{i})\neq y_{i}]=\sum _{{i:h_{t}(i)\neq y_{i}}}D_{t}(i)$

W praktyce “słaby” algorytm uczący może być algorytmem, który uwzględnia rozkład $D_{t}$ . Nie jest to jednak konieczne. Kiedy algorytm nie pozwala na bezpośrednie uwzględnienie rozkładu $D_{t}$ , losuje się (względem $D_{t}$ ) podzbiór zbioru treningowego, na którym następnie wywołuje się algorytm uczący.
Kiedy AdaBoost dostaje klasyfikator $h_{t}$ dobierany jest parametr $\alpha _{t}$ . Intuicyjnie $\alpha _{t}$ odpowiada za wagę jaką przykładamy do klasyfikatora $h_{t}$ . Zauważmy, że $\alpha _{t}\geq 0$ gdy $\varepsilon _{t}\leq\frac{1}{2}$ . Ponadto $\alpha _{t}$ rośnie kiedy $\varepsilon _{t}$ maleje.
Rozkład $D_{t}$ jest następnie zmieniany tak, aby zwiększyć (zmniejszyć) wagi elementów zbioru treningowego, które są źle (dobrze) klasyfikowane przez $h_{t}$ . Stąd wagi mają tendencję do skupiania się na “trudnych” przykładach.

Dane: $(x_{1},y_{1}),\ldots,(x_{m},y_{m})$ , gdzie $x_{i}\in X$ , $y_{i}\in Y=\{-1,+1\}$
Inicjalizacja: $D_{1}(i)=\frac{1}{m}\$ dla $\ i=1,\ldots,m$

for $t=1,\ldots,T$ do:

<+-> Wykorzystując “słaby” algorytm uczący zbuduj klasyfikator $h_{t}:X\rightarrow\{-1,+1\}$

(uwzględniając rozkład $D_{t}$ ).
<+-> $\varepsilon _{t}=Pr_{{D_{t}}}[h_{t}(x_{i})\neq y_{i}]=\sum _{{i:h_{t}(i)\neq y_{i}}}D_{t}(i)$
<+-> $\alpha _{t}=\frac{1}{2}\ln(\frac{1-\varepsilon _{t}}{\varepsilon _{t}})$
<+-> Uaktualnij wagi elementów zbioru treningowego:

$\displaystyle D_{{t+1}}(i)$ $\displaystyle=$ $\displaystyle\frac{D_{t}(i)}{Z_{t}}\times\left\{\begin{array}[]{l}e^{{-\alpha _{t}}}\ \textrm{ jeśli }h_{t}(x_{i})=y_{i}\\ e^{{\alpha _{t}}}\ \ \textrm{ jeśli }h_{t}(x_{i})\neq y_{i}\end{array}\right.$

$\displaystyle=$ $\displaystyle\frac{1}{Z_{t}}\times D_{t}(i)\times e^{{-\alpha _{t}y_{i}h_{t}(x_{i})}}$

\pause
$Z_{t}$ jest czynnikiem normalizującym (wybranym tak, aby $D_{{t+1}}$ było rozkładem).

Wynikowy klasyfikator powstaje za pomocą ważonego głosowania klasyfikatorów $h_{t}$ , gdzie $\alpha _{t}$ jest wagą przypisaną klasyfikatorowi $h_{t}$ .

$t=$	1	2	$\dots$	$T$
słabe klasyfikatory	$h_{1}$	$h_{2}$	$\dots$	$h_{T}$
wagi	$\alpha _{1}$	$\alpha _{2}$	$\dots$	$\alpha _{T}$

\pause\pause
\pause

$H_{{final}}=$

Treść automatycznie generowana z plików źródłowych LaTeXa za pomocą oprogramowania wykorzystującego LaTeXML.

	$\displaystyle D_{{t+1}}(i)$	$\displaystyle=$	$\displaystyle\frac{D_{t}(i)}{Z_{t}}\times\left\{\begin{array}[]{l}e^{{-\alpha _{t}}}\ \textrm{ jeśli }h_{t}(x_{i})=y_{i}\\ e^{{\alpha _{t}}}\ \ \textrm{ jeśli }h_{t}(x_{i})\neq y_{i}\end{array}\right.$
		$\displaystyle=$	$\displaystyle\frac{1}{Z_{t}}\times D_{t}(i)\times e^{{-\alpha _{t}y_{i}h_{t}(x_{i})}}$

Systemy decyzyjne

Zagadnienia

11. Metoda wzmacnienia klasyfikatorów (ang. Boosting)

11.1. Metoda wzmacnienia klasyfikatorów (ang. Boosting)

11.1.1. Wstęp

11.1.2. AdaBoost - opis algorytmu