Expressivity of Shallow Neural Networks Over Finite Fields

Resumen Técnico: Expresividad de Redes Neuronales Superficiales sobre Campos Finitos

Planteamiento del Problema
Este trabajo investiga la expresividad de redes neuronales polinómicas superficiales (PNN, por sus siglas en inglés) con funciones de activación monómicas $\sigma(x) = x^r$ sobre campos finitos $\mathbb{F}_q$. Mientras que la expresividad de las redes neuronales se estudia tradicionalmente mediante métodos estadísticos o sobre campos reales/complejos, este artículo aborda la expresividad algebraica en el contexto de los campos finitos. Esto está motivado por las ventajas prácticas de la cuantización de pesos (reducción de energía y almacenamiento) y la conexión teórica entre el conteo de puntos racionales sobre campos finitos y las conjeturas de Weil, que se relacionan con la estructura motivica de las variedades complejas.

El problema central es cuantificar la "capacidad expresiva aritmética" de una arquitectura de red. A diferencia de los campos continuos donde la expresividad se mide a menudo mediante la dimensión o la densidad de Zariski, los autores definen la expresividad sobre campos finitos a través de la cardinalidad del neuromanifold (neuromanifold)—la imagen del mapa de parámetros desde los pesos de la red hacia el espacio de las funciones polinómicas representables.

Metodología
Los autores adoptan un enfoque algebro-geométrico, tratando la salida de la red como elementos de un anillo polinómico en lugar de solo funciones.

1. Formalismo: Una red superficial con una arquitectura $\mathbf{d}=(n, m, k)$ y grado de activación $r$ mapea las entradas $\mathbf{x} \in \mathbb{F}_q^n$ a salidas en $(\mathbb{F}_q[x_1, \dots, x_n])^k$. La salida es una $k$-tupla de polinomios homogéneos de grado $r$.
2. Definición de Neuromanifold: El neuromanifold $\mathcal{P}_{\mathbf{d}, r}$ se define como la imagen del mapa de parámetros $\Psi_{\mathbf{d}, r}$ desde el espacio de pesos $\mathbb{F}_q^{m(n+k)}$ hacia el producto de los espacios de polinomios homogéneos $(S_r(\mathbb{F}_q^n))^k$.
3. Estrategia de Conteo: Dado que el espacio ambiente es finito, la expresividad se mide por la cardinalidad $|\mathcal{P}_{\mathbf{d}, r}|$. Los autores utilizan:
   • Teoremas de Congruencia Multinomial: Para determinar qué coeficientes monómicos se anulan módulo la característica $p$ del campo.
   • Descomposición Tensorial: Relacionando las salidas de la red con las descomposiciones de tensores simétricos (específicamente el rango CP y la diagonalización simultánea).
   • Conteo Combinatorio: Utilizando fórmulas para el número de matrices de un rango dado sobre campos finitos (MacWilliams, 1969) y coeficientes binomiales $q$.
   • Geometría Proyectiva: Analizando la estructura del neuromanifold en el espacio proyectivo para manejar la invarianza de escala.

Contribuciones Clave y Resultados

1. Límites Superiores Generales
El artículo establece un límite superior general sobre la cardinalidad del neuromanifold basado en la expansión en base-$p$ del grado de activación. Si $r = \sum r_t p^t$, el número de coeficientes monómicos no nulos es $\gamma_{n,p}(r) = \prod \binom{r_t+n-1}{r_t}$. En consecuencia, la cardinalidad está acotada por:
$$|\mathcal{P}_{\mathbf{d}, r}| \leq q^{\gamma_{n,p}(r) \cdot k}$$
Este límite surge porque los coeficientes multinomiales se anulan módulo $p$ para ciertas tuplas de exponentes, reduciendo la dimensión efectiva del espacio representable.

2. Cardinalidades Exactas para Arquitecturas Específicas
Los autores derivan fórmulas exactas para varias arquitecturas:

• Salida Única ($k=1$) con Activación Cuadrática ($r=2, p \neq 2$): El neuromanifold corresponde al conjunto de matrices simétricas $n \times n$ de rango $\leq m$. La cardinalidad es la suma del número de matrices simétricas de rango $j$ para $0 \leq j \leq m$, utilizando la fórmula de MacWilliams.
• Múltiples Salidas ($k>1$) con $r=2$: Los autores analizan el caso $\mathbf{d}=(n, n, 2)$. Demuestran un contraste marcado entre los campos finitos y complejos. Sobre $\mathbb{C}$, el neuromanifold es denso en el sentido de Zariski (llenando el espacio). Sobre $\mathbb{F}_q$, la capacidad expresiva aritmética se aproxima a $1/2$ cuando $q \to \infty$. Esto está vinculado al problema de la diagonalización simultánea de matrices simétricas mediante congruencia (SDC), que falla para una fracción no despreciable de pares sobre campos finitos.
• Arquitecturas con $m=1$ y $m=2$:
  • Para $m=1$, la cardinalidad se deriva mediante un producto de espacios proyectivos: $|\mathcal{P}_{\mathbf{d}, r}| = |\mathcal{P}_{(n,1,1), r}| \cdot |\mathbb{P}^{k-1}|$.
  • Para $m=2$, los autores particionan el espacio basándose en la dimensión del span de los tensores de salida. Proporcionan fórmulas distintas para $r > 1$ y $r=1$, señalando que para $r=1$, las combinaciones lineales de tensores de rango 1 permanecen de rango 1, lo que complica el conteo debido a pares de bases no únicos.

3. Divisibilidad de la Característica ($p \mid r$)
Un resultado teórico significativo es la reducción de los grados de activación divisibles por la característica. Si $r = i \cdot p$, la cardinalidad del neuromanifold es idéntica a la de la red con grado de activación $i$:
$$|\mathcal{P}_{\mathbf{d}, ip}| = |\mathbf{\mathcal{P}}_{\mathbf{d}, i}|$$
Esto se demuestra utilizando la identidad $(a+b)^p \equiv a^p + b^p$ en la característica $p$ y el hecho de que los campos finitos son perfectos. Esto permite la reducción de casos complejos a otros más simples.

• Caso Especial ($r=p$): Cuando $r=p$, el neuromanifold corresponde exactamente al conjunto de matrices $k \times n$ de rango a lo sumo $m$.

4. Diferencias Estructurales: Campos Finitos vs. Complejos
El artículo destaca que el comportamiento de los neuromanifolds sobre campos finitos puede diferir drásticamente de sus contrapartes complejos, incluso para arquitecturas pequeñas.

• Ejemplo: Para $\mathbf{d}=(2, 2, 2)$ con $r=2$, el neuromanifold sobre $\mathbb{C}$ es abierto en el sentido de Zariski (llenando el espacio), mientras que sobre $\mathbb{F}_q$, ocupa solo aproximadamente la mitad del espacio ambiente.
• Implicación: Las propiedades como el "llenado" (suryectividad sobre el espacio ambiente) no están garantizadas sobre campos finitos incluso cuando se cumplen sobre $\mathbb{C}$.

Significancia y Reivindicaciones
Los autores afirman que este trabajo proporciona un marco algebraico fundacional para comprender la expresividad de las redes neuronales cuantizadas. Al cambiar el enfoque de la aproximación de funciones al conteo de la cardinalidad de la imagen del mapa de parámetros, revelan las restricciones estructurales impuestas por la característica del campo.

El artículo sostiene que:

1. La Característica del Campo es Crítica: La característica del campo juega un papel decisivo en la expresividad, reduciendo a menudo la capacidad de la red en comparación con los campos de característica cero.
2. Conexión con la Matemática Profunda: El problema de contar estos manifolds está intrínsecamente ligado a las conjeturas de Weil y al estudio de los puntos racionales, ofreciendo un puente entre la teoría de redes neuronales y la geometría aritmética.
3. Limitaciones de la Teoría Actual: Los resultados sugieren que la intuición derivada de redes con valores reales o complejos (por ejemplo, la densidad de Zariski) puede no transferirse a los campos finitos, lo que requiere herramientas combinatorias y algebraicas específicas para arquitecturas cuantizadas.

El artículo concluye identificando problemas abiertos, tales como encontrar arquitecturas donde la capacidad expresiva converja a una fracción no nula $0 < a/b < 1$ y resolver el problema de la diagonalización simultánea para tensores simétricos sobre campos finitos. No propone nuevos algoritmos de entrenamiento ni evaluaciones experimentales, centrándose en los límites teóricos de la representabilidad.