Local Regularization Does Not Characterize Multiclass PAC Learnability

Technisches Resümee: Lokale Regularisierung charakterisiert keine Multiklassen-PAC-Lernbarkeit

Problemstellung
Eine zentrale Frage der statistischen Lerntheorie ist die Identifizierung einfacher algorithmischer Prinzipien, die die Lernbarkeit von Hypothesenklassen charakterisieren. In der binären Klassifikation charakterisiert die empirische Risikominimierung (ERM) die PAC-Lernbarkeit. Die Multiklassen-Situation ist jedoch komplexer; das korrekte Lernen kann für lernbare Klassen fehlschlagen, und optimale Lerner verlassen sich oft auf beispielabhängige Strukturen statt auf feste Hypothesen-Rangfolgen.

Asilis et al. schlugen die lokale Regularisierung als eine potenzielle Verallgemeinerung von ERM für den Multiklassen-Fall vor. Ein lokaler Regularisierer weist jedem Hypothesen $h$ an jedem Testpunkt $x$ einen festen Score $\psi(h, x)$ zu, der unabhängig von der Trainingsstichprobe ist. Ein durch einen solchen Regularisierer induzierter Lerner sagt das Label der Hypothese mit dem minimalen Score unter jenen voraus, die mit der beobachteten Stichprobe konsistent sind. Während Jafar, Asilis und Dughmi zuvor nachgewiesen haben, dass die lokale Regularisierung im transduktiven Modell (wo ein spezifischer zurückgehaltener Punkt getestet wird) fehlschlägt, blieb die Frage offen, ob dieses Prinzip die PAC-Lernbarkeit charakterisiert, bei der der zurückgehaltene Punkt eine vernachlässigbare Populationsmasse tragen kann und wiederholtes Sampling theoretisch dessen Struktur offenbaren könnte.

Methodik und Konstruktion
Das Paper konstruiert ein Gegenbeispiel unter Verwendung einer abzählbaren Hypothesenklasse basierend auf Turnieren (vollständigen gerichteten Graphen).

• Hypothesenklasse ($H$): Für eine ganze Zahl $q \ge 3$ entsprechen die Hypothesen Kanten eines vollständigen Graphen $K_q$. Eine Hypothese $h_{q,e}$ sagt den „Kopf“ (Zielknoten) der Kante $e$ innerhalb einer Turnier-Instanz $\tau$ voraus.
• Instanzraum: Instanzen sind Paare $(q, \tau)$, wobei $\tau$ ein Turnier auf $q$ Knoten ist.
• Schwierige Verteilungen: Die Autoren definieren eine Familie von „schwierigen“ Verteilungen $D_{e,v}$ für eine Zielkante $e=\{u,v\}$ und Endpunkt $v$. Diese Verteilungen sind gleichverteilt über Turniere, in denen die Kante $e$ in Richtung $v$ orientiert ist. Folglich sind alle beobachteten Labels in der Trainingsstichprobe identisch: $(q, v)$.
• Der Mechanismus des Scheiterns:
  1. Filterung: Die Trainingsstichprobe (alle Labels gleich $v$) filtert den Versionsraum und behält nur Hypothesen, die Kanten entsprechen, die incident zu $v$ sind und in den gesampelten Turnieren in Richtung $v$ orientiert sind.
  2. Feste Rangfolge: Der lokale Regularisierer $\psi$ erzwingt eine strikte totale Ordnung der an $v$ angrenzenden Kanten am Testpunkt bevor die Stichprobe beobachtet wird.
  3. Zyklische Inversionen: Die zentrale Schwierigkeit ergibt sich aus zyklischen Dreiecken im Turnier. Selbst wenn die Trainingsstichprobe viele Konkurrenten entfernt, kann die feste Ordnung der verbleibenden Kanten relativ zum wahren Ziel aufgrund der zyklischen Struktur „invertiert“ werden. Speziell: Wenn eine ausgehende Kante (die nicht das Ziel sein sollte) den Filterprozess überlebt und in der festen Rangfolge des Regularisierers vor der wahren eingehenden Zielkante erscheint, begeht der Lerner einen Fehler.

Wesentliche Beiträge und Ergebnisse

1. Existenz eines Gegenbeispiels: Das Paper beweist die Existenz einer abzählbaren Multiklassen-Hypothesenklasse $H$, die PAC-lernbar ist, aber nicht durch jeden lokalen Regularisierer lernbar ist.

   • Lernbarkeit: Die Klasse ist PAC-lernbar mit einer Stichprobenkomplexität von $O(\frac{1}{\varepsilon} \log \frac{1}{\delta})$. Ein expliziter Lerner ist erfolgreich, indem er die Zielkante identifiziert, sobald beide Endpunkt-Labels in der Stichprobe erscheinen.
   • Dimensionsgrenze: Die Klasse hat eine Daniely–Shalev-Shwartz (DS)-Dimension von höchstens 2. Dies wird dadurch etabliert, dass das Bild jeder Hypothese höchstens zwei Labels enthält, was die Bildung eines 3-dimensionalen Pseudo-Würfels verhindert.

2. Unmöglichkeitstheorem: Für jeden lokalen Regularisierer $\psi$ existiert ein induzierter Lerner $A_\psi$, der $H$ nicht PAC-lernen kann.

   • Fehlermodus: Für jeden festen Regularisierer zeigen die Autoren, dass es für beliebig große Stichprobengrößen $n$ realisierbare Verteilungen gibt, bei denen die Irrtumswahrscheinlichkeit eine Konstante $\delta_0 = \frac{1}{192e}$ überschreitet.
   • Quantitative Grenzen: Die Irrtumswahrscheinlichkeit ist von Null verschieden ($\varepsilon_0 = \frac{1}{96e}$), da die erwartete Anzahl an „Inversionen“ (vor eingehenden Kanten rangierte ausgehende Kanten) in der Turnierstruktur signifikant bleibt. Der Beweis nutzt die Tatsache, dass ein zufälliges Turnier $\Theta(q^3)$ zyklische Dreiecke enthält, was sicherstellt, dass für jede strikte Ordnung der Kanten ein konstanter Anteil der Ziel-Inzidenzen zu einem Vorhersagefehler führt.

Bedeutung und Ansprüche
Das Paper kommt zu dem Schluss, dass lokale Regularisierung nicht die realisierbare Multiklassen-PAC-Lernbarkeit charakterisiert.

• Abgrenzung zu transduktiven Ergebnissen: Im Gegensatz zum transduktiven Lower Bound von Jafar et al., der auf einem einzelnen zurückgehaltenen Punkt mit potenziell vernachlässigbarer Masse beruht, verteilt diese Konstruktion den Fehler über eine Population von Turnieren. Das Scheitern bleibt bestehen, selbst wenn die Stichprobengrößen beliebig groß werden, was verhindert, dass der Lerner die verborgene Struktur durch wiederholtes Sampling „lernt“.
• Limitierung fester Scores: Das Ergebnis hebt eine fundamentale Rigidität in der lokalen Regularisierung hervor: Da die Rangfolge der Hypothesen an einem Testpunkt vor der Beobachtung der Stichprobe festgelegt ist, kann der Lerner die relative Ordnung der überlebenden Konkurrenten nicht basierend auf der spezifischen Struktur der Trainingsdaten anpassen. In der Turnier-Situation führt diese Unfähigkeit zur Umordnung zu einem konstanten Populationsfehler, obwohl die Klasse eine niedrige DS-Dimension ($\le 2$) und durch andere Methoden effizient lernbar ist.
• Geltungsbereich: Das Ergebnis gilt spezifisch für Regularisierer, bei denen die Scores unabhängig von der Stichprobe feststehen. Es adresset nicht unüberwachte Frameworks, in denen die Regularisierungsregel von der ungelabelten Stichprobe abhängen könnte.

Zusammenfassend liefert das Paper eine definitive negative Antwort auf die Frage, ob die lokale Regularisierung die realisierbare Multiklassen-PAC-Lernbarkeit charakterisiert, und zeigt auf, dass selbst für Klassen mit geringer kombinatorischer Dimension (DS-dim $\le 2$) und optimaler Stichprobenkomplexität, feste-Score-Regularisierer scheitern können.