Icone color1 07

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

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 *