Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D La Corte in Rete
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Massimo Brescia » 27.Tecnologie di indagine scientifica in Astrofisica - parte quarta


SVM – Support Vector Machines

Le Support vector machines (SVM) sono un insieme di metodi di apprendimento supervisionato che possono essere utilizzati sia per fare classificazione sia per fare regressione. In un breve lasso temporale dalla loro prima implementazione hanno trovato numerose applicazioni in un nutrito varie branche scientifiche come fisica, biologia, chimica.

  • preparazione di farmaci (discriminazione tra leganti e non leganti, inibitori e non inibitori, etc.),
  • Ricerca di relazioni quantitative sulle attività di strutture dove le SVM, utilizzate come regressori sono usate per trovare varie proprietà fisiche, biologiche e chimiche),
  • Chemiometria (optimizazione della separazione cromatografica o per la misura della concentrazione di un composto basandosi sui dati spettrali ad esempio),
  • Sensori (per ottenere informazioni su parametri non realmente misurati dal sensore ma di interesse),
  • Ingegneria chimica (ricerca degli errori e modellazione dei processi industriali),
  • etc. (ad esempio riconoscimento di volti in una foto o in un filmato, utilizzato da alcuni aeroporti americani per individuare ricercati)

SVM Classification

I modelli SVM furono originariamente definiti per la classificazione di classi di oggetti lineramente separabili. Per ogni gruppo di oggetti divisi in due classi una SVM identifica l’iperpiano avente il massimo margine di separazione, nella figura a destra potete vedere come la linea verde non separa le due classi, la linea blu le separa ma con un piccolo margine mentre la linea rossa massimizza la distanza delle due classi.

Nella seconda figura l’iperpiano H1 definisce il bordo della classe i cui oggetti sono rappresentati dai “+1″ mentre l’iperpiano H2 quello degli oggetti rappresentati dai “-1″.

Potete notare che due oggetti della classe “+1″ servono a definire H1 (sono quelli cerchiati) e ne servono tre della classe “-1″ per definire H2; questi oggetti vengono chiamati “support vectors”, quindi il nostro problema di identificare la miglior separazione tra le due classi è risolto individuando i vettori di supporto che determinano il massimo margine tra i due iperpiani.

Fonte: Wikipedia

Fonte: Wikipedia

Fonte: Ivanciuc

Fonte: Ivanciuc


SVM Classification

In un piano le combinazioni di tre punti possono essere separate da una linea però già quattro punti non è detto che lo siano. Fonte: Ivanciuc

In un piano le combinazioni di tre punti possono essere separate da una linea però già quattro punti non è detto che lo siano. Fonte: Ivanciuc


SVM Classification

Ovviamente le SVM possono essere usate per separare classi che non potrebbero essere separate con un classificatore lineare, altrimenti la loro applicazione a casi di reale interesse non sarebbe possibile. In questi casi le coordinate degli oggetti sono mappate in uno spazio detto “feature space” utilizzando funzioni non lineare, chiamate “feature function” Φ. Il feature space è uno spazio fortemente multidimensionale in cui le due classi possono essere separate con un classificatore lineare.

Quindi lo spazio iniziale viene rimappato nel nuovo spazio, a questo punto viene identificato il classificatore che poi viene riportato nello spazio iniziale, come illustrato in figura.

Fonte: Stefano Cavuoti

Fonte: Stefano Cavuoti


SVM Classification

La funzione Φ combina quindi lo spazio iniziale (le caratteristiche originali degli oggetti) nello spazio delle features che potrebbe in linea di principio avere anche dimensione infinita. A causa del fatto che questo spazio ha molte dimensioni non sarebbe pratico utilizzare una funzione generica per trovare l’iperpiano di separazione, quindi vengono usate delle funzioni dette “kernel” e si identifica la funzione Φ tramite una combinazione di funzioni di kernel.
L’implementazione più famosa delle SVM (libSVM) usa quattro possibili kernel:

  • Lineare: K(x_i,x_j) = x_i ^T x_j
  • Polinomiale: K(x_i,x_j) = (\gamma x_i ^T x_j + r)^d,\gamma >0
  • RBF (radial basis function): K(x_i,x_j) = \exp (-\gamma\parallel x_i - x_j\parallel^2),\gamma>0
  • Sigmoidale: K(x_i,x_j) = \tanh (\gamma x_i ^T x_j + r)
Fonte: Ivanciuc

Fonte: Ivanciuc

Fonte: Imtech

Fonte: Imtech


SVM Toy

Questo è una semplicissima applicazione sviluppato dai creatori delle libSVM: Chih-Wei Hsu, Chih-Chung Chang e Chih-Jen Lin che permette di illustrare il funzionamento delle libSVM in maniera forse più chiara, premendo col mouse si tracciano dei punti sullo schermo, premendo su change si cambia la classe (ed il colore dei punti relativo) infine premendo su run una semplice SVM attribusce al piano l’appartenenza alle varie classi mostrandole colorate in maniera diversa.

Fonte: Csie

Fonte: Csie


SVM Classificazione

Per mostrare la capacità delle SVM di creare classificatori anche nel caso non lineare e valutare l’importanza della scelta del kernel giusto consideriamo come esempio la tabella qui a fianco, è un piccolissimo dataset di 15 oggetti con due parametri appartenenti a due classi chiamante +1 e -1, nelle figure che seguiranno la classe +1 sarà rappresentata da un + mentre la classe -1 da un punto nero. L’iperpiano trovato dalle SVM sarà rappresentato da una linea continua I vettori di supporto saranno cerchiati per individuarli meglio e il margine che individuano sarà tracciato con una linea tratteggiata.

Fonte: Ivanciuc

Fonte: Ivanciuc


SVM Classificazione

Come si può vedere, il kernel lineare non è assolutamente adatto a questo esempio mentre gli altri 4 riescono a discriminare le due classi perfettamente ma possiamo notare come le soluzioni siano molto differenti l’una dall’altra, è importante quindi avere un set di prova che permetta di scegliere la migliore configurazione in modo da evitare quello che si chiama usualmente “over-fitting” che significa che l’algoritmo si adatta molto ai dati con cui è addestrato ma non riesce poi a generalizzare il problema.
Si può notare inoltre che eccezion fatta per il kernel lineare parliamo non di funzioni semplici ma famiglie di funzioni, che dipendono da un certo numero di parametri (detti usualmente “hyper-parameters”) questo se da un lato ci dà maggiori speranze di individuare la soluzione ottimale dall’altro complica il nostro lavoro di ricerca dal momento che dobbiamo cercare il kernel con i migliori parametri.

Fonte: Ivanciuc

Fonte: Ivanciuc


SVM Regression

Le Support vector machines, che come detto nascono per risolvere problemi di classificazione, furono estese da Vapnik al problema della regressione.
Il set di parametri con cui si addestra la rete è utilizzato per ottenere un modello di regressione che può essere rappresentato come un ipertubo di raggio e, che sarà quindi un hyper-parametro, “fittato” ai dati. Nel caso ideale, la regressione tramite le SVM trova una funzione che mappa tutti i dati di input con una deviazione massima pari proprio ad e, dal valore del “target”. In questo caso tutti i punti con cui si addestrano le SVM si trovano all’interno del tubo di regressione. Comunque, usualmente non è possibile “fittare” tutti gli oggetti all’interno del tubo e avere ancora un modello che abbia un qualche significato quindi nel caso generale le SVM in modalità di regressione considerano zero l’errore per gli oggetti all’interno del tubo mentre quelli all’esterno hanno un errore che dipende dalla distanza dal margine del tubo.

Fonte: Ivanciuc

Fonte: Ivanciuc


SVM Regression

Una funzione lineare è chiaramente di praticamente nessuna utilità quindi non lo considereremo negli esempi che seguiranno, ancora una volta andiamo a prendere un semplice dataset, gli oggetti saranno indicati con un +, i vettori di supporto saranno cerchiati, l’iperpiano delle SVM sarà rappresentato con una linea continua e i margini del tubo di regressione con una linea tratteggiata.
Immaginiamo di aver fatto vari addestramenti che hanno indicato che un kernel polinomiale di secondo grado è quello che ci offre un buon modello e vediamo l’influenza del parametro e sul risultato. Quando il parametro è troppo piccolo il diametro del tubo è ovviamente piccolo forzando tutti gli oggetti ad essere al di fuori del tubo.
Questo vorrà dire che avranno un grosso errore e saranno quindi male interpretati.

Fonte: Ivanciuc

Fonte: Ivanciuc


SVM Regression

We can see how the variation of the radius changes the curvature. Fonte: Ivanciuc

We can see how the variation of the radius changes the curvature. Fonte: Ivanciuc


SVM Regression

Potete notare come l’uso di kernel più complessi faccia variare enormemente la forma del tubo. Fonte: Ivanciuc

Potete notare come l'uso di kernel più complessi faccia variare enormemente la forma del tubo. Fonte: Ivanciuc


SVM riassunto

Le SVM come abbiamo visto nascono come un modello supervisionato, deterministico per fare classificazione tra 2 classi (in quasi tutte le implementazioni attuali si lavora fino a 3 classi).
Abbiamo pure visto un esempio di come siano state riadattate per permettere di fare regressione, ad oggi esistono moltissime varianti delle SVM implementate nei più disparati linguaggi (c++, java, python, matlab ed R per citare le sole libSVM).
Ne esistono ad esempio implementazioni che permettono di fare classificazione a molti classi, non supervisionate per fare clustering, versioni che accettano come input del testo o delle immagini, per non parlare delle miriadi di implentazioni di kernel differenti, tra cui uno che permette di usare l’algoritmo delle svm per riprodurre una MLP.
Il punto forte delle SVM è che dato un generico problema a patto di scegliere accuratamente il kernel (e tutti i suoi parametri) è sempre risolvibile (non fosse altro che andando a fare un overfitting totale del dataset di input).
Il problema è che scala abbastanza male con la grandezza del dataset, gli viene attribuito classicamente un fattore D2 anche se in tal senso esistono implementazioni più veloci e si cerca di ottimizzare quest’aspetto, oltre a questo il problema è identificare il miglior kernel e dotarlo dei parametri migliori, parliamo di un “neverending work” dal momento che nella migliore delle ipotesi i parametri sono i numeri interi positivi, vedremo in seguito una possibile maniera di affrontare questo fatto.

PPS – Probabilistic Principal Surfaces

Questo metodo appartiene alla famiglia dei cosiddetti metodi delle variabili latenti, partendo dal metodo classico dell’analisi delle componenti principali si nota facilmente che le PCA hanno un limite: la riduzione lineare non è sempre efficace come si può vedere nel semplice esempio dove vediamo come la stessa aggregazione di punti viene vista da una PCA, da varie PCA e con una soluzione non lineare.

Le PPS in prima istanza si preoccupano di fornire una soluzione a questo problema.
In pratica una PPS viene addestrata a riconoscere le migliori funzioni di proiezione dallo spazio N-dimensionale dei parametri ad una superfice sferica in uno spazio tridimensionale; questa superficie è ricoperta da una griglia di variabili latenti, ovvero punti, ognuno dei quali rappresenta il picco di una gaussiana nello spazio N-parametrico. Questo permette di visualizzare il tutto con un grafico tridimensionale indipendentemente dal numero di parametri iniziali e in questo modo l’essere umano può iniziare a controllare l’esistenza o meno di strutture, strutture che così riesce a visualizzare ma che non riuscirebbe neanche ad immaginare senza fare questo lavoro.

Fonte: Kui-yu Chang, A Unified Model for Probabilistic Principal Surfaces

Fonte: Kui-yu Chang, A Unified Model for Probabilistic Principal Surfaces


PPS – Algoritmo

Affrontiamo ora l’algoritmo che sta alla base delle PPS in maniera più rigorosa.

L’obiettivo di ogni modello basato sulle variabili latenti è quello di esprimere la distribuzione p(\mathbf{t}) delle variabili \mathbf{t}=(t_{1},\ldots,t_{D}) \in \mathbb{R}^{D} in termini di un numero variabili latenti minore di quello originario \mathbf{x}=(x_{1},\ldots,x_{Q}) \in \mathbb{R}^{Q} dove Q <D. Per raggiungere questo scopo la distribuzione congiunta p(\mathbf{t},\mathbf{x}) viene decomposta nel prodotto della distribuzione di margine p(\mathbf{x}) delle variabili latenti e la distribuzione condizionata p(\mathbf{t}|\mathbf{x}).
E’ conveniente esprimere la distribuzione condizionata come la fattorizzazione sulle variabili originarie, in questo caso la distribuzione di congiunzione diviene:

p(\mathbf{t},\mathbf{x})=p(\mathbf{x})p(\mathbf{t}|\mathbf{x})=p(\mathbf{x})\prod_{d=1}^{D}p(t_{d}l\mathbf{x})

La distribuzione condizionata p(\mathbf{t}|\mathbf{x}) viene quindi espressa in termini di una mappatura dalle variabili latenti alle variabili originarie, cosicchè \mathbf{t}=\mathbf{y}(\mathbf{x};\mathbf{w})+\mathbf{u}.

PPS – Algoritmo

dove  \mathbf{y}(\mathbf{x};\mathbf{w}) è una funzione delle variabili latenti \mathbf{x} con parametri \mathbf{w}, e \mathbf{u} è un rumore indipendente dalle \mathbf{x}. Se le componenti di \mathbf{u} sono scorrelate, la distribuzione condizionata per \mathbf{t} sarà fattorizzabile come abbiamovisto prima. Dal punto di vista geometrico, la funzione \mathbf{y}(\mathbf{x};\mathbf{w}) definisce una varietà nello spazio dei dati dato dall’immagine dello spazio latente. La definizione di modello a variabili latenti necessita per essere completo di specificare la distribuzione p(\mathbf{u}), la mappatura \mathbf{y}(\mathbf{x};\mathbf{w}), e la distribuzione di margine p(\mathbf{x}). Il tipo di mappatura \mathbf{y}(\mathbf{x};\mathbf{w}) determina quale particolare modello di variabili latenti si utilizza. Il modello desiderato per la distribuzione p(\mathbf{t}) dei dati è quindi ottenuta integrando sulle variabili latenti:
p(\mathbf{t})=\int p(\mathbf{t}|\mathbf{x})p(\mathbf{x})d\mathbf{x}.

PPS – Algoritmo

Questa integrazione non è a priori trattabile analiticamente, è possibile farlo solo se le distribuzioni p(\mathbf{t}|\mathbf{x})p(\mathbf{x}) hanno forme particolari.

Le PPS definiscono una mappatura parametrica non lineare \mathbf{y}(\mathbf{x};\mathbf{W}), dove \mathbf{y} è continua e derivabile, che proietta ogni punto nello spazio delle variabili latenti in un punto dello spazio originario. Poichè lo spazio delle variabili latenti è Q-dimensionale, questi punti saranno confinati in una varietà inclusa, non linearmente, nello spazio D-dimensionale delle variabili originarie. Questo implica che i punti proiettati vicino a un nodo della superficie avranno maggior influenza su questo nodo dei punti proiettati lontano da esso.

PPS – Algoritmo

Ognuno di questi nodi mathbf{y}(\mathbf{x};\mathbf{w} , \mathbf{x}\in \{\mathbf{x}_m\}_{m=1}^M ha una covarianza espressa da:

\mathbf{\Sigma}(\mathbf{x})=\frac{\alpha}{\beta}\sum_{q=1}^Q\mathbf{e}_{q}(\mathbf{x})\mathbf{e}_{q}^{T}(\mathbf{x})+\frac{(D-\alpha Q)}{\beta (D-Q)}\sum_{d=Q+1}^{D}\mathbf{e}_{d}(\mathbf{x})\mathbf{e}_{d}^{T}(\mathbf{x}), 0<br />
<ul><br />
	<li>[tex]\{\mathbf{e}_{q}(\mathbf{x})\}_{q=1}^{Q} è il set di vettori ortonormali tangenti alla varietà in \mathbf{y}(\mathbf{x};\mathbf{w}),

  • \{\mathbf{e}_{d}(\mathbf{x})\}_{d=Q+1}^{D} è il set di vettori ortonormali ortogonali alla varietà in. \mathbf{y}(\mathbf{x};\mathbf{w}). Il set completo di vettori ortonormali \{\mathbf{e}_{d}(\mathbf{x})\}_{d=1}^{D} appartiene a \mathbb{R}^D e il parametro \alpha è un fattore di bloccaggio e determina l’orientamento della matrice di covarianza.\mathbf{\Sigma}(\mathbf{x}) = \left\{\begin{array}{ccc}0< \alpha <1 & & \perp \mbox{alla varieta' }\\\alpha = 1 & & \mbox{$I_D$ o sferico } \\ 1<\alpha</li>

PPS – Algoritmo

Per stimare i parametri \mathbf{W}\beta si usa l’algoritmo Expectation–Maximization (EM), mentre il fattore di bloccaggio è fissato e si assume essere costante durante le iterazioni dell’EM. In uno spazio latente 3D, allora, una varietà sferica può essere costruita utilizzando una PPS con nodi \{\mathbf{x}_m\}_{m=1}^M disposti regolarmente sulla superfice di una sfera nello spazio latente \mathbb{R}^3.

Le coordinate della varietà latente {\mathbf{\hat{x}}}_n di ogni punto {\mathbf{t}}_n sono calcolate come: {\mathbf{\hat{x}}}_n\equiv\langle {\mathbf{x}}|{\mathbf{t}}_n\rangle=\int{\mathbf{x}}p({\mathbf{x}}|{\mathbf{t}})d{\mathbf{x}}=\sum_{m=1}^M r_{mn{\mathbf{x}}_m

dove r_{mn} sono le variabili latenti responsibilities definite come:

{ll}r_{mn}=p(\mathbf{x}_m|\mathbf{t}_n)=& \frac{p(\mathbf{t}_n| \mathbf{x}_m)P(\mathbf{x}_m)}{\sum_{m\prime=1}^{M}p(\mathbf{t}_n| \mathbf{x}_{\prime})P(\mathbf{x}_{m\prime})}=\\& =\frac{p(\mathbf{t}_n|\mathbf{x}_m)}{\sum_{m\prime=1}^{M}p(\mathbf{t}_n|\mathbf{x}_{m\prime})}

Poichè \|\mathbf{x}_m\|=1 and \sum_{m} r_{mn} = 1, for n=1,\ldots,N, questi punti giacciono in una sfera unitaria, cioè \|{\mathbf{\hat{x}}}_n\|\leq 1.

PPS – Algoritmo

(a) Rappresentazione schematica della varietà sferica nello spazio latente tridimensionale R3, (b) la stessa varietà distorta nello spazio dei parametri RD con i punti associati ai dati, (c) la proiezione della distribuzione dei punti sulla superficie della varietà sferica sullo spazio latente R3.

Una questione interessante è la stima dell’incidenza di ogni parametro dei dati di ingresso sulle variabili latenti che aiuta a comprendere la relazione tra il parametro e i cluster trovati. L’incidenza dei parametri è calcolata valutando la densità di probabilita delle componenti dei vettori di ingresso rispetto a ogni variabile latente. Più precisamente, sia \{\mathbf{t}_n\}_{n=1}^N il set dei dati di ingresso D-dimensionali, cioè \mathbf{t}_n=(t_{n1},\ldots,t_{nD}) \in \mathbb{R}^D, e \{\mathbf{x}_m\}_{m=1}^M sia il set delle variabili latenti con \mathbf{x}_m \in \mathbb{R}^3.

Fonte: Physychom

Fonte: Physychom


PPS – Algoritmo

Per ogni dato \mathbf{t}_n=(t_{n1},\ldots,t_{nD})

vogliamo calcolare p(t_{ni}/t_{n1},\ldots,t_{ni-1},t_{ni+1},\ldots,t_{nD},\mathbf{x}_m), per m=1,\ldots,M e i=1,\ldots,D.

In dettaglio:

\label{ygivenyx} p(t_{ni}/t_{n1},\ldots,t_{ni-1},t_{ni+1},\ldots,t_{nD},\mathbf{x}_m)=\\ =\frac{p(t_{n1},t_{n2},\ldots,t_{nD},\mathbf{x}_m)}{p(t_{n1},\ldots,t_{ni-1},t_{ni+1} \ldots,t_{nD},\mathbf{x}_m)}=\\=\frac{p(t_{n1},\ldots,t_{nD}/\mathbf{x}_m)P(\mathbf{x}_m)}{p(t_{n1},\ldots,t_{ni-1},t_{ni+1},\ldots,t_{nD}/\mathbf{x}_m)P(\mathbf{x}_m)}= =\frac{p(t_{n1} \ldots,t_{nD}/\mathbf{x}_m)}{p(t_{n1},\ldots,t_{ni-1},y_{ni+1},\ldots,t_{nD}/\mathbf{x}_m)}.

L’ultimo termine si ottiene semplicemente poichè il numeratore è semplicemente il m-esimo termine della gaussiana ricavata dal modello delle PPS centrato su y(\mathbf{x}_m;\mathbf{W}) e varianza \Sigma_m, mentre il denominatore è lo stesso componente Gaussiano in cui l’i-esimo termine manca. Infine il valore della (\ref{ygivenyx}) sugli N dati di input, per ogni \mathbf{x}_m, è calcolato. Questo spiega perchè le PPS sferiche possono essere utilizzate come varietà di riferimento per classificare dati a molte dimensioni.

PPS – Algoritmo Easy

Durante la fase di addestramento viene creata una varietà di riferimento.

Nella fase di test, un dato mai visto dalla rete viene attribuito alla varietà sferica più vicina.

Ovviamente il concetto di più vicino implica il calcolo di una distanza tra un punto e il nodo dello spazio. Prima di questo calcolo i dati devono essere proiettati sullo spazio. Questo poiché una varietà sferica consiste di zone quadrate o triangolari, ognuna delle quali definita da tre o quattro nodi della varietà, una volta proiettato il dato viene calcolata un’approssimazione della distanza. Nelle PPS esistono tre criteri di approssimazione:

  • Nearest Neighbour: trova la minima distanza quadra da tutti i nodi della varietà;
  • Grid Projections: trova la più corta distanza di proiezione sulla griglia della varietà;
  • Nearest Triangulation: trova la proiezione più vicina alle possibili triangolazioni.

Per lo più dei tre criteri viene utilizzato Nearest Neighbour poiché tale criterio permette di valutare le distanze da ogni dato nello spazio dei parametri a tutti i nodi chiusi sulla varietà sferica; anche se è più pesante in termini di elaborazione dei dati rispetto agli altri due metodi, in pratica fornisce la più affidabile scelta del nodo (o dei nodi, qualora più di uno si trovi alla stessa distanza da un punto).

PPS – Riassunto

Le PPS sono un algoritmo non supervisionato per ridurre la dimensionalità al fine di rendere visibile all’operatore su di una sfera l’esistenza di strutture, per realizzare questo scopo fanno una sorta di quello che viene usualmente chiamato pre clustering

La motivazione che spinge a utilizzare questo metodo è che le PPS sferiche sono particolarmente adatte a gestire, per dataset particolarmente corposi, dati che si trovano sparsi pur avendo una complessità computazionale estremamente elevata.

NEC – Negentropy Clustering

Utilizzando un algortimo come le PPS per fare preclustering si ottiene un numero di cluster prefissato; in un primo stadio questo numero conviene venga tenuto alto, essendo ovviamente meglio avere un cluster ridondante, magari composto da uno o due elementi piuttosto che perderne uno fondamentale, il passo successivo è quello di dare il risultato così ottenuto in pasto un algoritmo che accorpi questi cluster, in questa lezione parleremo del NEC (Clustering Negentropico). Cos’è la Negentropia? E’ una quantità che si definisce in teoria dei segnali come la distanza dalla normalità . Il segnale viene detto normale se è una gaussiana. La Negentropia è nulla se il segnale è normale, altrimenti ha un valore maggiore di zero.
La Negentropia è una quantità invariante per ogni cambio di coordinate lineare. In pratica una NEC altro non è che una tecnica agglomerativa che serve per passare dalla clusterizzazione fatta ad esempio con le PPS a quella desiderata, usualmente si ottiene un dendogramma.


NEC – Principio

Ogni strato del dendogramma rappresenta uno dei cluster iniziali che al variare di un valore di soglia vengono mano a mano agglomerati. Può essere utile visualizzarlo in un’altra maniera disponendo da sinistra a destra i cluster che si accorpano con valori di soglia diverse (quelli a sinistra si accorperanno con bassi valori della soglia, quelli a destra con alti valori della soglia). La scelta di quale grado di accorpamento considerare resta all’utente e dipende dallo scopo della sua ricerca. Un esempio di possibile scelta è quello della ricerca dei plateau; graficando il numero di cluster in funzione del valore della soglia, la curva decrescente ottenuta potrebbe avere dei plateau, il cui significato è evidente: in quelle zone i cluster risultano ben separati e quindi è probabile che la classificazione così fatta abbia un forte significato. A questo punto abbiamo delle divisioni, però va ancora capito cosa rappresentino e qui entra in gioco la nostra conoscenza del campione che abbiamo utilizzato per addestrare la rete; difatti controllando gli oggetti di cui abbiamo informazioni ricavate per altre vie dove si dispongono possiamo dare un senso fisico ai vari cluster.

Fonte: Physychom

Fonte: Physychom

Fonte: Physychom

Fonte: Physychom


NEC – Algoritmo

La maggior parte dei metodi non supervisionati, e tra questi le PPS, richiedono che venga, in maniera diretta o indiretta seconda dei casi, fornito a priori il numero di cluster, ovviamente questo è un problema quando si sta utilizzando un data set piuttosto complesso dove il numero di cluster può essere molto grande o comunque non predicibile. Un semplice criterio di soglia non è soddisfacente nella maggior parte delle applicazioni astronomiche a causa dell’alta degenerazione e della rumorosità dei dati che possono portare a erronee agglomerazioni dei dati. Si deve quindi stabilire una definizione di distanza e un criterio di accorpamento, grazie ai quali si possa stabilire se due cluster vadano uniti o meno. Ovviamente il processo può andare avanti accorpando i cluster figli del primo accorpamento dando così luogo al dendogramma.
La NEC utilizza il discriminante lineare di Fisher che è un metodo di classificazione che prima proietta i dati a molte dimensioni su una retta, e quindi svolge la classificazione sullo spazio lineare risultante. La proiezione si attua massimizzando la distanza tra le medie di due classi e minimizzando la varianza all’interno di ogni classe.

Inoltre si definisce l’entropia differenziale H di un vettore casuale {\mathbf y} = (y_1, \ldots, y_n)^T con densità f(y) come:

H({\mathbf y}) = \int f({\mathbf y}) \log f({\mathbfy}) d{\mathbf y} cosicchè la negentropia J può essere definita come:

J(\mathbf{y}) = J({\mathbf y}_{Gauss}) - H(\mathbf{y}) dove \mathbf{y}_{Gauss} è un vettore casuale Gaussiano con la stessa matrice di covarianza di \mathbf{y}.

NEC – Algoritmo

La Negentropia può essere interpretata come una misura della non “Gaussianeità” e, poichè è invariante per trasformazioni lineari invertibili, è ovvio che trovare una trasformazione invertibile che minimizza la mutua informazione è praticamente equivalente a trovare la direzione in cui la Negentropia è massimizzata.
L’algoritmo del NEC può quindi essere usato per condurre un’agglomerazione non supervisionata dei cluster (detti anche “precluster”) trovati tramite le PPS. L’unica informazione a priori richiesta dal NEC è il valore della soglia di dissimilarità.
T. Supponiamo di avere n D-dimensionali precluster Xi con i=1,…,n che sono stati determinati dalle PPS; questi cluster sono passati alla NEC che in pratica controlla se ogni coppia di cluster contigui (secondo il discriminante lineare di Fisher) può essere o meno efficientemente rappresentata da una singola distribuzione Gaussiana multivariata. In altre parole, la NEC determina se due cluster appartenenti a una data coppia possono essere considerati sostanzialmente distinti o parti di un cluster
più grande.

Redshift Fotometrici

Il primo esempio di applicazione scentifica del DM riguarda la regressione (tramite MLP) in un campo particolarmente importante per l’astrofisica come la misura dei redshift fotometrici

L’idea è di utilizzare una rete neurale supervisionata (nella fattispecie una MLP) per ottenere dei redshift fotometrici, la procedura può essere riassunta così:

  • I set di training, validation e test sets sono stati ricavati utilizzando il campione spettroscopico della SDSS che è completo sotto una magnitudine in banda r di 17.7 mentre per le galassie più deboli contiene principalmente Luminous Red Galaxies or LRG’s.
  • Una prima MLP è addestrata a riconoscere gli oggetti più vicini (z<0.25) da quelli più distanti (0.25<0.5).
  • Quindi due reti vengono addestrate nei due differenti range di redshift.
  • Una volta che le tre reti sono state addestrate è stata processata l’intera tabella galaxy della SDSS in modo da ricavare i redshift di ogni oggetto.

Redshift Fotometrici

Il metodo ottiene risultati migliori di quelli apparsi in letteratura finora con una dispersione con una sigma robusta pari a 0.02 misurata dalla dispersione attorno allo zero della variabile scarto zphot-zspec

Fonte: Voneural

Fonte: Voneural

Fonte: Voneural

Fonte: Voneural


Classification of Active Galactic Nuclei

Il secondo esempio di applicazione scientifica che vi presento riguarda un problema di classificazione approcciato con MLP e SVM

Le classificazioni delle galssie sono basate su informazioni morfologiche che solo in parte riflettono la differenza fisica tra differenti classi di oggetti.
Un chiaro esempio è rappresentato dalle galassie che contengono AGN, che non rientrano in nessuna classificazione morfologica (fatte salve alcune lievi correlazioni). Approcciare il problema dal punto di vista del data-mining con metodi di machine learning quindi può risultare molto efficace.
Lo scopo del lavoro che verrà di seguito brevemente illustrato è trovare una maniera di scegliere le galassie che ospitano nuclei galattici attivi utilizzando solo parametri fotometrici e impiegando metodi supervisionati di classificazione, in particolare MLP e SVM su di una base di conoscenza ricavata dai parametri spettroscopici.

Fonte: NASA

Fonte: NASA


The data used for the BoK

The BoK is formed by objects residing in different regions of the BPT plot (Baldwin, Phillips and Tellevich 1981)

The BoK is formed by objects residing in different regions of the BPT plot (Baldwin, Phillips and Tellevich 1981)


The BoK

Fonte: Tesi di Stefano Cavuoti

Fonte: Tesi di Stefano Cavuoti


Photometric parameters

Photometric parameters used for training of the NNs and SVMs

Fonte: Tesi Stefano Cavuoti
Fonte: Tesi Stefano Cavuoti
Fonte: Gennaro Sorrentino, The environment of active galaxies in the SDSS-DR4


SVM

Come abbiamo detto esistono molte implementazioni delle SVM questo lavoro fa uso delle LIBSVM e di una delle implementazioni del motore di classificazione detto C-SVC il kernel scelto è l’RBF quindi va scelta la configurazione migliore per due Hyper-Parametri, C, parametro del C-SVC e il gamma delle RBF, purtroppo questi due parametri non sono sceglibili a priori quindi ho utilizzato il sistema di tuning proposto dagli autori stessi delle libSVM, che consiste nel fare girare vari esperimenti in una griglia facendo variare e gamma di un fattore quattro e partendo per C da 2 elevato alla meno 5 fino a 2 elevato alla 15 mentre gamma da 2 alla meno 15 fino a 2 elevato alla 23. Graficando l’efficienza di questi 110 processi (che è stato possibile eseguire grazie all’uso della GRID del progetto SCoPE) ho ottenuto delle curve di livello che permettono in una seconda fase di individuare le zone dove i risultati migliori giacciono e raffinare la ricerca, per l’addestramento è stato utilizzato inoltre un metodo di cross validation detto n-fold usando 5 folders.

Fonte: Tesi di Stefano Cavuoti

Fonte: Tesi di Stefano Cavuoti


Results

Checking the trained NN with a dataset of sure not AGN just 12.6% are false positive; False positive surely not AGN (according BoK) are 0.89%

Checking the trained NN with a dataset of sure not AGN just 12.6% are false positive; False positive surely not AGN (according BoK) are 0.89%


Ricerca di Candidati Quasar

Il terzo e ultimo esempio che vi propongo riguarda un problema di clustering
Quest’applicazione è volta all’individuazione di candidati quasar mediante parametri fotometrici fa uso di PPS e NEC in particolare prima individua dei precluster tramite le PPS, poi aggrega questi cluster tramite le NEC utilizzando le informazioni disponibili sugli oggetti del dataset per scegliere la migliore clusterizzazione.
Per fare questo prima di tutto diciamo che un cluster verrà chiamato di successo se la frazione di quasar confermati al suo interno è superiore ad una certa soglia
A questo punto vogliamo massimizzare il rapporto tra il numero di cluster di successo e il numero di cluster totali ottenuto (NSR,normalized success ratio).

Fonte: Raffaele D’Abrusco, Dipartimento di Astronomia, Università di Padova

Fonte: Raffaele D'Abrusco, Dipartimento di Astronomia, Università di Padova


Ricerca di Candidati Quasar

Fonte: Raffaele D’Abrusco, Dipartimento di Astronomia, Università di Padova

Fonte: Raffaele D'Abrusco, Dipartimento di Astronomia, Università di Padova

Fonte: Raffaele D’Abrusco, Dipartimento di Astronomia, Università di Padova

Fonte: Raffaele D'Abrusco, Dipartimento di Astronomia, Università di Padova


Ricerca di Candidati Quasar

Fonte: Raffaele D’Abrusco, Dipartimento di Astronomia, Università di Padova

Fonte: Raffaele D'Abrusco, Dipartimento di Astronomia, Università di Padova

Fonte: Raffaele D’Abrusco, Dipartimento di Astronomia, Università di Padova

Fonte: Raffaele D'Abrusco, Dipartimento di Astronomia, Università di Padova


Ricerca di Candidati Quasar

Fonte: Raffaele D’Abrusco, Dipartimento di Astronomia, Università di Padova

Fonte: Raffaele D'Abrusco, Dipartimento di Astronomia, Università di Padova

Fonte: Raffaele D’Abrusco, Dipartimento di Astronomia, Università di Padova

Fonte: Raffaele D'Abrusco, Dipartimento di Astronomia, Università di Padova


Le lezioni del Corso

I materiali di supporto della lezione

B. E. Boser, I. Guyon, e V. Vapnik . A training algorithm for optimal margin classifiers. Nei Proceedings of the Fifth Annual Workshop on Computational Learning Theory, pp. 144-152. ACM Press. (1992)

S. S. Keerthi e C.-J. Lin: Asymptotic behaviors of support vector machines with Gaussian kernel. Neural Computation 15 (7), 1667- 1689.(2003)

H.-T. Lin e C.-J. Lin: A study on sigmoid kernels for SVM and the training of non-PSD kernels by SMO-type methods. Technical report, Department of Computer Science, National Taiwan University. (2003)

Ovidiu Ivanciuc: Applications of Support Vector Machines in Chemistry in: reviews in computationa chemistry, volume 23, eds.: K.B. Lipkovitz and T.R. Cundari. Wiley-VCH, Weinheim, 2007, pp. 291-400

Kyu-yu Chang & J. Ghosh: A Unified Model for Probabilistic Principal Surfaces, Pattern Analysis and Machine Intelligence, IEEE Transactions on, Vol.23, Iss.1, Jan 2001 Pages:22-41 (1999)

Kyu-yu Chang & J. Ghosh: Three-Dimensional Model-Based Object Recognition and Pose Estimation Using Probabilistic Principal Surfaces, in SPIE: Applications of Artificial Neural Networks in Image, 192-203 (2000)

Kyu-yu Chang & J. Ghosh: A unified Model for Probabilistic Principal Surfaces in IEE Transactions on Pattern Analysis and Machine intelligence, 23, 22-41 (2001)

C. M. Bishop, M. Svensen & C. K. I. Williams: Neural Computation, 215-234 (1998)

C. M. Bishop: Latent variable models, in M. I. Jordan (Ed. ), Learning in Graphical Models, MIT Press, (1999)

Staiano A.: Unsupervised Neural Networks for the Extraction of Scientific Information from Astronomical Data, PhD thesis, University of Salerno (2003)

Staiano A., De Vinco L., Ciaramella A., Raiconi G., Tagliaferri R., Longo G., Miele G., Amato R., Del Mondo C., Donalek C., Mangano G., Di Bernardo D.: Probabilistic principal surfaces for yeast gene microarray data-mining, in ICDM'04 - Fourth IEEE International Conference on Data Mining, pp. 202-209, (2004)

R. D'Abrusco, A. Staiano, G. Longo, M. Brescia, M. Paolillo, E. De Filippis, R. Tagliaferri: Mining the SDSS archive. I. Photometric redshifts in the nearby universe., arXiv:astro-ph/0703108v2 9 Mar, (2007)

G. Sorrentino, M. Radovich, A. Rifatto: The environment of active galaxies in the SDSS-DR4

Materiale

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion

Fatal error: Call to undefined function federicaDebug() in /usr/local/apache/htdocs/html/footer.php on line 93