Minimal Filling Architectures of Polynomial Neural Networks: Counterexamples, Frontier Search, and Defects

Technische Samenvatting: Minimale Vullende Architecturen van Polynoom Neuronale Netwerken

Probleemstelling
Het artikel behandelt een fundamentele vraag in de neuroalgebraïsche meetkunde met betrekking tot de structurele eigenschappen van Polynoom Neuronale Netwerken (PNN's). Specifiek onderzoekt het de "Minimale Unimodale Vermoeden" (Vermoeden 12 in [8]). Het vermoeden stelt dat voor PNN's met macht-activeringsfuncties ($\sigma(z) = z^r$), elke Minimale Vullende Architectuur (MFA)—gedefinieerd als de kleinste netwerkconfiguratie die in staat is de volledige functionele ruimte (neurovariëteit) te overspannen voor vaste invoer/uitvoer-dimensies—unimodale verborgen-lagbreedtes moet bezitten. Dat wil zeggen, de reeks van laagbreedtes moet toenemen tot een piek en vervolgens afnemen ($d_0 \le \dots \le d_i \ge \dots \ge d_L$). Deze hypothese sluit aan bij de "conventionele wijsheid" in het machine learning dat netwerken hun capaciteit uitbreiden om patronen te vangen en deze vervolgens verkleinen om ze te verfijnen.

Methodologie
De auteurs maken gebruik van een combinatie van algebraïsche meetkunde, symbolische berekening en algoritmische zoektocht om het vermoeden te testen:

1. Algebraïsch Kader: De studie maakt gebruik van de parameterafbeelding $\Psi_{d,r}$, die netwerkgewichten afbeeldt op de ruimte van homogene polynomen (de neurovariëteit $V_{d,r}$). Een architectuur is "vullend" als de dimensie van zijn neurovariëteit gelijk is aan de dimensie van de omringende ruimte (de volledige symmetrische tensorruimte).
2. Dimensieverificatie: Om te bepalen of een architectuur vullend is, berekenen de auteurs de generieke rang van de Jacobiaan van de parameterafbeelding. Aangezien exacte symbolische rangberekening moeilijk is voor grote netwerken, maken ze gebruik van berekeningen over eindige velden (over $\mathbb{F}_p$) om de generieke rang te bepalen. Als de rang over een eindig veld overeenkomt met de dimensie van de omringende ruimte, is de architectuur vullend.
3. Recursieve Grenzen: Om minimaliteit te bewijzen (dat geen enkele subarchitectuur vullend is), passen de auteurs recursieve dimensiegrenzen toe die zijn afgeleid uit Lemma 2.4 in [8]. Dit stelt hen in staat de dimensie van een subarchitectuur te begrenzen door de som van de dimensies van zijn samenstellende delen min de interface-breedte.
4. Frontier Search-algoritme: Om MFAs te ontdekken, hebben de auteurs een "frontier search"-algoritme ontwikkeld (Algoritme 1). Dit algoritme stelt iteratief kandidaat-verborgen-lagbreedtes voor en snoeit de zoekruimte op basis van:
   • Naïeve dimensiegrenzen.
   • Bekende resultaten uit eerdere zoektochten (het bijhouden van verzamelingen van minimale vullende en maximale niet-vullende architecturen).
   • De definitie van minimaliteit: als een kandidaat vullend is, worden alle grotere architecturen gesnoeid; als deze niet vullend is, worden alle kleinere architecturen gesnoeid.

Belangrijkste Bijdragen en Resultaten

• Tegenvoorbeeld voor het Minimale Unimodale Vermoeden: De belangrijkste bijdrage is de ontdekking en certificering van een tegenvoorbeeld voor het vermoeden. De auteurs identificeerden de architectuur $d = (2, 3, 4, 5, 4, 6, 4, 1)$ (met $r=2$, invoer 2, uitvoer 1, diepte 7) als een Minimale Vullende Architectuur die niet unimodaal is.

  • Bewijs van Vullendheid: Zij verifieerden dat de dimensie van de neurovariëteit 65 is, wat overeenkomt met de dimensie van de omringende ruimte $\dim(\text{Sym}^{2^6}(\mathbb{R}^2) \oplus \mathbb{R}^1)$.
  • Bewijs van Minimaliteit: Zij toonden aan dat elke subarchitectuur die wordt verkregen door de breedte van een enkele verborgen laag met één te verkleinen, niet vullend is. Dit werd bereikt door aan te tonen dat de dimensies van deze sub-architecturen strikt kleiner zijn dan 65, met behulp van zowel berekeningen over eindige velden als recursieve grenzen.

• Ontdekking van Grote Defecten: Bij het analyseren van het tegenvoorbeeld en zijn sub-architecturen, observeerden de auteurs "grote defectiviteit". Defect wordt gedefinieerd als het verschil tussen de verwachte dimensie (gebaseerd op parameterstelling) en de werkelijke dimensie van de neurovariëteit. In tegenstelling tot eerdere voorbeelden waar defecten klein waren, vertoonden verschillende sub-architecturen van het tegenvoorbeeld aanzienlijke defecten, wat de aanname uitdaagt dat defecten verwaarloosbaar zijn in typische configuraties.

• Systematische Zoekresultaten: Met behulp van hun frontier search-algoritme catalogiseerden de auteurs MFAs voor $d_0=2, d_L=1, r=2$ tot diepte $L=7$.

  • Voor $L=7$ vonden zij 13 MFAs, waarvan slechts één (het bovengenoemde tegenvoorbeeld) niet-unimodaal was.
  • Voor $L=8$ vonden zij 82 MFAs, waarvan 20 niet-unimodaal waren.
  • Zij leverden een tabel met geverifieerde MFAs voor $L \le 7$, waarbij zij opmerkten dat hoewel zij volledigheid verifieerden voor $L \le 7$, een algemene methode om volledigheid voor grotere $L$ te bewijzen een open probleem blijft.

• Aanvullend Tegenvoorbeeld: De auteurs identificeerden een tweede, dieper tegenvoorbeeld met $d_0=d_L=2$ en $L=9$ ($d=(2, 3, 4, 4, 10, 17, 11, 12, 4, 2)$), wat verder illustreert dat niet-unimodale MFAs bestaan in diverse configuraties.

Betekenis en Aanspraken
Het artikel claimt het eerste tegenexample te leveren voor het Minimale Unimodale Vermoeden voor polynoom neuronale netwerken, waarmee het idee wordt weerlegd dat minimale expressiviteit altijd een unimodale reeks van breedtes vereist.

De auteurs formuleren de betekenis van hun werk bescheiden als volgt:

• Theoretische Correctie: De resultaten corrigeren de "conventionele wijsheid" met betrekking tot de efficiëntie van netwerkarchitecturen in de context van algebraïsche meetkunde.
• Inzicht in Defectiviteit: De ontdekking van grote defecten in sub-architecturen suggereert een gebrek aan systematisch inzicht met betrekking tot welke architecturen defectief zijn, en opent een nieuw onderzoeksgebied naar de meetkunde van functieruimten.
• Praktische Implicatie: De auteurs suggereren dat het begrijpen van MFAs voor macht-activeringen de selectie van architecturen kan informeren, met name bij het koppelen van polynoom-activeringen van lage graad (die computationeel efficiënt zijn maar de expressiviteit kunnen beperken) aan architecturen die a priori zeer expressief zijn.
• Toekomstige Richtingen: Het artikel identificeert verschillende volgende stappen, waaronder generalisatie naar bredere families van polynoom-activeringen (bijv. Chebyshev-basis), het toepassen van neuroalgebraïsche meetkunde op $\Pi$-netten, en het vergelijken van de trainingsdynamiek van MFAs versus maximale niet-vullende architecturen.

De auteurs claimen niet het algemene probleem van het karakteriseren van alle MFAs voor willekeurige diepten opgelost te hebben, noch het volledig hebben verklaard van de geometrische oorzaken van grote defecten, maar wel de existentie van niet-unimodale minimale vullingen gevestigd te hebben en de computationele hulpmiddelen en data te hebben geboden om dit fenomeen verder te onderzoeken.