Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Algoritmi di predizione su grafi pesati

Tesi di laurea Giovanni Zappella
by

Giovanni Zappella

on 25 April 2010

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Algoritmi di predizione su grafi pesati

Problema binario di classificazione
possibili
Applicazioni Online Majority Vote WTA Spanning
Trees Una misura di regolarita'
per il labelling del grafo Label Propagation Algoritmi
di Predizione Predittori su grafo
Predittori su albero GPA Garanzie
teoriche grazie per la cortese attenzione Resistenza come
distanza sul grafo Conclusioni Possibili sviluppi L'utilizzo di pesi offre un vantaggio dal punto di vista dell'accuratezza

WTA possiede solide basi teoriche ed ottime performance

GPA risulta piuttosto lento e spesso poco accurato in fase di predizione

OMV e Label Propagation non offrono garanzie sulle prestazioni Da "Fast prediction on a Tree" a "Fast Prediction on a Graph"

Utilizzo di diverse strategie di ensemble per i comitati

Valutazione delle performance di questi algoritmi in contesti di "Active Learning"
Herbster et al. utilizzano l'albero come approssimazione del
grafo per il calcolo veloce della pseudoinversa del Laplaciano Esperimenti Grafi d'interazione tra proteine
Pagine web SPAM/HAM
Reti sociali Votazione a maggioranza pesata tra i vicini del nodo richiesto con etichetta rivelata

Ad un maggiore peso dell'arco corrisponde una maggiore importanza del vicino cui esso e' collegato Apprendimento trasduttivo su grafo Focus sul lavoro
sperimentale Il metodo di Gutman e Xiao ci permette di ottenere la pseudoinversa del Laplaciano del grafo in tempo quadratico data la matrice delle resistenze del grafo

Sull'albero la matrice delle resistenze si puo' calcolare in tempo quadratico Graph Perceptron Algorithm Effettua un'operazione di embedding del grafo in uno spazio vettoriale Effettua una fase d'inizializzazione con una discesa ricorsiva sull'albero per calcolare la resistenza tra un nodo ed i suoi discendenti

Dividiamo il calcolo della resistenza totale per un nodo come somma della resistenza verso i nodi a livelli inferiori e quella verso nodi a livelli superiori

Conoscendo la diagonale del Laplaciano calcoliamo i valori rimanenti per completare la matrice Diffonde le etichette moltiplicando la matrice dei pesi normalizzata per il vettore delle etichette

Ad ogni passo le etichette rivelate vengono sovrascritte
Fino a convergenza: Raggiunta la convergenza: L'etichetta del nodo i e' data dal segno del valore del vettore delle etichette nella posizione i L'utilizzo dei pesi offre un vantaggio ai predittori

WTA ha un tasso d'errore costantemente inferiore rispetto a quello di GPA

LABPROP e OMV hanno buone prestazioni ma non hanno garanzie prestazionali

La complessita' in tempo di LABPROP potrebbe essere un problema serio Effettua una linearizzazione dell'albero e poi predice le etichette con un metodo Nearest Neighbor sulla line Facendo attenzione ad alcuni accorgimenti implementativi, l'algoritmo ha tempo ammortizzato costante Possiede solide basi teoriche Mistake bound GPA Mistake bound WTA Dipende da numero di archi phi, bilanciamento del labelling e diametro Dipende dalla regolarita' del grafo Kernel dato dalla pseudoinversa del Laplaciano del grafo me@giovannizappella.com I dati precedenti sono stati presentati in:

N. Cesa-Bianchi, C. Gentile, F. Vitale, G. Zappella - "Fast and Optimal Algorithms for Weighted Graph Prediction" in NIPS 2009 workshop “Analyzing Networks and Learning with Graphs”

N. Cesa-Bianchi, C. Gentile, F. Vitale, G. Zappella - "Random Spanning Trees and the Prediction of Weighted Graphs" to appear in ICML 2010





Problema: determinare le etichette dei nodi del grafo Il grafo e' interamente conosciuto

Divisione training set / test set

Richiesta delle etichette
binarie Modello mistake
bound Laplaciano L = D - W Esempi limite sul
numero di
errori l'avversario richiede una label al predittore

viene predetta un'etichetta per l'esempio

l'avversario rivela l'etichetta dell'esempio richiesto Ottimo a meno di un fattore logaritmico Il diametro dell'albero e' maggiorato come il doppio del diametro del grafo in distanza geodesica Maggiore irregolarita' maggiori difficolta' in fase di predizione Il reciproco del peso di ogni arco e' il resistore R Sotto alcune semplici condizioni il mistake bound si puo' scrivere come:
Full transcript