Incrustación estocástica de vecinos con distribución t

La incrustación estocástica de vecinos distribuida en t ( t-SNE) es un algoritmo de aprendizaje automático para visualización desarrollado por Laurens van der Maaten y Geoffrey Hinton [1] . Es una técnica de reducción de dimensionalidad no lineal muy adecuado para incrustar datos de alta dimensión para su visualización en un espacio de baja dimensión (2D o 3D). En particular, el método modela cada objeto de alta dimensión con un punto de dos o tres dimensiones de tal manera que los objetos similares se modelan mediante puntos muy próximos entre sí, y los puntos diferentes se modelan con una alta probabilidad mediante puntos que están muy separados.

Descripción

El algoritmo t-SNE consta de dos pasos principales. Primero, t-SNE crea una distribución de probabilidad sobre pares de características de alta dimensión, de modo que es muy probable que se seleccionen características similares, mientras que es poco probable que se seleccionen puntos diferentes. Luego, t-SNE determina una distribución de probabilidad similar sobre puntos en un espacio de baja dimensión y minimiza la distancia de Kullback-Leibler entre las dos distribuciones, teniendo en cuenta la posición de los puntos. Tenga en cuenta que el algoritmo original usa la distancia euclidiana entre objetos como base para medir la similitud, esto se puede cambiar según corresponda.

El algoritmo t-SNE se ha utilizado para visualizar una amplia gama de aplicaciones, incluida la investigación de seguridad informática [2] , el análisis de música [3] , la investigación del cáncer [4] , la bioinformática [5] y el procesamiento de señales biomédicas . [6] . El algoritmo se utiliza a menudo para visualizar representaciones de alto nivel obtenidas de una red neuronal artificial [7] .

Dado que las pantallas t-SNE a menudo se usan para mostrar grupos , y la elección de la parametrización puede afectar significativamente la visualización de grupos, es necesaria la capacidad de trabajar con los parámetros del algoritmo t-SNE. Pueden ser necesarios estudios interactivos [ término desconocido ] [8] [9] para seleccionar parámetros y validar resultados . Se ha demostrado que el algoritmo t-SNE a menudo es capaz de detectar grupos que están bien separados entre sí y, con una selección especial de parámetros, se aproxima a una forma simple de agrupamiento espectral [10] .

Detalles

Dado un conjunto de características de alta dimensión, t-SNE primero calcula las probabilidades , que son proporcionales a la similitud de las características y de la siguiente manera: $norte$ ${\ estilo de visualización \ mathbf {x} _ {1}, \ puntos, \ mathbf {x} _ {N}}$ $p_{{ij}}$ ${\ estilo de visualización \ mathbf {x} _ {i}}$ ${\ estilo de visualización \ mathbf {x} _ {j))$

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})}},

Van der Maaten y Hinton explicaron: "La similitud de un punto de datos con un punto es la probabilidad condicional de que se elija como punto vecino, si los vecinos se eligen proporcionalmente a su densidad de probabilidad gaussiana centrada en " [1] . $x_{j}$ $x_{yo}$ ${\ Displaystyle p_ {j|i}}$ $x_{yo}$ $x_{j}$ $x_{yo}$

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

Además, las probabilidades c se toman iguales a cero: ${\ estilo de visualización i = j}$ $p_{ii}=0$

El ancho de banda de los núcleos gaussianos se establece mediante el método de bisección para que la perplejidad de la distribución condicional sea igual a la perplejidad predefinida. Como resultado, el ancho de banda se adapta a la densidad de datos : se utilizan valores más pequeños en las partes más densas del espacio de datos. $\sigma_i$ $\sigma_i$

Dado que el núcleo gaussiano usa la distancia euclidiana , está sujeto a la maldición de la dimensionalidad y en datos de alta dimensión, cuando las distancias se vuelven indistinguibles, se vuelven demasiado similares (asintóticamente, convergen en una constante). Se propone ajustar la distancia mediante una transformación exponencial basada en el tamaño interno cada punto para mitigar el problema [11] . $\lVert x_{i}-x_{j}\rVert$ $p_{{ij}}$

El algoritmo t-SNE busca obtener un mapeo en espacio(s) -dimensional(es ) que refleje similitudes tanto como sea posible. Para ello, el algoritmo mide la similitud entre dos puntos y utiliza un enfoque muy similar. En concreto, se define como ${\ estilo de visualización \ mathbf {y} _ {1}, \ puntos, \ mathbf {y} _ {N}}$ $d$ ${\displaystyle \mathbf {y} _{i}\in \mathbb {R} ^{d))$ $p_{{ij}}$ ${\ Displaystyle q_ {ij}}$ ${\ estilo de visualización \ mathbf {y} _ {i}}$ ${\ estilo de visualización \ mathbf {y} _ {j}}$ ${\ Displaystyle q_ {ij}}$

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

Aquí, se usa una distribución t de Student de cola ponderada (con un grado de libertad, que es lo mismo que la distribución de Cauchy ) para medir la similitud entre puntos en un espacio de baja dimensión para poder colocar objetos diferentes muy separados. en el mapa. Tenga en cuenta que en este caso también establecemos $q_{ii}=0$

La ubicación de los puntos en el espacio de baja dimensión se determina minimizando la distancia (asimétrica) de Kullback-Leibler de la distribución a la distribución , es decir ${\ estilo de visualización \ mathbf {y} _ {i}}$ $q$ $PAGS$

KL(P||Q)=\sum_{i\neq j}p_{ij}\log {\frac {p_{ij}}{q_{ij}}}

La minimización de la distancia Kullback-Leibler con respecto a los puntos se realiza mediante descenso de gradiente . El resultado de la optimización es un mapeo que refleja la similitud entre objetos en un espacio de alta dimensión. ${\ estilo de visualización \ mathbf {y} _ {i}}$

Software

Algoritmo de "incrustación de vecinos estocásticos distribuidos en t" de Lawrence van der Maaten https://lvdmaaten.github.io/tsne/
ELKI contiene tSNE con aproximación de Barnes-Hut. https://github.com/elki-project/elki/blob/master/elki/src/main/java/de/lmu/ifi/dbs/elki/algorithm/projection/TSNE.java (enlace no disponible)

Notas

↑ 12 van der Maaten , Hinton, 2008 , pág. 2579–2605.
↑ Gashi, Stankovic, Leita, Thonnard, 2009 , pág. 4–11.
↑ Hamel, Eck, 2010 , pág. 339–344.
↑ Jamieson, Giger, Drukker, Lui, Yuan, Bhooshan, 2010 , pág. 339–35.
↑ Wallach, Liliian, 2009 , pág. 615–620.
↑ Birjandtalab, Pouyan y Nourani, 2016 , pág. 595–598.
↑ Blog de Olah, 2015 .
↑ Pezzotti, Lelieveldt, van der Maaten et al., 2017 , pág. 1739-1752
↑ Wattenberg, Viegas, Johnson, 2016 .
↑ Linderman, Steinerberger, 2017 .
↑ Schubert, Gertz, 2017 , pág. 188–203.

Literatura

van der Maaten LJP, Hinton GE Visualización de datos mediante t-SNE // Journal of Machine Learning Research. - 2008. - noviembre ( vol. 9 ).
Gashi I., Stankovic V., Leita C., Thonnard O. Un estudio experimental de la diversidad con motores antivirus comerciales // Actas del Simposio internacional IEEE sobre computación en red y aplicaciones. — 2009.
Hamel P., Eck D. Funciones de aprendizaje del audio musical con redes de creencias profundas // Actas de la Conferencia de la Sociedad Internacional para la Recuperación de Información Musical. — 2010.
Jamieson AR, Giger ML, Drukker K., Lui H., Yuan Y., Bhooshan N. Exploración de la reducción de la dimensión 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. - 2010. - T. 37 , núm. 1 . -doi : 10.1118 / 1.3267037 . —PMID 20175497 .
Wallach I., Liliian R. La base de datos de moléculas pequeñas de proteínas, un recurso estructural no redundante para el análisis de la unión de proteínas y ligandos // Bioinformática. - 2009. - T. 25 , núm. 5 . -doi : 10.1093 / bioinformática/btp035 . —PMID 19153135 .
Birjandtalab J., Pouyan MB, Nourani M. Reducción de la 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). - 2016. - ISBN 978-1-5090-2455-1 . -doi : 10.1109/ BHI.2016.7455968 .
Cristóbal Ola. Visualización de representaciones: aprendizaje profundo y seres humanos . — 2015.
Nicola Pezzotti, Boudewijn PF Lelieveldt, Laurens van der Maaten, Thomas Hollt, Elmar Eisemann, Anna Vilanova. tSNE orientable por el usuario y aproximado para análisis visual progresivo // Transacciones IEEE en visualización y gráficos por computadora. - 2017. - T. 23 , núm. 7 . — ISSN 1077-2626 . -doi : 10.1109/ tvcg.2016.2570755 . — PMID 28113434 .
Martín Wattenberg, Fernanda Viegas, Ian Johnson. Cómo usar t-SNE de manera efectiva . — Destilar, 2016.
George C. Linderman, Stefan Steinerberger. Agrupamiento con t-SNE, probablemente. — 2017.
Erich Schubert, Michael Gertz. Incrustación de vecinos t-estocásticos intrínsecos para visualización y detección de valores atípicos // SISAP 2017 - 10ª Conferencia internacional sobre búsqueda y aplicaciones de similitud. -2017.- doi : 10.1007/978-3-319-68474-1_13 .

Enlaces

Visualización de datos mediante t-SNE , Google Tech Talk sobre t-SNE

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ICA LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG