Piecewise linear functions and neural network expressivity via discriminantal arrangements

1. Problématique et Contexte

L'expressivité des réseaux de neurones, en particulier ceux utilisant des fonctions d'activation ReLU, est un problème central à l'intersection de la combinatoire, de la géométrie et de l'apprentissage automatique. Il est bien établi que les fonctions représentables par ces réseaux correspondent exactement aux fonctions continues linéaires par morceaux (CPWL).

La recherche précédente a relié cette expressivité à la géométrie des arrangements d'hyperplans, où les régions de linéarité d'un réseau correspondent aux cellules d'une subdivision polyédrale. Une approche particulièrement fructueuse a utilisé l'arrangement de tresses (braid arrangement) comme modèle fondamental. Dans ce cadre symétrique, les fonctions compatibles admettent une description combinatoire basée sur les fonctions d'ensemble sur le treillis booléen, régie par l'inversion de Möbius.

Cependant, l'arrangement de tresses représente un cas simple et hautement symétrique. De nombreux arrangements naturels en géométrie combinatoire possèdent des structures de dépendance plus riches qui ne sont pas capturées par ce modèle. L'article vise à combler cette lacune en étendant le cadre théorique des arrangements de tresses aux arrangements discriminants, qui encodent des dépendances minimales via des circuits et sont étroitement liés à la théorie des matroïdes.

2. Méthodologie

L'auteur développe un cadre combinatoire et algébrique pour analyser les fonctions CPWL compatibles avec des arrangements d'hyperplans généraux, en se concentrant sur les contraintes induites par les circuits.

• Modélisation par Matroïdes : Au lieu de travailler avec une réalisation géométrique spécifique, l'article encode l'arrangement via son matroïde associé. L'étude se concentre sur les arrangements de type discriminant $A(n, k)$, où les circuits (ensembles dépendants minimaux) sont tous de cardinalité $k+1$. Cela correspond au matroïde uniforme de rang $k$.
• Fonctions d'Ensemble et Encodeur : Les fonctions CPWL $f: \mathbb{R}^n \to \mathbb{R}$ sont encodées en fonctions d'ensemble $F: 2^{[n]} \to \mathbb{R}$ via l'évaluation sur les vecteurs indicateurs : $F(S) = f(\mathbf{1}_S)$.
• Contraintes de Circuit : L'article définit des fonctionnels linéaires $\alpha_C$ basés sur le principe d'inclusion-exclusion pour chaque circuit $C$. Une fonction $F$ est dite compatible si elle satisfait $\alpha_C(F) = 0$ pour tous les circuits $C$.
• Inversion de Möbius : L'outil central de l'analyse est la transformée de Möbius $\hat{F}$ sur le treillis booléen. L'article établit un lien direct entre les contraintes de circuit et la nullité de la transformée de Möbius sur les ensembles dépendants.

3. Contributions Clés

1. Extension du Cadre Combinatoire : Passage de l'arrangement de tresses (sans contraintes de circuit) aux arrangements discriminants, où les dépendances imposent des contraintes linéaires sur les fonctions d'ensemble.
2. Caractérisation Matroïdale : Démonstration que l'espace des fonctions compatibles est isomorphe à l'espace des fonctions dont la transformée de Möbius est supportée uniquement sur les ensembles indépendants du matroïde sous-jacent.
3. Formule de Dimension : Preuve que la dimension de l'espace fonctionnel est égale au nombre d'ensembles indépendants du matroïde.
4. Élimination des Interactions d'Ordre Supérieur : Démonstration que les contraintes de circuit éliminent les degrés de liberté correspondant aux interactions d'ordre supérieur à $k$.
5. Caractérisation Complète pour $k=2$ : Pour le cas où les circuits sont de taille 3 ($k=2$), l'article fournit une description explicite : les fonctions sont entièrement déterminées par leurs valeurs sur les sous-ensembles de taille au plus 2.

4. Résultats Principaux

• Théorème de Dimension (Théorème 4.6) : La dimension de l'espace des fonctions contraintes par un matroïde $M$, noté $F_M$, est égale au nombre d'ensembles indépendants de $M$ :
  $$\dim(F_M) = |I(M)|$$
  Pour l'arrangement $A(n, k)$, cela donne $\dim \le \sum_{i=0}^k \binom{n}{i}$.

• Réduction des Interactions (Théorème 6.3) : Toute fonction représentée par un réseau de neurones compatible avec un arrangement $A(n, k)$ a une transformée de Möbius $\hat{F}$ qui s'annule sur tout ensemble dépendant. Par conséquent, la fonction ne dépend que des interactions d'ordre au plus $k$.

• Cas $k=2$ (Théorème 5.3) : Dans le cas des arrangements discriminants de rang 2, toute fonction $F \in F_{A(n,2)}$ est uniquement déterminée par ses valeurs sur les sous-ensembles de taille $\le 2$. La relation de circuit pour un triplet $\{i, j, k\}$ s'écrit explicitement :
  $$F(\{i,j,k\}) = F(\{i,j\}) + F(\{i,k\}) + F(\{j,k\}) - F(\{i\}) - F(\{j\}) - F(\{k\}) + F(\emptyset)$$
  Cela signifie que les termes d'interaction d'ordre 3 et supérieur sont redondants et entièrement déduits des termes constants, linéaires et bilinéaires.

• Réduction de l'Expressivité (Théorème 6.7) : La classe des fonctions représentables par des réseaux conformes à $A(n, k)$ est une sous-classe stricte de l'ensemble des fonctions CPWL générales (lorsque $k < n$).

  • L'espace non contraint a une dimension $2^n$ (croissance exponentielle).
  • L'espace contraint a une dimension polynomiale en $n$ (de l'ordre de $n^k$).

5. Signification et Implications

• Contrôle Combinatoire de l'Expressivité : L'article démontre que la structure combinatoire de l'arrangement d'hyperplans gouverne directement la capacité expressive des réseaux de neurones. Les arrangements discriminants imposent une régularisation structurelle implicite en limitant la complexité des interactions.
• Interprétation en Modèles d'Interaction : Pour $k=2$, les réseaux conformes se comportent comme des modèles d'interaction par paires (analogues aux modèles quadratiques en statistiques ou aux modèles graphiques). Ils ne peuvent pas capturer des interactions d'ordre supérieur sans violer la compatibilité avec l'arrangement.
• Effondrement Dimensionnel : Il y a un "effondrement dimensionnel" de l'espace des fonctions réalisables. Alors que les réseaux de neurones classiques (sans contraintes d'arrangement spécifiques) peuvent théoriquement modéliser des interactions d'ordre $n$, les architectures contraintes par des arrangements discriminants sont intrinsèquement limitées à des interactions d'ordre borné.
• Perspective Future : Ce travail suggère que l'étude des réseaux de neurones via les arrangements d'hyperplans offre un mécanisme systématique pour contrôler et analyser la complexité des modèles, ouvrant la voie à de nouvelles recherches sur les exigences de profondeur et de largeur en fonction des contraintes combinatoires imposées.

En résumé, cet article établit un pont rigoureux entre la théorie des matroïdes, la géométrie des arrangements d'hyperplans et l'expressivité des réseaux de neurones, montrant que l'imposition de contraintes de circuit réduit drastiquement l'espace des fonctions réalisables en éliminant les interactions d'ordre supérieur.