Expressivity of Shallow Neural Networks Over Finite Fields

Resumo Técnico: Expressividade de Redes Neurais Rasas sobre Campos Finitos

Definição do Problema
Este trabalho investiga a expressividade de redes neurais polinomiais rasas (PNNs) com funções de ativação de monômios $\sigma(x) = x^r$ sobre campos finitos $\mathbb{F}_q$. Embora a expressividade de redes neurais seja tradicionalmente estudada via métodos estatísticos ou sobre campos reais/complexos, este artigo aborda a expressividade algébrica no contexto de campos finitos. Isso é motivado pelas vantagens práticas da quantização de pesos (redução de energia e armazenamento) e pela conexão teórica entre a contagem de pontos racionais sobre campos finitos e as conjecturas de Weil, que se relacionam com a estrutura motivica de variedades complexas.

O problema central é quantificar a "capacidade expressiva aritmética" de uma arquitetura de rede. Diferente de campos contínuos onde a expressividade é frequentemente medida por dimensão ou densidade de Zariski, os autores definem a expressividade sobre campos finitos através da cardinalidade do neuromanifold — a imagem do mapa de parâmetros dos pesos da rede para o espaço de funções polinomiais representáveis.

Metodologia
Os autores adotam uma abordagem algebro-geométrica, tratando a saída da rede como elementos de um anel de polinômios em vez de apenas funções.

1. Formalismo: Uma rede rasa com arquitetura $\mathbf{d}=(n, m, k)$ e grau de ativação $r$ mapeia entradas $\mathbf{x} \in \mathbb{F}_q^n$ para saídas em $(\mathbb{F}_q[x_1, \dots, x_n])^k$. A saída é um $k$-tupla de polinômios homogêneos de grau $r$.
2. Definição de Neuromanifold: O neuromanifold $\mathcal{P}_{\mathbf{d}, r}$ é definido como a imagem do mapa de parâmetros $\Psi_{\mathbf{d}, r}$ do espaço de pesos $\mathbb{F}_q^{m(n+k)}$ para o produto de espaços de polinômios homogêneos $(S_r(\mathbb{F}_q^n))^k$.
3. Estratégia de Contagem: Como o espaço ambiente é finito, a expressividade é medida pela cardinalidade $|\mathcal{P}_{\mathbf{d}, r}|$. Os autores utilizam:
   • Teoremas de Congruência Multinomial: Para determinar quais coeficientes de monômios desaparecem módulo a característica $p$ do campo.
   • Decomposição de Tensores: Relacionando as saídas da rede a decomposições de tensores simétricos (especificamente rank-CP e diagonalização simultânea).
   • Contagem Combinatória: Usando fórmulas para o número de matrizes de um determinado rank sobre campos finitos (MacWilliams, 1969) e coeficientes $q$-binomiais.
   • Geometria Projetiva: Analisando a estrutura do neuromanifold no espaço projetivo para lidar com a invariância de escala.

Principais Contribuições e Resultados

1. Limites Superiores Gerais
O artigo estabelece um limite superior geral para a cardinalidade do neuromanifold baseado na expansão de base-$p$ do grau de ativação $r$. Se $r = \sum r_t p^t$, o número de coeficientes de monômios não nulos é $\gamma_{n,p}(r) = \prod \binom{r_t+n-1}{r_t}$. Consequentemente, a cardinalidade é limitada por:
$$|\mathcal{P}_{\mathbf{d}, r}| \leq q^{\gamma_{n,p}(r) \cdot k}$$
Este limite surge porque os coeficientes multinomiais desaparecem módulo $p$ para certas tuplas de expoentes, reduzindo a dimensão efetiva do espaço representável.

2. Cardinalidades Exatas para Arquiteturas Específicas
Os autores derivam fórmulas exatas para diversas arquiteturas:

• Saída Única ($k=1$) com Ativação Quadrática ($r=2, p \neq 2$): O neuromanifold corresponde ao conjunto de matrizes simétricas $n \times n$ de rank $\leq m$. A cardinalidade é a soma do número de matrizes simétricas de rank $j$ para $0 \leq j \leq m$, utilizando a fórmula de MacWilliams.
• Múltiplas Saídas ($k>1$) com $r=2$: Os autores analisam o caso $\mathbf{d}=(n, n, 2)$. Eles demonstram um contraste gritante entre campos finitos e complexos. Sobre $\mathbb{C}$, o neuromanifold é Zariski denso (preenchendo o espaço). Sobre $\mathbb{F}_q$, a capacidade expressiva aritmética aproxima-se de $1/2$ quando $q \to \infty$. Isso está ligado ao problema da diagonalização simultânea de matrizes simétricas via congruência (SDC), que falha para uma fração não negligenciável de pares sobre campos finitos.
• Arquiteturas com $m=1$ e $m=2$:
  • Para $m=1$, a cardinalidade é derivada via um produto de espaços projetivos: $|\mathcal{P}_{\mathbf{d}, r}| = |\mathcal{P}_{(n,1,1), r}| \cdot |\mathbb{P}^{k-1}|$.
  • Para $m=2$, os autores particionam o espaço com base na dimensão do span dos tensores de saída. Eles fornecem fórmulas distintas para $r > 1$ e $r=1$, observando que para $r=1$, combinações lineares de tensores de rank-1 permanecem rank-1, complicando a contagem devido à não unicidade dos pares de base.

3. Divisibilidade da Característica ($p \mid r$)
Um resultado teórico significativo é a redução de graus de ativação divisíveis pela característica. Se $r = i \cdot p$, a cardinalidade do neuromanifold é idêntica à da rede com grau de ativação $i$:
$$|\mathcal{P}_{\mathbf{d}, ip}| = |\mathbf{\mathcal{P}}_{\mathbf{d}, i}|$$
Isso é provado usando a identidade $(a+b)^p \equiv a^p + b^p$ em característica $p$ e o fato de que campos finitos são perfeitos. Isso permite a redução de casos complexos para casos mais simples.

• Caso Especial ($r=p$): Quando $r=p$, o neuromanifold corresponde exatamente ao conjunto de matrizes $k \times n$ de rank no máximo $m$.

4. Diferenças Estruturais: Campos Finitos vs. Complexos
O artigo destaca que o comportamento dos neuromanifolds sobre campos finitos pode diferir drasticamente de seus equivalentes complexos, mesmo para arquiteturas pequenas.

• Exemplo: Para $\mathbf{d}=(2, 2, 2)$ com $r=2$, o neuromanifold sobre $\mathbb{C}$ é Zariski aberto (preenchendo o espaço), enquanto sobre $\mathbb{F}_q$, ele ocupa apenas aproximadamente metade do espaço ambiente.
• Implicação: Propriedades como "preenchimento" (surjetividade sobre o espaço ambiente) não são garantidas sobre campos finitos, mesmo quando ocorrem sobre $\mathbb{C}$.

Significância e Alegações
Os autores afirmam que este trabalho fornece um arcabouço algébrico fundamental para entender a expressividade de redes neurais quantizadas. Ao mudar o foco da aproximação de funções para a cardinalidade da imagem do mapa de parâmetros, eles revelam restrições estruturais impostas pela característica do campo.

O artigo afirma que:

1. A Característica do Campo é Crítica: A característica do campo desempenha um papel decisivo na expressividade, frequentemente reduzindo a capacidade da rede em comparação com campos de característica zero.
2. Conexão com Matemática Profunda: O problema de contar esses manifolds está intrinsecamente ligado às conjecturas de Weil e ao estudo de pontos racionais, oferecendo uma ponte entre a teoria de redes neurais e a geometria aritmética.
3. Limitações da Teoria Atual: Os resultados sugerem que a intuição derivada de redes de valores reais ou complexos (ex: densidade de Zariski) pode não se transferir para campos finitos, necessitando de ferramentas combinatórias e algébricas específicas para arquiteturas quantizadas.

O artigo conclui identificando problemas abertos, como encontrar arquiteturas onde a capacidade expressiva converge para uma fração não nula $0 < a/b < 1$ e resolver o problema da diagonalização simultânea para tensores simétricos sobre campos finitos. Não se propõe novos algoritmos de treinamento ou benchmarks experimentais, focando nos limites teóricos de representabilidade.