Incrustación vecinal estocástica distribuida en t

Técnica para reducción de dimensionalidad

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

Incorporaciones de T-SNE del conjunto de datos MNIST

La incrustación estocástica de vecinos con distribución t ( t-SNE ) es un método estadístico para visualizar datos de alta dimensión al otorgar a cada punto de datos una ubicación en un mapa bidimensional o tridimensional. Se basa en la incrustación estocástica de vecinos desarrollada originalmente por Geoffrey Hinton y Sam Roweis, ^[1] donde Laurens van der Maaten y Hinton propusieron la variante con distribución t ^{. [2]} Es una técnica de reducción de dimensionalidad no lineal para incrustar datos de alta dimensión para visualización en un espacio de baja dimensión de dos o tres dimensiones. Específicamente, modela cada objeto de alta dimensión por un punto bidimensional o tridimensional de tal manera que los objetos similares son modelados por puntos cercanos y los objetos diferentes son modelados por puntos distantes con alta probabilidad.

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 manera que a los objetos similares se les asigna una probabilidad más alta mientras que a los puntos diferentes se les asigna una probabilidad más baja. En segundo lugar, t-SNE define una distribución de probabilidad similar sobre los puntos en el 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. Si bien el algoritmo original utiliza la distancia euclidiana entre objetos como base de su métrica de similitud, esto se puede cambiar según sea necesario. Una variante de Riemann es UMAP .

La t-SNE se ha utilizado para la visualización en una amplia gama de aplicaciones, incluidas 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 del dominio geológico, ^{[7] [8] [9]} y el procesamiento de señales biomédicas. ^[10]

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

Detalles

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

Para , definir ${\displaystyle i\neq j}$

${\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 establezca . Tenga en cuenta que el denominador anterior garantiza para todos los . ${\displaystyle p_{i\mid i}=0}$ ${\displaystyle \sum _{j}p_{j\mid i}=1}$ ${\displaystyle i}$

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

Ahora defina

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

Esto está motivado porque y de las N muestras se estiman como 1/N, por lo que la probabilidad condicional se puede escribir como y . Como , se puede obtener la fórmula anterior. ${\displaystyle p_{i}}$ ${\displaystyle p_{j}}$ ${\displaystyle p_{i\mid j}=Np_{ij}}$ ${\displaystyle p_{j\mid i}=Np_{ji}}$ ${\displaystyle p_{ij}=p_{ji}}$

Tenga en cuenta también que y . ${\displaystyle p_{ii}=0}$ ${\displaystyle -\sum _{i,j}p_{ij}=1}$

El ancho de banda de los núcleos gaussianos se establece de tal manera que la entropía de la distribución condicional sea igual a una entropía predefinida utilizando el método de bisección . Como resultado, el ancho de banda se adapta a la densidad de los datos: se utilizan valores más pequeños de en las partes más densas del espacio de datos. La entropía aumenta con la perplejidad de esta distribución ; esta relación se ve como ${\displaystyle \sigma _{i}}$ ${\displaystyle \sigma _{i}}$ ${\displaystyle P_{i}}$

${\displaystyle Perp(P_{i})=2^{H(P_{i})}}$

¿Dónde está la entropía de Shannon? ${\displaystyle H(P_{i})}$ ${\displaystyle H(P_{i})=-\sum _{j}p_{j|i}\log _{2}p_{j|i}.}$

La perplejidad es un parámetro elegido manualmente de t-SNE y, como afirman los autores, "la perplejidad puede interpretarse como una medida uniforme del número efectivo de vecinos. El rendimiento de SNE es bastante robusto a los cambios en la perplejidad y los valores típicos están entre 5 y 50" . ^[2] .

Dado que el núcleo gaussiano utiliza la distancia euclidiana , se ve afectado por la maldición de la dimensionalidad y, en datos de alta dimensión, cuando las distancias pierden la capacidad de discriminar, se vuelven demasiado similares (asintóticamente, convergerían a una constante). Se ha propuesto ajustar las distancias con una transformación de potencia, basada en la dimensión intrínseca de cada punto, para aliviar esto. ^[12] ${\displaystyle \lVert x_{i}-x_{j}\rVert }$ ${\displaystyle p_{ij}}$

El objetivo de t-SNE es aprender un mapa de dimensiones (con y normalmente elegidos como 2 o 3) que refleje las similitudes lo mejor posible. Para ello, mide las similitudes entre dos puntos del mapa y , utilizando un enfoque muy similar. En concreto, para , se define como ${\displaystyle d}$ ${\displaystyle \mathbf {y} _{1},\dots ,\mathbf {y} _{N}}$ ${\displaystyle \mathbf {y} _{i}\in \mathbb {R} ^{d}}$ ${\displaystyle d}$ ${\displaystyle p_{ij}}$ ${\displaystyle q_{ij}}$ ${\displaystyle \mathbf {y} _{i}}$ ${\displaystyle \mathbf {y} _{j}}$ ${\displaystyle i\neq j}$ ${\displaystyle q_{ij}}$

${\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 . Aquí se utiliza una distribución t de Student de cola pesada (con un grado de libertad, que es lo mismo que una distribución de Cauchy ) para medir similitudes entre puntos de baja dimensión con el fin de permitir que se modelen objetos diferentes muy separados en el mapa. ${\displaystyle q_{ii}=0}$

Las ubicaciones de los puntos en el mapa se determinan minimizando la divergencia de Kullback-Leibler (no simétrica) de la distribución con respecto a la distribución , es decir: ${\displaystyle \mathbf {y} _{i}}$ ${\displaystyle P}$ ${\displaystyle Q}$

${\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 a los puntos se realiza mediante descenso de gradiente . El resultado de esta optimización es un mapa que refleja las similitudes entre las entradas de alta dimensión. ${\displaystyle \mathbf {y} _{i}}$

Producción

Aunque los gráficos t-SNE a menudo parecen mostrar agrupaciones , las agrupaciones visuales pueden verse fuertemente influenciadas por la parametrización elegida (especialmente la perplejidad) y, por lo tanto, se necesita una buena comprensión de los parámetros para t-SNE. Se puede demostrar que tales "agrupaciones" aparecen incluso en datos estructurados sin una agrupación clara, ^[13] y, por lo tanto, pueden ser hallazgos falsos. De manera similar, el tamaño de las agrupaciones producidas por t-SNE no es informativo, y tampoco lo es la distancia entre agrupaciones. ^[14] Por lo tanto, puede ser necesaria una exploración interactiva para elegir parámetros y validar resultados. ^{[15] [16]} Se ha demostrado que t-SNE a menudo puede recuperar agrupaciones bien separadas y, con elecciones de parámetros especiales, se aproxima a una forma simple de agrupación espectral . ^[17]

Software

• Una implementación en C++ de Barnes-Hut está disponible en la cuenta de Github de uno de los autores originales.
• El paquete R Rtsne implementa t-SNE en R.
• ELKI contiene tSNE, también con aproximación de Barnes-Hut
• scikit-learn , una popular biblioteca de aprendizaje automático en Python, implementa t-SNE con soluciones exactas y la aproximación de Barnes-Hut.
• Tensorboard, el kit de visualización asociado a TensorFlow , también implementa t-SNE (versión en línea)
• El paquete Julia TSne implementa t-SNE

Referencias

1. Hinton, Geoffrey; Roweis, Sam (enero de 2002). Incrustación de vecinos estocásticos (PDF) . Sistemas de procesamiento de información neuronal .
2. van der Maaten, LJP; Hinton, GE (noviembre de 2008). "Visualización de datos mediante t-SNE" (PDF) . Revista de investigación en aprendizaje automático . 9 : 2579–2605.
3. Gashi, I.; Stankovic, V.; Leita, C.; Thonnard, O. (2009). "Un estudio experimental de diversidad con motores antivirus disponibles comercialmente". Actas del Simposio internacional IEEE sobre computación en red y aplicaciones : 4–11.
4. Hamel, P.; Eck, D. (2010). "Características de aprendizaje de audio musical con redes de creencias profundas". Actas de la Conferencia de la Sociedad Internacional para la Recuperación de Información Musical : 339–344.
5. Jamieson, AR; Giger, ML; Drukker, K.; Lui, H.; Yuan, Y.; Bhooshan, N. (2010). "Explorando la reducción de dimensión del espacio de características no lineal y la representación de datos en Breast CADx con mapas propios laplacianos y t-SNE". Física médica . 37 (1): 339–351. doi :10.1118/1.3267037. PMC 2807447 . PMID  20175497. 
6. Wallach, I.; Liliean, R. (2009). "La base de datos de proteínas y moléculas pequeñas, un recurso estructural no redundante para el análisis de la unión proteína-ligando". Bioinformática . 25 (5): 615–620. doi : 10.1093/bioinformatics/btp035 . PMID  19153135.
7. Balamurali, Mehala; Silversides, Katherine L.; Melkumyan, Arman (1 de abril de 2019). "Una comparación de t-SNE, SOM y SPADE para identificar dominios de tipo de material en datos geológicos". Computers & Geosciences . 125 : 78–89. Bibcode :2019CG....125...78B. doi :10.1016/j.cageo.2019.01.011. ISSN  0098-3004. S2CID  67926902.
8. Balamurali, Mehala; Melkumyan, Arman (2016). Hirose, Akira; Ozawa, Seiichi; Doya, Kenji; Ikeda, Kazushi; Lee, Minho; Liu, Derong (eds.). "Visualización y agrupamiento del dominio geológico basados ​​en t-SNE". Procesamiento de información neuronal . Apuntes de clase en informática. 9950. Cham: Springer International Publishing: 565–572. doi :10.1007/978-3-319-46681-1_67. ISBN . 978-3-319-46681-1.
9. Leung, Raymond; Balamurali, Mehala; Melkumyan, Arman (1 de enero de 2021). "Estrategias de truncamiento de muestras para la eliminación de valores atípicos en datos geoquímicos: el enfoque de distancia robusta MCD frente a la agrupación por conjuntos t-SNE". Geociencias matemáticas . 53 (1): 105–130. Código Bibliográfico :2021MaGeo..53..105L. doi :10.1007/s11004-019-09839-z. ISSN  1874-8953. S2CID  208329378.
10. Birjandtalab, J.; Pouyan, MB; Nourani, M. (1 de febrero de 2016). "Reducción de dimensión no lineal para la detección de ataques epilépticos basada en EEG". Conferencia internacional IEEE-EMBS de 2016 sobre informática biomédica y de la salud (BHI) . págs. 595–598. doi :10.1109/BHI.2016.7455968. ISBN . 978-1-5090-2455-1.S2CID8074617  .​
11. Pezzotti, Nicola. "TsNE aproximado y orientable por el usuario para análisis visual progresivo" (PDF) . Consultado el 31 de agosto de 2023 .
12. Schubert, Erich; Gertz, Michael (4 de octubre de 2017). Incrustación de vecinos t-estocásticos intrínsecos para visualización y detección de valores atípicos . SISAP 2017 – Décima conferencia internacional sobre búsqueda de similitudes y aplicaciones. págs. 188–203. doi :10.1007/978-3-319-68474-1_13.
13. "Agrupamiento de K-medias en la salida de t-SNE". Validación cruzada . Consultado el 16 de abril de 2018 .
14. Wattenberg, Martin; Viégas, Fernanda; Johnson, Ian (13 de octubre de 2016). "Cómo utilizar t-SNE de forma eficaz". Distill . 1 (10): e2. doi : 10.23915/distill.00002 . ISSN  2476-0757.
15. Pezzotti, Nicola; Lelieveldt, Boudewijn PF; Maaten, Laurens van der; Hollt, Thomas; Eisemann, Elmar; Vilanova, Anna (1 de julio de 2017). "tSNE aproximado y orientable por el usuario para análisis visual progresivo". Transacciones IEEE sobre visualización y gráficos por computadora . 23 (7): 1739-1752. arXiv : 1512.01655 . doi :10.1109/tvcg.2016.2570755. ISSN  1077-2626. PMID  28113434. S2CID  353336.
16. Wattenberg, Martin; Viégas, Fernanda; Johnson, Ian (13 de octubre de 2016). "Cómo usar t-SNE de manera efectiva". Distill . 1 (10). doi : 10.23915/distill.00002 . Consultado el 4 de diciembre de 2017 .
17. Linderman, George C.; Steinerberger, Stefan (8 de junio de 2017). "Agrupamiento con t-SNE, demostrable". arXiv : 1706.02582 [cs.LG].

Enlaces externos

• Wattenberg, Martin; Viégas, Fernanda; Johnson, Ian (13 de octubre de 2016). "Cómo utilizar t-SNE de forma eficaz". Distill . 1 (10): e2. doi : 10.23915/distill.00002 . ISSN  2476-0757.. Demostración interactiva y tutorial.
• Visualización de datos con t-SNE, Google Tech Talk sobre t-SNE
• Implementaciones de t-SNE en varios lenguajes, una colección de enlaces mantenida por Laurens van der Maaten