Approximate full conformal prediction in an RKHS

Sintesi Tecnica: Predizione Conforme Completa Approssimata in un RKHS

Problema
La predizione conforme completa è un framework distribuito senza ipotesi (distribution-free) che costruisce regioni di predizione con intervalli di confidenza con copertura garantita per una vasta gamma di stimatori. Tuttavia, la sua applicazione pratica è severamente limitata dall'intratabilità computazionale. Per calcolare la regione di predizione conforme completa per un nuovo input $X_{n+1}$, è necessario valutare uno score di non-conformità per ogni possibile candidato output $y \in \mathcal{Y}$. Poiché il predittore sottostante $\hat{f}_{D_y}$ deve essere riaddestrato per ogni candidato $y$ (dove $D_y$ include il nuovo punto $(X_{n+1}, y)$), ciò richiede l'addestramento di un numero infinito di stimatori quando $\mathcal{Y} = \mathbb{R}$.

Le alternative esistenti, come la predizione split-conformal e cross-conformal, riducono i costi computazionali addestrando un numero fisso di predittori. Tuttavia, questi metodi comportano una perdita di informazione scartando dati durante l'addestramento o la suddivisione, risultando spesso in regioni di predizione più ampie e meno informative. Altri approcci basati su soluzioni in forma chiusa (ad esempio, per la regressione ridge) o su specifiche forme di p-value sono limitati a contesti ristretti e non si generalizzano ad arbitrarie funzioni di perdita o a Spazi di Hilbert con Kernel Riproducenti (RKHS).

Metodologia
Gli autori propongono una strategia generica per approssimare efficientemente la regione di predizione conforme completa senza suddividere i dati. Il nucleo della metodologia prevede:

1. Predittori Approssimati: Invece di riaddestrare il predittore per ogni candidato $y$, il metodo approssima il predittore $\hat{f}_{D_y}$ utilizzando un predittore fisso $\hat{f}_{D_z}$ (addestrato su un punto fisso $z$) o una correzione del primo ordine basata su funzioni di influenza.
2. Score di Non-Conformità Approssimati: Utilizzando il predittore approssimato, gli autori definiscono score di non-conformità approssimati $\tilde{S}_{D_y}$.
3. Limitazione dell'Errore di Approssimazione: Fondamentalmente, il metodo deriva espliciti limiti superiori ($\tau$) sulla discrepanza tra gli score veri e quelli approssimati. Questi limiti dipendono dalla regolarità (smoothness) della funzione di perdita e dalle proprietà del kernel.
4. "Sandwiching" della Regione: Incorporando questi limiti di errore nel calcolo del p-value conforme, gli autori costruiscono una regione approssimata "superiore" ($\hat{C}^{up}$) e una regione approssimata "inferiore" ($\hat{C}^{lo}$). La vera regione conforme completa è garantita trovarsi all'interno di questo sandwich ($\hat{C}^{lo} \subseteq \hat{C}^{full} \subseteq \hat{C}^{up}$).
5. Quantificazione dello Spessore (Thickness): Viene introdotta una nuova metrica chiamata "spessore" per quantificare il volume della differenza simmetrica tra le regioni di predizione approssimate e quelle conformi complete, fornendo una misura della compattezza dell'approssimazione oltre la semplice probabilità di copertura.

Il paper sviluppa tre livelli di approssimazione basati sulle assunzioni di regolarità della funzione di perdita:

• Livello 0 (Stabilità Uniforme): Utilizza costanti Lipschitz uniformi per le funzioni di perdita e di score. Questo recupera limiti simili agli approcci di stabilità uniforme ma permette l'uso di funzioni di perdita generali in RKHS.
• Livello 1 (Stabilità Locale): Sfrutta la differenziabilità della funzione di perdita per derivare limiti di stabilità locale che variano con $y$, rendendo più stretti i costanti di approssimazione.
• Livello 2 (Funzioni di Influenza): Sfrutta una regolarità di ordine superiore (funzioni di perdita due e tre volte differenziabili) e le funzioni di influenza (funzione di influenza di Bouligand) per creare un'approssimazione del predittore che dipende da $y$ tramite un'espansione di Taylor del primo ordine. Ciò produce tassi di convergenza più rapidi per l'errore di approssimazione.

Contributi Chiave

• Strategia di Approssimazione Generica: Il lavoro fornisce un framework generico e distribuito senza ipotesi per approssimare le regioni conformi complete in contesti RKHS con funzioni di perdita generali (non quadratiche), incluse perdite robuste come Logcosh, Pseudo-Huber e la versione smussata di Pinball.
• Garanzie Non-Asintotiche: A differenza dei precedenti approcci basati sulle funzioni di influenza che offrono solo garanzie asintotiche, questo lavoro fornisce limiti non-asintotici sulla qualità dell'approssimazione e assicura che la regione risultante sia una regione di confidenza valida (copertura $\geq 1-\alpha$).
• Metrica dello Spessore: L'introduzione dello "spessore" permette di quantificare la discrepanza tra le regioni di predizione approssimate e quelle conformi complete in termini di volume (misura di Lebesgue), non solo di probabilità di copertura.
• Miglioramento dei Tassi di Convergenza: Utilizzando le funzioni di influenza e assunzioni di regolarità di ordine superiore, gli autori dimostrano che l'errore di approssimazione decade a un tasso più veloce ($O(n^{-1+r+\min(-1+2r, 0)})$) rispetto ai limiti di stabilità uniforme ($O(n^{-1+r})$), specialmente quando il parametro di regolarizzazione $\lambda$ decade lentamente.

Risultati

• Limiti Teorici: L'analisi teorica mostra che lo spessore dell'approssimazione è limitato superiormente da termini dipendenti dalle proprietà del kernel, dal parametro di regolarizzazione e dalla regolarità della perdita. Per funzioni di perdita regolari, i limiti si stringono significativamente all'aumentare della dimensione del campione $n$.
• Performance Empirica: Gli esperimenti su dati sintetici (Friedman1) confrontano quattro strategie: Split-conformal, Uniform Stability (Livello 0), Local Stability (Livello 1) e Influence Function (Livello 2).
  • Copertura: Tutti i metodi proposti raggiungono una copertura empirica vicina al livello target ($1-\alpha = 0.9$).
  • Dimensione della Regione: Il metodo basato sulla Funzione di Influenza produce le regioni di predizione più strette (più informative) con bassa varianza, superando sia il metodo split-conformal che quelli basati sulla stabilità.
  • Computazione: Sebbene il metodo della Funzione di Influenza richieda più tempo di calcolo (a causa dell'inversione della matrice Hessiana), rimane trattabile. Il metodo della Stabilità Locale offre un compromesso favorevole tra precisione e costo computazionale.
• Visualizzazione: I grafici log-log dello scarto di "spessore" rispetto alla dimensione del campione confermano i tassi di convergenza teorici, mostrando che l'approccio della Funzione di Influenza converge più velocemente dell'approccio di stabilità uniforme.

Significatività e Rivendicazioni
Gli autori affermano che il loro lavoro colma il divario tra l'ottimalità teorica della predizione conforme completa e la fattibilità computazionale dei metodi split-conformal. Evitando la suddivisione dei dati, il metodo proposto utilizza l'intero dataset per l'addestramento, preservando così l'informazione e producendo regioni di predizione più strette. Il framework è significativo perché estende l'approssimazione conforme completa a una vasta classe di funzioni di perdita e contesti RKHS, fornendo garanzie non-asintotiche rigorose sia sulla copertura che sulla "compattezza" (spessore) delle regioni risultanti. Il paper sottolinea che, sebbene l'approssimazione sia computazionalmente efficiente (richiedendo solo uno o pochi calcoli del predittore), essa mantiene la validità distribution-free del framework conforme completo.