Icone color1 07

Incrustación estocástica de vecinos (SNE) y su corrección en t-SNE

Autor: Matteo Alberti

Traducido per Carlos Alfaro


 

 

 

Incrustación estocástica de vecinos (SNE) y su corrección en t-SNE

 

En este tutorial nos disponemos a enfrentar el problema de reducción de la dimensionalidad, con una herramienta significativa:

 

Stochastic Neighbor Embedding o “SNE”, como es normalmente conocido.

 

La definición del problema es:

 

“Tenemos un gran conjunto de datos y queremos encontrar una forma de reducir su dimensionalidad, tanto para el pre-procesamiento como para la clasificación/visualización”.

 

Podrían existir elementos ambiguos. Por lo tanto, la primera pregunta que nos planteamos es: ¿Qué queremos decir con ambigüedad?

 

Ejemplo: Estamos tratando con un problema de clasificación de texto y abordamos la siguiente palabra: bank.

 

Nos concentramos en asociar esta palabra a otras como ‘finance’ o ‘money’ pero podría estar relacionada con ‘river’ (riverbank/orilla del río) al mismo tiempo.

 

Dentro de las herramientas más populares para la reducción de la dimensionalidad, se encuentran:

 

* Multidimensional scaling (MDS).

* PCA (Principal Component Analysis).

* Local Geometry preserved tools (Local Linear Embedding).

 

 

Dado que, cada objeto de un espacio de alta dimensionalidad puede ser asociado con un solo objeto dentro de un espacio de baja dimensionalidad. El SNE trata de mapear objetos de alta dimesionalidad en objetos de poca dimensionalidad, preservando la estructura de parentesco de la vecindad, sin importar el intercambio que resulta de una clasificación incorrecta alrededor de objetos lejanos. El SNE no tiene nada que ver con las medidas de disimilaridad pero está basado en dos conceptos: Entropy y Probability Divergences.

 

La idea principal es centrar una distribución gaussiana para cada valor de entrada (a lo largo del espacio de alta dimensionalidad) a fin de usar su densidad para definir una distribución de probabilidad de todos los vecinos. El objetivo es aproximar esta distribución de probabilidad tanto como sea posible replicando la estructura de parentesco en un espacio de baja dimensionalidad.

 

 

Presentando el formalismo matemático apropiado:

 

Dado X1,…, Xn E R^K, intentamos construir una función (phi) E R^2.

Vamos a centrar una distribución gaussiana para cada valor y asociarle una probabilidad.

 

De esta manera, se espera tener un vistazo en lo que ocurre durante la transición de R^k a R^2:

Esta relación ocurre cada que {P1,…, Pk} y {Q1,…, Qn} son lo más similares posible. Con esto, nuestra función objetivo (K-L) es minimizar:


Nota explicativa:

Kullback-Leibler Divergence o Cross-Entropy:

Dado dos funciones de probabilidad:

Pi,…, Pk y Qi,…,Qk definimos la entropía cruzada, como:

Con las siguientes propiedades:

  1.     D(P||Q) ≥ 0
  2.     D(P||Q) = 0                 ↔ Q=P
  3.     D(P||Q) ≠ D(Q||P)      No simétrica

¿Qué significa esto?

 

  •  Si Pi incrementa, el objeto está más próximo.
  •  Si Qi aumenta mientras Pi disminuye, estamos aproximando dos objetos lejanos en R^k (lo cual no es bueno). Pero es un error despreciable porque nuestro Qi-ésimo elemento está ponderado por Pj|i. De esta forma el SNE preserva la estructura del vecino local sin importar la estructura global.

 

¿Cómo cambia C, mientras nos movemos a lo largo del espacio? ¿Cómo nos podemos mover?

Esto se puede realizar, al estudiar las derivadas parciales:

 

Primero, recordemos que la densidad de los puntos está dada por ‘sigma’ (Gaussian dilation y Smoothing parameter). Esto define si nuestros valores buscan más lejos o más cerca dentro del espacio.

 

¿Cómo podemos elegir ‘sigma‘?

Tenemos que definir un nuevo objeto llamado perplejidad:

Perplejidad: 2H(Pi). Donde:

Si la perplejidad es constante entonces nos permite cambiar los vecinos al mutar la única sigma.

 

Problema: En caso de alta dimensionalidad, los valores lejanos son acumulados en un ‘bloque periférico’. Este deslizamiento se debe a nuestra disposición de representar de manera adecuada la estructura del vecino.

 

Resolución: Su correción en t-SNE

Por lo tanto, nos disponemos a corregir esta concentración de clasificaciones erróneas. Para hacerlo, operaremos en la estructura general de la distribución gaussiana. La idea principal es muy simple, intenamos elevar las colas de la distribución. Al hacer esto, los puntos originalmente cerrados (cercano a uno) se deslizarán en un factor insignificante. Por otro lado, los valores lejanos experimentarán un deslizamiento considerable, distanciándolos unos de otros.


 

Hagamos uso de él con Python.

Únicamente tenemos que llamar a la biblioteca Scikit, en donde está implementado:

from sklearn.manifold import TSNE

Respecto a t-SNE, vamos a discutir los parámetros más relevantes:

TSNE(n_components=2, perplexity=30.0, early_exaggeration=12.0, learning_rate=200.0, n_iter=1000, n_iter_without_progress=300, min_grad_norm=1e-07, metric=’euclidean’, init=’random’, verbose=0, random_state=None, method=’barnes_hut’, angle=0.5)

 

  • n_components: por defecto (igual a 2), es el número de dimesiones finales.
  • perplejidad: es el parámetro principal. Cuanto mayor sea la perplejidad, mayor será la cantidad de vecinos. Una buena regla es ajustarlo entre 5 y 50.

 

¡Atención!

Si la perplejidad es demasiado pequeña, no capturaremos suficientes vecinos: al contrario, un número excesivo acercará valores demasiado lejanos. Con grandes conjuntos de datos se recomienda mejorar este parámetro.

 

* learning_rate : sugerimos un rango entre 10 y 1000.

 

Pero, ¿cómo deberíamos de inicializarlo de manera correcta en un rango tan grande?

Consideremos dos casos:

 

  • Los datos se concentran en un espacio casi equidistante el uno del otro, esto significa, que emerge un valor demasiado grande.
  • La conenctración fuerte de datos con solo algunos valores atípicos. El parámetro está ajustado muy bajo.

 

 

Ahora, queremos aplicarlo a los datos reales.

El conjunto de datos MNIST, consiste de más de 60 mil imágenes de digitos escritos a mano.

 

Importamos los paquetes y datos requeridos:

 %pylab inline from sklearn.datasets import fetch_mldata from sklearn.decomposition import PCA # Load MNIST dataset mnist = fetch_mldata("MNIST original") X, y = mnist.data / 255.0, mnist.target 

 

Hacemos una primera reducción de dimensionalidad con un análisis de componentes principales (PCA): útil cuando existen muchos datos comprimidos, a diferencia de cuando existen datos de sobra, en donde SVD puede ser la mejor alternativa.

 indices = arange(X.shape[0]) random.shuffle(indices) n_train_samples = 5000 X_pca = PCA(n_components=50).fit_transform(X) X_train = X_pca[indices[:n_train_samples]] y_train = y[indices[:n_train_samples]] 

 

Empecemos a usar el t-SNE. La perplejidad ha sido definida como 40, después de algunos intentos.

 

X_train_embedded = TSNE(n_components=2, perplexity=40, verbose=2).fit_transform(X_train)

 

Representando nuestros resultados:

 

 

matplotlib.rc('font', **{'family' : 'sans-serif',
                         'weight' : 'bold',
                         'size'   : 18})
matplotlib.rc('text', **{'usetex' : True})

def plot_mnist(X, y, X_embedded, name, min_dist=10.0):
    fig = figure(figsize=(10, 10))
    ax = axes(frameon=False)
    title("\\textbf{MNIST dataset} -- Two-dimensional "
          "embedding of 70,000 handwritten digits with %s" % name)
    setp(ax, xticks=(), yticks=())
    subplots_adjust(left=0.0, bottom=0.0, right=1.0, top=0.9,
                    wspace=0.0, hspace=0.0)
    scatter(X_embedded[:, 0], X_embedded[:, 1],
            c=y, marker="x")

    if min_dist is not None:
        from matplotlib import offsetbox
        shown_images = np.array([[15., 15.]])
        indices = arange(X_embedded.shape[0])
        random.shuffle(indices)
        for i in indices[:5000]:
            dist = np.sum((X_embedded[i] - shown_images) ** 2, 1)
            if np.min(dist) < min_dist:
                continue
            shown_images = np.r_[shown_images, [X_embedded[i]]]
            imagebox = offsetbox.AnnotationBbox(
                offsetbox.OffsetImage(X[i].reshape(28, 28),
                                      cmap=cm.gray_r), X_embedded[i])
            ax.add_artist(imagebox)

 


plot_mnist(X[indices[:n_train_samples]], y_train, X_train_embedded,

“t-SNE”, min_dist=20.0)

 

El t-SNE obtuvo el resultado en 17.51s.

 

Si queremos comprararlo con otras ténicas de reducción de la dimensionalidad (como se mencionó antes), hay dos cuestiones fundamentales a explicar:


  1. Habilidad discriminatoria efectiva.

Establecer los parámetros de manera adecuada no siempre es fácil. Por lo tanto, aquí hay un enlace que muestra cómo modificar los parámetros principales y mostrar el diseño de datos en tiempo real. Hay que recordar que los datos que se encuentran en el enlace son simulados y provienen de un ambiente controlado.

 

https://distill.pub/2016/misread-tsne/

 

  1. Tiempo de ejecución:

A diferencia de otras herramientas, el t-SNE requiere un número elevado de tiempo y recursos. Como se puede ver, mientras el PCA toma aproximadamente 0.01, el t-SNE es 17s más lento. Tenemos que considerar esto, si  consideramos el lapso de tiempo como un factor crucial.

 

Sin embargo, es posible proporcionar algunas ideas sobre cómo abordar este problema. Aquí hay dos artículos del Departamento de Ciencias de la Computación de la Universidad de California:

 

Fast Optimization for t-SNE, Laurens van der Maaten (University of California)

http://cseweb.ucsd.edu/~lvdmaaten/workshops/nips2010/papers/vandermaaten.pdf

Accelerating t-SNE using Tree-Based Algorithms, Laurens van der Maaten (University of California)

http://lvdmaaten.github.io/publications/papers/JMLR_2014.pdf

 

 

 

References:

http://scikit-learn.org/stable/index.html (Official Website of Scikit libraries)

http://www.cs.toronto.edu/~fritz/absps/sne.pdf (documentation about SNE)

http://www.cs.toronto.edu/~hinton/absps/tsne.pdf (documentation about t-SNE)

 

0 commenti

Lascia un Commento

Vuoi partecipare alla discussione?
Fornisci il tuo contributo!

Lascia un commento

Il tuo indirizzo email non sarà pubblicato. I campi obbligatori sono contrassegnati *