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

Resumen Técnico: Complejidad de Muestreo del Descubrimiento Científico

Planteamiento del Problema
El descubrimiento científico mediante la regresión simbólica (SR, por sus siglas en inglés) se caracteriza frecuentemente como estadística y computacionalmente intratable. La visión predominante sugiere que el espacio de hipótesis de las expresiones simbólicas crece de forma combinatoria con la profundidad, lo que convierte la búsqueda de expresiones óptimas en un problema NP-duro y hace que la generalización estadística de tales modelos sea poco fiable. Este artículo desafía la confusión entre la dificultad computacional y la aprendibilidad estadística. Postula que, si bien encontrar la estructura simbólica óptima es computacionalmente difícil, la generalización estadística de los árboles de funciones composicionales puede comportarse bien si los operadores subyacentes poseen propiedades de estabilidad. La cuestión central abordada es si la complejidad de muestreo para aprender árboles de operadores composicionales explota exponencialmente con la profundidad, o si, por el contrario, está controlada por la estabilidad (Lipschitzidad) de los operadores y la profundidad del árbol.

Metodología
Los autores abordan el problema a través de la lente de la teoría del aprendizaje Probablemente Aproximadamente Correcto (PAC), utilizando específicamente la complejidad de Rademacher para acotar el error de generalización.

1. Definición del Espacio de Hipótesis: El estudio define un espacio de hipótesis composicional, $H^d_{comp}$, que consiste en árboles de operadores con raíz de profundidad $d$. Los nodos internos se extraen de un vocabulario finito de operadores suaves y diferenciables ($H_{base}$), tales como $\{+, \times, \sin, \cos, \exp\}$ y mapas afines. Las hojas son coordenadas de entrada o funciones afines acotadas.
2. Marco Teórico:
   • Supuestos de Lipschitz: El análisis asume que los operadores base son localmente Lipschitz continuos con constantes $L_h$ en los rangos de datos relevantes. Se utiliza una constante de Lipschitz global $L = \max L_h$ para el acotamiento.
   • Complejidad de Rademacher: Los autores derivan cotas para la complejidad de Rademacher empírica, $R_n(H^d_{comp})$. Extienden los argumentos de contracción clásicos (Ledoux & Talagrand, 1991) y las desigualdades de contracción vectorial (Maurer, 2016) a las composiciones estructuradas en árboles.
   • Cotas Recursivas: Aplicando un límite de unión sobre el vocabulario finito de operadores ($K = |H_{base}|$) y utilizando la contracción vectorial para la composición de $b$ hijos (donde $b$ es la aridad), los autores establecen una relación recursiva entre la complejidad de la profundidad $d$ y la de la profundidad $d-1$.
3. Validación Experimental:
   • Datos Sintéticos: Los autores construyeron un código modular en PyTorch para generar objetivos sintéticos de tipo "física" con profundidades controladas ($d \in \{1, 2, 3, 4\}$) y estructuras de verdad fundamental conocidas.
   • Árboles Diferenciables: En lugar de utilizar programación genética o búsqueda discreta, entrenaron árboles de operadores diferenciables (no MLP) utilizando el descenso de gradiente (Adam) para ajustar los coeficientes de los operadores.
   • Métricas: Midieron la brecha de generalización (MSE de prueba menos MSE de entrenamiento) y la compararon contra el término de complejidad teórica $(bL^d)/\sqrt{n}$, donde $\hat{L}$ es un estimador empírico de la constante de Lipschitz derivado de las normas de los gradientes.

Contribuciones Clave

1. Aprendibilidad Estadística de la SR: El artículo demuestra que la capacidad de generalización de los árboles composicionales no necesariamente estalla exponencialmente con el número de estructuras simbólicas distintas. En su lugar, está gobernada por la profundidad $d$ y las constantes de Lipschitz de los operadores.
2. Cotas de Complejidad Explícitas: Los autores derivan una cota superior concreta para la complejidad de Rademacher:
   $$R_n(H^d_{comp}) \leq (K \cdot b \sqrt{2} L)^{d-1} R_n(H^1_{comp})$$
   Consecuentemente, el exceso de riesgo escala como $O(L^d / \sqrt{n})$ cuando el tamaño del vocabulario $K$ y la aridad $b$ se tratan como constantes. Esto contrasta con las cotas que dependen de la cardinalidad del espacio de sintaxis discreta.
3. Separación de Búsqueda y Estimación: El trabajo separa formalmente el problema de optimización discreta (la búsqueda de la estructura del árbol) del problema de regresión continua (el ajuste de coeficientes). Las cotas derivadas se aplican a este último, aclarando la escala estadística que se debe esperar una vez propuesta una estructura.
4. Correlación Empírica: Los experimentos demuestran una correlación positiva entre la brecha de generalización observada y el término de complejidad teórica $(bL^d)/\sqrt{n}$. Los datos muestran que, si bien la brecha aumenta con la profundidad (debido a la acumulación de las constantes de Lipschitz) y disminuye con el tamaño de la muestra ($1/\sqrt{n}$), la escala se alinea con la predicción teórica.

Resultados

• Teóricos: El Teorema 4.9 establece que para salidas acotadas y operadores Lipschitz, el exceso de riesgo decae como $1/\sqrt{n}$, con el factor constante dependiendo exponencialmente de la profundidad mediante el producto de las constantes de Lipschitz. El Corolario 4.11 traduce esto en una cota de complejidad de muestreo PAC, mostrando que la complejidad de muestreo escala con $L^{2d}$ en lugar del conteo combinatorio de árboles.
• Empíricos: A través de 400 ejecuciones experimentales variando la profundidad ($d$) y el tamaño de la muestra ($n$), se encontró que la brecha de generalización sigue el término teórico.
  • Para profundidades bajas ($d=1, 2$), el proxy de Lipschitz $\hat{L}$ se mantuvo estable, y la brecha escaló principalmente con $1/\sqrt{n}$.
  • Para composiciones más profundas ($d=3, 4$) que involucran no linealidades como $\exp$, $\hat{L}$ aumentó, provocando brechas mayores, lo cual es consistente con la acumulación multiplicativa de las constantes de estabilidad.
  • Un ajuste de ley de potencia en escalas log-log produjo una correlación de 0.48, lo que indica que el término de complejidad composicional captura una fracción significativa de la varianza en las brechas de generalización, aunque otros factores (error de optimización, ruido) también desempeñan un papel.

Significancia y Reivindicaciones
El artículo afirma proporcionar un "certificado de aprendibilidad" para el descubrimiento científico mediante la regresión simbólica. Su principal significancia radica en cambiar la perspectiva de la explosión combinatoria de las estructuras simbólicas hacia la estabilidad composicional de los operadores.

• Viabilidad del Descubrimiento con Pocos Datos: Los autores argumentan que, para vocabularios de operadores estables y profundidades modestas, el descubrimiento científico a partir de conjuntos de datos pequeños es estadísticamente factible. La generalización estadística no es el cuello de botella; el desafío sigue siendo la búsqueda computacional de estructuras y el diseño de sesgos inductivos.
• Clarificación de la Escala: El trabajo clarifica que la escala estadística de la estimación de coeficientes no lineales está determinada por la acumulación de las constantes de Lipschitz a lo largo del grafo de computación, no por la enumeración de posibles formas de árboles.
• Limitaciones: Los autores señalan modestamente que sus garantías son cotas uniformes y no aprovechan los sesgos estructurales (como la Navaja de Occam) tan eficazmente como podrían hacerlo los enfoques PAC-Bayes. Además, la validación empírica se basa en datos sintéticos controlados, in-distribución, con entradas unidimensionales; el comportamiento bajo un cambio de distribución o de especificación no está garantizado por estas cotas. El estimador $\hat{L}$ mide la estabilidad en el mapa ajustado en lugar de certificar una constante global de caso peor.

En conclusión, el artículo sostiene que los modelos de regresión simbólica, cuando se ven como árboles de funciones composicionales con primitivas estables, poseen propiedades estadísticas favorables que permiten la generalización incluso con datos limitados, siempre que la profundidad y la estabilidad de los operadores sean gestionadas.