Technische Samenvatting: Uitbreiding van de Kernel-truc naar Invloedsfuncties

Probleemstelling

Invloedsfuncties, oorspronkelijk ontwikkeld in robuuste statistiek en aangepast voor machine learning door Koh en Liang [1], bieden een methode om te schatten hoe modelparameters en -output veranderen wanneer trainingsdatapunten worden verstoord of verwijderd. Deze mogelijkheid is cruciaal voor machine unlearning, interpretbaarheid en privacy. De standaardtoepassing van invloedsfuncties op diepe leermodellen in grote schaal stuit echter op een aanzienlijke schaalbaarheidslimiet.

De kern van het computatiewerkelijke probleem ligt in het Inverse Hessian-Vector Product (IHVP), $H_{\theta^*}^{-1} \nabla_\theta L_{D_f}(\theta^*)$, dat nodig is om de verandering in parameters ($\theta_r^*$) na het verwijderen van een vergeetset $D_f$ te benaderen. In de oorspronkelijke formulering schaalt de Hessiaan-matrix $H_{\theta^*}$ met het kwadraat van het aantal modelparameters ($d_\theta$). Voor grote modellen (zoals diepe neurale netwerken) is het materialiseren en inverteren van deze matrix onuitvoerbaar. Hoewel iteratieve methoden zoals Geconjugeerde Gradienten (CG) het materialiseren van de Hessiaan vermijden, vertrouwen ze nog steeds op Hessiaan-Vector Producten (HVP's) die schalen met de modelgrootte, waardoor het proces computatiewerkelijk duur wordt wanneer $d_\theta$ groot is ten opzichte van de datasetgrootte.

Methodologie

De auteurs stellen een duale representatie van invloedsfuncties voor die de computatiewerkelijke complexiteit verschuift van schalen met de modelgrootte ($d_\theta$) naar schalen met de datasetgrootte ($|D|$) en de outputdimensie ($d_{out}$). Deze aanpak is gebaseerd op de theorie van lineariseerbare modellen en de Neural Tangent Kernel (NTK).

1. Linearisatie en Herparameterisatie

De methode neemt aan dat het model $f(\cdot, \theta)$ "lineariseerbaar" is, wat betekent dat zijn gedrag tijdens training kan worden benaderd door zijn linearisatie rond een referentiepunt $\theta'$ (doorgaans initialisatie). De auteurs definiëren een gelineariseerd model $f^{lin}$ en een overeenkomstige geregulariseerde empirische risicofunctie $\hat{L}_D(\theta)

.

Centraal in de afleiding staat Propositie 3.1, die vaststelt dat voor elke subset van data het verschil tussen de optimale parameters van het gelineariseerde model en de volledige dataset ligt in een specifieke lineaire deelruimte van $\mathbb{R}^{d_\theta}$:
$$\hat{\theta}_r^* - \hat{\theta}^* = \nabla_\theta f(X, \theta')^\top \Delta \alpha_r^*$$
waarbij $\Delta \alpha_r^* \in \mathbb{R}^{d_{out}|D|}$.

Deze observatie stelt de auteurs in staat om het optimalisatieprobleem te herparameteriseren. In plaats van te optimaliseren over de hoogdimensionale parameterruimte $\theta$, optimaliseren ze over de duale variabele $\Delta \alpha$. Het beperkte probleem in $\theta$ wordt omgezet in een onbeperkt probleem in de $\Delta \alpha$-ruimte:
$$\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)$$
waarbij $g^{lin}$ de empirische NTK omvat, $K(\cdot, \cdot) = \nabla_\theta f(\cdot, \theta') \nabla_\theta f(\cdot, \theta')^\top$.

2. Duale Invloedsfuncties

In de $\Delta \alpha$-ruimte wordt de invloed van het verwijderen van datapunten benaderd door een lineair systeem op te lossen dat de Hessiaan van het duale risico bevat, $H_{\Delta \alpha^*}$. Cruciaal is dat deze Hessiaan schaalt met $d_{out}|D| \times d_{out}|D|$ in plaats van $d_\theta \times d_\theta$.

De benadering voor de verandering in de duale variabele is:
$$\Delta \alpha_r^* \approx \frac{|D_f|}{|D|} H_{\Delta \alpha^*}^{-1} \nabla_{\Delta \alpha} \tilde{L}_{D_f}(0)$$
De auteurs tonen aan dat dit systeem efficiënt kan worden opgelost. Specifiek, als de vergeetset $D_f$ groot is, neemt de dimensie van het op te lossen lineaire systeem daadwerkelijk af, omdat de bekende componenten van $\Delta \alpha_r^*$ die overeenkomen met $D_f$ geïsoleerd kunnen worden.

3. Schatten van Veranderingen

Zodra $\Delta \alpha_r^*$ is verkregen, kunnen veranderingen in modeloutput en verlies voor testpunten worden geschat met behulp van de NTK:

• Outputverandering: $f^{lin}(x_t, \hat{\theta}_r^*) - f^{lin}(x_t, \hat{\theta}^*) \approx K(x_t, X) \Delta \alpha_r^*$
• Verliesverandering: Geschat via de gradiënt van het duale verlies met betrekking tot $\Delta \alpha$.

Deze formulering maakt de berekening van invloed mogelijk voor modellen met oneindig veel parameters, mits de NTK een analytische vorm toestaat.

Belangrijkste Bijdragen

1. Duale Representatie: Het artikel introduceert een duale formulering van invloedsfuncties waarbij de computatiewerkelijke complexiteit afhankelijk is van de datasetgrootte ($|D|$) en de outputdimensie ($d_{out}$) in plaats van het aantal modelparameters ($d_\theta$).
2. Efficiëntie voor Grote Modellen: De methode biedt een efficiënt alternatief voor oorspronkelijke invloedsfuncties wanneer $d_\theta \gg d_{out}|D|$. Het vermijdt de noodzaak om HVP's te berekenen met betrekking tot de enorme parameterruimte.
3. Toepasbaarheid voor Oneindige Breedte: Het kader breidt invloedanalyse uit tot oneindig brede neurale netwerken door gebruik te maken van de analytische NTK, waardoor schattingen mogelijk zijn van parameter- en outputveranderingen in de limiet van oneindige parameters.
4. Computatiewerkelijke Kortweg: De auteurs identificeren dat in de duale ruimte de grootte van het lineaire systeem afneemt naarmate de grootte van de vergeetset ($|D_f|$) toeneemt, wat een tegenintuïtieve winst in efficiëntie biedt voor unlearning-taken in grote schaal.

Experimentele Resultaten

De auteurs valideren hun methode op gelineariseerde versies van Fully Connected Neural Networks (FCNN) en Convolutional Neural Networks (CNN) getraind op MNIST- en CIFAR-10-subsets.

• Uitvoeringstijd: De methode in de $\Delta \alpha$-ruimte presteert consequent beter dan de oorspronkelijke methode in de $\theta$-ruimte, zowel in "cold-start"-scenario's (eerste uitvoering) als "warm-start"-scenario's (herhaalde uitvoering). Het prestatieverschil wordt groter naarmate de modelgrootte toeneemt ten opzichte van de dataset.
• Nauwkeurigheid: De unlearning-prestaties (gemeten door de relatieve $\ell_2$-afstand tussen onthouden en opnieuw getrainde parameters, en nauwkeurigheid op de vergeetset) zijn vergelijkbaar met de oorspronkelijke methode.
• Effect van Regularisatie ($\lambda$): Experimenten met niet-lineaire modellen tonen aan dat grotere waarden van de regularisatieconstante $\lambda$ de trainingsdynamiek van niet-lineaire modellen dichter bij hun linearisaties brengen. Dit verbetert de betrouwbaarheid van de duale representatie voor niet-lineaire modellen, maar gaat ten koste van een lagere testnauwkeurigheid.
• Oneindig Brede Netwerken: De methode schat succesvol output- en verliesveranderingen voor oneindig brede FCNN's en CNN's, waarbij de schattingen nauw overeenkomen met werkelijke veranderingen berekend via Kernel Gradient Descent.

Betekenis en Beweringen

Het artikel beweert dat de duale representatie een schaalbare oplossing biedt voor machine unlearning en invloedanalyse in situaties waar de modelgrootte te groot is voor traditionele methoden in de parameterruimte.

• Schaalbaarheid: Het maakt de schatting van invloed mogelijk voor modellen waarbij het evalueren van de oorspronkelijke invloedsfuncties in de parameterruimte onuitvoerbaar is.
• Theoretische Uitbreiding: Het biedt een theoretische brug om invloed te analyseren in de limiet van oneindige breedte van neurale netwerken.
• Beperkingen: De auteurs stellen expliciet dat de methode beperkt is tot lineariseerbare modellen. Hoewel grote regularisatie ($\lambda$) niet-lineaire modellen kan benaderen als lineariseerbaar, verslechtert dit de modelprestaties. Bovendien vereist de methode het materialiseren of impliciet opereren op de NTK-matrix, wat schaalt met het product van datasetgrootte en outputdimensie, wat potentieel een bottleneck kan worden voor zeer grote datasets met veel klassen.

Het werk claimt niet het unlearning-probleem op te lossen voor alle deep learning-modellen, maar biedt eerder een gespecialiseerd, efficiënt hulpmiddel voor scenario's waar de dataset klein is ten opzichte van de modelcapaciteit, of waar het model effectief als lineair kan worden behandeld.