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,[1]​ donde Laurens van der Maaten propuso la variante t-distribuida.[2]​ 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,[3]​ el procesamiento del lenguaje natural, el análisis musical,[4]​ la investigación del cáncer,[5]​ la bioinformática,[6]​ la interpretación de dominios geológicos,[7]​[8]​[9]​ y el procesamiento de señales biomédicas.[10]​

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,[11]​ 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.[12]​[13]​ 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.[14]​

Para un conjunto de datos con n elementos, t-SNE se ejecuta en tiempo O(n^2) y requiere espacio O(n^2).[15]​

Detalles

Dado un conjunto de ${\displaystyle N}$ objetos de alta dimensión ${\displaystyle \mathbf {x} _{1},\dots ,\mathbf {x} _{N}}$, t-SNE calcula primero las probabilidades ${\displaystyle p_{ij}}$ que son proporcionales a la similitud de los objetos ${\displaystyle \mathbf {x} _{i}}$ y ${\displaystyle \mathbf {x} _{j}}$ como sigue:

Para ${\displaystyle i\neq j}$ se define:

${\displaystyle p_{j\mid i}={\frac {\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{j}\rVert ^{2}/2\sigma _{i}^{2})}{\sum _{k\neq i}\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{k}\rVert ^{2}/2\sigma _{i}^{2})}}}$

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

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

Luego se define:

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

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

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

El ancho de banda de los núcleos gaussianos ${\displaystyle \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 ${\displaystyle \sigma _{i}}$ se utilizan en las partes más densas del espacio de datos.

Dado que el kernel gaussiano utiliza la distancia euclidiana ${\displaystyle \lVert x_{i}-x_{j}\rVert }$, 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 ${\displaystyle 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 ${\displaystyle d}$, que es ${\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{N}}$ (con ${\displaystyle \mathbf {y} _{i}\in \mathbb {R} ^{d}}$ y ${\displaystyle d}$ normalmente elegido como 2 o 3) que refleje las similitudes ${\displaystyle p_{ij}}$ lo mejor posible. Para ello, mide las similitudes ${\displaystyle q_{ij}}$ entre dos puntos del mapa ${\displaystyle \mathbf {y} _{i}}$ y ${\displaystyle \mathbf {y} _{j}}$ utilizando un enfoque muy similar. Específicamente, para ${\displaystyle i\neq j}$, ${\displaystyle q_{ij}}$ se define como:

${\displaystyle q_{ij}={\frac {(1+\lVert \mathbf {y} _{i}-\mathbf {y} _{j}\rVert ^{2})^{-1}}{\sum _{k}\sum _{l\neq k}(1+\lVert \mathbf {y} _{k}-\mathbf {y} _{l}\rVert ^{2})^{-1}}}}$

Y se establece ${\displaystyle 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 ${\displaystyle \mathbf {y} _{i}}$ en el mapa se determina minimizando la divergencia (no simétrica) de Kullback-Leibler de la distribución ${\displaystyle P}$ de la distribución ${\displaystyle Q}$, es decir:

${\displaystyle \mathrm {KL} \left(P\parallel Q\right)=\sum _{i\neq j}p_{ij}\log {\frac {p_{ij}}{q_{ij}}}}$

La minimización de la divergencia de Kullback-Leibler con respecto al punto ${\displaystyle \mathbf {y} _{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

Referencias

1. Hinton, Geoffrey; Roweis, Sam (2002). «Stochastic neighbor embedding». Neural Information Processing Systems. 
2. van der Maaten, L.J.P.; Hinton, G.E. (2008). «"Visualizing Data Using t-SNE"». Journal of Machine Learning Research. 
3. Gashi, I.; Stankovic, V.; Leita, C.; Thonnard, O. (2009). «"An Experimental Study of Diversity with Off-the-shelf AntiVirus Engines"». Proceedings of the IEEE International Symposium on Network Computing and Applications. 
4. Hamel, P.; Eck, D. (2010). «"Learning Features from Music Audio with Deep Belief Networks"». Proceedings of the International Society for Music Information Retrieval Conference. 
5. Jamieson, A.R.; Giger, M.L.; Drukker, K.; Lui, H.; Yuan, Y.; Bhooshan, N. (2010). «"Exploring Nonlinear Feature Space Dimension Reduction and Data Representation in Breast CADx with Laplacian Eigenmaps and t-SNE"». Medical Physics. PMID 20175497. doi:10.1118/1.3267037. 
6. Wallach, Izhar; Lilien, Ryan (19 de enero de 2009). «The protein–small-molecule database, a non-redundant structural resource for the analysis of protein-ligand binding». Bioinformatics 25 (5): 615-620. ISSN 1367-4811. doi:10.1093/bioinformatics/btp035. Consultado el 2 de mayo de 2024. 
7. Balamurali, Mehala; Silversides, Katherine L.; Melkumyan, Arman (2019). «"A comparison of t-SNE, SOM and SPADE for identifying material type domains in geological data"». Computers & Geosciences. ISSN 0098-3004. doi:10.1016/j.cageo.2019.01.011. 
8. Balamurali, Mehala; Melkumyan, Arman (2016). «t-SNE Based Visualisation and Clustering of Geological Domain». En Hirose, Akira, ed. Neural Information Processing (en inglés) (Springer International Publishing): 565-572. ISBN 978-3-319-46681-1. doi:10.1007/978-3-319-46681-1_67. Consultado el 2 de mayo de 2024. 
9. Leung, Raymond; Balamurali, Mehala; Melkumyan, Arman (1 de enero de 2021). «Sample Truncation Strategies for Outlier Removal in Geochemical Data: The MCD Robust Distance Approach Versus t-SNE Ensemble Clustering». Mathematical Geosciences (en inglés) 53 (1): 105-130. ISSN 1874-8953. doi:10.1007/s11004-019-09839-z. Consultado el 2 de mayo de 2024. 
10. Birjandtalab, J.; Pouyan, M. B.; Nourani, M. (2016). «"Nonlinear dimension reduction for EEG-based epileptic seizure detection"». 2016 IEEE-EMBS International Conference on Biomedical and Health Informatics (BHI). ISBN 978-1-5090-2455-1. doi:10.1109/BHI.2016.7455968. 
11. «Clustering on the output of t-SNE». Cross Validated (en inglés). Consultado el 2 de mayo de 2024. 
12. Pezzotti, Nicola; Lelieveldt, Boudewijn P. F.; Maaten, Laurens van der; Hollt, Thomas; Eisemann, Elmar; Vilanova, Anna (2017). «"Approximated and User Steerable tSNE for Progressive Visual Analytics".». IEEE Transactions on Visualization and Computer Graphics. PMID 28113434. doi:10.1109/tvcg.2016.2570755. 
13. Wattenberg, Martin; Viégas, Fernanda; Johnson, Ian (13 de octubre de 2016). «How to Use t-SNE Effectively». Distill (en inglés) 1 (10): e2. ISSN 2476-0757. doi:10.23915/distill.00002. Consultado el 2 de mayo de 2024. 
14. Linderman, George C.; Steinerberger, Stefan (2017). "Clustering with t-SNE, provably". 
15. Pezzotti, Nicola (2023). "Approximated and User Steerable tSNE for Progressive Visual Analytics". 

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