Skip to content
Torna ai risultati

Bagging Online

Introdotto da
Oza, N. C. & Russell, S.
Anno
2001
Tipo
Online ensemble (streaming bagging)
Famiglia
Machine learning

Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese

Dimensione del carattere

A cosa serve?

Online Bagging è un metodo d'insieme in streaming introdotto da Oza e Russell nel 2001 che adatta il framework classico del bootstrap aggregating (Bagging) all'impostazione dell'apprendimento online.

Invece di ricampionare un dataset fisso, ogni istanza in arrivo viene fornita a ciascun apprenditore di base un numero di volte distribuito secondo Poisson(1), approssimando fedelmente il campionamento bootstrap man mano che lo stream evolve. Il risultato è un insieme robusto, aggiornato incrementalmente, in grado di gestire il concept drift e l'arrivo continuo di dati senza memorizzare l'intero dataset.

L’intuizione alla base del metodo

Il Bagging classico estrae campioni bootstrap casuali da un dataset fisso e addestra un albero per campione. Online Bagging lo imita senza mai vedere l'intero dataset contemporaneamente: quando arriva un nuovo esempio, viene passato a ciascun apprenditore di base un numero casuale di volte estratto da una distribuzione di Poisson con media 1. In media, ogni apprenditore vede l'esempio una volta — esattamente ciò che il ricampionamento bootstrap ottiene in modalità batch — ma la casualità de-correlata gli apprenditori. Poiché non è necessario memorizzare dati, l'insieme può crescere indefinitamente con lo stream e adattarsi naturalmente alle distribuzioni mutevoli nel tempo.

Storia

Online Bagging è stato introdotto da Nitesh Oza e Stuart Russell all'AISTATS 2001 come estensione teorica e pratica dell'algoritmo Bagging di Breiman del 1996 all'impostazione online. L'intuizione chiave — sostituire il ricampionamento bootstrap con la ponderazione Poisson(1) per istanza — ha reso l'approssimazione matematicamente rigorosa. È diventato un algoritmo fondamentale nella letteratura sull'apprendimento automatico in streaming ed è l'insieme di base in piattaforme come MOA (Massive Online Analysis), che ha guidato la maggior parte delle valutazioni empiriche dei classificatori di stream dal 2010.

Quando usarlo

Utilizzare Online Bagging quando i dati arrivano come uno stream continuo e la memorizzazione dell'intero dataset è infattibile o proibita (ad es., log di sensori, clickstream, dati tick finanziari, monitoraggio in tempo reale). È appropriato quando si necessita di classificazione o regressione che si aggiorna con ogni nuova osservazione, tollera un lieve concept drift e rimane efficiente in termini di memoria. Non utilizzare Online Bagging come sostituto diretto per Random Forest batch su un dataset fisso, di piccole o medie dimensioni — gli insiemi batch con cross-validation lo supereranno in prestazioni in quel caso. Evitarlo anche quando lo stream di dati presenta un grave drift brusco senza aggiungere un meccanismo esplicito di rilevamento del drift.

Limiti e considerazioni

  • Su dataset statici, metodi batch come Random Forest o XGBoost superano costantemente Online Bagging perché possono utilizzare la cross-validation completa e split ottimali.
  • Online Bagging di base offre solo una limitata resilienza al grave concept drift; è necessario aggiungere esternamente rilevatori di drift dedicati (ad es., ADWIN).
  • La ponderazione di Poisson introduce varianza aggiuntiva per istanza, il che può rallentare la convergenza su stream brevi.
  • L'interpretabilità è bassa: l'insieme di molti alberi cresciuti incrementalmente è più difficile da ispezionare di un singolo albero decisionale.

Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.

Punti di forza

  • Elabora i dati un'istanza alla volta con memoria costante, abilitando stream veramente illimitati.
  • La ponderazione di Poisson approssima provatamente il ricampionamento bootstrap, fornendo una riduzione della varianza dell'insieme comparabile al Bagging batch.
  • Naturalmente parallelizzabile: ogni apprenditore di base si aggiorna indipendentemente, rendendolo adatto ad architetture di streaming distribuite.
  • Nessun iperparametro sensibile come la profondità dell'albero — l'insieme si auto-regola attraverso la diversità.
  • Si estende semplicemente alla classificazione multiclasse e alla regressione senza modifiche strutturali.

Applicazioni

  • Rilevamento frodi in tempo reale su stream continui di transazioni.
  • Manutenzione predittiva da stream di dati di sensori in contesti IoT industriali.
  • Predizione del tasso di click-through nella pubblicità online dove il comportamento dell'utente si evolve continuamente.
  • Rilevamento di intrusioni di rete su stream di pacchetti ad alto throughput.
  • Monitoraggio ambientale: classificazione incrementale di letture di sensori di qualità dell'aria o meteorologici.

Come funziona

Come funziona

1

Per ogni istanza in arrivo, un peso k viene campionato indipendentemente da una distribuzione Poisson(1) per ogni apprenditore di base. Un peso di 0 significa che l'apprenditore salta completamente questa istanza; un peso di 2 significa che apprende dall'istanza due volte. Questa ponderazione stocastica è l'analogo online del ricampionamento bootstrap ed è il nucleo matematico dell'algoritmo.

Formula
k \sim \text{Poisson}(1)
2

Ciascun apprenditore di base — tipicamente un albero decisionale incrementale come un Albero di Hoeffding — riceve l'istanza corrente con il suo peso assegnato e aggiorna immediatamente il suo modello interno. Nessuna istanza viene memorizzata dopo l'elaborazione. Questa proprietà di passaggio singolo mantiene la memoria limitata e consente all'insieme di scalare a stream arbitrariamente lunghi.

3

Quando è richiesta una predizione, tutti gli M apprenditori di base producono il loro output individuale per l'istanza di query. L'insieme li combina tramite voto di maggioranza per la classificazione o tramite media aritmetica per la regressione, fornendo la stessa logica aggregata del Bagging batch ma calcolata su modelli addestrati incrementalmente.

Formula
\hat{y} = \text{mode/mean of } M \text{ base learners}

Errori comuni

  • Valutare Online Bagging con un set di test tenuto da parte creato prima dell'inizio dell'addestramento — utilizzare invece la valutazione prequenziale (test-then-train), che è lo standard nell'apprendimento automatico in streaming.
  • Assumere che il numero predefinito di apprenditori di base (spesso 10) sia sufficiente; sono tipicamente necessari insiemi di almeno 50-100 apprenditori per predizioni stabili.
  • Ignorare il concept drift: distribuire Online Bagging su uno stream con drift senza rilevamento del drift porta a un degrado silenzioso dell'accuratezza.
  • Confrontare l'accuratezza su un benchmark statico con metodi batch e concludere che Online Bagging è inferiore — il confronto corretto è l'accuratezza per istanza vista su un benchmark in streaming.
  • Utilizzare apprenditori di base che non sono veramente incrementali (ad es., alberi batch ri-addestrati), il che vanifica i vantaggi di memoria e velocità del framework online.

Domande frequenti

Perché specificamente Poisson(1)?

Una distribuzione di Poisson con media 1 approssima il numero di volte in cui un'osservazione appare in un campione bootstrap di dimensione n quando n tende all'infinito. L'utilizzo di Poisson(1) per istanza per apprenditore replica esattamente questo comportamento limite, rendendo l'approssimazione online teoricamente valida.

In che modo Online Bagging differisce da Adaptive Random Forest?

Adaptive Random Forest (Gomes et al., 2017) estende Online Bagging aggiungendo il sotto-campionamento casuale delle feature ad ogni split (come Random Forest batch) e integrando rilevatori di drift per albero che resettano gli apprenditori individuali quando viene rilevato il concept drift. Online Bagging è la base più semplice; Adaptive Random Forest è l'attuale ensemble di streaming all'avanguardia costruito su di esso.

Quale apprenditore di base dovrei usare?

La scelta più comune è l'Albero di Hoeffding (chiamato anche VFDT), che è l'albero decisionale incrementale canonico. Utilizza i limiti di Hoeffding per decidere quando sono stati visti abbastanza dati in un nodo per effettuare uno split, mantenendo l'albero aggiornabile senza memorizzare istanze passate.

Quanti apprenditori di base mi servono?

Benchmark empirici nel framework MOA suggeriscono 50-100 apprenditori di base per prestazioni stabili dell'insieme sulla maggior parte dei task di streaming. Meno apprenditori riducono il costo computazionale ma aumentano la varianza di predizione, specialmente all'inizio dello stream.

Come dovrei valutare un classificatore Online Bagging?

Utilizzare la valutazione prequenziale: per ogni istanza in arrivo, prima predire la sua etichetta, poi aggiornare il modello. L'accuratezza viene calcolata come media mobile delle predizioni corrette. Questo evita qualsiasi bias di look-ahead e riflette le vere condizioni di distribuzione.

Metodi correlati

Fonti

  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.

    Apri il riferimento della pubblicazione
    Copiato.
  2. Bifet, A., Holmes, G., Kirkby, R., & Pfahringer, B. (2010). MOA: Massive Online Analysis. Journal of Machine Learning Research, 11, 1601–1604.

    Apri il riferimento della pubblicazione
    Copiato.