Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees

Résumé Technique : Complexité d'Échantillonnage de la Découverte Scientifique

Énoncé du Problème
La découverte scientifique via la régression symbolique (RS) est fréquemment caractérisée comme étant statistiquement et computationnellement intraitable. La vue prédominante suggère que l'espace d'hypothèses des expressions symboliques croît de manière combinatoire avec la profondeur, rendant la recherche d'expressions optimales NP-difficile et la généralisation statistique de tels modèles peu fiable. Ce document remet en question la confusion entre la difficulté computationnelle et l'apprentissage statistique. Il postule que si la recherche de la structure symbolique optimale est difficile sur le plan computationnel, la généralisation statistique des arbres de fonctions compositionnelles peut être bien comportementale si les opérateurs sous-jacents possèdent des propriétés de stabilité. La question centrale abordée est de savoir si la complexité d'échantillonnage de l'apprentissage d'arbres d'opérateurs compositionnels explose exponentiellement avec la profondeur, ou si elle est plutôt contrôlée par la stabilité (Lipschitzianité) des opérateurs et la profondeur de l'arbre.

Méthodologie
Les auteurs abordent le problème à travers le prisme de la théorie de l'apprentissage Probably Approximately Correct (PAC), en utilisant spécifiquement la complexité de Rademacher pour borner l'erreur de généralisation.

1. Définition de l'Espace d'Hypothèses : L'étude définit un espace d'hypothèses compositionnelles, $H^d_{comp}$, constitué d'arbres d'opérateurs enracinés de profondeur $d$. Les nœuds internes sont tirés d'un vocabulaire fini d'opérateurs lisses et différentiables ($H_{base}$), tels que $\{+, \times, \sin, \cos, \exp\}$ et des applications affines. Les feuilles sont soit des coordonnées d'entrée, soit des fonctions affines bornées.
2. Cadre Théorique :
   • Hypothèses de Lipschitz : L'analyse suppose que les opérateurs de base sont localement Lipschitz continus avec des constantes $L_h$ sur les plages de données pertinentes. Une constante de Lipschitz globale $L = \max L_h$ est utilisée pour le bornage.
   • Complexité de Rademacher : Les auteurs dérivent des bornes sur la complexité de Rademacher empirique, $R_n(H^d_{comp})$. Ils étendent les arguments de contraction classiques (Ledoux & Talagrand, 1991) et les inégalités de contraction vectorielle (Maurer, 2016) aux compositions d'arbres.
   • Bornes Récursives : En appliquant une borne d'union sur le vocabulaire fini d'opérateurs ($K = |H_{base}|$) et en utilisant la contraction vectorielle pour la composition de $b$ enfants (où $b$ est l'arité), les auteurs établissent une relation récursive entre la complexité de la profondeur $d$ et celle de la profondeur $d-1$.
3. Validation Expérimentale :
   • Données Synthétiques : Les auteurs ont construit une base de code PyTorch modulaire pour générer des cibles synthétiques de type "physique" avec des profondeurs contrôlées ($d \in \{1, 2, 3, 4\}$) et des structures de vérité terrain connues.
   • Arbres Différentiables : Au lieu d'utiliser la programmation génétique ou la recherche discrète, ils ont entraîné des arbres d'opérateurs différentiables (pas des MLP) en utilisant la descente de gradient (Adam) pour ajuster les coefficients des opérateurs.
   • Métriques : Ils ont mesuré l'écart de généralisation (MSE de test moins MSE d'entraînement) et l'ont comparé au terme de complexité théorique $(bL^d)/\sqrt{n}$, où $\hat{L}$ est un estimateur empirique de la constante de Lipschitz dérivé des normes de gradient.

Contributions Clés

1. Apprentissabilité Statistique de la RS : Le papier prouve que la capacité de généralisation des arbres compositionnels ne s'envole pas nécessairement de manière exponentielle avec le nombre de structures symboliques distinctes. Elle est plutôt gouvernée par la profondeur $d$ et les constantes de Lipschitz des opérateurs.
2. Bornes de Complexité Explicites : Les auteurs dérivent une borne supérieure concrète pour la complexité de Rademacher :
   $$R_n(H^d_{comp}) \leq (K \cdot b \sqrt{2} L)^{d-1} R_n(H^1_{comp})$$
   Par conséquent, le risque excédentaire suit une échelle de $O(L^d / \sqrt{n})$ lorsque la taille du vocabulaire $K$ et l'arité $b$ sont traités comme des constantes. Cela contraste avec les bornes qui dépendent de la cardinalité de l'espace syntaxique discret.
3. Séparation de la Recherche et de l'Estimation : Le travail sépare formellement le problème d'optimisation discrète (recherche de la structure de l'arbre) du problème de régression continue (ajustement des coefficients). Les bornes dérivées s'appliquent à ce dernier, clarifiant l'échelle statistique que l'on peut attendre une fois une structure proposée.
4. Corrélation Empirique : Les expériences démontrent une corrélation positive entre l'écart de généralisation observé et le terme de complexité théorique $(bL^d)/\sqrt{n}$. Les données montrent que si l'écart augmente avec la profondeur (en raison de l'accumulation des constantes de Lipschitz) et diminue avec la taille de l'échantillon ($1/\sqrt{n}$), l'échelle s'aligne sur la prédiction théorique.

Résultats

• Théoriques : Le Théorème 4.9 établit que pour des sorties bornées et des opérateurs Lipschitz, le risque excédentaire décroît en $1/\sqrt{n}$, avec le facteur constant dépendant exponentiellement de la profondeur via le produit des constantes de Lipschitz. Le Corollaire 4.11 traduit cela en une borne de complexité d'échantillonnage PAC, montrant que la complexité d'échantillonnage passe à l'échelle avec $L^{2d}$ plutôt qu'avec le compte combinatoire des arbres.
• Empiriques : À travers 400 essais expérimentaux variant la profondeur ($d$) et la taille de l'échantillon ($n$), l'écart de généralisation a été trouvé suivre le terme théorique.
  • Pour les profondeurs faibles ($d=1, 2$), le proxy de Lipschitz $\hat{L}$ est resté stable, et l'écart a suivi principalement une échelle en $1/\sqrt{n}$.
  • Pour les compositions plus profondes ($d=3, 4$) impliquant des non-linéarités comme $\exp$, $\hat{L}$ a augmenté, entraînant des écarts plus importants, ce qui est cohérent avec l'accumulation multiplicative des constantes de stabilité.
  • Un ajustement de loi de puissance sur des échelles log-log a produit une corrélation de 0,48, indiquant que le terme de complexité compositionnelle capture une fraction significative de la variance des écarts de généralisation, bien que d'autres facteurs (erreur d'optimisation, bruit) jouent également un rôle.

Signification et Revendications
Le papier revendique l'apport d'un "certificat d'apprentissage" pour la découverte scientifique utilisant la régression symbolique. Sa signification primaire réside dans le déplacement de la perspective de l'explosion combinatoire des structures symboliques vers la stabilité compositionnelle des opérateurs.

• Faisabilité de la Découverte avec de Petits Jeux de Données : Les auteurs soutiennent que pour des vocabulaires d'opérateurs stables et des profondeurs modérées, la découverte scientifique à partir de petits jeux de données est statistiquement faisable. La généralisation statistique n'est pas le goulot d'étranglement ; le défi reste la recherche computationnelle sur les structures et la conception des biais inductifs.
• Clarification de l'Échelle : Le travail clarifie que l'échelle statistique de l'estimation des coefficients non linéaires est déterminée par l'accumulation des constantes de Lipschitz le long du graphe de calcul, et non par l'énumération des formes d'arbres possibles.
• Limites : Les auteurs notent modestement que leurs garanties sont des bornes uniformes et n'exploitent pas les priors structurels (comme le rasoir d'Occam) aussi efficacement que des approches PAC-Bayes pourraient le faire. De plus, la validation empirique repose sur des données synthétiques contrôlées, in-distribution, avec des entrées unidimensionnelles ; le comportement sous un changement de distribution ou une erreur de spécification n'est pas garanti par ces bornes. L'estimateur $\hat{L}$ mesure la stabilité sur la fonction ajustée plutôt que de certifier une constante globale pire cas.

En conclusion, le papier affirme que les modèles de régression symbolique, lorsqu'ils sont vus comme des arbres de fonctions compositionnelles avec des primitives stables, possèdent des propriétés statistiques favorables qui permettent la généralisation même avec des données limitées, à condition que la profondeur et la stabilité des opérateurs soient maîtrisées.