Maximum Risk Minimization with Random Forests

Cet article propose des variantes de forêts aléatoires basées sur le principe de minimisation du risque maximal (MaxRM) pour améliorer la généralisation hors distribution, en fournissant des algorithmes efficaces, des preuves de consistance statistique et des garanties théoriques pour divers risques, y compris le regret.

L'essentiel

Voici une explication simple de ce papier de recherche, imagée comme si nous préparions un grand banquet pour des invités très différents.

Le Problème : Le Chef Cuisinier et ses Invités

Imaginez que vous êtes un chef cuisinier (c'est votre modèle d'intelligence artificielle) et que vous devez préparer un plat unique qui plaira à tout le monde.

Dans le monde classique de l'apprentissage automatique, on vous donne des données provenant d'une seule région : disons, la cuisine italienne. Vous apprenez à faire une excellente pizza. Mais le jour du service, vous recevez des clients venant de partout : un client qui aime le très épicé (Inde), un autre qui préfère le très sucré (Brésil), et un troisième qui veut du très salé (Japon).

Si vous servez votre meilleure pizza italienne à tout le monde :

• Le client brésilien sera content.
• Le client japonais sera déçu.
• Le client indien sera furieux.

Le problème, c'est que votre modèle a été entraîné pour être "moyennement bon" pour tout le monde, mais il échoue lamentablement pour le pire des cas (le client le plus difficile). C'est ce qu'on appelle le changement de distribution : les données d'entraînement ne ressemblent pas aux données de test.

La Solution Proposée : Le Principe "MaxRM"

Les auteurs de ce papier (Freni, Fries, et al.) proposent une nouvelle philosophie pour votre chef cuisinier. Au lieu de chercher à faire le plat le plus moyen pour tout le monde, ils disent :

"Préparez le plat qui sera le moins mauvais pour votre client le plus difficile."

C'est ce qu'ils appellent la Minimisation du Risque Maximum (MaxRM).
Au lieu de minimiser l'erreur moyenne, on minimise l'erreur du pire scénario. On s'assure que même le client le plus exigeant ne sera pas mécontent.

L'Outil Magique : Les Forêts Aléatoires (Random Forests)

Pour réaliser cette tâche, les auteurs utilisent une technique appelée Forêts Aléatoires.
Imaginez une forêt où chaque arbre est un petit expert cuisinier.

• Dans une forêt classique, on prend la moyenne de tous les avis des arbres pour décider du plat final.
• Dans leur nouvelle méthode (MaxRM-RF), on modifie la façon dont ces arbres "pensent".

Au lieu de simplement regarder les données globales, les arbres apprennent à se demander : "Si je fais cette décision, quel sera le pire client qui va arriver ?" Ils ajustent leurs prévisions pour protéger le groupe le plus vulnérable.

Les Trois Stratégies de l'Auteur

Les auteurs ont testé trois façons d'adapter cette forêt pour qu'elle soit plus robuste :

1. La méthode "Post-hoc" (Après coup) :
   Imaginez que vous construisez d'abord votre forêt normalement. Une fois les arbres construits, vous allez voir chaque branche (chaque "feuille" de l'arbre) et vous dites : "Attends, cette branche a fait une erreur terrible pour le client indien. Réajuste un peu ta valeur pour qu'elle soit meilleure pour lui, sans trop gâcher pour les autres."

   • Avantage : C'est rapide et efficace. C'est la méthode préférée des auteurs.

2. La méthode "Locale" :
   Pendant que l'arbre grandit, à chaque fois qu'il se divise en deux branches, on demande : "Laquelle de ces deux nouvelles branches protège le mieux le client difficile ?" On ajuste les valeurs au fur et à mesure.

3. La méthode "Globale" :
   C'est la plus complexe. À chaque division, on recalcule les valeurs de tous les arbres de la forêt pour s'assurer que l'ensemble est parfait pour le pire cas. C'est très précis, mais très lent (comme essayer de réécrire tout un livre à chaque fois qu'on change un mot).

Pourquoi c'est mieux que les anciennes méthodes ?

Il existait déjà des méthodes pour gérer ces différences (comme le "magging" ou les réseaux de neurones robustes), mais elles avaient des défauts :

• Le "Magging" : C'est comme demander à chaque expert de cuisiner pour sa propre région, puis de mélanger les plats. Ça marche bien si les clients ont tous les mêmes goûts de base, mais si l'un d'eux mange des piments très forts et l'autre du sucre, le mélange ne fonctionne pas.
• Les Réseaux de Neurones : Ils sont très puissants mais très capricieux. Ils nécessitent beaucoup de réglages (comme un moteur de voiture de course) et peuvent échouer si on ne les configure pas parfaitement.

La force de la méthode proposée :
Elle fonctionne même si les clients ont des goûts radicalement différents (par exemple, si la répartition des ingrédients change d'un client à l'autre). Elle est aussi plus stable et plus facile à utiliser que les réseaux de neurones complexes.

Le Résultat : Une Robustesse Réelle

Les auteurs ont testé leur méthode sur :

1. Des données simulées : Ils ont créé des scénarios où les clients étaient très différents. Leur méthode a toujours mieux protégé le client difficile que les autres.
2. Des données réelles (Immobilier en Californie) : Ils ont essayé de prédire le prix des maisons dans différents comtés. Certains comtés sont très chers et d'autres moins. La méthode a mieux prédit les prix dans les comtés les plus "difficiles" (ceux où les autres méthodes échouaient), garantissant qu'aucune région ne soit laissée pour compte.

En Résumé

Ce papier nous dit : "Ne cherchez pas à être parfait pour la moyenne. Cherchez à être le plus juste possible pour le cas le plus difficile."

En adaptant les "Forêts Aléatoires" pour qu'elles se soucient du pire scénario, les auteurs créent des modèles d'intelligence artificielle plus justes, plus robustes et plus fiables, capables de fonctionner même lorsque le monde change soudainement. C'est comme passer d'un parapluie fragile à un véritable abri anti-tempête.

Résumé technique

Voici un résumé technique détaillé de l'article "Maximum Risk Minimization with Random Forests" (Minimisation du risque maximum avec les forêts aléatoires), rédigé en français.

1. Problématique et Contexte

L'article s'intéresse au problème de la généralisation hors distribution (OOD - Out-of-Distribution) dans un cadre de régression.

• Contexte : Les données d'entraînement sont collectées dans plusieurs environnements distincts ($E_{tr}$), chacun ayant une distribution de données différente. Le but est de prédire une réponse $Y$ à partir de covariables $X$ dans des environnements de test ($E_{te}$) qui peuvent différer de ceux observés lors de l'entraînement (décalage de distribution).
• Limites des approches classiques : L'Empirical Risk Minimization (ERM) standard minimise la perte moyenne sur toutes les observations, ce qui peut conduire à de mauvaises performances dans l'environnement le plus défavorable (pire cas).
• Approche existante : La minimisation du risque maximum (MaxRM) vise à minimiser le risque le plus élevé parmi les environnements d'entraînement :
  $$\min_{f \in \mathcal{F}} \max_{e \in E_{tr}} \mathbb{E}_{P_e}[\ell(X_e, Y_e; f)]$$
  Bien que des méthodes existent pour les modèles linéaires (comme l'estimateur magging) ou les réseaux de neurones (via l'optimisation robuste de distribution ou DRO), il n'existait pas de méthode efficace et théoriquement fondée appliquée aux forêts aléatoires (Random Forests - RF), un modèle robuste et largement utilisé.

2. Méthodologie : MaxRM Random Forests (MaxRM-RF)

Les auteurs proposent d'adapter les forêts aléatoires pour résoudre le problème MaxRM. Ils définissent le risque $\ell$ de trois manières possibles :

1. Erreur Quadratique Moyenne (MSE) : Risque standard.
2. Récompense Négative (Negative Reward - NRW) : MSE moins la MSE du modèle nul (utilisé dans les travaux antérieurs sur les effets maximin).
3. Regret (Reg) : Différence entre la MSE du prédicteur et celle du meilleur prédicteur possible dans la classe $\mathcal{F}$.

L'algorithme proposé modifie la construction des arbres de régression et/ou le poids des arbres dans l'ensemble (ensemble) selon trois stratégies principales :

A. Ajustement Post-hoc des valeurs des feuilles (MaxRM-RF-posthoc)

C'est la méthode principale recommandée.

1. Construction : On entraîne des arbres de régression standards sur des échantillons bootstrap (comme une RF classique).
2. Optimisation : Une fois la partition de l'espace (les feuilles) fixée, on ré-optimise les valeurs constantes assignées à chaque feuille ($\theta$) en résolvant un problème d'optimisation convexe :
   $$\min_{\theta} \max_{e \in E_{tr}} \hat{R}_e(h_\theta)$$
   Ce problème peut être formulé comme un Programme de Cône Secondaire (SOCP) et résolu efficacement par des méthodes de points intérieurs.
3. Avantage : Cette approche est computationnellement efficace et sépare la structure de l'arbre de l'optimisation du risque.

B. Stratégies de partitionnement local et global

Pour améliorer la performance, les auteurs proposent d'intégrer l'objectif MaxRM directement lors de la construction de l'arbre :

• Local (MaxRM-RF-local) : À chaque split, on optimise uniquement les valeurs des deux nouvelles feuilles créées, en gardant les autres fixes.
• Global (MaxRM-RF-global) : À chaque split, on ré-optimise les valeurs de toutes les feuilles de l'arbre. Bien que plus performant théoriquement, ce coût computationnel est élevé.

C. Optimisation des poids des arbres

Au lieu de donner un poids égal ($1/B$) à chaque arbre, on peut optimiser les poids$w$ de l'ensemble pour minimiser le risque maximum, en résolvant un problème similaire à celui des valeurs des feuilles.

D. Algorithmes d'optimisation alternatifs

Pour les grands jeux de données où les solveurs de points intérieurs échouent, les auteurs proposent deux alternatives :

• La méthode Extragradient.
• La Descente de coordonnées par blocs (Block-Coordinate Descent).

3. Contributions Clés

1. Extension aux Forêts Aléatoires : Introduction de la première méthode MaxRM basée sur les forêts aléatoires, capable de gérer des distributions de covariables qui varient entre les environnements (contrairement à l'estimateur magging qui suppose une distribution de covariables fixe).
2. Garanties Théoriques :
   • Équivalence DRO/MaxRM : Démonstration que minimiser le risque maximum sur les environnements d'entraînement est équivalent à minimiser le risque sur l'enveloppe convexe des distributions d'entraînement (Théorème 3), y compris pour le regret.
   • Consistance : Preuve que les estimateurs obtenus par l'ajustement post-hoc convergent vers les minimiseurs de la population (Théorème 12).
   • Garantie OOD : Preuve d'une garantie de performance hors échantillon pour le risque de regret sur des distributions de test non vues.
3. Efficacité Computationnelle : Développement d'algorithmes scalables (SOCP, extragradient) permettant d'appliquer MaxRM à de grands ensembles de données.

4. Résultats Expérimentaux

Les auteurs évaluent leurs méthodes sur des données simulées et réelles.

• Données Simulées :

  • Comparaison avec RF standard et Group DRO (Réseaux de Neurones) : MaxRM-RF surpasse systématiquement les réseaux de neurones utilisant le DRO de groupe (Sagawa et al., 2020) en termes d'erreur quadratique moyenne maximale (Max MSE).
  • Comparaison avec Magging : Lorsque les distributions des covariables ($P_X$) changent entre les environnements, magging échoue souvent à minimiser le risque maximum. MaxRM-RF maintient une robustesse supérieure dans ces scénarios de décalage de distribution complexe.
  • Stratégie Post-hoc : La méthode MaxRM-RF-posthoc offre le meilleur compromis entre précision (proche de l'oracle) et temps de calcul, surpassant les stratégies globales plus lentes.

• Données Réelles (Logement en Californie) :

  • Sur un jeu de données de prix de l'immobilier divisé par comtés (environnements), MaxRM-RF (avec MSE) a obtenu le pire cas d'erreur (Max MSE) le plus bas sur 4 des 5 plis de validation croisée, avec des améliorations statistiquement significatives par rapport aux RF standards et à la régression linéaire.
  • La méthode montre une meilleure robustesse face aux hétérogénéités régionales.

5. Signification et Conclusion

Cet article comble un vide important entre la théorie de la robustesse distributionnelle (MaxRM/DRO) et les algorithmes d'apprentissage automatique pratiques et performants comme les forêts aléatoires.

• Impact Pratique : Il fournit une boîte à outils robuste pour les applications où la sécurité ou la fiabilité dans le pire des cas est cruciale (ex: santé, climat, finance), sans sacrifier la flexibilité des modèles non linéaires.
• Avance Théorique : L'extension des garanties de consistance et d'optimalité au regret et aux forêts aléatoires ouvre la voie à de nouvelles recherches en apprentissage robuste.
• Conclusion : La méthode proposée, en particulier la variante post-hoc, est recommandée comme une alternative supérieure aux approches basées sur les réseaux de neurones pour la généralisation hors distribution, offrant à la fois des garanties théoriques solides et une efficacité computationnelle supérieure.