Online Learning-to-Defer with Varying Experts

Formulazione del Problema
L'Apprendimento per la Rinuncia (Learning-to-Defer, L2D) è un framework progettato per integrare modelli predittivi con esperti esterni (umani o automatizzati) al fine di migliorare l'affidabilità del sistema instradando input incerti o ad alto rischio verso agenti più competenti. Sebbene la ricerca esistente sull'L2D operi principalmente in contesti batch con pool di esperti fissi e supervisione completa (osservando tutte le previsioni degli esperti durante l'addestramento), le implementazioni nel mondo reale affrontano sfide significative: i dati arrivano in sequenza, la disponibilità degli esperti fluttua (ad esempio, a causa di turni o vincoli di risorse) e l'affidabilità degli esperti può subire variazioni nel tempo. Inoltre, i sistemi pratici operano spesso sotto feedback a bandito, dove l'apprendente osserva solo l'esito dell'azione scelta (previsione o interrogazione specifica di un esperto) piuttosto che la verità fondamentale o le prestazioni di tutti gli esperti disponibili. Questo lavoro colma il divario tra le assunzioni classiche dell'L2D e queste realtà dinamiche e online introducendo il primo framework L2D online per la classificazione multiclasse con feedback a bandito e un pool di esperti dinamicamente variabile.

Metodologia
Gli autori propongono un framework generale in cui, ad ogni round $t$, viene rivelato un input aumentato $(x_t, A_t)$, costituito da un vettore di caratteristiche $x_t$ e un insieme di esperti disponibili $A_t$. L'apprendente deve decidere se prevedere un'etichetta di classe o rinviare a uno degli esperti disponibili in $A_t$. L'interazione segue un setting semi-avversario: gli input possono essere scelti in modo avversario, ma le etichette sono estratte da una distribuzione fissa (sebbene sconosciuta) condizionata all'input.

I principali contributi metodologici includono:

1. Perdita di Rinuncia Reale e Surrogato: Gli autori definiscono una perdita di rinuncia reale $\ell_{def}$ che tiene conto dei costi di classificazione errata e dei costi di interrogazione degli esperti. Poiché questa perdita non è differenziabile, introducono una funzione di perdita surrogata convessa $\Phi_{def}$ che estende i surrogati basati su punteggi standard (come la funzione di perdita a cerniera vincolata) al setting online con pool di esperti variabile. Questo surrogato è progettato per non essere influenzato dalle punteggi degli esperti non disponibili.
2. Limiti di H-Consistenza per l'Apprendimento Online: Un significativo passo teorico è l'estensione dei limiti di $H$-consistenza dall'apprendimento batch al setting online. Gli autori dimostrano che la minimizzazione del rimpianto della rinuncia surrogata nel framework online garantisce un rimpianto della rinuncia reale limitato, a condizione che il surrogato sottostante ammetta un limite di $H$-consistenza rispetto alla perdita zero-uno.
3. Progettazione dell'Algoritmo: L'algoritmo proposto (Algoritmo 1) utilizza la Discesa del Gradiente Online (OGD) con gradienti proiettati. Per gestire il vincolo secondo cui la somma delle punteggi per le etichette disponibili deve essere zero (richiesto dalla funzione di perdita a cerniera vincolata), l'algoritmo proietta la matrice dei pesi su un sottospazio ammissibile $K_{A_t}$ specifico per l'insieme corrente di esperti disponibili. Questa proiezione preserva le previsioni dell'ipotesi sull'insieme di etichette disponibile. L'algoritmo incorpora un tasso di esplorazione $\gamma_t$ per gestire il feedback a bandito, stimando la funzione di perdita basandosi sull'esito osservato dell'azione campionata.

Principali Contributi
Il lavoro rivendica quattro contributi primari:

1. Primo Framework L2D Online: Introduce il primo framework per l'Apprendimento per la Rinuncia online sotto feedback a bandito, dove sia la distribuzione dei dati sia il pool di esperti possono variare nel tempo.
2. Estensione Teorica: Estende la nozione di limiti di $H$-consistenza al setting online, una proprietà precedentemente limitata alle analisi di apprendimento batch.
3. Garanzie di Rimpianto: L'algoritmo proposto raggiunge un limite di rimpianto di $O((n + n_e)T^{2/3})$ nel caso generale, dove $n$ è il numero di classi e $n_e$ è il numero di esperti distinti osservati. Sotto un'ipotesi a basso rumore (quasi-realizzabile), questo migliora a $O((n + n_e)\sqrt{T})$.
4. Validazione Empirica: L'approccio è validato su dataset sintetici e reali (Reuters4 e CIFAR10H), dimostrando la sua capacità di adattarsi alla disponibilità variabile degli esperti e alla deriva delle competenze.

Risultati
Gli esperimenti sono stati condotti sotto tre regimi di complessità crescente: (1) disponibilità e competenze fisse, (2) disponibilità in deriva con competenze fisse, e (3) setting completamente dinamici con sia disponibilità in deriva sia competenze in deriva.

• Dati Sintetici: L'algoritmo ha appreso con successo il confine ottimale tra previsione e rinuncia, instradando coerentemente gli input verso gli esperti disponibili più competenti. Ha mantenuto una bassa perdita di rinuncia e un'alta accuratezza anche quando le regioni di competenza degli esperti si sono spostate nel tempo.
• Dati Reali (Reuters4): Nel setting più impegnativo (disponibilità e competenze in deriva), il metodo ha tracciato efficacemente le regioni di competenza degli esperti in movimento. Ha rinviato con alta frequenza agli esperti attualmente competenti, preservando una calibrazione stabile e raggiungendo un'accuratezza del compito paragonabile a quella delle baseline a competenze fisse.
• CIFAR10H: Utilizzando un predittore WideResNet e esperti annotati da umani, il metodo ha superato una baseline basata sulla confidenza che rinviava in modo uniforme e casuale. La politica appresa ha ottenuto una perdita di rinuncia inferiore e un'accuratezza superiore, indicando che ha imparato a instradare gli esempi verso gli esperti più adatti piuttosto che rinviare indiscriminatamente.

Significato
Il lavoro si posiziona come un passo fondamentale verso la realizzazione di sistemi di Apprendimento per la Rinuncia per ambienti reali non stazionari. Superando l'assunzione di pool di esperti fissi e supervisione completa, gli autori dimostrano che i metodi basati su surrogati coerenti possono essere resi robusti agli ambienti avversari e alla variabilità dell'affidabilità degli esperti. L'istituzione teorica della $H$-consistenza nel setting online fornisce una garanzia rigorosa secondo cui la minimizzazione della perdita surrogata porta alla minimizzazione del rimpianto della rinuncia reale, colmando un divario critico tra le garanzie teoriche dell'L2D e i requisiti pratici dei dati in streaming e dei sistemi di esperti dinamici.