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

El incrustamiento estocástico de vecinos 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 el incrustamiento estocástico de vecinos desarrollado originalmente por Geoffrey Hinton y Sam Roweis, ^{[ 1 ]} donde Laurens van der Maaten y Hinton propusieron la variante distribuida en t . ^{[ 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 disímiles 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 los objetos similares se les asigna una probabilidad mayor, mientras que a los puntos disímiles se les asigna una probabilidad menor. Segundo, 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 riemanniana es UMAP .

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

Para un conjunto de datos con${\displaystyle n}$elementos, t-SNE se ejecuta en${\displaystyle O(n^{2})}$tiempo y requiere${\displaystyle O(n^{2})}$espacio. ^{[ 11 ]}

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

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

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

Como explicaron van der Maaten y Hinton: "La similitud de los puntos de datos${\displaystyle x_{j}}$punto de datos${\displaystyle x_{i}}$es la probabilidad condicional,${\displaystyle p_{j|i}}$, eso${\displaystyle x_{i}}$elegirí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}}$." ^{[ 2 ]}

Ahora define

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

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

Tenga en cuenta también 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}}$está configurado 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: valores más pequeños de${\displaystyle \sigma _{i}}$se utilizan en las partes más densas del espacio de datos. La entropía aumenta con la perplejidad de esta distribución.${\displaystyle P_{i}}$; esta relación se considera como

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

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

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

Dado que el núcleo gaussiano utiliza la distancia euclidiana${\displaystyle \lVert x_{i}-x_{j}\rVert }$, 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,${\displaystyle p_{ij}}$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 mitigar este problema. ^{[ 12 ]}

t-SNE tiene como objetivo aprender un${\displaystyle d}$-mapa dimensional${\displaystyle \mathbf {y} _{1},\dots,\mathbf {y} _{N}}$(con${\displaystyle \mathbf {y} _{i}\in \mathbb {R} ^{d}}$y${\displaystyle d}$normalmente se elige como 2 o 3) que refleja las similitudes ${\displaystyle p_{ij}}$lo mejor posible. Para ello, mide las similitudes.${\displaystyle q_{ij}}$entre dos puntos en el mapa${\displaystyle \mathbf {y} _ {i}}$y${\displaystyle \mathbf {y} _ {j}}$, utilizando un enfoque muy similar. Específicamente, para${\displaystyle i\neq j}$, definir${\displaystyle q_{ij}}$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 establecer${\displaystyle q_{ii}=0}$En este trabajo 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 las similitudes entre puntos de baja dimensión con el fin de permitir que objetos disímiles se modelen muy separados en el mapa.

La ubicación de los puntos${\displaystyle \mathbf {y} _ {i}}$En el mapa se determinan minimizando la divergencia de Kullback-Leibler (no simétrica) de la distribución.${\displaystyle P}$de la distribución${\displaystyle Q}$, eso es:

${\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${\displaystyle \mathbf {y} _ {i}}$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.

Aunque los gráficos t-SNE a menudo parecen mostrar clústeres , estos pueden verse fuertemente influenciados por la parametrización elegida (especialmente la perplejidad), por lo que es necesario comprender bien los parámetros de t-SNE. Se ha demostrado que tales "clústeres" pueden aparecer incluso en datos estructurados sin una agrupación clara, ^{[ 13 ]} y, por lo tanto, pueden ser falsos positivos. Del mismo modo, el tamaño de los clústeres producidos por t-SNE no es informativo, ni tampoco la distancia entre ellos. ^{[ 14 ]} Por lo tanto, puede ser necesaria una exploración interactiva para elegir parámetros y validar los resultados. ^{[ 15 ] [ 16 ]} Se ha demostrado que t-SNE a menudo puede recuperar clústeres bien separados y, con elecciones de parámetros específicas, se aproxima a una forma simple de agrupamiento espectral . ^{[ 17 ]}

• Existe una implementación en C++ del algoritmo Barnes-Hut disponible en la cuenta de GitHub de uno de los autores originales.
• El paquete Rtsne implementa t-SNE en R.
• ELKI contiene tSNE, también con la 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 ).
• El paquete TSne de Julia implementa t-SNE.

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