Characterizing the Multiclass Learnability of Forgiving 0-1 Loss Functions

Dit paper karakteriseert de multiclass leerbaarheid van vergevingsgezinde 0-1-verliesfuncties door een nieuwe combinatorische dimensie, de gegeneraliseerde Natarajan-dimensie, te introduceren die de leerbaarheid van een hypotheseklasse precies bepaalt wanneer deze eindig is.

De kern

De Kern: Wat is dit onderzoek eigenlijk?

Stel je voor dat je een kunstenaar bent die schilderijen moet herkennen. In de "oude" manier van machine learning (de klassieke theorie) was het heel streng: als je een schilderij van Van Gogh moest herkennen, en je zei "dit is een Rembrandt", dan was je fout. Als je zei "dit is een Van Gogh", was je goed. Er was geen ruimte voor fouten. Dit noemen we de 0-1 verliesfunctie: of je hebt het helemaal goed (0 fouten), of je hebt het helemaal fout (1 fout).

Maar in het echte leven is het vaak wat ruimer.

• Voorbeeld: Stel je moet een recept voor "Italiaans eten" voorspellen. Als het recept "Pizza" is, en jij zegt "Pasta", is dat misschien ook wel goed genoeg? Of als je een lijstje met "top 3 favoriete films" moet maken, en de gebruiker had "Film A" op plek 1, maar jij had die op plek 2, is dat dan echt een ramp?

De auteurs van dit papier (Jacob, Tyson en Ambuj) zeggen: "Wacht even, de huidige theorie is te streng. Laten we kijken naar deze 'vergevingsgezinde' (forgiving) situaties waar een fout niet altijd even erg is."

Het Probleem: Te veel regels, te weinig duidelijkheid

In de wereld van kunstmatige intelligentie willen we weten: Kan een computer dit probleem leren?
Om dit te beantwoorden, gebruiken wetenschappers vaak een soort "meters" (dimensions) om te meten hoe moeilijk een taak is.

• Als de taak makkelijk is, is de meter laag.
• Als de taak onmogelijk is, is de meter oneindig hoog.

Voor de strenge situatie (alles of niets) hebben we al een goede meter: de Natarajan-dimensie. Maar voor de "vergevingsgezinde" situaties (waarbij je bijvoorbeeld een lijstje mag geven, of waarbij verschillende antwoorden als 'goed' worden beschouwd), hadden we geen goede meter. De oude meters werkten niet meer, omdat ze uitgingen van de regel: "Antwoord A is alleen goed als het exact A is."

De Oplossing: De "Vergelijkings-Bril"

De auteurs hebben een nieuwe meter bedacht: de Generalized Natarajan-dimensie (Veralgemeende Natarajan-dimensie).

De Analogie van de Vergelijkings-Bril:
Stel je voor dat je een bril opzet die kijkt naar wat er echt telt.

• In de strenge wereld zie je: "Antwoord A is A, en B is B."
• In deze nieuwe, vergevingsgezinde wereld, kijkt de bril naar groepen van acceptabele antwoorden.

Stel, de "juiste" antwoorden voor een vraag zijn {Pizza, Pasta, Lasagne}.

• Als de computer "Pizza" zegt, is dat goed.
• Als de computer "Pasta" zegt, is dat ook goed.
• Voor de computer zijn "Pizza" en "Pasta" in deze context hetzelfde. Ze vallen in dezelfde "goede groep".

De nieuwe meter meet niet of de computer het exacte woord heeft geraden, maar of hij de juiste groep heeft gevonden. Als de computer "Pizza" zegt en de groep is {Pizza, Pasta}, dan is hij goed. Maar als hij "Sushi" zegt (een groep die niet in de lijst staat), dan is hij fout.

Wat hebben ze bewezen?

1. De Gouden Regel: Een leerprobleem is oplosbaar (leerbaar) voor een computer als en slechts als deze nieuwe meter (Generalized Natarajan-dimensie) een eindig getal is.

   • Is de meter oneindig? Dan is het probleem te chaotisch; de computer kan het nooit leren, hoeveel voorbeelden je ook geeft.
   • Is de meter een gewoon getal? Dan kan de computer het leren, en weten we precies hoeveel voorbeelden hij nodig heeft.

2. Het is verrassend streng: Je zou denken: "Oh, als ik meer antwoorden mag geven (bijv. een lijstje van 3), moet het toch makkelijker zijn?"
   De auteurs tonen aan dat dit niet altijd zo werkt. Als de computer de "vergevensgezindheid" misbruikt (bijvoorbeeld door altijd het hele alfabet te raden), kan hij de leerkracht (de data) voor de gek houden. De theorie laat zien dat de computer echt moet leren welke groepen goed zijn, niet alleen maar raden.

3. Toepassingen in de echte wereld:
   Deze nieuwe meter werkt voor heel veel moderne toepassingen:

   • Medicijnontwikkeling: Als je een molecuul zoekt dat op een ziekte werkt, maakt het niet uit of je een molecuul vindt dat exact hetzelfde is, zolang het maar dezelfde structuur heeft (isomorfie).
   • Films ranken: Als je de top 3 films van iemand moet raden, maakt het niet uit of je ze in de exacte volgorde hebt, zolang ze er maar in zitten.
   • Set-leren: Als je moet zeggen of een object in een bepaalde verzameling hoort.

Samenvatting in één zin

Dit papier geeft ons een nieuwe "meetlat" om te bepalen of een computer een taak kan leren, zelfs als we hem toestaan om fouten te maken of meerdere goede antwoorden te geven, zolang die antwoorden maar binnen een bepaalde "groep van acceptatie" vallen.

Het is alsof we de regels van een spel hebben aangepast: vroeger was het "alleen winnen als je de exacte score haalt", maar nu is het "winnen als je binnen de scoreband ligt". De auteurs hebben bewezen hoe je precies kunt berekenen of een speler (de computer) dit nieuwe spel kan leren.

Technische samenvatting

Probleemstelling

Het artikel adresseert een beperking in de bestaande theoretische analyse van machine learning, specifiek binnen het domein van multiclass classificatie. Traditionele theorie (zoals de VC-dimensie en Natarajan-dimensie) richt zich voornamelijk op de standaard 0-1 verliesfunctie, waarbij een voorspelling alleen correct is als deze exact overeenkomt met het label ($\ell(y, y') = 0 \iff y = y'$).

In veel praktische toepassingen (zoals parafraas-generatie, ranking met partiële feedback, of het classificeren van grafen tot op isomorfisme) is een "perfecte" match niet nodig. Er bestaan "vergevingsgezinde" (forgiving) verliesfuncties waarbij meerdere outputs als correct kunnen worden beschouwd voor een gegeven label. Formeel is dit een setting met:

• Een inputruimte $X$.
• Een outputruimte $Z$ en een labelruimte $Y$ (die niet noodzakelijk gelijk zijn).
• Een verliesfunctie $\ell: Z \times Y \to \{0, 1\}$, waarbij $\ell(z, y) = 0$ betekent dat output $z$ acceptabel is voor label $y$.

Het probleem is dat bestaande combinatorische dimensies (zoals de Natarajan-dimensie of de DS-dimensie) niet direct toepasbaar zijn of onvoldoende zijn om de leerbaarheid (learnability) van deze specifieke klasse van verliesfuncties te karakteriseren, vooral wanneer de outputruimte "effectief eindig" is maar niet noodzakelijk identiek aan de labelruimte.

Methodologie

De auteurs introduceren een nieuwe theoretische raamwerk om deze problematiek aan te pakken:

1. Equivalentierelaties en Quotientruimten:
   In plaats van te kijken naar individuele labels of outputs, definiëren de auteurs equivalentierelaties gebaseerd op de verliesfunctie:

   • $\sigma(z) = \{y \in Y \mid \ell(z, y) = 0\}$: De verzameling labels waarvoor output $z$ een verlies van 0 heeft.
   • $\tau(y) = \{z \in Z \mid \ell(z, y) = 0\}$: De verzameling outputs die acceptabel zijn voor label $y$.
   • Twee outputs $z_1, z_2$ worden als equivalent beschouwd ($z_1 \sim_\sigma z_2$) als $\sigma(z_1) = \sigma(z_2)$.
     De auteurs reduceren het leerprobleem naar een equivalent probleem op de quotientruimten $\sigma(Z)$ en $\tau(Y)$. Ze tonen aan dat de leerbaarheid van het originele probleem volledig wordt bepaald door het gedrag op deze gereduceerde ruimten.

2. Aannames:

   • De verliesfunctie is binair ($\{0, 1\}$).
   • De grootte van de quotientruimte $|\sigma(Z)|$ is eindig ("effectief eindig").
   • Er geldt geen strikte inclusie: voor geen twee outputs $z_1, z_2$ geldt dat $\sigma(z_1) \subsetneq \sigma(z_2)$. Dit voorkomt dat een output objectief "beter" is dan een andere, wat de leerbaarheid zou trivialiseren.

3. De Generalized Natarajan Dimensie (GN-dimensie):
   De kern van de methodologie is de definitie van een nieuwe combinatorische dimensie, de Generalized Natarajan Dimension ($GNdim$).

   • Een verzameling $S$ wordt "gebroken" (shattered) door een hypothesesklasse $H$ als er twee hypotheses $h_1, h_2$ bestaan die voor elk element in $S$ verschillende equivalentieklassen van outputs genereren ($\sigma(h_1(s)) \neq \sigma(h_2(s))$), en voor elke deelverzameling van $S$ een hypothesis bestaat die de outputs van $h_1$ en $h_2$ selectief combineert.
   • Dit is een generalisatie van de klassieke Natarajan-dimensie, waarbij de "gelijkheid" niet wordt bepaald door $h(x) = y$, maar door de gelijkheid van de verzameling acceptabele labels $\sigma(h(x))$.

Belangrijkste Bijdragen

1. Definitie van de GN-dimensie: De auteurs introduceren een nieuwe combinatorische maatstaf die specifiek is ontworpen voor multiclass settingen met verliesfuncties die geen "identity of indiscernibles" eigenschap hebben (waarbij $\ell(y,y')=0$ niet noodzakelijk impliceert dat $y=y'$).
2. Karakterisering van Leerbaarheid: Het bewijs dat een hypothesesklasse $H$ PAC-learnable (Probably Approximately Correct) is met betrekking tot een dergelijke verliesfunctie als en slechts als de Generalized Natarajan Dimensie eindig is ($GNdim(H, \ell) < \infty$).
3. Vergelijking met Bestaande Dimensies: De auteurs tonen aan dat de GN-dimensie onvergelijkbaar is met bestaande dimensies zoals de Natarajan-dimensie, de DS-dimensie, en de $d_J$-dimensie.
   • Er bestaan klassen waar de Natarajan-dimensie oneindig is, maar de GN-dimensie 0 (vanwege de verliesfunctie die veel outputs equivalent maakt).
   • Er bestaan klassen waar de Natarajan-dimensie 0 is, maar de GN-dimensie groot (vanwege de structuur van de verliesfunctie).
4. Steekproefcomplexiteit: Het afleiden van boven- en ondergrenzen voor de steekproefcomplexiteit die afhankelijk zijn van de GN-dimensie en de grootte van de quotientruimte.

Resultaten

• Hoofdstelling (Theorem 1): Een leerprobleem $(X, Z, Y, H, \ell)$ is PAC-learnable dan en slechts dan als $GNdim(H, \ell) < \infty$.
• Noodzaak: Als de GN-dimensie oneindig is, kan er geen leeralgoritme bestaan dat voor alle distributies een lage verwachte verlieswaarde garandeert (bewezen via een aanpassing van de "No-Free-Lunch" stelling).
• Voldoende: Als de GN-dimensie eindig is, is Empirical Risk Minimization (ERM) een geldige leerder. De steekproefcomplexiteit wordt begrensd door $O\left(\frac{GNdim \cdot \log|\sigma(Z)| + \log(1/\delta)}{\epsilon^2}\right)$.
• Intuïtie over "Vergevingsgezindheid": De paper weerlegt de intuïtie dat een "vergevingsgezinde" verliesfunctie (waar veel outputs als correct worden beschouwd) automatisch makkelijker te leren is. Als de verliesfunctie de outputruimte niet reduceert (d.w.z. de quotientruimte is even groot als de originele ruimte), blijft de leerbaarheid even moeilijk als bij de standaard 0-1 loss. De "vergeving" helpt alleen als het de effectieve grootte van de outputruimte verkleint.

Significantie en Toepassingen

De paper is significant omdat het een breed scala aan machine learning problemen onder één theoretische paraplu brengt die eerder open stonden of slechts in specifieke gevallen (zoals online learning) waren opgelost.

Toepassingen die door deze karakterisering worden gedekt:

1. Set Learning: Waar de output een verzameling is en het label een subset, en de leerder moet voorspellen of het label in de outputverzameling zit.
2. Classificatie tot op Isomorfisme: Bijvoorbeeld in drug discovery, waar elke isomorfe grafiek als een correcte voorspelling telt.
3. Ranking met Partiële Feedback: Waar alleen de top-$p$ items van een ranking belangrijk zijn, ongeacht de exacte volgorde daarin.
4. Gewijzigde List Learning: Waar de algoritme een lijst van mogelijke antwoorden mag geven, maar de lijst moet corresponderen met de structuur van de verliesfunctie (niet willekeurige lijsten).

Conclusie:
Dit werk biedt een scherp, precies en interpreteerbaar theoretisch fundament voor het begrijpen van leerbaarheid in settings waar de definitie van "correct" losstaat van exacte gelijkheid. Het toont aan dat de complexiteit van het leerprobleem niet alleen afhangt van de hypothesesklasse, maar fundamenteel wordt bepaald door de interactie tussen de hypotheses en de structuur van de verliesfunctie (via de equivalentierelaties).