🤖 machine learning

Active Learning with Low-Rank Structure for Data Selection

Dieses Paper führt ein neues Datenselektionsverfahren ein, das eine Niedrigrang-Approximation und residuenbasierte Stichprobenziehung nutzt, um effizient eine gewichtete Teilmenge von Datenpunkten auszuwählen, wobei es theoretische Garantien und empirische Verbesserungen gegenüber traditionellen Clustering-basierten Methoden für Datensätze mit globaler algebraischer Struktur bietet.

Ursprüngliche Autoren: Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni, Mahdi Nikdan, David P. Woodruff, Samson Zhou

Veröffentlicht 2026-06-16

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni, Mahdi Nikdan, David P. Woodruff, Samson Zhou

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind ein Chefkoch, der versucht, die beste Suppe der Welt zu kreieren. Sie haben ein riesiges Lagerhaus voller tausender verschiedener Gemüse, Gewürze und Brühen (Ihr Datensatz). Um die perfekte Suppe herzustellen, müssen Sie all diese Dinge probieren und mischen. Aber hier ist das Problem: Ihre Küche ist winzig, Ihr Herd ist schwach und Sie haben nur wenige Stunden Zeit. Es ist unmöglich, mit dem gesamten Lagerhaus zu kochen.

Sie müssen eine kleine, perfekte Handvoll Zutaten auswählen, die genau denselben Geschmack wie das gesamte Lagerhaus liefern. Das ist das Data Selection-Problem (Datenauswahl-Problem).

Der alte Weg: Auswahl nach „Distanz“

Lange Zeit nutzten die besten Köche eine Methode namens Clustering. Stellen Sie sich vor, Sie betreten das Lagerhaus und nehmen aus jeder deutlich unterscheidbaren Ecke ein Gemüse mit. Sie nehmen eine Karotte aus dem Norden, eine Kartoffel aus dem Süden, eine Paprika aus dem Osten und eine Tomate aus dem Westen.

Die Logik dahinter war: „Wenn ich Dinge wähle, die weit voneinander entfernt liegen, decke ich damit alle Bereiche ab.“ Das funktionierte ganz gut für einfache Rezepte. Aber in der modernen Welt, in der Daten riesig und komplex sind (wie ein Lagerhaus mit Millionen von Artikeln), hat diese Methode einen Fehler. Sie konzentriert sich darauf, wo die Artikel sind, nicht darauf, was sie eigentlich bewirken. Sie könnten am Ende mit einer Tasche voller unterschiedlich aussehender Gemüse dastehen, die aber alle exakt gleich schmecken, während Sie das eine geheime Gewürz übersehen haben, das die Suppe eigentlich definiert.

Der neue Weg: Auswahl nach „Struktur“

Die Autoren dieser Arbeit sagen: „Hören Sie auf zu schauen, wo die Gemüse stehen. Schauen Sie auf die Form des Geschmacks.“

Sie schlagen eine neue Methode vor, die auf der Low-Rank-Struktur basiert.
Betrachten Sie Ihre Suppenzutaten nicht als einzelne Artikel, sondern als eine komplexe 3D-Skulptur. Selbst wenn die Skulptur kompliziert aussieht, könnte sie tatsächlich aus nur wenigen Hauptbalken und Stützen bestehen. Der Rest ist nur Dekoration.

Die Hauptbalken (Low-Rank): Dies sind die wichtigsten Richtungen des Geschmacks. Wenn Sie diese richtig hinbekommen, bekommen Sie auch die Suppe richtig hin.
Die Dekoration (Residuen): Dies sind die winzigen, unwichtigen Details, die den Geschmack nicht viel verändern.

Die Methode der Autoren nutzt eine mathematische „Röntgenaufnahme“ (genannt Low-Rank-Approximation), um diese Hauptbalken zu finden. Anstatt Gemüse zu wählen, die weit voneinander entfernt sind, wählen sie die spezifischen Zutaten aus, die die Hauptbalken der Geschmacksstruktur stützen.

Wie sie es machen: Die „Sensitivitäts“-Skala

Um herauszufinden, welche Zutaten die „Hauptbalken“ sind, verwenden sie eine Technik namens Sensitivity Sampling (Sensitivitäts-Sampling).

Stellen Sie sich vor, Sie haben eine riesige Waage. Sie legen ein Gemüse darauf, und die Waage sagt Ihnen: „Wenn du dieses hier weglässt, wie sehr wird sich der Geschmack der Suppe verändern?“

Wenn sich der Geschmack stark verändert, schlägt die Waage voll aus. Dieses Gemüse ist hochsensibel (sehr wichtig).
Wenn sich der Geschmack kaum verändert, bleibt die Waage niedrig. Dieses Gemüse ist wenig sensitiv (redundant).

Ihr Algorithmus berechnet diesen Wert für jeden einzelnen Artikel im Lagerhaus und wählt dann eine kleine Gruppe von Zutaten aus, allerdings gewichtet nach ihrer Wichtigkeit. Sie werden viel eher die „hochsensiblen“ Artikel auswählen.

Die Ergebnisse: Warum es wichtig ist

Das Papier hat diese Idee auf zwei Arten getestet:

Der Kreditkarten-Test: Sie versuchten, vorherzusagen, wer eine Kreditkartenzahlung versäumen würde, indem sie einen Standard-Finanzdatensatz verwendeten. Ihre „Low-Rank“-Methode wählte eine kleine Gruppe von Kunden aus, die das Ergebnis viel besser vorhersagten als die alte „Clustering“-Methode oder das bloße Zufallsverfahren.
Der Riesenhirn-Test (LLMs): Sie versuchten, eine massive KI (Llama3-8B) beizubringen, Matheaufgaben zu lösen und Fragen zu beantworten. Das Training der KI mit dem gesamten Datensatz dauert ewig und kostet ein Vermögen. Indem sie ihre Methode nutzten, um nur 6 % bis 25 % der Daten auszuwählen, trainierten sie die KI so, dass sie schlauer wurde, als wenn sie zufällige Daten oder die alte Clustering-Methode verwendet hätten.

Das große Fazit

Das Papier behauptet, dass für moderne, massive Datensätze die „Form“ der Daten (ihre algebraische Struktur) wichtiger ist als die „Distanz“ zwischen den Datenpunkten.

Indem man sich auf die zentralen strukturellen Balken der Daten konzentriert, anstatt nur zu versuchen, alle Ecken abzudecken, kann man 90 % seiner Daten wegwerfen und dennoch ein maschinelles Lernmodell trainieren, das genauso gut oder sogar besser performt, als wenn man alles verwendet hätte. Es ist, als würde man erkennen, dass man nicht jedes Salzkorn im Ozean probieren muss, um zu wissen, wie salzig die Suppe ist; man muss nur den Löffel probieren, der den wahren Charakter des Ozeans repräsentiert.

Technisches Resümee: Aktives Lernen mit Low-Rank-Struktur für die Datenselektion

Problemdefinition

Die Arbeit befasst sich mit dem Datenselektionsproblem im maschinellen Lernen, insbesondere der Herausforderung, eine kleine, repräsentative Teilmenge von Daten (einen Coreset) zu identifizieren, die ein effizientes Training von Modellen ermöglicht, ohne die Performance signifikant zu beeinträchtigen. Während moderne Datensätze und Foundation Models den Erfolg vorangetrieben haben, verursachen sie enorme Rechenkosten für das Training und Fine-Tuning.

Bestehende Ansätze, wie jene von Sener und Savarese [SS18] sowie Axiotis et al. [ACH+24], verlassen sich auf clustering-basierte Heuristiken (z. B. $k$ -Center oder $k$ -Means), die auf Einbettungen der Daten angewendet werden. Diese Methoden setzen voraus, dass Daten eine intrinsische geometrische Struktur besitzen, bei der Diversität und der Abstand zwischen Punkten die primären Treiber der Informativität sind. Die Autoren argumentieren jedoch, dass viele moderne Datensätze, insbesondere in hochdimensionalen Räumen, eine globale algebraische Struktur aufweisen, die besser durch Low-Rank-Approximationen (z. B. die Hauptkomponentenanalyse) als durch lokales geometrisches Clustering erfasst wird. Clustering-Methoden können daran scheitern, dominante Varianzrichtungen zu erfassen, wodurch kritische Komponenten für das Modelltraining potenziell übersehen werden.

Methodik

Die Arbeit schlägt ein neues Framework für die Datenselektion vor, das auf Low-Rank-Approximation und residuenbasierter Sensitivitäts-Sampling basiert. Der Kerngedanke besteht darin, die Bewahrung dominanter spektraler Richtungen der Daten zu priorisieren, anstatt lediglich die geometrische Diversität zu maximieren.

Theoretischer Rahmen

Der Ansatz ist im Row Subset Selection-Problem und der verlusterhaltenden Coreset-Konstruktion verwurzelt. Die Autoren führen Annahme 2.1 ein, die postuliert, dass für einen Datensatz $D$ mit einer Einbettungsmatrix die Verlustfunktion $\ell$ relativ zu einem $k$ -dimensionalen Unterraum $V$ (aufgespannt durch die obersten Singulärvektoren oder Hauptkomponenten) zerlegt werden kann:

Orthogonale Strafe: Die Verlustabweichung für einen Punkt $y$ außerhalb des Unterraums $V$ wird quadratisch durch die Norm seiner residuellen Komponente $r(y)$ begrenzt, die orthogonal zu $V$ steht, skaliert durch eine Konstante $\lambda$ .
Unterraum-Approximation: Innerhalb des Unterraums $V$ wird der Verlust gut durch eine gewichtete Summe der Verluste entlang der Basisrichtungen approximiert, skaliert durch eine Konstante $\gamma$ .

Diese Annahme formalisiert die Intuition, dass Richtungen orthogonal zum dominanten Low-Rank-Unterraum weniger zum Verlust beitragen oder weniger informativ sind – eine Eigenschaft, die bei Aufgaben wie PCA, Matrix Completion und Low-Rank Adaptation (LoRA) beobachtet wird.

Algorithmus: Sensitivitäts-Sampling

Der vorgeschlagene Algorithmus (Algorithmus 2) konstruiert einen gewichteten Coreset $S$ durch die folgenden Schritte:

Low-Rank Sketch: Berechne eine Rank- $k$ -Approximation des Datensatzes (z. B. via SVD), um den Unterraum $V$ und seine Basis $\{v_1, \dots, v_k\}$ zu definieren.
Dekomposition: Zerlege jeden Datenpunkt $x$ in seine Projektion $v(x)$ auf $V$ und sein Residuum $r(x)$ , das orthogonal zu $V$ steht.
Berechnung des Sensitivitäts-Scores: Berechne für jeden Punkt einen Sensitivitäts-Score $\sigma(x)$ $σ (x)$ , der Folgendes kombiniert:
- Den gewichteten Verlust entlang der Basisrichtungen: $(\gamma + 1)\sum \alpha_i^2 \ell(v_i)$ .
- Eine Strafe für das Residuum: $\lambda \|r(x)\|_2^2$ .
- Einen konstanten Term bezüglich des maximalen Verlusts in der Basis.
Sampling: Ziehe Stichproben aus dem Datensatz mit Ersetzung, proportional zu ihren normalisierten Sensitivitäts-Scores $p(x) = \sigma(x) / \sum \sigma(y)$ .
Gewichtung: Weise den gezogenen Punkten Gewichte $w(x) = 1/(s \cdot p(x))$ zu, um sicherzustellen, dass der Schätzer erwartungstreu (unbiased) ist.

Zentrale Beiträge

Theoretische Garantien (Theorem 2.2 & 2.3): Die Arbeit beweist, dass eine gewichtete Teilmenge der Größe $\tilde{O}(k + 1/\varepsilon^2)$ den durchschnittlichen Verlust des vollständigen Datensatzes innerhalb eines relativen Fehlers von $(1 \pm \varepsilon)$ approximieren kann, bis auf einen additiven Term, der proportional zur optimalen Rank- $k$ -Approximationskosten $\Phi_k(D)$ ist.
- Theorem 2.2 garantiert dies für eine allgemeine gewichtete Teilmenge.
- Theorem 2.3 erweitert dies auf die Row Subset Selection und stellt sicher, dass die ausgewählte Teilmenge aus tatsächlichen Datenpunkten des Eingangsdatensatzes besteht.
- Die Fehlerschranke hängt explizit von $\Phi_k(D)$ ab, was bedeutet, dass Datensätze mit starker Low-Rank-Struktur engere Schranken und präzisere Coresets liefern.
Algorithmische Innovation: Die Autoren führen einen Sensitivitäts-Sampling-Algorithmus ein, der die Low-Rank-Struktur nutzt, um Wichtigkeits-Scores zu berechnen, und sich damit von den geometrischen Distanzmetriken unterscheidet, die in Clustering-basierten Methoden verwendet werden.
Empirische Validierung: Das Framework wird sowohl auf tabellarischen Daten (Credit Card Default Datensatz) als auch beim Fine-Tuning von Large Language Models (Llama3-8B und Qwen2.5-3B auf GSM8k, ViGGO und SQL-Aufgaben) validiert.

Experimentelle Ergebnisse

Die Arbeit evaluiert das vorgeschlagene Low-Rank Sensitivity Sampling (Low-rank SS) gegen mehrere Baselines: Uniform Sampling, $k$ -Center, Clustering-basiertes Sensitivitäts-Sampling und Graph Cut.

Tabellarische Daten (Credit Card Dataset):
- Low-rank SS erreichte den niedrigsten Approximationsfehler in der Summe der Quadrate, wobei der Fehler im Vergleich zu Random Sampling um eine Größenordnung und im Vergleich zu Clustering bei kleinen Stichprobengrößen ( $s=1000$ ) um ca. 50 % reduziert wurde.
- In der nachgeschalteten logistischen Regression erreichte Low-rank SS bei $s=5000$ eine Testgenauigkeit von bis zu 74 %, womit es Clustering (70 %) und Random Sampling (67 %) übertraf.
LLM Fine-Tuning (Llama3-8B & Qwen2.5-3B):
- Bei den Aufgaben GSM8k, ViGGO und SQL übertraf Low-rank SS konsistent das Uniform Sampling und die Clustering-basierten Methoden.
- Beispielsweise erreichte Low-rank SS bei ViGGO mit Llama3-8B bei 25 % Datenkompression eine Genauigkeit von 77,6 % gegenüber 74,9 % bei Clustering-basiertem SS.
- Transferierbarkeit: Mit einem größeren Modell (Llama3-8B) ausgewählte Teilmengen ließen sich erfolgreich auf ein kleineres Modell (Qwen2.5-3B) übertragen und übertrafen dabei sogar die direkt vom Zielmodell ausgewählten Teilmengen, was darauf hindeutet, dass das Low-Rank-Kriterium intrinsische Dateneigenschaften erfasst.
- Ablation: Die Methode erwies sich als robust gegenüber der Wahl der Basis-Selektion; dabei performte Leverage Score Sampling am besten, wenngleich selbst eine uniforme Basis-Selektion konkurrenzfähige Ergebnisse lieferte.
Strukturanalyse: Experimente zu GSM8k zeigten, dass der Datensatz einen geringeren Approximationsfehler unter Low-Rank-Annahmen im Vergleich zu Clustering aufweist, was die Anwendbarkeit von Annahme 2.1 bestätigt.

Bedeutung und Ansprüche

Die Arbeit beansprucht, eine robuste und effiziente Alternative zum naiven Subsampling und zu Clustering-basierten Datenselektionen zu bieten, insbesondere in hochdimensionalen und großskaligen Settings.

Theoretischer Beitrag: Sie etabliert rigorose Garantien für die Datenselektion unter Low-Rank-Verlustannahmen und verknüpft die Qualität des Coresets direkt mit der Ausrichtung des Datensatzes auf eine Low-Rank-Struktur ( $\Phi_k(D)$ ).
Praktische Relevanz: Die Autoren zeigen, dass einfache Embeddings aus vortrainierten Modellen (wie BERT) ausreichen, um die benötigte Low-Rank-Struktur zur Selektion informativer Punkte zu approximieren, selbst für wesentlich größere Zielmodelle (LLMs).
Effizienz: Der Ansatz vermeidet die rechnerischen Hürden der Berechnung von Unsicherheits-Scores auf dem gesamten Datensatz (üblich im Active Learning) sowie die Redundanzprobleme der Clustering-basierten Batch-Selektion.
Bescheidenheit: Die Autoren räumen ein, dass Clustering in einigen Fällen weiterhin wertvoll ist, betonen jedoch, dass ihr Low-Rank-Ansatz eine zuverlässigere Grundlage für das dateneffiziente Training großer Modelle bietet, bei denen dominante spektrale Richtungen entscheidend sind. Sie behaupten keine universelle Optimalität, sondern eine signifikante Verbesserung in Szenarien, in denen Daten eine globale algebraische Struktur aufweisen.