Active Calibration of Reachable Sets Using Approximate Pick-to-Learn

1. Il Problema: Calibrazione dei Set Raggiungibili

Nelle applicazioni critiche per la sicurezza (come la robotica o l'aviazione), l'analisi di raggiungibilità (reachability analysis) è fondamentale per garantire la sicurezza dei sistemi dinamici. Tradizionalmente, questi metodi richiedono modelli predefiniti e sono computazionalmente costosi. L'uso di modelli appresi (learning-based) ha risolto alcuni di questi limiti, ma introduce nuove sfide:

• Incertezza del modello: I modelli appresi possono essere errati o non corrispondere alla realtà (es. training incompleto).
• Garanzie probabilistiche: Per fornire garanzie di sicurezza robuste, è necessario "calibrare" i set raggiungibili utilizzando campioni di dati.
• Costo del campionamento: Ottenere garanzie probabilistiche forti richiede un numero elevato di campioni, che può essere proibitivo.
• Violazione delle assunzioni IID: I metodi di calibrazione esistenti spesso assumono che i campioni siano indipendenti e identicamente distribuiti (IID). Tuttavia, nei processi iterativi di apprendimento attivo, il set raggiungibile si aggiorna dopo ogni campione, rendendo i campioni non IID e invalidando le garanzie statistiche standard.

L'obiettivo del paper è sviluppare un metodo per calibrare i set raggiungibili utilizzando meno campioni possibile, mantenendo garanzie probabilistiche rigorose anche in un contesto di apprendimento attivo adattivo.

2. Metodologia: Approximate Pick-to-Learn

Gli autori propongono un nuovo framework che tratta la calibrazione come un problema di Apprendimento Attivo, combinando l'algoritmo Pick-to-Learn con la Predizione Conformale (Conformal Prediction).

A. Concetto Chiave: Pick-to-Learn Adattato

L'algoritmo originale Pick-to-Learn (di Paccagnan et al.) è un meta-algoritmo per l'apprendimento supervisionato che trasforma qualsiasi procedura di apprendimento in uno schema di compressione, fornendo limiti di generalizzazione.

• Adattamento: Poiché nell'apprendimento attivo non esiste un dataset etichettato completo, gli autori ridefiniscono il dataset come un insieme non etichettato di stati. Invece di conoscere l'errore reale $e_h(z)$ per tutti i punti, scelgono attivamente i punti che massimizzano una funzione di errore approssimata.

B. Il Ruolo della Predizione Conformale

Il problema principale è che massimizzare una funzione di errore approssimata non garantisce che si stia effettivamente riducendo l'errore reale del modello. Per risolvere ciò, gli autori utilizzano la Predizione Conformale:

1. Costruiscono un intervallo di confidenza attorno alla funzione di errore approssimata $a_{h,\eta}(x)$.
2. Calcolano un parametro di calibrazione $\lambda$ basato su un set di calibrazione separato ($C$) per garantire che, con alta probabilità, l'errore reale $e_h(z)$ sia contenuto nell'intervallo definito dalla stima approssimata.
3. Definizione di un ordine totale approssimato $\hat{e}_{h,\eta}(x)$ che sostituisce l'errore reale nella strategia di selezione dei campioni.

C. L'Algoritmo (Approximate Pick-to-Learn)

L'algoritmo iterativo funziona come segue:

1. Inizializzazione: Si parte con un set di campioni $Q$ vuoto e un'ipotesi iniziale $h_0$.
2. Selezione Attiva: Si seleziona il punto $x$ nel dominio che massimizza l'errore approssimato calibrato $\hat{e}_{h,\eta}(x)$.
3. Ottimizzazione: Si ottiene il valore reale del sistema in quel punto (eseguendo la simulazione) e si aggiunge al set di training $Q$.
4. Ri-apprendimento: Si aggiorna il modello $h$ usando $Q$.
5. Ricalibrazione: Si ricalcola $\lambda$ e $\hat{e}_{h,\eta}$ usando il nuovo modello e il set di calibrazione.
6. Terminazione: Il ciclo continua finché l'errore approssimato non scende sotto una soglia $\omega$ per tutti i punti nel dominio.

Il teorema principale dimostra che, con probabilità $1-\alpha$, la funzione di valore appresa avrà un errore basso su stati non visti, anche se i campioni sono stati selezionati in modo adattivo.

3. Contributi Chiave

1. Inquadramento come Apprendimento Attivo: La calibrazione dei set raggiungibili è formulata come un problema di apprendimento attivo, permettendo di selezionare solo i campioni necessari.
2. Estensione Teorica (Approximate Pick-to-Learn): Introduzione di una variante dell'algoritmo Pick-to-Learn adattata all'apprendimento attivo, con una dimostrazione teorica delle garanzie probabilistiche.
3. Integrazione Conformale: Uso della predizione conformale per garantire che la strategia di campionamento attivo (che massimizza un errore approssimato) sia correlata all'errore reale del modello.
4. Efficienza e Accuratezza: Dimostrazione che il metodo richiede meno campioni rispetto alle tecniche baselines per ottenere set raggiungibili più accurati e con limiti di generalizzazione più stretti.

4. Risultati Sperimentali

Gli esperimenti sono stati condotti su un caso di studio simulato di racing di droni (un drone "ego" che deve superare un altro drone e raggiungere un cancello).

• Setup: Sistema dinamico a 12 dimensioni. Il modello di valore iniziale è un processo Gaussiano (GP) basato su una politica appresa.
• Baseline: Confronto con due metodi esistenti: LB Iterative [5] e LB Robust [6], che utilizzano ottimizzazione su scenari e campionamento casuale o adattivo non garantito teoricamente nello stesso modo.
• Metriche: Numero di campioni, tasso di falsi positivi (FPR), tasso di falsi negativi (FNR) e la strettezza del limite probabilistico ($\bar{\epsilon}$).

Risultati principali:

• Efficienza dei campioni: Il metodo proposto richiede significativamente meno campioni per raggiungere la calibrazione rispetto alle baseline.
• Accuratezza: I set raggiungibili calibrati sono più precisi, con migliori compromessi tra FPR e FNR. Le baseline tendono a sacrificare un errore per ridurre l'altro, mentre il metodo proposto bilancia meglio le due metriche.
• Robustezza: Il metodo funziona bene anche in slice dello spazio degli stati meno frequenti o più difficili da apprendere (es. Slice 2), dove le baseline falliscono perché si basano troppo sulla geometria dei livelli della funzione appresa.
• Scalabilità: Il metodo scala a dimensioni superiori (3D e 4D), sebbene richieda un rilassamento dei parametri di confidenza ($\alpha$) per mantenere l'efficienza, accettando un leggero aumento degli errori.

5. Significato e Implicazioni

Questo lavoro è significativo perché colma il divario tra l'apprendimento automatico adattivo e le garanzie di sicurezza formale.

• Sicurezza Adattiva: Permette di aggiornare le garanzie di sicurezza in tempo reale man mano che il sistema apprende dall'ambiente, senza dover raccogliere un numero enorme di dati offline.
• Indipendenza dal Modello: Funziona con modelli "black-box" o arbitrari, senza assumere che i dati siano IID o che il modello appartenga a una specifica classe di ipotesi (come nei metodi Bayesiani tradizionali).
• Futuro: Apre la strada all'applicazione di questi principi su hardware reale e a una comprensione più profonda del trade-off tra complessità dimensionale, conservatorismo del set e difficoltà di apprendimento.

In sintesi, il paper propone un framework rigoroso che rende l'apprendimento attivo non solo efficiente, ma anche statisticamente garantito per applicazioni di sicurezza critica.