Presentazione Conclusiva Attivita Dottorato` Apprendimento...

49
Presentazione Conclusiva Attivit` a Dottorato Apprendimento supervisionato distribuito con reti neurali Candidato: Simone Scardapane Supervisore: Prof. Aurelio Uncini Elettronica e Telecomunicazioni (DIET) Dipartimento di Ingegneria dell’Informazione,

Transcript of Presentazione Conclusiva Attivita Dottorato` Apprendimento...

Page 1: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Presentazione Conclusiva Attivita Dottorato

Apprendimento supervisionato distribuitocon reti neurali

Candidato: Simone ScardapaneSupervisore: Prof. Aurelio Uncini

Elettronica e Telecomunicazioni (DIET)

Dipartimento di Ingegneria dell’Informazione,

Page 2: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Indice della sezione

1 IntroduzioneFormulazione del problemaContributi della tesi

2 Apprendimento distribuito con reti RVFLDescrizione delle reti RVFLAlgoritmi proposti e risultati

3 Apprendimento distribuito semi-supervisionatoSVM semi-supervisionate∇-S3VM distribuite

4 Apprendimento distribuito con reti ricorrentiEcho state networks distribuite

5 ConclusioniConclusione e sviluppi futuriRiepilogo attivita accademiche

Page 3: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Apprendimento supervisionato

Per apprendimento supervisionato si intende l’estrazione di una re-lazione generale a partire da un campionamento finito di suoi ele-menti.

Formalmente, cerchiamo una funzione f : Rd → Y , partendo da Nesempi di tale relazione:

S = {(x1, y1), . . . , (xN, yN)} ,

Per ogni esempio (x, y) non osservato in precedenza vorremmo f (x) ≈ y.

Possibili applicazioni:

• Regressione: in questo caso Y ⊆ R (es. predizioni finanziarie).• Classificazione (binaria): Y = {−1,+1} (es. classificazione mu-

sicale).

Page 4: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Funzioni costo ed ottimizzazione

Dato uno spazio di ipotesi (o modelli)H, il problema di apprendimentosupervisionato puo formalizzarsi come :

minf∈H

N∑i=1

l(yi, f (xi)) + λr(f ) (1)

dove l(·, ·) e una funzione di errore, r(f ) impone determinati vincoli diregolarizzazione su f , e λ > 0 e uno scalare detto fattore di regolariz-zazione.

In questa presentazione, ci limitiamo al caso r(f ) , ‖w‖22, dove w riu-

nisce i parametri di f .

[1] Evgeniou, T., Pontil, M., & Poggio, T. (2000). Regularization networks and sup-port vector machines. Advances in computational mathematics, 13(1), 1-50.

Page 5: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Apprendimento distribuito

Nel caso distribuito, supponiamo che i dati S siano distribuiti su uninsieme di L agenti, con connettivita nota. In particolare, ogni agenteha accesso ad un dataset locale:

Sk = {(xk,1, yk,1), . . . , (xk,Nk , yk,Nk)}

Nel problema di apprendimento distribuito (AD), gli agenti devonorisolvere il seguente problema di ottimizzazione:

minf∈H

L∑k=1

Nk∑i=1

l(yk,i, f (xk,i)) + λr(f ) (2)

[1] Predd, J. B., Kulkarni, S. R., & Poor, H. V. (2006). Distributed learning in wire-less sensor networks. IEEE Signal Processing Magazine, 23(4), 56-69.

Page 6: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Rappresentazione grafica

Node 1

Node 3

Node 2

Dataset

Node

Model

S3

Node 4

S1

S2 S4

Model

Input/Output

Link

Figura 1 : Apprendimento supervisionato su reti di agenti: i dati sonodistribuiti sui vari agenti, i quali devono concordare su un singolo modello.

Page 7: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Vincoli

Siamo interessati in algoritmi che rispettino i seguenti vincoli:

Privacy Non dovrebbe essere richiesto lo scambio di es-empi tra i nodi.

Communicazione Ogni agente puo comunicare solo con i suoi im-mediati vicini.

Scalabilita L’algoritmo deve scalare a grandi reti di agenti,senza vincoli sulla topologia.

Esempi di applicazioni:

• Classificazione musicale su una rete peer-to-peer.• Riconoscimento di immagini su una rete di sensori.• Inferenza su database medici distribuiti.

Page 8: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Contributi della tesi

AD con reti random vector functional-link (RVFL):• Sviluppo di algoritmi distribuiti per reti di tipo RVFL.• Uniscono la semplicita dei modelli lineari alle prestazioni di mod-

elli non-lineari piu complessi.

AD semi-supervisionato• Estensione dell’AD al caso in cui siano presenti anche dati non

etichettati ad ogni agente.

AD con reti ricorrenti• Estensione al caso di dati tempo-varianti.• Uno degli algoritmi proposti costituisce il primo algoritmo com-

pletamente distribuito per reti internamente ricorrenti.

Page 9: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Notazione

La connettivita fra agenti puo essere rappresentata da un grafo G =(V, E), dove V = {1, . . . ,L} ed E e l’insieme di connessioni fra agenti.

Consideriamo solo grafi tempo-invarianti, connessi e non orientati.

Il simbolo Nk rappresenta il vicinato inclusivo del nodo k.

Il simbolo dk rappresenta il grado del nodo k.

Infine, associamo ad ogni connessione (i, j) ∈ E uno scalare Cij > 0,che pesa l’informazione proveniente dal nodo j verso il nodo i.

Page 10: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Indice della sezione

1 IntroduzioneFormulazione del problemaContributi della tesi

2 Apprendimento distribuito con reti RVFLDescrizione delle reti RVFLAlgoritmi proposti e risultati

3 Apprendimento distribuito semi-supervisionatoSVM semi-supervisionate∇-S3VM distribuite

4 Apprendimento distribuito con reti ricorrentiEcho state networks distribuite

5 ConclusioniConclusione e sviluppi futuriRiepilogo attivita accademiche

Page 11: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Reti random vector-functional-link

Una rete RVFL e un modello a due strati che si puo formalizzare come:

f (x) =B∑

i=1

βihi(x) = βTh(x) , (3)

dove i parametri di h1(x), . . . , hB(x) sono generati stocasticamente.

x1

x2

h1

h2

h3

y

β1

β2

β3

Figura 2 : Esempio di rete RVFL con due input e tre neuroni intermedi.

[1] Igelnik, B., & Pao, Y. H. (1995). Stochastic choice of basis functions in adap-tive function approximation and the functional-link net. IEEE Transactions on NeuralNetworks, 6(6), 1320-1329.

Page 12: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Apprendimento nelle reti RVFL

Definiamo le seguenti matrici:

y = [y1, . . . , yN]T

H =[hT(x1), . . . ,hT(xN)

]TI parametri ottimi β sono dati dal seguente problema di regressionelineare:

β∗ = arg minβ∈RB

12‖Hβ − y‖2

2 +λ

2‖β‖2

2 , (4)

la cui soluzione si puo esprimere in forma chiusa come:

β∗ =(HTH + λI

)−1HTy . (5)

Page 13: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Algoritmi proposti per l’apprendimento distribuito

Nel contesto dell’apprendimento distribuito di reti RVFL, abbiamo in-vestigato due algoritmi:

1 Consensus-based RVFL: strategia euristica, nella quale gli agenticompiono una media sui propri pesi ottimi locali.

2 ADMM-based RVFL: il problema di apprendimento globale vienerisolto tramite una strategia di ottimizzazione distribuita.

In entrambi i casi, la comunicazione fra agenti avviene solo per il cal-colo di medie globali (tramite un protocollo di consenso).

I risultati mostrano come la prima strategia, pur essendo euristica, siain molti casi comparabile a quella ottimale.

[1] Scardapane, S., Wang, D., Panella, M. & Uncini, A. (2015). Distributed Learningfor Random Vector Functional-Link Networks. Information Sciences, 301, pp. 271-284.

Page 14: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Consensus-based RVFL

La prima strategia che consideriamo e estremamente semplice:

1 Inizializzazione: I parametri di h1(x), . . . , hB(x) sono scelti in manieraconcorde tra i vari agenti.

2 Allenamento locale: Ogni agente risolve il problema di apprendi-mento locale, ottenendo una stima dei pesi ottimali:

β∗k =(HT

k Hk + λI)−1

HTk yk, k = 1, . . . ,n .

3 Media: Gli agenti eseguono una media distribuita sui vettoriβ1, . . . ,βL,ottenendo:

β∗CONS =1L

L∑k=1

β∗k

Page 15: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Calcolo della media (algoritmo del consenso)

Per calcolare in maniera distribuita la media, viene usato l’algoritmodel consenso:

• Ogni agente inizializza una stima della media locale come:

βk[0] = β∗k . (6)

• Iterativamente, tale stima viene migliorata eseguendo in parallelouna media pesata sul solo vicinato:

βk[n + 1] =∑j∈Nk

Ckjβj[n] . (7)

Sotto scelte determinate dei pesi Ckj, l’algoritmo converge asintotica-mente alla media globale dei pesi di partenza.

[1] Olfati-Saber, R., Fax, A., & Murray, R. M. (2007). Consensus and cooperation innetworked multi-agent systems. Proceedings of the IEEE, 95(1), 215-233.

Page 16: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

ADMM-based RVFL

Per permettere una soluzione distribuita tramite l’Alternating DirectionMethod of Multipliers (ADMM), riscriviamo il problema come:

β∗ADMM =minimize

z∈RB

12

(L∑

k=1

‖Hkβk − yk‖22

)+λ

2‖z‖2

2

subject to βk = z, k = 1 . . . L .

(8)

A questo problema associamo una Lagrangiana aumentata:

L =12

(L∑

k=1

‖Hkβk − yk‖22

)+λ

2‖z‖2

2+

L∑k=1

tTk (βk−z)+

γ

2

L∑k=1

‖βk − z‖22 ,

(9)dove i vettori tk, k = 1 . . . L sono i moltiplicatori di Lagrange e γ > 0.

[1] Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011). Distributed opti-mization and statistical learning via the alternating direction method of multipliers.Foundations and Trends® in Machine Learning, 3(1), 1-122.

Page 17: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

ADMM-based RVFL (2)

Risolviamo il problema iterando i seguenti passi:

βk[n + 1] = arg minβk∈RB

L (z[n],β1, . . . ,βL, t1[n], . . . , tL[n]) , (10)

z[n + 1] = arg minz∈RB

L (z,β1[n + 1], . . . ,βL[n + 1], t1[n], . . . , tL[n]) (11)

tk[n + 1] = tk[n] + γ (βk[n + 1]− z[n + 1]) . (12)

I passi per βk[n + 1] e z[n + 1] possono essere scritti in forma chiusa:

βk[n + 1] =(HT

k Hk + γI)−1 (

HTk yk − tk[n] + γz[n]

), (13)

z[n + 1] =γβ + tλ/L + γ

, (14)

con β = 1L

∑Lk=1 βk[n + 1] e t = 1

L

∑Lk=1 tk[n].

Page 18: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Esperimento su image recognition

Consideriamo il database CIFAR-10, composto da 60000 immagini (50000training, 10000 test), di dimensione 32 × 32, divise equamente fra 10classi.

Elaboriamo ogni immagine estraendo 1600 patch casuali. Ognuna diesse viene rappresentata con un vettore di 1600 elementi corrispon-denti alla somiglianza con le patch (spazio di dissimilarita).

Selezioniamo B = 3000 nella rete RVFL, parametri estratti dalla dis-tribuzione uniforme in [−1,+1], λ = 10, non-linearita di tipo sig-moide, grafi generati casualmente con connettivita 0.2.

Ogni esperimento viene ripetuto 25 volte, ed i risultati mediati sullevarie ripetizioni.

[1] Scardapane, S., Wang, D., Panella, M. & Uncini, A. (2015). Distributed Learningfor Random Vector Functional-Link Networks. Information Sciences, 301, pp. 271-284.

Page 19: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Risultati

2 4 6 8 10 1235

40

45

50

55

60

65

Nodes of network

Mis

cla

ssif

. E

rror

[%]

L−RVFL

CONS−RVFL

ADMM−RVFL

C−RVFL

(a) Errore di classificazione

2 4 6 8 10 120

20

40

60

80

100

120

Nodes of network

Tra

inin

g t

ime

[sec

s]

CONS−RVFL

ADMM−RVFL

C−RVFL

(b) Tempo di training

Figura 3 : Errore di classificazione e tempo di training, variando ladimensione della rete da 2 a 12.

Page 20: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Indice della sezione

1 IntroduzioneFormulazione del problemaContributi della tesi

2 Apprendimento distribuito con reti RVFLDescrizione delle reti RVFLAlgoritmi proposti e risultati

3 Apprendimento distribuito semi-supervisionatoSVM semi-supervisionate∇-S3VM distribuite

4 Apprendimento distribuito con reti ricorrentiEcho state networks distribuite

5 ConclusioniConclusione e sviluppi futuriRiepilogo attivita accademiche

Page 21: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Apprendimento semi-supervisionato

Con apprendimento semi-supervisionato ci si riferisce al caso nelquale, oltre a dati di training S, sia presente un secondo insieme nonetichettato U = {xN+1, . . . , xN+U}.

E un problema di grande interesse nel caso in cui i dati etichettati sianodifficili (o costosi) da ottenere, mentre i dati non etichettati sono pre-senti in grande quantita.

Contributo della tesi:• Due algoritmi che permettono di risolvere problemi di apprendi-

mento semi-supervisionato distribuiti.

[1] Chapelle, O., Schlkopf, B., & Zien, A. (2010). Semi-Supervised Learning, MITPress.

Page 22: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Support vector machines (lineari)

Una support vector machine (SVM) lineare e un iperpiano f (x) =wTx + b definito da:

minw,b

C2N

N∑i=1

l (yi, f (xi)) +12‖w‖2

2 , (15)

dove la funzione di errore e definita come:

l (y, f (x)) = max (0, 1− yf (x))2, (16)

Una possibile estensione semi-supervisionata e ottenibile aggiungendole etichette sconosciute y ∈ {−1,+1}U al problema di ottimizzazione:

minw,b,y

C1

2N

N∑i=1

l (yi, f (xi)) +C2

2U

U∑i=1

l(yi, f (xi)) +12‖w‖2

2 , (17)

[1] Chapelle, O., Sindhwani, V., & Keerthi, S. S. (2008). Optimization techniquesfor semi-supervised support vector machines. Journal of Machine Learning Research, 9,203-233.

Page 23: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

∇ S3VM (semi-supervised SVM)

La∇ S3VM e una delle approssimazioni piu note per risolvere il prob-lema precedente.

In particolare, fissando w e b, il vettore ottimo y e dato da:

yi = sign(wTxi + b), i = 1, . . . ,U.

Possiamo ottenere un problema di ottimizzazione differenziabile sos-tituendo la hinge loss su U con exp

{−5f (x)2

}:

minw,b

C1

2N

N∑i=1

l (yi, f (xi)) +C2

2U

U∑i=1

exp{−5f (xi)

2}+ 12‖w‖2

2 . (18)

[1] Chapelle, O., & Zien, A. (2005). Semi-supervised classification by low densityseparation. In Proceedings of the tenth international workshop on artificial intelligence andstatistics (Vol. 1, pp. 57-64).

Page 24: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Approssimazione della hinge loss

Signed output

-2 -1 0 1 2

Lo

ss v

alue

0

0.2

0.4

0.6

0.8

1Hinge

Approximation

Figura 4 : Visualizzazione dell’approssimazione di l (y, f (x)) data daexp

{−5f (x)2}.

Page 25: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Contributo della tesi: formulazione nel casodistribuito

Seguendo le stesso setting del caso precedente, il problema distribuitopuo porsi come:

minw

L∑k=1

lk(w) +

L∑k=1

gk(w) + r(w) , (19)

dove abbiamo definito:

lk(w) =C1

2N

Nk∑i=1

l (yk,i, f (xk,i)) , (20)

gk(w) =C2

2U

Uk∑i=1

exp{−5f (xk,i)

2} , (21)

r(w) =12‖w‖2

2 . (22)

Page 26: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Soluzioni proposte

Soluzione 1: discesa al gradiente

1 - Passo di aggiornamento locale

Passo di fusione dati:

1 - Definizione funzione surrogata convessa

2 - Minimizzazione funzione surrogata

3 – Passo di aggiornamento

[ ] [ ] ( )k k kn n J ww

Soluzione 2: approssimazioni convesse successive

[ 1]kk j kw n

[1] Scardapane, S., Fierimonte, R., Di Lorenzo, P., Panella, M., & Uncini, A. (2015).Distributed semi-supervised support vector machines. Neural Networks, under review.

Page 27: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Soluzione 1: discesa al gradiente distribuita

Una prima possibilita per risolvere il problema in maniera distribuitae data da una discesa al gradiente distribuita:

ψk = wk[n]− α[n]∇Jk(w) , (23)

wk[n + 1] =∑t∈Nk

Cktψt , (24)

dove Jk(w) = lk(w) + gk(w) + 1L r(w).

[1] Tsitsiklis, J. N., Bertsekas, D. P., & Athans, M. (1986). Distributed asynchronousdeterministic and stochastic gradient optimization algorithms. IEEE Transactions onAutomatic Control, 31(9), 803-812.

[2] Bianchi, P., & Jakubowicz, J. (2013). Convergence of a multi-agent projectedstochastic gradient algorithm for non-convex optimization. IEEE Transactions on Auto-matic Control, 58(2), 391-405.

[3] Sayed, A. H. (2014). Adaptive networks. Proceedings of the IEEE, 102(4), 460-497.

Page 28: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Soluzione 2: in-network non-convex optimization

La soluzione presentata prima e molto efficiente, ma la sua velocita diconvergenza e sub-ottimale per due ragioni:

1 Considera solo derivate del primo ordine, senza considerare chela funzione costo e composta da combinazioni di termini convessie non-convessi.

2 L’informazione sulle funzioni costo di altri agenti arriva solo in-direttamente tramite il passo di combinazione.

Recentemente, si e visto come sia possibile migliorare tali performancesfruttando tale combinazione, rimpiazzando iterativamente la funzionecosto locale con un surrogato fortemente convesso.

[1] Facchinei, F., Scutari, G., & Sagratella, S. (2015). Parallel Selective Algorithmsfor Nonconvex Big Data Optimization. IEEE Transactions on Signal Processing, 63(7),1874-1889.

[2] Di Lorenzo, P., & Scutari, G. (2015). NEXT: In-Network Nonconvex Optimiza-tion. IEEE Transactions on Signal and Information Processing over Networks, under review.

Page 29: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Funzione surrogata locale

Consideriamo il seguente surrogato:

Fk(w;wk[n]) = lk(w) + gk(w;wk[n]) + r(w)

+ πk[n]T (w−wk[n]) ,(25)

dove

gk(w;wk[n]) = gk(wk[n]) +∇gTk (wk[n]) (w−wk[n]) , (26)

e πk(wk[n]) e definita da:

πk[n] ≈∑t6=k

∇hk(wk[n]) , (27)

con ∇hk(·) = ∇lk(·) +∇gk(·).

Page 30: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Algoritmo NEXT (prima fase)

Nella prima fase dell’algoritmo, ogni agente risolve la propria fun-zione surrogata, ottenendo una nuova stima wk[n].

In seguito, una variabile ausiliaria zk[n] e calcolata come:

zk[n] = wk[n] + α[n] (wk[n]−wk[n]) . (28)

Infine, viene eseguito un passo di consenso per ottenere la nuova stimadei pesi ottimali:

wk[n + 1] =∑t∈Nk

Cktzk[n] . (29)

Page 31: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Algoritmo NEXT (seconda fase)

L’aggiornamento della stima di πk[n] avviene in due sotto-fasi distinte:

1 Una variabile ausiliaria vk[n] viene aggiornata come:

vk[n + 1] =∑t∈Nk

Cktvt[n] +(∇hk(wk[n + 1])−∇hk(wk[n])

). (30)

2 Le variabili πk[n] sono aggiornate come:

πk[n + 1] = Nvk[n + 1]−∇hk(wk[n + 1]) . (31)

[1] Zhu, M., & Martınez, S. (2010). Discrete-time dynamic average consensus. Au-tomatica, 46(2), 322-329.

Page 32: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Setup sperimentale

Consideriamo una derivazione di GARAGEBAND, dove l’obiettivoe distinguere fra canzoni ‘rock’ e ‘pop’ partendo da un vettore di 49feature.

Eseguiamo una 10-fold cross-validation ripetuta 15 volte.

Tutti i problemi di ottimizzazione sono risolti con una discesa al gra-diente, dove fissiamo T = 500 iterazioni massime. Ai fini del con-fronto, l’ottimizzazione si arresta se la norma del gradiente e minoredi 10−5.

Gli step size sono scelti come:

α[n] =α[0]

(n + 1)δ.

Page 33: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Risultati (1/2)

Iteration

0 10 20 30 40 50

Obje

ctiv

e fu

nct

ion

3

4

5

6

7

C-NS3VM

DG-NS3VM (25 NODES)

NEXT-NS3VM (25 NODES)

(a) Funzione obiettivoIteration

0 100 200 300 400 500

Gra

die

nt

norm

10-3

10-2

10-1

100

101

102

C-NS3VM

DG-NS3VM (25 NODES)

NEXT-NS3VM (25 NODES)

(b) Norma del gradiente

Figura 5 : Evoluzione della funzione obiettivo e della norma del gradiente suuna rete di 25 agenti.

Page 34: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Risultati (2/2)

Number of nodes

5 10 15 20 25 30 35 40

Cla

ssif

icati

on

Err

or

0.22

0.24

0.26

0.28

0.3

0.32

0.34

LIN-SVM

RBF-SVM

C-NS3VM

DG-NS3VM

NEXT-NS3VM

(a) Errore di classificazioneNumber of nodes

5 10 15 20 25 30 35 40

Tra

inin

g t

ime

[s]

10-4

10-2

100

102

104

LIN-SVM

RBF-SVM

C-NS3VM

DG-NS3VM

NEXT-NS3VM

(b) Tempo di training

Figura 6 : Errore di classificazione e tempo di training variando i nodi da 5 a40.

Page 35: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Indice della sezione

1 IntroduzioneFormulazione del problemaContributi della tesi

2 Apprendimento distribuito con reti RVFLDescrizione delle reti RVFLAlgoritmi proposti e risultati

3 Apprendimento distribuito semi-supervisionatoSVM semi-supervisionate∇-S3VM distribuite

4 Apprendimento distribuito con reti ricorrentiEcho state networks distribuite

5 ConclusioniConclusione e sviluppi futuriRiepilogo attivita accademiche

Page 36: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Apprendimento distribuito per dati tempo-varianti

Nel caso di dati tempo-varianti, supponiamo che vi sia una dipen-denza temporale fra dati osservati in instanti temporali successivi.

Nel contesto delle reti neurali, abbiamo due possibilita:

• Reti neurali a dinamica interna, nelle quali la memoria viene man-tenuta dallo stato della rete neurale (rete ricorrente).

• Reti neurali a dinamica esterna, nel quale la memoria viene preser-vata tramite un buffer in input.

Nel caso distribuito, nel primo caso non esistono algoritmi interamentedecentralizzati, mentre il secondo caso e stato investigato intensiva-mente nel caso del signal processing.

Page 37: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Echo state network

In una echo state network (ESN), lo strato centrale, pur essendo gen-erato in maniera stocastica, puo contenere connessioni ricorrenti:

1x

iNx

...

1h

2h

rNh

1y

oNy

...

Grazie a questa scelta, il problema di ottimizzazione risultante puo es-sere espresso in forma di regressione lineare, esattamente come avvieneper le reti RVFL.

[1] Lukosevicius, M., & Jaeger, H. (2009). Reservoir computing approaches torecurrent neural network training. Computer Science Review, 3(3), 127-149.

Page 38: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

ESN distribuite

Consideriamo un’estensione alle ESN dell’algoritmo basato su ADMMintrodotto per le reti RVFL. Lo testiamo sulla predizione della seriecaotica MacKey-Glass:

x[n] = βx[n] +αx[n− τ ]

1 + xγ [n− τ ]. (32)

con α = 0.2, β = −0.1, γ = 10 e τ = 30.

Selezioniamo 300 neuroni nello strato ricorrente, con λ = 10−3.

Generiamo 50 sequenze da 2000 elementi ciascuna, equamente suddi-vise fra gli agenti.

[1] Scardapane, S., Wang, D., & Panella, M. (2015). A decentralized training algo-rithm for Echo State Networks in distributed big data applications. Neural Networks,under press.

Page 39: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Risultati sperimentali

0 5 10 15 20 25 30

0.18

0.2

0.22

0.24

0.26

0.28

0.3

Number of nodes

Err

or

C−ESN

L−ESN

ADMM−ESN

(a) Errore (NRMSE)

0 5 10 15 20 25 300

2

4

6

8

10

Number of nodes

Tim

e [

secs]

C−ESN

L−ESN

ADMM−ESN

(b) Tempo di training

Figura 7 : Errore di classificazione e tempo di training variando i nodi da 5 a25.

Page 40: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Indice della sezione

1 IntroduzioneFormulazione del problemaContributi della tesi

2 Apprendimento distribuito con reti RVFLDescrizione delle reti RVFLAlgoritmi proposti e risultati

3 Apprendimento distribuito semi-supervisionatoSVM semi-supervisionate∇-S3VM distribuite

4 Apprendimento distribuito con reti ricorrentiEcho state networks distribuite

5 ConclusioniConclusione e sviluppi futuriRiepilogo attivita accademiche

Page 41: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Contributi principali della tesi

Gli algoritmi presentati affrontano un insieme diversificato di prob-lemi:

1 Algoritmi per l’apprendimento distribuito di reti RVFL.

2 Formulazione del problema dell’apprendimento semi-supervisionatodistribuito.

3 Due algoritmi per risolvere tale problema con SVM lineari e non-lineari.

4 Uno dei primi algoritmi per l’apprendimento distribuito di retineurali internamente ricorrenti.

Page 42: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Sviluppi futuri

1 Applicazione degli algoritmi presentati a problemi realistici coneventuale presenza di dati su larga scala.

2 Estensione al caso distribuito di altri algoritmi semi-supervisionatiper le SVM.

3 Verifica delle prestazioni degli algoritmi in situazione di partizion-amento non bilanciato dei dati.

4 Rilassamento di alcuni vincoli imposti nella tesi (topologia dellarete, sincronizzazione).

5 Introduzione di algoritmi per l’apprendimento di reti neurali gen-erali (problema non-convesso con possibilita di milioni di parametriadattabili).

Page 43: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Pubblicazioni relative alla presentazione

Riviste:

[1] Scardapane, S., Wang, D., Panella, M. & Uncini, A. (2015). Distributed Learning forRandom Vector Functional-Link Networks. Information Sciences, 301, pp. 271-284.

[2] Scardapane, S., Wang, D., & Panella, M. (2015). A decentralized training algorithmfor Echo State Networks in distributed big data applications. Neural Networks, underpress.

Conferenze:

[1] Scardapane, S., Panella, M., Comminiello, D., & Uncini, A. (2015). Learning fromDistributed Data Sources Using Random Vector Functional-Link Networks. ProcediaComputer Science, 53, 468-477.

[2] Scardapane, S., Fierimonte, R., Wang, D., Panella, M. & Uncini, A. (2015). Dis-tributed Music Classification Using Random Vector Functional-Link Nets. In 2015 Inter-national Joint Conference on Neural Networks (IJCNN’15), (pp. 1-8). IEEE/INNS.

[3] Fierimonte, R., Scardapane, S., Panella, M. & Uncini, A. (2015). A Comparison ofConsensus Strategies for Distributed Learning of Random Vector Functional-Link Net-works. Presented at the 25th Italian Workshop on Neural Networks (WIRN’15).

Page 44: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Pubblicazioni relative alla presentazione

In corso di revisione:

[1] Scardapane, S., Panella, M., Comminiello, D., Hussain, A. & Uncini, A. (2015). Dis-tributed Reservoir Computing with Sparse Readouts. Submitted to IEEE ComputationalIntelligence Magazine.

[2] Scardapane, S., Fierimonte, R., Di Lorenzo, P., Panella, M. & Uncini, A. (2015). Dis-tributed Semi-Supervised Support Vector Machines. Submitted to Neural Networks.

[3] Fierimonte, R., Scardapane, S., Uncini, A. & Panella, M. Fully Decentralized Semi-supervised Learning via Privacy-Preserving Matrix Completion. Submitted to IEEETransactions on Neural Networks and Learning Systems.

[4] Scardapane, S., Scarpiniti, M., Comminiello, D. & Uncini, A. (2015). Diffusion SplineAdaptive Filtering. Submitted to IEEE Transactions on Signal and Information Processingover Networks.

Page 45: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Altre pubblicazioni (riviste)

[1] Scardapane, S., Comminiello, D., Scarpiniti, M. & Uncini, A. (2015). Online Sequen-tial Extreme Learning Machine With Kernels. IEEE Transactions on Neural Networks andLearning Systems, 26(9), pp. 2214-2200.

[2] Comminiello, D., Scarpiniti, M., Scardapane, S., Parisi, R. & Uncini, A. (2015). Im-proving nonlinear modeling capabilities of functional link adaptive filters. Neural Net-works, 69, pp. 51-59.

[3] Scardapane, S., Scarpiniti, M., Bucciarelli, M., Colone, F., Mansueto, M. V., & Parisi,R. (2015). Microphone Array Based Classification for Security Monitoring in Unstruc-tured Environments. AEU-International Journal of Electronics and Communications, 69(11),pp. 1715-1723.

[4] Scardapane, S., Comminiello, D., Scarpiniti, M., & Uncini, A. (2015). A Semi-supervisedRandom Vector Functional-Link Network based on the Transductive Framework. Infor-mation Sciences, under press.

[5] Bianchi, F. M., Scardapane, S., Uncini, A., Rizzi, A., & Sadeghian, A. (2015). Predic-tion of telephone calls load using Echo State Network with exogenous variables. NeuralNetworks, 71, pp. 204-213.

[6] Bianchi, F. M., Scardapane, S., Rizzi, A., Uncini, A. & Sadeghian, A. (2015). GranularComputing Techniques for Classification and Semantic Characterization of StructuredData. Cognitive Computation, under press.

Page 46: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Altre pubblicazioni (conferenze)[1] Comminiello, D., Scardapane, S., Scarpiniti, M., & Uncini, A. (2013). Interactivequality enhancement in acoustic echo cancellation. In Proceedings of the 2013 36th Inter-national Conference on Telecommunications and Signal Processing (TSP’13), (pp. 488-492).IEEE.

[2] Scardapane, S., Comminiello, D., Scarpiniti, M., & Uncini, A. (2013). Music clas-sification using extreme learning machines. In Proceedings of the 2013 8th InternationalSymposium on Image and Signal Processing and Analysis (ISPA’13), (pp. 377-381). IEEE.

[3] Scardapane, S., Comminiello, D., Scarpiniti, M., & Uncini, A. (2014). GP-based ker-nel evolution for L2-Regularization Networks. In Proceedings of the 2014 IEEE Congresson Evolutionary Computation (CEC’14), (pp. 1674-1681). IEEE.

[4] Scardapane, S., Nocco, G., Comminiello, D., Scarpiniti, M., & Uncini, A. (2014).An effective criterion for pruning reservoir?s connections in Echo State Networks. InProceedings of the 2014 International Joint Conference on Neural Networks (IJCNN’14), (pp.1205-1212). IEEE.

[5] Bianchi, F. M., Scardapane, S., Livi, L., Uncini, A., & Rizzi, A. (2014). An Inter-pretable Graph-based Image Classifier. In Proceedings of the 2014 International Joint Con-ference on Neural Networks (IJCNN’14), (pp. 2339-2346). IEEE.

[6] Comminiello D., Scardapane, S., Scarpiniti, M., Parisi, R. & Uncini, A. (2015). Func-tional Link Expansions for Nonlinear Modeling of Audio and Speech Signals. In Pro-ceedings of the 2015 International Joint Conference on Neural Networks (IJCNN’15), (pp. 1-8).IEEE.

Page 47: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Altre attivita I

Corsi seguiti:

• Circuiti ed Algoritmi per il Riconoscimento (Prof. AntonelloRizzi), 6 CFU.

• Queueing Theory and Applications, (Prof. Izhak Rubin), 6 CFU• Fondamenti del sapere scientifico e tecnologico, (Prof. Giovanni

Iacovitti), 6 CFU.• Distributed Optimization over Complex Networks (Prof. Sergio

Barbarossa), 6 CFU.

Progetti di ricerca:

• Collaborato nell’ambito del progetto di ricerca “Antenna acusticapassiva basata su array di microfoni su membrana flessibile” tra IN-TECS S.p.a. e DIET, riguardante l’implementazione di un sistemadi apprendimento multi-strato per la classificazione di sorgentisonore.

Page 48: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Altre attivita II

• Partecipazione alle scuola di dottorato “Aspetti pluri-disciplinaridelle dinamiche di relazione multi-agente” e “Aspetti delle dinamichedi apprendimento automatico, biologico e sociale”, organizzate da SE-FIR, in collaborazione con il Servizio Nazionale per il ProgettoCulturale (Perugia, 2014/2015).

• Seminario “Sinergie Uomo/Macchina nel Processo Creativo”, pressoUniversita Campus Bio-Medico (17 Luglio 2014), su invito delProf. Flavio Keller.

• Publicity Co-Chair per la prima conferenza “INNS Conference onBig data” tenutasi dal 9 all’11 Agosto a San Francisco, e per la sec-onda edizione (in programma a Thessaloniki in Ottobre 2016).

• Co-organizzatore della special session “Distributed Learning Algo-rithms for Neural Networks” all’IJCNN 2016.

Page 49: Presentazione Conclusiva Attivita Dottorato` Apprendimento ...ispac.diet.uniroma1.it/.../05/Presentazione...Anno.pdf · Presentazione Conclusiva Attivita Dottorato` Apprendimento

Grazie per l’attenzione!Domande?