Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 63 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 65 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 67 Notice: Undefined index: mode in /home/misc/mst/public_html/common.php on line 69 Notice: Undefined variable: base in /home/misc/mst/public_html/lecture.php on line 36 Systemy decyzyjne – 11. Metoda wzmacnienia klasyfikatorów (ang. Boosting) – MIM UW

Zagadnienia

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.

Projekt współfinansowany przez Unię Europejską w ramach Europejskiego Funduszu Społecznego.

Projekt współfinansowany przez Ministerstwo Nauki i Szkolnictwa Wyższego i przez Uniwersytet Warszawski.