incrustación de vecinos estocásticos distribuidos en t

Técnica de reducción de dimensionalidad.

Visualización T-SNE de incrustaciones de palabras generadas utilizando literatura del siglo XIX.

Incorporaciones T-SNE del conjunto de datos MNIST

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 al darle a cada punto de datos una ubicación en un mapa de dos o tres dimensiones. Se basa en Stochastic Neighbor Embedding desarrollado originalmente por Geoffrey Hinton y Sam Roweis, ^[1] donde Laurens van der Maaten propuso la variante t distribuida . ^[2] Es una técnica de reducción de dimensionalidad no lineal para incrustar datos de alta dimensión para su visualización en un espacio de baja dimensión de dos o tres dimensiones. Específicamente, modela cada objeto de alta dimensión mediante un punto bidimensional o tridimensional de tal manera que los objetos similares se modelan mediante puntos cercanos y los objetos diferentes se modelan mediante puntos distantes con alta probabilidad.

El algoritmo t-SNE consta de dos etapas principales. Primero, t-SNE construye una distribución de probabilidad sobre pares de objetos de alta dimensión de tal manera que a objetos similares se les asigna una probabilidad más alta mientras que a 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 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 corresponda. Una variante riemanniana es la UMAP .

t-SNE se ha utilizado para la visualización en una amplia gama de aplicaciones, incluida la genómica , la investigación de seguridad informática , ^[3] el procesamiento del lenguaje natural , el análisis de música , ^[4] la investigación del cáncer , ^[5] la bioinformática , ^[6] la interpretación del dominio geológico, ^{[7] [8] [9]} y procesamiento de señales biomédicas. ^[10]

Si bien los gráficos de t-SNE a menudo parecen mostrar grupos , los grupos visuales pueden verse fuertemente influenciados por la parametrización elegida y, por lo tanto, es necesaria una buena comprensión de los parámetros para t-SNE. Se puede demostrar que tales "grupos" aparecen incluso en datos no agrupados ^[11] y, por lo tanto, pueden ser hallazgos falsos. Por lo tanto, puede ser necesaria una exploración interactiva para elegir parámetros y validar resultados. ^{[12] [13]} Se ha demostrado que t-SNE a menudo es capaz de recuperar grupos bien separados y, con opciones de parámetros especiales, se aproxima a una forma simple de agrupamiento espectral . ^[14]

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

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 , define ${\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 establecer . Tenga en cuenta que el denominador anterior garantiza para todos . ${\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 de un punto de datos con otro es la probabilidad condicional, que elegiría como vecino si los vecinos se eligieran en proporción a su densidad de probabilidad bajo un gaussiano centrado en ". ^[2] ${\displaystyle x_{j}}$ ${\displaystyle x_{i}}$ ${\displaystyle p_{j|i}}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{j}}$ ${\displaystyle x_{i}}$

Ahora define

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

Esto se debe a que y de las N muestras se estiman como 1/N, por lo que la probabilidad condicional se puede escribir como y . Desde entonces puedes 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}}$

También tenga en cuenta 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 partes más densas del espacio de datos. ${\displaystyle \sigma _{i}}$ ${\displaystyle \sigma _{i}}$

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). Para paliar esto se ha propuesto ajustar las distancias con una transformada de potencia, en función de la dimensión intrínseca de cada punto. ^[dieciséis] ${\displaystyle \lVert x_{i}-x_{j}\rVert }$ ${\displaystyle p_{ij}}$

t-SNE tiene como objetivo aprender un mapa dimensional (con y típicamente elegido como 2 o 3) que refleje las similitudes lo mejor posible. Para ello, mide similitudes entre dos puntos del mapa y , utilizando un enfoque muy similar. Específicamente, para , 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 establecer . 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 para permitir modelar objetos diferentes muy separados en el mapa. . ${\displaystyle q_{ii}=0}$

Las ubicaciones de los puntos en el mapa se determinan minimizando la divergencia Kullback-Leibler (no simétrica) de la distribución de 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}}$

Software

• 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 con TensorFlow , también implementa t-SNE (versión en línea)

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 sobre aprendizaje automático . 9 : 2579–2605.
3. Gashi, yo; Stankovic, V.; Leita, C.; Thonnard, O. (2009). "Un estudio experimental de la diversidad con motores antivirus disponibles en el mercado". Actas del Simposio internacional IEEE sobre aplicaciones y computación en red : 4–11.
4. Hamel, P.; Eck, D. (2010). "Aprendiendo funciones del audio musical con Deep Belief Networks". 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). "Exploración de la reducción de dimensiones del espacio de características no lineales y la representación de datos en CADx de mama 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, yo; 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 de proteínas y ligandos". Bioinformática . 25 (5): 615–620. doi : 10.1093/bioinformática/btp035 . PMID  19153135.
7. Balamurali, Mehala; Pejerreyes, Katherine L.; Melkumyan, Arman (1 de abril de 2019). "Una comparación de t-SNE, SOM y SPADE para identificar dominios de tipos de materiales en datos geológicos". Computadoras y geociencias . 125 : 78–89. Código Bib : 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 agrupación del dominio geológico basada en t-SNE". Procesamiento de información neuronal . Apuntes de conferencias sobre 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). "Ejemplos de estrategias de truncamiento para la eliminación de valores atípicos en datos geoquímicos: el enfoque de distancia robusta de MCD frente a la agrupación de conjuntos t-SNE". Geociencias Matemáticas . 53 (1): 105-130. Código Bib : 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 2016 sobre informática biomédica y de salud (BHI) . págs. 595–598. doi :10.1109/BHI.2016.7455968. ISBN 978-1-5090-2455-1. S2CID  8074617.
11. "K-significa agrupación en la salida de t-SNE". Validación cruzada . Consultado el 16 de abril de 2018 .
12. 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.
13. Wattenberg, Martín; Viegas, Fernanda; Johnson, Ian (13 de octubre de 2016). "Cómo utilizar t-SNE de forma eficaz". Destilar . 1 (10). doi : 10.23915/distill.00002 . Consultado el 4 de diciembre de 2017 .
14. Linderman, George C.; Steinerberger, Stefan (8 de junio de 2017). "Agrupación con t-SNE, demostrablemente". arXiv : 1706.02582 [cs.LG].
15. Pezzotti, Nicola. "tSNE aproximado y orientable por el usuario para análisis visual progresivo" (PDF) . Consultado el 31 de agosto de 2023 .
16. 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 – 10° Congreso Internacional sobre Búsqueda y Aplicaciones de Similitudes. págs. 188-203. doi :10.1007/978-3-319-68474-1_13.

enlaces externos

• Visualización de datos utilizando t-SNE, Google Tech Talk sobre t-SNE
• Implementaciones de t-SNE en varios idiomas, una colección de enlaces mantenida por Laurens van der Maaten