Przejdź do treści
Wróć do wyników wyszukiwania

Online Bagging

Autor metody
Oza, N. C. & Russell, S.
Rok
2001
Typ
Online ensemble (streaming bagging)
Rodzina
Machine learning

Ten tekst jest tłumaczeniem maszynowym i nie został jeszcze sprawdzony. Przeczytaj oryginał po angielsku

Rozmiar czcionki

Do czego służy?

Online Bagging to metoda zespołowa strumieniowa wprowadzona przez Oza i Russella w 2001 roku, która adaptuje klasyczne ramy agregacji bootstrap (Bagging) do ustawienia uczenia online.

Zamiast ponownego próbkowania ustalonego zbioru danych, każda napływająca instancja jest podawana każdemu uczącemu bazowemu określoną liczbę razy, rozłożoną zgodnie z rozkładem Poissona(1), wiernie aproksymując próbkowanie bootstrap w miarę ewolucji strumienia. Rezultatem jest solidny, przyrostowo aktualizowany zespół, który może obsługiwać dryf koncepcji i ciągłe napływanie danych bez przechowywania całego zbioru danych.

Intuicja stojąca za metodą

Klasyczny Bagging pobiera losowe próbki bootstrap z ustalonego zbioru danych i trenuje jedno drzewo na próbkę. Online Bagging naśladuje to, nigdy nie widząc całego zbioru danych naraz: gdy pojawia się nowy przykład, jest on przekazywany każdemu uczącemu bazowemu losową liczbę razy pobraną z rozkładu Poissona o średniej 1. Średnio każdy uczący widzi przykład raz — dokładnie to, co osiąga ponowne próbkowanie bootstrap w trybie wsadowym — ale losowość dezkoreluje uczących. Ponieważ nie trzeba przechowywać danych, zespół może rosnąć w nieskończoność wraz ze strumieniem i naturalnie dostosowywać się do zmieniających się rozkładów w czasie.

Historia

Online Bagging został wprowadzony przez Nitesha Oza i Stuarta Russella na AISTATS 2001 jako teoretyczne i praktyczne rozszerzenie algorytmu Bagging Breimana z 1996 roku do ustawienia online. Kluczowa koncepcja — zastąpienie ponownego próbkowania bootstrap ważeniem Poissona(1) na instancję — uczyniła aproksymację matematycznie rygorystyczną. Stał się on fundamentalnym algorytmem w literaturze strumieniowego uczenia maszynowego i jest podstawowym zespołem w platformach takich jak MOA (Massive Online Analysis), która napędza większość ewaluacji empirycznych klasyfikatorów strumieniowych od 2010 roku.

Kiedy stosować

Używaj Online Bagging, gdy dane napływają jako ciągły strumień, a przechowywanie pełnego zbioru danych jest niewykonalne lub zabronione (np. logi z czujników, strumienie kliknięć, dane tickowe z finansów, monitorowanie w czasie rzeczywistym). Jest odpowiedni, gdy potrzebujesz klasyfikacji lub regresji, która aktualizuje się z każdą nową obserwacją, toleruje łagodny dryf koncepcji i pozostaje wydajny pamięciowo. Nie używaj Online Bagging jako zamiennika typu 'plug-and-play' dla wsadowego Random Forest na ustalonym, małym lub średnim zbiorze danych — zespoły wsadowe z walidacją krzyżową będą tam lepsze. Unikaj go również, gdy strumień danych wykazuje silny, nagły dryf bez dodania mechanizmu wykrywania dryfu.

Ograniczenia i uwagi

  • Na statycznych zbiorach danych, metody wsadowe, takie jak Random Forest lub XGBoost, konsekwentnie przewyższają Online Bagging, ponieważ mogą wykorzystywać pełną walidację krzyżową i optymalne podziały.
  • Podstawowy Online Bagging oferuje jedynie ograniczoną odporność na silny dryf koncepcji; dedykowane detektory dryfu (np. ADWIN) muszą być dodane zewnętrznie.
  • Ważenie Poissona wprowadza dodatkową wariancję na instancję, co może spowolnić zbieżność na krótkich strumieniach.
  • Interpretowalność jest niska: zespół wielu przyrostowo rosnących drzew jest trudniejszy do inspekcji niż pojedyncze drzewo decyzyjne.

Warunki podane w źródle nie zastępują niezależnego przeglądu naukowego ani walidacji przez silnik analityczny.

Mocne strony

  • Przetwarza dane po jednej instancji na raz ze stałą pamięcią, umożliwiając prawdziwie nieograniczone strumienie.
  • Ważenie Poissona udowodniwie aproksymuje ponowne próbkowanie bootstrap, zapewniając redukcję wariancji zespołu porównywalną z wsadowym Baggingiem.
  • Naturalnie równoległy: każdy uczący bazowy aktualizuje się niezależnie, co czyni go odpowiednim dla rozproszonych architektur strumieniowych.
  • Brak hiperparametru tak wrażliwego jak głębokość drzewa — zespół samoreguluje się poprzez różnorodność.
  • Prosto rozszerza się na klasyfikację wieloklasową i regresję bez zmian strukturalnych.

Zastosowania

  • Wykrywanie oszustw w czasie rzeczywistym na ciągłych strumieniach transakcji.
  • Predykcja konserwacji z danych strumieniowych z czujników w środowiskach przemysłowych IoT.
  • Predykcja współczynnika klikalności w reklamie online, gdzie zachowanie użytkownika stale ewoluuje.
  • Wykrywanie intruzji w sieci na strumieniach pakietów o dużej przepustowości.
  • Monitorowanie środowiska: przyrostowa klasyfikacja odczytów z czujników jakości powietrza lub pogody.

Jak to działa

Jak to działa

1

Dla każdej napływającej instancji, waga k jest próbkowana niezależnie z rozkładu Poissona(1) dla każdego uczącego bazowego. Waga 0 oznacza, że uczący całkowicie pomija tę instancję; waga 2 oznacza, że uczy się z tej instancji dwukrotnie. Ta stochastyczna ważona jest analogiem online ponownego próbkowania bootstrap i stanowi matematyczne jądro algorytmu.

Wzór
k \sim \text{Poisson}(1)
2

Każdy uczący bazowy — zazwyczaj przyrostowe drzewo decyzyjne, takie jak drzewo Hoeffdinga — otrzymuje bieżącą instancję z przypisaną wagą i natychmiast aktualizuje swój wewnętrzny model. Żadna instancja nie jest przechowywana po przetworzeniu. Ta właściwość jednoprzebiegowa utrzymuje ograniczoną pamięć i pozwala zespołowi skalować się do dowolnie długich strumieni.

3

Gdy wymagana jest predykcja, wszyscy M uczący bazowi generują swoje indywidualne wyniki dla instancji zapytania. Zespół łączy je przez głosowanie większościowe w przypadku klasyfikacji lub przez średnią arytmetyczną w przypadku regresji, dając tę samą logikę agregacji co wsadowy Bagging, ale obliczoną na przyrostowo trenowanych modelach.

Wzór
\hat{y} = \text{mode/mean of } M \text{ base learners}

Częste pułapki

  • Oceniając Online Bagging za pomocą zbioru testowego odłożonego przed rozpoczęciem treningu — zamiast tego użyj ewaluacji prekwencyjnej (testuj-następnie-trenuj), która jest standardem w strumieniowym uczeniu maszynowym.
  • Zakładając, że domyślna liczba uczących bazowych (często 10) jest wystarczająca; zespoły co najmniej 50–100 uczących są zazwyczaj potrzebne do stabilnych predykcji.
  • Ignorowanie dryfu koncepcji: wdrażanie Online Bagging na strumieniu z dryfem bez wykrywania dryfu prowadzi do cichej degradacji dokładności.
  • Porównywanie dokładności na statycznym benchmarku z metodami wsadowymi i stwierdzenie, że Online Bagging jest gorszy — właściwe porównanie to dokładność na instancję widzianą na strumieniowym benchmarku.
  • Używanie uczących bazowych, które nie są prawdziwie przyrostowe (np. przetrenowane drzewa wsadowe), co niweczy zalety pamięciowe i szybkościowe ram online.

Najczęściej zadawane pytania

Dlaczego konkretnie Poisson(1)?

Rozkład Poissona o średniej 1 aproksymuje liczbę razy, jaką obserwacja pojawia się w próbce bootstrap o rozmiarze n, gdy n dąży do nieskończoności. Użycie Poissona(1) na instancję na uczącego replikuje to zachowanie graniczne dokładnie, czyniąc aproksymację online teoretycznie uzasadnioną.

Czym Online Bagging różni się od Adaptive Random Forest?

Adaptive Random Forest (Gomes et al., 2017) rozszerza Online Bagging poprzez dodanie losowego podpróbkowania cech przy każdym podziale (jak w wsadowym Random Forest) i integrację detektorów dryfu na drzewo, które resetują poszczególne uczące po wykryciu dryfu koncepcji. Online Bagging jest prostszą podstawą; Adaptive Random Forest jest obecnym stanem techniki w zespołach strumieniowych zbudowanych na jego bazie.

Jakiego uczącego bazowego powinienem użyć?

Najczęstszym wyborem jest drzewo Hoeffdinga (zwane również VFDT), które jest kanonicznym przyrostowym drzewem decyzyjnym. Wykorzystuje ono granice Hoeffdinga do określenia, kiedy wystarczająca ilość danych została już widziana w węźle, aby dokonać podziału, utrzymując drzewo aktualizowalne bez przechowywania przeszłych instancji.

Ilu uczących bazowych potrzebuję?

Empiryczne benchmarki w ramach MOA sugerują 50–100 uczących bazowych dla stabilnej wydajności zespołu w większości zadań strumieniowych. Mniejsza liczba uczących zmniejsza koszt obliczeniowy, ale zwiększa wariancję predykcji, szczególnie na wczesnym etapie strumienia.

Jak powinienem ocenić klasyfikator Online Bagging?

Użyj ewaluacji prekwencyjnej: dla każdej napływającej instancji najpierw przewidź jej etykietę, a następnie zaktualizuj model. Dokładność jest obliczana jako bieżąca średnia poprawnych predykcji. Pozwala to uniknąć jakiegokolwiek błędu patrzenia w przyszłość i odzwierciedla rzeczywiste warunki wdrożenia.

Pokrewne metody

Źródła

  1. Oza, N. C., & Russell, S. (2001). Online bagging and boosting. In Proceedings of the Eighth International Workshop on Artificial Intelligence and Statistics (AISTATS 2001), pp. 105–112.

    Otwórz odnośnik do publikacji
    Skopiowano.
  2. Bifet, A., Holmes, G., Kirkby, R., & Pfahringer, B. (2010). MOA: Massive Online Analysis. Journal of Machine Learning Research, 11, 1601–1604.

    Otwórz odnośnik do publikacji
    Skopiowano.