Czy AdaBoost jest mniej lub bardziej podatny na nadmierne dopasowanie?

20

Czytałem różne (pozornie) sprzeczne stwierdzenia, czy AdaBoost (lub inne techniki wspomagające) są mniej lub bardziej podatne na nadmierne dopasowanie w porównaniu do innych metod uczenia się.

Czy istnieją dobre powody, by wierzyć w to jedno lub drugie? Jeśli to zależy, od czego to zależy? Jakie są powody, dla których AdaBoost jest mniej / bardziej podatny na nadmierne dopasowanie?

blubb
źródło
1
Moją intuicją jest to, że jest bardziej podatna na przerost niż losowy las. Algorytm został jednak zaprojektowany w taki sposób, aby uniknąć nadmiernego dopasowania i zwykle nie stanowi problemu. Nie mam żadnych odniesień, aby to zrobić, ale możesz użyć tego caretpakietu do krzyżowej weryfikacji adaboost, i zauważyłem, że zwykle dobrze się uogólnia.
Zach

Odpowiedzi:

17

Jak mówisz, wiele zostało omawianych na ten temat, a wraz z nim istnieje dość ciężka teoria, której muszę przyznać, że nigdy nie zrozumiałem w pełni. Z mojego praktycznego doświadczenia AdaBoost jest dość odporny na nadmierne dopasowanie, a LPBoost (Linear Programming Boosting) jeszcze bardziej (ponieważ funkcja celu wymaga rzadkiej kombinacji słabych uczniów, co jest formą kontroli zdolności). Główne czynniki, które wpływają na to:

  • „Siła” „słabych” uczniów: jeśli korzystasz z bardzo prostych słabych uczniów, takich jak pniaki decyzyjne (drzewa decyzyjne 1-poziomowe), algorytmy są znacznie mniej podatne na nadmierne dopasowanie. Ilekroć próbowałem użyć bardziej skomplikowanych słabych uczniów (takich jak drzewa decyzyjne, a nawet hiperplany), odkryłem, że przeuczenie następuje znacznie szybciej

  • Poziom hałasu w danych: AdaBoost jest szczególnie podatny na nadmierne dopasowanie w głośnych zestawach danych. W tym ustawieniu preferowane są formularze uregulowane (RegBoost, AdaBoostReg, LPBoost, QPBoost)

  • Wymiarowość danych: Wiemy, że ogólnie rzecz biorąc, doświadczamy nadmiernego dopasowania w przestrzeniach o dużych wymiarach („przekleństwo wymiarowości”), a AdaBoost może również cierpieć z tego powodu, ponieważ jest to po prostu liniowa kombinacja klasyfikatorów, których sami cierpią z problemu. Trudno ustalić, czy jest on tak podatny, jak inne klasyfikatory.

Oczywiście możesz użyć metod heurystycznych, takich jak zestawy sprawdzania poprawności lub k-fold cross-validation, aby ustawić parametr zatrzymania (lub inne parametry w różnych wariantach), tak jak dla każdego innego klasyfikatora.

tdc
źródło
9

Zgadzam się z większością punktów wymienionych w komentarzu tdc. muszę jednak dodać i poprawić kilka rzeczy.

  • Jak pokazano w L2Boost autorstwa Petera Bühlmanna, wraz ze wzrostem liczby słabych uczniów (rund wzmocnienia), tendencyjność zbiega się wykładniczo szybko, podczas gdy wariancja wzrasta o geometrycznie zmniejszające się wielkości, co oznacza: Jest o wiele wolniejsza niż większość innych metod.
  • Błędnie wspomniano w komentarzu Zacha, że ​​jest lepszy od przypadkowego lasu pod względem przebiegu. To jest całkowicie złe. W rzeczywistości, zgodnie z teorią (patrz oryginalny losowy artykuł leśny autorstwa Breimana), Random Forest jest absolutnie odporny na przeuczenie, o ile jego słabe klasyfikatory nie pasują do danych.
  • W przeciwieństwie do tego, co wspomniano w komentarzu tdc, większość metod wzmacniania jest bardzo wrażliwa na hałas związany z etykietowaniem i może łatwo się przewyższać w obecności szumu związanego z etykietowaniem.
  • W zestawach danych, w których wskaźniki błędów Bayesa są dalekie od zera (tj. Cechy nie są wystarczająco dyskryminujące), metody zwiększania mogą również łatwo się przestawić. Ponieważ próbują zredukować błąd szkolenia do zera, podczas gdy w rzeczywistości nawet optymalny klasyfikator, tj. Klasyfikator Bayesa może osiągnąć poziom powiedzmy 40% błędu.
  • wreszcie, i nie zostało to opublikowane gdziekolwiek (według mojej najlepszej wiedzy) istnieje rodzaj nadmiernego dopasowania, w którym błąd uogólnienia nie zwiększa się wraz ze wzrostem rund wzmocnienia, ale też nie maleje. Oznacza to, że algorytm utknął w lokalnych optymach. W tej sytuacji błąd szkolenia stale maleje, podczas gdy błąd testu pozostaje prawie stały. Do tej pory nigdy nie uważaliśmy tego zjawiska za przejaw nadmiernego dopasowania, ale uważam, że jest to przejaw nadmiernego dopasowania i używając bardziej złożonych słabych uczniów (dziwne!) Możemy w rzeczywistości temu przeciwdziałać (ten ostatni punkt należy rozpatrywać ostrożnie :RE)
TNM
źródło
1
Warto dodać do tej odpowiedzi, że mógłbym dziś doświadczyć tego drugiego rodzaju nadmiernego dopasowania, zarówno w przypadku AdaBoost, jak i Random Forest. W walidacji krzyżowej błąd out-of-fold zbiegał się do stałej z jedynie 20 podstawowymi estymatorami, a następnie odbijał się wokół tej stałej z dużą wariancją. Moje podejrzenia były dokładnie takie same: zachłanne algorytmy utknęły w jakimś lokalnym optimum. To nie jest potwierdzenie tego, co się stało, ale miło jest wiedzieć, że ktoś miał taką samą myśl.
shadowtalker
@ssdecontrol Czy możesz podzielić się tym, co zrobiłeś? Chcę odtworzyć wyniki, aby lepiej zrozumieć
saurabh agarwal
@saurabhagarwal Myślę, że pracowałem nad projektem Kaggle Titanic
shadowtalker