The minimal width of universal $p$-adic ReLU neural networks

Diese Arbeit bestimmt die minimale Breite von $p$-adischen neuronalen Netzen mit der universellen Approximationseigenschaft für stetige $\mathbb Q_p$-wertige Funktionen auf kompakten offenen Mengen unter Verwendung einer natürlichen $p$-adischen Analogie der ReLU-Aktivierungsfunktion.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, einen sehr komplizierten Weg durch eine Stadt zu beschreiben. Normalerweise tun wir das mit einer Landkarte, die auf reellen Zahlen basiert (wie unsere normale Welt). Aber in diesem Papier erforschen die Autoren eine ganz andere Art von Stadt: die Welt der p-adischen Zahlen.

Das klingt zunächst sehr mathematisch und abstrakt, aber lassen Sie es uns mit einfachen Bildern erklären.

1. Die Stadt der p-adischen Zahlen (Qp)

Stellen Sie sich unsere normale Welt als einen flachen, zusammenhängenden Boden vor. Wenn Sie von Punkt A nach Punkt B gehen, können Sie jeden Schritt dazwischen machen.

Die Welt der p-adischen Zahlen ist hingegen wie ein riesiges, unendliches Fraktal oder ein französisches Dorf, das aus unzähligen kleinen, getrennten Inseln besteht.

• In dieser Welt gibt es keine "glatten" Übergänge. Alles ist in winzige, isolierte Blöcke unterteilt.
• Wenn Sie sich in einem dieser Blöcke bewegen, fühlen Sie sich sicher und stabil. Sobald Sie den Block verlassen, sind Sie plötzlich in einer ganz anderen, weit entfernten Welt.
• Diese Eigenschaft nennt man "total unzusammenhängend". Das ist der Schlüssel zum Verständnis dieses Papiers.

2. Der KI-Neuronale Netzwerker (Das ReLU)

Neuronale Netze sind wie Teams von Arbeitern, die eine Aufgabe lösen sollen: Sie sollen eine Funktion (eine Regel oder einen Weg) nachahmen.

• Die Aktivierungsfunktion (pReLU): In normalen Netzen nutzen wir Funktionen wie "ReLU", die wie ein Schalter funktionieren: "Wenn der Wert positiv ist, lass ihn durch, sonst mach ihn null".
• In dieser p-adischen Welt nutzen die Autoren eine p-adische Version dieses Schalters. Sie funktioniert so: "Wenn der Wert in einem bestimmten, sicheren Bereich (den ganzen Zahlen) liegt, lass ihn durch. Wenn er 'zu weit draußen' ist, mach ihn null."

3. Das Problem: Wie breit muss das Team sein?

Die große Frage, die die Autoren beantworten, lautet: Wie viele Arbeiter (Breite des Netzes) brauchen wir mindestens, um jede beliebige Aufgabe in dieser Stadt zu lösen?

In der normalen Welt (reelle Zahlen) ist das kompliziert. Es gibt topologische Hindernisse (wie Löcher in der Stadt), die verhindern, dass ein kleines Team alles schafft. Man muss oft sehr tiefe oder breite Netze bauen.

Aber in der p-adischen Welt ist es einfacher!
Da die Stadt aus getrennten Inseln besteht, gibt es keine "glatten" Hindernisse. Man kann jede Aufgabe lösen, indem man einfach für jede Insel eine eigene kleine Regel aufstellt.

4. Die Entdeckung: Die perfekte Teamgröße

Die Autoren haben herausgefunden, dass die minimale Breite des Teams (die Anzahl der Arbeiter pro Ebene) genau dann ausreicht, wenn sie eine bestimmte Formel erfüllt:

Minimale Breite = Max(Inspirationen + 1, Ziel-Komplexität)

• Inspirationen (dx): Wie viele Eingabedaten haben wir? (Wie viele Koordinaten beschreiben wir?)
• Ziel-Komplexität (dy): Wie viele Ausgabedaten wollen wir produzieren?

Die Regel lautet also:
Sie brauchen mindestens so viele Arbeiter, wie es Eingabedaten gibt, plus einen zusätzlichen "Manager", ODER so viele, wie es Ausgabedaten gibt – je nachdem, was größer ist.

Warum "+1"?
Stellen Sie sich vor, Sie haben einen Eingangskanal. Um die Daten in der p-adischen Welt so zu manipulieren, dass sie in die verschiedenen getrennten Inseln passen, brauchen Sie einen zusätzlichen "Trick" oder eine zusätzliche Dimension, um die Daten zu kodieren (wie einen Schlüssel, der alle Türen öffnet).

5. Warum ist das wichtig?

Die Autoren zeigen, dass man in dieser p-adischen Welt mit einem sehr einfachen, flachen Netz alles perfekt nachahmen kann.

• Keine tiefen, komplizierten Strukturen nötig: Weil die Welt so "zerklüftet" ist, braucht man keine langen, verschachtelten Wege, um von A nach B zu kommen. Ein kurzer, breiter Weg reicht.
• Perfekte Approximation: Egal wie kompliziert die Funktion ist, wenn das Netz breit genug ist, kann es sie exakt nachbilden. Es gibt keine "Lücken" oder Fehler, die durch die Topologie der Welt verursacht werden.

Zusammenfassung in einem Satz

Die Autoren haben bewiesen, dass man in der seltsamen, inselartigen Welt der p-adischen Zahlen mit einem neuronalen Netz, das nur so breit ist wie die Eingabe plus ein bisschen mehr, jede beliebige Aufgabe perfekt lösen kann, weil die Struktur dieser Welt es erlaubt, alles in kleine, handhabbare Blöcke zu zerlegen.

Es ist, als würde man sagen: "Wenn Sie eine Stadt aus getrennten Häusern haben, brauchen Sie nicht einen riesigen Tunnelbauer, um sie zu verbinden. Sie brauchen nur einen Schlüsselmeister, der für jedes Haus den richtigen Schlüssel hat."

Technische Zusammenfassung

1. Problemstellung und Motivation

Das Paper adressiert das Problem der minimalen Breite universeller neuronaler Netze im Kontext der p-adischen Analysis. Während die universelle Approximationsfähigkeit und die minimalen Breiten von ReLU-Netzen über den reellen Zahlen ($\mathbb{R}$) intensiv untersucht wurden, fehlt eine entsprechende Theorie für den Körper der p-adischen Zahlen ($\mathbb{Q}_p$).

• Ziel: Bestimmung der minimalen Breite $w$, die notwendig ist, damit p-adische neuronale Netze mit einer spezifischen Aktivierungsfunktion (pReLU) beliebige stetige Funktionen $f: \mathbb{Z}_p^{d_x} \to \mathbb{Q}_p^{d_y}$ approximieren können.
• Kontext: Die Autoren betrachten Funktionen, die auf kompakten offenen Teilmengen von $\mathbb{Z}_p^{d_x}$ definiert sind (insbesondere auf $\mathbb{Z}_p^{d_x}$ selbst) und Werte in $\mathbb{Q}_p^{d_y}$ annehmen.
• Aktivierungsfunktion: Es wird eine natürliche p-adische Analogie zur ReLU-Funktion verwendet:
  $$\text{pReLU}(x) = \begin{cases} x & \text{wenn } x \in \mathbb{Z}_p \\ 0 & \text{sonst} \end{cases}$$
• Besonderheit: Im Gegensatz zu reellen Netzen, bei denen die Topologie von $\mathbb{R}$ (Zusammenhang) zu subtilen topologischen Hindernissen führt, ist $\mathbb{Q}_p$ total unzusammenhängend (totally disconnected). Dies vereinfacht die Approximationstheorie fundamental, da stetige Funktionen durch lokal konstante Funktionen approximiert werden können.

2. Methodik und mathematischer Rahmen

Die Autoren nutzen die einzigartigen topologischen und algebraischen Eigenschaften von $\mathbb{Q}_p$ und $\mathbb{Z}_p$:

• Topologie und Maße: $\mathbb{Z}_p^d$ ist eine kompakte, total unzusammenhängende topologische Gruppe mit einem eindeutigen Haar-Maß $\mu$. Dies ermöglicht die Definition von $L_q$-Normen ($1 \le q \le \infty$).
• Konvexität: In $\mathbb{Q}_p$-Vektorräumen wird Konvexität über $\mathbb{Z}_p$-Untermoduln definiert. Eine Menge ist konvex, wenn sie eine Nebenklasse eines $\mathbb{Z}_p$-Untermoduls ist.
• Approximationsstrategie:
  1. Reduktion auf lokal konstante Funktionen: Da $\mathbb{Z}_p^d$ total unzusammenhängend ist, ist die Menge der lokal konstanten Funktionen dicht in der Menge der stetigen Funktionen (bezüglich der Supremumsnorm).
  2. Diskretisierung: Lokal konstante Funktionen sind konstant auf Nebenklassen von $p^m \mathbb{Z}_p^d$. Das Problem reduziert sich somit auf die Interpolation von Werten auf endlichen Mengen.
  3. Konstruktion von Netzwerken: Die Beweise für die obere Schranke basieren auf der Konstruktion spezifischer pReLU-Netze, die als „Encoder" (Verschlüsseln von Koordinaten in einen einzigen Wert) und „Decoder" (Entschlüsseln eines Werts in mehrere Koordinaten) fungieren.

3. Hauptergebnisse

Das zentrale Ergebnis des Papers ist der folgende Satz (Theorem 1.2):

Satz: Für jedes $q \in [1, \infty]$ haben pReLU-Netze der Breite $w$ die universelle Approximationseigenschaft für stetige Funktionen $f: \mathbb{Z}_p^{d_x} \to \mathbb{Q}_p^{d_y}$ genau dann, wenn:
$$w \ge \max(d_x + 1, d_y)$$

Dieses Ergebnis gilt für alle $L_q$-Normen sowie für die $C^1$-Norm (die hier als $L_\infty$-Norm definiert ist).

Wichtige Beobachtungen im Vergleich zu reellen Netzen:

• Keine Diskrepanz: Im Gegensatz zu reellen Netzen, wo die untere und obere Schranke für die $C^1$-Approximation oft unterschiedlich sind, stimmen sie hier überein.
• Gewichte: Die universelle Approximation erfordert, dass die Gewichte in $\mathbb{Q}_p$ liegen. Wenn die Gewichte auf $\mathbb{Z}_p$ beschränkt wären, wäre das pReLU-Netz nur eine affine Abbildung und nicht universell (Remark 1.3).

4. Technische Beweisschritte

A. Untere Schranke ($w \ge \max(d_x + 1, d_y)$)

Der Beweis der Untergrenze erfolgt durch Konstruktion von Hindernissen:

1. Dimension des Ausgaberaums ($w \ge d_y$): Wenn $w < d_y$, liegt das Bild des Netzes in einer echten affinen Teilmenge von $\mathbb{Q}_p^{d_y}$. Da diese Teilmenge konvex ist und $\mathbb{Z}_p^{d_y}$ nicht vollständig abdeckt, kann sie nicht alle stetigen Funktionen approximieren (insbesondere nicht solche, die den gesamten Raum „ausfüllen").
2. Dimension des Eingaberaums ($w \ge d_x + 1$): Dies ist der subtilere Teil.
   • Theorem 2.13: Jedes pReLU-Netz der Breite $n$ ist entweder eine affine Abbildung auf $\mathbb{Z}_p^n$ oder es existiert eine Kugel $B$ vom Radius $1/p$, auf der die Funktion in einer Richtung konstant ist.
   • Widerspruch: Man konstruiert eine injektive stetige Funktion (z.B. eine Einbettung oder eine quadratische Abbildung), die nicht in einer Richtung konstant sein kann. Um diese zu approximieren, müsste das Netz also affin sein. Aber für $d_x \ge 2$ sind nicht-affine Funktionen notwendig, um Injektivität zu erhalten, was bei Breite $w \le d_x$ unmöglich ist, da affine Abbildungen auf $\mathbb{Z}_p^{d_x}$ ($d_x \ge 2$) in einer Richtung konstant sind (auf Kugeln).

B. Obere Schranke (Konstruktion universeller Netze)

Der Beweis, dass die Breite $\max(d_x + 1, d_y)$ ausreicht, basiert auf zwei Schlüsselkonstruktionen:

1. Encoding (Verschlüsselung):
   • Theorem 3.4: Jede lokal konstante Funktion $f: \mathbb{Z}_p^{d_x} \to \mathbb{Q}_p$ kann durch ein Netz der Breite $d_x + 1$ berechnet werden.
   • Methode: Konstruktion einer „Encoding-Funktion" $g: \mathbb{Z}_p^{d_x} \to \mathbb{Z}_p$, die verschiedene Nebenklassen von $p^m \mathbb{Z}_p^{d_x}$ auf verschiedene Werte in $\mathbb{Z}_p$ abbildet. Dies wird durch eine Kombination von pReLU-Netzen der Breite 2 (die spezifische Werte auf Nebenklassen setzen) erreicht.
2. Decoding (Entschlüsselung):
   • Lemma 3.16 & 3.19: Konstruktion einer „Juggling-Funktion" (eine Art Permutations- oder Mischfunktion) $g: \mathbb{Z}_p \to \mathbb{Z}_p$, die so konstruiert ist, dass sie auf jeder Nebenklasse von $p^m \mathbb{Z}_p$ surjektiv ist.
   • Durch Iteration dieser Funktion ($x, g(x), g(g(x)), \dots$) kann ein Netz der Breite $d_y$ eine „Decoding-Funktion" $h: \mathbb{Z}_p \to \mathbb{Z}_p^{d_y}$ erzeugen, die jede Nebenklasse in $\mathbb{Z}_p^{d_y}$ trifft.
3. Zusammensetzung: Durch die Kombination von Encoder (Breite $d_x+1$) und Decoder (Breite $d_y$) kann jede lokal konstante Funktion approximiert werden. Da diese dicht liegen, gilt die universelle Approximationseigenschaft.

5. Bedeutung und Fazit

• Vollständige Lösung: Das Paper liefert eine vollständige Antwort auf das Problem der minimalen Breite für p-adische ReLU-Netze, analog zu den bekannten Ergebnissen für reelle Netze, aber mit einem anderen, durch die p-adische Topologie bedingten Ergebnis ($d_x+1$ statt $d_x$ in manchen Kontexten, hier spezifisch $d_x+1$ für die Eingabe).
• Topologischer Unterschied: Die Arbeit unterstreicht, wie die totale Unzusammenhängendheit von $\mathbb{Q}_p$ die Approximationstheorie vereinfacht (keine topologischen Hindernisse wie bei $C^1$-Approximation im Reellen), aber gleichzeitig neue algebraische Strukturen (Konvexität über $\mathbb{Z}_p$-Moduln) erfordert.
• Praktische Implikationen: Obwohl p-adische Zahlen in der klassischen KI noch selten sind, bietet diese Arbeit ein theoretisches Fundament für Anwendungen in der p-adischen Signalverarbeitung oder bei Problemen, die natürlicherweise in diskreten, hierarchischen Strukturen (wie p-adischen Bäumen) auftreten.
• Methodischer Beitrag: Die Einführung von „Encoding" und „Decoding" als pReLU-Netze ist ein elegantes technisches Werkzeug, das die Interpolation auf endlichen Mengen in diesem Kontext löst.

Zusammenfassend beweisen die Autoren, dass p-adische neuronale Netze mit der pReLU-Aktivierungsfunktion universell sind, sobald ihre Breite die Eingabedimension plus eins oder die Ausgabedimension (je nachdem, was größer ist) erreicht, und dass diese Schranke scharf ist.