🤖 machine learning

Sample Complexity of Scientific Discovery: PAC Learnability of Compositional Function Trees

Diese Arbeit stellt fest, dass die Stichprobenkomplexität des Lernens kompositorischer Funktionbäume für die wissenschaftliche Entdeckung durch die Baumtiefe und die Lipschitz-Konstanten der Operatoren bestimmt wird, anstatt durch die kombinatorische Explosion symbolischer Strukturen, wobei sie PAC-lernbarkeitsschranken sowie eine empirische Validierung liefert, wonach die Generalisierungslücke mit $\mathcal{O}(L^d/\sqrt{n})$ skaliert.

Ursprüngliche Autoren: Şuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem Yalçın

Veröffentlicht 2026-06-30

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Şuayp Talha Kocabay, Talha Rüzgar Akkuş, Kerem Yalçın

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, einem Computer beizubringen, die „Gesetze der Physik“ (wie $F=ma$ oder wie Gravitation funktioniert) zu entdecken, indem er lediglich einen Haufen von Datenpunkten betrachtet. Normalerweise verwenden Wissenschaftler eine Methode namens Symbolische Regression. Anstatt dem Computer ein Black-Box-Neuronales Netz zu geben, bitten sie ihn, eine Formel aus einem bestimmten Satz von Lego-Steinen zu bauen: grundlegende mathematische Operationen wie Addition ( $+$ ), Multiplikation ( $\times$ ), Sinus ( $\sin$ ) und Exponenten ( $e^x$ ).

Das große Problem war bisher: „Es gibt zu viele Möglichkeiten, diese Legos zu stapeln!“

Wenn man 10 Steine tief stapelt, explodiert die Anzahl der möglichen Strukturen in die Milliarden. Lange Zeit glaubten die Menschen, dass dies bedeutete, dass der Computer eine unmögliche Menge an Daten bräuchte, um die richtige Formel zu lernen. Sie glaubten, dass die „statistische Kostenlast“ (die benötigte Datenmenge) exponentiell mit der Tiefe der Formel wachsen würde.

Dieses Paper sagt: „Nicht unbedingt.“

Hier ist die einfache Aufschlüsselung dessen, was die Autoren herausgefunden haben, unter Verwendung alltäglicher Analogien:

1. Der „Lego-Turm“ vs. der „Wackelige Stapel“

Stellen Sie sich das Bauen einer Formel wie das Stapeln eines Turms aus Lego-Steinen vor.

Die alte Angst: Die Leute dachten, weil es so viele verschiedene Formen von Türmen gibt, die man bauen könnte, würde der Computer verwirrt werden und Millionen von Datenpunkten benötigen, um herauszufinden, welche davon richtig ist.
Die neue Erkenntnis: Die Autoren argumentieren, dass die Schwierigkeit nicht darin liegt, wie viele Formen existieren. Es geht darum, wie stabil der Turm ist.

Wenn Sie einen Turm bauen, bei dem jeder Stein wackelig und rutschig ist (mathematisch gesehen, wenn die Operationen „instabil“ sind oder hohe Lipschitz-Konstanten haben), könnte der ganze Turm bei einer winzigen Änderung des Inputs zusammenbrechen oder wild schwanken.

Die Behauptung des Papers: Wenn Ihre Lego-Steine stabil und fest sind (mathematisch „Lipschitz“), dann erfordert selbst ein sehr hoher Turm (eine tiefe Formel) nicht zwangsläufig eine massive Menge an Daten, um gelernt zu werden. Die „statistischen Kosten“ hängen davon ab, wie sehr der Turm wackelt, und nicht nur davon, wie viele verschiedene Türme Sie hätten bauen können.

2. Der „Ripple-Effekt“ (Tiefe und Komplexität)

Die Autoren beweisen, dass die „Komplexität“ der Formel auf eine bestimmte Weise wächst:

Tiefe ( $d$ ): Wie viele Schichten von Mathematik sind übereinander gestapelt.
Stabilität ( $L$ ): Wie sehr jede mathematische Operation kleine Fehler verstärkt.

Sie fanden heraus, dass die Schwierigkeit des Lernens etwa wie $L^d / \sqrt{n}$ skaliert:

$L^d$ : Wenn Ihre Steine etwas wackelig sind ( $L > 1$ ), bewirkt das Stapeln dieser Steine in der Tiefe ( $d$ ), dass sich das Wackeln vervielfacht. Das sind die „schlechten Nachrichten“.
$\sqrt{n}$ : Aber, wenn Sie dem Computer mehr Daten ( $n$ ) geben, wird das Lernen einfacher. Je mehr Daten Sie haben, desto mehr können Sie das Wackeln glätten.

Die Analogie: Stellen Sie sich vor, Sie versuchen, einen Stapel von 10 Büchern zu balancieren.

Wenn die Bücher rutschig sind (hohes $L$ ), brauchen Sie eine sehr ruhige Hand (viele Daten), um sie vor dem Umfallen zu bewahren.
Wenn die Bücher Gummigrip haben (niedriges $L$ , stabil), können Sie sie mit weniger Aufwand höher stapeln.
Das Paper zeigt, dass man nicht automatisch eine „magische Menge“ an Daten braucht, nur weil der Stapel hoch ist; man braucht nur genug Daten, um das Rutschen der spezifischen Bücher, die man verwendet, entgegenzuwirken.

3. Das „Physiklabor“-Experiment

Um zu beweisen, dass dies nicht nur Mathematik auf dem Papier war, bauten die Autoren ein Computerprogramm, das wie ein Wissenschaftler in einem Labor agiert:

Sie erstellten fiktive „Physik-Daten“ (wie einen Ball, der einen Hügel hinunterrollt) mit bekannten Formeln unterschiedlicher Tiefen (1 Schicht, 2 Schichten, bis zu 4 Schichten).
Sie trainierten ihren „Lego-Builder“ mit kleinen Mengen an Daten (50 bis 5.000 Beispiele).
Das Ergebnis: Sie maßen, wie gut der Computer die Formel auf neue Daten errät, die er noch nicht gesehen hatte (die „Generalisierungslücke“ bzw. den „Generalization Gap“).

Sie fanden heraus, dass die Fehler des Computers exakt ihrer Vorhersage entsprachen:

Wenn die Formel tiefer war oder „rutschige“ Mathematik verwendete (wie $e^x$ ), wurden die Fehler größer.
Wenn sie mehr Daten hinzufügten, wurden die Fehler kleiner, genau wie ihre Formel es vorhersagte.

4. Was das für die „Wissenschaftliche Entdeckung“ bedeutet

Das Paper kommt zu dem Schluss, dass Symbolische Regression selbst für tiefe Formeln statistisch „lernbar“ ist, vorausgesetzt, die verwendeten mathematischen Operationen sind stabil.

Die gute Nachricht: Wir brauchen keine unendlichen Daten, um wissenschaftliche Gesetze zu entdecken. Wenn die Gesetze, nach denen wir suchen, aus stabiler, glatter Mathematik bestehen, kann ein Computer sie mit einer vernünftigen Menge an Daten finden.
Der Haken: Das Paper sagt nicht, dass es einfach ist, die Formel zu finden. Es sagt nur, dass es möglich ist, sie zu lernen, sobald man die richtige Struktur hat. Der „schwere Teil“, also die Suche durch Milliarden möglicher Lego-Formen, bleibt ein Problem der Computergeschwindigkeit, nicht ein Datenproblem.

Zusammenfassend:
Das Paper sagt uns, dass die „statistische Schwierigkeit“, wissenschaftliche Formeln zu entdecken, nicht von der schieren Anzahl der möglichen Formeln abhängt. Es geht darum, wie „wackelig“ die Mathematik ist. Wenn die Mathematik stabil ist, können wir tiefe, komplexe Gesetze selbst mit relativ kleinen Datensätzen entdecken. Der Computer braucht nur genug Daten, um den wackeligen Turm vor dem Umfallen zu bewahren.

Technisches Resümee: Stichprobenkomplexität der wissenschaftlichen Entdeckung

Problemstellung
Wissenschaftliche Entdeckung mittels symbolischer Regression (SR) wird häufig als statistisch und rechnerisch unpraktikabel charakterisiert. Die vorherrschende Ansicht legt nahe, dass der Hypothesenraum symbolischer Ausdrücke mit der Tiefe kombinatorisch wächst, was die Suche nach optimalen Ausdrücken zu einem NP-schweren Problem macht und die statistische Generalisierung solcher Modelle unzuverlässig werden lässt. Dieses Paper stellt die Verwechslung von rechnerischer Komplexität mit statistischer Lernbarkeit in Frage. Es postuliert, dass die statistische Generalisierung von kompositorischen Funktionbäumen gutartig sein kann, wenn die zugrunde liegenden Operatoren Stabilitätseigenschaften besitzen, auch wenn das Finden der optimalen symbolischen Struktur rechnerisch schwierig ist. Die zentrale Frage lautet, ob die Stichprobenkomplexität des Lernens kompositorischer Operatorbäume exponentiell mit der Tiefe explodiert oder ob sie stattdessen durch die Stabilität (Lipschitz-Stetigkeit) der Operatoren und die Tiefe des Baumes kontrolliert wird.

Methodik
Die Autoren nähern sich dem Problem aus der Perspektive der PAC-Lerntheorie (Probably Approximately Correct), wobei sie die Rademacher-Komplexität nutzen, um den Generalisierungsfehler zu begrenzen.

Definition des Hypothesenraums: Die Studie definiert einen kompositorischen Hypothesenraum, $H^d_{comp}$ , bestehend aus verwurzelten Operatorbäumen der Tiefe $d$ . Die internen Knoten werden aus einem endlichen Vokabular glatter, differenzierbarer Operatoren ( $H_{base}$ ) gezogen, wie etwa $\{+, \times, \sin, \cos, \exp\}$ und affine Abbildungen. Die Blätter sind entweder Eingabekoordinaten oder beschränkte affine Funktionen.
Theoretischer Rahmen:
- Lipschitz-Annahmen: Die Analyse setzt voraus, dass die Basisloper auf den relevanten Datenbereichen lokal Lipschitz-stetig mit Konstanten $L_h$ sind. Eine globale Lipschitz-Konstante $L = \max L_h$ wird zur Begrenzung verwendet.
- Rademacher-Komplexität: Die Autoren leiten Schranken für die empirische Rademacher-Komplexität, $R_n(H^d_{comp})$ , ab. Sie erweitern klassische Kontraktionsargumente (Ledoux & Talagrand, 1991) und Vektor-Kontraktionsungleichungen (Maurer, 2016) auf baumstrukturierte Kompositionen.
- Rekursive Schranken: Durch Anwendung einer Union Bound über das endliche Operator-Vokabular ( $K = |H_{base}|$ ) und unter Nutzung der Vektor-Kontraktion für die Komposition von $b$ Kindern (wobei $b$ die Arität ist), etablieren die Autoren eine rekursive Beziehung zwischen der Komplexität der Tiefe $d$ und der Tiefe $d-1$ .
Experimentelle Validierung:
- Synthetische Daten: Die Autoren konstruierten eine modulare PyTorch-Codebasis, um synthetische „physikähnliche“ Targets mit kontrollierten Tiefen ( $d \in \{1, 2, 3, 4\}$ ) und bekannten Ground-Truth-Strukturen zu generieren.
- Differenzierbare Bäume: Anstatt genetische Programmierung oder diskrete Suche zu verwenden, trainierten sie differenzierbare Operatorbäume (keine MLPs) mittels Gradientenabstieg (Adam), um die Koeffizienten der Operatoren anzupassen.
- Metriken: Sie maßen die Generalisierungslücke (Test-MSE abzüglich Train-MSE) und verglichen diese mit dem theoretischen Komplexitätsterm $(bL^d)/\sqrt{n}$ , wobei $\hat{L}$ ein empirischer Schätzer der Lipschitz-Konstante ist, der aus den Gradientennormen abgeleitet wurde.

Zentrale Beiträge

Statistische Lernbarkeit von SR: Das Paper beweist, dass die Generalisierungsfähigkeit kompositorischer Bäume nicht zwangsläufig exponentiell mit der Anzahl der unterschiedlichen symbolischen Strukturen ansteigt. Stattdessen wird sie durch die Tiefe $d$ und die Lipschitz-Konstanten der Operatoren bestimmt.
Explizite Komplexitätsschranken: Die Autoren leiten eine konkrete obere Schranke für die Rademacher-Komplexität ab:
$R_n(H^d_{comp}) \leq (K \cdot b \sqrt{2} L)^{d-1} R_n(H^1_{comp})$
Folglich skaliert das exzessive Risiko als $O(L^d / \sqrt{n})$ , wenn die Vokabulargröße $K$ und die Arität $b$ als Konstanten behandelt werden. Dies steht im Gegensatz zu Schranken, die von der Kardinalität des diskreten Syntaxraums abhängen.
Trennung von Suche und Schätzung: Die Arbeit trennt formal das diskrete Optimierungsproblem (Suche nach der Baumstruktur) vom kontinuierlichen Regressionsproblem (Anpassung der Koeffizienten). Die abgeleiteten Schranken gelten für letzteres und klären, welche statistische Skalierung zu erwarten ist, sobald eine Struktur vorgeschlagen wurde.
Empirische Korrelation: Die Experimente zeigen eine positive Korrelation zwischen der beobachteten Generalisierungslücke und dem vorhergesagten Komplexitätsterm $(bL^d)/\sqrt{n}$ . Die Daten zeigen, dass während die Lücke mit der Tiefe zunimmt (aufgrund der Akkumulation von Lipschitz-Konstanten) und mit der Stichprobengröße abnimmt ( $1/\sqrt{n}$ ), die Skalierung mit der theoretischen Vorhersage übereinstimmt.

Ergebnisse

Theoretisch: Theorem 4.9 etabliert, dass für beschränkte Outputs und Lipschitz-stetige Operatoren das exzessive Risiko als $1/\sqrt{n}$ abfällt, wobei der Konstantenfaktor exponentiell von der Tiefe über das Produkt der Lipschitz-Konstanten abhängt. Korollar 4.11 übersetzt dies in eine PAC-Stichprobenkomplexitäts-Schranke und zeigt, dass die Stichprobenkomplexität mit $L^{2d}$ skaliert, anstatt mit der kombinatorischen Anzahl der Bäume.
Empirisch: Über 400 experimentelle Durchläufe mit variierenden Tiefen ( $d$ $d$ ) und Stichprobengrößen ( $n$ $n$ ) hinweg wurde festgestellt, dass die Generalisierungslücke dem theoretischen Term folgt.
- Bei geringen Tiefen ( $d=1, 2$ ) blieb der Lipschitz-Proxy $\hat{L}$ stabil, und die Lücke skalierte primär mit $1/\sqrt{n}$ .
- Bei tieferen Kompositionen ( $d=3, 4$ ), die Nichtlinearitäten wie $\exp$ beinhalteten, stieg $\hat{L}$ an, was zu größeren Lücken führte – konsistent mit der multiplikativen Akkumulation von Stabilitätskonstanten.
- Ein Power-Law-Fit auf Log-Log-Skalen ergab eine Korrelation von 0,48, was darauf hindeutet, dass der kompositorische Komplexitätsterm einen bedeutsamen Teil der Varianz der Generalisierungslücken erfasst, wenngleich auch andere Faktoren (Optimierungsfehler, Rauschen) eine Rolle spielen.

Bedeutung und Behauptungen
Das Paper behauptet, ein „Lernbarkeits-Zertifikat“ für die wissenschaftliche Entdeckung mittels symbolischer Regression bereitzustellen. Seine primäre Bedeutung liegt im Wechsel der Perspektive von der kombinatorischen Explosion symbolischer Strukturen hin zur kompositorischen Stabilität der Operatoren.

Machbarkeit der Entdeckung bei kleinen Datensätzen: Die Autoren argumentieren, dass für stabile Operator-Vokabulare und moderate Tiefen die wissenschaftliche Entdeckung aus kleinen Datensätzen statistisch machbar ist. Die statistische Generalisierung ist nicht der Flaschenhals; vielmehr bleibt die Herausforderung in der rechnerischen Suche über Strukturen und dem Design induktiver Biases.
Klärung der Skalierung: Die Arbeit klärt, dass die statistische Skalierung der nichtlinearen Koeffizientenschätzung durch die Akkumulation von Lipschitz-Konstanten entlang des Rechengraphen bestimmt wird und nicht durch die Enumeration möglicher Baumformen.
Einschränkungen: Die Autoren merken bescheiden an, dass ihre Garantien uniforme Schranken sind und strukturelle Priors (wie Occam’s Razor) nicht so effektiv nutzen wie etwa PAC-Bayes-Ansätze. Zudem basiert die empirische Validierung auf kontrollierten, in-distribution synthetischen Daten mit eindimensionalen Inputs; das Verhalten unter Verteilungsshifts oder Fehlspezifikationen wird durch diese Schranken nicht garantiert. Der Schätzer $\hat{L}$ misst die Stabilität auf der angepassten Abbildung und zertifiziert keine globale Worst-Case-Konstante.

Zusammenfassend lässt sich sagen, dass das Paper behauptet, dass symbolische Regressionsmodelle, wenn sie als kompositorische Funktionsbäume mit stabilen Primitiven betrachtet werden, günstige statistische Eigenschaften besitzen, die eine Generalisierung selbst mit begrenzten Daten ermöglichen, sofern Tiefe und Stabilität der Operatoren kontrolliert werden.

1. Der „Lego-Turm“ vs. der „Wackelige Stapel“

2. Der „Ripple-Effekt“ (Tiefe und Komplexität)

3. Das „Physiklabor“-Experiment

4. Was das für die „Wissenschaftliche Entdeckung“ bedeutet

Mehr davon