Manifold Dimension Estimation via Local Graph Structure

Sintesi Tecnica: Stima della Dimensione della Varietà tramite Struttura Locale del Grafo

Enunciato del Problema
Stimare la dimensione intrinseca $d$ di una varietà immersa in uno spazio ambientale ad alta dimensione $\mathbb{R}^p$ è una sfida fondamentale nella riduzione della dimensionalità non lineare. Mentre molti stimatori esistenti (ad es. PCA Locale, DanCo, TwoNN) si basano sull'"assunzione di piattezza" — approssimando i vicoli locali come sottospazi lineari $d$-dimensionali — questo approccio fatica quando le varietà presentano una curvatura significativa o sono immerse in modo non lineare. Metodi recenti come la PCA Aggiustata per la Curvatura (CA-PCA) tentano di affrontare ciò correggendo esplicitamente le strutture proprie per la curvatura, ma spesso soffrono di sovrastima in spazi ambientali ad alta dimensione o di instabilità computazionale. Gli autori identificano un vuoto nei metodi capaci di modellare robustamente la curvatura locale senza affidarsi a una stima diretta instabile della curvatura o al rilevamento del gap degli autovalori.

Metodologia
Gli autori propongono un nuovo quadro che riformula la stima della dimensione della varietà come un problema di regressione sulle coordinate PCA locali. Invece di assumere la piattezza locale o stimare esplicitamente i tensori di curvatura, il metodo modella il vicolo locale di un punto $x_k$ come il grafico di una funzione liscia $g: \mathbb{R}^d \to \mathbb{R}^{p-d}$.

1. Rappresentazione del Grafo Locale: Per un punto $x_k$ e i suoi $K$-vicini più prossimi, gli autori eseguono la PCA per stabilire un sistema di coordinate locale allineato con lo spazio tangente stimato. Le prime $d$ coordinate rappresentano lo spazio tangente, mentre le rimanenti $p-d$ coordinate rappresentano lo spazio normale.
2. Formulazione della Regressione: Il quadro ipotizza che le coordinate normali possano essere espresse come una funzione delle coordinate tangenti. Poiché lo sviluppo di Taylor del primo ordine di questa funzione è zero (per definizione dello spazio tangente), gli autori utilizzano termini del secondo ordine (quadratici) per catturare la curvatura locale.
3. Sondaggio delle Dimensioni Candidate: L'algoritmo itera attraverso le dimensioni candidate $j$ (da 1 a $p-1$). Per ciascuna $j$, tratta le prime $j$ coordinate PCA come ingressi e la $(j+1)$-esima coordinata come uscita, adattando un modello di regressione quadratica.
4. Due Stimatori:
   • Incorporamento Quadratico (QE): Utilizza i Minimi Quadrati Ordinari (OLS) per adattare il modello quadratico. Valuta la bontà di adattamento utilizzando la statistica $F$ e l'$R^2$ aggiustato. La dimensione stimata è la più piccola $j$ in cui l'adattamento del modello diventa statisticamente significativo (p-value < 1%) e rimane significativo per tutte le dimensioni superiori.
   • Minimi Quadrati Totali (TLS): Utilizza i Minimi Quadrati Totali per tenere conto degli errori sia nelle variabili di ingresso che in quelle di uscita. Invece delle statistiche $F$, valuta il calo relativo nell'errore TLS totale ($\eta_j$) tra dimensioni consecutive. La dimensione stimata corrisponde al picco del calo relativo.

Contributi Chiave

• Quadro Basato sulla Regressione: Il documento introduce una prospettiva innovativa che trasforma la stima della dimensionalità in un problema di regressione ricorsivo. Ciò sostituisce la stima geometrica locale instabile (come il calcolo diretto della curvatura) con una procedura di adattamento statisticamente aggregata, offrendo maggiore robustezza alla scarsità del campionamento e al rumore.
• Modellazione Consapevole della Curvatura: Utilizzando modelli quadratici, il metodo cattura esplicitamente la curvatura della varietà senza richiedere una stima esplicita della curvatura o una correzione degli autovalori, mitigando così i problemi di sovrastima comuni nei metodi basati sulla PCA.
• Robustezza al Rumore e alla Non Linearità: Il quadro si adatta naturalmente al rumore ed è progettato per funzionare bene su varietà con incorporamenti complessi e non lineari dove le assunzioni di piattezza falliscono.
• Implementazione Pratica: Gli autori forniscono due stimatori concreti (QE e TLS) con algoritmi dettagliati, inclusi euristiche per limitare lo spazio di ricerca ($p_{max}$) in base alla dimensione del vicolo per garantire la fattibilità computazionale.

Risultati Sperimentali
Gli autori hanno valutato QE e TLS su 18 varietà sintetiche (inclusi sfere, sfere deformate e superfici gaussiane) e 6 dataset reali (ISOMAP, MNIST, ISOLET, Fashion MNIST, Frey Face, Gas Sensor Array Drift).

• Dati Sintetici: QE e TLS hanno dimostrato prestazioni competitive o superiori rispetto ai metodi all'avanguardia (PCA Locale, CA-PCA, DanCo, TwoNN, MADA, ecc.), in particolare nei regimi a piccolo campione e su varietà immerse in modo non lineare (ad es. sfere deformate). Hanno efficacemente mitigato la sovrastima osservata in CA-PCA e PCA Locale quando la dimensione ambientale $p$ supera significativamente la dimensione intrinseca $d$.
• Robustezza al Rumore: In presenza di rumore gaussiano, uniforme e di Laplace, i metodi proposti hanno mantenuto prestazioni robuste, superando molti stimatori basati sulla piattezza la cui accuratezza si è degradata significativamente.
• Dati Reali: Su dataset reali, gli stimatori hanno prodotto risultati coerenti con i range di consenso (ad es. stimando ISOMAP $\approx 3$, MNIST $\approx 8-11$). Notabilmente, hanno evitato la grave sovrastima osservata in PCA Locale e CA-PCA su dataset con alte dimensioni ambientali.
• Limitazioni Osservate: I metodi hanno mostrato prestazioni ridotte su varietà "triviali" con curvatura zero (ad es. ipersfere), dove il modello quadratico è una specificazione errata. Inoltre, TLS è limitato inferiormente da 2 a causa della sua dipendenza dai cali relativi dell'errore tra le dimensioni.

Significato e Affermazioni
Il documento afferma che, spostando il paradigma dall'approssimazione geometrica alla regressione statistica, il quadro proposto ottiene una robustezza e un'accuratezza migliorate, in particolare in regimi impegnativi che coinvolgono piccoli campioni e curvatura complessa. Gli autori affermano che i loro metodi offrono un'alternativa convincente agli stimatori esistenti che performano meglio, affrontando efficacemente i limiti sia degli approcci basati sulla piattezza che delle correzioni di curvatura basate sugli autovalori. Concludono che, sebbene la formulazione quadratica attuale sia efficace, un lavoro futuro potrebbe esplorare modelli più espressivi se verranno sviluppati strumenti diagnostici affidabili per le statistiche campionarie. Il lavoro è presentato come un passo significativo verso la risoluzione delle sfide persistenti nella stima della dimensione della varietà, sebbene gli autori rimangano modesti riguardo alla necessità di un ulteriore affinamento nei criteri di valutazione (in particolare per TLS) e nella gestione del rumore nella stima dello spazio tangente.