🤖 machine learning

Efficient Coreset Selection via K-Nearest Neighbor Graphs

Questo articolo introduce KNNG-CS, un metodo di selezione di coreset leggero che sfrutta i grafi dei K-vicini più prossimi per identificare efficientemente sottoinsiemi di dati rappresentativi con costi di tempo e memoria significativamente ridotti, mantenendo al contempo un'accuratezza paragonabile agli approcci di approssimazione del gradiente esistenti.

Autori originali: Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui

Pubblicato 2026-08-18

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Yingfan Liu, Leiyu Zhang, Jiadong Xie, Mingzhe Wang, Jeffrey Xu Yu, Jiangtao Cui

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

I modelli di machine learning sono i motori che alimentano molti strumenti moderni, dal riconoscimento dei volti nelle foto alla previsione delle tendenze del mercato azionario. Per imparare a svolgere questi compiti, questi modelli devono essere nutriti con enormi quantità di dati. Immaginate di cercare di insegnare a uno studente fornendogli ogni singolo libro di una biblioteca; alla fine imparerebbe, ma il processo sarebbe incredibilmente lento ed estenuante. Nel mondo dell'intelligenza artificiale, questa è la realtà dell'addestramento su enormi dataset. Ciò richiede un'enorme potenza di calcolo e memoria, rendendo spesso l'operazione troppo costosa o lenta per molte applicazioni pratiche. Per risolvere questo problema, gli scienziati utilizzano una tecnica chiamata selezione del coreset. L'obiettivo è semplice: invece di usare l'intera biblioteca, trovare un piccolo sottoinsieme perfetto di libri che contenga tutte le lezioni essenziali. Se si riesce ad addestrare il modello su questo minuscolo campione rappresentativo, esso imparerà altrettanto bene come se avesse letto tutto, ma in una frazione del tempo e con molta meno memoria.

Per anni, i modi migliori per trovare questi piccoli sottoinsiemi perfetti si sono basati su un metodo computazionalmente pesante. Questi approcci esistenti cercano di misurare la distanza tra ogni singolo punto dati e ogni altro punto dati per vedere quali siano i più simili tra loro. È come cercare di trovare il miglior rappresentante per una folla facendo sì che ogni persona misuri la propria distanza da tutte le altre persone nella stanza. Sebbene questo funzioni, crea una quantità enorme di dati che è difficile da archiviare ed elaborare, specialmente quando il dataset cresce. I ricercatori della Xidian University e i loro collaboratori hanno capito che questo approccio "misura tutto" era inefficiente. Hanno osservato che i rappresentanti più utili in un dataset sono solitamente quelli che si trovano al centro di gruppi densi di elementi simili, piuttosto che quelli che stanno da soli. Un campione che è vicino a molti altri è probabilmente rappresentativo di un modello comune, mentre un campione isolato ha meno probabilità di essere un buon sostituto per un gruppo numeroso.

Per affrontare questo problema, il team ha sviluppato un nuovo metodo chiamato KNNG-CS. Invece di costringere ogni elemento a misurare la propria distanza da ogni altro elemento, hanno costruito una mappa che collega solo ogni elemento ai suoi dieci vicini più prossimi. Questo crea una rete sparsa, o grafo, che cattura le relazioni locali tra i punti dati senza l'onere schiacciante di calcolare ogni possibile connessione. Una volta costruita questa mappa, i ricercatori hanno assegnato un punteggio a ogni elemento in base a quanti altri elementi lo indicavano come vicino e a quanto fossero vicini tali vicini. Gli elementi che venivano scelti frequentemente come vicino da molti altri ricevevano un punteggio elevato, segnalandoli come rappresentanti altamente importanti. L'algoritmo ha quindi selezionato in modo avido (greedy) gli elementi con il punteggio più alto per formare il sottoinsieme finale. Man mano che ogni elemento con punteggio elevato veniva scelto, l'algoritmo lo rimuoveva insieme ai suoi vicini dal pool, assicurando che il gruppo selezionato coprisse l'intero dataset in modo efficiente e senza ridondanze.

I risultati di questo nuovo approccio sono stati sorprendenti quando testati su quattro dataset del mondo reale, che spaziavano dai tipi di copertura forestale alle valutazioni dei film e ai default delle carte di credito. Il nuovo metodo ha prodotto un set di addestramento ridotto che ha permesso al modello di machine learning di raggiungere un'accuratezza paragonabile ai migliori metodi esistenti. Tuttavia, la differenza in termini di efficienza è stata drammatica. Il nuovo metodo è stato tra le 2,3 e le 41,2 volte più veloce delle precedenti tecniche d'avanguardia. Ancora più impressionante è stata la riduzione dell'uso della memoria. Mentre i vecchi metodi richiedevano la memorizzazione di enormi tabelle di distanze che potevano consumare gigabyte di memoria, il nuovo approccio ha utilizzato solo lo 0,3% - 7,5% di tale memoria. In termini pratici, ciò significa che compiti che prima richiedevano server costosi e di fascia alta possono ora essere eseguiti su macchine molto più piccole e accessibili. I ricercatori hanno scoperto che, anche con un sottoinsieme di dati molto piccolo, il modello impara efficacemente, convergendo verso una soluzione stabile molto più velocemente rispetto a un addestramento sull'intero dataset.

Questo lavoro dimostra che concentrandosi sulle relazioni locali anziché sui confronti globali, è possibile semplificare drasticamente il processo di preparazione dei dati per il machine learning. Lo studio conferma che non è necessario calcolare ogni possibile distanza per trovare i punti dati più importanti; una mappa locale intelligente è sufficiente. Utilizzando questa strategia basata sui grafi, i ricercatori hanno dimostrato che è possibile ottenere un addestramento di alta qualità con una frazione del tempo e delle risorse precedentemente ritenute necessarie. Ciò apre la strada a processi di addestramento più efficienti, consentendo lo sviluppo e l'implementazione di modelli complessi in ambienti dove la potenza di calcolo è limitata, senza sacrificare la qualità del risultato finale.

Riepilogo Tecnico: Selezione Efficiente di Coreset tramite Grafi K-Nearest Neighbor

Definizione del Problema

La selezione di coreset mira a ridurre i costi computazionali e di memoria dell'addestramento di modelli di machine learning, sostituendo un grande set di addestramento con un sottoinsieme piccolo e rappresentativo. Il paper si concentra sulla selezione di coreset basata sull'approssimazione del gradiente (GA). In questo framework, l'obiettivo è selezionare un sottoinsieme $C$ di dimensione $M$ da un set di addestramento $T$ tale che i gradienti dell'intero set siano ben approssimati dal sottoinsieme. Questo problema è ridotto matematicamente alla minimizzazione dell'errore di rappresentanza nello spazio delle feature (Eq. 1), dove ogni punto dati è rappresentato dal suo vicino più prossimo nel coreset selezionato.

I metodi esistenti basati su GA, come CRAIG e FastCore, si affidano a strategie di selezione greedy. Tuttavia, essi affrontano significativi problemi di scalabilità:

CRAIG pre-calcola una matrice di distanze pairwise densa, richiedendo $O(n^2)$ di spazio e $O(n^2d)$ di tempo, il che diventa proibitivo su dataset di grandi dimensioni.
FastCore sostituisce le distanze tra elementi con limiti superiori elemento-cluster per risparmiare spazio, ma spesso richiede un numero massiccio di cluster (centinaia o decine di migliaia) per mantenere l'accuratezza, portando a un overhead considerevole nel calcolo e nella memorizzazione di grandi matrici di limiti.

Gli autori osservano che la rappresentatività nello spazio delle feature è intrinsecamente locale: un campione che funge da vicino per molti altri campioni è probabilmente un rappresentante di una regione locale densa con basso errore di approssimazione. I metodi esistenti non riescono a sfruttare efficientemente questa località perché si affidano a strutture dense piuttosto che a relazioni di vicinato sparse.

Metodologia: KNNG-CS

Il paper propone KNNG-CS, un metodo di selezione di coreset leggero basato su un Grafo K-Nearest Neighbor (KNNG). Il metodo opera in tre fasi principali:

1. Costruzione Approssimativa del KNNG

Invece di calcolare tutte le distanze pairwise, il metodo costruisce un KNNG approssimativo $G=(V, E)$ sui vettori delle feature. Ogni nodo $x_i$ si connette ai suoi $K$ vicini più prossimi.

Efficienza: Utilizzando metodi approssimativi allo stato dell'arte (ad es., KGraph), il tempo di costruzione è $O(n^{1.14}d)$ , e la complessità dello spazio è lineare, $O(nK)$, dove $K$ è una costante piccola (impostata a 10 negli esperimenti). Ciò evita il requisito di spazio quadratico delle matrici dense.

2. Punteggio dei Nodi Sensibile alla Distanza

L'innovazione principale è una funzione di punteggio che stima l'importanza di ogni nodo (elemento dei dati) in base alla sua struttura di vicinato locale all'interno del KNNG.

In-Degree: Un nodo con un alto in-degree (molti nodi puntano a esso come vicino più prossimo) è un forte candidato per la rappresentatività.
Consapevolezza della Distanza: L'in-degree da solo non è sufficiente. Il metodo incorpora le distanze degli archi convertendole in probabilità utilizzando una funzione softmax (Eq. 2).
Formula di Punteggio: Il punteggio di importanza $P_i$ per un nodo $v_i$ è la somma delle probabilità softmax di tutti gli archi entranti (Eq. 3):
$P_i = \sum_{v_j \in N_{in}^G(v_i)} p_{ji}$
dove $p_{ji}$ rappresenta il peso di vicinanza normalizzato dal vicino $v_j$ a $v_i$ . Ciò consente al metodo di distinguere tra nodi con uguali in-degree ma diverse prossimità ai propri vicini.

3. Selezione Greedy con Rimozione della Ridondanza

Il processo di selezione è un algoritmo greedy a singolo passaggio:

Calcolare il punteggio di importanza $P_i$ per tutti i nodi.
Selezionare il nodo con il punteggio più alto e aggiungerlo al coreset $C$ .
Rimozione della Ridondanza: Rimuovere immediatamente il nodo selezionato e tutti i suoi in-vicini dal grafo. La logica è che se un nodo viene selezionato, i suoi in-vicini (che lo considerano un vicino stretto) saranno rappresentati da esso e non devono essere selezionati a loro volta.
Ripetere fino a quando non vengono selezionati $M$ elementi.

Questo approccio evita il ricalcolo ripetuto del beneficio, un collo di bottiglia principale nei metodi greedy tradizionali.

Contributi Chiave

Algoritmo KNNG-CS: Un metodo di selezione di coreset basato su GA e scalabile, che utilizza un grafo K-Nearest Neighbor sparso per evitare costose strutture di distanza dense.
Meccanismo di Punteggio Innovativo: Una funzione di punteggio dei vicini entranti sensibile alla distanza che stima la rappresentatività locale direttamente dal KNNG senza memorizzare distanze pairwise dense.
Guadagni di Efficienza: Validazione empirica che dimostra come il metodo riduca significativamente il tempo di selezione e l'uso della memoria mantenendo una qualità del coreset comparabile ai metodi allo stato dell'arte.

Risultati Sperimentali

Gli autori hanno valutato KNNG-CS su quattro dataset reali: CovType, IMDB, Brazil e Card. Hanno confrontato il loro metodo con il campionamento Random, CRAIG e FastCore.

Efficacia (Accuratezza): KNNG-CS ha ottenuto un'accuratezza di test comparabile a CRAIG e FastCore, e significativamente migliore del campionamento Random. Sebbene CRAIG abbia mostrato un'accuratezza leggermente superiore su alcuni dataset (IMDB, Card, Brazil) grazie all'uso di distanze esatte, KNNG-CS ha mantenuto prestazioni competitive.
Efficienza (Tempo): KNNG-CS ha dimostrato accelerazioni sostanziali:
- Da 2.3× a 41.2× più veloce di CRAIG.
- Da 2.3× a 4.9× più veloce di FastCore.
  L'accelerazione è attribuita all'efficiente costruzione del KNNG e alla strategia greedy a singolo passaggio che evita calcoli matriciali.
Utilizzo della Memoria: KNNG-CS ha ridotto drasticamente il consumo di memoria di picco:
- Ha richiesto solo lo 0.3% - 3.4% della memoria di picco utilizzata da CRAIG.
- Ha richiesto solo il 4.1% - 7.5% della memoria di picco utilizzata da FastCore.
  Ciò è dovuto al fatto che KNNG-CS memorizza solo $O(nK)$ archi, mentre i competitor memorizzano matrici di distanza $O(n^2)$ o grandi matrici di limiti elemento-cluster.
Convergenza: L'addestramento sul coreset selezionato è confluito molto più velocemente (in termini di iterazioni) rispetto all'addestramento sul dataset completo, con la dimensione del coreset $M=0.01n$ che fornisce un buon equilibrio tra efficienza ed efficacia.

Significato e Rivendicazioni

Il paper afferma che KNNG-CS offre una soluzione pratica per la selezione di coreset su larga scala spostandosi da strutture di distanza globali e dense a strutture di vicinato locali e sparse. Sfruttando l'intrinseca località degli spazi delle feature, il metodo ottiene:

Complessità di memorizzazione lineare ($O(nK)$) rispetto alla complessità quadratica ( $O(n^2)$ ) dei precedenti metodi allo stato dell'arte.
Riduzioni significative sia nei costi di tempo che di memoria senza sacrificare la qualità del sottoinsieme selezionato.
Un processo di selezione leggero che richiede un unico passaggio di selezione greedy dopo la costruzione del grafo, eliminando la necessità di calcoli di distanza ripetuti.

Gli autori concludono che questo approccio consente una selezione di coreset efficiente per grandi dataset dove i metodi tradizionali di approssimazione del gradiente sono computazionalmente o memoriamente proibitivi.