Local Regularization Does Not Characterize Multiclass PAC Learnability

Technische Samenvatting: Lokale Regularisatie Karakteriseert Geen Multiclass PAC-Leerbaarheid

Probleemstelling
Een centrale vraag in de statistische leertheorie is het identificeren van eenvoudige algoritmische principes die de leerbaarheid van hypotheseklassen karakteriseren. In binaire classificatie karakteriseert Empirical Risk Minimization (ERM) de PAC-leerbaarheid. De multiclass-setting is echter complexer; gepaste leerprocessen kunnen falen voor leerbare klassen, en optimale leerders vertrouwen vaak op de structuur van de steekproef zelf in plaats van op vaste hypothese-ordeningen.

Asilis et al. stelden lokale regularisatie voor als een potentiële generalisatie van ERM voor de multiclass-setting. Een lokale regularisator wijst een vaste score $\psi(h, x)$ toe aan elke hypothese $h$ bij elk testpunt $x$, onafhankelijk van de trainingssteekproef. Een leerder die door een dergelijke regularisator wordt geïnduceerd, voorspelt het label van de hypothese met de minimale score onder de hypothesen die consistent zijn met de geobserveerde steekproef. Hoewel Jafar, Asilis en Dughmi eerder hebben aangetoond dat lokale regularisatie faalt om leerbaarheid te karakteriseren in het transductieve model (waarbij een specifiek achtergehouden punt wordt getest), bleef de vraag open of dit principe ook de PAC-leerbaarheid karakteriseert, waarbij het achtergehouden punt een verwaarloosbare populatiemassa kan hebben en herhaaldelijk samplen theoretisch de structuur zou kunnen onthullen.

Methodologie en Constructie
Het artikel construeert een tegenvoorbeeld met behulp van een aftelbare hypotheseklasse gebaseerd op toernooien (volledige gerichte grafen).

• Hypotheseklasse ($H$): Voor een geheel getal $q \ge 3$ corresponderen hypothesen met de randen van een volledige graaf $K_q$. Een hypothese $h_{q,e}$ voorspelt de "kop" (doelvertex) van rand $e$ binnen een toernooi-instantie $\tau$.
• Instantieruimte: Instanties zijn paren $(q, \tau)$, waarbij $\tau$ een toernooi is op $q$ vertices.
• Harde Distributies: De auteurs definiëren een familie van "harde" distributies $D_{e,v}$ voor een doelrand $e=\{u,v\}$ en eindpunt $v$. Deze distributies zijn uniform over toernooien waar de rand $e$ naar $v$ is gericht. Bijgevolg zijn alle geobserveerde labels in de trainingssteekproef identiek: $(q, v)$.
• Het Mechanisme van Falen:
  1. Filtering: De trainingssteekproef (alle labels gelijk aan $v$) filtert de version space, waardoor alleen hypothesen overblijven die corresponderen met randen incident aan $v$ die in de gesamplede toernooien naar $v$ zijn gericht.
  2. Vaste Rangschikking: De lokale regularisator $\psi$ legt een strikte totale ordening op aan de randen incident aan $v$ bij het testpunt voordat de steekproef is geobserveerd.
  3. Cyclische Inversies: De kern van de moeilijkheid komt voort uit cyclische driehoeken in het toernooi. Zelfs als de trainingssteekproef veel concurrenten verwijdert, kan de vaste ordening van de resterende randen ten opzichte van de werkelijke doelrand worden "geïnverteerd" door de cyclische structuur. Specifiek: als een uitgaande rand (die niet de doelrand zou moeten zijn) de filtering overleeft en eerder verschijnt in de vaste rangschikking van de regularisator dan de ware inkomende doelrand, maakt de leerder een fout.

Belangrijkste Bijdragen en Resultaten

1. Bestaan van een Tegenvoorbeeld: Het artikel bewijst het bestaan van een aftelbare multiclass hypotheseklasse $H$ die PAC-leerbaar is maar niet leerbaar door een lokale regularisator.

   • Leerbaarheid: De klasse is PAC-leerbaar met een steekproefcomplexiteit van $O(\frac{1}{\varepsilon} \log \frac{1}{\delta})$. Een expliciete leerder slaagt door de doelrand te identificeren zodra beide eindpuntlabels in de steekproef voorkomen.
   • Dimensie-grens: De klasse heeft een Daniely–Shalev-Shwartz (DS) dimensie van maximaal 2. Dit wordt vastgesteld door aan te tonen dat de afbeelding van elke hypothese maximaal twee labels bevat, wat de vorming van een 3-dimensionale pseudo-kubus voorkomt.

2. Onmogelijkheidstheorema: Voor elke lokale regularisator $\psi$ bestaat er een geïnduceerde leerder $A_\psi$ die $H$ niet kan PAC-leren.

   • Faalmodus: Voor elke vaste regularisator tonen de auteurs aan dat er, voor willekeurig grote steekproefomvang $n$, realizabele distributies bestaan waarbij de foutkans groter is dan een constante $\delta_0 = \frac{1}{192e}$.
   • Kwantitatieve Grenzen: De foutkans is begrensd weg van nul ($\varepsilon_0 = \frac{1}{96e}$) omdat het verwachte aantal "inversies" (uitgaande randen die vóór inkomende randen gerangschikt zijn) in de toernooistructuur significant blijft. Het bewijs maakt gebruik van het feit dat een willekeurig toernooi $\Theta(q^3)$ cyclische driehoeken bevat, wat garandeert dat voor elke strikte ordening van randen een constante fractie van de doel-incidenties zal resulteren in een voorspellingsfout.

Betekenis en Claims
Het artikel concludeert dat lokale regularisatie de realizabele multiclass PAC-leerbaarheid niet karakteriseert.

• Onderscheid met Transductieve Resultaten: In tegen tegenstelling tot de transductieve ondergrens door Jafar et al., die steunt op een enkel achtergehouden punt met mogelijk verwaarloosbare massa, verspreidt deze constructie de fout over een populatie van toernooien. Het falen houdt aan zelfs wanneer de steekproefomvang willekeurig groot wordt, waardoor de leerder de verborgen structuur niet kan "leren" door middel van herhaaldelijk samplen.
• Beperking van Vaste Scores: Het resultaat benadrukt een fundamentele rigiditeit in lokale regularisatie: omdat de rangschikking van hypothesen bij een testpunt vaststaat vóór de observatie van de steekproef, kan de leerder de relatieve ordening van overgebleven concurrenten niet aanpassen op basis van de specifieke structuur van de trainingsdata. In de toernooi-setting leidt dit onvermogen om te herordenen tot een constante populatiefout, ondanks het feit dat de klasse een lage DS-dimensie heeft en door andere middelen efficiënt leerbaar is.
• Reikwijdte: Het resultaat is specifiek van toepassing op regularisatoren waarbij scores vaststaan onafhankelijk van de steekproef. Het behandelt geen unsupervised frameworks waarbij de regularisatieregel afhankelijk kan zijn van de ongelabelde steekproef.

Samenvattend biedt het artikel een definitief negatief antwoord op de vraag of lokale regularisatie de multiclass PAC-leerbaarheid karakteriseert, door aan te tonen dat zelfs voor klassen met een lage combinatorische dimensie (DS-dim $\le 2$) en optimale steekproefcomplexiteit, vaste-score regularisatoren kunnen falen om te leren.