🔢 mathematics

Expressivity of Shallow Neural Networks Over Finite Fields

Diese Arbeit untersucht die Expressivität flacher polynomieller neuronaler Netze über endlichen Körpern, indem sie eine Neuromanifold definiert, deren Kardinalität durch das Zählen rationaler Punkte verknüpft mit den Weil-Vermutungen begrenzt wird, und demonstriert letztlich, wie die Feldcharakteristik die Expressivität von Netzwerken im Vergleich zu Charakteristik Null entscheidend beeinflusst.

Ursprüngliche Autoren: Maksym Zubkov, Carol Wu, Shiwei Yang, Param Mody, Yifei Chen

Veröffentlicht 2026-07-21

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Maksym Zubkov, Carol Wu, Shiwei Yang, Param Mody, Yifei Chen

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, eine Maschine zu bauen, die Rätsel lösen kann. In der Welt der Computer werden diese Maschinen neuronale Netze genannt. Normalerweise denken wir über sie als riesige Taschenrechner nach, die jede beliebige Zahl verarbeiten können, von winzigen Dezimalzahlen bis hin zu massiven ganzen Zahlen, genau wie die Zahlen auf einem Standardrechner. Aber was wäre, wenn wir diese Maschinen dazu zwingen würden, nur einen sehr spezifischen, winzigen Satz an Zahlen zu verwenden? Stellen Sie sich eine Welt vor, in der Sie nur mit den Zahlen 0, 1, 2, 3 und 4 zählen können, und wenn Sie versuchen, bis 5 zu zählen, springen Sie zurück auf 0. Das ist, was Mathematiker einen „endlichen Körper“ nennen. Es ist wie eine Uhr, die nur fünf Stunden hat.

Warum sollte das überhaupt jemand wollen? In der realen Welt verbrauchen Computer viel Energie und Speicherplatz, um all diese großen, komplexen Zahlen zu speichern. Wenn wir unsere Rätsellösungsmaschinen dazu bringen könnten, nur mit ein paar einfachen Zahlen zu arbeiten, könnten wir sie schneller laufen lassen, weniger Batterie verbrauchen und sie in kleinere Geräte integrieren. Aber es gibt einen Haken: Wenn wir die Regeln der Zahlen ändern, ändern wir unter Umständen auch die Regeln dessen, was die Maschine tatsächlich tun kann. Dieses Paper stellt eine große Frage: Wenn wir unser Zahlensystem auf einen winzigen endlichen Körper schrumpfen, verliert unser neuronales Netz dann seine Superkräfte oder bleibt es genauso stark? Die Autoren testen im Wesentlichen die Grenzen dieser vereinfachten Maschinen, um zu sehen, wie viele verschiedene Rätsel sie tatsächlich lösen können.

Das Paper: Das Zählen der Möglichkeiten in einer winzigen Welt

Dieses Paper taucht ein in die „Expressivität“ eines speziellen Typs von neuronalem Netz, eines sogenannten „flachen polynomischen neuronalen Netzes“. In einfachem Deutsch ausgedrückt: „Expressivität“ ist nur ein schicker Begriff für „wie viele verschiedene Dinge kann diese Maschine tatsächlich erschaffen?“ Denken Sie an die Maschine wie an einen Koch. Wenn der Koch eine riesige Vorratskammer hat (ein komplexes Zahlensystem), kann er fast jedes Gericht kochen. Aber wenn seine Vorratskammer winzig ist (ein endlicher Körper), kann er dann immer noch eine große Vielfalt an Mahlzeiten zubereiten, oder ist er darauf beschränkt, immer wieder die gleiche Suppe zu kochen?

Die Autoren konzentrieren sich auf „flache“ Netze, die wie einfache Küchen sind, die nur eine einzige Kochstation zwischen den Zutaten und dem fertigen Teller besitzen. Sie verwenden eine spezielle Art von „Aktivierungsfunktion“, was im Grunde eine Regel ist, der die Maschine folgt, um ihre Zutaten zu mischen. In diesem Fall ist die Regel einfach: Nimm eine Zahl und erhebe sie zu einer Potenz (wie das Quadrieren oder Kubieren).

Die Forscher haben einen mathematischen Rahmen aufgebaut, um exakt zu zählen, wie viele verschiedene „Gerichte“ (oder mathematische Funktionen) diese Netze produzieren können, wenn sie gezwungen sind, in einem endlichen Körper zu arbeiten. Sie nennen die Gesamtheit aller möglichen Gerichte ein „Neuromanifold“. Es ist wie eine Landkarte von jeder möglichen Mahlzeit, die der Koch zubereiten kann. Je größer die Landkarte ist, desto expressiver ist das neuronale Netz.

Die große Überraschung: Uhren vs. reelle Zahlen
Die überraschendste Erkenntnis ist, dass sich diese Netze sehr unterschiedlich verhalten, je nachdem, ob sie in der „echten Welt“ (unter Verwendung komplexer Zahlen) oder in der „winzigen Welt“ (endliche Körper) arbeiten.

In der realen Welt, wenn man ein Netzwerk mit zwei Ausgängen hat (zwei Teller, die gefüllt werden sollen), ist die Landkarte der möglichen Gerichte riesig und deckt fast alles ab. Es ist so, als würde man sagen: „Mit genügend Übung kann dieser Koch fast jede Kombination von zwei Gerichten zubereiten.“ Doch als die Autoren dieses identische Netzwerk in einen endlichen Körper übertrugen, schrumpfte die Landkarte der möglichen Gerichte dramatisch. Für einen spezifischen Aufbau konnte das Netzwerk nur etwa die Hälfte der Gerichte erstellen, die es in der realen Welt produzieren könnte.

Anders ausgedrückt: In der realen Welt ist das Netzwerk ein Meisterkoch, der fast alles zaubern kann. In dem endlichen Körper ist derselbe Koch plötzlich eingeschränkt und unfähig, einen riesigen Teil des Menüs zu kreieren, obwohl das Rezept (die Architektur) sich nicht geändert hat. Die Autoren zeigen, dass der „Charakteristik“ des Körpers (eine Eigenschaft der Zahlen, wie etwa ob die Uhr eine gerade oder ungerade Anzahl an Stunden hat) eine entscheidende Rolle bei dieser Einschränkung spielt.

Das Zählen der Gerichte
Das Paper sagt nicht nur „es ist kleiner“; es zählt die Gerichte tatsächlich.

Für einige einfache Setups (wie ein Netzwerk mit einem Ausgang) fanden sie heraus, dass das Netzwerk das gesamte Menü füllen kann, genau wie in der realen Welt.
Für andere (wie das oben erwähnte Setup mit zwei Ausgängen) berechneten sie, dass das Netzwerk nur einen spezifischen Bruchteil des Menüs füllt. Beispielsweise nähert sich die Fähigkeit des Netzwerks, Vielfalt zu erzeugen, bei einer bestimmten Uhrzeitgröße (Primzahl $p$ ), die man zu einer Potenz erhebt, exakt dem Wert 1/2 der Gesamtmöglichkeiten an, während die Uhrgröße größer wird.
Sie entdeckten auch einen seltsamen Trick mit den Zahlen: Wenn die Potenz, zu der man die Zahlen erhebt, ein Vielfaches der Größe des Körpers ist (wie das Erheben zur Potenz 5 bei einer 5-stündigen Uhr), verhält sich das Netzwerk exakt so, als würde man es zur Potenz 1 erheben. Es ist eine mathematische Abkürzung, die das Problem vereinfacht, aber auch die Vielfalt einschränkt.

Was sie nicht gelöst haben
Die Autoren merken vorsichtig an, dass sie zwar die Mathematik für einfache, einlagige Netzwerke gelöst haben, die Dinge aber mit tieferen Netzwerken (mehr Kochstationen) oder komplexeren Setups viel komplizierter werden. Sie stellen explizit fest, dass für Netzwerke mit drei oder mehr „Zutaten“ in der mittleren Schicht das Zählen unglaublich schwierig wird und sie noch keine saubere Formel dafür haben. Sie weisen auch darauf hin, dass sie zwar bewiesen haben, dass diese Netzwerke in endlichen Körpern begrenzt sind, aber nicht jede mögliche Einschränkung für jede einzelne Art von Netzwerkarchitektur vollständig kartiert haben.

Das Fazhrgebnis
Letztendlich beweist dieses Paper, dass man nicht einfach davon ausgehen kann, dass ein neuronales Netz genauso funktioniert, wenn man sein Zahlensystem verkleinert. Die „Regeln des Spiels“ ändern sich. Für einige einfache Aufgaben ist das Netzwerk völlig in Ordnung. Aber für andere wirkt der endliche Körper wie ein Filter, der die Hälfte der Möglichkeiten blockiert. Dies ist eine entscheidende Erkenntnis für Ingenieure, die effiziente, stromsparende KI bauen wollen. Es zeigt ihnen, dass das Verkleinern der Zahlen zwar Energie spart, sie aber sehr vorsichtig bei der Gestaltung des Netzwerks sein müssen, da das „Menü“ dessen, was die KI lernen kann, viel kleiner sein könnte, als sie erwartet haben. Die Autoren legen nahe, dass das Verständnis dieser Grenzen der erste Schritt ist, um bessere, effizientere Maschinen zu bauen, die nicht ihren Zauber verlieren, wenn sie zu einem winzigen Zahlensystem wechseln.

Technisches Resümee: Expressivität flacher neuronaler Netze über endlichen Körpern

Problemstellung
Diese Arbeit untersucht die Expressivität flacher polynomieller neuronaler Netze (PNNs) mit Monomial-Aktivierungsfunktionen $\sigma(x) = x^r$ über endlichen Körpern $\mathbb{F}_q$ . Während die Expressivität neuronaler Netze traditionell mittels statistischer Methoden oder über reelle/komplexe Körper untersucht wird, befasst sich dieses Paper mit der algebraischen Expressivität im Kontext endlicher Körper. Dies wird durch die praktischen Vorteile der Gewichtsquantisierung (Reduzierung von Energie und Speicherbedarf) sowie die theoretische Verbindung zwischen dem Zählen rationaler Punkte über endlichen Körpern und den Weil-Vermutungen motiviert, welche die motivische Struktur komplexer Varietäten beschreiben.

Der Kern des Problems besteht darin, die „arithmetische expressive Kapazität“ einer Netzwerkarchitektur zu quantifizieren. Im Gegensatz zu kontinuierlichen Körpern, in denen die Expressivität oft über Dimension oder Zariski-Dichte gemessen wird, definieren die Autoren die Expressivität über endlichen Körpern über die Kardinalität der Neuromanifold – dem Bild der Parameterabbildung von den Netzwerkgewichten auf den Raum der repräsentierbaren Polynomfunktionen.

Methodik
Die Autoren verfolgen einen algebro-geometrischen Ansatz und behandeln den Netzwerkausgang als Elemente eines Polynomrings statt lediglich als Funktionen.

Formalismus: Ein flaches Netzwerk mit der Architektur $\mathbf{d}=(n, m, k)$ und dem Aktivierungsgrad $r$ bildet Eingaben $\mathbf{x} \in \mathbb{F}_q^n$ auf Ausgaben in $(\mathbb{F}_q[x_1, \dots, x_n])^k$ ab. Der Ausgang ist ein $k$ -Tupel homogener Polynome vom Grad $r$ .
Definition der Neuromanifold: Die Neuromanifold $\mathcal{P}_{\mathbf{d}, r}$ ist definiert als das Bild der Parameterabbildung $\Psi_{\mathbf{d}, r}$ aus dem Gewichtraum $\mathbb{F}_q^{m(n+k)}$ auf das Produkt der Räume homogener Polynome $(S_r(\mathbb{F}_q^n))^k$ .
Zählstrategie: Da der Umgebungsraum endlich ist, wird die Expressivität über die Kardinalität $|\mathcal{P}_{\mathbf{d}, r}|$ $∣ P_{d, r} ∣$ gemessen. Die Autoren nutzen hierfür:
- Multinomiale Kongruenzsätze: Um zu bestimmen, welche Monomialkoeffizienten modulo der Charakteristik $p$ des Körpers verschwinden.
- Tensordekomposition: Die Verknüpfung von Netzwerkausgängen mit symmetrischen Tensordekompositionen (speziell CP-Rang und simultane Diagonalisierung).
- Kombinatorisches Zählen: Verwendung von Formeln für die Anzahl von Matrizen eines gegebenen Rangs über endlichen Körpern (MacWilliams, 1969) und $q$ -Binomialkoeffizienten.
- Projektive Geometrie: Analyse der Struktur der Neuromanifold im projektiven Raum, um Skalierungsinvarianz zu handhaben.

Wesentliche Beiträge und Ergebnisse

1. Allgemeine obere Schranken
Das Paper etabliert eine allgemeine obere Schranke für die Kardinalität der Neuromanifold basierend auf der Basis- $p$ -Entwicklung des Aktivierungsgrades $r$ . Wenn $r = \sum r_t p^t$ , ist die Anzahl der nicht verschwindenden Monomialkoeffizienten $\gamma_{n,p}(r) = \prod \binom{r_t+n-1}{r_t}$ . Folglich ist die Kardinalität nach oben beschränkt durch:
$|\mathcal{P}_{\mathbf{d}, r}| \leq q^{\gamma_{n,p}(r) \cdot k}$
Diese Schranke ergibt sich daraus, dass multinomiale Koeffizienten modulo $p$ für bestimmte Exponenten-Tupel verschwinden, was die effektive Dimension des repräsentierbaren Raums reduziert.

2. Exakte Kardinalitäten für spezifische Architekturen
Die Autoren leiten exakte Formeln für verschiedene Architekturen her:

Einzelner Ausgang ( $k=1$ ) mit quadratischer Aktivierung ( $r=2, p \neq 2$ ): Die Neuromanifold entspricht der Menge der symmetrischen $n \times n$ -Matrizen mit Rang $\leq m$ . Die Kardinalität ist die Summe der Anzahl der symmetrischen Matrizen des Rang $j$ für $0 \leq j \leq m, unter Verwendung von MacWilliams' Formel.
Mehrfache Ausgänge ( $k>1$ ) mit $r=2$ : Die Autoren analysieren den Fall $\mathbf{d}=(n, n, 2)$ . Sie zeigen einen drastischen Kontrast zwischen endlichen und komplexen Körpern auf. Über $\mathbb{C}$ ist die Neuromanifold Zariski-dicht (füllt den Raum aus). Über $\mathbb{F}_q$ nähert sich die arithmetische expressive Kapazität für $q \to \infty$ dem Wert $1/2 an$. Dies ist verknüpft mit dem Problem der simultanen Diagonalisierung symmetrischer Matrizen durch Kongruenz (SDC), welches für einen nicht vernachlässigbaren Anteil von Paaren über endlichen Körpern fehlschlägt.
Architekturen mit $m=1$ und $m=2$ :
- Für $m=1$ wird die Kardinalität über ein Produkt von projektiven Räumen abgeleitet: $|\mathcal{P}_{\mathbf{d}, r}| = |\mathcal{P}_{(n,1,1), r}| \cdot |\mathbb{P}^{k-1}|$ .
- Für $m=2$ partitionieren die Autoren den Raum basierend auf der Dimension des Spanns der Output-Tensoren. Sie liefern unterschiedliche Formeln für $r > 1$ und $r=1$ , wobei sie darauf hinweisen, dass für $r=1$ Linearkombinationen von Rang-1-Tensoren weiterhin Rang-1-Tensoren bleiben, was das Zählen aufgrund nicht-eindeutiger Basispare erschwert.

3. Charakteristische Teilbarkeit ( $p \mid r$ )
Ein bedeutendes theoretisches Ergebnis ist die Reduktion von Aktivierungsgraden, die durch die Charakteristik teilbar sind. Wenn $r = i \cdot p$ , ist die Kardinalität der Neuromanifold identisch mit der der Neuromanifold mit Aktivierungsgrad $i$ :
$|\mathcal{P}_{\mathbf{d}, ip}| = |\mathbf{\mathcal{P}}_{\mathbf{d}, i}|$
Dies wird unter Verwendung der Identität $(a+b)^p \equiv a^p + b^p$ in Charakteristik $p$ und der Tatsache, dass endliche Körper perfekt sind, bewiesen. Dies ermöglicht die Reduktion komplexer Fälle auf einfachere Fälle.

Spezialfall ( $r=p$ ): Wenn $r=p$ , entspricht die Neuromanifold exakt der Menge der $k \times n$ -Matrizen mit Rang höchstens $m$ .

4. Strukturelle Unterschiede: Endliche vs. komplexe Körper
Das Paper hebt hervor, dass das Verhalten von Neuromanifolds über endlichen Körpern drastisch von ihren komplexen Gegenstücken abweichen kann, selbst bei kleinen Architekturen.

Beispiel: Für $\mathbf{d}=(2, 2, 2)$ mit $r=2$ ist die Neuromanifold über $\mathbb{C}$ Zariski-offen (sie füllt den Raum aus), während sie über $\mathbb{F}_q$ nur etwa die Hälfte des Umgebungssraums einnimmt.
Implikation: Eigenschaften wie das „Ausfüllen“ (Surjektivität auf den Umgebungssraum) sind über endlichen Körpern nicht garantiert, selbst wenn dies über $\mathbb{C}$ der Fall ist.

Bedeutung und Behauptungen
Die Autoren behaupten, dass diese Arbeit einen grundlegenden algebraischen Rahmen für das Verständnis der Expressivität quantisierter neuronaler Netze bietet. Durch die Verschiebung des Fokus von der Funktionsapproximation auf die Kardinalität des Bildes der Parameterabbildung enthüllen sie strukturelle Beschränkungen, die durch die Charakteristik des Körpers auferlegt werden.

Das Paper stellt fest:

Die Charakteristik des Körpers ist entscheidend: Die Charakteristik des Körpers spielt eine entscheidende Rolle für die Expressivität und reduziert oft die Kapazität des Netzwerks im Vergleich zu Körpern mit Charakteristik Null.
Verbindung zu tiefer Mathematik: Das Problem des Zählens dieser Manifolds ist intrinsisch mit den Weil-Vermutungen und der Untersuchung rationaler Punkte verknüpft, was eine Brücke zwischen der Theorie neuronaler Netze und der arithmetischen Geometrie schlägt.
Grenzen der aktuellen Theorie: Die Ergebnisse legen nahe, dass die aus komplexen oder reellen Werten abgeleitete Intuition (z. B. bezüglich der Zariski-Dichte) nicht ohne Weiteres auf endliche Körper übertragbar ist, was spezifische kombinatorische und algebraische Werkzeuge für quantisierte Architekturen erforderlich macht.

Das Paper schließt mit der Identifizierung offener Probleme, wie etwa dem Finden von Architekturen, bei denen die expressive Kapazität gegen einen nicht-verschwindenden Bruchteil $0 < a/b < 1$ konvergiert, und der Lösung des Problems der simultanen Diagonalisierung symmetrischer Tensoren über endlichen Körpern. Es schlägt keine neuen Trainingsalgorithmen oder experimentellen Benchmarks vor, sondern konzentriert sich auf die theoretischen Grenzen der Repräsentierbarkeit.

Das Paper: Das Zählen der Möglichkeiten in einer winzigen Welt

Technisches Resümee: Expressivität flacher neuronaler Netze über endlichen Körpern

Mehr davon