🤖 machine learning

Efficient Coreset Selection via K-Nearest Neighbor Graphs

Dit artikel introduceert KNNG-CS, een lichtgewicht coreset-selectiemethode die K-nearest neighbor-grafen gebruikt om efficiënt representatieve datasubsets te identificeren met aanzienlijk lagere tijd- en geheugenkosten, terwijl de nauwkeurigheid vergelijkbaar blijft met bestaande gradiënt-benaderingsmethoden.

Oorspronkelijke auteurs: Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui

Gepubliceerd 2026-08-18

📖 4 min leestijd☕ Koffiepauze-leesvoer

CC BY 4.0

Oorspronkelijke auteurs: Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui

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

Machine learning-modellen zijn de motoren achter veel moderne hulpmiddelen, van het herkennen van gezichten in foto's tot het voorspellen van trends op de aandelenmarkt. Om te leren hoe ze deze taken moeten uitvoeren, moeten deze modellen gevoed worden met enorme hoeveelheden gegevens. Stel je voor dat je een student probeert te onderwijzen door hem elk enkel boek in een bibliotheek te geven; hij zou uiteindelijk wel leren, maar het proces zou ongelooflijk traag en uitputtend zijn. In de wereld van kunstmatige intelligentie is dit de realiteit van trainen op enorme datasets. Het vereist enorme rekenkracht en geheugen, wat het vaak te duur of te traag maakt voor veel praktische toepassingen. Om dit op te lossen, gebruiken wetenschappers een techniek genaamd coreset-selectie. Het doel is simpel: in plaats van de hele bibliotheek te gebruiken, zoek je een kleine, perfecte deelverzameling van boeken die alle essentiële lessen bevat. Als je het model kunt trainen op deze kleine, representatieve steekproef, leert het net zo goed als wanneer het alles had gelezen, maar in een fractie van de tijd en met veel minder geheugen.

Jarenlang hebben de beste manieren om deze kleine, perfecte deelverzamelingen te vinden vertrouwd op een methode die computationeel zwaar is. Deze bestaande benaderingen proberen de afstand tussen elk datapunt en elk ander datapunt te meten om te zien welke het meest op elkaar lijken. Het is also als proberen de beste vertegenwoordiger van een menigte te vinden door elke persoon hun afstand tot elke andere persoon in de kamer te laten meten. Hoewel dit werkt, creëert het een enorme hoeveelheid gegevens die moeilijk op te slaan en te verwerken zijn, vooral wanneer de dataset groot wordt. De onderzoekers aan de Xidian University en hun medewerkers realiseerden zich dat deze "alles meten"-benadering inefficiënt was. Ze observeerden dat de meest nuttige vertegenwoordigers in een dataset meestal degenen zijn die in het midden van dichte groepen vergelijkbare items zitten, in plaats van degenen die alleen staan. Een steekproef die dicht bij veel anderen ligt, is waarschijnlijk een representatie van een veelvoorkomend patroon, terwijl een geïsoleerde steekproef minder waarschijnlijk een goede vervanger is voor een grote groep.

Om dit aan te pakken, ontwikkelde het team een nieuwe methode genaamd KNNG-CS. In plaats van elk item te dwingen de afstand tot elk ander item te meten, bouwden ze een kaart die elk item alleen verbindt met zijn tien dichtstbijzijnde buren. Dit creëert een ijle netwerk, of een graaf, die de lokale relaties tussen datapunten vastlegt zonder de overweldigende last van het berekenen van elke mogelijke verbinding. Zodra deze kaart is gebouwd, gaven de onderzoekers een score toe aan elk item op basis van hoeveel andere items het als buur aanwezen en hoe dicht die buren waren. Items die vaak als een nabije buur door velen werden gekozen, ontvingen een hoge score, wat hen markeerde als zeer belangrijke vertegenwoordigers. Het algoritme selecteerde vervolgens gulzig de hoogst scorende items om de uiteindelijke kleine deelverzameling te vormen. Terwijl elk hoog scorend item werd gekozen, verwijderde het algoritme dit item en zijn buren uit de pool, waardoor de geselecteerde groep de volledige dataset efficiënt dekte zonder redundantie.

De resultaten van deze nieuwe benadering waren opmerkelijk toen ze werden getest op vier real-world datasets, variërend van bosbedekkingssoorten tot filmbeoordelingen en kredietkaart wanbetalingen. De nieuwe methode produceerde een kleine trainingsset waarmee het machine learning-model een nauwkeurigheid kon bereiken die vergelijkbaar is met de beste bestaande methoden. Echter, het verschil in efficiëntie was dramatisch. De nieuwe methode draaide tussen de 2,3 en 41,2 keer sneller dan de voorheen leidende technieken. Nog indrukwekkender was de vermindering in geheugengebruik. Terwijl oudere methoden enorme tabellen met afstanden vereisten die gigabytes aan geheugen konden consumeren, gebruikte de nieuwe benadering slechts 0,3% tot 7,5% van dat geheugen. In praktische termen betekent dit dat taken die voorheen dure, hoogwaardige servers vereisten, nu kunnen worden uitgevoerd op veel kleinere, meer toegankelijke machines. De onderzoekers ontdekten dat zelfs met een zeer kleine deelverzameling van gegevens, het model effectief leerde en veel sneller convergeerde naar een stabiele oplossing dan wanneer het op de volledige dataset zou zijn getraind.

Dit werk demonstreert dat door te focussen op lokale relaties in plaats van globale vergelijkingen, het mogelijk is om het proces van het voorbereiden van gegevens voor machine learning drastisch te vereenvoudigen. De studie bevestigt dat u niet elke mogelijke afstand hoeft te berekenen om de belangrijkste datapunten te vinden; een slimme, lokale kaart is voldoende. Door deze graafgebaseerde strategie te gebruiken, hebben de onderzoekers aangetoond dat hoogwaardige modeltraining kan worden bereikt met een fractie van de tijd en middelen die voorheen nodig werden geacht. Dit opent de deur naar efficiëntere trainingsprocessen, waardoor complexe modellen kunnen worden ontwikkeld en ingezet in omgevingen waar de rekenkracht beperkt is, zonder dat dit ten koste gaat van de kwaliteit van het eindresultaat.

Technische Samenvatting: Efficiënte Coreset-selectie via K-Nearest Neighbor Grafen

Probleemstelling

Coreset-selectie beoogt de computationele en geheugenkosten van het trainen van machine learning-modellen te verminderen door een grote trainingsset te vervangen door een kleine, representatieve deelverzameling. Het artikel richt zich op gradient-approximation (GA) gebaseerde coreset-selectie. In dit kader is het doel om een deelverzameling $C$ van grootte $M$ te selecteren uit een trainingsset $T$ , zodanig dat de gradiënten van de volledige set goed worden benaderd door de deelverzameling. Dit probleem wordt wiskundig gereduceerd tot het minimaliseren van de fout in de kenmerkruimte-representatie (Vergelijking 1), waarbij elk datapunt wordt gerepresenteerd door zijn dichtstbijzijnde buur in de geselecteerde coreset.

Bestaande GA-gebaseerde methoden, zoals CRAIG en FastCore, vertrouwen op greedily selectiestrategieën. Zij kampen echter met aanzienlijke schaalbaarheidsproblemen:

CRAIG berekent vooraf een dichte paarwijze afstandsmatrix, wat $O(n^2)$ ruimte en $O(n^2d)$ tijd vereist, wat prohibitief wordt bij grote datasets.
FastCore vervangt item-item afstanden door item-cluster bovengrenzen om ruimte te besparen, maar vereist vaak een enorm aantal clusters (honderden tot tienduizenden) om de nauwkeurigheid te behouden, wat leidt tot aanzienlijke overhead bij het berekenen en opslaan van grote bounding-matrices.

De auteurs observeren dat representativiteit in de kenmerkruimte inherent lokaal is: een sample die dient als een nabije buur voor veel andere samples, is waarschijnlijk een representant van een dicht lokaal gebied met een lage benaderingsfout. Bestaande methoden slagen er niet in deze lokaliteit efficiënt te exploiteren omdat ze vertrouwen op dichte structuren in plaats van ijle (sparse) buurtrelaties.

Methodologie: KNNG-CS

Het artikel stelt KNNG-CS voor, een lichtgewicht coreset-selectiemethode gebaseerd op een K-Nearest Neighbor Graph (KNNG). De methode werkt in drie hoofdfases:

1. Benaderende KNNG-constructie

In plaats van alle paarwijze afstanden te berekenen, bouwt de methode een benaderende KNNG $G=(V, E)$ over de feature vectoren. Elke node $x_i$ is verbonden met zijn $K$ dichtstbijzijnde buren.

Efficiëntie: Door gebruik te maken van state-of-the-art benaderende methoden (bijv. KGraph), is de constructietijd $O(n^{1.14}d)$ , en de ruimtecomplexiteit is lineair, $O(nK)$, waarbij $K$ een kleine constante is (gesteld op 10 in experimenten). Dit voorkomt de kwadratische ruimtevereiste van dichte matrices.

2. Afstandbewuste Node Scoring

De kerninnovatie is een scoringfunctie die de belangrijkheid van elke node (datapunt) schat op basis van zijn lokale buurtstructuur binnen de KNNG.

In-degree: Een node met een hoge in-degree (veel nodes wijzen naar deze als dichtstbijzijnde buur) is een sterke kandidaat voor representativiteit.
Afstandsbewustzijn: In-degree alleen is onvoldoende. De methode incorporeert edge-afstanden door ze om te zetten in waarschijnlijkheden met behulp van een softmax-functie (Vergelijking 2).
Scoringformule: De belangrijkheidsscore $P_i$ voor een node $v_i$ is de som van de softmax-waarschijnlijkheden van alle inkomende edges (Vergelijking 3):
$P_i = \sum_{v_j \in N_{in}^G(v_i)} p_{ji}$
waarbij $p_{ji}$ de genormaliseerde nabijheidsscore vertegenwoordigt van buur $v_j$ naar $v_i$ . Dit stelt de methode in staat om onderscheid te maken tussen nodes met gelijke in-degrees maar verschillende nabijheid tot hun buren.

3. Greedy Selectie met Redundantieverwijdering

Het selectieproces is een one-pass greedy algoritme:

Bereken de belangrijkheidsscore $P_i$ voor alle nodes.
Selecteer de node met de hoogste score en voeg deze toe aan de coreset $C$ .
Redundantieverwijdering: Verwijder onmiddellijk de geselecteerde node en al zijn in-buren uit de graaf. De ratio is dat als een node wordt geselecteerd, zijn in-buren (die hem als een nabije buur beschouwen) door hemzelf worden gerepresenteerd en dus niet zelf geselecteerd hoeven te worden.
Herhaal tot $M$ items zijn geselecteerd.

Deze aanpak vermijdt herhaalde herberekening van het voordeel (benefit recomputation), een belangrijke bottleneck in traditionele greedy methoden.

Belangrijkste Bijdragen

KNNG-CS Algoritme: Een schaalbare, GA-gebaseerde coreset-selectiemethode die een ijle K-Nearest Neighbor Graaf gebruikt om dure dichte afstandstructuren te vermijden.
Nieuw Scoringmechanisme: Een afstandbewuste inkomende-buur scoringfunctie die lokale representativiteit direct uit de KNNG schat zonder dichte paarwijze afstanden op te slaan.
Efficiëntiewinsten: Empirische validatie die aantoont dat de methode de selectietijd en het geheugengebruik aanzienlijk vermindert, terwijl de coreset-kwaliteit vergelijkbaar blijft met state-of-the-art methoden.

Experimentele Resultaten

De auteurs evalueerden KNNG-CS op vier real-world datasets: CovType, IMDB, Brazil, en Card. Ze vergeleken hun methode met Random sampling, CRAIG en FastCore.

Effectiviteit (Nauwkeurigheid): KNNG-CS behaalde een testnauwkeurigheid die vergelijkbaar is met CRAIG en FastCore, en significant beter dan Random sampling. Hoewel CRAIG op sommige datasets (IMDB, Card, Brazil) een iets hogere nauwkeurigheid vertoonde vanwege het gebruik van exacte afstanden, behield KNNG-CS een concurrerende prestatie.
Efficiëntie (Tijd): KNNG-CS demonstreerde substantiële versnellingen:
- 2,3× tot 41,2× sneller dan CRAIG.
- 2,3× tot 4,9× sneller dan FastCore.
  De versnelling wordt toegeschreven aan de efficiënte KNNG-constructie en de one-pass greedy strategie die herhaalde matrixberekeningen vermijdt.
Geheugengebruik: KNNG-CS reduceerde het piekgeheugengebruik drastisch:
- Vereiste slechts 0,3% tot 3,4% van het piekgeheugen dat door CRAIG werd gebruikt.
- Vereiste slechts 4,1% tot 7,5% van het piekgeheugen dat door FastCore werd gebruikt.
  Dit komt doordat KNNG-CS slechts $O(nK)$ edges opslaat, terwijl concurrenten $O(n^2)$ afstandmatrices of grote item-cluster bounding-matrices opslaan.
Convergentie: Trainen op de geselecteerde coreset convergeerde veel sneller (in termen van iteraties) dan trainen op de volledige dataset, waarbij de coreset-grootte $M=0.01n$ een goede balans bood tussen efficiëntie en effectiviteit.

Betekenis en Claims

Het artikel claimt dat KNNG-CS een praktische oplossing biedt voor grootschalige coreset-selectie door over te stappen van dichte, globale afstandstructuren naar ijle, lokale buurtstructuren. Door gebruik te maken van de inherente lokaliteit van kenmerkruimtes, bereikt de methode:

Lineaire opslagcomplexiteit ($O(nK)$) vergeleken met de kwadratische complexiteit ( $O(n^2)$ ) van voorheen state-of-the-art methoden.
Significante reducties in zowel tijd- als kosten voor geheugen zonder de kwaliteit van de geselecteerde deelverzameling op te offeren.
Een lichtgewicht selectieproces dat slechts één pass van de greedy selectie vereist na de graafconstructie, waardoor herhaalde afstandsberekeningen worden geëlimineerd.

De auteurs concluderen dat deze aanpak efficiënte coreset-selectie mogelijk maakt voor grote datasets waar traditionele gradient-approximation methoden computationeel of geheugentechnisch prohibitief zijn.