Riepilogo Tecnico: Estensione del Kernel Trick alle Funzioni di Influenza

Enunciato del Problema

Le funzioni di influenza, originariamente sviluppate nella statistica robusta e adattate all'apprendimento automatico da Koh e Liang [1], forniscono un metodo per stimare come i parametri e gli output di un modello cambiano quando i punti dei dati di addestramento vengono perturbati o rimossi. Questa capacità è fondamentale per l'oblio automatico (machine unlearning), l'interpretabilità e la privacy. Tuttavia, l'applicazione standard delle funzioni di influenza ai modelli di deep learning su larga scala incontra un significativo collo di bottiglia nella scalabilità.

La sfida computazionale centrale risiede nel Prodotto Inverso Hessiano-Vettore (IHVP), $H_{\theta^*}^{-1} \nabla_\theta L_{D_f}(\theta^*)$, richiesto per approssimare la variazione dei parametri ($\theta_r^*$) dopo la rimozione di un insieme di oblio $D_f$. Nella formulazione originale, la matrice Hessiana $H_{\theta^*}$ scala con il quadrato del numero di parametri del modello ($d_\theta$). Per modelli di grandi dimensioni (ad esempio, reti neurali profonde), la materializzazione e l'inversione di questa matrice sono impraticabili. Sebbene i metodi iterativi come i Gradienti Coniugati (CG) evitino la materializzazione dell'Hessiano, fanno comunque affidamento su Prodotti Hessiano-Vettore (HVP) che scalano con la dimensione del modello, rendendo il processo computazionalmente costoso quando $d_\theta$ è grande rispetto alla dimensione del dataset.

Metodologia

Gli autori propongono una rappresentazione duale delle funzioni di influenza che sposta la complessità computazionale dal scalare con la dimensione del modello ($d_\theta$) al scalare con la dimensione del dataset ($|D|$) e la dimensione dell'output ($d_{out}$). Questo approccio si fonda sulla teoria dei modelli linearizzabili e sul Kernel Tangente Neurale (NTK).

1. Linearizzazione e Riparametrizzazione

Il metodo assume che il modello $f(\cdot, \theta)$ sia "linearizzabile", il che significa che il suo comportamento durante l'addestramento può essere approssimato dalla sua linearizzazione attorno a un punto di riferimento $\theta'$ (tipicamente l'inizializzazione). Gli autori definiscono un modello linearizzato $f^{lin}$ e un corrispondente rischio empirico regolarizzato $\hat{L}_D(\theta)$.

Chiave per la derivazione è la Proposizione 3.1, che stabilisce che per qualsiasi sottoinsieme di dati, la differenza tra i parametri ottimali del modello linearizzato e l'intero dataset giace in uno specifico sottospazio lineare di $\mathbb{R}^{d_\theta}$:
$$\hat{\theta}_r^* - \hat{\theta}^* = \nabla_\theta f(X, \theta')^\top \Delta \alpha_r^*$$
dove $\Delta \alpha_r^* \in \mathbb{R}^{d_{out}|D|}$.

Questa osservazione permette agli autori di riparametrizzare il problema di ottimizzazione. Invece di ottimizzare sullo spazio dei parametri ad alta dimensionalità $\theta$, essi ottimizzano sulla variabile duale $\Delta \alpha$. Il problema vincolato in $\theta$ viene trasformato in un problema non vincolato nello spazio $\Delta \alpha$:
$$\tilde{L}_D(\Delta \alpha) := \frac{1}{|D|} \sum_{(x,y) \in D} \left( \ell(g^{lin}(x, \Delta \alpha), y) + \frac{\lambda}{2} \|\phi(\Delta \alpha) - \theta'\|_2^2 \right)$$
dove $g^{lin}$ coinvolge l'NTK empirico, $K(\cdot, \cdot) = \nabla_\theta f(\cdot, \theta') \nabla_\theta f(\cdot, \theta')^\top$.

2. Funzioni di Influenza Duali

Nello spazio $\Delta \alpha$, l'influenza della rimozione dei punti dati è approssimata risolvendo un sistema lineare che coinvolge l'Hessiano del rischio duale, $H_{\Delta \alpha^*}$. Crucialmente, questo Hessiano scala con $d_{out}|D| \times d_{out}|D|$ invece che con $d_\theta \times d_\theta$.

L'approssimazione per la variazione della variabile duale è:
$$\Delta \alpha_r^* \approx \frac{|D_f|}{|D|} H_{\Delta \alpha^*}^{-1} \nabla_{\Delta \alpha} \tilde{L}_{D_f}(0)$$
Gli autori dimostrano che questo sistema può essere risolto in modo efficiente. Nello specifico, se l'insieme di oblio $D_f$ è grande, la dimensione del sistema lineare da risolvere in realtà diminuisce perché i componenti noti di $\Delta \alpha_r^*$ corrispondenti a $D_f$ possono essere isolati.

3. Stima delle Variazioni

Una volta ottenuto $\Delta \alpha_r^*$, le variazioni negli output del modello e nella perdita per i punti di test possono essere stimate utilizzando l'NTK:

• Variazione dell'Output: $f^{lin}(x_t, \hat{\theta}_r^*) - f^{lin}(x_t, \hat{\theta}^*) \approx K(x_t, X) \Delta \alpha_r^*$
• Variazione della Perdita: Stimata tramite il gradiente della perdita duale rispetto a $\Delta \alpha$.

Questa formulazione permette il calcolo dell'influenza per modelli con un numero infinito di parametri, a condizione che l'NTK ammetta una forma analitica.

Contributi Chiave

1. Rappresentazione Duale: Il paper introduce una formulazione duale delle funzioni di influenza in cui la complessità computazionale dipende dalla dimensione del dataset ($|D|$) e dalla dimensione dell'output ($d_{out}$) piuttosto che dal numero di parametri del modello ($d_\theta$).
2. Efficienza per Modelli Grandi: Il metodo fornisce un'alternativa efficiente alle funzioni di influenza originali quando $d_\theta \gg d_{out}|D|$. Evita la necessità di calcolare HVP rispetto allo spazio dei parametri massiccio.
3. Applicabilità a Larghezza Infinita: Il framework estende l'analisi dell'influenza alle reti neurali a larghezza infinita sfruttando l'NTK analitico, permettendo la stima delle variazioni di parametri e output nel limite di parametri infiniti.
4. Scorciatoia Computazionale: Gli autori identificano che nello spazio duale, la dimensione del sistema lineare diminuisce all'aumentare della dimensione dell'insieme di oblio ($|D_f|$), offrendo un guadagno di efficienza controintuitivo per compiti di oblio su larga scala.

Risultati Sperimentali

Gli autori validano il loro metodo su versioni linearizzate di Reti Neurali Fully Connected (FCNN) e Reti Neurali Convoluzionali (CNN) addestrate su sottoinsiemi di MNIST e CIFAR-10.

• Tempo di Esecuzione: Il metodo nello spazio $\Delta \alpha$ supera costantemente il metodo originale nello spazio $\theta$ sia negli scenari "cold-start" (prima esecuzione) che "warm-start" (esecuzione ripetuta). Il divario di prestazioni si amplia all'aumentare della dimensione del modello rispetto al dataset.
• Accuratezza: Le prestazioni di oblio (misurate dalla distanza relativa $\ell_2$ tra i parametri dopo l'oblio e quelli riaddestrati, e dall'accuratezza sull'insieme di oblio) sono comparabili al metodo originale.
• Effetto della Regolarizzazione ($\lambda$): Esperimenti su modelli non lineari mostrano che valori più elevati della costante di regolarizzazione $\lambda$ fanno sì che le dinamiche di addestramento dei modelli non lineari assomiglino più da vicino alle loro linearizzazioni. Ciò migliora l'affidabilità della rappresentazione duale per modelli non lineari, sebbene a costo di una minore accuratezza di test.
• Reti a Larghezza Infinita: Il metodo stima con successo le variazioni di output e perdita per FCNN e CNN a larghezza infinita, con stime che corrispondono strettamente alle variazioni reali calcolate tramite Discesa del Gradiente Kernel.

Significato e Affermazioni

Il paper afferma che la rappresentazione duale offre una soluzione scalabile per l'oblio automatico e l'analisi dell'influenza in contesti in cui la dimensione del modello è proibitivamente grande per i metodi tradizionali nello spazio dei parametri.

• Scalabilità: Permette la stima dell'influenza per modelli in cui la valutazione delle funzioni di influenza originali nello spazio dei parametri è impraticabile.
• Estensione Teorica: Fornisce un ponte teorico per analizzare l'influenza nel limite di larghezza infinita delle reti neurali.
• Limitazioni: Gli autori dichiarano esplicitamente che il metodo è limitato a modelli linearizzabili. Sebbene una forte regolarizzazione ($\lambda$) possa approssimare modelli non lineari come linearizzabili, ciò degrada le prestazioni del modello. Inoltre, il metodo richiede la materializzazione o l'operatività implicita sulla matrice NTK, che scala con il prodotto della dimensione del dataset e della dimensione dell'output, potenzialmente diventando un collo di bottiglia per dataset molto grandi con molte classi.

Il lavoro non afferma di risolvere il problema dell'oblio per tutti i modelli di deep learning, ma piuttosto fornisce uno strumento specializzato ed efficiente per scenari in cui il dataset è piccolo rispetto alla capacità del modello o in cui il modello può essere efficacemente trattato come lineare.