1 Le bagging
Le bagging, ou “bootstrap aggregating”, est une méthode ensembliste qui vise à améliorer la stabilité et la précision des algorithmes d’apprentissage automatique en agrégeant plusieurs modèles (Breiman (1996)). Chaque modèle est entraîné sur un échantillon distinct généré par une technique de rééchantillonnage (bootstrap). Ces modèles sont ensuite combinés pour produire une prédiction agrégée, souvent plus robuste et généralisable que celle obtenue par un modèle unique.
Le bagging est peu utilisé en pratique car il a été supplanté par les forêts aléatoires (présentées dans le chapitre suivant) dont il constitue l’un des fondements méthodologiques.
1.1 Principe du bagging
Le bagging comporte trois étapes principales:
L’échantillonnage bootstrap : L’échantillonnage bootstrap consiste à créer des échantillons distincts en tirant aléatoirement avec remise des observations du jeu de données initial. Chaque échantillon bootstrap contient le même nombre d’observations que le jeu de données initial, mais certaines observations sont répétées (car sélectionnées plusieurs fois), tandis que d’autres sont omises.
L’entraînement de plusieurs modèles : Un modèle est entraîné sur chaque échantillon bootstrap. Les modèles peuvent être des arbres de décision, des régressions ou tout autre algorithme d’apprentissage. Le bagging est particulièrement efficace avec des modèles instables, tels que les arbres de décision non élagués.
L’agrégation des prédictions : Les prédictions de tous les modèles sont ensuite agrégées, généralement en prenant la moyenne des prédictions dans le cas de la régression, et la classe majoritaire (ou la moyenne des probabilités prédites pour chaque classe) dans le cas de la classification.
1.2 Pourquoi (et dans quelles situations) le bagging fonctionne
L’objectif du bagging est de construire un prédicteur plus précis en agrégeant les prédictions de plusieurs modèles entraînés sur des échantillons (légèrement) différents les uns des autres. Breiman (1996) a démontré que cette méthode est particulièrement efficace lorsqu’elle est appliquée à des modèles très instables, dont les performances sont particulièrement sensibles aux variations du jeu de données d’entraînement, et peu biaisés. Cette section vise à expliquer pourquoi (et sous quelles conditions) l’agrégation par bagging permet de construire un prédicteur agrégé plus performant. Dans la suite, nous notons \(φ(x, L)\) un prédicteur (d’une valeur numérique dans le cas de la régression ou d’une classe dans le cas de la classification), entraîné sur un ensemble d’apprentissage \(L\), et prenant en entrée un vecteur de caractéristiques \(x\).
1.2.1 La régression: réduction de l’erreur quadratique moyenne par agrégation
Dans le contexte de la régression, l’objectif est de prédire une valeur numérique \(Y\) à partir d’un vecteur de caractéristiques \(x\). Un modèle de régression \(\phi(x, L)\) est construit à partir d’un ensemble d’apprentissage \(L\), et produit une estimation de \(Y\) pour chaque observation \(x\).
1.2.1.1 Définition du prédicteur agrégé
Dans le cas de la régression, le prédicteur agrégé est défini comme suit :
\[ \phi_{A}(x) = E_L[\phi(x, L)] \]
où \(\phi_A(x)\) représente la prédiction agrégée, \(E_L[.]\) correspond à l’espérance prise sur tous les échantillons d’apprentissage possibles \(L\), chacun étant tiré selon la même distribution que le jeu de données initial, et \(\phi(x, L)\) correspond à la prédiction du modèle construit sur l’échantillon d’apprentissage \(L\).
1.2.1.2 La décomposition biais-variance
Pour mieux comprendre comment l’agrégation améliore la performance globale d’un modèle individuel \(\phi(x, L)\), revenons à la décomposition biais-variance de l’erreur quadratique moyenne en \(x\), qui est une mesure de performance très courante pour les problèmes de régression:
\[ E_L[\left(Y - \phi(x, L)\right)^2] = \underbrace{\left(E_L\left[\phi(x, L) - Y\right]\right)^2}_{\text{Biais}^2} + \underbrace{E_L[\left(\phi(x, L) - E_L[\phi(x, L)]\right)^2]}_{\text{Variance}} \tag{1}\]
L’erreur quadratique moyenne en \(x\) se décompose en deux termes:
Le biais est la différence entre la valeur observée \(Y\) que l’on souhaite prédire et la prédiction moyenne \(E_L[\phi(x, L)]\). Si le modèle est peu prédictif, le biais sera élevé.
La variance est la variabilité des prédictions \(\phi(x, L)\) autour de leur moyenne \(E_L[\phi(x, L)]\). Un modèle avec une variance élevée est très sensible aux fluctuations au sein des données d’entraînement: ses prédictions varient beaucoup lorsque les données d’entraînement se modifient.
L’équation 1 illustre l’arbitrage biais-variance qui est omniprésent en machine learning: plus la complexité d’un modèle s’accroît (exemple: la profondeur d’un arbre), plus son biais sera plus faible (car ses prédictions seront de plus en plus proches des données d’entraînement), et plus sa variance sera élevée (car ses prédictions, étant très proches des données d’entraînement, auront tendance à varier fortement d’un jeu d’entraînement à l’autre).
1.2.1.3 L’inégalité de Breiman (1996)
Breiman (1996) compare l’erreur quadratique moyenne d’un modèle individuel avec celle du modèle agrégé et démontre l’inégalité suivante :
\[ (Y - \phi_{A}(x))^2 \leq E_L[(Y - \phi(x, L))^2] \tag{2}\]
Le terme \((Y - \phi_A(x))^2\) représente l’erreur quadratique en \(x\) du prédicteur agrégé \(\phi_A(x)\);
Le terme \(E_L[(Y - \phi(x, L))^2]\) est l’erreur quadratique moyenne en \(x\) d’un prédicteur individuel \(\phi(x, L)\) entraîné sur un échantillon aléatoire \(L\). Cette erreur varie en fonction des données d’entraînement.
Cette inégalité montre que l’erreur quadratique du prédicteur agrégé est toujours inférieure ou égale à l’erreur quadratique moyenne d’un prédicteur individuel. Étant donné que le biais du prédicteur agrégé est égal au biais du prédicteur individuel, l’inégalité précédente implique que la variance du modèle agrégé \(\phi_A(x)\) est toujours inférieure ou égale à la variance moyenne d’un modèle individuel:
\[ \text{Var}(\phi_A(x)) = \text{Var}(E_L[\phi(x, L)]) \leq E_L[\text{Var}(\phi(x, L))] \]
Autrement dit, le processus d’agrégation réduit l’erreur de prédiction globale en réduisant la variance des prédictions, tout en conservant un biais constant.
Ce résultat ouvre la voie à des considérations pratiques immédiates. Lorsque le modèle individuel est instable et présente une variance élevée, l’inégalité \(Var(\phi_A(x)) \leq E_L[Var(\phi(x,L))]\) est forte, ce qui signifie que l’agrégation peut améliorer significativement la performance globale du modèle. En revanche, si \(\phi(x,L)\) varie peu d’un ensemble d’entraînement à un autre (modèle stable avec variance faible), alors \(Var(\phi_A(x))\) est proche de \(E_L[Var(\phi(x,L))]\), et la réduction de variance apportée par l’agrégation est faible. Ainsi, le bagging est particulièrement efficace pour les modèles instables, tels que les arbres de décision, mais moins efficace pour les modèles stables tels que les méthodes des k plus proches voisins.
1.2.2 La classification: vers un classificateur presque optimal par agrégation
Dans le cas de la classification, le mécanisme de réduction de la variance par le bagging permet, sous une certaine condition, d’atteindre un classificateur presque optimal (nearly optimal classifier). Ce concept a été introduit par Breiman (1996) pour décrire un modèle qui tend à classer une observation dans la classe la plus probable, avec une performance approchant celle du classificateur Bayésien optimal (la meilleure performance théorique qu’un modèle de classification puisse atteindre).
Pour comprendre ce résultat, introduisons \(Q(j|x) = E_L(1_{φ(x, L) = j}) = P(φ(x, L) = j)\), la probabilité qu’un modèle \(φ(x, L)\) prédise la classe \(j\) pour l’observation \(x\), et \(P(j|x)\), la vraie probabilité qu’une observation de caractéristiques \(x\) appartienne à la classe \(j\).
1.2.2.1 Définition : classificateur order-correct
Un classificateur \(φ(x, L)\) est dit order-correct pour une observation \(x\) si, en espérance, il identifie correctement la classe la plus probable, même s’il ne prédit pas toujours avec exactitude les probabilités associées à chaque classe \(Q(j∣x)\). Formellement, un prédicteur est dit “order-correct” pour un vecteur de caractéristiques \(x\) si \(\underset{j}{argmax} Q(j|x) = \underset{j}{argmax} P(j|x)\) où \(P(j|x)\) est la vraie probabilité que l’observation de caractéristiques \(x\) appartienne à la classe \(j\), et \(Q(j|x)\) est la probabilité que l’observation de caractéristiques \(x\) appartienne à la classe \(j\) prédite par le modèle \(φ(x, L)\). En termes moins techniques, la classe prédite le plus souvent par le modèle pour une observation \(x\) correspond à la classe la plus probable pour cette observation dans la vraie distribution.
En généralisant sur toutes les valeurs de \(x\), un classificateur est order-correct si, pour tout \(x\), la classe qu’il prédit le plus souvent correspond à celle qui a la probabilité maximale \(P(j|x)\) dans la vraie distribution.
1.2.2.2 Prédicteur agrégé en classification: le vote majoritaire
Dans le cas de la classification, le prédicteur agrégé est défini par le vote majoritaire. Cela signifie que si \(K\) classificateurs sont entraînés sur \(K\) échantillons distincts, la classe prédite pour \(x\) est celle qui reçoit le plus de votes de la part des modèles individuels. Formellement, le classificateur agrégé \(φA(x)\) est défini par :
\[ φA(x) = \text{argmax}_j \sum_{L} I(\phi(x, L) = j) = argmax_j Q(j|x) \]
1.2.2.3 Performance globale: convergence vers un classificateur presque optimal
Breiman (1996) montre que si chaque prédicteur individuel \(φ(x, L)\) est order-correct pour une observation \(x\), alors le prédicteur agrégé \(φA(x)\), obtenu par vote majoritaire, atteint la performance optimale pour cette observation, c’est-à-dire que lorsque le nombre de prédicteurs individuels augmente le prédicteur agrégé converge vers la classe ayant la probabilité maximale \(P(j∣x)\) pour l’observation \(x\). Le vote majoritaire permet ainsi de réduire les erreurs aléatoires des classificateurs individuels. En généralisant sur toutes les valeurs de \(x\), si chaque prédicteur individuel \(φ(x, L)\) est order-correct pour tout \(x\), alors le classificateur agrégé \(ϕA\) sera optimal pour tout \(x\). Ce résultat d’optimalité en tout point dépend d’une hypothèse cruciale: les classificateurs individuels doivent être order-corrects en tout point. Dans les régions de l’espace où ils ne sont pas order-corrects (c’est-à-dire que la classe qu’ils prédisent le plus fréquemment n’est pas la classe la plus probable dans la vraie distribution), l’agrégation par vote majoritaire n’améliore pas les performances du prédicteur; celles-ci peuvent même se détériorer par rapport aux modèles individuels si l’agrégation conduit à amplifier des erreurs systématiques (biais).
Or, si l’on peut raisonnablement penser qu’un classificateur individuel présentant un biais faible (peu d’erreurs systématiques) sera order-correct pour la plupart des points \(x\), il n’est pas certain qu’il le soit en tout point. En effet, chaque classificateur individuel est entraîné sur un échantillon fini de données, ce qui introduit du bruit dans son estimation de la vraie distribution conditionnelle \(P(j|x)\). Il peut donc, pour certains \(x\), prédire le plus souvent une classe différente de celle qui maximise la vraie probabilité \(P(j|x)\). Par ailleurs, la variabilité due à l’échantillonnage peut induire une couverture incomplète de l’ensemble des \(x\) possibles et aboutir à des erreurs systématiques sur certains points \(x\). C’est pour ces raisons que Breiman conclut que le prédicteur agrégé \(φA(x)\) converge vers un classificateur presque optimal, au sens d’optimal presque partout.
1.3 Quand utiliser le bagging en pratique
Le bagging est particulièrement utile lorsque les modèles individuels présentent une variance élevée et sont instables. Dans de tels cas, l’agrégation des prédictions peut réduire significativement la variance globale, améliorant ainsi la performance du modèle agrégé. Les situations où le bagging est recommandé incluent typiquement:
Les modèles instables : Les modèles tels que les arbres de décision non élagués, qui sont sensibles aux variations des données d’entraînement, bénéficient grandement du bagging. L’agrégation atténue les fluctuations des prédictions dues aux différents échantillons.
Les modèles avec biais faibles: En classification, si les modèles individuels sont order-corrects pour la majorité des observations, le bagging peut améliorer la précision en renforçant les prédictions correctes et en réduisant les erreurs aléatoires.
Inversement, le bagging peut être moins efficace ou même néfaste dans certaines situations :
Les modèles stables avec variance faible : Si les modèles individuels sont déjà stables et présentent une faible variance (par exemple, la régression linéaire), le bagging n’apporte que peu d’amélioration, car la réduction de variance supplémentaire est minimale.
La présence de biais élevé : Si les modèles individuels sont biaisés, entraînant des erreurs systématiques, le bagging peut amplifier ces erreurs plutôt que de les corriger. Dans de tels cas, il est préférable de s’attaquer d’abord au biais des modèles avant de considérer l’agrégation.
Les échantillons de petite taille : Avec des ensembles de données limités, les échantillons bootstrap peuvent ne pas être suffisamment diversifiés ou représentatifs, ce qui réduit l’efficacité du bagging et peut augmenter le biais des modèles.
Ce qui qu’il faut retenir: le bagging peut améliorer substantiellement la performance des modèles d’apprentissage automatique lorsqu’il est appliqué dans des conditions appropriées. Il est essentiel d’évaluer la variance et le biais des modèles individuels, ainsi que la taille et la représentativité du jeu de données, pour déterminer si le bagging est une stratégie adaptée. Lorsqu’il est utilisé judicieusement, le bagging peut conduire à des modèles plus robustes et précis, exploitant efficacement la puissance de l’agrégation pour améliorer la performance des modèles individuels.