Skeleton Regression: A Graph-Based Approach to Estimation with Manifold Structure

1. Il Problema

Il lavoro affronta il problema della regressione non parametrica su dati ad alta dimensionalità in cui le variabili esplicative (covariate) non sono distribuite uniformemente nello spazio euclideo, ma giacciono attorno a una struttura a varietà (manifold) a bassa dimensione.
Le sfide principali identificate sono:

• Maledizione della dimensionalità: I metodi di regressione tradizionali (come la regressione a kernel o k-NN nello spazio euclideo) soffrono quando la dimensione dello spazio di input ($d$) è molto più grande della dimensione intrinseca del manifold.
• Strutture complesse: I dati possono provenire dall'unione di più varietà disgiunte o componenti, con strutture geometriche irregolari.
• Rumore e osservazioni corrotte: La presenza di rumore additivo e osservazioni fuori distribuzione (outliers) può degradare le prestazioni dei metodi basati su varietà esistenti.
• Limitazioni dei metodi attuali: Approcci come la regressione sui polinomi locali o gli spline di ordine superiore richiedono definizioni di derivata e orientamento che sono spesso mal definite o complesse su grafi generici o nodi con grado elevato.

2. Metodologia: Il Framework "Skeleton Regression"

Gli autori propongono un nuovo framework in due fasi che combina la costruzione di un grafo (chiamato scheletro) con tecniche di regressione non parametrica.

Fase 1: Costruzione dello Scheletro (Skeleton Construction)

Invece di utilizzare ogni punto campione come vertice di un grafo (il che porta a grafi troppo grandi), lo scheletro è una rappresentazione compatta dello spazio delle covariate:

• Nodi (Knots): Vengono identificati come centri di cluster ottenuti tramite algoritmo $k$-means con un numero elevato di cluster ($k \approx \sqrt{n}$). Questi nodi rappresentano le regioni di interesse ad alta densità.
• Bordi (Edges): I nodi vengono collegati se le loro celle di Voronoi sono adiacenti o se esiste una regione di dati significativa tra di loro. La connessione è determinata esaminando la regione dei 2-Nearest Neighbors (2-NN) delle coppie di nodi.
• Ponderazione e Segmentazione: Vengono calcolate delle pesature basate sulla Densità di Voronoi per misurare la similarità tra i nodi. Questo permette di potare i bordi irrilevanti o di segmentare lo scheletro in componenti disgiunte se i dati provengono da varietà separate.
• Proiezione dei Dati: Ogni covariata originale $\mathbf{x}_i$ viene proiettata sullo scheletro $\mathcal{S}$. Se il punto è vicino a un bordo tra due nodi, viene proiettato ortogonalmente su quel segmento; altrimenti, viene proiettato sul nodo più vicino.

Fase 2: Definizione della Distanza e Regressione

Una volta proiettati i dati sullo scheletro, si definisce una distanza basata sullo scheletro ($d_S$):

• La distanza tra due punti sullo stesso bordo è la distanza euclidea.
• La distanza tra punti su bordi diversi è la somma delle lunghezze dei percorsi attraverso i nodi intermedi (lunghezza del cammino più breve nel grafo).
• Questa distanza rende lo scheletro uno spazio metrico, indipendente dalla dimensione ambientale $d$.

Sulla base di questa struttura metrica, vengono applicati tre metodi di regressione non parametrica:

1. S-Kernel Regression: Una versione adattata della regressione a kernel (Nadaraya-Watson) che utilizza la distanza $d_S$ invece della distanza euclidea.
2. S-kNN (k-Nearest Neighbors): Utilizza la distanza $d_S$ per selezionare i vicini più prossimi.
3. S-Lspline (Linear Spline): Un modello di spline lineare vincolato a essere continuo sui nodi e lineare sui bordi. Il paper dimostra un teorema di rappresentazione che permette di parametrizzare l'intera funzione solo attraverso i valori ai nodi, trasformando il problema in una regressione lineare con covariate trasformate.

3. Contributi Chiave

• Indipendenza dalla Dimensione: Il metodo è progettato per essere indipendente dalla dimensione ambientale $d$, sfruttando solo la struttura intrinseca del manifold.
• Gestione di Varietà Disgiunte: A differenza di molti metodi di apprendimento di varietà che assumono un manifold connesso, lo scheletro può naturalmente rappresentare l'unione di componenti disgiunte.
• Robustezza al Rumore: L'approccio di proiezione e la costruzione dello scheletro basata sulla densità lo rendono robusto rispetto a osservazioni rumorose e corrotte.
• Garanzie Teoriche: Gli autori forniscono prove di consistenza e tassi di convergenza per la regressione a kernel su punti di bordo e nodi (sia con massa di probabilità zero che non zero).
• Limiti degli altri metodi: Il paper discute dettagliatamente perché metodi come la regressione polinomiale locale o gli spline di ordine superiore non sono direttamente applicabili agli scheletri a causa della mancanza di un orientamento ben definito e di derivate continue sui nodi.

4. Risultati Sperimentali

I risultati sono stati valutati su dati simulati e reali:

• Dati Simulati:

  • Yinyang Data (Componenti Disgiunte): Su dati composti da 5 strutture geometriche disgiunte in uno spazio 1000-dimensionale, i metodi basati sullo scheletro (S-Kernel, S-kNN, S-Lspline) hanno superato significativamente il kNN classico, la regressione Ridge/Lasso e metodi basati su kernel machine learning (Fast-KRR) e reti neurali (MLP Autoencoder).
  • Dati con Rumore: Aggiungendo rumore e osservazioni spurie, i metodi basati sullo scheletro hanno mantenuto prestazioni elevate, mentre gli altri metodi hanno fallito. In particolare, S-Kernel ha mostrato la migliore robustezza.
  • Swiss Roll (Manifold Connesso): Su un manifold connesso a 2 dimensioni in uno spazio 3D, i metodi basati sullo scheletro hanno nuovamente superato i competitor, dimostrando che la distanza geodetica approssimata dallo scheletro è efficace.
  • Dimensione dei Nodi: È stato osservato che il numero ottimale di nodi dipende dalla dimensione intrinseca del manifold (più nodi per manifold di dimensione superiore).

• Dati Reali:

  • COIL-20 (Immagini di tazze): Predizione dell'angolo di rotazione. Il metodo S-Lspline ha ottenuto le prestazioni migliori, superando il kNN, suggerendo che la struttura lineare a tratti dello scheletro è adatta a questo tipo di manifold circolare.
  • SDSS (Galassie): Predizione del redshift spettroscopico. Sebbene il kNN e Spectral Series abbiano ottenuto le migliori prestazioni di precisione, lo scheletro ha fornito una struttura chiara e interpretabile della distribuzione delle covariate, dimostrando utilità come strumento di esplorazione dei dati.

5. Significato e Conclusioni

Il framework Skeleton Regression offre un approccio innovativo per l'analisi di dati geometrici strutturati.

• Interpretabilità: Oltre a fornire previsioni, il metodo restituisce un grafo (lo scheletro) che visualizza la struttura sottostante dei dati, utile per l'analisi esplorativa.
• Efficienza Computazionale: Rispetto ai modelli di deep learning, il metodo ha un costo computazionale inferiore e non richiede un addestramento complesso.
• Versatilità: Funziona bene sia su varietà connesse che disgiunte e in presenza di rumore, colmando il divario tra l'analisi geometrica e la regressione statistica classica.

Il lavoro suggerisce direzioni future per l'estensione a complessi simpliciali (per catturare strutture di dimensione superiore) e per l'aggiornamento online dello scheletro in scenari di dati in streaming.