Technische Samenvatting: Leren met meerdere correcte antwoorden – Regret Bounds onder verschillende feedbackmodellen

1. Probleemdefinitie en Motivatie

Dit werk behandelt het probleem van online leren met meerdere correcte antwoorden, een setting waarin een enkele inputinstantie $x$ een verzameling geldige labels $S \subseteq \mathcal{Y}$ toelaat in plaats van één enkel doel-label. Deze formulering wordt gemotiveerd door moderne taken zoals taalgeneratie (waarbij een prompt vele acceptabele voltooiingen heeft), open-ended vraagbeantwoording, dialooggeneratie en aanbevelingssystemen.

De studie richt zich op het online leerparadigma, dat verloopt in rondes $t \in [T]$. In elke ronde presenteert een tegenstander een instantie $x_t$ en een verzameling acceptabele labels $S_t$. De leerder voorspelt een label $\hat{y}_t$ en incasseert een verlies van 1 als $\hat{y}_t \notin S_t$. Het artikel analyseert dit probleem onder drie verschillende feedbackmodellen:

1. Mistake-unknown: De leerder ontvangt alleen een enkel geldig label $y_t \in S_t$ (gekozen door de tegenstander), maar weet niet of de eigen voorspelling correct was.
2. Mistake-known: De leerder ontvangt een enkel geldig label $y_t \in S_t$ en een binaire indicator die onthult of de eigen voorspelling $\hat{y}_t$ een fout was.
3. Set-valued: De leerder krijgt de volledige verzameling van geldige labels $S_t$ onthuld.

De analyse beslaat zowel de realiseerbare setting (waarbij een hypothese $h^* \in \mathcal{H}$ bestaat zodanig dat $h^*(x_t) = S_t$ voor alle $t$) als de agnostische setting (waarbij de leerder concurreert met de beste hypothese in $\mathcal{H}$ die de cumulatieve loss minimaliseert).

2. Methodologie en Combinatorische Karakterisaties

De auteurs introduceren nieuwe combinatorische dimensies om de leerbaarheid van multi-label hypotheseklassen $\mathcal{H}$ te karakteriseren onder elk feedbackmodel. Deze dimensies zijn gedefinieerd via tree-shattering argumenten die zijn aangepast aan de specifieke informatie die in elk model beschikbaar is.

Combinatorische Dimensies

• Set-Valued Littlestone Dimension ($LD_{set}$): Gedefinieerd op een verzameling-gebaseerde boom waarbij knopen zijn gelabeld met deelverzamelingen van $\mathcal{Y}$. Een boom is geshattered als er voor elke pad van voorspellingen een hypothese bestaat die consistent is met de onthulde verzamelingen $S_t$, maar een fout maakt op het voorspelde label.
• Mistake-Known Littlestone Dimension ($LD_{known}$): Gedefinieerd op een multi-label boom waarbij knopen zijn gelabeld met enkele labels. Shattering vereist consistentie met het onthulde enkele label $y_t$ en een fout op de voorspelling.
• Mistake-Unknown Littlestone Dimension ($LD_{unknown}$): Gedefinieerd met behulp van een "mistake offset" functie. Een boom is $d$-geshattered als het cumulatieve aantal fouten langs elke pad, plus een offset voor de hypothese, groter is dan $d$. Dit houdt rekening met het gebrek aan directe feedback over de juistheid.

Algoritmen

Voor de realiseerbare setting stellen de auteurs Standard Optimal Algorithms (SOA) voor voor elk feedbackmodel. Deze algoritmen houden een versie-ruimte bij van consistente hypothesen en selecteren voorspellingen die de worst-case dimensie van de resterende versie-ruimte minimaliseren.

• SOA voor Mistake-Unknown: Houdt een versie-ruimte en een offset-functie bij, en voorspelt het label dat de maximale $LD_{unknown}$ van de resulterende subklassen minimaliseert.
• SOA voor Mistake-Known: Voorspelt om de maximale $LD_{known}$ van de subklassen gevormd door de fout-bit te minimaliseren.
• SOA voor Set-Valued: Voorspelt om de maximale $LD_{set}$ van de subklassen gevormd door de onthulde verzameling $S_t$ te minimaliseren.

3. Belangrijkste Resultaten

Realiseerbaar Online Leren

Het artikel biedt een volledige karakterisering van de optimale mistake bound voor elke multi-label klasse $\mathcal{H}$ in de realiseerbare setting:

• Mistake-unknown: De optimale mistake bound is $\min(LD_{unknown}(\mathcal{H}), T)$.
• Mistake-known: De optimale mistake bound is $\min(LD_{known}(\mathcal{H}), T)$.
• Set-valued: De optimale mistake bound is $\min(LD_{set}(\mathcal{H}), T)$.

Deze resultaten generaliseren eerder werk op eindige klassen naar willekeurige (mogelijk oneindige) hypotheseklassen. De auteurs bewijzen dat $LD_{set}(\mathcal{H}) = 0 \iff LD_{known}(\mathcal{H}) = 0 \iff LD_{unknown}(\mathcal{H}) = 0$, wat optreedt indien en slechts indien de doorsnede van de labelverzamelingen van alle hypothesen voor elke instantie niet-leeg is.

Agnostisch Online Leren (Regret Bounds)

Een belangrijke bijdrage is de demonstratie dat regret-rates drastisch variëren tussen feedbackmodellen in de agnostische setting, in contrast met single-label leren waar regret typisch $\tilde{\Theta}(\sqrt{T})$ is.

1. Mistake-Unknown: De auteurs tonen aan dat regret lineair in $T$ kan groeien ($\Omega(T)$), zelfs voor eenvoudige hypotheseklassen met $LD_{unknown}=1$. Dit impliceert dat realiseerbare leerbaarheid (gekarakteriseerd door $LD_{unknown}$) in de agnostische setting voor dit feedbackmodel geen sublineaire regret garandeert.
2. Mistake-Known: Het artikel stelt een sublineaire regret upper bound vast van $O(\sqrt{LD_{known}(\mathcal{H}) |\mathcal{Y}| T \log T})$. Dit wordt bereikt door het probleem te reduceren tot non-stochastische bandits met expert-advies, gebruikmakend van een verzameling SOA-gebaseerde experts.
3. Set-Valued:
   • Voor specifieke klassen (bijv. de voorbeeldklasse $H_3$) is de regret constant ($O(1)$).
   • Voor algemene klassen wordt de regret begrensd door $O(\sqrt{LD_{set}(\mathcal{H}) T \log T})$. Opvallend genoeg is deze bound onafhankelijk van de grootte van de labelruimte $|\mathcal{Y}|$, waardoor deze ook geldt voor oneindige labelruimtes.

Implicaties voor Batch Leren

De afgeleide combinatorische dimensies en online bounds impliceren sample complexity bounds voor de corresponderende batch learning problemen. De auteurs bieden de eerste bekende upper bounds voor batch learning onder het full-set feedbackmodel en verbeteren bestaande bounds voor het geval met één correct antwoord van eindige naar oneindige klassen.

4. Betekenis en Claims

Het artikel claimt de eerste volledige combinatorische karakterisering te bieden van realiseerbaar online multi-label leren onder drie verschillende feedbackmodellen. De primaire theoretische betekenis ligt in de separatie tussen realiseerbare en agnostische leerbaarheid in de mistake-unknown setting, waar de standaard Littlestone-dimensie geen betekenisvolle regret bounds vangt.

Verder benadrukt het werk een rijke structuur in agnostisch multi-label leren:

• Het feedbackmodel verandert fundamenteel de haalbare regret-rates (van lineair naar constant).
• Het set-valued feedbackmodel staat constante regret toe op specifieke klassen en dimension-onafhankelijke bounds voor algemene klassen, een fenomeen dat niet wordt waargenomen in single-label leren.
• De resultaten suggereren dat het karakteriseren van agnostisch multi-label leren combinatorische objecten vereist die verder gaan dan die voldoende zijn voor realiseerbaar leren.

De auteurs merken expliciet op dat hun definities van regret verschillen van eerdere werken (bijv. Joshi et al. [JLB+25] en Raman et al. [RST24]) om beter aan te sluiten bij de onderliggende voorspeltaak van het minimaliseren van de fout tegen de ware verzameling acceptabele labels, in plaats van te concurreren tegen een hypothese die slechts een specifiek onthuld label bevat.