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

Resumo Técnico: Complexidade de Amostra da Descoberta Científica

Enunciado do Problema
A descoberta científica via regressão simbólica (SR) é frequentemente caracterizada como estatística e computacionalmente intratável. A visão predominante sugere que o espaço de hipóteses de expressões simbólicas cresce combinatoriamente com a profundidade, tornando a busca por expressões ótimas um problema NP-difícil e a generalização estatística de tais modelos pouco confiável. Este artigo contesta a confluência entre dificuldade computacional e aprendibilidade estatística. Ele postula que, embora encontrar a estrutura simbólica ótima seja computacionalmente difícil, a generalização estatística de árvores de funções composicionais pode ser bem comportada se os operadores subjacentes possuírem propriedades de estabilidade. A questão central abordada é se a complexidade de amostra para aprender árvores de operadores composicionais explode exponencialmente com a profundidade ou se é, em vez disso, controlada pela estabilidade (Lipschitzidade) dos operadores e pela profundidade da árvore.

Metodologia
Os autores abordam o problema através da lente da teoria de aprendizado Provavelmente Aproximadamente Correto (PAC), utilizando especificamente a complexidade de Rademacher para limitar o erro de generalização.

1. Definição do Espaço de Hipóteses: O estudo define um espaço de hipóteses composicional, $H^d_{comp}$, consistindo em árvores de operadores enraizadas de profundidade $d$. Os nós internos são extraídos de um vocabulário finito de operadores suaves e diferenciáveis ($H_{base}$), como $\{+, \times, \sin, \cos, \exp\}$ e mapas afins. As folhas são coordenadas de entrada ou funções afins limitadas.
2. Estrutura Teórica:
   • Pressuposições de Lipschitz: A análise assume que os operadores base são localmente Lipschitz contínuos com constantes $L_h$ nos intervalos de dados relevantes. Uma constante de Lipschitz global $L = \max L_h$ é utilizada para o limite superior.
   • Complexidade de Rademacher: Os autores derivam limites para a complexidade de Rademacher empírica, $R_n(H^d_{comp})$. Eles estendem argumentos de contração clássicos (Ledoux & Talagrand, 1991) e desigualdades de contração vetorial (Maurer, 2016) para composições estruturadas em árvore.
   • Limites Recursivos: Ao aplicar um limite de união sobre o vocabulário finito de operadores ($K = |H_{base}|$) e utilizar a contração vetorial para a composição de $b$ filhos (onde $b$ é a aridade), os autores estabelecem uma relação recursiva entre a complexidade da profundidade $d$ e da profundidade $d-1$.
3. Validação Experimental:
   • Dados Sintéticos: Os autores construíram um código modular em PyTorch para gerar alvos sintéticos do tipo "semelhantes à física" com profundidades controladas ($d \in \{1, 2, 3, 4\}$) e estruturas de verdade fundamental conhecidas.
   • Árvores Diferenciáveis: Em vez de usar programação genética ou busca discreta, eles treinaram árvores de operadores diferenciáveis (não MLPs) usando gradiente descendente (Adam) para ajustar os coeficientes dos operadores.
   • Métricas: Eles mediram o gap de generalização (MSE de teste menos MSE de treino) e compararam-no com o termo de complexidade teórica $(bL^d)/\sqrt{n}$, onde $\hat{L}$ é um estimador empírico da constante de Lipschitz derivado das normas de gradiente.

Principais Contribuições

1. Aprendibilidade Estatística da SR: O artigo prova que a capacidade de generalização de árvores composicionais não necessariamente explode exponencialmente com o número de estruturas simbólicas distintas. Em vez disso, ela é governada pela profundidade $d$ e pelas constantes de Lipschitz dos operadores.
2. Limites de Complexidade Explícitos: Os autores derivam um limite superior concreto para a complexidade de Rademacher:
   $$R_n(H^d_{comp}) \leq (K \cdot b \sqrt{2} L)^{d-1} R_n(H^1_{comp})$$
   Consequentemente, o risco excessivo escala como $O(L^d / \sqrt{n})$ quando o tamanho do vocabulário $K$ e a aridade $b$ são tratados como constantes. Isso contrasta com limites que dependem da cardinalidade do espaço de sintaxe discreta.
3. Separação de Busca e Estimativa: O trabalho separa formalmente o problema de otimização discreta (busca pela estrutura da árvore) do problema de regressão contínua (ajuste de coeficientes). Os limites derivados aplicam-se a este último, esclarecendo a escala estatística que se deve esperar uma vez proposta uma estrutura.
4. Correlação Empírica: Os experimentos demonstram uma correlação positiva entre o gap de generalização observado e o termo de complexidade teórica $(bL^d)/\sqrt{n}$. Os dados mostram que, embora o gap aumente com a profundidade (devido ao acúmulo de constantes de Lipschitz) e diminua com o tamanho da amostra ($1/\sqrt{n}$), a escala alinha-se com a previsão teórica.

Resultados

• Teóricos: O Teorema 4.9 estabelece que, para saídas limitadas e operadores Lipschitz, o risco excessivo decai como $1/\sqrt{n}$, com o fator constante dependendo exponencialmente da profundidade via o produto das constantes de Lipschitz. O Corolário 4.11 traduz isso em um limite de complexidade de amostra PAC, mostrando que a complexidade de amostra escala com $L^{2d}$ em vez da contagem combinatória de árvores.
• Empíricos: Em 400 execuções experimentais variando profundidade ($d$) e tamanho de amostra ($n$), descobriu-se que o gap de generalização acompanha o termo teórico.
  • Para profundidades rasas ($d=1, 2$), o proxy de Lipschitz $\hat{L}$ permaneceu estável, e o gap escalou principalmente com $1/\sqrt{n}$.
  • Para composições mais profundas ($d=3, 4$) envolvendo não-linearidades como $\exp$, $\hat{L}$ aumentou, levando a gaps maiores, consistente com o acúmulo multiplicativo das constantes de estabilidade.
  • Um ajuste de lei de potência em escalas log-log resultou em uma correlação de 0,48, indicando que o termo de complexidade composicional captura uma fração significativa da variância nos gaps de generalização, embora outros fatores (erro de otimização, ruído) também desempenhem um papel.

Significância e Alegações
O artigo alega fornecer um "certificado de aprendibilidade" para a descoberta científica usando regressão simbólica. Sua principal significância reside na mudança de perspectiva da explosão combinatória de estruturas simbólicas para a estabilidade composicional dos operadores.

• Viabilidade de Descoberta com Pequenos Dados: Os autores argumentam que, para vocabulários de operadores estáveis e profundidades modestas, a descoberta científica a partir de pequenos conjuntos de dados é estatisticamente viável. A generalização estatística não é o gargalo; o desafio permanece sendo a busca computacional sobre estruturas e o design de vieses indutivos.
• Esclarecimento de Escala: O trabalho esclarece que a escala estatística da estimativa de coeficientes não lineares é determinada pelo acúmulo de constantes de Lipschitz ao longo do grafo de computação, não pela enumeração de possíveis formas de árvore.
• Limitações: Os autores notam modestamente que seus limites são uniformes e não exploram vieses estruturais (como o Navalha de Occam) tão eficazmente quanto abordagens PAC-Bayes poderiam. Além disso, a validação empírica baseia-se em dados sintéticos controlados, in-distribution, com entradas unidimensionais; o comportamento sob mudança de distribuição ou especificação incorreta não é garantido por estes limites. O estimador $\hat{L}$ mede a estabilidade no mapa ajustado, em vez de certificar uma constante global de pior caso.

Em conclusão, o artigo afirma que os modelos de regressão simbólica, quando vistos como árvores de funções composicionais com primitivas estáveis, possuem propriedades estatísticas favoráveis que permitem a generalização mesmo com dados limitados, desde que a profundidade e a estabilidade do operador sejam geridas.