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

Technische Samenvatting: Steekproefcomplexiteit van Wetenschappelijke Ontdekking

Probleemstelling
Wetenschappelijke ontdekking via symbolische regressie (SR) wordt vaak gekenmerkt als statistisch en computationeel onhandelbaar. De heersende opvatting suggereat dat de hypotheseruimte van symbolische expressies combinatorisch groeit met de diepte, waardoor de zoektocht naar optimale expressies NP-hard is en de statistische generalisatie van dergelijke modellen onbetrouwbaar is. Dit artikel daagt de samensmelting van computationele hardheid met statistische leerbaarheid uit. Het stelt dat hoewel het vinden van de optimale symbolische structuur computationeel moeilijk is, de statistische generalisatie van compositionele functiebomen goed gedrag kan vertonen als de onderliggende operatoren stabiliteitseigenschappen bezitten. De kernvraag die wordt behandeld, is of de steekproefcomplexiteit van het leren van compositionele operatorbomen exponentieel explodeert met de diepte, of dat deze in plaats daarvan wordt beheerst door de stabiliteit (Lipschitz-continuïteit) van de operatoren en de diepte van de boom.

Methodologie
De auteurs benaderen het probleem vanuit het perspectief van de Probably Approximately Correct (PAC) leertcholing, waarbij specifiek gebruik wordt gemaakt van de Rademacher-complexiteit om de generalisatiefout te begrenzen.

1. Definitie van de Hypotheseruimte: De studie definieert een compositionele hypotheseruimte, $H^d_{comp}$, bestaande uit gewortelde operatorbomen van diepte $d$. De interne knopen zijn afkomstig uit een eindige vocabulaire van gladde, differentieerbare operatoren ($H_{base}$), zoals $\{+, \times, \sin, \cos, \exp\}$ en affiene mappen. De bladeren zijn ofwel inputcoördinaten of begrensde affiene functies.
2. Theoretisch Kader:
   • Lipschitz-aannames: De analyse gaat ervan uit dat de basisoperatoren lokaal Lipschitz-continu zijn met constanten $L_h$ op de relevante databereiken. Een globale Lipschitz-constante $L = \max L_h$ wordt gebruikt voor de begrenzing.
   • Rademacher-complexiteit: De auteurs leiden bounds af voor de empirische Rademacher-complexiteit, $R_n(H^d_{comp})$. Ze breiden klassieke contractie-argumenten (Ledoux & Talagrand, 1991) en vector-contractie-ongelijkheden (Maurer, 2016) uit naar boomstructuur-composities.
   • Recursieve Bounds: Door een union bound toe te passen over de eindige operator-vocabulaire ($K = |H_{base}|$) en gebruik te maken van vector-contractie voor de compositie van $b$ kinderen (waarbij $b$ de ariteit is), stellen de auteurs een recursieve relatie vast tussen de complexiteit van diepte $d$ en diepte $d-1$.
3. Experimentele Validatie:
   • Synthetische Data: De auteurs hebben een modulaire PyTorch-codebase geconstrueerd om synthetische "physics-like" doelwitten te genereren met gecontroleerde dieptes ($d \in \{1, 2, 3, 4\}$) en bekende grondwaarheid-structuren.
   • Differentiabele Bomen: In plaats van genetische programmering of discrete zoekalgoritmen, hebben ze differentiabele operatorbomen (geen MLPs) getraind met behulp van gradiëntafdaling (Adam) om de coëfficiënten van de operatoren aan te passen.
   • Metrieken: Ze hebben het generalisatieverschil (test MSE minus train MSE) gemeten en dit vergeleken met de theoretische complexiteitsterm $(bL^d)/\sqrt{n}$, waarbij $\hat{L}$ een empirische estimator van de Lipschitz-constante is, afgeleid van gradiëntnormen.

Belangrijkste Bijdragen

1. Statistische Leerbaarheid van SR: Het artikel bewijst dat het generalisatievermogen van compositionele bomen niet noodzakelijkerwijs exponentieel explodeert met het aantal verschillende symbolische structuren. In plaats daarvan wordt het beheerst door de diepte $d$ en de Lipschitz-constanten van de operatoren.
2. Expliciete Complexiteitsbounds: De auteurs leiden een concrete bovengrens af voor de Rademacher-complexiteit:
   $$R_n(H^d_{comp}) \leq (K \cdot b \sqrt{2} L)^{d-1} R_n(H^1_{comp})$$
   Bij consequentie schaalt het excessieve risico als $O(L^d / \sqrt{n})$ wanneer de vocabulairegrootte $K$ en de ariteit $b$ als constanten worden beschouwd. Dit staat in contrast met bounds die afhankelijk zijn van de cardinaliteit van de discrete syntaxisruimte.
3. Scheiding van Zoektocht en Schatting: Het werk scheidt formeel het discrete optimalisatieprobleem (het zoeken naar de boomstructuur) van het continue regressieprobleem (het aanpassen van de coëfficiënten). De afgeleide bounds zijn van toepassing op dat laatste, wat verduidelijkt welke statistische schaling men kan verwachten zodra een structuur is voorgesteld.
4. Empirische Correlatie: De experimenten tonen een positieve correlatie aan tussen de geobserveerde generalisatiekloof en de voorspelde complexiteitsterm $(bL^d)/\sqrt{n}$. De gegevens laten zien dat hoewel de kloof toeneemt met de diepte (door de accumulatie van Lipschitz-constanten) en afneemt met de steekproefomvang ($1/\sqrt{n}$), de schaling overeenkomt met de theoretische voorspelling.

Resultaten

• Theoretisch: Stelling 4.9 stelt vast dat voor begrensde outputs en Lipschitz-continue operatoren, het excessieve risico vervalt als $1/\sqrt{n}$, waarbij de constante factor exponentieel afhankelijk is van de diepte via het product van de Lipschitz-constanten. Corolarium 4.11 vertaalt dit naar een PAC-steekproefcomplexiteit-bound, die laat zien dat de steekproefcomplexiteit schaalt met $L^{2d}$ in plaats van met de combinatorische telling van bomen.
• Empirisch: Over 400 experimentele runs variërend in diepte ($d$) en steekproefomvang ($n$), werd gevonden dat de generalisatiekloof de theoretische term volgt.
  • Voor ondiepe dieptes ($d=1, 2$) bleef de Lipschitz-proxy $\hat{L}$ stabiel, en de kloof schaalde primair met $1/\sqrt{n}$.
  • Voor diepere composities ($d=3, 4$) met niet-lineaire elementen zoals $\exp$, nam $\hat{L}$ toe, wat leidde tot grotere kloven, consistent met de multiplicatieve accumulatie van stabiliteitsconstanten.
  • Een power-law fit op log-log schalen leverde een correlatie op van 0,48, wat aangeeft dat de compositionele complexiteitsterm een betekenend deel van de variantie in de generalisatiekloven verklaart, hoewel andere factoren (optimalisatiefouten, ruis) ook een rol spelen.

Betekenis en Claims
Het artikel claimt een "leerbaarheidscertificaat" te bieden voor wetenschappelijke ontdekking via symbolische regressie. De primaire betekenis ligt in het verschuiven van het perspectief van de combinatorische explosie van symbolische structuren naar de compositionele stabiliteit van de operatoren.

• Haalbaarheid van Ontdekking met Kleine Datasets: De auteurs argumenteren dat voor stabiele operator-vocabularia en bescheiden dieptes, wetenschappelijke ontdekking vanuit kleine datasets statistisch haalbaar is. De statistische generalisatie is niet de bottleneck; de uitdaging blijft de computationele zoektocht over structuren en het ontwerp van inductieve biases.
• Verduidelijking van Schaling: Het werk verheldert dat de statistische schaling van niet-lineaire coëfficiëntschatting wordt bepaald door de accumulatie van Lipschitz-constanten langs de computationele graaf, en niet door de enumeratie van mogelijke boomvormen.
• Beperkingen: De auteurs merken bescheiden op dat hun garanties uniforme bounds zijn en de structurele priors (zoals Occam's Razor) niet zo effectief benutten als PAC-Bayes benaderingen zouden kunnen doen. Bovendien berust de empirische validatie op gecontroleerde, in-distributie synthetische data met ééndimensionale inputs; het gedrag onder distributieverschuiving of mis-specificatie wordt niet door deze bounds gegarandeerd. De estimator $\hat{L}$ meet de stabiliteit op de gefitte kaart in plaats van een worst-case globale constante te certificeren.

Concluderend stelt het artikel dat symbolische regressiemodellen, wanneer ze worden beschouwd als compositionele functiebomen met stabiele primitieven, gunstige statistische eigenschappen bezitten die generalisatie mogelijk maken zelfs met beperkte data, mits de diepte en de stabiliteit van de operatoren worden beheerd.