Ver el código de «Incrustación de vecinos estocásticos distribuidos en t (t-SNE)»

[[Archivo:T-SNE visualisation of word embeddings generated using 19th century literature.png|miniaturadeimagen|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ística|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]],<ref>{{Cita publicación|url=https://cs.nyu.edu/~roweis/papers/sne_final.pdf|título=Stochastic neighbor embedding|apellidos=Hinton, Geoffrey; Roweis, Sam|fecha=2002|publicación=Neural Information Processing Systems}}</ref> donde Laurens van der Maaten propuso la [[Distribución t de Student|variante t-distribuida]].<ref>{{Cita publicación|url=http://jmlr.org/papers/volume9/vandermaaten08a/vandermaaten08a.pdf|título="Visualizing Data Using t-SNE"|apellidos=van der Maaten, L.J.P.; Hinton, G.E.|fecha=2008|publicación=Journal of Machine Learning Research.}}</ref> Se trata de una técnica no lineal de [[Reducción de dimensionalidad|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.
[[Archivo:T-SNE Embedding of MNIST.png|miniaturadeimagen|Incrustaciones T-SNE del conjunto de datos [[Base de datos MNIST|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 [[Euclidiano|euclidiana]] entre objetos como base de su métrica de similitud, ésta puede modificarse según convenga. Una [[Variedad de Riemann|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]],<ref>{{Cita publicación|título="An Experimental Study of Diversity with Off-the-shelf AntiVirus Engines"|apellidos=Gashi, I.; Stankovic, V.; Leita, C.; Thonnard, O.|fecha=2009|publicación=Proceedings of the IEEE International Symposium on Network Computing and Applications}}</ref> el [[procesamiento del lenguaje natural]], el [[análisis musical]],<ref>{{Cita publicación|título="Learning Features from Music Audio with Deep Belief Networks"|apellidos=Hamel, P.; Eck, D.|fecha=2010|publicación=Proceedings of the International Society for Music Information Retrieval Conference}}</ref> la investigación del [[cáncer]],<ref>{{Cita publicación|url=https://www.ncbi.nlm.nih.gov/pmc/articles/PMC2807447|título="Exploring Nonlinear Feature Space Dimension Reduction and Data Representation in Breast CADx with Laplacian Eigenmaps and t-SNE"|apellidos=Jamieson, A.R.; Giger, M.L.; Drukker, K.; Lui, H.; Yuan, Y.; Bhooshan, N.|fecha=2010|publicación=Medical Physics|doi=10.1118/1.3267037|pmid=20175497}}</ref> la [[bioinformática]],<ref>{{Cita publicación|url=https://doi.org/10.1093/bioinformatics/btp035|título=The protein–small-molecule database, a non-redundant structural resource for the analysis of protein-ligand binding|apellidos=Wallach|nombre=Izhar|apellidos2=Lilien|nombre2=Ryan|fecha=2009-01-19|publicación=Bioinformatics|volumen=25|número=5|páginas=615–620|fechaacceso=2024-05-02|issn=1367-4811|doi=10.1093/bioinformatics/btp035}}</ref> la interpretación de dominios geológicos,<ref>{{Cita publicación|url=https://www.sciencedirect.com/science/article/pii/S0098300418306010|título="A comparison of t-SNE, SOM and SPADE for identifying material type domains in geological data"|apellidos=Balamurali, Mehala; Silversides, Katherine L.; Melkumyan, Arman|fecha=2019|publicación=Computers & Geosciences|issn=0098-3004|doi=10.1016/j.cageo.2019.01.011}}</ref><ref>{{Cita publicación|url=https://link.springer.com/chapter/10.1007/978-3-319-46681-1_67|título=t-SNE Based Visualisation and Clustering of Geological Domain|apellidos=Balamurali|nombre=Mehala|apellidos2=Melkumyan|nombre2=Arman|fecha=2016|publicación=Neural Information Processing|editorial=Springer International Publishing|páginas=565–572|fechaacceso=2024-05-02|apellidos-editor=Hirose|nombre-editor=Akira|idioma=en|doi=10.1007/978-3-319-46681-1_67|isbn=978-3-319-46681-1}}</ref><ref>{{Cita publicación|url=https://doi.org/10.1007/s11004-019-09839-z|título=Sample Truncation Strategies for Outlier Removal in Geochemical Data: The MCD Robust Distance Approach Versus t-SNE Ensemble Clustering|apellidos=Leung|nombre=Raymond|apellidos2=Balamurali|nombre2=Mehala|fecha=2021-01-01|publicación=Mathematical Geosciences|volumen=53|número=1|páginas=105–130|fechaacceso=2024-05-02|idioma=en|issn=1874-8953|doi=10.1007/s11004-019-09839-z|apellidos3=Melkumyan|nombre3=Arman}}</ref> y el procesamiento de señales biomédicas.<ref>{{Cita publicación|título="Nonlinear dimension reduction for EEG-based epileptic seizure detection"|apellidos=Birjandtalab, J.; Pouyan, M. B.; Nourani, M.|fecha=2016|publicación=2016 IEEE-EMBS International Conference on Biomedical and Health Informatics (BHI)|doi=10.1109/BHI.2016.7455968|isbn=978-1-5090-2455-1}}</ref>

Aunque los gráficos t-SNE a menudo parecen mostrar ''[[Clúster (sistema de archivos)|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,<ref>{{Cita web|url=https://stats.stackexchange.com/a/264647|título=Clustering on the output of t-SNE|fechaacceso=2024-05-02|sitioweb=Cross Validated|idioma=en}}</ref> 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.<ref>{{Cita publicación|título="Approximated and User Steerable tSNE for Progressive Visual Analytics".|apellidos=Pezzotti, Nicola; Lelieveldt, Boudewijn P. F.; Maaten, Laurens van der; Hollt, Thomas; Eisemann, Elmar; Vilanova, Anna|fecha=2017|publicación=IEEE Transactions on Visualization and Computer Graphics|doi=10.1109/tvcg.2016.2570755|pmid=28113434}}</ref><ref>{{Cita publicación|url=http://distill.pub/2016/misread-tsne|título=How to Use t-SNE Effectively|apellidos=Wattenberg|nombre=Martin|apellidos2=Viégas|nombre2=Fernanda|fecha=2016-10-13|publicación=Distill|volumen=1|número=10|páginas=e2|fechaacceso=2024-05-02|idioma=en|issn=2476-0757|doi=10.23915/distill.00002|apellidos3=Johnson|nombre3=Ian}}</ref> 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 [[Agrupamiento espectral|agrupación espectral]].<ref>{{Cita publicación|título="Clustering with t-SNE, provably"|apellidos=Linderman, George C.; Steinerberger, Stefan|fecha=2017|publicación=}}</ref>

Para un conjunto de datos con ''n'' elementos, t-SNE se ejecuta en tiempo {{Math|O(''n''<sup>2</sup>)}} y requiere espacio {{Math|O(''n''<sup>2</sup>)}}.<ref>{{Cita publicación|url=https://arxiv.org/pdf/1512.01655.pdf|título="Approximated and User Steerable tSNE for Progressive Visual Analytics"|apellidos=Pezzotti, Nicola|fecha=2023|publicación=}}</ref>

== Detalles ==
Dado un conjunto de <math>N</math> objetos de alta dimensión <math>\mathbf{x}_1, \dots, \mathbf{x}_N</math>,  t-SNE calcula primero las probabilidades <math>p_{ij}</math> que son proporcionales a la similitud de los objetos <math>\mathbf{x}_i</math> y <math>\mathbf{x}_j</math> como sigue:

Para <math>i \neq j</math> se define:

<math>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)}</math>

Y se establece <math>p_{i\mid i} = 0</math>. Obsérvese que el denominador anterior garantiza <math>\sum_j p_{j\mid i} = 1</math> para todas las <math>i</math>.

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

Luego se define:

<math>p_{ij} = \frac{p_{j\mid i} + p_{i\mid j}}{2N}</math>

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

También se debe tener en cuenta que <math>p_{ii} = 0 </math> y <math>\sum_{i, j} p_{ij} = 1</math>.

El ancho de banda de los [[núcleos gaussianos]] <math>\sigma_i</math> 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 <math>\sigma_i</math> se utilizan en las partes más densas del espacio de datos.

Dado que el [[Kernel (álgebra)|kernel]] gaussiano utiliza la [[distancia euclidiana]]  <math>\lVert x_i-x_j \rVert</math>, se ve afectada por la [[Maldición de la dimensión|maldición de la dimensionalidad]], y en datos de alta dimensionalidad cuando las distancias pierden la capacidad de discriminar, entonces <math>p_{ij}</math> 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 <math>d</math>, que es <math>\mathbf{y}_1, \dots, \mathbf{y}_N</math> (con <math>\mathbf{y}_i \in \mathbb{R}^d</math> y <math>d</math> normalmente elegido como 2 o 3) que refleje las similitudes <math>p_{ij}</math> lo mejor posible. Para ello, mide las similitudes <math>q_{ij}</math> entre dos puntos del mapa <math>\mathbf{y}_i</math> y <math>\mathbf{y}_j</math> utilizando un enfoque muy similar. Específicamente, para <math>i \neq j</math>, <math>q_{ij}</math>  se define como:

<math>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}}</math>

Y se establece <math> q_{ii} = 0 </math>. 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 <math>\mathbf{y}_i</math> en el mapa se determina minimizando la [[Divergencia de Kullback-Leibler|divergencia (no simétrica) de Kullback-Leibler]] de la distribución <math>P</math> de la distribución <math>Q</math>, es decir:

<math>\mathrm{KL}\left(P \parallel Q\right) = \sum_{i \neq j} p_{ij} \log \frac{p_{ij}}{q_{ij}}</math>

La minimización de la divergencia de Kullback-Leibler con respecto al punto <math>\mathbf{y}_i</math> se realiza mediante el [[Descenso del gradiente|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 (lenguaje de programación)|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 ==
{{listaref}}

== Enlaces externos ==
* [https://www.youtube.com/watch?v=RJVL80Gg3lA Visualizing Data Using t-SNE], Google Tech Talk about t-SNE
* [https://lvdmaaten.github.io/tsne/ Implementations of t-SNE in various languages], A link collection maintained by Laurens van der Maaten
{{Control de autoridades}}
[[Categoría:Aprendizaje automático]]
[[Categoría:Algoritmos]]
[[Categoría:Dimensión]]
[[Categoría:Software]]