🤖 machine learning

Active Learning with Low-Rank Structure for Data Selection

Dit artikel introduceert een nieuw dataselectiekader dat gebruikmaakt van laag-rang benadering en residu-gebaseerde bemonstering om efficiënt een gewogen deelverzameling van datapunten te kiezen, waarbij theoretische garanties en empirische verbeteringen worden geboden ten opzichte van traditionele clusteringgebaseerde methoden voor datasets met een globale algebraïsche structuur.

Oorspronkelijke auteurs: Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni, Mahdi Nikdan, David P. Woodruff, Samson Zhou

Gepubliceerd 2026-06-16

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Vincent Cohen-Addad, Sasidhar Kunapuli, Vahab Mirrokni, Mahdi Nikdan, David P. Woodruff, Samson Zhou

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een chef bent die probeert de beste soep ter wereld te maken. Je hebt een enorme loods vol met duizenden verschillende groenten, kruiden en bouillon (jouw dataset). Om de perfecte soep te maken, moet je al deze ingrediënten proeven en mengen. Maar hier is het probleem: je keuken is piepklein, je fornuis is zwak en je hebt slechts een paar uur. Koken met de volledige loods is onmogelijk.

Je moet een kleine, perfecte handvol ingrediënten kiezen die precies dezelfde smaak geven als de hele loods. Dit is het Data Selectie-problek.

De Oude Manier: Kiezen op basis van "Afstand"

Een tijdlang gebruikten de beste chefs een methode genaamd Clustering. Stel je voor dat je de loods binnenloopt en uit elke verschillende hoek één groente pakt. Je pakt een wortel uit het noorden, een aardappel uit het zuiden, een paprika uit het oosten en een tomaat uit het westen.

De logica was: "Als ik dingen kies die ver van elkaar verwijderd zijn, moet ik alle basiszaken dekken." Dit werkte redelijk voor eenvoudige recepten. Maar in de moderne wereld, waar data enorm en complex is (zoals een loods met miljoenen artikelen), heeft deze methode een gebrek. Het focust op waar de items zich bevinden, niet op wat ze eigenlijk doen. Je kunt eindigen met een tas vol verschillende ogende groenten die allemaal exact hetzelfde smaken, terwijl je de ene geheime specerij mist die de smaak van de soep eigenlijk bepaalt.

De Nieuwe Manier: Kiezen op basis van "Structuur"

De auteurs van dit artikel zeggen: "Stop met kijken naar waar de groenten staan. Kijk naar de vorm van de smaak."

Ze stellen een nieuwe methode voor die gebaseerd is op Low-Rank Structure.
Beschouw je soepingrediënten niet als individuele items, maar als een complex 3D-sculptuur. Zelfs al ziet het sculptuur er ingewikkeld uit, het kan in feite gebouwd zijn van slechts een paar hoofdbalken en steunpilaren. De rest is slechts decoratie.

De Hoofdbalken (Low-Rank): Dit zijn de belangrijkste richtingen van de smaak. Als je deze goed krijgt, krijg je de soep goed.
De Decoratie (Residuals): Dit zijn de kleine, onbelangrijke details die de smaak niet veel veranderen.

De methode van de auteurs gebruikt een wiskundige "röntgenfoto" (genoemd Low-Rank Approximation) om die hoofdbalken te vinden. In plaats van groenten te kiezen die ver uit elkaar liggen, kiezen ze de specifieke ingrediënten die de hoofdbalken van de smaakstructuur ondersteunen.

Hoe ze het doen: De "Gevoeligheidsschaal"

Om te bepalen welke ingrediënten de "hoofdbalken" zijn, gebruiken ze een techniek genaamd Sensitivity Sampling.

Stel je voor dat je een enorme weegschaal hebt. Je legt een groente op de schaal, en de schaal vertelt je: "Als je deze weglaat, hoeveel zal de smaak van de soep dan veranderen?"

Als de smaak veel verandert, schiet de schaal uit de bochten. Die groente is zeer gevoelig (zeer belangrijk).
Als de smaak nauwelijks verandert, blijft de schaal laag. Die groente heeft een lage gevoeligheid (redundant).

Hun algoritme berekent deze score voor elk enkel item in de loods, en kiest vervolgens willekeurig een kleine groep ingrediënten, maar dan gewogen naar hoe belangrijk ze zijn. Je hebt een veel grotere kans om de "hoog gevoelige" items te kiezen.

De Resultaten: Waarom het ertoe doet

Het paper testte dit idee op twee manieren:

De Creditcardtest: Ze probeerden te voorspellen wie een betaling met een creditcard zou missen met behulp van een standaard financiële dataset. Hun "Low-Rank"-methode koos een kleine groep klanten die de uitkomst veel beter voorspelde dan de oude "Clustering"-methode of het simpelweg willekeurig kiezen.
De Reusachtige Brein Test (LLM's): Ze probeerden een enorme AI (Llama3-8B) te leren om wiskunde te doen en vragen te beantwoorden. Het trainen van de AI op de volledige dataset duurt eeuwig en kost een fortuin. Door hun methode te gebruiken om slechts 6% tot 25% van de data te kiezen, trainden ze de AI om slimmer te zijn dan wanneer ze willekeurige data of de oude clustering-methode hadden gebruikt.

De Belangrijkste Conclusie

Het paper beweert dat voor moderne, enorme datasets de "vorm" van de data (de algebraïsche structuur) belangrijker is dan de "afstand" tussen datapunten.

Door te focussen op de belangrijkste structurele balken van de data in plaats van alleen maar te proberen alle hoeken te dekken, kun je 90% van je data weggooien en nog steeds een machine learning-model trainen dat net zo goed, of zelfs beter presteert, dan wanneer je alles had gebruikt. Het is alsof je beseft dat je niet elke korrel zout in de oceaan hoeft te proeven om te weten hoe zout de soep is; je hebt alleen een lepel nodig die de ware karakteristiek van de oceaan vertegenwoordigt.

Technische Samenvatting: Active Learning met Low-Rank Structuur voor Dataselectie

Probleemdefinitie

Het artikel behandelt het dataselectieprobleem in machine learning, specifiek de uitdaging om een kleine, representatieve deelverzameling van data (een coreset) te identificeren die een efficiënte training van modellen mogelijk maakt zonder de prestaties significant te verminderen. Hoewel moderne datasets en fundamentmodellen succes hebben gedreven, brengen zij steile computationele kosten met zich mee voor training en fine-tuning.

Bestaande benaderingen, zoals die van Sener en Savarese [SS18] en Axiotis et et al. [ACH+24], vertrouwen op clustering-gebaseerde heuristieken (bijv. $k$ -center of $k$ -means) toegepast op data-embeddings. Deze methoden gaan ervan uit dat data een intrinsieke geometrische structuur bezit waarbij diversiteit en de afstand tussen punten de primaire drijvers van informatieve waarde zijn. De auteurs stellen echter dat veel moderne datasets, met name in hoogdimensionale ruimtes, een globale algebraïsche structuur vertonen die beter wordt gevangen door low-rank benaderingen (bijv. Principal Component Analysis) dan door lokale geometrische clustering. Clusteringmethoden kunnen er mogelijk niet in slagen om dominante richtingen van variantie te vangen, waardoor kritieke componenten voor modeltraining gemist kunnen worden.

Methodologie

Het artikel stelt een nieuw raamwerk voor dataselectie voor op basis van low-rank benadering en residueel-gebaseerde sensitiviteitssteekproeven (sensitivity sampling). Het kernidee is om de nadruk te leggen op het behoud van dominante spectrale richtingen van de data, in plaats van enkel de geometrische diversiteit te maximaliseren.

Theoretisch Raamwerk

De benadering is geworteld in het Row Subset Selection probleem en loss-preserving coreset constructie. De auteurs introduceren Aanname 2.1, die stelt dat voor een dataset $D$ met een embedding-matrix, de verliesfunctie $\ell$ kan worden gedecomposeerd ten opzichte van een $k$ -dimensionale subspace $V$ (gespannen door de top singuliere vectoren of hoofdcomponenten):

Orthogonale Straf: De afwijking in verlies voor een punt $y$ buiten de subspace $V$ wordt kwadratisch begrensd door de norm van zijn residuele component $r(y)$ die orthogonaal staat op $V$ , geschaald door een constante $\lambda$ .
Subspace Approximatie: Binnen de subspace $V$ wordt het verlies goed benaderd door een gewogen som van verliezen langs de basisrichtingen, geschaald door een constante $\gamma$ .

Deze aanname formaliseert de intuïtie dat richtingen die orthogonaal staan op de dominante low-rank subspace minder bijdragen aan het verlies of minder informatief zijn, een eigenschap die wordt waargenomen in taken zoals PCA, matrix completion en Low-Rank Adaptation (LoRA).

Algoritme: Sensitivity Sampling

Het voorgestelde algoritme (Algoritme 2) construeert een gewogen coreset $S$ via de volgende stappen:

Low-Rank Sketch: Bereken een rank- $k$ benadering van de dataset (bijv. via SVD) om de subspace $V$ en de basis $\{v_1, \dots, v_k\}$ te definiëren.
Decompositie: Decomposeer elk datapunt $x$ in zijn projectie $v(x)$ op $V$ en zijn residu $r(x)$ dat orthogonaal staat op $V$ .
Berekening van de Sensitivity Score: Bereken een sensitiviteitsscore $\sigma(x)$ $σ (x)$ voor elk punt die het volgende combineert:
- Het gewogen verlies langs de basisrichtingen: $(\gamma + 1)\sum \alpha_i^2 \ell(v_i)$ .
- Een straf voor het residu: $\lambda \|r(x)\|_2^2$ .
- Een constante term gerelateerd aan het maximale verlies in de basis.
Steekproef (Sampling): Trek punten uit de dataset met vervanging, evenredig aan hun genormaliseerde sensitiviteitsscores $p(x) = \sigma(x) / \sum \sigma(y)$ .
Weging: Ken gewichten $w(x) = 1/(s \cdot p(x))$ toe aan de getrokken punten om ervoor te zorgen dat de estimator onbevooroordeeld is.

Belangrijkste Bijdragen

Theoretische Garanties (Theorem 2.2 & 2.3): Het artikel bewijst dat een gewogen deelverzameling van omvang $\tilde{O}(k + 1/\varepsilon^2)$ het gemiddelde verlies van de volledige dataset kan benaderen binnen een $(1 \pm \varepsilon)$ relatieve fout, tot een additieve term die proportioneel is aan de optimale rank- $k$ benaderingskosten $\Phi_k(D)$ .
- Theorem 2.2 garandeert dit voor een algemene gewogen deelverzameling.
- Theorem 2.3 breidt dit uit naar Row Subset Selection, wat ervoor zorgt dat de geselecteerde deelverzameling daadwerkelijke datapunten uit de invoerdataset bestaat.
- De foutmarge is expliciet afhankelijk van $\Phi_k(D)$ , wat aangeeft dat datasets met een sterke low-rank structuur nauwere grenzen en accuratere coresets opleveren.
Algoritmische Innovatie: De auteurs introduceren een sensitivity sampling algoritme dat gebruikmaakt van de low-rank structuur om belangsscores te berekenen, wat afwijkt van de geometrische afstandmetrieken die worden gebruikt in clustering-gebaseerde methoden.
Empirische Validatie: Het raamwerk wordt gevalideerd op zowel tabulaire data (Credit Card Default dataset) als grootschalige taalmodel fine-tuning (Llama3-8B en Qwen2.5-3B op GSM8k, ViGGO en SQL taken).

Experimentele Resultaten

Het artikel evalueert de voorgestelde Low-Rank Sensitivity Sampling (Low-rank SS) tegenover verschillende baselines: Uniform Sampling, $k$ -Center, Clustering-gebaseerde Sensitivity Sampling en Graph Cut.

Tabulaire Data (Credit Card Dataset):
- Low-rank SS bereikte de laagste benaderingsfout in som van kwadraten, waarbij de fout met een orde van grootte werd verminderd vergeleken met random sampling en met ~50% vergeleken met clustering bij kleine steekproefgroottes ( $s=1000$ ).
- In downstream logistische regressie behaalde Low-rank SS een testnauwkeurigheid van tot wel 74% bij $s=5000$ , waarmee het clustering (70%) en random sampling (67%) versloeg.
LLM Fine-Tuning (Llama3-8B & Qwen2.5-3B):
- Op de GSM8k, ViGGO en SQL taken presteerde Low-rank SS consistent beter dan uniform sampling en clustering-gebaseerde methoden.
- Bijvoorbeeld, op ViGGO met Llama3-8B bij 25% datacompressie behaalde Low-rank SS een nauwkeurigheid van 77,6% tegenover 74,9% voor clustering-gebaseerde SS.
- Transfereerbaarheid: Deelverzamelingen geselecteerd met een groter model (Llama3-8B) werden succesvol overgedragen naar een kleiner model (Qwen2.5-3B), en presteerden zelfs beter dan deelverzamelingen die direct door het doelmodel waren geselecteerd, wat suggereert dat het low-rank criterium intrinsieke datagegenschappen vastlegt.
- Ablatie: De methode bleek robuust voor de keuze van de basisselectie, waarbij leverage score sampling het beste presteerde, hoewel zelfs uniforme basisselectie concurrerende resultaten opleverde.
Structuuranalyse: Experimenten op GSM8k toonden aan dat de dataset een lagere benaderingsfout vertoont onder low-rank aannames vergeleken met clustering, wat de toepasbaarheid van Aanname 2.1 valideert.

Betekenis en Claims

Het artikel beweert een robuust en efficiënt alternatief te bieden voor naïeve subsampling en clustering-gebaseerde dataselectie, met name voor hoogdimensionale en grootschalige settings.

Theoretische Bijdrage: Het vestigt rigoureuze garanties voor dataselectie onder low-rank verliesaannames, waarbij de kwaliteit van de coreset direct wordt gekoppeld aan de uitlijning van de dataset met een low-rank structuur ( $\Phi_k(D)$ ).
Praktische Impact: De auteurs tonen aan dat eenvoudige embeddings van getrainde modellen (zoals BERT) voldoende zijn om de low-rank structuur te benaderen die nodig is voor het selecteren van informatieve punten, zelfs voor veel grotere doelmodellen (LLM's).
Efficiëntie: De aanpak vermijdt de computationele beperkingen van het berekenen van onzekerheidsscores op volledige datasets (gebruikelijk in active learning) en de redundantieproblemen van clustering-gebaseerde batchselectie.
Bescheidenheid: De auteurs erkennen dat clustering in sommige gevallen nog steeds waarde heeft, maar dat hun low-rank benadering een betrouwbaarder fundament biedt voor data-efficiënte training op grootschalige modellen waar dominante spectrale richtingen cruciaal zijn. Ze beweren geen universele optimaliteit, maar een significante verbetering in settings waar data een globale algebraïsche structuur vertoont.