Articoli

Introduzione a Metodi di riduzioni della Dimensionalità ed elementi di Algebra lineare [Parte 2]

 

Autore: Matteo Alberti

                            

Sommario

Metodi lineari per la riduzione: 2

Identificazione attraverso l’individuazione di sottospazi 2

Approssimazioni Matriciali per la riduzione. 10

Casi di applicazione base: Decomposizione in Valori Singolari (SVD). 11

Norme Matriciali 11

Norme vettoriali 13

Norme indotte. 13

Norme di Schatten. 13

Norma di Frobenius. 13

Casi di applicazione base: Analisi dei Cluster. 16

Definizione di metrica. 16

Distanze di Minkowski (Manhattan, Euclidea, Lagrange). 16

 

 

 

Lo scopo di questo primo tutorial è di introdurre le nozioni base di riduzione della dimensionalità dal punto di vista matematico (spazi, sottospazi, mappe lineari) e di riprendere gli elementi necessari di algebra lineare (norme, isometria, isomorfismo…) per ogni algoritmo di machine learning.

 

Norme Matriciali

 

Abbiamo a questo punto impostato il problema della riduzione della dimensionalità dei dati come un problema di approssimazione tra matrici, dobbiamo a questo punto andar a stabilire valutare e quindi calcolare la distanza fra la matrice dei dati originari e quella approssimante attraverso lo studio delle differenti norme:

Esistono tre principali tipologie di norme:

  • Norme vettoriali
  • Norme indotte
  • Norme di Schatten

Dove nel campo dell’analisi dei dati essenzialmente ci si riconduce, salvo eccezioni, alla norma di Frobenius (distanza euclidea)

 

 

 

 

Elementi di algebra:

Norma

Una norma (comunemente contrassegnata con ) è una funzione dallo spazio vettoriale delle matrici se:

 

Art2 1

 

Norme vettoriali

 

La famiglia delle norme vettoriali trattano la matrice X_n_x_k  come un vettore di nk componenti dove possiamo definire la norma utilizzando una delle qualsiasi norme seguenti:

art2 imagr2

Nota:

Ponendo p=2 ci si ricollega alla norma euclidea

 

Norme indotte

 

Una matrice X_n_x_k  può essere vista come un operatore lineare da   R^k \mapsto R^n .

Misurando in R^k  le lunghezze con una norma fissata e facciamo altrettanto in R^n , con una differente norma, possiamo andare a misurare quanto X allunga o accorcia un vettore , confrontando la norma di v  \in R^k con la relativa norma della sua immagine Xv.

La norma indotta  \parallel X \parallel _k _n  risulta definita come:

 

art2 3

Norme di Schatten

 

La norma di Schatten, di ordine p, di una matrice X è data semplicemente da:

Art2 4

Dove \omega_i  sono i valori singolari

 

 

Norma di Frobenius

 

La norma di Frobenius della nostra matrice  X_n_x_k di partenza è data da:

ART25

 

 

Andando a svolgere i conti, esplicitando il prodotto matriciale si ottiene:

art6.art2

Ne corrisponde che la norma di Frobenius è pari alla radice quadrata della somma del quadrato degli elementi ossia una norma euclidea vista come un vettore che coincide con la norma vettoriale di X di ordine 2.

 

 

 

 

 

Elementi di algebra:

Traccia

L’operatore traccia, indicata con Tr \left ( . \right ), è definita come la somma degli elementi diagonali della matrice argomento

 

 

 

 

 

 

 

 

Casi di applicazione base: Analisi dei Cluster

 

La cluster analysis e’ una tecnica di analisi multivariata attraverso la quale e’ possibile raggruppare le unità statistiche, in modo da minimizzare la “lontananza logica” interna a ciascun gruppo e di massimizzare quella tra i gruppi.

Rientra fra le tecniche di apprendimento non supervisionato.

Nasce quindi spontaneo dover definire che cosa si intende per lontananza logica ed in base a quale metrica.

 

 

 

Definizione di metrica

Sia  X^-\in R^p ed Y^-\in R^p definiamo metrica una funzione tale che   R^p x R^p\mapsto R^+   U\left \{ 0 \right \} 

che goda delle seguenti proprietà:

  •  d \left ( X^-, Y^- \right ) \geq O non negativa
  •  d \left ( X^-, Y^- \right ) = d \left ( Y^-,X^- \right ) simmetria
  •  d \left ( X^-, Y^- \right ) = 0 \leftrightarrow X= Y identità
  •  d \left ( X^-, Y^- \right ) \leq d \left ( X^-, Z^- \right ) + d \left ( Z^-, X^- \right )   diseguaglianza triangolare

 

Distanze di Minkowski (Manhattan, Euclidea, Lagrange)

 

Andiamo a questo punto ad analizzare i casi principali delle distanze appartenenti alla famiglia delle distanze di Minkowski dove:

art27

Evidenziamo i seguenti casi:

  • k=1 Distanza di Manhattan
  • k=2  Distanza Euclidea
  • k\rightarrow \infty Distanza Lagrangiana (Čebyšëv)

In particolare:

 

 

euclidea

Riprendendo dunque con l’esempio della Cluster Analysis, risulta fondamentale quindi definire il tipo di distanza con cui vogliamo affrontare la nostra analisi.

Principalmente nei pacchetti già implementati si trovano le tre varianti delle distanze di Minkowski (per variabili quantitative)

Importando da sklearn:

AgglomerativeClustering(n_clusters=2, affinity=’euclidean’, memory=None, connectivity=None, compute_full_tree=’auto’, linkage=’ward’

 

 

distanze

 

 

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