En anteriores posts os hemos hablado sobre la maldición de la dimensionalidad, y cómo evitarla aplicando PCA (Principal Component Analysis). En este artículo os vamos a explicar en qué consiste el algoritmo T-SNE (T-distributed Stochastic Neighbor Embedding) e implementamos con Python un ejemplo.
Recordamos que la dimensionalidad la marca el número de variables o features de nuestro dataset. Para poder visualizar los datos con muchas variables, es necesario reducirlo a 2 o 3 dimensiones para que los humanos podamos interpretar los resultados. Existen otras técnicas para reducirla, pero nos centraremos explicando las principales diferencias entre PCA y T-SNE.
PCA vs T-SNE
La principal diferencia es que PCA es un algoritmo lineal, por lo que únicamente encontrará dependencias o relaciones lineales en los datos. De esta forma obviará todo tipo de relación polinomial compleja, mientras que T-SNE si que será capaz de resaltarlas.
Además otro problema importante, es que al ser un algoritmo lineal, al representar los datos en un espacio de baja dimensionalidad tiende a preservar la estructura global original de los datos, siendo no siempre una interpretación correcta.
Finalmente, PCA no trata de forma correcta los outliers.
Algoritmo T-SNE
La principal diferencia de este algoritmo con el resto de algoritmos utilizados para reducir la dimensionalidad, es que en lugar de utilizar la distancia Euclídea entre puntos utiliza probabilidades condicionales de similitud entre puntos. A esto se le conoce en español como incrustación de vecinos estocásticos, o en inglés Stochastic Neighbor Embedding (SNE) [1].
El primer paso consiste por tanto en la probabilidad condicional pi/j, la cuál será la si- militud entre xi y xj. Se trata de la probabilidad de que sean vecinos, si éstos se eligiesen en proporción a su densidad de probabilidad bajo una distribución Gausiana o normal centrada en xi. Por tanto, si son vecinos pi/j será alta, y si están alejados pi/j tendrá un valor bajo.
Matemáticamente, pi/j tiene la siguiente expresión, siendo σ la varianza de la Gausiana:
p_{i/j} = \frac{exp(\frac{- ||{x_{i} - x_{j}}||^2}{2 \sigma^2})}{\sum_{ k} exp(\frac{- ||{x_{i} - x_{k}}||^2}{2 \sigma^2})}En segundo lugar, computamos la probabilidad de similitud de los datos en baja dimensión. Denotamos como yi y yj los puntos equivalentes a xi y xj en baja dimensión, y qi/j a la probabilidad condicional, fijando σ a un valor de 1/√2 . Por tanto la expresión es la siguiente:
q_{i/j} = \frac{exp(- ||{y_{i} - y_{j}}||^2)}{\sum_{ k} {exp(- ||{y_{i} - y_{k}}||^2})}Por tanto, es lógico esperar que pi/j y qi/j deben tener valores idénticos para que haya una réplica exacta de los datos en el espacio de alta dimensionalidad en el espacio de baja dimensionalidad.
Para computar el problema de optimización, el algoritmo SNE minimiza la suma de las divergencias de Kullback-Leibler [2] de todos los puntos usando el descenso por gradiente. Sin embargo, las divergencias de Kullback-Leibler son asimétricas. La función de coste es la siguiente:
C= \sum_{i}{KL(\frac{P_i}{P_i})} = \sum_{i}\sum_{j} p_{i/j} log(\frac{p_{i/j} }{q_{i/j} })Sin embargo, aunque el algoritmo SNE, construye unas visualizaciones razonablemente buenas, la función de coste de SNE es computacionalmente costosa e ineficiente de optimizar.
Por tanto, la función de coste del algoritmo final, T-SNE, difiere de la anteriormente explicada en dos formas:
- Utiliza una versión simétrica con gradientes más simples
- Emplea una distribución t-student en lugar de una Gaussiana para computar la similitud entre dos puntos en el espacio de baja dimensión. esta distribución al ser de cola pesada permite «llegar» a las muestras más alejadas.
La versión simétrica la conseguimos realizando la siguiente transformación:
p_{ij} = \frac{p_{i/j} + p_{j/i}}{2N}Utilizamos, como hemos comentado, la distribución de t-student para encontrar la repre- sentación yi en baja dimensión de cada xi:
q_{i/j} = \frac{(1+ ||{y_{i} - y_{j}}||^2)^{-1}}{\sum_{ k} \sum_{ l} {(1+ ||{y_{k} - y_{l}}||^2)^{-1}}}Finalmente computamos la siguiente función de coste:
C= {KL(P||Q)} = \sum_{i \neq j} p_{ij} log(\frac{p_{ij} }{q_{ij} })Ejemplo con Python
Ahora que ya hemos visto de forma teórica como funciona este algoritmo, veamos un ejemplo práctico con el paquete sklearn y Python. Vamos a trabajar sobre el famoso dataset de números de MNIST.
En primer lugar importamos y visualizamos los datos:
from tensorflow.keras.datasets import mnist
(X_train, Y_train), (X_test, Y_test) = mnist.load_data()
plt.gray()
fig, axes = plt.subplots(1,10,figsize=(20,200))
for k,ax in enumerate(axes):
ax.imshow(X_train[k])Si ejecutamos ese código podremos visualizar la siguiente imagen. Observamos como se trata de números escritos a mano:
Las imágenes originales cargadas de MNIST, se trata de un array en 3d. Para poder aplicar el algoritmo tendremos que convertirlo a 2d. Para ello hacemos un reshape :
x_test = X_test.reshape(X_test.shape[0],X_test.shape[1]*X_test.shape[2])
Posteriormente hacemos un escalado de los datos:
from sklearn.preprocessing import StandardScaler x_test = StandardScaler().fit_transform(x_test)
Finalmente implementamos el algoritmo con los hiperparámetros por defecto, excepto el número de componentes que indicamos 2, para poder visualizar en dos dimensiones el resultado. Es decir, una perplejidad de 30 y un learning rate de 200.
from sklearn.manifold import TSNE tsne = TSNE(n_components=2) output = tsne.fit_transform(x_test)
Visualizamos el resultado. Básicamente representamos el output del algoritmo TSNE, junto con las etiquetas reales, asignándole un color.
import numpy as np
import seaborn as sns
import matplotlib.patches as mpatches
palette = sns.color_palette("hls", 10)
fig,ax=plt.subplots(1,1,figsize=(9,9))
sns.scatterplot(x = output[:,0]
, y = output[:,1]
, hue = Y_test
, palette = palette
, legend = 'full')
Se pueden diferenciar claramente los 10 clústers. Sin embargo, hay algunos que los entremezcla. Por ejemplo, los números 7 y 9, hay dos clústers para cada número y entre ellos están ligeramente mezclados.
Probamos a reducir la perplejidad a 10 (parámetro perplexity), y vemos cómo mejora ligeramente la diferenciación de clusters, aunque sigue mezclando ligeramente los números 7 y 9.
Por otra parte, comparamos los resultados de T-SNE con los obtenidos con PCA, y ver las diferencias.
from sklearn.decomposition import PCA pca = PCA(n_components=2) output = pca.fit_transform(x_test)
Conclusiones
Se ha podido contrastar resultados de visualización de la distribución de los datos reduciendo dimensiones a dos dimensiones utilizando PCA y T-SNE, obteniendo resultados mucho mejores con T-SNE.
Sin embargo, en cuanto a complejidad y por tanto, velocidad de entrenamiento, PCA es mucho mejor. Esto se debe a la complejidad de convergencia de la función de coste de T-SNE.
Finalmente comentar una utilidad que he encontrado especialmente interesante. Podemos implementar T-SNE sobre un dataset, previo a aplicar el algoritmo K-means para tener una primera impresión del posible número de clusters (K).
Referencias
[1] Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9, 2008.
[2] S. Kullback. Letter to the editor: The kullback–leibler distance. The American Statistician, 41, 1987.
