Universal Multiclass Transductive Online Learning

Technische Samenvatting: Universele Multiclass Transductieve Online Learning

Probleemstelling
Dit artikel onderzoekt het probleem van universele transductieve online classificatie met een telbaar oneindige labelruimte. In deze setting neemt een leerder deel aan een sequentiële game tegen een tegenstander (adversary). Voordat de game begint, selecteert de tegenstander een sequentie van instanties $X = \{X_t\}_{t \in \mathbb{N}}$ en onthult de volledige sequentie vooraf aan de leerder. In elke ronde $t$ voorspelt de leerder een label $\hat{Y}_t$ op basis van de bekende sequentie van instanties en de geschiedenis van ware labels $Y_{<t}$. De tegenstander onthult vervolgens het ware label $Y_t$. De prestaties van de leerder worden gemeten aan de hand van het aantal fouten (in de realizable setting) of regret (in de agnostische setting).

Het kerndoel is het karakteriseren van de universele leerbaarheid van een conceptklasse $\mathcal{H}$. In tegenstelling tot uniforme snelheden die onafhankelijk zijn van de specifieke datasequentie, vereist universele leerbaarheid dat voor elke realizable sequentie er een algoritme bestaat waarvan het aantal fouten sublineair groeit (of voldoet aan specifieke grenzen) met de tijdshorizon $T$. Het artikel richt zich specifiek op de kloof in de bestaande literatuur, die zich voornamelijk heeft gericht op binaire classificatie of uniforme snelheden, door deze concepten uit te breiden naar multiclass-settings met onbegrensde labels.

Methodologie en Kernconcepten
De auteurs maken gebruik van combinatorische speltheorie en structurele analyse van conceptklassen om leerbaarheidsvoorwaarden af te leiden.

1. Combinatorische Structuren:

   • Littlestone Tree: Een standaardstructuur voor online learning waarbij knopen instanties zijn en randen labels.
   • Level-Constrained Littlestone (LCL) Tree: Een variatie waarbij alle knopen op dezelfde diepte dezelfde instantie delen.
   • LCL-Littlestone (LCLL) Tree: Een nieuwe structuur geïntroduceerd in dit werk. Het breidt de Littlestone-boom uit naar multiclass-settings met onbegrensde labels. In een LCLL-boom is een knoop op diepte $k$ geassocieerd met een sequentie van $k+1$ instanties, en randen vertegenwoordigen sequenties van labels die overeenkomen met paden in een diepte-$k+1$ LCL-boom.
   • Indifferent Property (Onverschilligheidseigenschap): Een cruciale eigenschap aangepast uit binair classificatiewerk (Bousquet et al., 2023). Een boom is "indifferent" als voor elke knoop $v$ die vóór knoop $u$ verschijnt in de Breadth-First-Search (BFS) volgorde, alle afstammelingen van $u$ instemmen met het label van $v$. Deze eigenschap stelt een tegenstander in staat om een random walk-strategie te gebruiken om fouten te forceren, zelfs wanneer de leerder de sequentie van instanties kent.

2. Speltheoretische Aanpak (Gale-Stewart Games):
   De auteurs ontwerpen een nieuwe Gale-Stewart game om leerbaarheid te karakteriseren. In tegenstelling tot eerdere games waar de tegenstander een sequentie van instanties voorstelt, stelt de tegenstander hier een "level-constrained tree" voor (een sequentie van instanties en een verzameling mogelijke labelsequenties). De leerder (Speler B) probeert een pad te selecteren dat consistent is met de conceptklasse.

   • Een belangrijke technische bijdrage is het ontwerp van deze game om de indifferent property te vangen. De auteurs tonen aan dat standaard uitbreidingen van binaire classificatiebomen (zoals DSL- of LCL-bomen) falen in het karakteriseren van leerbaarheid in de onbegrensde multiclass-setting, omdat de "indifferent" eigenschap niet automatisch geldt voor oneindige bomen in deze context.
   • Ze maken gebruik van de Borel Determinacy Theorem om vast te stellen dat als de conceptklasse geen oneindige indifferent LCLL-boom heeft, de leerder (Speler B) een winnende strategie heeft.

3. Algoritme Ontwerp:

   • Realizable Setting: De auteurs stellen algoritmen voor die de voortgang van de Gale-Stewart game volgen. Als de game vordert (wat wijst op de aanwezigheid van een shattered subsequence), werkt het algoritme zijn status bij. Als de game stagneert, schakelt het algoritme over naar een weighted majority strategy (met een gewichtfunctie gebaseerd op shattered subsequences) om de resterende gedeeltelijke conceptklasse te leren.
   • Agnostic Setting: De auteurs breiden het realizable algoritme uit met een "learning with experts" framework. Ze construeren een tellbare verzameling experts op basis van het gedrag van het realizable algoritme op gehalucineerde sequenties en foutindices, waarbij ze de Squint-algoritme (Koolen & van Erven, 2015) met niet-uniforme initiële gewichten gebruiken om regret te minimaliseren.

Belangrijkste Resultaten

1. Trichotomie voor de Realizable Setting:
   Het artikel stelt een trichotomie vast voor de optimale foutensnelheden van universele transductieve online learning met onbegrensde labels:

   • Constante Fouten ($O(1)$): Bereikbaar indien en slechts indien $\mathcal{H}$ geen oneindige indifferent Littlestone-boom heeft.
   • Logaritmische Fouten ($\Theta(\log T)$): Bereikbaar indien en slechts indien $\mathcal{H}$ een oneindige indifferent Littlestone-boom heeft maar geen oneindige indifferent LCLL-boom.
   • Lineaire Fouten ($\Omega(T)$): Indien $\mathcal{H}$ een oneindige indifferent LCLL-boom heeft, kan geen enkel algoritme sublineaire fouten garanderen.

2. Agnostic Setting:

   • Een conceptklasse $\mathcal{H}$ is agnostisch universeel transductief online leerbaar indien en slechts indien deze geen oneindige indifferent LCLL-boom heeft.
   • Voor dergelijke klassen bieden de auteurs een algoritme dat een regret bound van $\tilde{O}(\sqrt{T})$ bereikt (waarbij poly-logaritmische factoren verborgen zijn).
   • Een lower bound wordt bewezen die aantoont dat voor elke klasse die ten minste twee verschillende concepten bevat, de regret niet $o(\sqrt{T})$ kan zijn.

3. Stochastische Proces Extensie:
   De resultaten worden uitgebreid naar de setting waarin de leerder alleen het stochastische proces kent dat de instantie-sequentie genereert (in plaats van de sequentie zelf). De voorwaarde voor "alle processen die universele online learning toelaten" wordt getoond gelijk te zijn aan de afwezigheid van een oneindige indifferent LCLL-boom.

Betekenis en Claims
Het artikel claimt verschillende significante bijdragen aan de theorie van online learning:

• Oplossing voor de Onbegrensde Multiclass Casus: Het biedt de eerste volledige karakterisering van universele transductieve online learning voor multiclass-problemen met tellbaar oneindige labelruimtes, waarmee de kloof die achterbleef door binaire of eindige labelstudies wordt gedicht.
• Nieuwe Combinatorische Karakterisering: De introductie van de Level-Constrained-Littlestone-Littlestone (LCLL) boom en de indifferent property als de correcte karakterisering voor deze setting. De auteurs merken expliciet op dat eerdere kandidaten (DSL-bomen, LCL-bomen of standaard Littlestone-bomen) onvoldoende zijn, zoals aangetoond door tegenvoorbeelden waarbij een klasse een oneindige LCLL-boom heeft maar toch leerbaar blijft, of een oneindige Littlestone-boom heeft maar de vereiste indifferent property mist voor de lower bound.
• Nieuw Spelontwerp: Het artikel benadrukt het ontwerp van een specifieke Gale-Stewart game waarbij de tegenstander labelsequenties voor intervallen van instanties voorstelt, in plaats van alleen instanties. Dit ontwerp wordt gepresenteerd als een conceptuele bijdrage die noodzakelijk is om de indifferent property te vangen in onbegrensde settings, waar standaard spelstructuren tekortschieten.
• Optimistisch Universeel Leren: Het werk verbindt transductieve leerbaarheid met het bredere probleem van "optimistisch universeel online leren" (leren wanneer leren mogelijk is). Het verheldert dat het kennen van de instantie-sequentie (transductief) of het stochastische proces (optimistisch) leidt tot dezelfde leerbaarheidsvoorwaarden gedefinieerd door de LCLL-boomstructuur.

De auteurs blijven bescheiden over de agnostische setting en erkennen een poly-logaritmische kloof tussen de upper bound ($\tilde{O}(\sqrt{T})$) en de lower bound ($\Omega(\sqrt{T})$), en laten het aanscherpen van deze kloof als een open vraag. Ze identificeren ook de karakterisering van universele online learning voor processen met onbegrensde labels als een open probleem.