Bagging (agregacja bootstrapowa)
- Autor metody
- Breiman, L.
- Rok
- 1996
- Typ
- Ensemble meta-algorithm (variance reduction via bootstrap aggregation)
Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku
Do czego służy?
Bagging, skrót od Bootstrap Aggregating, to meta-algorytm zespołowy wprowadzony przez Leo Breimana w 1996 roku, który trenuje wiele kopii bazowego modelu uczącego na niezależnie pobranych próbach bootstrapowych danych treningowych i łączy ich predykcje — przez uśrednianie dla regresji lub głosowanie większościowe dla klasyfikacji — w celu uzyskania finalnego predyktora o znacznie niższej wariancji niż pojedynczy bazowy model uczący.
Intuicja stojąca za metodą
Wyobraźmy sobie, że prosimy jednego eksperta o opinię: jego odpowiedź zależy mocno od jego konkretnych doświadczeń. Teraz wyobraźmy sobie, że prosimy stu ekspertów, z których każdy ma nieco inne tło, i uśredniamy ich odpowiedzi. Indywidualne cechy znoszą się nawzajem, a konsensus grupy jest znacznie bardziej wiarygodny. Bagging robi dokładnie to samo dla modeli uczenia maszynowego: generuje wiele nieco różnych zbiorów treningowych poprzez próbkowanie z powtórzeniami oryginalnych danych, trenuje jeden model dla każdego zbioru i łączy wszystkie predykcje. Każdy model widzi inny wycinek rzeczywistości, więc ich indywidualne błędy zazwyczaj się nie pokrywają, a agregat jest znacznie stabilniejszy niż jakikolwiek pojedynczy model.
Historia
Leo Breiman opublikował Bagging Predictors in Machine Learning w 1996 roku, motywowany obserwacją, że niestabilne modele uczące — te, których wyjście znacząco się zmienia pod wpływem małych perturbacji danych — mogą być stabilizowane przez uśrednianie replik bootstrapowych zbioru treningowego. Uzasadnienie teoretyczne opiera się na dekompozycji bias-wariancja: uśrednianie redukuje wariancję, pozostawiając obciążenie (bias) niezmienione. Breiman zademonstrował spójne poprawy dokładności w porównaniu z pojedynczymi drzewami decyzyjnymi na zestawie benchmarków klasyfikacji i regresji. Bagging szybko stał się fundamentalną techniką zespołową i bezpośrednio zainspirował Random Forest (Breiman, 2001), który dodaje losowe próbkowanie cech przy każdym podziale, aby dalej de-korelować drzewa i osiągnąć jeszcze większą redukcję wariancji. Obecnie bagging służy jako koncepcyjny kręgosłup dla szerokiej rodziny metod zespołowych i jest standardowym tematem w programach nauczania uczenia maszynowego na poziomie magisterskim.
Kiedy stosować
Bagging jest odpowiedni, gdy bazowy algorytm uczący ma wysoką wariancję — to znaczy, jest wrażliwy na małe perturbacje w danych treningowych — a redukcja tej wariancji jest głównym źródłem błędu. Kanonicznym przykładem są w pełni rozwinięte, nieprzycinane drzewa decyzyjne. Bagging nadaje się zarówno do klasyfikacji, jak i regresji na danych tabelarycznych, nie wymaga założeń dotyczących rozkładu danych i obsługuje mieszane typy cech. Jest najbardziej korzystny, gdy zbiór danych jest wystarczająco duży, aby wspierać B niezależnych prób bootstrapowych o odpowiedniej jakości (praktyczna dolna granica to co najmniej około 30 obserwacji, choć preferowane są setki). Bagging nie jest korzystny, gdy bazowy model uczący jest już stabilny (np. regresja liniowa w dobrze określonych problemach) lub gdy dominującym źródłem błędu jest obciążenie (bias) zamiast wariancji — w takich przypadkach bardziej odpowiednie są metody boostingowe.
Ograniczenia i uwagi
- Nie redukuje obciążenia (bias): jeśli bazowy model uczący niedopasowuje się (underfits), bagging nie może tego skorygować.
- Predykcje zespołowe są trudniejsze do interpretacji niż pojedynczy model; brak analogii do wizualnej struktury pojedynczego drzewa decyzyjnego.
- Pamięć i przechowywanie skalują się liniowo wraz z B: utrzymywanie setek dużych modeli w pamięci może być niewykonalne.
- Zyski szybko maleją wraz ze wzrostem B; wydajność zazwyczaj stabilizuje się na długo przed B = 500.
- Na stabilnych bazowych modelach uczących (np. regresja liniowa z poprawną specyfikacją) bagging daje znikome ulepszenie.
Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.
Mocne strony
- Bezpośrednio redukuje wariancję estymatora bez zwiększania obciążenia (bias), generując bardziej stabilne predykcje niż jakikolwiek pojedynczy model bazowy.
- Trywialnie równoległy: każda iteracja bootstrapowa jest niezależna, co czyni duże zespoły obliczeniowo wykonalnymi.
- Wbudowana estymacja błędu OOB zapewnia uczciwą estymatę generalizacji bez dodatkowych kosztów danych.
- Meta-algorytm niezależny od modelu: kompatybilny z każdym wystarczająco niestabilnym bazowym modelem uczącym (drzewa, sieci neuronowe, najbliżsi sąsiedzi).
- Odporny na wartości odstające w zbiorze treningowym: każda pojedyncza nietypowa obserwacja jest nieobecna w większości prób bootstrapowych.
Zastosowania
- Konstruowanie stabilnych modeli klasyfikacji i regresji na zaszumionych danych tabelarycznych, gdzie pojedyncze drzewo decyzyjne nadmiernie dopasowałoby się (overfit).
- Generowanie przedziałów predykcji poprzez inspekcję rozrzutu predykcji między B bazowymi modelami uczącymi.
- Estymacja ważności cech poprzez spadek dokładności OOB, gdy każda cecha jest permowana w całym zespole.
- Punkt odniesienia dla zespołów: szybki benchmark do kwantyfikacji, o ile bardziej wyrafinowana metoda (boosting, stacking) poprawia się w stosunku do prostego agregowania.
Jak to działa
Jak to działa
B niezależnych prób bootstrapowych jest pobieranych z oryginalnego zbioru treningowego o rozmiarze n. Każda próba jest generowana przez pobranie n obserwacji z powtórzeniami z oryginalnych danych, więc średnio każda próba zawiera około 63,2% unikalnych instancji treningowych; pozostałe ~36,8% pozostaje poza próbą i tworzy zbiór poza próbą (out-of-bag, OOB) dla danej iteracji.
Wzór
\mathcal{D}_b = \{(\mathbf{x}_i^*, y_i^*)\}_{i=1}^{n}, \quad (\mathbf{x}_i^*, y_i^*) \overset{\text{i.i.d.}}{\sim} \hat{F}_n, \quad b = 1, \dots, BBazowy algorytm uczący — najczęściej drzewo decyzyjne rosnące do pełnej głębokości, ale kwalifikuje się każdy wystarczająco niestabilny model uczący — jest dopasowywany niezależnie do każdej próby bootstrapowej, dając B odrębnych modeli. Kluczowym wymogiem jest niestabilność: jeśli małe perturbacje danych powodują duże zmiany modelu, bagging daje największą redukcję wariancji.
Wzór
\hat{f}_b = \mathcal{A}(\mathcal{D}_b)Dla zadań regresji B wyjść modeli jest uśrednianych. Ten krok uśredniania jest głównym mechanizmem redukcji wariancji: przy założeniu niezależności wariancja średniej z B identycznie rozłożonych modeli wynosi 1/B wariancji pojedynczego modelu, a nawet przy dodatniej korelacji redukcja jest znacząca.
Wzór
\hat{f}_{\text{bag}}(\mathbf{x}) = \frac{1}{B} \sum_{b=1}^{B} \hat{f}_b(\mathbf{x})Dla zadań klasyfikacji każdy bazowy model uczący oddaje jeden głos na etykietę klasy, a klasa z największą liczbą głosów jest zwracana jako finalna predykcja. Remisy są rozstrzygane arbitralnie. Głosowanie większościowe jest asymptotycznie równoważne uśrednianiu estymatorów prawdopodobieństwa klasy wyprodukowanych przez każdy bazowy model uczący.
Wzór
\hat{y}(\mathbf{x}) = \underset{k}{\operatorname{arg\,max}} \sum_{b=1}^{B} \mathbf{1}\!\left[\hat{f}_b(\mathbf{x}) = k\right]Ponieważ każdy bazowy model uczący jest trenowany na około 63,2% danych, pozostałe obserwacje mogą służyć jako uczciwy, odłożony zbiór testowy dla tego modelu. Uśrednianie tych predykcji OOB ze wszystkich modeli, które nie widziały danej obserwacji, daje prawie nieobciążoną estymatę błędu generalizacji bez potrzeby stosowania oddzielnego składnika walidacyjnego lub walidacji krzyżowej.
Wzór
\widehat{\text{Err}}_{\text{OOB}} = \frac{1}{n} \sum_{i=1}^{n} L\!\left(y_i,\; \frac{1}{|\mathcal{B}_i^c|} \sum_{b \in \mathcal{B}_i^c} \hat{f}_b(\mathbf{x}_i)\right)Częste pułapki
- Stosowanie baggingu do bazowego modelu uczącego o niskiej wariancji (takiego jak regresja grzbietowa) i oczekiwanie dużych zysków dokładności.
- Ustawienie zbyt małego B (np. B < 10), tak że agregat jest nadal zaszumiony, a estymaty OOB są niewiarygodne.
- Ignorowanie niezbalansowania klas: bagging zachowuje rozkład klas oryginalnych danych w każdej próbie bootstrapowej, więc silne niezbalansowanie jest replikowane we wszystkich modelach uczących.
- Mylenie baggingu z boostingiem: bagging trenuje modele równolegle na niezależnych próbkach w celu redukcji wariancji, podczas gdy boosting trenuje modele sekwencyjnie w celu redukcji obciążenia (bias) — zajmują się różnymi źródłami błędów.
- Traktowanie błędu OOB jako substytutu właściwej oceny na odłożonym zbiorze, gdy zbiór danych jest bardzo mały, ponieważ estymaty OOB mogą być optymistyczne w tym reżimie.
Najczęściej zadawane pytania
Ile prób bootstrapowych B powinienem użyć?
Breiman (1996) stwierdził, że wydajność stosunkowo szybko się stabilizuje; B = 50 do 100 jest często wystarczające dla drzew decyzyjnych. Zwiększanie B powyżej kilkuset daje malejące zyski. Monitoruj błąd OOB w miarę wzrostu B i zatrzymaj się, gdy się ustabilizuje.
Jaka jest różnica między baggingiem a Random Forest?
Random Forest rozszerza bagging poprzez dodanie losowego próbkowania cech przy każdym podziale każdego drzewa. Ta dodatkowa losowość dalej de-koreluje bazowe modele uczące, redukując wariancję poza to, co osiąga sam bagging. Bagging z w pełni rozwiniętymi drzewami jest zatem szczególnym przypadkiem Random Forest, gdzie wszystkie cechy są brane pod uwagę przy każdym podziale.
Czy bagging można zastosować do modeli uczących innych niż drzewa decyzyjne?
Tak. Każdy model uczący, który jest niestabilny — którego predykcje znacząco się zmieniają przy niewielkich zmianach danych treningowych — może skorzystać na baggingu. Sieci neuronowe, k-najbliżsi sąsiedzi i nieprzycinane drzewa regresyjne kwalifikują się. Stabilne modele uczące, takie jak regresja liniowa z dobrze określonym modelem, czerpią niewielkie korzyści, ponieważ jest niewiele wariancji do zredukowania.
Czy błąd OOB jest wiarygodnym substytutem walidacji krzyżowej?
Dla umiarkowanych do dużych zbiorów danych błąd OOB jest prawie nieobciążoną estymatą błędu generalizacji i jest obliczeniowo darmowy, ponieważ nie wymaga dodatkowych dopasowań modelu. Na bardzo małych zbiorach danych (n poniżej około 50) estymaty OOB mogą być optymistyczne i preferowana jest walidacja krzyżowa.
Pokrewne metody
Źródła
Breiman, L. (1996). Bagging Predictors. Machine Learning, 24(2), 123–140.
Otwórz odnośnik DOISkopiowano.Hastie, T., Tibshirani, R. & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 8.7). Springer.
ISBN: 978-0-387-84857-0Skopiowano.James, G., Witten, D., Hastie, T. & Tibshirani, R. (2013). An Introduction to Statistical Learning (Ch. 8.2). Springer.
ISBN: 978-1-4614-7138-7Skopiowano.