Incrustación de vecinos estocásticos distribuidos en t (t-SNE)

Visualización T-SNE de incrustaciones de palabras (word embedding) generadas a partir de literatura del siglo XIX

La incrustación de vecinos estocásticos distribuidos en t (t-SNE) es un método estadístico para visualizar datos de alta dimensión asignando a cada punto de datos una ubicación en un mapa bidimensional o tridimensional. Se basa en la incrustación de vecinos estocástica desarrollada originalmente por Geoffrey Hinton y Sam Roweis, donde Laurens van der Maaten propuso la variante t-distribuida. Se trata de una técnica no lineal de reducción de la dimensionalidad para incrustar datos de alta dimensión para su visualización en un espacio de baja dimensión de dos o tres dimensiones. Concretamente, modela cada objeto de alta dimensión mediante un punto bidimensional o tridimensional, de tal forma que los objetos similares se modelan mediante puntos cercanos y los objetos disímiles se modelan mediante puntos distantes con alta probabilidad.

Incrustaciones T-SNE del conjunto de datos MNIST

El algoritmo t-SNE consta de dos etapas principales. En primer lugar, t-SNE construye una distribución de probabilidad sobre pares de objetos de alta dimensión de tal forma que a los objetos similares se les asigna una probabilidad mayor, mientras que a los puntos disímiles se les asigna una probabilidad menor. En segundo lugar, t-SNE define una distribución de probabilidad similar sobre los puntos del mapa de baja dimensión y minimiza la divergencia de Kullback-Leibler (divergencia KL) entre las dos distribuciones con respecto a las ubicaciones de los puntos en el mapa. Aunque el algoritmo original utiliza la distancia euclidiana entre objetos como base de su métrica de similitud, ésta puede modificarse según convenga. Una variante riemanniana es UMAP.

La t-SNE se ha utilizado para la visualización en una amplia gama de aplicaciones, como la genómica, la investigación en seguridad informática, el procesamiento del lenguaje natural, el análisis musical, la investigación del cáncer, la bioinformática, la interpretación de dominios geológicos, y el procesamiento de señales biomédicas.

Aunque los gráficos t-SNE a menudo parecen mostrar clusters, los clústers o conglomerados visuales pueden estar fuertemente influenciados por la parametrización elegida y, por lo tanto, es necesario un buen conocimiento de los parámetros para t-SNE. Se puede demostrar que estos "conglomerados" aparecen incluso en datos no agrupados, por lo que pueden ser falsos hallazgos. Por tanto, puede ser necesaria una exploración interactiva para elegir los parámetros y validar los resultados. Se ha demostrado que t-SNE a menudo es capaz de recuperar conglomerados bien separados y, con elecciones especiales de los parámetros, se aproxima a una forma simple de agrupación espectral.

Para un conjunto de datos con n elementos, t-SNE se ejecuta en tiempo Plantilla:Math y requiere espacio Plantilla:Math.

Detalles

Dado un conjunto de $N$ objetos de alta dimensión ${𝐱}_1,\dots ,{𝐱}_N$, t-SNE calcula primero las probabilidades $p_{ij}$ que son proporcionales a la similitud de los objetos ${𝐱}_i$ y ${𝐱}_j$ como sigue:

Para $i\ne j$ se define:

$p_{j\mid i}=\frac{\exp (-\Vert {𝐱}_i-{𝐱}_j{\Vert }^2/2{\sigma }_i^2)}{\sum _{k\ne i}\exp (-\Vert {𝐱}_i-{𝐱}_k{\Vert }^2/2{\sigma }_i^2)}$

Y se establece $p_{i\mid i}=0$. Obsérvese que el denominador anterior garantiza $\sum _j{p}_{j\mid i}=1$ para todas las $i$.

Como explicaron van der Maaten y Hinton: "La similitud de los puntos de datos $x_j$ a los puntos de datos $x_i$ es la probabilidad condicional $p_{j|i}$ de que $x_i$ escoja a $x_j$ como su vecino si los vecinos se eligieran en proporción a su densidad de probabilidad bajo una gaussiana centrada en $x_i$.

Luego se define:

$p_{ij}=\frac{p_{j\mid i}+p_{i\mid j}}{2N}$

Esto es motivado debido a que $p_i$ y $p_j$ de las N muestras se estiman como 1/N, por lo que la probabilidad condicional puede escribirse como $p_{i\mid j}=N{p}_{ij}$ y $p_{j\mid i}=N{p}_{ji}$. Teniendo en cuenta que $p_{ij}=p_{ji}$ se puede obtener la fórmula anterior.

También se debe tener en cuenta que $p_{ii}=0$ y $\sum _{i,j}{p}_{ij}=1$.

El ancho de banda de los núcleos gaussianos ${\sigma }_i$ se fija de forma que la entropía de la distribución condicional sea igual a una entropía predefinida mediante el método de bisección. Como resultado, el ancho de banda se adapta a la densidad de los datos: los valores más pequeños de ${\sigma }_i$ se utilizan en las partes más densas del espacio de datos.

Dado que el kernel gaussiano utiliza la distancia euclidiana $\Vert x_i-x_j\Vert$, se ve afectada por la maldición de la dimensionalidad, y en datos de alta dimensionalidad cuando las distancias pierden la capacidad de discriminar, entonces $p_{ij}$ se vuelven demasiado similares (asintóticamente, convergerían a una constante). Para paliarlo, se ha propuesto ajustar las distancias con una transformada de potencia, basada en la dimensión intrínseca de cada punto.

t-SNE pretende aprender un mapa dimensional $d$, que es ${𝐲}_1,\dots ,{𝐲}_N$ (con ${𝐲}_i\in {ℝ}^d$ y $d$ normalmente elegido como 2 o 3) que refleje las similitudes $p_{ij}$ lo mejor posible. Para ello, mide las similitudes $q_{ij}$ entre dos puntos del mapa ${𝐲}_i$ y ${𝐲}_j$ utilizando un enfoque muy similar. Específicamente, para $i\ne j$, $q_{ij}$ se define como:

$q_{ij}=\frac{(1+\Vert {𝐲}_i-{𝐲}_j{\Vert }^2{)}^{-1}}{\sum _k\sum _{l\ne k}(1+\Vert {𝐲}_k-{𝐲}_l{\Vert }^2{)}^{-1}}$

Y se establece $q_{ii}=0$. En este caso se utiliza una distribución t de Student de colas gruesas (con un grado de libertad, que es lo mismo que una distribución de Cauchy) para medir las similitudes entre puntos de baja dimensión, con el fin de permitir que los objetos disímiles se modelen muy separados en el mapa.

La ubicación del punto ${𝐲}_i$ en el mapa se determina minimizando la divergencia (no simétrica) de Kullback-Leibler de la distribución $P$ de la distribución $Q$, es decir:

$\mathrm{K}\mathrm{L}(P\parallel Q)=\sum _{i\ne j}{p}_{ij}\log \frac{p_{ij}}{q_{ij}}$

La minimización de la divergencia de Kullback-Leibler con respecto al punto ${𝐲}_i$ se realiza mediante el descenso de gradiente. El resultado de esta optimización es un mapa que refleja las similitudes entre las entradas de alta dimensión.

Software

• El paquete R Rtsne implementa t-SNE en R.
• ELKI contiene tSNE, también con aproximación Barnes-Hut
• scikit-learn, una popular biblioteca de aprendizaje automático en Python, implementa t-SNE tanto con soluciones exactas como con la aproximación de Barnes-Hut.
• Tensorboard, el kit de visualización asociado a TensorFlow, también implementa t-SNE

Enlaces externos

• Visualizing Data Using t-SNE, Google Tech Talk about t-SNE
• Implementations of t-SNE in various languages, A link collection maintained by Laurens van der Maaten