📊 statistics

Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity

Dieser Artikel zeigt, dass jede feste Feedforward-Neuronale-Netzwerk-Architektur, die innerhalb einer o-minimalen Struktur definierbar ist, eine endliche Stichprobenkomplexität im agnostischen PAC-Modell aufweist, und belegt damit, dass lernbare Verteilungsfreiheit eine fundamentale Konsequenz zahmer mathematischer Definitionen ist und keine einzigartige Eigenschaft spezifischer Aktivierungsfunktionen oder Architekturen darstellt.

Ursprüngliche Autoren: Anastasis Kratsios, Gregory Cousins, Haitz Sáez de Ocáriz Borde, Bum Jun Kim, Simone Brugiapaglia

Veröffentlicht 2026-05-11

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Anastasis Kratsios, Gregory Cousins, Haitz Sáez de Ocáriz Borde, Bum Jun Kim, Simone Brugiapaglia

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, einen Roboter zu lehren, Katzen zu erkennen, Aktienkurse vorherzusagen oder Sprachen zu übersetzen. Sie bauen eine komplexe Maschine aus vielen kleinen Teilen (Schichten), die jeweils eine spezifische Aufgabe erfüllen. In der Welt der KI werden diese Maschinen Neuronale Netze genannt.

Seit langem stellen Mathematiker und Informatiker eine knifflige Frage: „Wie viel Daten benötigt dieser Roboter tatsächlich, um zu lernen, bevor er Sinn ergibt?"

Wenn ein Roboter zu kompliziert ist, benötigt er möglicherweise eine unendliche Menge an Daten, um zu lernen, oder er merkt sich die Daten einfach auswendig, ohne etwas zu verstehen (ein Problem, das als „Overfitting" bezeichnet wird). Wenn er eine handhabbare, endliche Menge an Daten benötigt, sagen wir, er hat eine „endliche Stichprobenkomplexität". Auf Deutsch ausgedrückt: Er kann tatsächlich aus einem realen Datensatz lernen.

Diese Arbeit mit dem Titel „Every Feedforward Neural Network Definable in an o-Minimal Structure Has Finite Sample Complexity" (Jedes vorwärtsgerichtete neuronale Netz, das in einer o-minimalen Struktur definierbar ist, besitzt eine endliche Stichprobenkomplexität), liefert eine massive, beruhigende Antwort auf diese Frage.

Hier ist die Aufschlüsselung in einfachen Worten:

1. Die große Entdeckung: „Wenn es gut gebaut ist, kann es lernen."

Die Autoren beweisen, dass fast jedes moderne, standardmäßige neuronale Netz, das Sie heute sehen (wie die, die Chatbots, Bildgeneratoren und autonome Fahrzeuge antreiben), lernen kann.

Sie haben nicht nur einen spezifischen Netztyp überprüft. Sie haben die gesamte „Familie" der in der Praxis verwendeten Netze betrachtet:

MLPs: Der klassische „Stapel von Schichten".
CNNs: Diejenigen, die hervorragend darin sind, Bilder zu betrachten.
Transformer: Diejenigen hinter modernen Large Language Models (wie dem, mit dem Sie gerade sprechen).
GNNs: Diejenigen, die Graphen und Beziehungen verstehen.

Die Arbeit besagt: Solange das Netz „feedforward" ist (es bewegt sich in eine Richtung, wie Wasser, das eine Rutsche hinunterfließt, ohne sich selbst zu umkreisen) und aus standardmäßigen, wohlverhaltenen mathematischen Operationen besteht, ist garantiert, dass es eine endliche Stichprobenkomplexität besitzt.

2. Der geheime Bestandteil: „o-minimale Strukturen"

Sie fragen sich vielleicht: „Was macht diese Netze zu ‚wohlverhaltenen'?" Die Arbeit verwendet ein ausgefeiltes mathematisches Konzept namens o-minimale Strukturen.

Die Analogie: Der „zahme" versus der „wilde" Garten
Stellen Sie sich zwei Gärten vor:

Der wilde Garten: Hier können Pflanzen in unendlichen, chaotischen Spiralen wachsen, sich endlos selbst umkreisen und mit unendlicher Komplexität zappeln. Wenn Sie versuchen, diesen Garten zu kartieren, benötigen Sie möglicherweise eine unendliche Menge an Papier. Dies repräsentiert „wilde" mathematische Funktionen, die zu chaotisch sind, um aus Daten zu lernen.
Der zahme Garten (o-minimal): Hier sind die Pflanzen wohlverhalten. Sie können sich krümmen, biegen oder verzweigen, aber sie zappeln nicht unendlich. Sie sind „zahm". Sie können den gesamten Garten mit einer endlichen Menge an Regeln beschreiben.

Die Autoren zeigen, dass die Mathematik, die zum Bau moderner KI verwendet wird (Dinge wie ReLU, Sigmoid, Softmax, Aufmerksamkeitsmechanismen), im zahmen Garten lebt. Da diese Funktionen „zahm" sind, ist auch das gesamte daraus gebaute Netz zahm. Und da es zahm ist, kann es nicht unendlich komplex sein. Daher muss es in der Lage sein, aus einer endlichen Menge an Daten zu lernen.

3. Die „unbeschränkte" Überraschung

Normalerweise müssen Mathematiker, wenn sie beweisen, dass ein Netz lernen kann, ein „Geschwindigkeitslimit" für die Zahlen innerhalb des Netzes (die Parameter) festlegen. Sie sagen: „Okay, die Zahlen dürfen nicht größer als 1.000.000 werden."

Diese Arbeit sagt: Sie benötigen kein Geschwindigkeitslimit.
Selbst wenn die Zahlen innerhalb des Netzes unendlich groß werden können (unbeschränkt), lernt es immer noch, solange die Form des Netzes aus diesen „zahmen" Regeln aufgebaut ist. Es ist, als würde man sagen, ein Auto kann so schnell fahren, wie es möchte, aber solange es auf einer gepflasterten Straße bleibt (der zahmen Struktur), wird es schließlich sein Ziel erreichen.

4. Was dies für die Zukunft der KI bedeutet

Die Autoren machen einen sehr wichtigen Punkt darüber, wie wir über KI-Design denken sollten:

Die Verschiebung des „Basiswerts"
In der Vergangenheit versuchten Forscher zu beweisen, dass ihre spezifische neue Architektur „lernbar" war. Sie behandelten Lernbarkeit als einen besonderen Preis, der gewonnen werden musste.

Diese Arbeit sagt: Lernbarkeit ist die Standardeinstellung.
Wenn Sie ein standardmäßiges, festgroßes, feedforward-Netz bauen, ist es garantiert lernbar. Es ist wie Atmen; Sie müssen nicht beweisen, dass Sie atmen können, um am Leben zu sein.

Also, worauf sollten wir uns jetzt konzentrieren?
Da die Frage „Kann es lernen?" nicht mehr die schwierige Frage ist, sollten wir aufhören, uns darum zu sorgen. Stattdessen sollten wir uns auf Folgendes konzentrieren:

Induktive Verzerrung: Hat das Netz die richtige „Intuition" für das spezifische Problem? (z. B. Weiß es, dass eine Katze gleich aussieht, egal ob sie auf dem Kopf steht?)
Symmetrie: Respektiert es die Geometrie der Daten?
Effizienz: Kann es schnell lernen, ohne einen Supercomputer zu benötigen?
Optimierung: Können wir es tatsächlich trainieren, ohne dass es stecken bleibt?

Zusammenfassung

Die Arbeit ist ein mathematisches „Sicherheitsnetz". Sie beweist, dass die chaotische, vielfältige Welt der modernen KI (Transformer, CNNs usw.) tatsächlich auf einem Fundament aus „zahmer" Mathematik aufgebaut ist. Aufgrund dessen sind diese Netze keine magischen Black Boxes, die möglicherweise versagen zu lernen; sie sind mathematisch garantiert in der Lage, aus Daten zu lernen, selbst wenn ihre internen Zahlen riesig werden.

Die Kernaussage: Sorgen Sie sich nicht länger darum, ob Ihre KI lernen kann. Sie kann es. Konzentrieren Sie sich nun darauf, sie besser und schneller lernen zu lassen.

Technische Zusammenfassung: Endliche Stichprobenkomplexität von Feedforward-Neuronalen Netzen in o-minimalen Strukturen

1. Problemstellung

Der Artikel adressiert eine fundamentale Frage der statistischen Lerntheorie: Besitzen alle Standard-Feedforward-Neuronalen Netze mit fester endlicher Architektur eine endliche Stichprobenkomplexität im Probably Approximately Correct (PAC)-Lernmodell?

Während spezifische Architekturfamilien (z. B. stückweise lineare MLPs, bestimmte GNNs oder Transformer) zuvor durch architekturspezifische Argumente (wie VC-Dimension-Schranken für ReLU-Netze) als lernbar nachgewiesen wurden, fehlte eine einheitliche theoretische Garantie, die das breite Spektrum moderner Architekturen – einschließlich solcher mit unbeschränkten Parametern – abdeckt. Die Autoren untersuchen, ob die „zahme" Natur der mathematischen Funktionen, aus denen diese Netze bestehen, ausreicht, um Lernbarkeit zu garantieren, ohne restriktive Gewichtsbeschränkungen aufzuerlegen oder sich auf ad-hoc kombinatorische Beweise für jede neue Architektur zu verlassen.

2. Methodik und Theoretischer Rahmen

2.1 O-minimale Strukturen

Die Kernmethodik stützt sich auf o-minimale Strukturen, ein Konzept aus mathematischer Logik und Modelltheorie. Eine o-minimale Struktur $\mathcal{S}$ , die den reellen Körper erweitert, ist eine Sammlung von Teilmengen von $\mathbb{R}^n$ , die unter booleschen Operationen, Projektionen und kartesischen Produkten abgeschlossen ist, mit der entscheidenden Eigenschaft, dass jede definierbare Teilmenge von $\mathbb{R}$ eine endliche Vereinigung von Punkten und Intervallen ist. Diese „Zähmheit" verhindert die pathologischen Oszillationen, die typischerweise zu unendlichen VC-Dimensionen führen.

Die Autoren nutzen folgende logische Schlüsselwerkzeuge:

Definierbarkeit: Eine Abbildung ist definierbar, wenn ihr Graph eine definierbare Menge innerhalb der Struktur ist.
Gemeinsame Definierbarkeit: Die Autoren zeigen, dass, wenn die primitiven Operationen (Gatter) eines Netzes definierbar sind, die gesamte Netzwerkfunktion gemeinsam in ihren Eingaben und Parametern definierbar ist.
Zellenzerlegung: Ein fundamentaler Satz der o-minimalen Geometrie besagt, dass jede definierbare Menge in eine endliche Anzahl von „Zellen" zerlegt werden kann. Dies impliziert, dass die Anzahl der zusammenhängenden Komponenten von Niveaumengen (Oszillationen) einer definierbaren Funktion unabhängig von den Parameterwerten gleichmäßig beschränkt ist.

2.2 Formalisierung des Netzwerks

Der Artikel definiert ein G-Neuronales Netz als eine Berechnung, die durch einen gerichteten azyklischen Graphen (DAG) organisiert ist.

Knoten: Eingabeknoten, Berechnungsknoten (Gatter) und Ausgabeknoten.
Gatter: Parametrisierte Abbildungen $g: \mathbb{R}^n \times \mathbb{R}^p \to \mathbb{R}^m$ , ausgewählt aus einem „Gatterwörterbuch" $\mathcal{G}$ .
Zusammensetzung: Das Netz berechnet eine Funktion $f_\theta(x)$ , indem es Zustände durch den DAG propagiert, wobei $\theta$ die trainierbaren Parameter darstellt.

Die zentrale technische Erkenntnis ist Proposition 2.5: Wenn jedes Gatter im Wörterbuch $\mathcal{G}$ in einer o-minimalen Struktur $\mathcal{S}$ definierbar ist, dann ist das resultierende G-Neuronale Netz gemeinsam in seinen Eingaben und Parametern definierbar.

3. Hauptbeiträge

3.1 Vereinheitlichte Lernbarkeitstheoreme

Der Artikel liefert zwei Hauptsätze, die eine endliche Stichprobenkomplexität für das agnostische PAC-Setting etablieren:

Satz 3.1 (Klassifikation): Für jede feste endliche Feedforward-Architektur mit definierbaren Schichten hat die Klasse der Klassifikatoren eine endliche VC-Dimension. Folglich konvergiert das empirische Risiko gleichmäßig zum wahren Risiko mit einer Stichprobenkomplexitätsschranke von $O(K \log(1/\delta) / \epsilon^2)$ , wobei $K$ von der Architektur abhängt, aber nicht von der Parameternorm.
Satz 3.2 (Regression): Für Regression mit definierbaren Verlustfunktionen (z. B. geklammertes MSE, MAE) hat die Klasse eine endliche Pseudo-Dimension (und fat-shattering Dimension), was ähnliche Garantien für die gleichmäßige Konvergenz liefert.

Kritische Unterscheidung: Diese Ergebnisse gelten auch dann, wenn der Parameterraum unbeschränkt ist. Traditionelle Argumente mit Überdeckungszahlen scheitern hier oft, da die metrische Größe des Parameterraums divergiert, wenn die Gewichte wachsen. Der o-minimale Ansatz umgeht dies, indem er die geometrische Komplexität (Anzahl der Oszillationen) der Funktionsklasse statt der metrischen Größe des Parameterraums beschränkt.

3.2 Verifikation der Definierbarkeit für moderne Architekturen

Ein erheblicher Teil der Arbeit (Abschnitt 4) verifiziert, dass die „Definierbarkeitsannahme" mild ist, indem nachgewiesen wird, dass Standardkomponenten des Deep Learnings in spezifischen o-minimalen Strukturen (primär $\mathbb{R}_{exp}$ und $\mathbb{R}_{an,exp}$ ) definierbar sind:

Lineare/Convolutional-Schichten: Polynomiale Abbildungen (semi-algebraisch).
Aktivierungsfunktionen: ReLU, LeakyReLU, Sigmoid, Tanh, Softplus, GELU, Swish, SwiGLU und Mish erweisen sich als in $\mathbb{R}_{exp}$ oder $\mathbb{R}_{an,exp}$ definierbar.
Aufmerksamkeitsmechanismen: Multi-Head-Self-Attention und Cross-Attention sind in $\mathbb{R}_{exp}$ definierbar aufgrund der Definierbarkeit der Exponentialfunktion und der Softmax-Funktion.
Normalisierung: Batch-, Layer-, Group- und RMS-Normalisierung sind semi-algebraisch.
Positionscodierungen: Fourier-basierte Codierungen sind definierbar, sofern der Positionsdomäne beschränkt ist (eine Standardbeschränkung in der Praxis).
Erweiterte Blöcke: Residualverbindungen, Gating-Mechanismen, Maxout und Deep Equilibrium (DEQ)-Schichten erweisen sich als erhaltend für die Definierbarkeit.

3.3 Architektonische Korollarien

Durch die Kombination der Definierbarkeit der Primitiven mit den Abgeschlossenheitseigenschaften o-minimaler Strukturen leiten die Autoren ab, dass die folgenden Standardarchitekturen eine endliche Stichprobenkomplexität besitzen:

Multilayer Perceptrons (MLPs)
Convolutional Neural Networks (CNNs)
Graph Neural Networks (GNNs)
Transformer (einschließlich solcher mit festen Sequenzlängen)

4. Ergebnisse und Bedeutung

4.1 Hauptergebnis

Der Artikel kommt zu dem Schluss, dass verteilungsfreie Lernbarkeit eine universelle Konsequenz zahmer Feedforward-Berechnungen ist. Jede feste endliche Feedforward-Architektur, die aus definierbaren Primitiven konstruiert ist (was die überwiegende Mehrheit moderner nicht-rekurrenter Modelle abdeckt), besitzt im agnostischen PAC-Setting eine endliche Stichprobenkomplexität, unabhängig von Parametergrenzen.

4.2 Perspektivwechsel

Die Autoren argumentieren, dass dieses Ergebnis die endliche Stichprobenkomplexität von einem „Unterscheidungsmerkmal" zu einer Basis-Eigenschaft verschiebt.

Bisherige Sicht: Lernbarkeit wurde oft als eine fragile Eigenschaft betrachtet, die spezifische architektonische Beschränkungen oder Aktivierungsfunktionen erfordert, um sie zu beweisen.
Neue Sicht: Lernbarkeit ist für jedes „zahme" Feedforward-Modell automatisch gegeben. Daher sollte sich der theoretische Fokus davon verlagern, ob ein Modell lernt, hin zum Verständnis, wie es lernt.

4.3 Praktische Implikationen

Der Artikel schlägt vor, dass Architekturvergleiche durch feinere Kriterien geleitet werden sollten als durch allgemeine Lernbarkeit:

Induktive Verzerrungen: Wie gut die Architektur problemspezifische Symmetrien und geometrische Prioritäten kodiert.
Optimierungsverhalten: Die Landschaft der Verlustfunktion und Konvergenzeigenschaften.
Skalierbarkeit: Rechenleistung und Fähigkeit, wachsende Modellgrößen zu bewältigen.

4.4 Einschränkungen

Die Autoren weisen ausdrücklich auf den Geltungsbereich und die Einschränkungen hin:

Feste Architektur: Die Ergebnisse gelten für feste Tiefe, Breite und Graphgröße. Sie liefern keine gleichmäßigen Schranken für wachsende Modellgrößen.
Keine Rekurrenz: Echte rekurrente Architekturen (RNNs, geschleifte Transformer) sind nicht abgedeckt, es sei denn, sie werden auf einen festen Zeithorizont entrollt.
Qualitativer Charakter: Die Schranken sind qualitativ (Existenz von Konstanten) und liefern keine scharfen, architekturspezifischen Raten.
Optimierung: Der Artikel garantiert Lernbarkeit (Existenz einer guten Hypothese), macht aber keine Aussagen über die Effizienz, diese zu finden (Optimierungsgarantien).

5. Fazit

Der Artikel stellt fest, dass die mathematische „Zähmheit" moderner neuronaler Netze, formalisiert durch o-minimale Strukturen, ausreicht, um eine endliche Stichprobenkomplexität zu garantieren. Dies vereinheitlicht die Lerntheorie diverser Architekturen unter einem einzigen Rahmen und legt nahe, dass die Fähigkeit zu lernen ein generisches Merkmal der Feedforward-Berechnung ist und keine spezielle Eigenschaft spezifischer Designs. Die Autoren schließen, dass sich zukünftige Forschung auf die spezifischen induktiven Verzerrungen und Optimierungsdynamiken konzentrieren sollte, die Architekturen unterscheiden, und nicht auf ihre fundamentale Lernfähigkeit.