Riepilogo Tecnico: Conformal Prediction Online Senza Parametri e Condizionale per Gruppi

1. Impostazione del Problema e Motivazione

I modelli di machine learning vengono sempre più impiegati in ambienti ad alto rischio e non stazionari (ad es., triage medico, veicoli autonomi) dove le distribuzioni dei dati cambiano nel tempo, violando l'assunto di scambiabilità richiesto dalla Conformal Prediction (CP) standard. La Online Conformal Prediction (OCP) affronta questo problema generando una sequenza di insiemi di predizione per flussi di dati avversari. Tuttavia, i metodi OCP standard garantiscono tipicamente solo la copertura marginale (ovvero, il tasso di errore complessivo si avvicina a $1-\alpha$). Questa garanzia marginale può mascherare una sottocopertura sistematica per specifiche sottopopolazioni, portando a problemi di equità (fairness) e sicurezza.

Sebbene lavori precedenti abbiano proposto la Group-Conditional OCP (G-OCP) per garantire garanzie di copertura per gruppi specifici, i metodi esistenti (ad es., GCACI) si basano su learning rates (step size) che devono essere sintonizzati manualmente. In ambienti di dati avversari o in evoluzione, la sintonizzazione dei learning rate è problematica perché:

1. Non è disponibile un set di validazione per la sintonizzazione.
2. Cambiamenti arbitrari nei dati possono rendere inappropriato un learning rate precedentemente "buono".
3. I metodi parameter-free esistenti (ad es., UP-OCP) ottengono solo la copertura marginale, non le garanzie condizionali per gruppo.

Il problema centrale affrontato è la progettazione di un algoritmo OCP senza parametri che fornisca simultaneamente rigorose garanzie di copertura condizionale per gruppo senza richiedere la sintonizzazione manuale degli iperparametri.

2. Metodologia: POGO

Gli autori propongono POGO (Portfolios for Online Group Conformal), il primo algoritmo senza parametri per la G-OCP. La metodologia si basa sul concetto di ottimizzazione della Universal Portfolio (UP), precedentemente applicata alla marginal OCP (UP-OCP), ed estende tale concetto per gestire molteplici gruppi sovrapposti.

2.1 Formulazione del Problema

Dato un flusso di dati $(X_t, Y_t)$ e un predittore $\hat{Y}_t$, l'obiettivo è apprendere una sequenza di raggi $\tau_t$ tali che l'intervallo di predizione $I_t = [\hat{Y}_t - \tau_t, \hat{Y}_t + \tau_t]$ soddisfi:
$$\lim_{T \to \infty} \left| \frac{1}{T_j} \sum_{t=1}^T \mathbb{1}\{Y_t \in I_t\} c_j(X_t) - (1-\alpha) \right| = 0$$
per tutti i $k$ gruppi, dove $c_j(X_t) \in [0, 1]$ è una funzione indicatrice "soft" per l'appartenenza al gruppo, e $T_j$ è il conteggio cumulativo del gruppo $j$.

2.2 Parametrizzazione Lineare

A differenza della OCP standard che apprende un raggio scalare, POGO apprende un vettore di parametri $k$-dimensionale $\theta_t \in \mathbb{R}^k$. Il raggio è parametrizzato come una funzione lineare del vettore di appartenenza al gruppo $c(X_t)$:
$$\tau_t(X_t) = \langle \theta_t, c(X_t) \rangle$$
Ciò consente all'algoritmo di assegnare diversi raggi in base alle specifiche appartenenze di gruppo di un campione, garantendo al contempo la produzione di un singolo intervallo di predizione unificato.

2.3 Meccanismo di Ottimizzazione del Portafoglio

POGO tratta l'apprendimento di $\theta_t$ come un problema di ottimizzazione di un portafoglio.

1. Subgradient come Errori: L'algoritmo definisce una perdita di quantile (pinball loss) per ogni gruppo. Il subgradiente $g_t$ di questa perdita quantifica l'errore di mancata copertura. Nello specifico, l' $j$-esimo elemento della somma cumulativa dei subgradient $\sum g_{t,j}$ corrisponde all'errore di mancata copertura per il gruppo $j$.
2. Processi di Ricchezza: Per ogni gruppo $j$, POGO costruisce un "mercato" con due titoli. I rendimenti di questi titoli dipendono dal fatto che la predizione copra o meno il valore reale:
   • Se la predizione manca (sottocopertura), un titolo genera un rendimento elevato.
   • Se la predizione copre, l'altro titolo genera un rendimento modesto.
3. Universal Portfolio (UP): POGO impiega l'algoritmo Universal Portfolio per apprendere una sequenza di pesi di portafoglio $\lambda_{t,j}$ per ogni gruppo $j$. L'obiettivo è massimizzare la crescita logaritmica della "ricchezza" $W_{t,j}$ associata a ciascun gruppo.
4. Aggiornamento dei Parametri: I parametri $\theta_{t,j}$ sono derivati direttamente dai processi di ricchezza $W_{t,j}$ e dai pesi del portafoglio $\lambda_{t,j}$, assicurando che i subgradient cumulativi crescano lentamente. Questa crescita lenta si traduce direttamente in una mancata copertura condizionale per gruppo limitata.

Fondamentalmente, questo processo è senza parametri; non richiede un learning rate $\eta$ o una step size, affidandosi invece alle proprietà intrinseche dell'algoritmo Universal Portfolio.

3. Contributi Chiave

1. Primo Algoritmo G-OCP Senza Parametri: L'introduzione di POGO, che fornisce garanzie di copertura condizionale per gruppo senza la sintonizzazione manuale dei learning rate.
2. Garanzie Rigorose nel Tempo Finito: Gli autori stabiliscono i limiti di copertura per POGO. Il tasso di mancata copertura per il gruppo $j$ è limitato da:
   $$\text{MisCov}_T(c_j) \leq \frac{1}{T_j} \left[ U_T(k) + \sqrt{2T_j \alpha(1-\alpha) U_T(k)} \right]$$
   dove $U_T(k)$ scala logaritmicamente con il numero di gruppi $k$ e il tempo $T$. Questo rappresenta i migliori risultati noti di copertura per gruppo nel tempo finito.
3. Scalabilità Superiore: L'analisi teorica mostra che il limite di errore di POGO dipende logaritmicamente dal numero di gruppi ($O(\ln k)$), mentre i metodi esistenti dipendenti dai parametri (come GCACI) scalano con $\sqrt{k}$ e dipendono fortemente dalla scelta del learning rate.
4. Output a Intervallo Singolo: A differenza degli approcci ingenui che eseguono algoritmi OCP separati per ogni gruppo (producendo $k$ raggi differenti), POGO produce un singolo raggio $\tau_t$ per ogni campione, evitando problemi di intervalli conflittuali e potenziali fughe di privacy riguardanti l'appartenenza al gruppo.

4. Risultati Sperimentali

Gli autori valutano POGO su dataset sintetici e reali, confrontandolo con GCACI (lo standard attuale per la OCP condizionale per gruppo) e UP-OCP (marginale OCP senza parametri).

4.1 Esperimenti Sintetici

• Punteggi Limitati e Varianti Gradualmente: POGO raggiunge i tassi di copertura target entro il 3% per tutti i gruppi e produce i raggi medi più piccoli rispetto alle varianti di GCACI. Mantiene un'alta adattività, con la sequenza più lunga di eventi di mancata copertura comparabile al miglior GCACI sintonizzato.
• Spostamenti Abrupt (Ripidi): Quando le distribuzioni dei dati cambiano bruscamente, POGO rimane robusto. Al contrario, GCACI con un learning rate fisso (anche uno ben sintonizzato come $\eta=0.01$) soffre di una scarsa adattività, mostrando lunghe sequenze di mancata copertura finché il learning rate non viene effettivamente "ri-sintonizzato" dai dati.
• Punteggi Crescenti Non Limitati: In scenari in cui i punteggi di non conformità crescono quadraticamente per un gruppo specifico, la maggior parte delle varianti di GCACI fallisce nel raggiungere la copertura target. POGO raggiunge costantemente una copertura più vicina ai livelli target, particolarmente con requisiti di copertura elevati ($1-\alpha \in [0.9, 0.95]$).

4.2 Dati del Mondo Reale

• MIMIC-IV (Degenza in Terapia Intensiva): Utilizzando dati di pazienti (razza, assicurazione, sesso come gruppi), POGO raggiunge una copertura comparabile a GCACI ma con dimensioni dei set di predizione (raggi) minori.
• Mercato Azionario (Apple, Delta, Boeing): Per la predizione dei prezzi giornalieri, POGO dimostra nuovamente prestazioni competitive, raggiungendo la copertura target con dimensioni dei set più piccole rispetto a GCACI.
• Trade-off: Sebbene POGO presenti talvolta sequenze di mancata copertura consecutiva leggermente più lunghe rispetto al miglior GCACI sintonizzato in specifici regimi statici, supera significativamente GCACI in regimi dinamici o in evoluzione dove la sintonizzazione è impossibile.

5. Significato e Rivendicazioni

L'articolo sostiene che POGO getti le basi per una quantificazione dell'incertezza equa e robusta in ambienti mutevoli. Unificando la copertura condizionale per gruppo con l'apprendimento online senza parametri, il metodo elimina la necessità di sintonizzazione manuale degli iperparametri, che rappresenta un collo di bottiglia critico in contesti avversari o non stazionari.

Gli autori sottolineano che:

• POGO fornisce i migliori limiti di copertura per gruppo nel tempo finito noti.
• Raggiunge queste garanzie senza la fragilità della selezione del learning rate.
• Offre una soluzione pratica per applicazioni ad alto rischio dove è richiesta l'equità tra le sottopopolazioni e dove non si può assumere che le distribuzioni dei dati siano statiche o scambiabili.

Il documento conclude con modestia, notando che sebbene POGO utilizzi una specifica lineare per i raggi, il lavoro futuro potrebbe esplorare modelli più ricchi per il raggio ed estendere questi strumenti ad altre forme di quantificazione dell'incertezza online, come la calibrazione.