Articoli

Capsule Networks – Daniele D’Armiento

Daniele D’Armiento – Physicist presso Samsung
“Analisi di una rete neurale capsulare nella Computer Vision”
L’attuale stato dell’arte per la classificazione d’immagini, introdotte nell’ottobre 2017, sta aprendo nuove strade inesplorate nel mondo del Deep Learning (apprendimento profondo) non più basate sull’ormai comune prassi di aumentare la profondità della rete o aumentare i dati a nostra disposizione per raggiungere performance migliori ma contrariamente su una struttura capsulare ed un processo definito “routing-by-agreement” in grado di superare la perdita delle informazioni spaziali delle reti convoluzionali ed al tempo stesso di ottenere simil-analoghe performance con una quantità di dati inferiore.

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)

 

Metodi per la riduzione della dimensionalità basati sulla Varietà differenziabile: il caso ISOMAP

Autore: Matteo Alberti


 

In questo tutorial andiamo ad aprire una mini serie dedicata ai metodi di riduzione della dimensionalità basati su una struttura matematica chiamata Varietà differenziabile (Manifold)

Andiamo dunque a capire che cosa sia una Varietà differenziabile, quando risulta utile e come applicarlo senza però entrare nel dettaglio sulla struttura e sulle proprietà matematiche.

“Manifold non è altro che uno spazio matematico dove localmente viene a ricrearsi uno spazio euclideo (di una specifica dimensione) ma non a livello globale”

Quindi quando e come andremo ad applicare questa serie di metodi?

La risposta è semplice: Quando i metodi lineari falliscono

 

Andiamo ad indagare in maniera più approfondita:


 

Esempio:

Nei metodi lineari (come PCA, MDS, SVD) i nostri dati possono essere ridimensionati solo attraverso combinazioni lineari delle nostre features, ciò comporta che strutture più complesse e non lineari non vengono scovate e dunque discriminate.

Riportiamo un esempio grafico:

 

Metodi Lineari ci ridurrebbero i dati perdendo la struttura geometrica. Come mostra in figura i punti X1 ed X2 risulterebbero avvicinati (e cosi tutta la struttura risulterebbe “appiattita”)

Metodi basati sulla Varietà differenziabile contrariamente ci riescono. I principali sono:

  • ISOMAP
  • Local Linear Embedding (LLE)

 

Vogliamo ricordare che il nostro obiettivo è “preservare la geometria locale”


 

Questa idea di base ci permette di risolvere molti problemi non solo in fase di pre-processing (Nella computer Vision per esempio ci permette di risolvere problemi di: Stima della posizione, compressione dei dati, riduzione del rumore nell’immagine ed interpolazione di dati mancanti)

 

 

ISOMAP

Iniziamo dunque con il primo strumento:

L’algoritmo si compone di tre fasi:

  • Determinare il numero di vicini (neighbors) sul Manifold (basandola sulle distanze Euclidea)

Per ogni punto andremo a mappare i vicini (determinati in base al numero di vicini fissato come nell’algoritmo K-NN o in base ad un raggio fissato)

 

  • In questo step andremo a stimare la Geodetica. Andremo dunque a calcolare la distanza di ogni coppia di punti ma non lavorando in uno spazio Euclideo esso corrisponderà al percorso più breve fra tutti i possibili percorsi per collegare due punti nel manifold. Un esempio di comune utilizzo può esser l’algoritmo di Djkstra, molto comune nel calcolo di della navigazione stradale.
  • In questo ultimo step andremo ad applicare una MDS (multidimensional scaling) alla matrice di distanze della geodetica al fine di ricostruirlo in uno spazio Euclideo che manterrà la stessa struttura geometrica. I vettori di coordinate nello spazio euclideo sono scelti per minimizzare la seguente funzione di costo:


Dy corrisponde alla matrice di distanze Euclidee

L2 corrisponde alla radice quadrata della somma degli elementi

τ non è altro che una funzione di conversione (le distanze vengono sostituite in prodotti interni) al fine di utilizzare algoritmi di ottimizzazione efficienti.


 

 

Andiamo ad implementarlo in Python:

Prima di tutto importiamo i pacchetti necessari di scikit-learn

import numpy as np

import matplotlib.pyplot as plt

from sklearn import manifold

 

La nostra classe sarà cosi articolata:

DATA= manifold.Isomap(n_neighbors=N, n_components=C, eigen_solver=’auto’, tol=0, max_iter=None, path_method=’auto’, neighbors_algorithm=’auto’, n_jobs=1)

Andiamo ad analizzare i parametri principali:

  • n_ neighbors= Numero intero, corrisponde al numero di vicini
  • n_ components= Numero intero, generalmente impostato di default su 2. Corrisponde al numero di coordinate nello spazio del Manifold
  • path_ method= di default ’auto’, FW per Floyd-Warshall, D per l’algoritmo di Djkstra imposta in che modo calcolare le distanze nel grafo.

 

 

Se vogliamo andare a stampare un grafico con i relativi tempi di esecuzione:

 

 

from time import time

t0=time()

ISOMAP_DATA= manifold.Isomap(n_neighbors, n_components=2).fit_transform(OUR_DATA)

t1=time()

print("%s: %.2g sec" % ('ISO' t1-t0))

plot.embedding(ISOMAP_DATA, "ISOMAP ottenuto in " % (t1-t0)

plot.show()

Facciamo due ultime considerazioni di utilizzo pratico:

 

ISOMAP risulta esser uno strumento di riduzione molto efficace che ci permette di bypassare molti problemi legati alla linearità ma il poter preservare una struttura geometrica locale naturalmente è a discapito di alcuni fattori, in particolare:

  • Sensibile ad outliers
  • Pochi parametri liberi

Questo perché la funzionalità dell’algoritmo dipende principalmente dalla scelta di pochi parametri (la scelta del numero dei vicini) infatti anche solo pochi valori outliers possono in qualche modo avvicinare porzioni di dati che dovrebbero contrariamente venir discriminati.

Per questo motivo ISOMAP è altamente consigliato quando abbiamo già qualche idea sulla struttura dei dati anche perché rispetto ad altri metodi lineari risulta computazionalmente più intensivo.

 

Nel Prossimo tutorial andremo ad affrontare LLE, il secondo dei nostri metodi basati sul Manifold.

 

Riferimenti

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

http://web.mit.edu/cocosci/Papers/sci_reprint.pdf  (documentazione su ISOMAP)

Stochastic Neighbor Embedding (SNE) and its correction in t-SNE

Author: Matteo Alberti

 

In this tutorial we are willing to face with a significant tool for the Dimensionality Reduction problem:

Stochastic Neighbor Embedding or just “SNE” as it is commonly called.

The problem definition is:

“We have a large dataset, and we want to find a way to reduce the dimensionality,  both for pre-processing and classification/visualization”. However we have a constraint:

There might exist ambiguous elements.

Therefore, the first question is:

What do we mean by ambiguity?

 

Example We are dealing with a text classification problem and we address with the following word:

Bank.

We are focused on binding this word to others like “finance” or “money” but it might arise that it is related to “river” (namely, bank river) in the same time.

The most popular common dimensionality reduction tools Givesuch as:

  • Multidimensional scaling (MDS)
  • PCA (Principal Component Analysis).
  • Local Geometry preserved tools (Local Linear Embedding)

Given that, every object from an high-dimensional space, can be associated with only one object within a low-dimensional space.

SNE tries to map high-dimensional into low-dimensional objects by preserving the neighbourhood relationship structure in spite of a trade-off consisting of a misclassification around the far objects. SNE has nothing to do with  non-dissimilarity measures but it is grounded on the concept of Entropy and Probability Divergences.

The main idea is to centre a Gaussian distribution for each input value (within the high dimensional space) in order to use its density to define a probability distribution of all neighbours. The aim is to approximate this probability distribution as much accurately as possible replicating the relations structure in a low dimensional space.

Let us introduce the appropriate mathematical formalism:

Given X1….Xn ∈ RK , we intend to to build a mapping function (𝛗) ∈ R2.

We are going to centre a Gaussian distribution for each value and associate a probability to them.

X_{i}\rightarrow\{P_{j|i}\}_{j\neq i}}= \frac{ exp-\{{\frac{\left[|X_{i}-X_{j}|]^2}{2\sigma i^2}}\}} {\sum_{i\neq j} exp-\{{\frac{\left[|X_{i}-X_{j}|]^2}{2\sigma i^2}}\}}}

 

This way, we wish to have a look at what we see during the transition from Rk to Ras much as possible.

 

R^k \{X_1, ... , X_k\} \frac{\varphi}{\rightarrow} \{Y_1, ... , Y_k\} \in R^2 \\ ... \\ R^k \{P_1, ... , P_k\} \leftrightarrow \{Q_1, ... , Q_k\} \in R^2

 

 

This relation occurs whenever {P1…Pk} and {Q1…Qn} are as similar as possible.

From this, our goal function (K-L) is to minimize:

C=\sum_{i=1}^{k} D(P_i||Q_i)=\sum_{i,j} P_{i|j}ln (\frac{Q_{j|i}}{P_{j|i}})

Explanatory note:


 Kullback-Leibler Divergence or  Cross-Entropy:

Given two probability distribution :

Pi… Pk  and Qi…Qk

We define Kullback-Leibler Divergence as:

With the following properties:

1.      D(P||Q) ≥ 0

2.      D(P||Q) = 0                 ↔ Q=P

3.      D(P||Q) ≠ D(Q||P)      Not symmetrical


 

What is the meaning?

  •  If Pi increases the object is closer
  • If Qi increases while Pi decreases means approaching two far objects in Rk (not good!) But it’s a negligible error because our Qi is weighted by Pj|i. This is way SNE preserve local neighbour structure despite global one.

How does c change while we move within the space? How can we move?

This can be done by a study of partial derivatives:

Firstly, let us remind that the density of points is given by σ (Gaussian dilation and Smoothing parameter). This means that our values look further or closer.

 

How can we choose σ?

We have to define a new object called Perplexity:

 Perplexity: 2H(Pi)

Where H(P)=-\sum_{i=1}^{k} P_i ln ({P_i}) Entropy

If Perplexity is constant then it enables us to vary the neighbours by mutating the only σ.

 

Problem: In case of high-dimensionality, far values are accumulated in a “block around”. This slippage is due to our willingness to adequately represent the neighbour’s structure.

 

Resolution: its correction in t-SNE

Therefore, we are willing to remedy this concentration of miss-classification error. In order to do so, we will operate on the overall structure of the Gaussian distribution. The main insight is very simple. We intend to raise the queues of the distribution. By doing so, the originally close points (next to one) will be slipped away in a negligible factor. On the other hand, far values will undergo a considerable sliding, distancing them from each other.

 

  

 

 

 

Let us make use of it with Python

We just have to recall Scikit library where it is implemented:


from sklearn.manifold import TSNE</span></td>

 

t-SNE  (we are going to discuss the most relevant parameters)



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: default (equal to 2), it is the number of the ending dimensions.
  • Perplexity: It is the main parameter. The higher perplexity, the more the the number of neighbours. A good rule is setting it up between 5-50.

Pay attention!

If Perplexity is too small we will not capture enough neighbours; on the contrary, an excessive number will approach values too far. With large datasets, an enhancement of this parameter is recommended.

 

  • learning_rate: we suggest a range between 10 and 1000.

BUT how should we initialize it correctly in such a huge range?

Let us consider two cases:

 Former: Data concentrates in an almost equidistant space from each other. That means that an overly large value arises.

 Second: Strong Data concentration with only some outliers. The parameter is set too low.

 

Now we want to apply it to real data:

Dataset MNIST, consisting of over 60,000 images of handwritten digits.

 

Le us import the required packages and data.





%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

 

We make a first dimension reduction with PCA: useful when there are many compressed data, whereas, by spare data, SVD can be the best choose.


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]]

Le us start t-SNE, perplexity has been set at 40 after some attempts.



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

 

 

Now let us depict our results:

 


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)


 

t-SNE got in 17.51s

 

If we want to compare it with other dimensionality reduction techniques (as mentioned earlier), there are two critical issues to explain:

 

  1. Effective discrimination ability

Of course setting parameters correctly is not always easy. Hence, here you have a link showing how to modify the main parameters and display the data layout in real time: remind that the data you will find here are simulated and well known.

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

 

  1. Execution time:

In spite of other tools, t-SNE requires a greater number of time and resources. As you can see, while PCA takes about 0.01, t-SNE is 17s slower. We have to evaluate this issue if we coondised “time-lapse” as a crucial factor.

However, it is possible to provide some insights about how to tackle this problem. Here you are with two articles from the Computer Science Department at the University of 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:

 

Stochastic Neighbor Embedding (SNE) e la sua correzione in t-SNE

Autore: Matteo Alberti


 

 

Vogliamo affrontare un importante metodo di riduzione della dimensionalità:

Stochastic Neighbor Embedding; anche conosciuto come SNE.

Il punto di partenza:

Abbiamo un large dataset (con molti dati) e vogliamo trovare uno strumento in grado di ridurci la dimensionalità (sia come strumento di pre-processing, sia come strumento di classificazione o di visualizzazione) ma abbiamo un vincolo da rispettare:­

abbiamo oggetti ambigui?

La prima domanda risulta quindi essere:

Cosa intendiamo per ambiguo?

 

Esempio Stiamo facendo classificazione di documenti ed incorriamo nella seguente parola:

Calcio.

È nostro interesse che la parola calcio venga associata a parole come pallone, sport ma al tempo stesso anche a vocabili come sale minerale, potassio, salute.

I più comuni metodi di riduzione di dimensionalità come :

  • Multidimensional scaling (MDS)
  • PCA (Principal Component Analysis).
  • Metodi che preservano una geometria locale (Local Linear Embedding)

richiedono che ogni oggetto “high-dimensional “ sia associato ad una sola posizione in uno spazio con poche dimensioni (“low-dimensional space”).

 

Questo rende difficile spiegare mappature in cui un singolo oggetto appartiene a differenti posizioni in uno spazio a poche dimensioni.

SNE si pone questo obiettivo: mappare gli oggetti in spazi low-dimensional preservando la struttura dei vicini anche a costo di mal classificare oggetti distanti attraverso misure di entropia (quindi su “divergenze in probabilità”) piuttosto che misure di dissimilarità.

L’idea è quella di centrare una Gaussiana per ogni valore iniziale (ossia nello spazio a high-dimensional di origine) così da utilizzare le relative densità per definire una distribuzione di probabilità di tutti i potenziali vicini (neighbors). L’obiettivo risulta quindi esser di approssimare quanto più correttamente questa distribuzione di probabilità al fine di replicarla in uno spazio low-dimensional.

 

 

Introducendo l’adeguato formalismo matematico:

Sia X1….Xn ∈ RK vogliamo creare una mappa (𝛗) ∈ R2.

 

 

Costruiamo una Gaussiana in ogni punto, in questo modo stiamo associando ad ogni valore una probabilità.

Vogliamo che cio che vedo in

 R^k\{x_1, ... , x_k\} \frac{\varphi} {\to} \{Y_1, ..., Y_n\} \in R^2 \\ ... \\ R^k\{x_1, ... , x_k\} \leftrightarrow \{Q_1, ..., Q_n\} \in R^2

 

risulti esser quanto più possibile simile in R2.

 

Questo avviene quando {P1…Pk} e  {Q1…Qn} sono il più possibili simili.

Espresso con altri termini ciò significa  minimizzare la seguente funzione (che chiameremo funzione obiettivo di K-L)

C= \sum_{i=1}^k D(P_i||Q_i) = \sum_{i,j} P_{i|j}ln(\frac{P_{j|i}}{Q_{j|i}})

 

Piccola nota:


 Divergenza di Kullback-Leibler o di Cross-Entropia:

Abbiamo due distribuzioni di probabilità :

Pi… Pk  e Qi…Qk

Definiamo Divergenza di K-L:

Che gode delle seguenti proprietà:

1.      D(P||Q) ≥ 0

2.      D(P||Q) = 0                 ↔ Q=P

3.      D(P||Q) ≠ D(Q||P)      Non è simmetrica


 

Cosa significa ciò?

  •  All’aumentare di Pi il l’oggetto risulta essere vicino
  • Se Q viene reso grande al decrescere di P significa avvicinare due punti distanti in Rk. Ma ne risulta un errore trascurabile in quanto vengono pesate dalle Pj|i. In questo modo SNE tende, come definito nella fase di introduzione a preservare le strutture di vicinanze a discapito delle lontananze

 

Come cambia c mentre lo spostiamo nel piano? Lo studiamo attraverso le derivate parziali:

Da notare che la densità dei punti è data da σi dove il parametro mi dilata o restringe la gaussiana facendo sembrar i valori siano più distanti o più vicini.

 

Come assegnamo σ?

Definiamo un nuovo oggetto:

Perplessità: 2H(Pi)

Se la Perplessità risulta costante: ci permette di far variare l’intorno considerando la distanza dagl’altri punti facendo variare unicamente σ.

 

Problema: Con alta dimensionalità i valori lontani vengono accumulati in un “intorno a blocchi”. Questo slittamento è dovuto al nostro voler rappresentare adeguatamente la struttura dei vicini.

 

Risoluzione: La correzione t-SNE

Vogliamo dunque rimediare a questo concentramento di valori distanti mal classificati, per far ciò andremo ad agire sulla struttura della nostra Gaussiana. L’idea è in se molto semplice. Vogliamo alzare le code delle distribuzioni. Così facendo, i punti originariamente vicini (prossimi ad 1) verranno dilatati ma di un fattore che riterremo “trascurabile” in compenso i punti più lontani subiranno uno slittamento maggiore tanto è maggiore la loro distanza. La t che precede l’SNE corrisponde alla t-student

 

 

 

 

Implementiamolo con Python

Non dobbiamo far altro che richiamare dalle librerie Scikit:

from sklearn.manifold import TSNE

Dove TSNE presenta i seguenti parametri (obbligatori ed opzionali) di cui esamineremo i più rilevanti:

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: di default settato a 2, rappresenta il numero di dimensioni finali

 

  • perplexity: è il parametro principale del nostro metodo; più è grande maggiore sarà il numero di vicini che prendermo in esame. È buona norma utilizzare dei parametri fra 5 e 50 per testare.

Attenzione!

 

Una perplessità troppo piccola rischia di non catturare sufficienti vicini, contrariamente un intorno eccessivo fa avvicinare valori che in realtà sono distanti, Si consiglia con large dataset di aumentare il parametro perplessità.

 

 

  • learning_rate: (dovrebbe variare da 10 a 1000) per settare correttamente questo parametro bisogna tener conto dei casi estremi:

Se i dati si concentrano in una forma quasi equidistante significa che è stato impostato un valore eccessivamente grande e bisogna ridurlo.

Contrariamente al verificarsi di un forte concentramento dei dati con qualche outliers è buona norma aumentare il grado di learning rate.

 

 

Applichiamolo su dati reali:

Dataset MNIST, costituito da oltre 60.000 immagini di numeri scritti a mano

Importiamo i pacchetti ed i dati necessari

%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

A questo punto facciamo una prima riduzione di dimensionalità con la PCA (utile quando vi sono molti dati addensati, contrariamente SVD con dati sparsi)

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]]

Facciamo dunque partire il nostro t-SNE impostando come livello di perplessità un 40, dopo vari tentativi

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

Vogliamo a questo punto plottare i nostri dati cosi ottenuti

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) &amp;amp;amp;amp;lt; 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)

Il risultato che otteremo sarà il seguente:

t-SNE ottenuto in 17.51s

 

Confrontandolo con altri strumenti di Riduzione di dimensionalità è possibile constatare due grosse tematiche:

 

  1. l’effettiva capacità discriminante

Naturalmente settare correttamente questa serie di parametri non è sempre facile.

Per questo motivo vogliamo riportare un link dove si può “giocare” a modificar i principali parametri visualizzando in tempo reale la disposizione del dato (tenendo a mente che i dati sono simulati e quindi conosciuti a priori)

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

 

 

  1. I tempi di esecuzione

Contrariamente ad altri metodi t-SNE assorbe un quantitativo di tempo e risorse maggiore. Occorre valutare quindi quale se nelle analisi in gioco il fattore tempo risulti una variabile significativa.

Vogliamo comunque dar degli spunti per superare in parte questo problema proponendo due articoli provenienti dai dipartimenti di Computer Science dell’università della 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

 

 

 

Riferimenti