Technisches Resümee: Subsampling für überwachtes Lernen in Reproduzierenden Kernel-Hilbert-Räumen

Problemstellung

Im Zeitalter von Big Data sind die Rechenkosten und der Energieverbrauch beim Training statistischer Lernmodelle auf massiven Datensätzen zu kritischen Engpässen geworden. Zwar existieren verschiedene Techniken zur Datenreduktion (z. B. Sketching, Coresets, stochastische Optimierung), doch viele davon sind entweder aufgabenspezifisch unabhängig oder beruhen auf intratablen Wahrscheinlichkeiten für eine optimale Auswahl. Insbesondere im nichtparametrischen überwachten Lernen, bei dem Hypothesen in einem Reproduzierenden Kernel-Hilbert-Raum (RKHS) liegen, versagen bestehende Methoden oft dabei, ein datenabhängiges Subsampling-Schema bereitzustellen, das die asymptotische Varianz des Schätzers minimiert. Kernel-Methoden skalieren typischerweise schlecht ($O(n^2)$ oder $O(nm)$) mit der ursprünglichen Datensatzgröße $n$, während Standard-Uniform-Subsampling dies zwar auf $O(s^2)$ reduziert (wobei $s \ll n$), aber das Uniform-Subsampling den Informationswert einzelner Datenpunkte ignoriert, was zu einer suboptimalen Schätzpräzision führt.

Methodik

Die Autoren schlagen ein Framework für Subsampled Risk Minimization (SRM) in RKHSs vor, das ein Horvitz-Thompson-Reweighting-Schema nutzt, um eine erwartungstreue Schätzung des empirischen Risikos zu gewährleisten. Die Kernmethodik umfasst:

1. Theoretischer Rahmen:

   • Setting: Nichtparametrisches überwachtes Lernen (Klassifikation und Regression) mit einer konvexen, zweimal differenzierbaren Verlustfunktion $\ell$ und einem Ridge-Penalty. Der Schätzer minimiert ein regularisiertes empirisches Risiko.
   • Subsampling-Strategien: Das Paper analysiert zwei Strategien:
     • Multinomial Subsampling (mit Zurücklegen): Punkte werden unabhängig mit Einschlusswahrscheinlichkeiten $\pi_{n,i}$ gezogen.
     • Poisson Subsampling (ohne Zurücklegen): Punkte werden unabhängig mit Wahrscheinlichkeit $s_n \pi_{n,i}$ einbezogen.
   • Asymptotische Analyse: Unter Verwendung von Werkzeugen aus funktionalen Wahrscheinlichkeitsräumen und der Martingaltheorie etablieren die Autoren die asymptotische Normalität des SRM-Schätzers. Sie leiten den asymptotischen Kovarianzoperator $\Sigma^*$ her, der von den Einschlusswahrscheinlichkeiten $\pi_{n,i}$ abhängt.

2. Optimales Subsampling-Schema:

   • Die Autoren definieren L-Optimalität als die Minimierung der Spur des asymptotischen Kovarianzoperators (vorkonditioniert durch die inverse Hesse-Matrix des wahren Risikos).
   • Sie leiten einen geschlossenen Ausdruck für die L-optimale absolute Interessensfunktion $\psi^*$ her, welche die optimalen Einschlusswahrscheinlichkeiten diktiert:
     $$\psi^*(z) = |\ell'(h_0(x), y)| \sqrt{k(x, x)}$$
     Dies impliziert, dass Datenpunkte mit hoher Vorhersagefehlerrate (großes $|\ell'|$) oder hoher Kernel-Selbstähnlichkeit mit höherer Wahrscheinlichkeit gesampelt werden sollten.
   • Dies bedeutet, dass Datenpunkte mit hohem Vorhersagefehler (großes $|\ell'|$) oder hoher Kernel-Selbstähnlichkeit mit höherer Wahrscheinlichkeit gesampelt werden sollten.

3. Praktische Implementierung (Pilotierter Schätzer):

   • Da $h_0$ unbekannt ist, schlagen die Autoren einen Plug-in-Ansatz vor:
     1. Berechnung eines Pilot-Schätzers $\hat{h}_{k_n}$ auf einer kleinen Teilmenge der Daten ($k_n \ll s_n$).
     2. Schätzung der optimalen Wahrscheinlichkeiten unter Verwendung von $\hat{h}_{k_n}$.
     3. Glättung der geschätzten Wahrscheinlichkeiten, um sicherzustellen, dass sie technische Annahmen erfüllen (speziell, dass sie nicht zu schnell gegen Null konvergieren), unter Verwendung eines Hyperparameters $\alpha \in (0, 1]$:
        $$\tilde{\pi}_{n,i}^\alpha = (1-\alpha)\tilde{\pi}_{n,i} + \frac{\alpha}{n}$$
     4. Für Poisson Subsampling wird eine Post-hoc-Trunkierung angewendet, um sicherzustellen, dass die Wahrscheinlichkeiten gültig bleiben ($\leq 1/s_n$).
   • Für diesen $\alpha$-pilotierten Schätzer werden theoretische Garantien (Konsistenz und asymptotische Normalität) bereitgestellt.

Zentrale Beiträge

• Asymptotische Normalität in RKHS: Das Paper etabliert die asymptotische Normalität von Subsampling-Schätzern in unendlichdimensionalen RKHSs und unterscheidet sich dadurch von parametrischen Ergebnissen durch den Einsatz von Techniken des funktionalen zufälligen Wahrscheinlichkeitsraums und der Martingaltheorie.
• Ableitung des optimalen Schemas: Es liefert die erste Ableitung eines optimalen Subsampling-Schemas speziell für nichtparametrische Kernel-Methoden und zeigt, dass die optimale Einschlusswahrscheinlichkeit proportional zum Betrag des Verlustgradienten gewichtet durch die Kernel-Diagonale ist.
• Vergleich der Strategien: Die Autoren analysieren die Trade-offs zwischen Multinomial und Poisson Subsampling und zeigen auf, dass die optimale Wahl vom Grenzwertverhältnis $c = \lim s_n/n$ abhängt. Bemerkenswerterweise führen die beiden Strategien aufgrund der Ridge-Regularisierung nicht zu identischen asymptotischen Effizienzen, wenn $c=0$, was von Befunden in parametrischen Settings abweicht.
• Robuster praktischer Algorithmus: Der Vorschlag eines zweistufigen „pilotierten“ Algorithmus, der einen Pilot-Schätzer mit Glättung und Trunkierung kombiniert, macht das theoretisch optimale Schema praktisch implementierbar, während gleichzeitig statistische Garantien erhalten bleiben.

Ergebnisse

Numerische Experimente wurden auf synthetischen Datensätzen (Klassifikation und Regression) sowie einem realen Datensatz (UCI Covertype) durchgeführt, wobei der vorgeschlagene $\alpha$-pilotierte SRM gegen Folgendes getestet wurde:

• Uniform Subsampling (Baseline).
• Nyström-Methode.
• Random Fourier Features (RFF).
• Kernel-Sketching.

Ergebnisse:

• Glättungsparameter: Ein Glättungsparameter $\alpha$ zwischen 0,1 und 0,4 liefert den besten Generalisierungsfehler, indem er den Nutzen des optimalen Subsamplings mit der Stabilität des Uniform-Samplings ausbalanciert.
• Große Datenregime: Bei großen Datensätzen übertrifft das vorgeschlagene SRM das Uniform Subsampling signifikant im Hinblick auf den Trade-off zwischen Generalisierungsfehler und Rechenzeit (CPU).
• Vergleich mit Approximationen: Auf dem realen Covertype-Datensatz war die SRM-Methode effizienter als Nyström, RFF und Sketching. Auf synthetischen niedrigdimensionalen Aufgaben waren Kernel-Approximationen (Nyström, RFF) schneller, was darauf hindeutet, dass Subsampling und Kernel-Approximation komplementäre Techniken sind.
• Hybrider Ansatz: Die Kombination von Subsampling mit der Nyström-Methode verbesserte die Leistung weiter, was die Kompatibilität der Methode mit bestehenden Kernel-Approximationstechniken unterstreicht.

Bedeutung und Ansprüche

Das Paper beansprucht, eine theoretisch fundierte und praktisch lebensfähige Methode zur Reduzierung der Rechenlast des Kernel-basierten Lernens bereitzustellen, ohne die statistische Effizienz zu opfern. Durch die Ableitung eines optimalen Subsampling-Schemas basierend auf der Spur der asymptotischen Kovarianz bieten die Autoren einen Weg, „informative“ Individuen aus großen Datensätzen zu extrahieren.

Die Autoren rahmen ihre Arbeit bescheiden als Schritt hin zu einem energieeffizienteren Lernen ein, indem sie anmerken, dass die Methode zwar das Optimierungsproblem von $O(n^2)$ auf $O(s^2)$ reduziert, aber auf einem Pilot-Schätzer basiert. Sie räumen ein, dass die Theorie derzeit auf regularisierten Risiken basiert und dass die Erweiterung auf nicht-regularisierte Settings oder die Entwicklung von mehrstufigen Online-Verfahren potenzielle Richtungen für zukünftige Forschung darstellen. Die Arbeit unterscheidet sich dadurch, dass sie die spezifischen Herausforderungen des nichtparametrischen RKHS-Settings adressiert, welche bestehende parametrische Subsampling-Theorien nicht vollständig abdecken.