Expressivity of Shallow Neural Networks Over Finite Fields

Résumé Technique : Expressivité des Réseaux de Neurones Faibles sur les Corps Finis

Énoncé du Problème
Ce travail étudie l'expressivité des réseaux de neurones polynomiaux peu profonds (PNN) avec des fonctions d'activation monomials $\sigma(x) = x^r$ sur les corps finis $\mathbb{F}_q$. Alors que l'expressivité des réseaux de neurones est traditionnellement étudiée via des méthodes statistiques ou sur les corps réels/complexes, cet article traite de l'expressivité algébrique dans le contexte des corps finis. Cela est motivé par les avantages pratiques de la quantification des poids (réduction de l'énergie et du stockage) et par le lien théorique entre le comptage des points rationnels sur les corps finis et les conjectures de Weil, qui sont liées à la structure motivique des variétés complexes.

Le problème central est de quantifier la « capacité expressive arithmétique » d'une architecture de réseau. Contrairement aux corps continus où l'expressivité est souvent mesurée par la dimension ou la densité de Zariski, les auteurs définissent l'expressivité sur les corps finis via la cardinalité de la neuromanifold (neurovariété) — l'image de l'application de paramétrage des poids du réseau vers l'espace des fonctions polynomiales représentables.

Méthodologie
Les auteurs adoptent une approche algébrico-géométrique, traitant la sortie du réseau comme des éléments d'un anneau polynomial plutôt que comme de simples fonctions.

1. Formalisme : Un réseau peu profond avec une architecture $\mathbf{d}=(n, m, k)$ et un degré d'activation $r$ projette les entrées $\mathbf{x} \in \mathbb{F}_q^n$ vers des sorties dans $(\mathbb{F}_q[x_1, \dots, x_n])^k$. La sortie est un $k$-uplet de polynômes homogènes de degré $r$.
2. Définition de la Neuromanifold : La neuromanifold $\mathcal{P}_{\mathbf{d}, r}$ est définie comme l'image de l'application de paramétrage $\Psi_{\mathbf{d}, r}$ de l'espace des poids $\mathbb{F}_q^{m(n+k)}$ vers le produit des espaces de polynômes homogènes $(S_r(\mathbb{F}_q^n))^k$.
3. Stratégie de Comptage : Puisque l'espace ambiant est fini, l'expressivité est mesurée par la cardinalité $|\mathcal{P}_{\mathbf{d}, r}|$. Les auteurs utilisent :
   • Théorèmes de Congruence Multinomiale : Pour déterminer quels coefficients monomiaux s'annulent modulo la caractéristique $p$ du corps.
   • Décomposition Tensorielle : En reliant les sorties du réseau aux décompositions de tenseurs symétriques (spécifiquement le rang CP et la diagonalisation simultanée).
   • Comptage Combinatoire : En utilisant des formules pour le nombre de matrices de rang donné sur des corps finis (MacWilliams, 1969) et les coefficients $q$-binomiaux.
   • Géométrie Projective : En analysant la structure de la neuromanifold dans l'espace projectif pour gérer l'invariance par mise à l'échelle.

Contributions Clés et Résultats

1. Bornes Supérieures Générales
L'article établit une borne supérieure générale sur la cardinalité de la neuromanifold basée sur l'expansion en base-$p$ du degré d'activation $r$. Si $r = \sum r_t p^t$, le nombre de coefficients monomiaux non nuls est $\gamma_{n,p}(r) = \prod \binom{r_t+n-1}{r_t}$. Par conséquent, la cardinalité est bornée par :
$$|\mathcal{P}_{\mathbf{d}, r}| \leq q^{\gamma_{n,p}(r) \cdot k}$$
Cette borne découle du fait que les coefficients multinomiaux s'annulent modulo $p$ pour certains tuples d'exposants, réduisant la dimension effective de l'espace représentable.

2. Cardinalités Exactes pour des Architectures Spécifiques
Les auteurs dérivent des formules exactes pour plusieurs architectures :

• Sortie Unique ($k=1$) avec Activation Carrée ($r=2, p \neq 2$) : La neuromanifold correspond à l'ensemble des matrices symétriques $n \times n$ de rang $\leq m$. La cardinalité est la somme du nombre de matrices symétriques de rang $j$ pour $0 \leq j \leq m$, en utilisant la formule de MacWilliams.
• Sorties Multiples ($k>1$) avec $r=2$ : Les auteurs analysent le cas $\mathbf{d}=(n, n, 2)$. Ils démontrent un contraste frappant entre les corps finis et complexes. Sur $\mathbb{C}$, la neuromanifold est Zariski dense (remplit l'espace). Sur $\mathbb{F}_q$, la capacité expressive arithmétique approche $1/2$ quand $q \to \infty$. Ceci est lié au problème de la diagonalisation simultanée de matrices symétriques par congruence (SDC), qui échoue pour une fraction non négligeable de paires sur les corps finis.
• Architectures avec $m=1$ et $m=2$ :
  • Pour $m=1$, la cardinalité est dérivée via un produit d'espaces projectifs : $|\mathcal{P}_{\mathbf{d}, r}| = |\mathcal{P}_{(n,1,1), r}| \cdot |\mathbb{P}^{k-1}|$.
  • Pour $m=2$, les auteurs partitionnent l'espace en fonction de la dimension de l'espace engendré par les tenseurs de sortie. Ils fournissent des formules distinctes pour $r > 1$ et $r=1$, notant que pour $r=1$, les combinaisons linéaires de tenseurs de rang 1 restent de rang 1, ce qui complique le comptage en raison de la non-unicité des paires de bases.

3. Divisibilité par la Caractéristique ($p \mid r$)
Un résultat théorique important est la réduction des degrés d'activation divisibles par la caractéristique. Si $r = i \cdot p$, la cardinalité de la neuromanifold est identique à celle du réseau avec le degré d'activation $i$ :
$$|\mathcal{P}_{\mathbf{d}, ip}| = |\mathbf{\mathcal{P}}_{\mathbf{d}, i}|$$
Ceci est prouvé en utilisant l'identité $(a+b)^p \equiv a^p + b^p$ dans une caractéristique $p$ et le fait que les corps finis sont parfaits. Cela permet de réduire les cas complexes à des cas plus simples.

• Cas Particulier ($r=p$) : Quand $r=p$, la neuromanifold correspond exactement à l'ensemble des matrices $k \times n$ de rang au plus $m$.

4. Différences Structurelles : Corps Finis vs Complexes
L'article souligne que le comportement des neuromanifolds sur les corps finis peut différer radicalement de leurs homologues complexes, même pour de petites architectures.

• Exemple : Pour $\mathbf{d}=(2, 2, 2)$ avec $r=2$, la neuromanifold sur $\mathbb{C}$ est un ouvert de Zariski (remplit l'espace), tandis que sur $\mathbb{F}_q$, elle n'occupe qu'environ la moitié de l'espace ambiant.
• Implication : Des propriétés telles que le fait de « remplir » (surjectivité sur l'espace ambiant) ne sont pas garanties sur les corps finis, même lorsqu'elles sont vérifiées sur $\mathbb{C}$.

Signification et Revendications
Les auteurs affirment que ce travail fournit un cadre algébrique fondamental pour comprendre l'expressivité des réseaux de neurones quantifiés. En déplaçant l'attention de l'approximation de fonctions vers la cardinalité de l'image de l'application de paramétrage, ils révèlent les contraintes structurelles imposées par la caractéristique du corps.

L'article soutient que :

1. La Caractéristique du Corps est Critique : La caractéristique du corps joue un rôle décisif dans l'expressivité, réduisant souvent la capacité du réseau par rapport aux champs de caractéristique zéro.
2. Connexion avec les Mathématiques Profondes : Le problème du comptage de ces variétés est intrinsèquement lié aux conjectures de Weil et à l'étude des points rationnels, offrant un pont entre la théorie des réseaux de neurones et la géométrie arithmétique.
3. Limites de la Théorie Actuelle : Les résultats suggèrent que l'intuition dérivée des réseaux à valeurs réelles ou complexes (par exemple, concernant la densité de Zariski) ne se transfère pas nécessairement aux corps finis, nécessant des outils combinatoires et algébriques spécifiques pour les architectures quantifiées.

L'article conclut en identifiant des problèmes ouverts, tels que la recherche d'architectures où la capacité expressive converge vers une fraction non nulle $0 < a/b < 1$ et la résolution du problème de la diagonalisation simultanée pour les tenseurs symétriques sur les corps finis. Il ne propose pas de nouveaux algorithmes d'entraînement ou de bancs d'essai expérimentaux, se concentrant sur les limites théoriques de la représentabilité.