When One Point Is Not Enough: Addressing Ambiguous Instances in Dimensionality Reduction by Splitting

Riepilogo Tecnico: Gestione delle Istanze Ambigue nella Riduzione della Dimensionalità mediante Divisione

Definizione del Problema
La Riduzione della Dimensionalità (DR) è uno strumento fondamentale per la visualizzazione di dati ad alta dimensionalità, e tuttavia è intrinsecamente un processo con perdita di informazioni. Sebbene la letteratura esistente abbia catalogato varie distorsioni, come lo strappo del manifold, questo articolo identifica una fonte precedentemente trascurata di artefatti visivi: le istanze ambigue. Si tratta di punti dati altamente simili a più vicinati, mutualmente dissimili, nello spazio ad alta dimensionalità.

I metodi DR standard mappano ogni istanza di dati in un singolo punto nello spazio visivo. Di conseguenza, un'istanza ambigua non può rappresentare fedelmente la propria appartenenza a più vicinati distinti simultaneamente. È costretta in una singola posizione, risultando in un embedding parziale del vicinato. In questo stato, l'istanza appare appartenere a un solo vicinato (o a nessuno), oscurando la sua vera relazione con altri gruppi dissimili. Questo artefatto è particolarmente problematico per le analisi a livello di istanza, come l'Intelligenza Artificiale Spiegabile (XAI) o la biologia delle singole cellule, dove la comprensione della struttura precisa del vicinato è critica. Le metriche esistenti, come affidabilità e continuità, non riescono a distinguere l'embedding parziale del vicinato da altre distorsioni perché operano sull'embedding finale senza accesso all'ambiguità dei dati sottostante.

Metodologia
Gli autori propongono un approccio basato su grafi per identificare e risolvere queste ambiguità "dividendo" le istanze ambigue in più punti, ciascuno posizionato all'interno del proprio rispettivo vicinato. La metodologia segue il framework DR in due fasi (relazione e mappatura) introdotto da Paulovich et al.:

1. Costruzione e Sparsificazione del Grafo:

   • Le relazioni ad alta dimensionalità sono modellate come un grafo pesato non diretto $G$.
   • Per esporre strutture di vicinato significative ed eliminare bordi ridondanti causati da una prossimità accidentale, gli autori applicano la sparsificazione spettrale utilizzando l'algoritmo di Spielman-Srivastava. Ciò produce un grafo ridotto $\bar{G}$ che preserva le proprietà strutturali e algebriche dell'originale, rimuovendo al contempo le connessioni deboli.

2. Identificazione delle Istanze Ambigue:

   • L'ambiguità è definita topologicamente. Gli autori adattano il concetto di Punti di Articolazione Locali (LAP). Un vertice è considerato un LAP se la sua rimozione aumenta il numero di componenti connesse all'interno di un vicinato indotto locale di $r$ passi.
   • Un'istanza è considerata ambigua se è un LAP nel grafo sparsificato $\bar{G}$. Ciò indica che l'istanza connette vicinati disgiunti che altrimenti sarebbero separati.
   • Il Lemma 3.1 è utilizzato per ottimizzare il calcolo: se un vertice non è un LAP a un certo raggio $r$, non può essere un LAP a nessun raggio più grande $r' > r$.

3. Divisione dei Vertici e Regole Decisionali:

   • Una volta identificato un vertice ambiguo $v_i$, questo viene diviso in $K$ copie, dove $K$ corrisponde al numero di componenti connesse rimanenti dopo la rimozione di $v_i$ dal suo vicinato locale.
   • Regole Decisionali: Non tutte le divisioni potenziali vengono eseguite. L'approccio filtra:
     • Connessioni LAP-LAP: Se un bordo collega due vicinati e entrambi gli estremi sono LAP, la divisione viene soppressa per evitare di creare isolamento artificiale.
     • Connessioni deboli: Una soglia definita dall'utente $\tau_w$ (rapporto tra la forza della connessione e la componente più forte) filtra le divisioni in cui la connessione a un vicinato è troppo debole per essere significativa. Ciò previene la creazione di punti visivamente isolati a causa di forze di attrazione insufficienti.

4. Mappatura e Visualizzazione:

   • Il grafo modificato, contenente i vertici divisi, viene proiettato nello spazio visivo utilizzando tecniche DR locali standard (ad esempio, UMAP o ForceAtlas2).
   • Codifica Visiva: Le istanze divise vengono rese come marcatori distinti (ad esempio, croci) collegati da linee tratteggiate alla loro posizione originale o tra loro, consentendo agli analisti di tracciare le multiple appartenenze al vicinato di un singolo punto dati.

Contributi Chiave

• Definizione dell'Embedding Parziale del Vicinato: L'articolo introduce e definisce formalmente questo specifico artefatto derivante da istanze ambigue, distinguendolo dalle distorsioni generali della DR.
• Rilevamento basato sulla Teoria dei Grafi: Presenta un metodo per identificare le istanze ambigue utilizzando i Punti di Articolazione Locali su grafi di vicinato sparsificati.
• Meccanismo di Divisione: Gli autori propongono un approccio concreto, con complessità temporale quasi lineare, per dividere le istanze ambigue, replicandole nella proiezione per riflettere le multiple appartenenze al vicinato.
• Validazione Empirica: L'approccio è dimostrato su dataset diversificati (SVHN, MNIST, corpora testuali e sequenziamento RNA di singole cellule), mostrando che rivela appartenenze al vicinato nascoste non visibili nelle proiezioni standard.

Risultati

• Insight Qualitativi: Nel dataset SVHN, una cifra '1' mal classificata (predetta come '7') era mostrata in UMAP standard come appartenente esclusivamente al vicinato '7'. L'approccio proposto ha diviso l'istanza, rivelando la sua simultanea somiglianza con il vicinato '1', spiegando così l'ambiguità dell'errore del classificatore. Analogamente, nei dati testuali, un articolo su "Modelli assistiti da ILP per la tossicologia" è risultato appartenere sia al cluster ILP che a quello del Ragionamento Basato su Casi (CBR), una dualità oscurata nelle proiezioni standard.
• Analisi Quantitativa:
  • Impatto della Sparsificazione: Esperimenti che misuravano i vicini più prossimi preservati ($k$NN) hanno mostrato che la sparsificazione spettrale mantiene strutture di vicinato locali comparabili al grafo originale (rapporti vicini a 1 per la maggior parte dei dataset), sebbene sia stata osservata una certa varianza nei dati di singole cellule ad alta dimensionalità intrinseca.
  • Limiti delle Metriche: Le metriche standard (affidabilità e continuità) si sono rivelate inefficaci nell'identificare le istanze ambigue, poiché questi punti sono distribuiti in modo simile ai punti non ambigui attraverso le distribuzioni delle metriche.
  • Sensibilità ai Parametri: Aumentare il numero di vicini nel grafo iniziale ha generalmente ridotto il numero di divisioni rilevate, poiché una connettività aumentata collega vicinati che altrimenti apparirebbero disgiunti.

Significato e Affermazioni
L'articolo sostiene che riconoscere l'ambiguità è essenziale per interpretare strutture locali fini nella DR. Gli autori affermano che non tenere conto delle istanze ambigue può portare a interpretazioni incomplete o errate, specialmente in domini come XAI e biologia dove il contesto a livello di istanza è vitale. Dividendo queste istanze, il metodo fornisce una rappresentazione più fedele della topologia ad alta dimensionalità dei dati, rivelando "appartenenze al vicinato precedentemente nascoste". Il lavoro suggerisce che le attuali metriche di qualità della DR sono insufficienti per questo specifico tipo di artefatto e che i futuri framework di valutazione devono tenere conto dell'ambiguità guidata dai dati piuttosto che solo dell'instabilità indotta dalla mappatura.