Technische Zusammenfassung: Erweiterung des Kernel-Tricks auf Einflussfunktionen

Problemstellung

Einflussfunktionen, die ursprünglich in der robusten Statistik entwickelt und von Koh und Liang [1] auf das maschinelle Lernen übertragen wurden, bieten eine Methode, um abzuschätzen, wie sich Modellparameter und -ausgaben ändern, wenn Trainingsdatenpunkte gestört oder entfernt werden. Diese Fähigkeit ist entscheidend für maschinelles Vergessen, Interpretierbarkeit und Privatsphäre. Die Standardanwendung von Einflussfunktionen auf großskalige Deep-Learning-Modelle stößt jedoch auf ein erhebliches Skalierungsproblem.

Die zentrale rechnerische Herausforderung liegt im inversen Hesse-Matrix-Vektor-Produkt (IHVP), $H_{\theta^*}^{-1} \nabla_\theta L_{D_f}(\theta^*)$, das erforderlich ist, um die Änderung der Parameter ($\theta_r^*$) nach dem Entfernen einer Vergessensmenge $D_f$ zu approximieren. In der ursprünglichen Formulierung skaliert die Hesse-Matrix $H_{\theta^*}$ mit dem Quadrat der Anzahl der Modellparameter ($d_\theta$). Für große Modelle (z. B. tiefe neuronale Netze) ist die Materialisierung und Inversion dieser Matrix nicht durchführbar. Während iterative Methoden wie das konjugierte Gradientenverfahren (CG) die Materialisierung der Hesse-Matrix vermeiden, beruhen sie dennoch auf Hesse-Matrix-Vektor-Produkten (HVPs), die mit der Modellgröße skalieren, was den Prozess rechnerisch teuer macht, wenn $d_\theta$ im Verhältnis zur Datengröße groß ist.

Methodik

Die Autoren schlagen eine duale Darstellung von Einflussfunktionen vor, die die rechnerische Komplexität von einer Skalierung mit der Modellgröße ($d_\theta$) auf eine Skalierung mit der Datengröße ($|D|$) und der Ausgabedimension ($d_{out}$) verlagert. Dieser Ansatz basiert auf der Theorie linearisierbarer Modelle und des Neural Tangent Kernel (NTK).

1. Linearisierung und Reparametrisierung

Die Methode geht davon aus, dass das Modell $f(\cdot, \theta)$ „linearisierbar" ist, was bedeutet, dass sein Verhalten während des Trainings durch seine Linearisierung um einen Referenzpunkt $\theta'$ (typischerweise die Initialisierung) angenähert werden kann. Die Autoren definieren ein linearisiertes Modell $f^{lin}$ und einen entsprechenden regularisierten empirischen Risiko $\hat{L}_D(\theta)$.

Schlüssel für die Herleitung ist Proposition 3.1, die feststellt, dass für jede Teilmenge von Daten die Differenz zwischen den optimalen Parametern des linearisierten Modells und dem vollständigen Datensatz in einem spezifischen linearen Unterraum von $\mathbb{R}^{d_\theta}$ liegt:
$$\hat{\theta}_r^* - \hat{\theta}^* = \nabla_\theta f(X, \theta')^\top \Delta \alpha_r^*$$
wobei $\Delta \alpha_r^* \in \mathbb{R}^{d_{out}|D|}$.

Diese Beobachtung ermöglicht es den Autoren, das Optimierungsproblem zu reparametrisieren. Anstatt über den hochdimensionalen Parameterraum $\theta$ zu optimieren, optimieren sie über die duale Variable $\Delta \alpha$. Das in $\theta$ beschränkte Problem wird in ein unbeschränktes Problem im $\Delta \alpha$-Raum transformiert:
$$\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)$$
wobei $g^{lin}$ den empirischen NTK beinhaltet, $K(\cdot, \cdot) = \nabla_\theta f(\cdot, \theta') \nabla_\theta f(\cdot, \theta')^\top$.

2. Duale Einflussfunktionen

Im $\Delta \alpha$-Raum wird der Einfluss des Entfernens von Datenpunkten durch das Lösen eines linearen Systems approximiert, das die Hesse-Matrix des dualen Risikos, $H_{\Delta \alpha^*}$, beinhaltet. Entscheidend ist, dass diese Hesse-Matrix mit $d_{out}|D| \times d_{out}|D|$ skaliert und nicht mit $d_\theta \times d_\theta$.

Die Approximation für die Änderung der dualen Variable lautet:
$$\Delta \alpha_r^* \approx \frac{|D_f|}{|D|} H_{\Delta \alpha^*}^{-1} \nabla_{\Delta \alpha} \tilde{L}_{D_f}(0)$$
Die Autoren zeigen, dass dieses System effizient gelöst werden kann. Insbesondere wenn die Vergessensmenge $D_f$ groß ist, nimmt die Dimension des zu lösenden linearen Systems tatsächlich ab, da die bekannten Komponenten von $\Delta \alpha_r^*$, die $D_f$ entsprechen, isoliert werden können.

3. Schätzung von Änderungen

Sobald $\Delta \alpha_r^*$ ermittelt ist, können Änderungen der Modellausgaben und des Verlusts für Testpunkte unter Verwendung des NTK geschätzt werden:

• Änderung der Ausgabe: $f^{lin}(x_t, \hat{\theta}_r^*) - f^{lin}(x_t, \hat{\theta}^*) \approx K(x_t, X) \Delta \alpha_r^*$
• Änderung des Verlusts: Geschätzt über den Gradienten des dualen Verlusts bezüglich $\Delta \alpha$.

Diese Formulierung ermöglicht die Berechnung von Einfluss für Modelle mit unendlich vielen Parametern, sofern der NTK eine analytische Form zulässt.

Hauptbeiträge

1. Duale Darstellung: Die Arbeit führt eine duale Formulierung von Einflussfunktionen ein, bei der die rechnerische Komplexität von der Datengröße ($|D|$) und der Ausgabedimension ($d_{out}$) und nicht von der Anzahl der Modellparameter ($d_\theta$) abhängt.
2. Effizienz für große Modelle: Die Methode bietet eine effiziente Alternative zu den ursprünglichen Einflussfunktionen, wenn $d_\theta \gg d_{out}|D|$. Sie vermeidet die Notwendigkeit, HVPs bezüglich des massiven Parameterraums zu berechnen.
3. Anwendbarkeit bei unendlicher Breite: Das Framework erweitert die Einflussanalyse auf unendlich breite neuronale Netze, indem es den analytischen NTK nutzt, was die Schätzung von Parameter- und Ausgabeänderungen im Grenzfall unendlicher Parameter ermöglicht.
4. Rechnerischer Shortcut: Die Autoren identifizieren, dass im dualen Raum die Größe des linearen Systems mit zunehmender Größe der Vergessensmenge ($|D_f|$) abnimmt, was einen kontraintuitiven Effizienzgewinn für großskalige Vergessensaufgaben bietet.

Experimentelle Ergebnisse

Die Autoren validieren ihre Methode an linearisierten Versionen von Fully Connected Neural Networks (FCNN) und Convolutional Neural Networks (CNN), die auf Teilmengen von MNIST und CIFAR-10 trainiert wurden.

• Laufzeit: Die $\Delta \alpha$-Raum-Methode übertrifft die ursprüngliche $\theta$-Raum-Methode sowohl im „Cold-Start"-Fall (erste Ausführung) als auch im „Warm-Start"-Fall (wiederholte Ausführung) konsistent. Die Leistungslücke vergrößert sich, wenn die Modellgröße im Verhältnis zum Datensatz zunimmt.
• Genauigkeit: Die Leistung beim Vergessen (gemessen durch den relativen $\ell_2$-Abstand zwischen vergessenen und neu trainierten Parametern sowie die Genauigkeit auf der Vergessensmenge) ist mit der ursprünglichen Methode vergleichbar.
• Einfluss der Regularisierung ($\lambda$): Experimente an nichtlinearen Modellen zeigen, dass größere Werte der Regularisierungskonstante $\lambda$ die Trainingsdynamik nichtlinearer Modelle ihren Linearisierungen ähnlicher machen. Dies verbessert die Zuverlässigkeit der dualen Darstellung für nichtlineare Modelle, geht jedoch auf Kosten einer geringeren Testgenauigkeit.
• Unendlich breite Netze: Die Methode schätzt Ausgabe- und Verluständerungen für unendlich breite FCNNs und CNNs erfolgreich, wobei die Schätzungen den tatsächlich über Kernel Gradient Descent berechneten Änderungen sehr nahe kommen.

Bedeutung und Behauptungen

Die Arbeit behauptet, dass die duale Darstellung eine skalierbare Lösung für maschinelles Vergessen und Einflussanalyse in Szenarien bietet, in denen die Modellgröße für traditionelle Methoden im Parameterraum prohibitiv groß ist.

• Skalierbarkeit: Sie ermöglicht die Schätzung von Einfluss für Modelle, bei denen die Evaluierung der ursprünglichen Einflussfunktionen im Parameterraum nicht durchführbar ist.
• Theoretische Erweiterung: Sie bietet eine theoretische Brücke, um Einfluss im Grenzfall unendlicher Breite neuronaler Netze zu analysieren.
• Einschränkungen: Die Autoren stellen ausdrücklich fest, dass die Methode auf linearisierbare Modelle beschränkt ist. Zwar können große Regularisierungswerte ($\lambda$) nichtlineare Modelle als linearisierbar approximieren, dies verschlechtert jedoch die Modellleistung. Darüber hinaus erfordert die Methode die Materialisierung oder implizite Operation mit der NTK-Matrix, die mit dem Produkt aus Datengröße und Ausgabedimension skaliert und potenziell zu einem Flaschenhals für sehr große Datensätze mit vielen Klassen werden kann.

Die Arbeit behauptet nicht, das Vergessensproblem für alle Deep-Learning-Modelle zu lösen, sondern bietet vielmehr ein spezialisiertes, effizientes Werkzeug für Szenarien, in denen der Datensatz klein im Verhältnis zur Modellkapazität ist oder das Modell effektiv als linear behandelt werden kann.