🔢 mathematics

Expressivity of Shallow Neural Networks Over Finite Fields

Dit artikel onderzoekt de expressiviteit van ondiepe polynomiale neurale netwerken over eindige velden door een neuromanifold te definiëren waarvan de kardinaliteit wordt begrensd via het tellen van rationale punten gekoppeld aan de Weil-vermoedens, wat uiteindelijk aantoont hoe de karakteristiek van het veld de expressiviteit van het netwerk kritisch beïnvloedt in vergelijking met karakteristiek nul.

Oorspronkelijke auteurs: Maksym Zubkov, Carol Wu, Shiwei Yang, Param Mody, Yifei Chen

Gepubliceerd 2026-07-21

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Maksym Zubkov, Carol Wu, Shiwei Yang, Param Mody, Yifei Chen

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een machine probeert te bouwen die puzzels kan oplossen. In de wereld van computers worden deze machines neurale netwerken genoemd. Normaal gesproken denken we aan deze machines als gigantische rekenmachines die elk getal kunnen verwerken, van minuscule decimalen tot enorme gehele getallen, precies zoals de getallen op een standaard rekenmachine. Maar wat als we deze machines zouden dwingen om alleen een zeer specifieke, kleine set getallen te gebruiken? Stel je een wereld voor waarin je alleen kunt tellen met de getallen 0, 1, 2, 3 en 4, en als je naar 5 probeert te tellen, je terugspringt naar 0. Dit is wat wiskundigen een "eindig veld" noemen. Het is als een klok die slechts vijf uren heeft.

Waarom zou iemand dit willen doen? In de echte wereld verbruiken computers veel energie en geheugen om al die grote, complexe getallen op te slaan. Als we onze puzzeloplossende machines zouden kunnen leren om met slechts een paar eenvoudige getallen te werken, zouden we ze sneller kunnen laten draaien, minder batterij kunnen verbruiken en ze in kleinere apparaten kunnen laten passen. Maar er is een addertje onder het gras: wanneer we de regels van de getallen veranderen, veranderen we misschien ook de regels van wat de machine daadwerkelijk kan doen. Dit artikel stelt een grote vraag: als we ons getallensysteem verkleinen tot een piepklein eindig veld, verliest ons neurale netwerk dan zijn superkrachten, of blijft het net zo sterk? De auteurs testen in feite de grenzen van deze vereenvoudigde machines om te zien hoeveel verschillende puzzels ze daadwerkelijk kunnen oplossen.

Het Papier: Het Tellen van de Mogelijkheden in een Kleine Wereld

Dit papier duikt in de "expressiviteit" van een specifiek type neuraal netwerk, een "shallow polynomial neural network" (ondiep polynomiaal neuraal netwerk). In gewone mensentaal is "expressiviteit" gewoon een chic woord voor "hoeveel verschillende dingen kan deze machine daadwerkelijk creëren?" Denk aan de machine als een chef-kok. Als de chef een enorme voorraadkast heeft (een complex getallensysteem), kan hij bijna elk gerecht bereiden. Maar als de voorraadkast klein is (een eindig veld), kan hij dan nog steeds een grote verscheidenheid aan maaltijden bereiden, of zit hij vast aan het maken van steeds dezelfde soep?

De auteurs richten zich op "ondiepe" netwerken, die lijken op eenvoudige keukens met slechts één kookstation tussen de ingrediënten en het uiteindelijke bord. Ze gebruiken een speciale soort "activatiefunctie", wat simpelweg een regel is die de machine volgt om de ingrediënten te mengen. In dit geval is de regel eenvoudig: neem een getal en verhef het tot een macht (zoals het kwadrateren of cuberen).

De onderzoekers hebben een wiskundig kader gebouwd om exact te tellen hoeveel verschillende "gerechten" (of wiskundige functies) deze netwerken kunnen produceren wanneer ze gedwongen worden om in een eindig veld te werken. Ze noemen de collectie van alle mogelijke gerechten een "neuromanifold". Het is als een kaart van elke mogelijke maaltijd die de chef kan maken. Hoe groter de kaart, hoe expressiever het netwerk is.

De Grote Verrassing: Klokken versus Echte Getallen
De meest opvallende bevinding is dat deze netwerken heel anders reageren afhankelijk van of ze werken in de "echte wereld" (met complexe getallen) of in de "kleine wereld" (eindige velden).

In de echte wereld, als je een netwerk hebt met twee outputs (twee borden om te vullen), is de kaart van mogelijke gerechten enorm en dekt het bijna alles. Het is alsover zeggen: "Met genoeg oefening kan deze chef bijna elke combinatie van twee gerechten maken." Echter, wanneer de auteurs dit zelfde netwerk naar een eindig veld verplaatsten, kromp de kaart drastelijk. Voor een specifieke opstelling kon het netwerk slechts ongeveer de helft van de gerechten maken die het in de echte wereld zou kunnen maken.

Op een andere manier gezegd: in de echte wereld is het netwerk een meesterchef die bijna alles kan maken. In het eindige veld is diezelfde chef plotseling beperkt en kan hij een enorm deel van de menukaart niet meer creëren, zelfs niet als het recept (de architectuur) niet is veranderd. De auteurs laten zien dat de "kenmerk" van het veld (een eigenschap van de getallen, zoals of de klok een even of oneven aantal uren heeft) een cruciale rol speelt bij deze beperking.

Het Tellen van de Gerechten
Het papier zegt niet alleen "het is kleiner"; het telt de gerechten daadwerkelijk.

Voor sommige eenvoudige opstellingen (zoals een netwerk met één output), vonden ze dat het netwerk de volledige menukaart kan vullen, net als in de echte wereld.
Voor andere (zoals de opstelling met twee outputs die hierboven werd genoemd), berekenden ze dat het netwerk slechts een specifiek deel van de menukaart vult. Bijvoorbeeld, met een specifieke klokgrootte (priemgetal $p$ ), nadert het vermogen van het netwerk om variatie te creëren exact 1/2 van de totale mogelijkheden naarmate de klok groter wordt.
Ze ontdekten ook een vreemde truc met de getallen: als de macht waartoe je de getallen verheft een veelvoud is van de grootte van de klok (zoals verheffen tot de macht 5 op een 5-urige klok), gedraagt het netwerk zich precies alsof je tot de macht 1 verheft. Het is een wiskundige afkorting die het probleem vereenvoudigt, maar ook de variëteit beperkt.

Wat Ze Niet Hebben Opgelost
De auteurs merken zorgvuldig op dat hoewel ze de wiskunde voor eenvoudige, enkelvoudige lagen hebben opgelost, zaken veel ingewikkelder worden met diepere netwerken (meer kookstations) of complexere opstellingen. Ze geven expliciet aan dat voor netwerken met drie of meer "ingrediënten" in de middelste laag, het tellen ongelooflijk moeilijk wordt, en dat ze daar nog geen heldere formule voor hebben. Ze wijzen er ook op dat hoewel ze bewezen hebben dat deze netwerken beperkt zijn in eindige velden, ze nog niet elk mogelijk type beperking voor elke denkbare netwerkarchitectuur volledig in kaart hebben gebracht.

De Kernboodschap
Uiteindelijk bewijst dit papier dat je niet zomaar kunt aannemen dat een neuraal netwerk hetzelfde zal werken als je het getallensysteem verkleint. De "spelregels" veranderen. Voor sommige eenvoudige taken is het netwerk prima. Maar voor andere taken werkt het eindige veld als een filter die de helft van de mogelijkheden blokkeert. Dit is een cruciaal inzicht voor ingenieurs die efficiënte, energiezuinige AI willen bouwen. Het vertelt hen dat hoewel het verkleinen van de getallen energie bespaart, ze zeer voorzichtig moeten zijn met het ontwerp van het netwerk, omdat de "menukaart" van wat de AI kan leren veel kleiner kan zijn dan ze hadden verwacht. De auteurs suggereren dat het begrijpen van deze grenzen de eerste stap is naar het bouwen van betere, efficiëntere machines die hun magie niet verliezen wanneer ze overschakelen naar een klein getallensysteem.

Technische Samenvatting: Expressiviteit van Ondiepe Neurale Netwerken over Eindige Velden

Probleemstelling
Dit werk onderzoekt de expressiviteit van ondiepe polynomiale neurale netwerken (PNN's) met monomiale activatiefuncties $\sigma(x) = x^r$ over eindige velden $\mathbb{F}_q$ . Hoewel de expressiviteit van neurale netwerken traditioneel wordt bestudeerd via statistische methoden of over reële/complexe velden, behandelt dit artikel de algebraïsche expressiviteit in de context van eindige velden. Dit wordt gemotiveerd door de praktische voordelen van gewichtskwantisering (reductie van energie en opslag) en de theoretische verbinding tussen het tellen van rationale punten over eindige velden en de Weil-vermoedens, die gerelateerd zijn aan de motieve structuur van complexe variëteiten.

Het kernprobleem is het kwantificeren van de "arithmetische expressieve capaciteit" van een netwerkarchitectuur. In tegenstelling tot continue velden waar expressiviteit vaak wordt gemeten via dimensie of Zariski-dichtheid, definiëren de auteurs expressiviteit over eindige velden via de kardinaliteit van de neuromanifold — de afbeelding van de parametermap van netwerkgewichten naar de ruimte van representeerbare polynomiale functies.

Methodologie
De auteurs hanteren een algebraïsch-geometrische benadering, waarbij ze de output van het netwerk behandelen als elementen van een polynoomring in plaats van enkel als functies.

Formalisme: Een ondiep netwerk met architectuur $\mathbf{d}=(n, m, k)$ en activatiegraad $r$ brengt inputs $\mathbf{x} \in \mathbb{F}_q^n$ naar outputs in $(\mathbb{F}_q[x_1, \dots, x_n])^k$ . De output is een $k$ -tupel van homogene polynomen van graad $r$ .
Definitie Neuromanifold: De neuromanifold $\mathcal{P}_{\mathbf{d}, r}$ wordt gedefinieerd als de afbeelding van de parametermap $\Psi_{\mathbf{d}, r}$ van de gewichtsruimte $\mathbb{F}_q^{m(n+k)}$ naar de productruimtes van homogene polynomen $(S_r(\mathbb{F}_q^n))^k$ .
Strategie voor het tellen: Omdat de omgevingsruimte eindig is, wordt expressiviteit gemeten via de kardinaliteit $|\mathcal{P}_{\mathbf{d}, r}|$ $∣ P_{d, r} ∣$ . De auteurs maken gebruik van:
- Multinomiale Congruentiestellingen: Om te bepalen welke monomiale coëfficiënten verdwijnen modulo de karakteristiek $p$ van het veld.
- Tenseerdecompositie: Het relateren van netwerkoutputs aan symmetrische tensordecompositie (specifiek CP-rang en gelijktijdige diagonalisatie).
- Combinatorisch tellen: Het gebruik van formules voor het aantal matrices van een bepaalde rang over eindige velden (MacWilliams, 1969) en $q$ -binomialcoëfficiënten.
- Projectieve Geometrie: Het analyseren van de structuur van de neuromanifold in de projectieve ruimte om schaalinvariantie te behandelen.

Belangrijkste Bijdragen en Resultaten

1. Algemene Bovengrenzen
Het artikel stelt een algemene bovengrens vast voor de kardinaliteit van de neuromanifold op basis van de basis- $p$ expansie van de activatiegraad $r$ . Als $r = \sum r_t p^t$ , is het aantal niet-verdwijnende monomiale coëfficiënten $\gamma_{n,p}(r) = \prod \binom{r_t+n-1}{r_t}$ . Bijgevolg is de kardinaliteit begrensd door:
$|\mathcal{P}_{\mathbf{d}, r}| \leq q^{\gamma_{n,p}(r) \cdot k}$
Deze grens ontstaat omdat multinomiale coëfficiënten modulo $p$ verdwijnen voor bepaalde exponent-tuples, wat de effectieve dimensie van de representeerbare ruimte vermindert.

2. Exacte Kardinaliteiten voor Specifieke Architecturen
De auteurs leiden exacte formules af voor verschillende architecturen:

Enkele Output ( $k=1$ ) met Kwadratische Activatie ( $r=2, p \neq 2$ ): De neuromanifold komt overeen met de verzameling symmetrische $n \times n$ matrices met rang $\leq m$ . De kardinaliteit is de som van het aantal symmetrische matrices van rang $j$ voor $0 \leq j \leq m$ , gebruikmakend van MacWilliams' formule.
Meerdere Outputs ( $k>1$ ) met $r=2$ : De auteurs analyseren het geval $\mathbf{d}=(n, n, 2)$ . Zij tonen een scherp contrast aan tussen eindige en complexe velden. Over $\mathbb{C}$ is de neuromanifold Zariski-dicht (vult de ruimte). Over $\mathbb{F}_q$ nadert de arithmetische expressieve capaciteit $1/2$ wanneer $q \to \infty$ . Dit is gekoppeld aan het probleem van de gelijktijdige diagonalisatie van symmetrische matrices via congruentie (SDC), wat faalt voor een niet-verwaarloosbaar deel van de paren over eindige velden.
Architecturen met $m=1$ en $m=2$ :
- Voor $m=1$ wordt de kardinaliteit afgeleid via een product van projectieve ruimten: $|\mathcal{P}_{\mathbf{d}, r}| = |\mathcal{P}_{(n,1,1), r}| \cdot |\mathbb{P}^{k-1}|$ .
- Voor $m=2$ verdelen de auteurs de ruimte op basis van de dimensie van de span van de output-tensoren. Zij bieden onderscheidende formules voor $r > 1$ en $r=1$ , waarbij zij opmerken dat voor $r=1$ , lineaire combinaties van rang-1 tensoren ook rang-1 blijven, wat het tellen bemoeilijkt vanwege niet-unieke basisparen.

3. Karakteristiek Deelbaarheid ( $p \mid r$ )
Een belangrijke theoretische resultaat is de reductie van activatiegraden die deelbaar zijn door de karakteristiek. Als $r = i \cdot p$ , is de kardinaliteit van de neuromanifold identiek aan die van het netwerk met activatiegraad $i$ :
$|\mathcal{P}_{\mathbf{d}, ip}| = |\mathbf{\mathcal{P}}_{\mathbf{d}, i}|$
Dit wordt bewezen met behulp van de identiteit $(a+b)^p \equiv a^p + b^p$ in karakteristiek $p$ en het feit dat eindige velden perfect zijn. Dit maakt het mogelijk om complexe gevallen te reduceren tot eenvoudigere gevallen.

Speciaal geval ( $r=p$ ): Wanneer $r=p$ , komt de neuromanifold exact overeen met de verzameling $k \times n$ matrices met een rang van hoogstens $m$ .

4. Structurele Verschillen: Eindige vs. Complexe Velden
Het artikel benadrukt dat het gedrag van neuromanifolds over eindige velden drastisch kan verschillen van hun complexe tegenhangers, zelfs voor kleine architecturen.

Voorbeeld: Voor $\mathbf{d}=(2, 2, 2)$ met $r=2$ is de neuromanifold over $\mathbb{C}$ een Zariski-open verzameling (vult de ruimte), terwijl deze over $\mathbb{F}_q$ slechts ongeveer de helft van de omgevingsruimte inneemt.
Implicatie: Eigenschappen zoals "vullen" (surjectiviteit op de omgevingsruimte) zijn niet gegarandeerd over eindige velden, zelfs wanneer deze wel gelden over $\mathbb{C}$ .

Betekenis en Claims
De auteurs beweren dat dit werk een fundamenteel algebraïsch kader biedt voor het begrijpen van de expressiviteit van gekwantiseerde neurale netwerken. Door de focus te verschuiven van functiebenadering naar de kardinaliteit van de afbeelding van de parametermap, onthullen zij de structurele beperkingen die worden opgelegd door de karakteristiek van het veld.

Het artikel stelt dat:

Veldkarakteristiek is Cruciaal: De karakteristiek van het veld speelt een beslissende rol in de expressiviteit, en vermindert vaak de capaciteit van het netwerk vergeleken met karakteristiek nul-velden.
Verbinding met Diepe Wiskunde: Het probleem van het tellen van deze manifolds is intrinsiek verbonden met de Weil-vermoedens en de studie van rationale punten, wat een brug slaat tussen neurale netwerktheorie en arithmetische geometrie.
Beperkingen van de Huidige Theorie: De resultaten suggereren dat intuïtie afgeleid van netwerken met reële of complexe waarden (bijv. met betrekking tot Zariski-dichtheid) niet zomaar overdraagbaar is naar eindige velden, wat specifieke combinatorische en algebraïsche instrumenten vereist voor gekwantiseerde architecturen.

Het artikel concludeert door openstaande problemen te identificeren, zoals het vinden van architecturen waar de expressieve capaciteit convergeert naar een niet-nul fractie $0 < a/b < 1$ en het oplossen van het gelijktijdige diagonalisatieprobleem voor symmetrische tensoren over eindige velden. Het stelt geen nieuwe trainingsalgoritmen of experimentele benchmarks voor, maar richt zich op de theoretische limieten van representeerbaarheid.

Het Papier: Het Tellen van de Mogelijkheden in een Kleine Wereld

Technische Samenvatting: Expressiviteit van Ondiepe Neurale Netwerken over Eindige Velden

Meer zoals dit