Tubular Neighbourhoods of Pfaffian Sets and Applications to Neural Networks

Résumé technique : Voisinages tubulaires des ensembles pfaffiens et applications aux réseaux de neurones

Énoncé du problème
L'article traite de la complexité géométrique des frontières de décision des classifieurs de réseaux de neurones, spécifiquement ceux employant des fonctions d'activation lisses et transcendantes (par exemple, la sigmoïde logistique, tanh). Un problème central dans l'analyse de la robustesse de ces classifieurs consiste à quantifier la probabilité qu'une entrée aléatoire se situe dans un voisinage tubulaire de rayon $\varepsilon$ de la frontière de décision. Cette probabilité se traduit directement par des bornes de queue sur le nombre de conditionnement du classifieur, une mesure de robustesse définie comme le rapport de la norme de l'entrée sur la distance jusqu'à la classification erronée.

Bien que les bornes de volume pour les voisinages tubulaires des variétés algébriques soient bien établies (par exemple, la formule du tube de Weyl, les résultats de Smale, Renegar et Basu-Lerario), l'extension de celles-ci aux réseaux de neurones avec des activations transcendantes est non triviale. Les outils algébriques standards comme le théorème de Bézout sont insuffisants. Au lieu de cela, les auteurs utilisent la théorie des fonctions pfaffiennes, qui généralisent les ensembles semi-algébriques pour inclure des fonctions satisfaisant des systèmes triangulaires d'équations aux dérivées partielles du premier ordre à coefficients polynomiaux. Un défi primaire identifié est que l'application des bornes pfaffiennes générales (basées sur la théorie des peu de monomials de Khovanskii) aux réseaux de neurones produit des constantes dépendant exponentiellement de la largeur du réseau, ce qui rend les bornes pratiquement et théoriquement sous-optimales.

Méthodologie
Les auteurs développent un cadre combinant la géométrie intégrale, la géométrie o-minimale et la combinatoire algébrique :

1. Formule du tube pfaffien : Les auteurs dérivent une borne pour le volume du voisinage tubulaire d'une hypersurface pfaffienne lisse. Ceci est réalisé en combinant une variante de la formule du tube de Weyl avec des bornes sur le degré de la carte de Gauss généralisée. Le degré de la carte de Gauss est borné en utilisant le théorème de Khovanskii, qui limite le nombre de solutions à un système d'équations pfaffiennes en fonction du « format » $(\alpha, \beta, s)$ des fonctions définissantes (degré de la chaîne, degré de la fonction et ordre de la chaîne).
2. Réseau de neurones comme fonctions pfaffiennes : L'article établit que les réseaux de neurones avec des activations pfaffiennes lisses et autonomes sont eux-mêmes des fonctions pfaffiennes. Le format du réseau est dérivé de manière inductive en fonction de la profondeur, de la largeur et du format des fonctions d'activation.
3. Bornes polynomiales pour les réseaux à une couche : Pour surmonter la dépendance exponentielle vis-à-vis de la largeur inhérente aux bornes de Khovanskii générales, les auteurs se concentrent sur des réseaux sigmoïdes à une seule couche cachée avec des poids rationnels. Ils emploient un changement de variables (substitution exponentielle) pour transformer le système de la carte de Gauss en un système de polynômes de Laurent. En appliquant le théorème de Bernstein-Kushnirenko-Khovanskii (BKK), ils bornent le nombre de solutions par le volume mixte des polytopes de Newton. Crucialement, ils montrent que pour les poids rationnels, la structure de réseau permet d'obtenir une borne qui est polynomiale en la largeur du réseau $w$, spécifiquement de l'ordre $O(w^n)$.
4. Gestion des sections affines : Pour la formule du tube complète, des bornes sont requises pour les intersections avec des sous-espaces affines de diverses dimensions. Les auteurs montrent que si les sections génériques détruisent la structure de réseau rationnel requise pour l'approche BKK, une transformation de carte multiplicative permet de traiter le système comme un système pfaffien avec une longueur de chaîne indépendante de la largeur, produisant une borne polynomiale $O(w^{2n})$ pour tous les degrés de section.

Contributions clés et résultats

• Bornes de tube générales pour les hypersurfaces pfaffiennes (Théorème 3.6) : Les auteurs établissent une borne de volume pour le voisinage tubulaire d'une hypersurface pfaffienne lisse et bornée $V = Z(f)$. Pour un point $X$ uniformément distribué dans une boule $B(p, \rho)$, la probabilité que $X$ se situe à une distance $\varepsilon$ de $V$ est bornée par :
  $$P\{d(X, V) \le \varepsilon\} \le C_{\alpha,\beta,s,n} \left[ \left(1 + \frac{(\alpha+\beta+1)\varepsilon}{\rho}\right)^n - \left(1 + \frac{\varepsilon}{\rho}\right)^n \right]$$
  où la constante $C$ dépend du format pfaffien. Ceci généralise les résultats précédents pour les variétés algébriques.

• Garanties de robustesse pour les réseaux pfaffiens généraux (Théorème 5.4, Corollaire 5.7) : En appliquant la formule du tube aux réseaux de neurones, les auteurs dérivent des bornes de queue pour le nombre de conditionnement $C(X)$. Pour les réseaux avec $\ell$ couches cachées et $h$ unités totales, la probabilité de queue décroît comme $O(1/t)$. Cependant, la constante implique un facteur exponentiel $2^{h(h-1)/2}$ provenant de la borne standard de Khovanskii sur la longueur de la chaîne.

• Bornes polynomiales en largeur pour les réseaux sigmoïdes à une couche (Théorème 4.15, Corollaire 5.8) : Pour les réseaux à une seule couche cachée avec des poids rationnels, les auteurs éliminent le facteur exponentiel de Khovanskii. Ils prouvent que le degré maximal de la carte de Gauss est borné par $C(n, L) \cdot w^n$ (et les degrés de section par $w^{2n}$), où $L$ est une constante de réseau liée aux poids. Par conséquent, la borne de queue pour le nombre de conditionnement devient polynomiale en la largeur $w$ :
  $$P\{C_p(X) > t\} \le O\left(\frac{w^n}{t}\right)$$
  Il est démontré que ce résultat est précis dans sa dépendance vis-à-vis de $w$ via une borne inférieure constructive (Proposition 4.11).

• Réglages Gaussien vs Uniforme : L'article fournit des bornes de queue pour les distributions uniformes sur une boule et pour les perturbations gaussiennes. Pour le cas gaussien, les auteurs notent que bien que la borne polynomiale soit valable pour la partie « grand rayon » de l'intégrale, la partie « petit rayon » repose toujours sur la borne pfaffienne générale, conduisant à une borne hybride où le facteur exponentiel peut dominer à moins que des conditions de concentration spécifiques ne soient remplies (Remarque 5.11).

Signification et revendications
L'article prétend fournir les premières garanties de robustesse quantitatives et effectives pour les réseaux de neurones avec des activations transcendantes qui ne sont pas simplement exponentielles en la taille du réseau. En généralisant la théorie des voisinages tubulaires au cadre pfaffien, les auteurs comblent le fossé entre la théorie classique du conditionnement en analyse numérique et l'apprentissage profond moderne.

La signification primaire réside dans l'affinement des bornes pour les réseaux à une couche. Les auteurs démontent que l'application « prête à l'emploi » du théorème de Khovanskii produit des bornes exponentielles trop pessimistes, tandis qu'exploiter la structure spécifique des poids rationnels et l'architecture à une couche permet d'obtenir des bornes polynomiales. Cela suggère que la complexité géométrique des frontières de décision dans les réseaux peu profonds est nettement plus faible que ce que la théorie générale des peu de monomials implique.

Les auteurs restent modestes concernant les réseaux multicouches. Ils déclarent explicitement que la borne polynomiale en largeur pour les réseaux à une couche ne s'étend pas automatiquement aux réseaux plus profonds en raison de l'« obstruction de Rolle stratifiée » et de l'absence d'un lemme de Rolle multidimensionnel pour les chaînes stratifiées. Ils proposent la Conjecture 6.1 (Borne de Khovanskii par blocs) et la Conjecture 4.13, suggérant que des bornes entièrement polynomiales pourraient exister pour les réseaux multicouches, mais que prouver cela nécessite de nouveaux outils au-delà de l'application séquentielle actuelle du théorème de Khovanskii. De plus, l'article note que les résultats actuels nécessitent la régularité (gradients non nuls), et l'extension de ces bornes aux frontières de décision singulières (communes dans les réseaux ReLU ou des configurations de poids spécifiques) reste un problème ouvert en raison de l'absence d'outils analytiques complexes pour les fonctions pfaffiennes.