Online Conformal Prediction Beyond Feedback

Formulazione del Problema: Conformal Prediction Online Oltre il Feedback

La quantificazione dell'incertezza è fondamentale per l'implementazione del machine learning in applicazioni critiche per la sicurezza. La Conformal Prediction Online (OCP) offre un quadro teoricamente fondato per generare set di predizione che garantiscono che l'etichetta reale sia inclusa con una frequenza specificata dall'utente, anche per flussi di dati non i.i.d. e classificatori black-box. Tuttavia, i metodi standard di OCP si basano su un ciclo di feedback: dopo aver emesso un set di predizione, l'algoritmo riceve un feedback (ovvero l'etichetta reale o un segnale di copertura) per regolare i set futuri, compensando le mis-coperture passate.

Questo articolo affronta un setting in cui tale feedback non è disponibile o è proibitivo. In molti scenari critici per la sicurezza, come i probe latenti per i Large Language Models (LLM), un algoritmo può dover classificare gli input in categorie di sicurezza. Se il probe si astiene (interroga un essere umano o un sistema più forte), l'etichetta può infine diventare disponibile. Tuttavia, per gli input in cui il probe compie una decisione implementata, l'etichetta non viene mai osservata. Questo crea uno scenario "oltre il feedback" (beyond feedback): l'apprendista deve scegliere tra l'emettere un set di predizione o interrogare l'etichetta corretta, ma non può fare entrambe le cose. Di conseguenza, l'apprendista non osserva mai se un set di predizione implementato fosse corretto, impedendo i meccanismi di compensazione standard utilizzati dai metodi OCP esistenti.

Metodologia: OCP con Query (OCPQ)

Gli autori propongono la Online Conformal Prediction with Queries (OCPQ), un metodo progettato per questo protocollo "oltre il feedback". L'approccio procede in due fasi principali:

1. Riduzione al Monitoraggio Parziale: Il problema viene ridotto a un gioco di monitoraggio parziale finito. Le "braccia" (arms) del gioco consistono in un insieme finito di soglie di predizione $M \subset [0, 1]$ e un'azione separata di query.

   • Azione di Predizione: Selezionare una soglia $m \in M$ genera un set di predizione $\Gamma_C(x_t, m)$ basato su un classificatore black-box $C$. Questa azione non produce osservazioni (feedback nullo $\perp$) e nessun reward diretto.
   • Azione di Query: Selezionare l'azione di query rivela l'etichetta reale $y_t$ ma non produce alcun set di predizione e fornisce un reward pari a zero.
   • Struttura del Reward: L'algoritmo definisce una funzione di reward ausiliaria $R(m, t)$. Se l'etichetta reale è coperta dal set di predizione ($y_t \in \Gamma_C(x_t, m)$), il reward è $1 - m(1-\beta)$, dove $\beta$ è un parametro definito dall'utente che controlla il trade-off tra copertura ed efficienza. Se l'etichetta non è coperta, il reward è 0. L'azione di query produce sempre un reward di 0. Questa struttura incentiva l'apprendista a selezionare soglie strette (piccolo $m$) pur mantenendo la copertura.

2. Design dell'Algoritmo: OCPQ adatta il forecaster esponenzialmente pesato con etichette efficienti di Cesa-Bianchi, Lugosi e Stoltz (2004).

   • In ogni round $t$, l'algoritmo esegue una query con una probabilità fissa $\epsilon$.
   • Se viene effettuata una query, l'etichetta reale $y_t$ viene osservata. L'algoritmo aggiorna quindi le stime del reward cumulativo $\hat{Z}_{m,t}$ per tutte le soglie $m \in M$ utilizzando uno schema di ponderazione per probabilità inversa, ricostruendo efficacementamente il reward che sarebbe stato ottenuto se fosse stata fatta una predizione.
   • Se non viene effettuata una query, l'algoritmo campiona una soglia $m_t$ da una distribuzione esponenzialmente pesata basata sulle attuali stime $\hat{Z}_{m,t}$ e restituisce il corrispondente set di predizione. Non viene ricevuto alcun feedback.

Risultati Teorici

L'articolo stabilisce garanzie a orizzonte finito per OCPQ sotto un flusso di dati avversario oblivo di lunghezza $T$:

• Regret: Il regret atteso rispetto alla migliore soglia fissa a posteriori è $O(T^{2/3})$. Nello specifico, con $\epsilon = T^{-1/3}$ e $\eta = T^{-2/3}\sqrt{\ln|M|}$, il regret è limitato da $T^{2/3}(2\sqrt{\ln|M|} + 1)$. Gli autori osservano che questo tasso è asintoticamente ottimale per questa classe di giochi di monitoraggio parziale.
• Copertura: Il tasso di copertura atteso $p_{cover}$ soddisfa:
  $$E[p_{cover}] \ge \beta - O(T^{-1/3})$$
  Ciò garantisce che la copertura si avvicini al target $\beta$ definito dall'utente all'aumentare di $T$.
• Tasso di Query: L'algoritmo interroga l'etichetta solo in una frazione attesa di $T^{-1/3}$ di round.
• Limiti ad Alta Probabilità: Il documento deriva anche limiti ad alta probabilità per sia il regret che la copertura, dimostrando che la varianza delle prestazioni dell'algoritmo è controllata e non presenta comportamenti patologici.

Risultati Empirici

Gli esperimenti sono stati condotti su dataset reali per validare l'approccio:

• Spostamento della Distribuzione (Distribution Shift): OCPQ è stato testato su benchmark standard (MNIST, CIFER-10, CIFER-100) dove la distribuzione di training differiva dalla distribuzione di test (ad esempio, da MNIST a USPS, o da MNIST a MNIST-C). I risultati hanno mostrato che il trade-off copertura-efficienza può essere controllato tramite il parametro $\beta$. La copertura empirica ha costantemente superato il limite teorico inferiore.
• Monitoraggio della Sicurezza degli LLM: Il metodo è stato applicato al monitoraggio della sicurezza per prompt di LLM utilizzando il dataset WildGuardMix, che include sia prompt vanilla che riscritti in modo avversariale. L'accuratezza del classificatore base è scesa significativamente sui prompt avversariali, eppure OCPQ ha mantenuto la copertura sopra il limite teorico mantenendo i set di predizione informativi.
• Confronto: Rispetto ad Adaptive Conformal Inference (ACI), che assume il feedback completo, OCPQ ha raggiunto frontiere di copertura-efficienza comparabili nonostante l'uso di una quantità di informazioni significativamente minore (interrogando solo circa il 5% dei round).

Significato e Contributi

L'articolo rivendica i seguenti contributi:

1. Nuovo Protocollo: Formula la OCP in un setting "oltre il feedback" dove le predizioni implementate non vengono mai valutate, uno scenario comune nelle applicazioni critiche per la sicurezza dove le etichette sono disponibili solo per le query di astensione.
2. Riduzione Algoritmica: Riduce questo problema a un gioco di monitoraggio parziale e adatta le tecniche di apprendimento avversariale con etichette efficienti per risolverlo, modificando specificamente il forecaster per trattare le query come azioni distinte che sostituiscono, anziché seguire, le predizioni.
3. Garanzie Teoriche: Fornisce garanzie di regret atteso e copertura a orizzonte finito per la OCP in questo setting, dimostrando che una quantificazione dell'incertezza valida è possibile con sole $O(T^{-1/3})$ query di etichette.
4. Efficacia Pratica: Gli esperimenti dimostrano che la supervisione sparsa (query casuali) è sufficiente per mantenere utili trade-off tra copertura ed efficienza, anche sotto spostamenti distributivi avversariali, senza richiedere feedback dalle predizioni implementate.

Gli autori osservano che, sebbene il metodo sia conservativo (la copertura empirica spesso supera il limite), ciò è una conseguenza dei deboli assunti richiesti dalla formulazione del gioco di monitoraggio parziale. Il lavoro futuro potrebbe esplorare metodi meno conservativi o estensioni per avversari adattivi.