Résumé Technique : Améliorer la Généralisation de la Construction de Caractéristiques Évolutives par la Minimisation de l'Écart de Jensen Vicinal

Énoncé du Problème

La construction de caractéristiques basée sur la Programmation Génétique (GP) est apparue comme une technique puissante d'apprentissage automatique symbolique automatisé. Cependant, un défi persistant qui limite sa large applicabilité est le surapprentissage (overfitting). Bien que les méthodes de GP atteignent souvent des performances élevées sur les données d'entraînement, les caractéristiques construites échouent fréquemment à se généraliser aux données non vues. Les approches traditionnelles pour contrôler le surapprentissage, telles que la régulation de la taille du modèle (pression de parcimonie), se sont révélées insuffisantes pour caractériser la complexité des modèles évolutifs modernes. De plus, les mesures théoriques existantes comme la dimension VC ou la complexité de Rademacher échouent souvent à prédire avec précision la performance de généralisation dans des contextes inspirés de l'apprentissage profond. De plus, l'application directe de la Minimisation du Risque Vicinal (VRM) — une technique ayant réussi dans l'apprentissage profond pour atténuer le surapprentissage via l'augmentation de données — à la régression par GP est problématique car la VRM standard suppose que les étiquettes cibles restent stables sous de petites perturbations, une hypothèse qui échoue souvent dans les tâches de régression où les valeurs cibles sont continues.

Méthodologie

Le papier propose un cadre pour améliorer la généralisation en décomposant le Risque Vicinal en une composante de perte empirique et un terme de régularisation. Cette décomposition permet l'optimisation indépendante de la précision d'entraînement et de la lissité du modèle.

1. Décomposition Théorique du Risque Vicinal

Les auteurs prouvent que le risque vicinal est borné par la somme du risque empirique et d'un terme de régularisation, dépendant de la stratégie d'augmentation de données :

• Perturbation par Bruit : Si les exemples vicinaux sont synthétisés via une perturbation par le bruit (ex: bruit gaussien), le terme de régularisation est une Différence Finie. Cela pénalise les changements rapides de la sortie de la fonction en réponse à de petites variations d'entrée.
• Augmentation par Mixup : Si les exemples vicinaux sont synthétisés en utilisant la méthode Mixup (interpolation linéaire des entrées et des étiquettes), le terme de régularisation est l'Écart de Jensen Vicinal. Ce terme, défini par $(\lambda f(x_i) + (1-\lambda)f(x_j) - f(\lambda x_i + (1-\lambda)x_j))^2$, pénalise la convexité et la concavité, favorisant la linéarité locale entre des points de données proches.

Les auteurs soutiennent que la décomposition du risque est supérieure à l'optimisation du risque vicinal brut car elle permet :

• Des Compromis Flexibles : Un contrôle précis de l'équilibre entre la perte empirique et la lissité.
• Une Estimation Précise de l'Erreur : Garantir que la perte empirique est calculée précisément sur les données originales plutôt que d'être confondue avec des échantillons augmentés bruités.
• L'Intégration de la Perte de Validation : Permettre l'utilisation de la perte de validation croisée (plutôt que de la simple perte empirique) comme métrique de précision principale.

2. L'Algorithme Proposé (VJM-GP)

Les auteurs introduisent la GP basée sur la Minimisation de l'Écart de Jensen Vicinal (VJM-GP), un cadre de construction de caractéristiques évolutives qui optimise conjointement :

1. La Perte Empirique : Mesurée via la validation croisée de type Leave-One-Out (LOOCV) pour assurer la robustesse.
2. Le Terme de Régularisation : L'Écart de Jensen Vicinal (ou la Différence Finie).

Les composants clés de l'algorithme incluent :

• Optimisation Multi-Objectif : Utilise le tri non dominé avec distance de crowding pour faire évoluer un front de Pareto de solutions, équilibrant la perte de validation croisée et le terme de régularisation.
• Stratégie d'Estimation du Bruit : Puisque les jeux de données varient en termes de niveaux de bruit, les auteurs proposent une stratégie dynamique pour ajuster le poids de régularisation ($\tau$). Ils utilisent le score $R^2$ d'arbres extrêmement randomisés (Extra Trees) sur le jeu de données pour estimer le bruit ; des niveaux de bruit plus élevés déclenchent un poids de régularisation plus fort pour éviter de s'ajuster au bruit.
• Détection d'Intrusion de Variété (Manifold Intrusion) : Pour traiter le problème où les échantillons générés par Mixup tombent en dehors de la véritable variété des données (créant des échantillons irréalistes), les auteurs proposent un mécanisme de détection. Si l'étiquette d'un échantle synthétisé (prédite par un modèle Extra Trees entraîné sur les données originales) dévie significativement de l'interpolation linéaire de ses parents, l'échantillon est rejeté. Cela empêche la minimisation de l'écart de Jensen de pénaliser excessivement des modèles efficaces dans des régions hautement non linéaires.

Contributions Clés

1. Décomposition Théorique : Le papier dérive des bornes supérieures montrant que la VRM par perturbation se décompose en risque empirique et différence finie, tandis que la VRM par mixup se décompose en risque empirique et écart de Jensen vicinal.
2. Cadre de GP Régularisé : Un nouveau cadre de GP (VJM-GP) est proposé qui optimise simultanément la perte de validation croisée et l'écart de Jensen vicinal, offrant un contrôle plus efficace du surapprentissage que les mesures de complexité traditionnelles.
3. Régularisation Adaptative : Une stratégie d'estimation du bruit est introduite pour ajuster dynamiquement la force de régularisation en fonction des caractéristiques du jeu de données, évitant une pénalisation excessive dans les scénarios à faible bruit.
4. Atténuation de l'Intrusion de Variété : Une stratégie de détection est proposée pour filtrer les échantillons augmentés irréalistes, garantissant que le terme de régularisation reflète la véritable géométrie de la variété des données.

Résultats Expérimentaux

La méthode proposée a été évaluée sur 58 jeux de données de régression réels provenant du Penn Machine Learning Benchmark (PMLB).

• Comparaison des Régularisateurs : L'Écart de Jensen Vicinal s'est avéré être un régularisateur plus efficace que la Différence Finie, surpassant cette dernière sur 15 jeux de données tout en étant moins performant sur seulement 5.
• Comparaison avec les Mesures de Complexité : VJM-GP a nettement surpassé la GP standard et sept autres méthodes de contrôle de la complexité (incluant la pression de parcimonie, la régularisation de Tikhonov, la complexité de Rademacher et la P-VRM) en termes de scores $R^2$ de test. Il a obtenu une généralisation supérieure sur 36 jeux de données par rapport à la GP standard.
• Comparaison avec les Références : VJM-GP a été comparé à 15 algorithmes de pointe de régression symbolique et d'apprentissage automatique (incluant XGBoost et ExcelFormer). Il a obtenu des performances compétitives ou supérieures, particulièrement dans les scénarios avec des tailles d'échantillons limitées, tout en maintenant des tailles de modèles nettement plus petites que les méthodes de gradient boosting.
• Études d'Ablation :
  • Détection d'Intrusion de Variété : Le retrait de cette stratégie a entraîné une performance de test inférieure sur 6 jeux de données, confirmant sa nécessité.
  • Estimation du Bruit : La stratégie de pondération adaptative a considérablement amélioré les performances sur 12 jeux de données par rapport à un poids fixe, validant le besoin d'une régularisation dynamique.
• Bruit d'Étiquette : Dans les expériences avec des étiquettes bruitées, VJM-GP a démontré une robustesse supérieure par rapport à la GP standard et la P-VRM.

Signification et Revendications

Le papier affirme que la décomposition proposée du risque vicinal fournit une compréhension théorique plus profonde du surapprentissage dans la construction de caractéristiques évolutives. En séparant la perte empirique du terme de régularisation, la méthode permet un contrôle plus nuancé de la complexité du modèle qui se concentre sur la complexité fonctionnelle (lissité et linéarité) plutôt que sur la simple complexité syntaxique (taille de l'arbre).

Les auteurs soutiennent que leur approche permet à la GP d'atteindre des performances de premier plan dans les tâches de régression symbolique, particulièrement lorsque les données sont rares ou bruitées. Ils soulignent qu'un contrôle efficace du surapprentissage nécessite de l'équilibrer l'exactitude et la lissité, et que minimiser aveuglément la taille du modèle est insuffisant. Le travail suggère que le cadre proposé peut être intégré à d'autres algorithmes évolutifs et potentiellement adapté aux méthodes de régression symbolique basées sur l'apprentissage profond à l'avenir.