📊 statistics

An Optimal Agnostic PAC Algorithm

Dieses Paper präsentiert einen agnostischen PAC-Lernalgorithmus für die binäre Klassifikation, der eine statistisch optimale Risikogrenze erreicht und die Stichprobenkomplexität bis auf universelle Konstanten festlegt, indem er etablierte untere Schranken erreicht.

Ursprüngliche Autoren: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

Veröffentlicht 2026-08-07

📖 8 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Markus Engelund Mathiasen, Jian Qian, Nikita Zhivotovskiy

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 Roboter beizubringen, den Unterschied zwischen Katzen und Hunden zu erkennen. Sie zeigen ihm tausende Bilder, aber die Welt ist chaotisch: Manchmal versteckt sich die Katze im Dunkeln, manchmal trägt der Hund einen Hut, und manchmal sind die Labels, die Sie dem Roboter geben, einfach schlichtweg falsch. Dies ist die Welt des maschinellen Lernens, speziell eines Feldes namens statistische Lerntheorie. Die große Frage hierbei ist: Wie viele Beispiele muss ein Roboter sehen, bevor er gut darin wird, zu raten?

Um dies zu beantworten, nutzen Wissenschaftler ein Konzept namens VC-Dimension (benannt nach Vapnik und Chervonenkis). Betrachten Sie die VC-Dimension als ein Maß dafür, wie „verwirrend“ oder „komplex“ das Gehirn des Roboters ist. Ein einfaches Gehirn, das nur auf die Ohrenform achtet, hat eine niedrige VC-Dimension; ein superkomplexes Gehirn, das jedes einzelne Pixel betrachtet, hat eine hohe VC-Dimension. Das Ziel ist es, einen „Sweet Spot“ zu finden, an dem der Roboter schnell genug lernt, um nützlich zu sein, aber nicht so komplex ist, dass er die Trainingsfotos auswendig lernt, anstatt die Regeln zu verstehen. Seit Jahrzehnten versuchen Mathematiker, die perfekte Formel zu finden, die uns genau sagt, wie viel „zusätzlichen“ Fehler ein Roboter im Vergleich zum absolut besten möglichen Roboter machen wird, gegeben eine bestimmte Anzahl von Beispielen und ein gewisses Maß an Komplexität.

Lange Zeit gab es eine Wissenslücke. Wir wussten, wie die optimale Lerngeschwindigkeit ist, wenn die Daten perfekt sind (keine Fehler in den Labels), und wir wussten, wie sie ist, wenn die Daten sehr verrauscht sind. Aber was ist mit dem Mittelweg? Was, wenn die Daten nur ein bisschen verrauscht sind? Frühere Versuche, dies zu lösen, waren wie der Versuch, ein Rennen mit einem schweren Rucksack zu laufen; sie waren nah dran, aber sie trugen ein zusätzliches „logarithmisches“ Gewicht mit sich herum, das sie langsamer machte, als sie sein müssten. Die große Frage war: Können wir einen Lerner bauen, der mit der absolut schnellstmöglichen Geschwindigkeit läuft, egal wie viel Rauschen in den Daten ist, ohne dieses zusätzliche Gewicht zu tragen?

Dieses Paper mit dem Titel „An Optimal Agnostic PAC Algorithm“ beantwortet diese Frage mit einem entschiedenen „Ja“. Die Autoren, Markus Engelund Mathiasen, Jian Qian und Nikita Zhivotovskiy, haben einen spezifischen Lernalgorithmus konstruiert, der die statistisch optimale Risikogrenze erreicht. Auf Deutsch bedeutet das: Sie haben einen Weg gefunden, einen Klassifikator zu trainieren, der die wenigsten Fehler macht, und haben mathematisch bewiesen, dass keine andere Methode sie schlagen kann (bis auf einige universelle Konstanten) für jedes beliebige Maß an Rauschen. Sie haben nicht nur geraten; sie haben es bewiesen.

So haben sie es gemacht, unter Verwendung einer Geschichte über eine sehr organisierte Bibliothek und ein cleveres Spiel der „One-Inclusion“.

Das Problem: Die verrauschte Bibliothek

Stellen Sie sich eine riesige Bibliothek vor, in der jedes Buch ein Bild ist und jedes Buch ein Label auf dem Buchrücken hat, das „Katze“ oder „Hund“ sagt. Der Bibliothekar ist jedoch etwas tollpatschig. Manchmal etikettiert er ein Buch falsch, oder das Buch ist beschädigt. Sie möchten ein System bauen, das ein neues, unbeschriftetes Buch betrachten und dessen Label korrekt erraten kann.

Das „bestmögliche“ System (nennen wir es den Oracle) kennt die wahren Regeln des Universums. Selbst das Oracle wird einige Fehler machen, weil die Labels des Bibliothekars manchmal falsch sind. Diese minimale Fehlerrate wird als $L^*$ bezeichnet. Ihr Ziel ist es, ein System zu bauen, das so nah wie möglich an die Leistung des Oracle herankommt, unter Verwendung einer begrenzten Anzahl von Büchern ( $n$ ) aus der Bibliothek.

Das Paper beweist, dass ihr neues System, nennen wir es The Optimizer, eine Fehlerrate ( $L(\hat{h})$ ) hat, die durch Folgendes begrenzt ist:
$L(\hat{h}) \le L^* + 7 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$
Lassen Sie sich von der Mathematik nicht abschrecken. Der entscheidende Teil ist der Term mit der Quadratwurzel. Diese Formel besagt, dass die zusätzlichen Fehler (das „exzessive Risiko“) sinken, wenn man mehr Bücher ( $n$ ) erhält, und dass sie mit der schnellstmöglichen Geschwindigkeit sinken, die durch die Gesetze der Wahrscheinlichkeit erlaubt ist. Vorherige Methoden hatten zusätzliche Faktoren (wie $\log(n)$ ), die sie langsamer machten, aber The Optimizer lässt diese weg.

Das Geheimrezept: Der Würfel und die Orientierung

Wie haben sie das geschafft? Sie nutzten eine brillante Kombination aus zwei Ideen: dem One-Inclusion-Graphen und dem Suffix Averaging.

1. Der One-Inclusion-Graph (Das Würfelspiel)
Stellen Sie sich alle möglichen Arten vor, wie die Bücher in Ihrer Stichprobe etikettiert werden könnten. Wenn Sie $n$ Bücher haben, gibt es $2^n$ mögliche Label-Kombinationen. Sie können diese Kombinationen als Ecken eines riesigen, mehrdimensionalen Würfels (eines „Booleschen Würfels“) visualisieren.

Zwei Ecken sind durch eine Kante verbunden, wenn sie sich durch genau ein Label eines Buches unterscheiden.
Das „Oracle“ (die beste Regel) lebt irgendwo in diesem Würfel.
Das Ziel ist es, herauszufinden, in welche Richtung man zeigen muss, wenn man sich an einer Ecke befindet, damit man sich dem Oracle annähert.

Die Autoren verwenden eine Technik namens Orientierung. Stellen Sie sich vor, Sie stehen auf einer Ecke dieses Würfels. Sie müssen entscheiden, in welche Richtung Sie gehen sollen. Das Paper führt ein neues mathematisches Werkzeug ein, Lemma 2.1, welches eine „klassabhängige isoperimetrische Ungleichung der Kante“ ist. In unserer Bibliotheksanalogie ist dies wie eine Regel, die besagt: „Die Anzahl der Pfade, die Sie prüfen müssen, um die richtige Richtung zu finden, hängt davon ab, wie weit Sie vom Oracle entfernt sind und wie komplex die Bibliothek ist.“

Sie beweisen, dass man jeder Kante in diesem riesigen Würfel eine Richtung zuweisen kann, sodass man, egal wo man startet, niemals mehr als eine bestimmte Anzahl von Schritten benötigt, um dem besten Ergebnis nahe zu kommen. Dieser Schritt ist entscheidend, da er ein chaotisches Ratespiel in einen deterministischen Pfad verwandelt.

2. Suffix Averaging (Die Expertenkommission)
Sobald sie diese perfekte Orientierung haben, müssen sie sie in einen realen Prädiktor umwandeln. Sie nutzen einen Trick namens Suffix Averaging.
Stellen Sie sich vor, Sie bauen ein Team von Experten auf. Sie fragen nicht nur einen Experten nach seiner Meinung. Stattdessen fragen Sie eine Reihe von Experten, die jeweils leicht unterschiedliche Mengen an Daten gesehen haben.

Experte 1 hat die ersten $k$ Bücher gesehen.
Experte 2 hat die ersten $k+1$ Bücher gesehen.
...
Experte $m$ hat die ersten $2k-1$ Bücher gesehen.

Die endgültige Vorhersage ist der Durchschnitt aller Meinungen dieser Experten. Das ist deshalb so leistungsstark, weil es die Zufälligkeit glättet. Wenn ein Experte durch ein verrauschtes Buch Pech hatte, gleichen die anderen dies aus. Das Paper beweist, dass dieser Mittelungsprozess, kombtiniert mit ihrer perfekten Würfelorientierung, die Fehlerrate auch dann niedrig hält, wenn die Daten verrauscht sind.

3. Das letzte Schliffstück: Thresholding
Das gemittelte Ergebnis ist eine Zahl zwischen -1 und 1 (ein „Score“). Um zu einer endgültigen „Katze“- oder „Hund“-Antwort zu gelangen, verwenden sie einen Threshold (Schwellenwert). Sie testen verschiedene Grenzwerte an einem separaten Satz von Validierungsbüchern, um denjenigen auszuwählen, der am besten funktioniert. Dieser Schritt stellt sicher, dass das Endergebnis eine einfache, deterministische Regel (ein binärer Klassifikator) ist und keine vage Wahrscheinlichkeit.

Warum das wichtig ist

Vor diesem Paper mussten Sie sich entscheiden: Entweder Sie wollten die schnellstmögliche Lernrate, dann mussten Sie zwischen Methoden wählen, die gut für perfekte Daten funktionierten, oder Methoden, die gut für verrauschte Daten funktionierten. Man konnte nicht das Beste aus beiden Welten haben, ohne eine Strafe zu zahlen.

Dieses Paper zeigt, dass man beides haben kann. Sie haben einen Lerner konstruiert, der:

Kein Wissen über den Rauschpegel benötigt: Er funktioniert, ohne zu wissen, wie unordentlich die Daten sind ( $L^*$ ) oder wie sicher man sein möchte ( $\delta$ ).
Optimal ist: Er erreicht die theoretische untere Schranke (die Geschwindigkeitsbegrenzung des Lernens), die zuvor von Forschern wie Devroye, Györfi und Lugosi etabliert wurde.
Deterministisch ist: Er verlässt sich nicht auf das Glück; er liefert bei den gleichen Daten jedes Mal die gleiche Antwort.

Die Autoren schließen explizit die Idee aus, dass wir „polylogarithmische“ Faktoren (jene zusätzlichen Verlangsamungen) benötigen, um optimale Ergebnisse im agnostischen (verrauschten) Setting zu erzielen. Sie beweisen, dass diese Faktoren unnötig sind. Sie zeigen auch, dass einige vorherige Methoden (wie einfache Mehrheitsentscheidungen) zwar gut für perfekte Daten funktionieren, aber scheitern, wenn Rauschen eingeführt wird, um die optimale Geschwindigkeit beizubehalten.

Kurz gesagt: Dieses Paper schließt ein langjähriges Kapitel in der Geschichte der Theorie des maschinellen Lernens. Es liefert den „perfekten“ Algorithmus für die binäre Klassifikation in der realen Welt, in der Daten niemals perfekt sind. Es ist ein wenig so, als hätte man eine Karte gefunden, die garantiert, dass man das Ziel in der minimalen Anzahl von Schritten erreicht, egal wie viele Schlaglöcher auf der Straße sind. Die Autoren haben nicht nur suggeriert, dass dies möglich sei; sie haben die Karte gebaut und bewiesen, dass sie funktioniert.

Technisches Resümee: Ein optimaler agnostischer PAC-Algorithmus

Problemstellung
Die Arbeit adressiert das grundlegende Problem der Bestimmung scharfer Risikogrenzen im agnostischen Probably Approximately Correct (PAC) Lernen für die binäre Klassifikation. Sei $H \subseteq \{-1, +1\}^{\mathcal{X}}$ eine Hypothesenklasse mit VC-Dimension $d \geq 1$ . Gegeben sei eine i.i.d. Stichprobe $S$ der Größe $n$ aus einer Verteilung über $\mathcal{X} \times \{-1, +1\}$ ; das Ziel ist es, einen Lerner zu konstruieren, der einen Klassifikator $\hat{h}$ ausgibt, sodass dessen Risiko $L(\hat{h})$ nahe am optimalen Risiko $L^* = \min_{h \in H} L(h)$ liegt.

Historisch wurden Schranken in diesem Setting über zwei unterschiedliche Regime hergeleitet:

Realisierbarer Fall ( $L^*=0$ ): Optimale Raten von $O(d/n)$ werden durch kombinatorische Argumente wie den One-Inclusion-Graphen (Haussler, Littlestone, Warmuth) oder spezifische Aggregationsschemata erreicht.
Agnostischer Fall ( $L^* > 0$ ): Klassische Methoden der empirischen Prozesse (Chaining, Covering) liefern optimale Raten von $O(\sqrt{d/n})$ , wenn $L^*$ von Null verschieden ist.

Die offene Frage, die durch untere Schranken von Devroye, Györfi und Lugosi etabliert wurde, ist, ob ein einziger Algorithmus die optimale Rate über das gesamte Spektrum von $L^*$ hinweg erreichen kann, insbesondere passend zur Schranke:
$L(\hat{h}) \leq L^* + C \left( \sqrt{\frac{L^*(d + \log(1/\delta))}{n}} + \frac{d + \log(1/\delta)}{n} \right)$
Vorherige obere Schranken erforderten entweder suboptimale polylogarithmische Faktoren im Begriff der schnellen Rate oder verlangten spezifische Bedingungen auf $L^*$ (z. B. $L^* \lesssim (d+\log(1/\delta))/n$ ), um Optimalität zu erreichen.

Methodik
Die Autoren konstruieren einen deterministischen, im Allgemeinen ungeeigneten (improper) Lerner, der die optimale Schranke ohne Vorwissen über $L^*$ oder den Konfidenzparameter $\delta$ erreicht. Die Methodik gliedert sich in drei Hauptphasen:

Klassengestützte Kanten-Isoperimetrie (Abschnitt 2):
Die zentrale theoretische Innovation ist Lemma 2.1, eine klassengestützte kantenisoperimetrische Ungleichung auf dem Booleschen Würfel. Im Gegensatz zu früheren Ergebnissen, die Kantenanzahlen allein durch die VC-Dimension oder die Distanz zu einem Trace begrenzen, führt dieses Lemma Gewichte $w_{v,p}$ ein, die gleichzeitig erfüllen:
- $w_{v,p} + w_{v \oplus p, p} = 1$ (Partitionierung der Kanten).
- $\sum_{p \in D} w_{v,p} \leq \rho_F(v) + R_D(F)$ , wobei $\rho_F(v)$ die Hamming-Distanz zu einem Trace $F$ ist und $R_D(F)$ die unnormierte Rademacher-Breite der Projektion von $F$ auf die Koordinaten $D$ darstellt.
Diese Ungleichung ermöglicht eine lokalisierte Schranke für die Anzahl der induzierten Kanten $|E_U|$ in einem Subgraphen, indem sie diese sowohl über die Distanz zum optimalen Trace als auch über die Komplexität der Projektion kontrolliert.
Optimale Leave-One-Out-Orientierung (Abschnitt 2):
Unter Verwendung des Hallschen Theorem für Paarungen konvertieren die Autoren die isoperimetrische Ungleichung in eine deterministische Orientierung $\sigma$ des vollständigen Booleschen Würfels. Diese Orientierung stellt sicher, dass für jeden Knoten $v$ der Auswärtsgrad beschränkt ist durch:
$\text{out}(v; \sigma) \leq \rho_F(v) + 120\sqrt{d \rho_F(v)} + 7202d$
Dies führt zu einer Leave-One-Out-Regel, bei der der erwartete Fehler durch den optimalen empirischen Risiko plus einen Term begrenzt wird, der mit $\sqrt{d L^*/n}$ und $d/n$ skaliert.
Von Leave-One-Out zu PAC-Schranken (Abschnitt 3):
Um die Leave-One-Out-Regel in eine Hochwahrscheinlichkeits-PAC-Garantie zu überführen, wenden die Autoren einen zweistufigen Derandomisierungs- und Mittelungsprozess an:
- Symmetrisierung und Suffix-Mittelung: Die deterministische Leave-One-Out-Regel wird über Permutationen symmetrisiert. Ein randomisierter Prädiktor $\hat{p}$ wird konstruiert, indem diese symmetrisierten Scores über einem Suffix der Stichprobe (Indizes $k$ bis $2k-1$ ) gemittelt werden. Dieser Schritt nutzt Rückwärts- und Vorwärts-Martingal-Argumente (Lemmata 3.1 und 3.2), die von Aden-Ali et al. adaptiert wurden, um die Varianz und Abweichung des exzessiven Risikos zu kontrollieren und sicherzustellen, dass die Schranke uniform in $L^*$ gilt.
- Schwellenwertbildung und ERM: Der randomisierte Prädiktor $\hat{p}$ (der Werte in $[-1, 1]$ annimmt) wird in einen deterministischen binären Klassifikator umgewandelt. Dies geschieht durch die Betrachtung einer Klasse von Schwellenwert-Hypothesen $T_{\hat{p}} = \{ x \mapsto 2\mathbb{1}[\hat{p}(x) \geq u] - 1 \}$ . Ein empirischer Risikominimierer (ERM) wird aus dieser Klasse unter Verwendung einer unabhängigen Validierungsstichprobe ausgewählt. Entscheidend ist, dass die verschachtelte Struktur der Schwellenwertklasse eine lokale Entropieschranke ermöglicht, ohne einen zusätzlichen logarithmischen Faktor in der Stichprobengröße zu verursachen, wodurch der optimale Koeffizient auf $L^*$ erhalten bleibt.

Wesentliche Beiträge und Ergebnisse
Das Paper beweist Theorem 1 und etabliert die Existenz eines deterministischen Lerners, der für jede Verteilung, jede Stichprobengröße $n$ und jedes Vertrauensniveau $\delta$ einen Klassifikator $\hat{h}$ ausgibt, der erfüllt:
$L(\hat{h}) \leq L^* + 2 \cdot 10^8 \left( \sqrt{\frac{L^*(d + \log(48/\delta))}{n}} + \frac{d + \log(48/\delta)}{n} \right)$
mit einer Wahrscheinlichkeit von mindestens $1-\delta$ . Die abschließende Ableitung in dem Beweis zu Theorem 1 liefert eine engere Konstante von etwa $3.1 \cdot 10^7$ .

Optimalität: Diese Schranke entspricht den unteren Schranken von Devroye, Györfi und Lugosi bis auf universelle Konstanten. Es ist das erste Ergebnis, das die optimale Rate für jedes feste $L^*$ erreicht und somit die Lücke zwischen dem realisierbaren und dem voll agnostischen Regime ohne suboptimale polylogarithmische Faktoren schließt.
Algorithmische Eigenschaften: Der Lerner ist deterministisch, im Allgemeinen ungeeignet (improper) (gibt einen Klassifikator aus, der nicht notwendigerweise in $H$ liegt) und erfordert kein Wissen über $L^*$ oder $\delta$ .
Technische Neuheit: Der Beweis stützt sich auf die neue klassengestützte Kanten-Isoperimetrie (Lemma 2.1), welche die Anzahl induzierter Kanten durch eine Kombination aus Approximationsfehlern und projizierten Rademacher-Breiten kontrolliert – eine Technik, die sich von bisherigen kombinatorischen oder rein empirischen Prozess-Ansätzen unterscheidet.

Bedeutung
Das Paper beansprucht, die Stichprobenkomplexität des agnostischen PAC-Lernens bis auf universelle Konstanten geklärt zu haben. Durch die Konstruktion eines Algorithmus, der das minimax-exzessive Risiko für die binäre Klassifikation bei jedem festen $L^*$ erreicht, lösen die Autoren eine langjährige offene Frage bezüglich der Existenz eines einzelnen Algorithmus, der über das gesamte Spektrum der Rauschpegel optimal ist. Die Arbeit zeigt, dass die optimale Rate erreicht werden kann, ohne den führenden Koeffizienten des $L^*$ -Terms zu opfern – eine Leistung, die aufgrund der Spannung zwischen Techniken des realisierbaren und des agnostischen Lernens zuvor als schwierig galt.

Das Problem: Die verrauschte Bibliothek

Das Geheimrezept: Der Würfel und die Orientierung

Warum das wichtig ist

Technisches Resümee: Ein optimaler agnostischer PAC-Algorithmus

Mehr davon