🤖 machine learning

Quantitative Approximation Rates for Group Equivariant Learning

Diese Arbeit schließt die Lücke in der Approximationstheorie, indem sie quantitative Approximationsraten für verschiedene gruppequivariante Architekturen herleitet und zeigt, dass das Einbetten von Symmetrien die Ausdrucksstärke von neuronalen Netzen nicht verringert.

Ursprüngliche Autoren: Jonathan W. Siegel, Snir Hordan, Hannah Lawrence, Ali Syed, Nadav Dym

Veröffentlicht 2026-04-17

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Jonathan W. Siegel, Snir Hordan, Hannah Lawrence, Ali Syed, Nadav Dym

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

Die große Frage: Brauchen wir spezielle Werkzeuge für spezielle Aufgaben?

Stell dir vor, du bist ein Architekt, der Häuser bauen soll.

Das normale Haus: Du kannst jedes beliebige Haus bauen, indem du Ziegelsteine (Neuronen) beliebig anordnest. Das ist ein ganz normales, tiefes neuronales Netz.
Das spezielle Haus: Du sollst ein Haus bauen, das sich immer gleich anfühlt, egal ob du es drehst, verschiebst oder die Möbel im Raum vertauschst. Ein Beispiel: Ein Bild eines Hundes ist immer ein Hund, egal ob du es drehst (Rotation) oder den Hund nach links schiebst (Translation).

In der Welt der Künstlichen Intelligenz (KI) nennen wir diese Eigenschaft Equivarianz (Ähnlichkeit bei Veränderung) oder Invarianz (Unveränderlichkeit).

Die Forscher in diesem Papier stellen sich eine sehr wichtige Frage:

„Wenn wir die KI zwingen, diese speziellen Regeln (Symmetrien) von Anfang an zu befolgen, wird sie dann schlauer oder effizienter beim Lernen, als wenn wir ihr erlauben, alles chaotisch zu lernen?"

Man dachte lange, dass man für solche speziellen Aufgaben (wie das Erkennen von Objekten in 3D-Räumen oder das Analysieren von Molekülen) spezielle, „symmetrische" Netzwerke braucht, um gut zu funktionieren.

Die Entdeckung: Der „Universal-Apparat" ist genauso stark

Die Forscher haben herausgefunden, dass die Antwort überraschend einfach ist: Nein, die speziellen Netzwerke sind nicht „intelligenter" im Sinne von Ausdrucksstärke.

Stell dir vor, du hast zwei Werkzeuge:

Einen riesigen, flexiblen Knetmasse-Klumpen (das normale Netz), aus dem du alles formen kannst.
Eine spezielle Schablone (das symmetrische Netz), die dir nur erlaubt, Dinge zu formen, die von bestimmten Regeln erfüllt sind.

Die Studie zeigt: Wenn du einen α-Hölder-Funktion (eine mathematische Art, „glatte" und vorhersehbare Muster zu beschreiben) nachbauen willst, brauchst du genau die gleiche Menge an Knete (Parameter) für beide Werkzeuge.

Das bedeutet:

Ein normales Netz kann die Symmetrien lernen, wenn es genug Daten hat.
Ein symmetrisches Netz ist nicht „magisch" besser darin, die Form zu erkennen. Es ist nur geordneter.

Die drei Szenarien der Studie

Die Autoren haben drei verschiedene „Welten" untersucht, um das zu beweisen:

1. Die Welt der vertauschbaren Punkte (Permutationen)

Stell dir einen Sack mit Murmeln vor. Es ist egal, in welcher Reihenfolge du die Murmeln herausnimmst; der Inhalt des Sacks ist derselbige.

Das Problem: Wie lernt eine KI, dass die Murmeln 1, 2 und 3 dasselbe sind wie 3, 1 und 2?
Die Lösung: Das berühmte Deep Sets-Modell. Es nimmt jede Murmel einzeln, macht etwas damit und summiert dann alles auf.
Das Ergebnis: Diese einfache Summen-Methode ist genauso gut darin, komplexe Muster zu erkennen, wie ein riesiges, kompliziertes Netz, das jede einzelne Murmel mit jeder anderen vergleicht. Die „Schablone" ist nicht schlechter als der „Klumpen".

2. Die Welt der drehbaren Objekte (Rigid Motions)

Stell dir einen 3D-Scan eines Autos vor. Egal, wie du das Auto drehst oder verschiebst, es bleibt ein Auto.

Das Problem: Hier ist die Mathematik viel schwieriger. Die „Schablone" muss wissen, wie man das Auto in eine Standardposition dreht, bevor man es analysiert.
Die Lösung: Die Forscher nutzen eine Technik namens Frame Averaging (Rahmen-Mittelung). Stell dir vor, du hast viele verschiedene Kamerawinkel, um das Auto zu fotografieren, und bildest dann den Durchschnitt.
Das Ergebnis: Auch hier gilt: Ein normales Netz könnte das auch lernen, wenn es groß genug ist. Aber das spezielle Netz, das die Drehungen von Hand berechnet, erreicht das gleiche Ziel mit der gleichen Anzahl an Bausteinen. Es ist also keine „Super-KI", sondern eine „effiziente KI".

3. Die Welt der strengen Regeln (Bi-Lipschitz Modelle)

Hier geht es um Modelle, die garantieren, dass kleine Änderungen im Input nur kleine Änderungen im Output bewirken (wie ein stabiles Seil, das nicht reißt).

Das Ergebnis: Selbst bei diesen sehr strengen mathematischen Regeln gilt: Die spezielle Architektur verliert keine „Kreativität" oder Ausdruckskraft im Vergleich zu einem normalen Netz.

Die große Metapher: Der Koch und das Rezept

Stell dir vor, du willst einen perfekten Kuchen backen (die Funktion approximieren).

Das normale Netz ist wie ein Koch, der alles aus dem Gedächtnis und durch Ausprobieren macht. Er kann jeden Kuchen backen, aber er muss vielleicht 1000 Versuche machen, um zu verstehen, dass der Kuchen egal ist, ob du ihn um 90 Grad drehst.
Das symmetrische Netz ist wie ein Koch, der ein Rezept hat, das sagt: „Dreh den Kuchen nicht, er ist symmetrisch."

Die Studie sagt: Beide Köche brauchen die gleiche Menge an Zutaten (Parameter), um den perfekten Kuchen zu backen.

Der Unterschied liegt nicht darin, was sie backen können (die Ausdrucksstärke), sondern darin, wie schnell sie es lernen und wie wenig Daten sie dafür brauchen.

Das symmetrische Netz braucht weniger Daten (Sample Efficiency), weil es nicht erst lernen muss, dass Drehen egal ist. Es weiß es schon.
Das normale Netz braucht mehr Daten, um das zu lernen, aber wenn es genug Daten hat, ist das Ergebnis am Ende genauso gut.

Fazit für den Alltag

Warum ist das wichtig?

Kein Verlust an Kraft: Wenn du eine spezielle KI für eine Aufgabe mit Symmetrien (wie Bilderkennung oder Molekülanalyse) baust, musst du keine Angst haben, dass du durch die „Einschränkung" der Symmetrie die Leistung verlierst. Du verlierst keine Magie.
Der wahre Vorteil: Der Vorteil dieser speziellen Modelle liegt in der Effizienz. Sie lernen schneller und brauchen weniger Daten, weil sie nicht raten müssen. Sie sind wie ein gut organisiertes Werkzeug, das schneller zum Ziel führt, aber nicht „magisch" stärker ist als ein unordentliches Werkzeug, das genug Zeit hat.

Kurz gesagt: Symmetrie ist ein cleverer Trick, um Daten zu sparen, aber kein Zauberstab, um die Grenzen der Mathematik zu sprengen.

1. Problemstellung

Das universelle Approximations-Theorem besagt, dass neuronale Netze beliebige stetige Funktionen auf kompakten Mengen approximieren können. Allerdings liefert dieses Theorem keine quantitativen Aussagen darüber, wie groß das Netzwerk (Anzahl der Parameter) sein muss, um eine bestimmte Genauigkeit $\epsilon$ zu erreichen. Bisherige Arbeiten haben diese Approximationsraten für tiefe ReLU-Netze auf klassischen glatten Funktionenräumen (z. B. $\alpha$ -Hölder-Funktionen) für den allgemeinen Fall untersucht. Die Raten hängen typischerweise exponentiell von der Dimension des Eingaberaums $N$ ab, nämlich $\sim (1/\epsilon)^{N/2\alpha}$ .

In vielen maschinellen Lernanwendungen (z. B. Bilderkennung, Punktwolken, Graphen) besitzen die zu lernenden Funktionen jedoch spezifische Symmetrien (Invarianz oder Äquivarianz) bezüglich einer Gruppe $G$ (z. B. Permutationen, Rotationen, Translationen). Die zentrale Fragestellung dieses Papers ist:

Kann die Annahme der Invarianz/Äquivarianz die Approximationsrate für allgemeine ReLU-Netze verbessern, indem die Abhängigkeit von der Dimension des Eingaberaums $N$ durch die Dimension des Quotientenraums $N_G = \dim(V/G)$ ersetzt wird?
Können moderne, von Grund auf symmetrisch konstruierte Architekturen (wie Deep Sets, Transformer, Frame-Averaging) diese verbesserten Raten tatsächlich erreichen?

Bisherige Forschung konzentrierte sich stark auf die Universalität (Existenz einer Approximation), lieferte aber kaum quantitative Raten für äquivariante Modelle.

2. Methodik und Vorgehensweise

Die Autoren analysieren die Approximationsraten für $\alpha$ -Hölder-stetige Funktionen $f: [0,1]^N \to \mathbb{R}$ , die unter der Wirkung einer Gruppe $G$ invariant oder äquivariant sind. Sie betrachten drei Hauptsettings:

Permutations-invariante und -äquivariante Modelle:
- Deep Sets: Analyse der Architektur $\rho(\sum \Phi(x_i))$ .
- Sumformer & Transformer: Erweiterung der Ergebnisse auf äquivariante Funktionen.
- Technischer Kern: Die Autoren konstruieren eine diskrete Approximation des Eingaberaums durch Unterteilung in Zellen. Sie nutzen eine spezielle Technik, die auf dem Kolmogorov-Arnold-Superpositionstheorem basiert, um diskontinuierliche Charakteristikfunktionen durch ReLU-Netze zu approximieren. Ein entscheidender Schritt ist die Verwendung mehrerer verschobener Partitionen der Einheit, um sicherzustellen, dass für jeden Eingabepunkt mindestens eine Partition „gut" (d.h. diskret) ist. Das Ergebnis wird durch eine Median-Operation über mehrere Netze stabilisiert.
Invarianz gegenüber Permutationen und starren Bewegungen (Rigid Motions):
- Hier wird die Gruppe $G = E(d) \times S_n$ betrachtet (Rotationen/Translationen und Permutationen).
- Methode: Die Autoren nutzen die Gram-Schmidt-Orthogonalisierung, um einen Orthonormalbasis-Rahmen (Frame) aus den Punktwolken zu extrahieren. Da die Funktion invariant gegenüber Rotationen ist, kann sie auf einem niedrigerdimensionalen Unterraum (dem Quotientenraum) approximiert werden.
- Herausforderung: Die Gram-Schmidt-Prozedur ist nicht überall stabil (bei linear abhängigen Vektoren). Die Autoren beweisen die Stabilität der Gram-Schmidt-Approximation durch ReLU-Netze unter Verwendung von „Super-Approximation" für Polynome, rationale Funktionen und Wurzeln (Lemma 14).
- Frame-Averaging: Sie zeigen, dass die Anwendung von Frame-Averaging auf ein Deep-Set-Rückgrat die gewünschten Raten erhält, indem sie die Approximation auf den Quotientenraum reduzieren.
Bi-Lipschitz-invariante Modelle:
- Betrachtung allgemeiner geschlossener Isometriegruppen.
- Methode: Nutzung von bi-Lipschitz-invarianten Einbettungen $E: V \to \mathbb{R}^m$ (z. B. Max-Filter, Sortierung, Fourier-Sliced-Wasserstein). Da $E$ eine bi-Lipschitz-Abbildung ist, ist die Approximation von $f$ äquivalent zur Approximation von $\tilde{f} \circ E^{-1}$ auf dem Bild des Quotientenraums. Dies ermöglicht die Anwendung bekannter Approximationsergebnisse für nicht-invariante Netze auf den intrinsischen Dimension des Quotientenraums.

3. Wichtige Beiträge und Ergebnisse

Die Hauptergebnisse sind in Tabelle 1 des Papers zusammengefasst und lassen sich wie folgt zusammenfassen:

Optimale Raten für ReLU-Netze: Die Autoren beweisen, dass selbst nicht-invariante ReLU-Netze die optimale Approximationsrate von $\sim (1/\epsilon)^{N_G/2\alpha}$ erreichen können, wobei $N_G$ die Dimension des Quotientenraums (intrinsische Dimension) ist. Dies widerlegt die Annahme, dass Symmetrien nur durch spezielle Architekturen effizient genutzt werden können.
Deep Sets und Permutationsinvarianz: Es wird gezeigt, dass die Deep-Set-Architektur $\rho(\sum \Phi(x_i))$ die optimale Rate $\sim (1/\epsilon)^{nd/2\alpha}$ für $\alpha$ -Hölder-Funktionen auf Punktwolken erreicht. Dies widerlegt frühere Vermutungen (z. B. von Zweig und Bruna), dass Deep Sets aufgrund des Fehlens von Paar-Interaktionen suboptimale Raten haben.
Äquivariante Architekturen (Sumformer/Transformer): Es wird bewiesen, dass Sumformer und Transformer-Architekturen die gleichen Approximationsraten wie Deep Sets für äquivariante Funktionen erreichen.
Rotationen und Starre Bewegungen: Für Funktionen, die invariant gegenüber $E(d) \times S_n$ sind, wird gezeigt, dass Modelle, die auf Frame-Averaging basieren (kombiniert mit Deep Sets), die Rate $\sim (1/\epsilon)^{(nd - \dim(E(d)))/2\alpha}$ erreichen.
Bi-Lipschitz-Modelle: Für allgemeine bi-Lipschitz-invariante Modelle (z. B. Max-Filter) wird eine Rate von $\sim (1/\epsilon)^{d_{\text{intrinsic}}/2\alpha}$ bewiesen.
Verbesserung bei intrinsischer Dimension: Als Nebenprodukt verbessern die Autoren die bekannten Approximationsraten für Funktionen auf Mannigfaltigkeiten mit niedriger intrinsischer Dimension $d_{\text{intrinsic}}$ von $\sim \epsilon^{-d_{\text{intrinsic}}/\alpha}$ auf $\sim \epsilon^{-d_{\text{intrinsic}}/2\alpha}$ .

4. Signifikanz und Implikationen

Ausdrucksstärke vs. Optimierung: Das wichtigste Ergebnis ist, dass das „Hard-Coding" von Symmetrien in die Architektur keinen Verlust an Ausdrucksstärke (Expressivity) oder Approximationskraft für invarianten Funktionen im asymptotischen Sinne bedeutet. Ein gleich großes, nicht-invariantes ReLU-Netzwerk kann die gleiche Genauigkeit erreichen wie ein spezialisiertes invariantes Modell.
Praktische Vorteile: Da die asymptotischen Raten gleich sind, deuten die praktischen Vorteile von äquivarianten Modellen (bessere Generalisierung, geringerer Stichprobenbedarf) nicht auf eine höhere theoretische Kapazität zurück, sondern auf Effizienz in der Optimierung und Stichprobeneffizienz. Die eingeschränkte Parametrisierung führt zu einem einfacheren Suchraum und robusterem Lernen.
Theoretische Lücke geschlossen: Das Paper schließt die Lücke zwischen der bekannten Universalität äquivarianter Modelle und deren quantitativen Approximationsraten. Es liefert die ersten rigorosen Raten für prominente Architekturen wie Deep Sets, Transformer und Frame-Averaging-Modelle.
Zukünftige Richtungen: Die Autoren weisen darauf hin, dass die Analyse für spezifische moderne Modelle wie EGNN oder Dimenet noch aussteht und dass asymptotische Raten möglicherweise zu grob sind, um subtile Unterschiede zwischen Modellen bei realistischen Größenordnungen zu erfassen.

Zusammenfassend etabliert das Paper, dass die Einbeziehung von Symmetrien in neuronale Netze primär ein Werkzeug zur Verbesserung der Lernbarkeit und Generalisierung ist, nicht jedoch eine Notwendigkeit, um die theoretische Approximationsgrenze für symmetrische Funktionen zu erreichen.