Piecewise linear functions and neural network expressivity via discriminantal arrangements

Titel: Stuksgewijs lineaire functies en de expressiviteit van neurale netwerken via discriminante arrangementen

1. Probleemstelling

Het begrijpen van de expressieve kracht (het vermogen om complexe functies te benaderen) van neurale netwerken is een centraal probleem op het snijvlak van combinatoriek, meetkunde en machine learning. Voor feedforward neurale netwerken met ReLU-activatie is bekend dat de klasse van representeerbare functies overeenkomt met de klasse van continue stuksgewijs lineaire (CPWL) functies.

Eerdere onderzoeken hebben deze expressiviteit bestudeerd via de combinatoriek van polyedrale complexen en hyperplane-arrangementen, met name het braids-arrangement (vlechtwerk-arrangement). Dit model is echter zeer symmetrisch en relatief eenvoudig; het vertegenwoordigt een geval waarin geen afhankelijkheidsrelaties tussen hypervlakken bestaan. Veel natuurlijke arrangementen in de combinatorische meetkunde vertonen echter rijkere afhankelijkheidsstructuren die niet door het braids-model worden gevangen. De vraag is hoe deze complexere structuren, specifiek discriminante arrangementen (die minimale afhankelijkheden via "circuits" coderen), de expressiviteit van neurale netwerken beperken of beïnvloeden.

2. Methodologie

De auteur breidt het bestaande raamwerk van hyperplane-arrangementen uit van het braids-arrangement naar discriminante arrangementen. De methodologische aanpak omvat de volgende stappen:

• Combinatorische Encoding: CPWL-functies worden gekoppeld aan verzamelfuncties op het Boolese traliewerk ($2^{[n]}$) door evaluatie op indicatorvectoren ($F(S) = f(\mathbf{1}_S)$).
• Circuit-gebaseerde Beperkingen: In plaats van alleen te kijken naar de geometrie, wordt de structuur van het arrangement gedefinieerd door zijn matroid (een abstracte structuur die onafhankelijkheid en afhankelijkheid beschrijft). Een "circuit" is een minimaal afhankelijke verzameling van hypervlakken.
• Lineaire Functionals: Voor elke circuit $C$ wordt een lineaire functional $\alpha_C$ gedefinieerd via een inclusie-exclusie som:
  $$\alpha_C(F) = \sum_{S \subseteq C} (-1)^{|C|-|S|} F(S) = 0$$
  Deze vergelijkingen stellen lineaire constraints op de verzamelfuncties.
• Möbius-inversie: De auteur gebruikt Möbius-inversie op het Boolese traliewerk om de constraints te vertalen naar voorwaarden voor de Möbius-transformatie $\hat{F}$ van de functie.
• Matroidale Karakterisering: De ruimte van toegestane functies wordt geanalyseerd in termen van de onafhankelijke verzamelingen van de onderliggende matroid.

3. Belangrijkste Bijdragen

1. Uitbreiding van het Raamwerk: Introductie van een circuit-gebaseerd raamwerk voor CPWL-functies dat het specifieke geval van het braids-arrangement generaliseert naar een algemeen model gedreven door afhankelijkheden (discriminante arrangementen).
2. Circuit-Gebonden Verzamelfuncties: Definitie van een nieuwe klasse van verzamelfuncties die voldoen aan de circuit-constraints, en het bewijs dat deze corresponderen met CPWL-functies die compatibel zijn met het arrangement.
3. Matroidale Karakterisering: Een fundamenteel resultaat waarbij de dimensie van de functie-ruimte gelijk wordt gesteld aan het aantal onafhankelijke verzamelingen van de onderliggende matroid.
4. Eliminatie van Hogere Orde Interacties: Het bewijs dat circuit-constraints hogere-orde interacties elimineren. Voor circuits van grootte $k+1$ worden functies volledig bepaald door waarden op deelverzamelingen van grootte ten hoogste $k$.
5. Toepassing op Neurale Netwerken: Het aantonen dat neurale netwerken die zijn ontworpen om compatibel te zijn met een specifiek arrangement (A-conforming networks) intrinsiek beperkt zijn tot het modelleren van interacties van een beperkte orde.

4. Kernresultaten

• Dimensie Formule: De dimensie van de ruimte van arrangement-compatibele CPWL-functies ($F_M$) is exact gelijk aan het aantal onafhankelijke verzamelingen $|I(M)|$ van de bijbehorende matroid $M$.
  $$\dim(F_M) = |I(M)|$$
  Dit staat in contrast met het braids-geval (geen circuits), waar de dimensie $2^n$ is (alle subsets zijn onafhankelijk).

• Het Geval $k=2$ (Uniforme Matroid):

  • Als alle circuits grootte 3 hebben (d.w.z. $k=2$), dan zijn alle subsets van grootte $\le 2$ onafhankelijk.
  • Stelling: Elke functie in deze ruimte wordt uniek bepaald door zijn waarden op deelverzamelingen van grootte ten hoogste 2.
  • De dimensie is dus $\binom{n}{0} + \binom{n}{1} + \binom{n}{2} = 1 + n + \frac{n(n-1)}{2}$, wat polynomiaal is in $n$ (kwadratisch), in plaats van exponentieel ($2^n$).

• Expressiviteitsbeperking:

  • Voor een discriminant arrangement $A(n, k)$ met circuits van grootte $k+1$, is de Möbius-transformatie $\hat{F}(S)$ gelijk aan 0 voor elke afhankelijke verzameling $S$.
  • Dit betekent dat de representeerbare functies alleen afhankelijk zijn van interacties van orde $\le k$.
  • Er bestaat een strikte expressiviteitsreductie: de klasse van functies die door $A(n, k)$-conforme netwerken kunnen worden weergegeven, is een strikte deelverzameling van alle CPWL-functies (zolang $k < n$).

5. Betekenis en Implicaties

• Combinatorische Controle: Het werk toont aan dat de combinatorische structuur van een hyperplane-arrangement direct de expressieve capaciteit van neurale netwerken reguleert. Door de keuze van het arrangement (en dus de circuits) kan men de complexiteit van het netwerk systematisch beperken.
• Structuur als Regularisatie: De beperking tot interacties van lage orde (bijv. alleen paarsgewijze interacties bij $k=2$) kan worden gezien als een vorm van impliciete structurele regularisatie. Dit reduceert de modelcomplexiteit en kan de interpretatiebaarheid verbeteren, aangezien het netwerk geen complexe hogere-orde interacties hoeft te leren.
• Dimensionale Ineenstorting: Waar de ruimte van alle CPWL-functies exponentieel groeit met de inputdimensie $n$, groeit de expressiviteit van arrangement-conforme netwerken slechts polynoom (voor vaste $k$). Dit biedt een theoretisch kader om te begrijpen waarom bepaalde architecturen minder flexibel zijn dan anderen.
• Toekomstperspectief: De studie suggereert dat het analyseren van de diepte en breedte-eisen van neurale netwerken kan worden benaderd via de combinatoriek van hyperplane-arrangementen, waarbij verschillende arrangementen leiden tot verschillende klassen van representeerbare functies.

Conclusie:
Dit artikel biedt een diep wiskundig inzicht in de beperkingen van neurale netwerken door ze te koppelen aan de theorie van matroiden en discriminante arrangementen. Het bewijst dat de aanwezigheid van circuit-afhankelijkheden leidt tot een drastische reductie in de dimensie van de functie-ruimte, waardoor netwerken beperkt worden tot het modelleren van interacties van een specifieke, lage orde.