TorchKM: A GPU-Oriented Library for Kernel Learning and Model Selection

Sintesi Tecnica di TorchKM: Una Libreria Orientata alle GPU per l'Apprendimento dei Kernel e la Selezione dei Modelli

Problematica
Le macchine a kernel, inclusi i Support Vector Machines (SVM), la regressione logistica a kernel e la regressione quantilica a kernel, sono algoritmi fondamentali noti per le loro forti prestazioni predittive e rigorose fondamenta teoriche. Tuttavia, il loro adozione nella pratica moderna è spesso limitata dagli elevati costi computazionali, in particolare durante la fase di selezione del modello. I flussi di lavoro tradizionali trattano l'addestramento e la selezione del modello (ad esempio, la sintonizzazione degli iperparametri tramite cross-validation) come fasi separate. Ciò richiede ripetuti adattamenti del modello attraverso una griglia di parametri di sintonizzazione e fold di cross-validation. Per i metodi a kernel, che comportano la risoluzione di sistemi lineari con complessità $O(n^3)$, questo rifit ripetuto crea un collo di bottiglia proibitivo. Sebbene l'accelerazione hardware tramite unità di elaborazione grafica (GPU) sia stata esplorata (ad esempio, ThunderSVM), il semplice porting di esistenti solver per CPU su GPU produce spesso solo miglioramenti modesti, poiché le ripetute operazioni matriciali attraverso i parametri di sintonizzazione e i fold continuano a dominare il costo computazionale.

Metodologia
TorchKM affronta queste limitazioni attraverso un approccio di "co-design algoritmo-hardware". Invece di limitarsi a portare un solver per CPU su GPU, la libreria è costruita da zero per sfruttare l'algebra lineare favorevole alle GPU. La metodologia principale si basa su due innovazioni algoritmiche chiave che permettono la soluzione esatta della pipeline di addestramento e sintonizzazione senza approssimazioni:

1. Formula di Cross-Validation Esatta: Per evitare l'onere computazionale del riaddestramento dei modelli per ogni fold di cross-validation, TorchKM utilizza una riformulazione in cui la matrice del kernel rimane invariata. Invece di rifare l'adattamento, il metodo modifica il vettore di risposta per ogni fold. Ciò consente il riutilizzo della stessa matrice del kernel e delle sue decomposizioni associate, riducendo significativamente l'overhead della cross-validation.
2. Algoritmo Spettrale: Per gestire la sintonizzazione dei parametri di regolarizzazione (il percorso della soluzione), TorchKM impiega un approccio spettrale. Esso calcola una singola decomposizione degli autovalori della matrice del kernel ($K = U\Lambda U^\top$). Gli aggiornamenti successivi per diversi parametri di sintonizzazione vengono eseguiti tramite moltiplicazioni matrice-vettore ($O(n^2)$) piuttosto che tramite ripetute inversioni di matrice ($O(n^3)$). Questa struttura è intrinsecamente parallelizzabile e ben adatta all'architettura GPU.

Questi algoritmi sono integrati in una pipeline unificata che supporta un'API "stile scikit-learn". La libreria supporta vari metodi tra cui SVM, Discriminazione Pesata con Distanza (DWD), regressione logistica a kernel e regressione quantilica a kernel. Offre inoltre un'approssimazione di Nyström per dataset su larga scala dove le soluzioni esatte sono impraticabili, e include la scalatura di Platt per la calibrazione della probabilità.

Contributi Chiave

• Pipeline Integrata: A differenza delle librerie che separano addestramento e sintonizzazione, TorchKM integra entrambi i processi in un singolo passaggio algoritmico, eliminando la necessità di ripetuti rifit esterni.
• Soluzioni Esatte: La libreria fornisce soluzioni esatte (non approssimate) per l'intera pipeline di addestramento e sintonizzazione, distinguendosi dai metodi che si affidano ad approssimazioni euristiche per la velocità.
• Ampio Supporto ai Metodi: Oltre agli SVM, la libreria implementa la regressione logistica a kernel, la regressione quantilica a kernel e la DWD, condividendo tutte un'API coerente.
• Implementazione Open-Source: La libreria è rilasciata sotto licenza MIT, disponibile tramite PyPI e GitHub, e include documentazione completa, tutorial e benchmark.

Risultati
I benchmark presentati nel paper dimostrano che TorchKM raggiunge prestazioni predittive competitive con sostanziali accelerazioni rispetto ai baseline standard:

• Confronto con scikit-learn: TorchKM supera significativamente le implementazioni basate su CPU. In uno scenario con $n=20.000$ campioni e $p=1.000$ feature, scikit-learn non è riuscito a completare il compito di addestramento e sintonizzazione entro un limite di 8 ore, mentre TorchKM ha completato il compito in 129,3 secondi.
• Confronto con ThunderSVM: Sebbene ThunderSVM acceleri il fitting di un singolo modello su GPU, TorchKM migliora ulteriormente le prestazioni accelerando l'intera pipeline di sintonizzazione. Nello stesso setting $n=20.000, p=1.000$, TorchKM (129,3s) è stato più veloce di ThunderSVM (580,8s).
• Scalabilità: Il paper nota che per $n=10.000$, TorchKM è più di due ordini di grandezza più veloce delle implementazioni standard su CPU e quasi due ordini di grandezza più veloce delle implementazioni standard su GPU che non utilizzano le strategie integrate spettrali e di cross-validation.
• Calibrazione: La libreria produce stime di probabilità ben calibrate, con un Errore di Calibrazione Attesa (ECE) di 0,044 e un punteggio di Brier di 0,130 nei casi testati.

Significatività
Il paper sostiene che la barriera primaria all'uso diffuso delle macchine a kernel sia il costo computazionale della sintonizzazione degli iperparametri. Riprogettando l'algoritmo per spostare l'onere della complessità cubica in operazioni matrice-vettore che sfruttano il parallelismo delle GPU, TorchKM rende fattibile l'intera pipeline di addestramento e sintonizzazione per dati strutturati su larga scala. Gli autori sostengono che questo approccio consenta ai metodi a kernel di raggiungere il loro pieno potenziale predittivo, abilitando una sintonizzazione accurata del modello che era precedentemente proibitiva dal punto di vista computazionale. La libreria rappresenta un passo verso la resa pratica dell'apprendimento a kernel esatto per i moderni dataset attraverso la sinergia tra innovazione algoritmica e accelerazione hardware.