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

Resumen Técnico: Cómo el suavizado de la matriz de afinidad afecta la preservación de vecindades en t-SNE

Planteamiento del problema
El t-SNE (t-Distributed Stochastic Neighbor Embedding) es una técnica de reducción de dimensionalidad ampliamente utilizada, conocida por preservar las estructuras de vecindad local. Sin embargo, a pesar de su popularidad, los embeddings de t-SNE suelen exhibir puntuaciones de preservación de vecindad absoluta bajas, y los errores se distribuyen frecuentemente de forma desigual. Si bien mucha investigación se ha centrado en mejorar la preservación de la estructura global de t-SNE o en optimizar el procedimiento de optimización (por ejemplo, la inicialización o las tasas de aprendizaje), se ha investigado de forma limitada si la preservación de la estructura local de t-SNE puede mejorarse mediante la modificación de la propia matriz de afinidad de alta dimensión.

Los autores observan que, en el t-SNE estándar, las distribuciones de probabilidad condicional (filas de afinidad) suelen ser muy "afiladas" (sharp), lo que significa que unos pocos vecinos cercanos dominan la masa de probabilidad. Además, la agudeza de estas distribuciones varía entre los puntos de datos. El artículo investiga cómo la "agudeza" de estas distribuciones de afinidad influye en la preservación de la vecindad a diferentes escalas y si la modificación de esta agudeza puede producir mejores embeddings que el t-SNE estándar o métodos multiescala alternativos.

Metodología
El estudio introduce una perturbación controlada a la construcción de la afinidad estándar de t-SNE: una transformación de potencia por fila aplicada a las probabilidades condicionales $p_{j|i}$.

1. La transformación: Para un punto dado $i$, las probabilidades condicionales se transforman utilizando un parámetro $\gamma \geq 0$:
   $$\tilde{p}_{j|i} = \frac{p_{j|i}^\gamma}{\sum_{m \neq i} p_{m|i}^\gamma}$$

   • $\gamma = 1$: Recupera el t-SNE estándar.
   • $\gamma < 1$ (Suavizado/Smoothing): Reduce las probabilidades grandes en relación con las más pequeñas, redistribuyendo la masa hacia los vecinos de menor probabilidad.
   • $\gamma > 1$ (Agudización/Sharpening): Concentra aún más la masa en las probabilidades mayores.
   • $\gamma = 0$: Resulta en una distribución uniforme sobre los vecinos (descartando el orden de rango).

2. Caracterización teórica:

   • Los autores demuestran que esta transformación de potencia es matemáticamente equivalente a reescalar el ancho de banda Gaussiano ($\sigma_i$) del kernel original. Específicamente, el nuevo ancho de banda efectivo es $\tilde{\sigma}_i = \sigma_i / \sqrt{\gamma}$.
   • Crucialmente, a diferencia del cambio de la perplejidad global $\rho$ (que obliga a cada punto a tener el mismo número efectivo de vecinos), la aplicación de un $\gamma$ fijo resulta en perplejidades efectivas dependientes del punto. La perplejidad efectiva varía según la forma de la distribución original para cada punto específico.

3. Configuración experimental:

   • El método se implementó dentro de openTSNE y se evaluó en los conjuntos de datos MNIST, UCI Adult y Mouse Cortex.
   • La métrica principal de evaluación fue el Solapamiento de Vecindad en $k$ (NO@k), que mide la fracción de los $k$-vecinos más cercanos de alta dimensión preservados en el embedding.
   • Se realizaron comparaciones contra el t-SNE estándar, variando la perplejidad global, y contra otras construcciones de afinidad (Multiscale, Fixed Sigma, Uniform y tt-SNE).

Resultados clave
Los experimentos revelan un claro compromiso (trade-off) dependiente de la escala gobernado por $\gamma$:

• Agudización ($\gamma > 1$): Mejora la preservación de los vecinos más cercanos (pequeña $k$). Sin embargo, el rendimiento se degrada rápidamente a medida que $k$ aumenta.
• Suavizado ($\gamma < 1$): Mejora la preservación de vecindades locales más amplias (rango medio de $k$) y la estructura global.
  • Específicamente, el suavizado con $\gamma \approx 0.7$ superó al t-SNE estándar y a los métodos multiescala en el rango "medio-local" ($k \approx 25–90$).
  • El suavizado también mejoró la preservación de la estructura global (medida por la correlación de rango de Spearman de las distancias), particularmente a perplejidades altas.
• Comparación con el ajuste de la perplejidad global: Simplemente aumentar la perplejidad global $\rho$ en el t-SNE estándar no replica los beneficios del suavizado. El suavizado crea una distribución heterogénea de tamaños de vecindad efectivos entre los puntos, mientras que aumentar $\rho$ desplaza uniformemente la escala para todos los puntos. En consecuencia, el t-SNE suavizado logró puntuaciones de NO@k más altas en valores específicos de $k$ intermedios que el t-SNE estándar con perplejidades iguales o superiores.
• Comparación con otros métodos: En el rango medio-local, la variante suavizada ($\gamma=0.7$) superó a Multiscale Mixture y Multiscale, que incorporan múltiples escalas de ancho de banda. Las variantes agudizadas ($\gamma=1.5$) dominaron en $k$ muy pequeños, mientras que las distribuciones uniformes ($\gamma=0$) dominaron en $k$ muy grandes.

Significado y afirmaciones
El artículo afirma que la agudeza de la afinidad es un eje de comportamiento de t-SNE significativo y previamente poco explorado. Las contribuciones principales son:

1. Desacoplamiento del tamaño y la distribución de la vecindad: El estudio demuestra que el número de vecinos (controlado por la perplejidad) y la distribución de la masa de probabilidad entre ellos (controlada por $\gamma$) son factores distintos.
2. Ajuste ligero (Lightweight Tuning): El parámetro $\gamma$ ofrece a los profesionales un mecanismo sencillo y ligero para desplazar el enfoque del embedding:
   • Use afinidades más agudas ($\gamma > 1$) si el objetivo es una alta fidelidad para los vecinos más cercanos.
   • Use afinidades más suaves ($\gamma < 1$) para mejorar la preservación de estructuras locales más amplias y la topología global.
3. Limitaciones: Los autores señalan modestamente que, aunque las mejoras son consistentes, son modestas en términos absolutos. El estudio se centra en una única medida de calidad (NO@k), y la traducción práctica de estas mejoras métricas a conocimientos específicos de dominio sigue siendo una pregunta abierta. Además, los hiperparámetros óptimos ($\rho, \gamma$) para valores específicos de $k$ no fueron optimizados exhaustivamente en este trabajo.

En conclusión, el artículo argumenta que el t-SNE estándar puede concentrar la masa de probabilidad demasiado fuertemente en los primeros pocos vecinos, lo que limita su capacidad para preservar estructuras locales más amplias. Al suavizar la matriz de afinidad, se puede redistribuir esta masa hacia los vecinos de rango medio, mejorando así la fiabilidad de las subestructuras de los clústeres y el diseño global sin alterar el procedimiento de optimización ni la escalabilidad computacional.