Skip to content
Retour aux résultats

Online Bagging

Introduite par
Oza, N. C. & Russell, S.
Année
2001
Type
Online ensemble (streaming bagging)
Famille
Machine learning

Ce texte est une traduction automatique et n’a pas encore été relu. Lire l’original en anglais

Taille de police

À quoi sert-elle ?

Online Bagging est une méthode d'ensemble en flux introduite par Oza et Russell en 2001 qui adapte le cadre classique de bootstrap aggregating (Bagging) au contexte de l'apprentissage en ligne.

Au lieu de rééchantillonner un jeu de données fixe, chaque instance entrante est fournie à chaque apprenant de base un nombre de fois distribué selon une loi de Poisson(1), ce qui approxime fidèlement l'échantillonnage bootstrap à mesure que le flux évolue. Le résultat est un ensemble robuste, mis à jour de manière incrémentielle, capable de gérer la dérive conceptuelle et l'arrivée continue de données sans stocker l'intégralité du jeu de données.

L’intuition derrière la méthode

Le Bagging classique tire des échantillons bootstrap aléatoires d'un jeu de données fixe et entraîne un arbre par échantillon. Online Bagging imite cela sans jamais voir l'ensemble du jeu de données simultanément : lorsqu'un nouvel exemple arrive, il est présenté à chaque apprenant de base un nombre aléatoire de fois tiré d'une distribution de Poisson de moyenne 1. En moyenne, chaque apprenant voit l'exemple une fois – exactement ce que réalise le rééchantillonnage bootstrap en mode batch – mais le caractère aléatoire décorrèle les apprenants. Comme aucune donnée n'a besoin d'être stockée, l'ensemble peut croître indéfiniment avec le flux et s'adapter naturellement aux distributions changeantes au fil du temps.

Histoire

Online Bagging a été introduit par Nitesh Oza et Stuart Russell à AISTATS 2001 comme une extension théorique et pratique de l'algorithme Bagging de Breiman (1996) au contexte en ligne. L'idée clé – remplacer le rééchantillonnage bootstrap par une pondération Poisson(1) par instance – a rendu l'approximation mathématiquement rigoureuse. Il est devenu un algorithme fondamental dans la littérature sur l'apprentissage automatique en flux et constitue l'ensemble de base dans des plateformes telles que MOA (Massive Online Analysis), qui a piloté la plupart des évaluations empiriques des classificateurs de flux depuis 2010.

Quand l’utiliser

Utilisez Online Bagging lorsque les données arrivent sous forme de flux continu et que le stockage de l'ensemble du jeu de données est infaisable ou interdit (par exemple, journaux de capteurs, flux de clics, données de cotation financière, surveillance en temps réel). Il est approprié lorsque vous avez besoin d'une classification ou d'une régression qui se met à jour à chaque nouvelle observation, tolère une légère dérive conceptuelle et reste économe en mémoire. N'utilisez pas Online Bagging comme substitut direct à Random Forest en batch sur un jeu de données fixe, petit à moyen – les ensembles en batch avec validation croisée y seront supérieurs. Évitez-le également lorsque le flux de données présente une dérive abrupte sévère sans ajouter de mécanisme de détection de dérive explicite.

Limites et points d’attention

  • Sur les jeux de données statiques, les méthodes en batch telles que Random Forest ou XGBoost surpassent systématiquement Online Bagging car elles peuvent utiliser la validation croisée complète et des divisions optimales.
  • Le Online Bagging de base n'offre qu'une résilience limitée à une dérive conceptuelle sévère ; des détecteurs de dérive dédiés (par exemple, ADWIN) doivent être ajoutés extérieurement.
  • La pondération de Poisson introduit une variance supplémentaire par instance, ce qui peut ralentir la convergence sur des flux courts.
  • L'interprétabilité est faible : l'ensemble de nombreux arbres cultivés de manière incrémentielle est plus difficile à inspecter qu'un seul arbre de décision.

Les conditions de la source ne remplacent ni une revue scientifique indépendante ni la validation par un moteur d’analyse.

Points forts

  • Traite les données une instance à la fois avec une mémoire constante, permettant des flux véritablement illimités.
  • La pondération de Poisson approxime de manière prouvée le rééchantillonnage bootstrap, offrant une réduction de la variance de l'ensemble comparable au Bagging en batch.
  • Naturellement parallélisable : chaque apprenant de base se met à jour indépendamment, le rendant adapté aux architectures de flux distribuées.
  • Aucun hyperparamètre aussi sensible que la profondeur de l'arbre – l'ensemble s'autorégule par la diversité.
  • S'étend directement à la classification multi-classe et à la régression sans changements structurels.

Applications

  • Détection de fraude en temps réel sur des flux continus de transactions.
  • Maintenance prédictive à partir de flux de données de capteurs dans des environnements IoT industriels.
  • Prédiction du taux de clics dans la publicité en ligne où le comportement de l'utilisateur évolue continuellement.
  • Détection d'intrusion réseau sur des flux de paquets à haut débit.
  • Surveillance environnementale : classification incrémentale de lectures de capteurs de qualité de l'air ou météorologiques.

Comment ça marche

Comment ça marche

1

Pour chaque instance arrivant, un poids k est échantillonné indépendamment d'une distribution de Poisson(1) pour chaque apprenant de base. Un poids de 0 signifie que l'apprenant ignore complètement cette instance ; un poids de 2 signifie qu'il apprend de l'instance deux fois. Cette pondération stochastique est l'analogue en ligne du rééchantillonnage bootstrap et constitue le cœur mathématique de l'algorithme.

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

Chaque apprenant de base – typiquement un arbre de décision incrémental tel qu'un Arbre de Hoeffding – reçoit l'instance courante avec son poids assigné et met à jour son modèle interne immédiatement. Aucune instance n'est stockée après traitement. Cette propriété de passage unique maintient une mémoire bornée et permet à l'ensemble de s'adapter à des flux arbitrairement longs.

3

Lorsqu'une prédiction est requise, tous les M apprenants de base produisent leur sortie individuelle pour l'instance de requête. L'ensemble combine ces sorties par vote majoritaire pour la classification ou par moyenne arithmétique pour la régression, donnant la même logique agrégée que le Bagging en batch mais calculée sur des modèles entraînés de manière incrémentielle.

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

Pièges courants

  • Évaluer Online Bagging avec un ensemble de test mis de côté créé avant le début de l'entraînement – utilisez plutôt l'évaluation préquentielle (tester puis entraîner), qui est la norme en apprentissage automatique en flux.
  • Supposer que le nombre par défaut d'apprenants de base (souvent 10) est suffisant ; des ensembles d'au moins 50 à 100 apprenants sont généralement nécessaires pour des prédictions stables.
  • Ignorer la dérive conceptuelle : déployer Online Bagging sur un flux dérivant sans détection de dérive entraîne une dégradation silencieuse de la précision.
  • Comparer la précision sur un benchmark statique avec des méthodes en batch et conclure qu'Online Bagging est inférieur – la comparaison correcte est la précision par instance vue sur un benchmark en flux.
  • Utiliser des apprenants de base qui ne sont pas véritablement incrémentaux (par exemple, des arbres en batch réentraînés), ce qui annule les avantages de mémoire et de vitesse du cadre en ligne.

Questions fréquentes

Pourquoi spécifiquement Poisson(1)?

Une distribution de Poisson de moyenne 1 approxime le nombre de fois qu'une observation apparaît dans un échantillon bootstrap de taille n lorsque n tend vers l'infini. L'utilisation de Poisson(1) par instance et par apprenant reproduit exactement ce comportement limite, rendant l'approximation en ligne théoriquement solide.

Comment Online Bagging diffère-t-il d'Adaptive Random Forest?

Adaptive Random Forest (Gomes et al., 2017) étend Online Bagging en ajoutant un sous-échantillonnage aléatoire de caractéristiques à chaque division (comme Random Forest en batch) et en intégrant des détecteurs de dérive par arbre qui réinitialisent les apprenants individuels lorsque la dérive conceptuelle est détectée. Online Bagging est la base plus simple ; Adaptive Random Forest est l'ensemble de flux de pointe actuel construit sur celui-ci.

Quel apprenant de base devrais-je utiliser?

Le choix le plus courant est l'Arbre de Hoeffding (également appelé VFDT), qui est l'arbre de décision incrémental canonique. Il utilise les bornes de Hoeffding pour décider quand suffisamment de données ont été vues à un nœud pour le diviser, gardant l'arbre actualisable sans stocker les instances passées.

Combien d'apprenants de base ai-je besoin?

Les benchmarks empiriques dans le cadre MOA suggèrent 50 à 100 apprenants de base pour des performances d'ensemble stables sur la plupart des tâches de flux. Moins d'apprenants réduisent le coût de calcul mais augmentent la variance de prédiction, surtout tôt dans le flux.

Comment devrais-je évaluer un classificateur Online Bagging?

Utilisez l'évaluation préquentielle : pour chaque instance entrante, prédisez d'abord son étiquette, puis mettez à jour le modèle. La précision est calculée comme la moyenne courante des prédictions correctes. Cela évite tout biais de prévision et reflète les conditions de déploiement réelles.

Méthodes associées

Sources

  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.

    Ouvrir la référence de la publication
    Copié.
  2. Bifet, A., Holmes, G., Kirkby, R., & Pfahringer, B. (2010). MOA: Massive Online Analysis. Journal of Machine Learning Research, 11, 1601–1604.

    Ouvrir la référence de la publication
    Copié.