Expressivity of Shallow Neural Networks Over Finite Fields

Sintesi Tecnica: Espressività di Reti Neurali Superficiali su Campi Finiti

Enunciato del Problema
Questo lavoro investiga l'espressività di reti neurali polinomiali superficiali (PNN) con funzioni di attivazione monomiali $\sigma(x) = x^r$ su campi finiti $\mathbb{F}_q$. Sebbene l'espressività delle reti neurali sia tradizionalmente studiata tramite metodi statistici o su campi reali/complessi, questo articolo affronta l'espressività algebrica nel contesto dei campi finiti. Ciò è motivato dai vantaggi pratici della quantizzazione dei pesi (riduzione di energia e memoria) e dalla connessione teorica tra il conteggio dei punti razionali su campi finiti e le congetture di Weil, che si relazionano alla struttura motivica delle varietà complesse.

Il problema centrale è quantificare la "capacità espressiva aritmetica" di un'architettura di rete. A differenza dei campi continui dove l'espressività è spesso misurata tramite la dimensione o la densità di Zariski, gli autori definiscono l'espressività su campi finiti tramite la cardinalità del neuromanifold (neuromanifold) — ovvero l'immagine della mappa dei parametri dai pesi della rete allo spazio delle funzioni polinomiali rappresentabili.

Metodologia
Gli autori adottano un approccio algebro-geometrico, trattando l'output della rete come elementi di un anello polinomiale piuttosto che come semplici funzioni.

1. Formalismo: Una rete neurale superficiale con architettura $\mathbf{d}=(n, m, k)$ e grado di attivazione $r$ mappa gli input $\mathbf{x} \in \mathbb{F}_q^n$ in output in $(\mathbb{F}_q[x_1, \dots, x_n])^k$. L'output è una $k$-upla di polinomi omogenei di grado $r$.
2. Definizione di Neuromanifold: Il neuromanifold $\mathcal{P}_{\mathbf{d}, r}$ è definito come l'immagine della mappa dei parametri $\Psi_{\mathbf{d}, r}$ dallo spazio dei pesi $\mathbb{F}_q^{m(n+k)}$ al prodotto degli spazi di polinomi omogenei $(S_r(\mathbb{F}_q^n))^k$.
3. Strategia di Conteggio: Poiché lo spazio ambiente è finito, l'espressività è misurata tramite la cardinalità $|\mathcal{P}_{\mathbf{d}, r}|$. Gli autori utilizzano:
   • Teoremi di Congruenza Multinomiale: Per determinare quali coefficienti monomiali si annullano modulo la caratteristica $p$ del campo.
   • Decomposizione Tensoriale: Relazionare gli output della rete alle decomposizioni di tensori simmetrici (specificamente al rango CP e alla diagonalizzazione simultanea).
   • Conteggio Combinatorio: Utilizzando formule per il numero di matrici di un dato rango su campi finiti (MacWilliams, 1969) e coefficienti binomiali $q$.
   • Geometria Proiettiva: Analizzare la struttura del neuromanifold nello spazio proiettivo per gestire l'invarianza di scala.

Contributi Chiave e Risultati

1. Limiti Superiori Generali
L'articolo stabilisce un limite superiore generale sulla cardinalità del neuromanifold basato sull'espansione in base-$p$ del grado di attivazione $r$. Se $r = \sum r_t p^t$, il numero di coefficienti monomiali non nulli è $\gamma_{n,p}(r) = \prod \binom{r_t+n-1}{r_t}$. Di conseguenza, la cardinalità è limitata da:
$$|\mathcal{P}_{\mathbf{d}, r}| \leq q^{\gamma_{n,p}(r) \cdot k}$$
Questo limite deriva dal fatto che i coefficienti multinomiali si annullano modulo $p$ per determinati tuple di esponenti, riducendo la dimensione effettiva dello spazio rappresentabile.

2. Cardinalità Esatte per Architetture Specifiche
Gli autori derivano formule esatte per diverse architetture:

• Output Singolo ($k=1$) con Attivazione Quadrata ($r=2, p \neq 2$): Il neuromanifold corrisponde all'insieme delle matrici simmetriche $n \times n$ di rango $\leq m$. La cardinalità è la somma del numero di matrici simmetriche di rango $j$ per $0 \leq j \leq m$, utilizzando la formula di MacWilliams.
• Output Multipli ($k>1$) con $r=2$: Gli autori analizzano il caso $\mathbf{d}=(n, n, 2)$. Dimostrano un netto contrasto tra campi finiti e complessi. Su $\mathbb{C}$, il neuromanifold è denso rispetto a Zariski (riempie lo spazio). Su $\mathbb{F}_q$, la capacità espressiva aritmetica si avvicina a $1/2$ quando $q \to \infty$. Ciò è legato al problema della diagonalizzazione simultanea di matrici simmetriche tramite congruenza (SDC), che fallisce per una frazione non trascurabile di coppie su campi finiti.
• Architetture con $m=1$ e $m=2$:
  • Per $m=1$, la cardinalità è derivata tramite un prodotto di spazi proiettivi: $|\mathcal{P}_{\mathbf{d}, r}| = |\mathcal{P}_{(n,1,1), r}| \cdot |\mathbb{P}^{k-1}|$.
  • Per $m=2$, gli autori partizionano lo spazio in base alla dimensione dello span dei tensori di output. Forniscono formule distinte per $r > 1$ e $r=1$, notando che per $r=1$, le combinazioni lineari di tensori di rango-1 rimangono di rango-1, complicando il conteggio a causa della non unicità delle coppie di basi.

3. Divisibilità della Caratteristica ($p \mid r$)
Un risultato teorico significativo è la riduzione dei gradi di attivazione divisibili per la caratteristica. Se $r = i \cdot p$, la cardinalità del neuromanifold è identica a quella della rete con grado di attivazione $i$:
$$|\mathcal{P}_{\mathbf{d}, ip}| = |\mathbf{\mathcal{P}}_{\mathbf{d}, i}|$$
Questo è dimostrato utilizzando l'identità $(a+b)^p \equiv a^p + b^p$ in caratteristica $p$ e il fatto che i campi finiti sono perfetti. Ciò permette di ridurre i casi complessi a casi più semplici.

• Caso Speciale ($r=p$): Quando $r=p$, il neuromanifold corrisponde esattamente all'insieme delle matrici $k \times n$ di rango al massimo $m$.

4. Differenze Strutturali: Campi Finiti vs. Complessi
L'articolo evidenzia come il comportamento dei neuromanifold su campi finiti possa differire drasticamente dai loro controparti complessi, anche per architetture piccole.

• Esempio: Per $\mathbf{d}=(2, 2, 2)$ con $r=2$, il neuromanifold su $\mathbb{C}$ è un insieme Zariski aperto (riempie lo spazio), mentre su $\mathbb{F}_q$ occupa solo circa la metà dello spazio ambiente.
• Implicazione: Proprietà come il "riempimento" (suriettività sullo spazio ambiente) non sono garantite su campi finiti, anche quando valgono su $\mathbb{C}$.

Significato e Rivendicazioni
Gli autori affermano che questo lavoro fornisce un quadro algebrico fondamentale per comprendere l'espressività delle reti neurali quantizzate. Spostando l'attenzione dall'approssimazione di funzioni alla cardinalità dell'immagine della mappa dei parametri, essi rivelano i vincoli strutturali imposti dalla caratteristica del campo.

L'articolo asserisce che:

1. La Caratteristica del Campo è Critica: La caratteristica del campo gioca un ruolo decisivo nell'espressività, riducendo spesso la capacità della rete rispetto ai campi a caratteristica zero.
2. Connessione con la Matematica Profonda: Il problema del conteggio di questi manifold è intrinsecamente legato alle congetture di Weil e allo studio dei punti razionali, offrendo un ponte tra la teoria delle reti neurali e la geometria aritmetica.
3. Limiti della Teoria Corrente: I risultati suggeriscono che l'intuizione derivata da reti con valori complessi o reali (ad esempio, la densità di Zariski) potrebbe non trasferirsi ai campi finiti, richiedendo strumenti combinatori e algebrici specifici per le architetture quantizzate.

L'articolo conclude identificando problemi aperti, come la ricerca di architetture in cui la capacità espressiva converga a una frazione non nulla $0 < a/b < 1$ e la risoluzione del problema della diagonalizzazione simultanea per tensori simmetrici su campi finiti. Non propone nuovi algoritmi di addestramento o benchmark sperimentali, concentrandosi invece sui limiti teorici della rappresentabilità.