How smoothing the affinity matrix affects neighborhood preservation in t-SNE

Sintesi Tecnica: Come l'addolcimento della matrice di affinità influenza la preservazione dei vicini in t-SNE

Definizione del problema
L'embedding t-Distributed Stochastic Neighbor Embedding (t-SNE) è una tecnica di riduzione della dimensionalità ampiamente utilizzata, nota per la sua capacità di preservare le strutture locali dei vicini. Tuttavia, nonostante la sua popolarità, gli embedding t-SNE mostrano spesso punteggi di preservazione assoluta dei vicini bassi, ed gli errori sono frequentemente distribuiti in modo non uniforme. Mentre molta ricerca si è concentrata sul miglioramento della preservazione della struttura globale di t-SNE o sull'ottimizzazione della procedura di ottimizzazione (ad esempio, inizializzazione, tassi di apprendimento), c'è stata un'indagine limitata sul fatto se la preservazione della struttura locale di t-SNE possa essere migliorata modificando la matrice di affinità ad alta dimensione stessa.

Gli autori osservano che, nel t-SNE standard, le distribuzioni di probabilità condizionata (righe di affinità) sono spesso molto "acute" (sharp), il che significa che pochi vicini prossimi dominano la massa di probabilità. Inoltre, l'acutezza di queste distribuzioni varia tra i diversi punti dati. Il documento investiga come l' "acutezza" di queste distribuzioni di affinità influenzi la preservazione dei vicini a diverse scale e se la modifica di questa acutezza possa produrre embedding migliori rispetto al t-SNE standard o ad altri metodi multiscala.

Metodologia
Lo studio introduce una perturbazione controllata alla costruzione dell'affinità standard di t-SNE: una trasformazione di potenza riga per riga applicata alle probabilità condizionate $p_{j|i}$.

1. La Trasformazione: Per un dato punto $i$, le probabilità condizionate vengono trasformate utilizzando un parametro $\gamma \geq 0$:
   $$\tilde{p}_{j|i} = \frac{p_{j|i}^\gamma}{\sum_{m \neq i} p_{m|i}^\gamma}$$

   • $\gamma = 1$: Recupera il t-SNE standard.
   • $\gamma < 1$ (Smoothing/Addolcimento): Riduce le probabilità elevate rispetto a quelle minori, ridistribuendo la massa verso i vicini con probabilità inferiore.
   • $\gamma > 1$ (Sharpening/Affilamento): Concentra ulteriormente la massa sulle probabilità più grandi.
   • $\gamma = 0$: Risulta in una distribuzione uniforme sui vicini (scartando l'ordine di rango).

2. Caratterizzazione Teorica:

   • Gli autori dimostrano che questa trasformazione di potenza è matematicamente equivalente alla riscalatura della larghezza di banda Gaussiana ($\sigma_i$) del kernel originale. Nello specifico, la nuova larghezza di banda effettiva diventa $\tilde{\sigma}_i = \sigma_i / \sqrt{\gamma}$.
   • Fondamentalmente, a differenza del cambiamento del parametro di perplexity globale $\rho$ (che forza ogni punto ad avere lo stesso numero effettivo di vicini), l'applicazione di un $\gamma$ fisso risulta in perplessità effettive dipendenti dal punto. La perplessità effettiva varia in base alla forma della distribuzione originale per ogni specifico punto.

3. Configurazione Sperimentale:

   • Il metodo è stato implementato all'interno di openTSNE ed è stato valutato su MNIST, UCI Adult e dataset Mouse Cortex.
   • La metrica principale di valutazione è stata la Sovrapposzione dei Vicini a $k$ (NO@k), che misura la frazione di vicini $k$-più prossimi ad alta dimensione preservati nell'embedding.
   • Sono stati effettuati confronti con il t-SNE standard, la variazione della perplexity globale, e diverse costruzioni di affinità (Multiscale, Fixed Sigma, Uniform, e tt-SNE).

Risultati Chiave
Gli esperimenti rivelano un chiaro compromesso dipendente dalla scala governato da $\gamma$:

• Affilamento ($\gamma > 1$): Migliora la preservazione dei vicini estremamente prossimi (piccolo $k$). Tuttavia, le prestazioni degradano rapidamente all'aumentare di $k$.
• Addolcimento ($\gamma < 1$): Migliora la preservazione di ampi vicinati locali (range di $k$ intermedio) e della struttura globale.
  • Nello specifico, l'addolcimento con $\gamma \approx 0.7$ ha superato il t-SNE standard e i metodi multiscala nel range "mid-local" ($k \approx 25–90$).
  • L'addolcimento ha anche migliorato la preservazione della struttura globale (misurata tramite la correlazione di rango di Spearman delle distanze), particolarmente ad alte perplexity.
• Confronto con la sintonizzazione della Perplexity Globale: Semplicemente aumentare la perplexity globale $\rho$ nel t-SNE standard non replica i benefici dell'addolcimento. L'addolcimento crea una distribuzione eterogenea di dimensioni di vicinato effettive tra i punti, mentre aumentare $\rho$ sposta uniformemente la scala per tutti i punti. Di conseguenza, il t-SNE addolcito ha ottenuto punteggi NO@k più elevati a specifici valori di $k$ intermedi rispetto al t-SNE standard con perplexity uguali o superiori.
• Confronto con Altri Metodi: Nel range mid-local, la variante addolcita ($\gamma=0.7$) ha superato il Multiscale Mixture e i metodi Multiscale, che incorporano molteplici scale di larghezza di banda. Le varianti affilate ($\gamma=1.5$) hanno dominato a piccoli $k$, mentre le distribuzioni uniformi ($\gamma=0$) hanno dominato a grandi $k$.

Significatività e Rivendicazioni
Il documento sostiene che l'acutezza dell'affinità sia un asse di comportamento di t-SNE significativo e precedentemente poco esplorato. I contributi primari sono:

1. Disaccoppiamento della Dimensione del Vicinato e della sua Distribuzione: Lo studio dimostra che il numero di vicini (controllato dalla perplexity) e la distribuzione della massa di probabilità tra di essi (controllata da $\gamma$) sono fattori distinti.
2. Sintonizzazione Leggera (Lightweight Tuning): Il parametro $\gamma$ offre ai professionisti un meccanismo semplice e leggero per spostare il focus dell'embedding:
   • Usare affinità più affilate ($\gamma > 1$) se l'obiettivo è l'alta fedeltà per i vicini più prossimi.
   • Usare affinità più dolci ($\gamma < 1$) per migliorare la preservazione di strutture locali più ampie e della topologia globale.
3. Limitazioni: Gli autori notano con modestia che, sebbene i miglioramenti siano costanti, sono modesti in termini assoluti. Lo studio si concentra su una singola misura di qualità (NO@k), e la traduzione pratica di questi miglioramenti metrici in insight di dominio specifici rimane una questione aperta. Inoltre, gli iperparametri ottimali ($\rho, \gamma$) per specifici valori di $k$ non sono stati esaustivamente ottimizzati in questo lavoro.

In conclusione, il documento sostiene che il t-SNE standard possa concentrare eccessivamente la massa di probabilità sui primi pochi vicini, limitando la sua capacità di preservare strutture locali più ampie. Addolcendo la matrice di affinità, è possibile ridistribuire questa massa verso vicini di rango intermedio, migliorando così l'affidabilità delle sottostrutture dei cluster e del layout globale senza alterare la procedura di ottimizzazione o la scalabilità computazionale.