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.
  

• Algorytm na wejściu otrzymuje zbiór treningowy x1,y1,x2,y2,…,xm,ym, gdzie każdy xi należy do pewnej dziedziny problemu X, natomiast każda etykieta (decyzja) yi 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ż 12.

• 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 Dt⁢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) ht:X→Y odpowiedniego dla aktualnego rozkładu Dt.

• Skuteczność takiego klasyfikatora jest mierzona przez jego błąd (z uwzględnieniem rozkładu Dt):

  εt=P⁢rDtht⁢xi≠yi=∑i:ht⁢i≠yiDt⁢i

• W praktyce “słaby” algorytm uczący może być algorytmem, który uwzględnia rozkład Dt. Nie jest to jednak konieczne. Kiedy algorytm nie pozwala na bezpośrednie uwzględnienie rozkładu Dt, losuje się (względem Dt) podzbiór zbioru treningowego, na którym następnie wywołuje się algorytm uczący.

• Kiedy AdaBoost dostaje klasyfikator ht dobierany jest parametr αt. Intuicyjnie αt odpowiada za wagę jaką przykładamy do klasyfikatora ht. Zauważmy, że αt≥0 gdy εt≤12. Ponadto αt rośnie kiedy εt maleje.

• Rozkład Dt jest następnie zmieniany tak, aby zwiększyć (zmniejszyć) wagi elementów zbioru treningowego, które są źle (dobrze) klasyfikowane przez ht. Stąd wagi mają tendencję do skupiania się na “trudnych” przykładach.

Dane: x1,y1,…,xm,ym, gdzie xi∈X, yi∈Y=-1,+1
Inicjalizacja: D1⁢i=1m⁢ dla ⁢i=1,…,m
 
for t=1,…,T do:

• <+-> Wykorzystując “słaby” algorytm uczący zbuduj klasyfikator ht:X→-1,+1

  (uwzględniając rozkład Dt).

• <+-> εt=P⁢rDtht⁢xi≠yi=∑i:ht⁢i≠yiDt⁢i

• <+-> αt=12⁢ln⁡1-εtεt

• <+-> Uaktualnij wagi elementów zbioru treningowego:

  	Dt+1⁢i	=	Dt⁢iZt⁢⁡e-αt⁢⁢jeśli ⁢ht⁢xi=yieαt⁢⁢⁢jeśli ⁢ht⁢xi≠yi⁢
  		=	1Zt×Dt×i×e-αt⁢yi⁢ht⁢xi

  \pause

  Zt jest czynnikiem normalizującym (wybranym tak, aby Dt+1 było rozkładem).

Wynikowy klasyfikator powstaje za pomocą ważonego głosowania klasyfikatorów ht, gdzie αt jest wagą przypisaną klasyfikatorowi ht.

Hf⁢i⁢n⁢a⁢l=