AdaBoost - AdaBoost

AdaBoost , skrót od Adaptive Boosting , to meta-algorytm klasyfikacji statystycznej sformułowany przez Yoava Freunda i Roberta Schapire , którzy za swoją pracę otrzymali Nagrodę Gödla w 2003 roku . Może być używany w połączeniu z wieloma innymi rodzajami algorytmów uczenia się, aby poprawić wydajność. Wyniki innych algorytmów uczenia („słabi uczniowie”) są łączone w ważoną sumę, która reprezentuje końcowy wynik wzmocnionego klasyfikatora. AdaBoost jest adaptacyjny w tym sensie, że kolejni słabi uczniowie są modyfikowani na korzyść przypadków błędnie sklasyfikowanych przez poprzednie klasyfikatory. W niektórych problemach może być mniej podatny na problem nadmiernego dopasowania niż inne algorytmy uczące. Poszczególni uczniowie mogą być słabi, ale dopóki wyniki każdego z nich są nieco lepsze niż losowe zgadywanie, można udowodnić, że ostateczny model jest zbieżny do silnego ucznia.

Każdy algorytm uczący ma tendencję do lepszego dopasowania do niektórych typów problemów niż do innych i zazwyczaj ma wiele różnych parametrów i konfiguracji, które należy dostosować, zanim osiągnie optymalną wydajność w zestawie danych. AdaBoost (z drzewami decyzyjnymi jako słabi uczniowie) jest często określany jako najlepszy, gotowy do użycia klasyfikator. W przypadku korzystania z uczenia drzewa decyzyjnego informacje zebrane na każdym etapie algorytmu AdaBoost o względnej „twardości” każdej próbki treningowej są wprowadzane do algorytmu wzrostu drzewa, tak że późniejsze drzewa mają tendencję do skupiania się na trudniejszych do sklasyfikowania przykładach.

Szkolenie

AdaBoost odnosi się do konkretnej metody trenowania wzmocnionego klasyfikatora. Klasyfikator doładowania to klasyfikator w formie

${\ Displaystyle F_ {T} (x) = \ suma _ {t = 1} ^ {T} f_ {t} (x) \ \!}$

gdzie każdy jest słabym uczniem, który przyjmuje obiekt jako dane wejściowe i zwraca wartość wskazującą klasę obiektu. Na przykład w zadaniu dwuklasowym znak słabego wyniku ucznia identyfikuje przewidywaną klasę obiektu, a wartość bezwzględna daje pewność tej klasyfikacji. Podobnie, klasyfikator jest dodatni, jeśli próbka jest w klasie dodatniej, a w przeciwnym razie ujemna. ${\displaystyle f_{t}}$${\displaystyle x}$${\displaystyle T}$

Każdy słaby uczeń tworzy hipotezę wyjściową, , dla każdej próbki w zbiorze uczącym . W każdej iteracji wybierany jest słaby uczący się i przypisywany mu współczynnik taki, że sumaryczny błąd uczący wynikowego klasyfikatora wzmocnienia -etapowego jest zminimalizowany. ${\ Displaystyle h (x_ {i})}$${\displaystyle t}$${\ Displaystyle \ alfa _ {t}}$${\ Displaystyle E_ {t}}$${\displaystyle t}$

${\ Displaystyle E_ {t} = \ suma _ {i} E [F_ {t-1} (x_ {i}) + \ alfa _ {t} h (x_ {i})]}$

Oto wzmocniony klasyfikator, który został zbudowany na poprzednim etapie szkolenia, jest funkcją błędu i jest słabym uczniem, który jest rozważany jako dodatek do końcowego klasyfikatora. ${\ Displaystyle F_ {t-1} (x)}$${\ Displaystyle E (F)}$${\ Displaystyle f_ {t} (x) = \ alfa _ {t} h (x)}$

Ważenie

W każdej iteracji procesu uczącego każdej próbce w zbiorze uczącym przypisywana jest waga równa aktualnemu błędowi na tej próbce. Wagi te mogą być wykorzystane do informowania o szkoleniu słabego ucznia, na przykład można wyhodować drzewa decyzyjne, które faworyzują dzielenie zestawów próbek o wysokich wagach. ${\displaystyle w_{i,t}}$${\ Displaystyle E (F_ {t-1} (x_ {i}))}$

Pochodzenie

To wyprowadzenie następuje po Rojas (2009):

Załóżmy, że mamy zestaw danych, w którym każdy element ma skojarzoną klasę oraz zestaw słabych klasyfikatorów, z których każdy generuje klasyfikację dla każdego elementu. Po -tej iteracji nasz klasyfikator wzmocniony jest liniową kombinacją słabych klasyfikatorów postaci: ${\ Displaystyle \ {(x_ {1}, y_ {1}), \ ldots, (x_ {N}, y_ {N}) \}}$${\displaystyle x_{i}}$${\ Displaystyle y_ {i} \ w \ {-1, 1 \}}$${\displaystyle \{k_{1},\ldots,k_{L}\}}$${\ Displaystyle k_ {j} (x_ {i}) \ w \ {-1,1 \}}$${\ Displaystyle (m-1)}$

${\ Displaystyle C_ {(m-1)} (x_ {i}) = \ alfa _ {1} k_ {1} (x_ {i}) + \ cdots + \ alfa _ {m-1} k_ {m- 1}(x_{i})}$

Gdzie klasa będzie znakiem . W -tej iteracji chcemy rozszerzyć to na lepiej wzmocniony klasyfikator, dodając kolejny słaby klasyfikator o innej wadze : ${\ Displaystyle C_ {(m-1)} (x_ {i})}$${\ Displaystyle m}$${\displaystyle k_{m}}$${\ Displaystyle \ alfa _ {m}}$

${\ Displaystyle C_ {m} (x_ {i}) = C_ {(m-1)} (x_ {i}) + \ alfa _ {m} k_ {m} (x_ {i})}$

Pozostaje więc ustalić, który słaby klasyfikator jest najlepszym wyborem i jaka powinna być jego waga . Określamy całkowity błąd w jako sumę jej wykładniczej straty na każdym punkcie danych, biorąc pod uwagę, co następuje: ${\displaystyle k_{m}}$${\ Displaystyle \ alfa _ {m}}$${\ Displaystyle E}$${\ Displaystyle C_ {m}}$

${\ Displaystyle E = \ suma _ {i = 1} ^ {N} e ^ {-y_ {i} C_ {m} (x_ {i})} = \ suma _ {i = 1} ^ {N} e ^{-y_{i}C_{(m-1)}(x_{i})}e^{-y_{i}\alpha _{m}k_{m}(x_{i})}}$

Wynajem i dla , mamy: ${\ Displaystyle w_ {i} ^ {(1)} = 1}$${\ Displaystyle w_ {i} ^ {(m)} = e ^ {-y_ {i} C_ {m-1} (x_ {i})}}$${\ Displaystyle m> 1}$

${\ Displaystyle E = \ suma _ {i = 1} ^ {N} w_ {i} ^ {(m)} e ^ {-y_ {i} \ alfa _ {m} k_ {m} (x_ {i} )}}$

Możemy podzielić to podsumowanie na te punkty danych, które są poprawnie sklasyfikowane przez (so ) i te, które są błędnie sklasyfikowane (so ): ${\displaystyle k_{m}}$${\ Displaystyle y_ {i} k_ {m} (x_ {i}) = 1}$${\ Displaystyle y_ {i} k_ {m} (x_ {i}) = -1}$

${\ Displaystyle E = \ suma _ {y_ {i} = k_ {m} (x_ {i})} w_ {i} ^ {(m)} e ^ {- \ alfa _ {m}} + \ suma _ {y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}e^{\alpha _{m}}}$

${\ Displaystyle = \ suma _ {i = 1} ^ {N} w_ {i} ^ {(m)} e ^ {- \ alfa _ {m}} + \ suma _ {y_ {i} \ neq k_ { m}(x_{i})}w_{i}^{(m)}(e^{\alpha _{m}}-e^{-\alpha _{m}})}$

Ponieważ jedyną częścią prawej strony tego równania, od której zależy, jest , widzimy, że minimalizująca to ta, która minimalizuje [zakładając, że ], czyli słaby klasyfikator z najmniejszym błędem ważonym (z wagami ). ${\displaystyle k_{m}}$${\ Displaystyle \ suma _ {y_ {i} \ neq k_ {m} (x_ {i})} w_ {i} ^ {(m)}}$${\displaystyle k_{m}}$${\ Displaystyle E}$${\ Displaystyle \ suma _ {y_ {i} \ neq k_ {m} (x_ {i})} w_ {i} ^ {(m)}}$${\ Displaystyle \ alfa _ {m}> 0}$${\ Displaystyle w_ {i} ^ {(m)} = e ^ {-y_ {i} C_ {m-1} (x_ {i})}}$

Aby określić pożądaną wagę, która minimalizuje się z tą , którą właśnie ustaliliśmy, rozróżniamy: ${\ Displaystyle \ alfa _ {m}}$${\ Displaystyle E}$${\displaystyle k_{m}}$

${\ Displaystyle {\ Frac {de} {d \ alfa _ {m}}} = {\ Frac {d (\ suma _ {y_ {i} = k_ {m} (x_ {i})} w_ {i} ^{(m)}e^{-\alpha _{m}}+\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}e ^{\alfa _{m}})}{d\alfa _{m}}}}$

Ustawiając to na zero i rozwiązując plony: ${\ Displaystyle \ alfa _ {m}}$

${\ Displaystyle \ alfa _ {m} = {\ Frac {1} {2}} \ ln \ lewo ({\ Frac {\ suma _ {y_ {i} = k_ {m} (x_ {i})} w_ {i}^{(m)}}{\sum _{y_{i}\neq k_{m}(x_{i})}w_{i}^{(m)}}}\right)}$

Obliczamy ważoną stopę błędu słabego klasyfikatora jako , a zatem wynika, że: ${\ Displaystyle \ epsilon _ {m} = \ suma _ {y_ {i} \ neq k_ {m} (x_ {i})} w_ {i} ^ {(m)} / \ suma _ {i = 1} ^{N}w_{i}^{(m)}}$

${\ Displaystyle \ alfa _ {m} = {\ Frac {1} {2}} \ ln \ lewo ({\ Frac {1-\ epsilon _ {m}} {\ epsilon _ {m}}} \ po prawej) }$

czyli ujemna funkcja logitowa pomnożona przez 0,5.

W ten sposób wyprowadziliśmy algorytm AdaBoost: w każdej iteracji wybierz klasyfikator , który minimalizuje całkowity błąd ważony , użyj go do obliczenia stopy błędu , użyj tego do obliczenia wagi , a na koniec użyj tego do poprawienia wzmocnionego klasyfikatora do . ${\displaystyle k_{m}}$${\ Displaystyle \ suma _ {y_ {i} \ neq k_ {m} (x_ {i})} w_ {i} ^ {(m)}}$${\ Displaystyle \ epsilon _ {m} = \ suma _ {y_ {i} \ neq k_ {m} (x_ {i})} w_ {i} ^ {(m)} / \ suma _ {i = 1} ^{N}w_{i}^{(m)}}$${\ Displaystyle \ alfa _ {m} = {\ Frac {1} {2}} \ ln \ lewo ({\ Frac {1-\ epsilon _ {m}} {\ epsilon _ {m}}} \ po prawej) }$${\ Displaystyle C_ {m-1}}$${\ Displaystyle C_ {m} = C_ {(m-1)} + \ alfa _ {m} k_ {m}}$

Statystyczne zrozumienie wzmocnienia

Wzmacnianie jest formą regresji liniowej, w której cechy każdej próbki są wynikami niektórych słabych uczniów zastosowanych do . ${\displaystyle x_{i}}$${\ Displaystyle h}$${\displaystyle x_{i}}$

Choć stara regresji, aby pasowały do tak dokładnie, jak to możliwe bez utraty uogólnienia, zazwyczaj z zastosowaniem co najmniej kwadratowy błąd , funkcja błędu adaboost bierze pod uwagę fakt, że tylko znak końcowy wynik jest używany, więc może być znacznie większa niż 1 bez zwiększania błąd. Jednak wykładniczy wzrost błędu dla próby wraz ze wzrostem powoduje, że nadmierną wagę przypisuje się wartościom odstającym. ${\ Displaystyle F (x)}$${\ Displaystyle y (x)}$${\ Displaystyle E (f) = (y (x) - f (x)) ^ {2}}$${\ Displaystyle E (f) = e ^ {-y (x) f (x)}}$${\ Displaystyle | F (x) |}$${\displaystyle x_{i}}$${\ Displaystyle -y (x_ {i}) f (x_ {i})}$

Jedną z cech wyboru wykładniczej funkcji błędu jest to, że błąd końcowego modelu addytywnego jest iloczynem błędu każdego etapu, czyli . Widać zatem, że aktualizacja wagi w algorytmie AdaBoost jest równoznaczna z ponownym obliczeniem błędu po każdym etapie. ${\ Displaystyle e ^ {\ suma _ {i}-y_ {i} f (x_ {i})} = \ prod _ {i} e ^ {-y_ {i} f (x_ {i})}}$${\ Displaystyle F_ {t} (x)}$

Dozwolona jest duża elastyczność w wyborze funkcji straty. Dopóki funkcja strat jest monotoniczna i ciągle różniczkowalna , klasyfikator zawsze kieruje się w stronę czystszych rozwiązań. Zhang (2004) dostarcza funkcję straty opartą na najmniejszych kwadratach, zmodyfikowaną funkcję straty Hubera :

${\ Displaystyle \ phi (y, f (x)) = {\ zacząć {przypadki} -4yf (x) i {\ mbox {jeśli}} yf (x) <-1, \ \ (yf (x) -1 )^{2}&{\mbox{if }}-1\leq yf(x)\leq 1,\\0&{\mbox{if }}yf(x)>1\end{cases}}}$

Ta funkcja jest lepiej zachowana niż LogitBoost dla wartości bliskich 1 lub -1, nie karze „zbyt pewnych ” prognoz ( ), w przeciwieństwie do niezmodyfikowanych najmniejszych kwadratów, i karze tylko próbki błędnie sklasyfikowane z ufnością większą niż 1 liniowo, w przeciwieństwie do kwadratowej lub wykładniczej , a tym samym jest mniej podatny na działanie wartości odstających. ${\displaystyle f(x)}$${\displaystyle yf(x)>1}$

Wzmacnianie jako zejście gradientowe

Wzmocnienie może być postrzegane jako minimalizacja wypukłej funkcji straty nad wypukłym zbiorem funkcji. W szczególności strata minimalizowana przez AdaBoost jest stratą wykładniczą , podczas gdy LogitBoost wykonuje regresję logistyczną, minimalizując . ${\ Displaystyle \ suma _ {i} \ phi (i, y, f) = \ suma _ {i} e ^ {-y_ {i} f (x_ {i})}}$${\ Displaystyle \ suma _ {i} \ phi (i, y, f) = \ suma _ {i} \ ln \ lewo (1 + e ^ {-y_ {i} f (x_ {i})} \ prawo )}$

W analogii ze spadkiem gradientu wynik klasyfikatora dla każdego punktu treningowego jest uważany za punkt w przestrzeni n-wymiarowej, gdzie każda oś odpowiada próbce treningowej, każdemu słabemu uczniowi odpowiada wektor o ustalonej orientacji i długości, a cel jest osiągnięcie punktu docelowego (lub dowolnego regionu, w którym wartość funkcji straty jest mniejsza niż wartość w tym punkcie) w najmniejszej liczbie kroków. Zatem algorytmy AdaBoost wykonują albo Cauchy'ego (znajdź z najbardziej stromym gradientem, wybierz minimalizację błędu testu) lub Newtona (wybierz jakiś punkt docelowy, znajdź, który zbliża się do tego punktu) optymalizację błędu treningu. ${\ Displaystyle \ lewo (F_ {t} (x_ {1}), \ kropki, F_ {t} (x_ {n}) \ po prawej)}$${\ Displaystyle h (x)}$${\ Displaystyle (y_ {1}, \ kropki, y_ {n})}$${\ Displaystyle E_ {T} (x_ {1}, \ kropki, x_ {n})}$${\ Displaystyle h (x)}$${\ Displaystyle \ alfa}$${\ Displaystyle \ alfa h (x)}$${\ Displaystyle F_ {t}}$

Przykładowy algorytm (Discrete AdaBoost)

Z:

• Próbki ${\displaystyle x_{1}\kropki x_{n}}$
• Pożądane wyjścia ${\ Displaystyle y_ {1} \ kropki y_ {n}, y \ w \ {-1, 1 \}}$
• Wagi początkowe ustawione na${\ Displaystyle w_ {1,1} \ kropki w_ {n, 1}}$${\ Displaystyle {\ Frac {1} {n}}}$
• Funkcja błędu ${\ Displaystyle E (f (x), y, ja) = e ^ {-y_ {i} f (x_ {i})}}$
• Słabi uczniowie ${\ Displaystyle h \ dwukropek x \ rightarrow \ {-1, 1 \}}$

Za w : ${\displaystyle t}$${\displaystyle 1\kropki T}$

• Wybierz : ${\ Displaystyle h_ {t} (x)}$
  • Znajdź słabego ucznia, który minimalizuje błąd sumy ważonej dla błędnie sklasyfikowanych punktów${\ Displaystyle h_ {t} (x)}$${\ Displaystyle \ epsilon _ {t}}$${\ Displaystyle \ epsilon _ {t} = \ suma _ {\ stackrel {i = 1} {h_ {t} (x_ {i}) \ neq y_ {i}}} ^ {n} w_ {i, t} }$
  • Wybierać ${\ Displaystyle \ alfa _ {t} = {\ Frac {1} {2}} \ ln \ lewo ({\ Frac {1-\ epsilon _ {t}} {\ epsilon _ {t}}} \ po prawej) }$
• Dodaj do zespołu:
  • ${\ Displaystyle F_ {t} (x) = F_ {t-1} (x) + \ alfa _ {t} h_ {t} (x)}$
• Zaktualizuj wagi:
  • ${\ Displaystyle w_ {i, t + 1} = w_ {i, t} e ^ {-y_ {i} \ alfa _ {t} h_ {t} (x_ {i})}}$dla in${\displaystyle i}$${\displaystyle 1\kropki n}$
  • Zrenormalizuj tak, aby${\displaystyle w_{i,t+1}}$${\ Displaystyle \ suma _ {i} w_ {i, t + 1} = 1}$
  • (Uwaga: można to wykazać na każdym kroku, co może uprościć obliczanie nowych wag.)${\ Displaystyle {\ Frac {\ suma _ {h_ {t + 1} (x_ {i}) = y_ {i}} w_ {i, t + 1}} {\ suma _ {h_ {t + 1} ( x_{i})\neq y_{i}}w_{i,t+1}}}={\frac {\sum _{h_{t}(x_{i})=y_{i}}w_{i ,t}}{\suma _{h_{t}(x_{i})\neq y_{i}}w_{i,t}}}}$

Wybór α _t

${\ Displaystyle \ alfa _ {t}}$ jest wybrany, ponieważ można go analitycznie wykazać jako minimalizator funkcji błędu wykładniczego dla Discrete AdaBoost.

Zminimalizować:

${\ Displaystyle \ suma _ {i} w_ {i} e ^ {-y_ {i} h_ {i} \ alfa _ {t}}}$

Wykorzystując wypukłość funkcji wykładniczej i zakładając, że mamy: ${\ Displaystyle \ dla wszystkich ja, h_ {i} \ w \ {-1, 1 \}}$

${\ Displaystyle {\ zacząć {wyrównany} \ suma _ {i} w_ {i} e ^ {-y_ {i} h_ {i} \ alfa _ {t}} i \ leq \ suma _ {i} \ lewo ( {\frac {1-y_{i}h_{i}}{2}}\right)w_{i}e^{\alpha _{t}}+\sum _{i}\left({\frac { 1+y_{i}h_{i}}{2}}\right)w_{i}e^{-\alpha _{t}}\\&=\left(\epsilon _{t}\right)e ^{\alpha _{t}}+\left(1-\epsilon _{t}\right)e^{-\alpha _{t}}\end{aligned}}}$

Następnie różnicujemy to wyrażenie względem i ustawiamy je na zero, aby znaleźć minimum górnej granicy: ${\ Displaystyle \ alfa _ {t}}$

${\ Displaystyle {\ zacząć {wyrównany} \ po lewej (\ epsilon _ {t} \ po prawej) e ^ {\ alfa _ {t}} - \ po lewej (1- \ epsilon _ {t} \ po prawej) e ^ {- \alpha _{t}}&=0\\\alpha _{t}&={\frac {1}{2}}\ln \left({\frac {1-\epsilon _{t}}{\ epsilon _{t}}}\right)\end{aligned}}}$

Należy pamiętać, że ma to zastosowanie tylko wtedy , gdy , choć może być dobrym początkiem w innych przypadkach, na przykład gdy słaby uczeń jest stronniczy ( ), ma wiele liści ( ) lub pełni inną funkcję . W takich przypadkach wybór słabego ucznia i współczynnika można skondensować do pojedynczego kroku, w którym wybierany jest ze wszystkich możliwych jako minimalizator przez jakąś procedurę wyszukiwania numerycznego. ${\ Displaystyle h_ {i} \ w \ {-1, 1 \}}$${\ Displaystyle h (x) \ w \ {a, b \}, a \ neq -b}$${\ Displaystyle h (x) \ w \ {a, b, \ kropki, n \}}$${\ Displaystyle h (x) \ w \ mathbb {R}}$${\ Displaystyle f_ {t} = \ alfa _ {t} h_ {t} (x)}$${\displaystyle \alfa,h}$${\ Displaystyle \ suma _ {i} w_ {i, t} e ^ {-y_ {i} f_ {t} (x_ {i})}}$

Warianty

Prawdziwe AdaBoost

Wynikiem drzew decyzyjnych jest oszacowanie prawdopodobieństwa klasy , prawdopodobieństwo znajdujące się w klasie dodatniej. Friedman, Hastie i Tibshirani wyprowadzają analityczny minimalizator dla pewnych stałych (zwykle wybieranych przy użyciu ważonego błędu najmniejszych kwadratów): ${\ Displaystyle p (x) = P (y = 1 | x)}$${\displaystyle x}$${\ Displaystyle e ^ {-y \ lewo (F_ {t-1} (x) + f_ {t} (p (x)) \ prawo)}}$${\displaystyle p(x)}$

${\ Displaystyle f_ {t} (x) = {\ Frac {1} {2}} \ ln \ lewo ({\ Frac {x} {1-x}} \ prawej)}$.

Dlatego zamiast mnożyć wynik całego drzewa przez pewną stałą wartość, każdy węzeł liścia jest zmieniany tak, aby wyprowadzał połowę transformacji logitowej swojej poprzedniej wartości.

LogitBoost

LogitBoost reprezentuje zastosowanie ustalonych technik regresji logistycznej do metody AdaBoost. Zamiast minimalizować błąd w odniesieniu do y, słabi uczniowie są wybierani tak, aby zminimalizować (ważony najmniejszych kwadratów) błąd w odniesieniu do ${\ Displaystyle f_ {t} (x)}$

${\ Displaystyle Z_ {t} = {\ Frac {y ^ {*}-p_ {t} (x)} {2p_ {t} (x) (1-p_ {t} (x))}}}$

gdzie

${\ Displaystyle p_ {t} (x) = {\ Frac {e ^ {F_ {t-1} (x)}} {e ^ {F_ {t-1} (x)} + e ^ {-F_ { t-1}(x)}}},}$

${\ Displaystyle w_ {t} = p_ {t} (x) (1-p_ {t} (x))}$

${\ Displaystyle y ^ {*} = {\ Frac {y + 1} {2}}.}$

Że jest to Newton-Raphsona przybliżeniem Minimizer błędu log-prawdopodobieństwa na scenie , a słaby uczeń został wybrany jako ucznia, który najlepiej aproksymuje przez ważonych najmniejszych kwadratów. ${\displaystyle z_{t}}$${\displaystyle t}$${\displaystyle f_{t}}$${\displaystyle z_{t}}$

Gdy p zbliża się do 1 lub 0, wartość z staje się bardzo mała, a składnik z , który jest duży dla błędnie zaklasyfikowanych próbek, może stać się numerycznie niestabilny z powodu błędów zaokrąglania precyzji maszyny. Można to przezwyciężyć, narzucając pewien limit wartości bezwzględnej z i minimalnej wartości  w${\ Displaystyle p_ {t} (x_ {i}) (1-p_ {t} (x_ {i}))}$

Delikatny AdaBoost

Podczas gdy poprzednie algorytmy wzmacniające wybierają chciwie, minimalizując ogólny błąd testu na każdym kroku, GentleBoost oferuje ograniczony rozmiar kroku. jest wybrany, aby zminimalizować i nie jest stosowany żaden inny współczynnik. Tak więc w przypadku, gdy słaby uczeń wykazuje doskonałą wydajność klasyfikacji, GentleBoost wybiera dokładnie równe , podczas gdy algorytmy najbardziej stromego zniżania próbują ustawić . Obserwacje empiryczne dotyczące dobrej wydajności GentleBoost wydają się potwierdzać uwagę Schapire i Singera, że ​​dopuszczanie zbyt dużych wartości może prowadzić do słabej wydajności uogólniania. ${\displaystyle f_{t}}$${\displaystyle f_{t}}$${\ Displaystyle \ suma _ {i} w_ {t, i} (y_ {i}-f_ {t} (x_ {i})) ^ {2}}$${\ Displaystyle f_ {t} (x) = \ alfa _ {t} h_ {t} (x)}$${\displaystyle y}$${\ Displaystyle \ alfa _ {t} = \ infty}$${\ Displaystyle \ alfa}$

Wczesne zakończenie

Technika przyspieszania przetwarzania wzmocnionych klasyfikatorów, wczesne zakończenie odnosi się tylko do testowania każdego potencjalnego obiektu z tyloma warstwami końcowego klasyfikatora, które są niezbędne do osiągnięcia pewnego progu ufności, przyspieszając obliczenia w przypadkach, w których można łatwo określić klasę obiektu. Jednym z takich schematów jest struktura wykrywania obiektów wprowadzona przez Violę i Jonesa: w aplikacji ze znacznie większą liczbą próbek ujemnych niż dodatnich szkolona jest kaskada oddzielnych klasyfikatorów wzmacniających, a wynik każdego etapu jest obciążony tak, że pewna dopuszczalna niewielka część próbek dodatnich jest błędnie oznakowane jako ujemne, a wszystkie próbki oznaczone jako ujemne po każdym etapie są odrzucane. Jeśli 50% negatywnych próbek zostanie odfiltrowanych na każdym etapie, tylko bardzo niewielka liczba obiektów przejdzie przez cały klasyfikator, zmniejszając wysiłek obliczeniowy. Od tego czasu metoda ta została uogólniona, z formułą przewidzianą do wyboru optymalnych progów na każdym etapie w celu osiągnięcia pożądanego odsetka wyników fałszywie dodatnich i fałszywie ujemnych.

W dziedzinie statystyki, gdzie AdaBoost jest częściej stosowane do problemów o umiarkowanej wymiarowości, wczesne zatrzymanie jest wykorzystywane jako strategia redukcji overfittingu . Zbiór walidacyjny próbek jest oddzielany od zbioru uczącego, wydajność klasyfikatora na próbkach użytych do uczenia jest porównywana z wydajnością na próbkach walidacyjnych, a uczenie zostaje zakończone, jeśli wydajność na próbce walidacyjnej spada, nawet jeśli wydajność na próbce walidacyjnej zestaw treningowy stale się poprawia.

Algorytmy całkowicie korygujące

W przypadku najbardziej stromych wersji AdaBoost, gdzie jest wybierana na każdej warstwie t, aby zminimalizować błąd testu, następna dodana warstwa jest uważana za maksymalnie niezależną od warstwy t : jest mało prawdopodobne, aby wybrać słabego ucznia t+1, który jest podobny do ucznia t . Pozostaje jednak możliwość, że t+1 wygeneruje podobne informacje do jakiejś innej wcześniejszej warstwy. Całkowicie korygujące algorytmy, takie jak LPBoost , optymalizują wartość każdego współczynnika po każdym kroku, tak aby nowe dodawane warstwy były zawsze maksymalnie niezależne od każdej poprzedniej warstwy. Można to osiągnąć poprzez backfit, programowanie liniowe lub inną metodę. ${\ Displaystyle \ alfa _ {t}}$

Przycinanie

Przycinanie to proces usuwania słabo działających słabych klasyfikatorów w celu poprawienia pamięci i kosztu czasu wykonania ulepszonego klasyfikatora. Najprostsze metody, które mogą być szczególnie skuteczne w połączeniu z treningiem całkowicie korygującym, to przycinanie wagi lub marginesu: gdy współczynnik lub udział w całkowitym błędzie testu jakiegoś słabego klasyfikatora spada poniżej pewnego progu, ten klasyfikator jest porzucone. Margineantu i Dietterich zasugerowali alternatywne kryterium przycinania: słabe klasyfikatory należy dobierać w taki sposób, aby zmaksymalizować różnorodność zespołu. Jeśli dwóch słabych uczniów daje bardzo podobne wyniki, wydajność można poprawić usuwając jednego z nich i zwiększając współczynnik pozostałego słabego ucznia.

Zobacz też

• Agregacja Bootstrap
• CoBoosting
• BrownBoost
• Wzmocnienie gradientu
• Metoda multiplikatywnej aktualizacji wagi § Algorytm AdaBoost

Bibliografia

Dalsza lektura