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

Sintesi Tecnica: Complessità Campionaria della Scoperta Scientifica

Enunciato del Problema
La scoperta scientifica tramite regressione simbolica (SR) è frequentemente caratterizzata come statisticamente e computazionalmente intrattabile. La visione prevalente suggerisce che lo spazio delle ipotesi di espressioni simboliche cresca in modo combinatorio con la profondità, rendendo la ricerca di espressioni ottimali un problema NP-hard e la generalizzazione statistica di tali modelli inaffidabile. Questo articolo sfida la conflazione tra difficoltà computazionale e apprendibilità statistica. Esso postula che, sebbene trovare la struttura simbolica ottimale sia computazionalmente difficile, la generalizzazione statistica di alberi di funzioni compositive possa essere ben comportata se gli operatori sottostanti possiedono proprietà di stabilità. La domanda centrale affrontata è se la complessità campionaria dell'apprendimento di alberi di operatori compositivi esploda esponenzialmente con la profondità o se sia invece controllata dalla stabilità (Lipschitzianità) degli operatori e dalla profondità dell'albero.

Metodologia
Gli autori approcciano il problema attraverso la lente della teoria dell'apprendimento Probably Approximately Correct (PAC), utilizzando specificamente la complessità di Rademacher per limitare l'errore di generalizzazione.

1. Definizione dello Spazio delle Ipotesi: Lo studio definisce uno spazio di ipotesi compositivo, $H^d_{comp}$, costituito da alberi di operatori radicati di profondità $d$. I nodi interni sono tratti da un vocabolario finito di operatori derivabili e regolari ($H_{base}$), come $\{+, \times, \sin, \cos, \exp\}$ e mappe affini. Le foglie sono o coordinate di input o funzioni affini limitate.
2. Framework Teorico:
   • Assunzioni di Lipschitz: L'analisi assume che gli operatori base siano localmente Lipschitz continui con costanti $L_h$ sugli intervalli di dati rilevanti. Una costante di Lipschitz globale $L = \max L_h$ viene utilizzata per il bounding.
   • Complessità di Rademacher: Gli autori derivano i limiti della complessità empirica di Rademacher, $R_n(H^d_{comp})$. Essi estendono i classici argomenti di contrazione (Ledoux & Talagrand, 1991) e le disuguaglianze di contrazione vettoriale (Maurer, 2016) alle composizioni strutturate ad albero.
   • Limiti Ricorsivi: Applicando un limite superiore (union bound) sul vocabolario finito di operatori ($K = |H_{base}|$) e utilizzando la contrazione vettoriale per la composizione di $b$ figli (dove $b$ è l'arità), gli autori stabiliscono una relazione ricorsiva tra la complessità di profondità $d$ e di profondità $d-1$.
3. Validazione Sperimentale:
   • Dati Sintetici: Gli autori hanno costruito un codice PyTorch modulare per generare target sintetici "simili alla fisica" con profondità controllate ($d \in \{1, 2, 3, 4\}$) e strutture di verità fondamentale note.
   • Alberi Differenziabili: Invece di utilizzare la programmazione genetica o la ricerca discreta, hanno addestrato alberi di operatori differenziabili (non MLP) utilizzando la discesa del gradiente (Adam) per adattare i coefficienti degli operatori.
   • Metriche: Hanno misurato il gap di generalizzazione (MSE di test meno MSE di training) e l'hanno confrontato con il termine di complessità teorica $(bL^d)/\sqrt{n}$, dove $\hat{L}$ è un estimatore empirico della costante di Lipschitz derivato dalle norme dei gradienti.

Contributi Chiave

1. Apprendibilità Statistica della SR: Il documento prova che la capacità di generalizzazione degli alberi compositivi non esplode necessariamente esponenzialmente con il numero di distinte strutture simboliche. Al contrario, essa è governata dalla profondità $d$ e dalle costanti di Lipschitz degli operatori.
2. Limiti Espliciti di Complessità: Gli autori derivano un limite superiore concreto per la complessità di Rademacher:
   $$R_n(H^d_{comp}) \leq (K \cdot b \sqrt{2} L)^{d-1} R_n(H^1_{comp})$$
   Di conseguenza, l'eccesso di rischio scala come $O(L^d / \sqrt{n})$ quando la dimensione del vocabolario $K$ e l'arità $b$ sono trattate come costanti. Ciò contrasta con i limiti che dipendono dalla cardinalità dello spazio della sintassi discreta.
3. Separazione di Ricerca e Stima: Il lavoro separa formalmente il problema di ottimizzazione discreta (ricerca della struttura dell'albero) dal problema di regressione continua (adattamento dei coefficienti). I limiti derivati si applicano a quest'ultimo, chiarendo la scalabilità statistica che ci si può aspettare una volta proposta una struttura.
4. Correlazione Empirica: Gli esperimenti dimostrano una correlazione positiva tra il gap di generalizzazione osservato e il termine di complessità predetto $(bL^d)/\sqrt{n}$. I dati mostrano che, sebbene il gap aumenti con la profondità (a causa dell'accumulo delle costanti di Lipschitz) e diminuisca con la dimensione del campione ($1/\sqrt{n}$), la scalabilità si allinea con la previsione teorica.

Risultati

• Teorici: Il Teorema 4.9 stabilisce che per output limitati e operatori Lipschitz, l'eccesso di rischio decade come $1/\sqrt{n}$, con il fattore costante che dipende esponenzialmente dalla profondità tramite il prodotto delle costanti di Lipschitz. Il Corollario 4.11 traduce questo in un limite di complessità campionaria PAC, mostrando che la complessità campionaria scala con $L^{2d}$ piuttosto che con il conteggio combinatorio degli alberi.
• Empirici: Attraverso 400 sessioni sperimentali variando la profondità ($d$) e la dimensione del campione ($n$), si è scoperto che il gap di generalizzazione segue il termine teorico.
  • Per profondità superficiali ($d=1, 2$), il proxy di Lipschitz $\hat{L}$ è rimasto stabile e il gap è scalato principalmente con $1/\sqrt{n}$.
  • Per composizioni più profonde ($d=3, 4$) che coinvolgono non linearità come $\exp$, $\hat{L}$ è aumentato, portando a gap più ampi, coerentemente con l'accumulo moltiplicativo delle costanti di Lipschitz.
  • Un fit power-law su scale log-log ha prodotto una correlazione di 0.48, indicando che il termine di complessità compositiva cattura una frazione significativa della varianza dei gap di generalizzazione, sebbene altri fattori (errore di ottimizzazione, rumore) giochino un ruolo.

Significatività e Rivendicazioni
Il documento rivendica di fornire un "certificato di apprendibilità" per la scoperta scientifica tramite regressione simbolica. La sua significatività primaria risiede nello spostamento della prospettiva dall'esplosione combinatoria delle strutture simboliche alla stabilità compositiva degli operatori.

• Fattibilità della Scoperta con Piccoli Campioni: Gli autori sostengono che per vocabolari di operatori stabili e profondità moderate, la scoperta scientifica da piccoli dataset è statisticamente fattibile. La generalizzazione statistica non è l'ostacolo; piuttosto, la sfida rimane la ricerca computazionale sulle strutture e la progettazione dei bias induttivi.
• Chiarificazione della Scalabilità: Il lavoro chiarisce che la scalabilità statistica della stima dei coefficienti non lineari è determinata dall'accumulo delle costanti di Lipschitz lungo il grafo computazionale, non dall'enumerazione delle possibili forme degli alberi.
• Limitazioni: Gli autori notano con modestia che le loro garanzie sono limiti uniformi e non sfruttano i priori strutturali (come l'Occam's razor) in modo altrettanto efficace quanto potrebbero fare gli approcci PAC-Bayes. Inoltre, la validazione empirica si basa su dati sintetici controllati, in-distribution, con input monodimensionali; il comportamento sotto shift di distribuzione o misspecificazione non è garantito da questi limiti. L'estimatore $\hat{L}$ misura la stabilità sulla mappa adattata piuttosto che certificare una costante globale nel caso peggiore.

In conclusione, il documento afferma che i modelli di regressione simbolica, quando visti come alberi di funzioni compositive con primitive stabili, possiedono proprietà statistiche favorevoli che permettono la generalizzazione anche con dati limitati, a patto che la profondità e la stabilità degli operatori siano gestite.