Online Learning-to-Defer with Varying Experts

Probleemformulering
Learning-to-Defer (L2D) is een raamwerk dat is ontworpen om voorspellende modellen te integreren met externe experts (menselijk of geautomatiseerd) om de betrouwbaarheid van systemen te verbeteren door onzekere of hoog-risico inputs door te sturen naar bekwaamere agenten. Waar bestaand L2D-onderzoek voornamelijk werkt in batch-omgevingen met vaste pools van experts en volledige supervisie (waarbij tijdens het trainen alle expertvoorspellingen worden waargenomen), staan real-world implementaties voor aanzienlijke uitdagingen: data arriveert sequentieel, de beschikbaarheid van experts fluctueert (bijvoorbeeld door diensten of beperkingen in middelen), en de betrouwbaarheid van experts kan in de loop van de tijd veranderen. Bovendien opereren praktische systemen vaak onder bandit-feedback, waarbij de leerder alleen het resultaat van de gekozen actie (voorspelling of specifieke expertvraag) waarneemt, in plaats van de grondwaarheid of de prestaties van alle beschikbare experts. Dit artikel adresseert de kloof tussen klassieke L2D-aannames en deze dynamische, online realiteiten door het eerste online L2D-raamwerk te introduceren voor multiclass-classificatie met bandit-feedback en een dynamisch variërende pool van experts.

Methodologie
De auteurs stellen een algemeen raamwerk voor waarbij, in elke ronde $t$, een uitgebreide input $(x_t, A_t)$ wordt onthuld, bestaande uit een feature-vector $x_t$ en een set van beschikbare experts $A_t$. De leerder moet beslissen of hij een class-label voorspelt of doorgaat naar een van de beschikbare experts in $A_t$. De interactie volgt een semi-adversariaal setting: inputs kunnen adversariaal worden gekozen, maar labels worden getrokken uit een vaste (hoewel onbekende) verdeling, conditioneel op de input.

De kernmethodologische bijdragen omvatten:

1. Ware Deferral-Loss en Surrogaat: De auteurs definiëren een ware deferral-loss $\ell_{def}$ die rekening houdt met kosten voor verkeerde classificatie en kosten voor expertvragen. Aangezien deze loss niet-differentieerbaar is, introduceren ze een convexe surrogaat-loss $\Phi_{def}$ die standaard score-gebaseerde surrogaatlosses (zoals de constrained hinge loss) uitbreidt naar de online, variërend-expert setting. Deze surrogaat is ontworpen om niet beïnvloed te worden door de scores van niet-beschikbare experts.
2. H-Consistentiegrenzen voor Online Learning: Een significante theoretische stap is de uitbreiding van $H$-consistentiegrenzen van batch learning naar de online setting. De auteurs bewijzen dat het minimaliseren van de surrogaat-deferral-regret in het online raamwerk een gebonden ware deferral-regret garandeert, mits de onderliggende surrogaat een $H$-consistentiegrens toestaat met betrekking tot de zero-one loss.
3. Algoritmeontwerp: Het voorgestelde algoritme (Algoritme 1) maakt gebruik van Online Gradient Descent (OGD) met geprojecteerde gradiënten. Om de beperking te hanteren dat de som van scores voor beschikbare labels nul moet zijn (vereist voor de constrained hinge loss), projecteert het algoritme de gewichtsmatrix op een haalbare deelruimte $K_{A_t}$ die specifiek is voor de huidige set van beschikbare experts. Deze projectie behoudt de voorspellingen van de hypothese op de beschikbare labelset. Het algoritme integreert een exploratie-rate $\gamma_t$ om de bandit-feedback te hanteren, waarbij de lossfunctie wordt geschat op basis van het waargenomen resultaat van de bemonsterde actie.

Kernbijdragen
Het artikel claimt vier primaire bijdragen:

1. Eerste Online L2D-raamwerk: Het introduceert het eerste raamwerk voor online Learning-to-Defer onder bandit-feedback, waarbij zowel de data-verdeling als de pool van experts in de loop van de tijd kunnen variëren.
2. Theoretische Uitbreiding: Het breidt het concept van $H$-consistentiegrenzen uit naar de online setting, een eigenschap die eerder beperkt was tot analyses van batch learning.
3. Regret-garanties: Het voorgestelde algoritme bereikt een regret-bound van $O((n + n_e)T^{2/3})$ in het algemene geval, waarbij $n$ het aantal klassen is en $n_e$ het aantal onderscheiden experts dat is waargenomen. Onder een low-noise (near-realizable) aanname verbetert dit tot $O((n + n_e)\sqrt{T})$.
4. Empirische Validatie: De aanpak wordt gevalideerd op zowel synthetische als real-world datasets (Reuters4 en CIFAR10H), waarbij de capaciteit wordt aangetoond om zich aan te passen aan variërende expert-beschikbaarheid en drijvende expertise.

Resultaten
Experimenten werden uitgevoerd onder drie regimes van toenemende complexiteit: (1) vaste beschikbaarheid en expertise, (2) drijvende beschikbaarheid met vaste expertise, en (3) volledig dynamische settings met zowel drijvende beschikbaarheid als drijvende expertise.

• Synthetische Data: Het algoritme leerde succesvol de optimale grens tussen voorspellen en deferral, en routeerde inputs consequent naar de meest bekwaam beschikbare experts. Het behield een lage deferral-loss en hoge nauwkeurigheid, zelfs wanneer de competentiegebieden van experts in de loop van de tijd verschoven.
• Real-World Data (Reuters4): In de meest uitdagende setting (drijvende beschikbaarheid en expertise) volgde de methode effectief bewegende competentiegebieden van experts. Het defereerde met hoge frequentie naar momenteel competente experts, behield stabiele kalibratie en bereikte taaknauwkeurigheid die vergelijkbaar was met baselines met vaste expertise.
• CIFAR10H: Met behulp van een WideResNet-predictor en menselijk geannoteerde experts, presteerde de methode beter dan een op vertrouwen gebaseerde baseline die uniform willekeurig defereert. Het geleerde beleid bereikte een lagere deferral-loss en hogere nauwkeurigheid, wat aangeeft dat het leerde voorbeelden door te sturen naar de meest geschikte experts in plaats van indiscriminately te deferen.

Betekenis
Het artikel positioneert zichzelf als een fundamentele stap richting het haalbaar maken van Learning-to-Defer-systemen voor real-world, niet-stationaire omgevingen. Door verder te gaan dan de aanname van vaste expert-pools en volledige supervisie, tonen de auteurs aan dat consistente op surrogaat gebaseerde methoden robuust kunnen worden gemaakt voor adversariale omgevingen en variërende expert-betrouwbaarheid. De theoretische vaststelling van $H$-consistentie in de online setting biedt een rigoureuze garantie dat het minimaliseren van surrogaat-loss leidt tot het minimaliseren van ware deferral-regret, waarmee een kritieke kloof wordt overbrugd tussen theoretische L2D-garanties en de praktische vereisten van streaming data en dynamische expert-systemen.