Università di Pisa
Dipartimento di Informatica
Corso di Laurea Magistrale in Informatica
(Classe LM-18)
Tesi di Laurea
Stima di proprietà non funzionali di
applicazioni parallele con reti neurali.
Relatori:
Prof. Alessio Micheli
Prof. Marco Danelutto
Dott. Claudio Gallicchio
Candidato:
Mattia Lacroce
Indice
Introduzione iv
1 Modelli Paralleli e Performances 1
1.1 Skeleton Trees . . . 2
1.1.1 Esempi di skeletons algoritmici . . . 2
1.1.2 Regole di riscrittura . . . 4
1.2 Misure di Performance . . . 4
1.2.1 Misure basate sul tempo . . . 4
2 Reti Neurali su Dati Strutturati: Tree ESN 7 2.1 Echo State Network . . . 7
2.1.1 Contrattività ed Echo State Property . . . 8
2.1.2 Inizializzazione ed addestramento . . . 10
2.1.3 Fattore Markoviano di una ESN . . . 11
2.1.4 Varianti architetturali e modelli avanzati . . . 12
2.2 Tree Echo State Network . . . 20
2.2.1 Trasduzioni ricorsive su alberi . . . 20
2.2.2 Descrizione del modello . . . 22
2.2.3 Markovanità di una TreeESN . . . 24
2.2.4 Risultati sperimentali TreeESN . . . 26
3 Approccio TreeESN per l'High Performance Computing 27 3.1 Analisi del problema e stato dell'arte . . . 27
3.2 Generazione dei dataset . . . 28
3.2.1 Scelta del codice sequenziale . . . 29
3.2.2 Esecuzione dei sequenziali . . . 30
3.2.3 Generazione degli alberi . . . 30
3.2.4 Compilazione ed esecuzione . . . 34
3.2.5 Parsing . . . 34
4 Risultati sperimentali 41 4.1 Metriche per la valutazione delle performance . . . 41
4.2 Applicazione del modello di apprendimento . . . 42
4.2.1 Addestramento e validazione del modello . . . 43
4.3 Risultati: tempo di completamento . . . 44
4.3.1 Dataset che non includono il modello dei costi . . . 44
4.3.2 Dataset che includono il modello dei costi . . . 46
4.4 Risultati: consumo di energia . . . 50
4.4.1 Rappresentazioni semplici . . . 50
4.4.2 Rappresentazioni miste . . . 52
4.4.3 Analisi bipartita . . . 55
5 Conclusioni 57 A Dataset - Consumo di energia 59 A.1 Rappresentazioni semplici . . . 59
A.1.1 Dataset originale . . . 59
A.1.2 Dataset replicato . . . 61
A.1.3 Dataset basato sui core . . . 63
A.2 Rappresentazioni miste . . . 65
A.2.1 Dataset originale . . . 65
A.2.2 Dataset replicato . . . 67
A.2.3 Dataset basato sui core . . . 69
A.2.4 Dataset sinergico . . . 71
A.2.5 Dataset con modello dei costi . . . 74
Introduzione
Tempo di completamento e consumo di energia stanno diventando fattori chiave nell'High Performance Computing (HPC), soprattutto per ragioni di carattere economico ed ambientale. Infatti un elevato consumo di energia causa l'innal-zamento delle temperature dei sistemi, incrementando la probabilità di guasti alle componenti. E' stato dimostrato che la manutenzione dei sistemi richiede un dollaro aggiuntivo per ogni dollaro speso in elettricità [31]. Altro aspetto da considerare è l'emissione di CO2, che nella somma dei data center degli Stati Uniti è paragonabile a quello di intere nazioni come l'Argentina. Le soluzioni per far fronte al problema descritto, si basano sull'aumento del numero di core (per abbattere il tempo di completamento delle applicazioni), alla loro riduzione (o alla riduzione della loro frequenza) per limitare il consumo di energia. Quindi l'aumento o la riduzione di risorse di calcolo incrementano alcune performance, degradandone altre. Per trovare un trade-o, è possibile dare un limite al consu-mo di energia, ponendo dei vincoli anche sul tempo di completamento massiconsu-mo. Per soddisfare tali requisiti è necessario saper rispondere alla seguente domanda: Quale è la con gurazione dell'applicazione parallela che consuma meno energia, permettendo all'applicazione di completare la sua esecuzione prima di una data deadline?
Per queste ragioni, abbiamo bisogno di un algoritmo di stima del tempo di completamento e del consumo di energia che sia preciso, ma abbastanza e cien-te da poe cien-ter essere applicato a e cien-tempo di compilazione o a runtime con impatto minimo sulla latenza dell'applicazione.
Nel 1989 è stato proposto un nuovo framework strutturato per la programma-zione parallela basato, come vedremo nel Capitolo 1, su Skeleton Algoritmici. Conoscendo l'insieme dei pattern implementati nel framework, può essere svi-luppato un modello dei costi analitico per la predizione del tempo di comple-tamento. Tuttavia, i modelli analitici richiedono delle importanti assunzioni sempli cative sul dominio, che talvolta possono condurre a predizioni scaden-ti, senza considerare che sulle architetture moderne produrre un tale modello può essere un compito arduo. Pertanto viene spontanea una seconda domanda, funzionale alla prima:
Considerando un programma parallelo, rappresentato in termini dei pat-tern elementari che lo compongono, come stimarne il tempo di completamento ed il consumo di energia in modo e cace, e ciente e senza fare assunzioni sul dominio?
Un nuovo paradigma per costruire modelli predittivi, che è oggetto di questa tesi, può essere esplorato utilizzando l'apprendimento automatico. Un modello di apprendimento può infatti catturare le relazioni esistenti nei dati, usando un training set di esempi per approssimare la funzione obiettivo,
ap-prendendo il comportamento dell'applicazione parallela su una data architettura come black-box, cioè senza fare assunzioni sull'architettura stessa. Prenderemo in considerazione applicazioni basate su skeletons tree, annotati con le informa-zioni rilevanti ai ni della predizione, come per esempio il numero di processori usati dall'applicazione. Similmente al comportamento del modello dei costi, il modello di apprendimento prenderà in considerazione la struttura dello skeleton tree per stimare il tempo di completamento e l'energia consumata dell'applica-zione. Avremo inoltre bisogno di modelli capaci di trattare dati strutturati, ed in particolare abili a processare domini caratterizzati da alberi (che sono uti-lizzati per rappresentare le applicazioni). In particolare, il modello scelto per arontare il problema è la Echo State Network, appartenente all'area del Reser-voir Computing. Tale paradigma, con particolare riferimento al modello ESN, è stato esteso al trattamento di domini strutturati ad albero con l'introduzione delle TreeESN [6]. La tesi indaga su come costruire un modello predittivo per le performances di un'applicazione basata su skeletons. In prospettiva l'idea è di poter includere il modello sviluppato in un framework più avanzato, che sarà in grado di compilare l'applicazione parallela utilizzando la con gurazione migliore per lo skeleton tree, oppure ricon gurare l'applicazione a runtime.
La tesi è organizzata come segue:
• Nel capitolo 1 verrà descritto in dettaglio il framework, basato su skeletons algoritmici, ed il modello analitico dei costi ad esso associato.
• Il capitolo 2 è incentrato sui modelli basati sul reservoir usati per il task in questione. Verrà illustrato il funzionamento della Echo State Network su dati sequenziali, per poi estendere la trattazione alla Tree Echo Sta-te Network, che esSta-tende il paradigma Reservoir Computing a domini di alberi.
• Nel capitolo 3 verrà illustrato in dettaglio l'approccio al problema oggetto di questa tesi, in particolare la generazione del dataset.
• Nel capitolo 4, dopo l'introduzione delle misure di performance e del pro-cedimento di l'applicazione della TreeESN ai dati generati, vengono ripor-tati in dettaglio gli esperimenti condotti ed i risulripor-tati ottenuti usando la TreeESN, per la predizione del tempo di completamento e del consumo di energia.
• In ne, nel capitolo 5 viene fatto il punto della situazione sui risultati ottenuti nella tesi, con riguardo alle applicazioni del modello ottenuto ed a possibili sviluppi futuri.
Capitolo 1
Modelli Paralleli e
Performances
Negli ultimi anni, gli sviluppi nella tecnologia hanno reso disponibili nuove ar-chitetture parallele con capacità di calcolo senza precedenti. Questa rivoluzione hardware ha provocato l'aggiunta di più CPU sullo stesso chip, segnando il passaggio da architetture single core ad architetture multicore, con ovvie ri-percussioni anche sul software ("hardware parallelo ha bisogno di software pa-rallelo" [4]). Nasce quindi l'esigenza di modelli e paradigmi di programmazio-ne parallela. Progettare un'applicazioprogrammazio-ne parallela normalmente consiste programmazio-nelle seguenti fasi:
• Individuare l'insieme delle attività concorrenti (attività che possono essere combinate per risolvere un singolo problema). Esse dipendono ovviamente dalle caratteristiche del problema in esame.
• Coordinare le attività concorrenti, cioè prevedere i meccanismi di sincro-nizzazione per l'accesso ai dati condivisi, ed individuare dipendenze di controllo (quali attività eseguire prima o dopo, a discrezione del program-matore) e dipendenze nei dati (quali attività eseguire tenendo conto che il dato calcolato da un'attività concorrente è necessario ad un'altra attività concorrente).
• Implementare le attività concorrenti in parallelo usando al meglio le ri-sorse ed i meccanismi concorrenti disponibili, per massimizzare i bene ci derivanti dal parallelismo.
Alla luce di quanto detto, nel resto di questo capitolo saranno arontati in dettaglio alcuni strumenti di base utilizzati per perseguire i punti di cui sopra. In particolare, per individuare le attività concorrenti e coordinarle tra di loro, verranno introdotti gli skeleton algoritmici e skeleton trees, mentre per valutare l'uso delle risorse, e gli eettivi bene ci del parallelismo si parlerà di misure di performance.
Pipe Farm Seq Seq Comp Seq Farm Seq Figura 1.1: Esempio di Skeleton Tree.
1.1 Skeleton Trees
Uno skeleton tree (Figura 1.1) è un albero avente come nodi interni degli ske-letons algoritmici, e come foglie delle porzioni di codice sequenziale (business logic code), che rappresenta una applicazione parallela strutturata. Gli skeletons algoritmici furono introdotti per la prima volta nel 1988 da Murray Cole [2], e de niscono un nuovo paradigma di programmazione parallela strutturata. Sono dei pattern, che incapsulano un costrutto di parallelismo speci co, fornito all'u-tente come costrutto linguistico già pronto da usare per scrivere applicazioni, con notevoli vantaggi legati a riuso del codice, ed astrazione: l'utente program-matore non deve preoccuparsi della correttezza dello skeleton (quindi la fase di debug è sempli cata), ma solo a scrivere la logica di funzionamento della sua applicazione utilizzando gli skeleton disponibili. Il singolo skeleton nasconde la complessità dell'architettura parallela sottostante, occupandosi della sincroniz-zazione delle entità parallele. In ne va ricordato che gli skeletons algoritmici sono pienamente componibili tra di loro, in accordo alla seguente grammatica, (che modella solo un insieme ristretto di skeleton stream parallel, che sono quelli usati in questa tesi):
Grammatica 1. Sk ::= Seq(Code)| Farm(Sk) | Pipe(Sk,Sk) | Comp (Sk,Sk) quindi è interessante la composizionalità, che porta alla nascita degli ske-leton trees introdotti ad inizio sezione, come framework di programmazione parallela. Risulta molto importante perchè permette di esprimere computazioni parallele complesse a partire da componenti più elementari.
1.1.1 Esempi di skeletons algoritmici
In questa sezione saranno presentati gli skeletons algoritmici utilizzati nella tesi. Saranno analizzati gli stream parallel skeletons, i quali, dato uno stream di dati in input, eseguono parallelamente calcoli su elementi consecutivi dello stream, ciascuno disponibile in tempi diversi. Diversamente, i data parallel
1 2 3
Figura 1.2: Illustrazione di una pipeline.
E w w w ... w w w C
Figura 1.3: Illustrazione di una Farm con Emitter (E), workers (w) e Collector (C).
skeletons sfruttano il parallelismo su dierenti sottoproblemi, derivanti da uno stesso elemento dello stream. Esempi di questi ultimi, che verranno solo elencati in questa sede, sono Map, Reduce, Parallel Pre x [4].
Pipeline
La pipeline è uno skeleton utilizzato per modellare computazioni espresse in stadi (stages), come si vede in Figura 1.2. La sua semantica garantisce che tutti gli stadi saranno eseguiti parallelamente su diversi input, quindi per due elementi consecutivi xi ed xi+1, supponendo che gli stadi n ed n + 1 calcolino
le rispettivamente le funzioni g e f, si ha che f(xi+1)e g(f(xi)) sono eseguite
contemporaneamente. Farm
La farm è un paradigma basato sulla replicazione di una computazione puramen-te funzionale. La struttura di una Farm è illustrata in Figura 1.3. In particolare, l'emitter si occupa di schedulare i tasks ai workers (secondo una data strategia di scheduling), i quali eseguono tutti la stessa funzione, e passano il risultato ad un collector che li restituisce in output (dopo una eventuale riorganzzazione). Ovviamente emitter, collector, ed i vari workers vengono eseguiti in parallelo. Di conseguenza la scelta del numero di workers rappresenta un parametro chia-ve, in relazione alle risorse messe a disposizione dall'architettura sottostante. Sono inoltre possibili architetture diverse, come un collector che restituisce i task all'emitter, oppure architetture che non prevedano il collector.
Comp
Il costrutto comp può essere rappresentato analogamente ad una pipeline. La sola dierenza è che i vari stadi sono eseguiti uno dietro l'altro in maniera
sequenziale, e non parallelamente come invece avviene nella pipeline. Questo costrutto diventa semanticamente rilevante soprattutto quando viene combinato con gli altri visti sopra.
1.1.2 Regole di riscrittura
Le regole di riscrittura [4] de niscono delle classi di equivalenza tra skeletons, e permettono di ottenere trasformazioni tra skeleton trees, mantenendo l'equiva-lenza semantica. Quelle usate in questa tesi sono:
Regola 1 (Introduzione/eliminazione farm). farm(∆) ≡ ∆
Regola 2 (Introduzione/eliminazione pipeline). comp(∆1, ∆2) ≡ pipe(∆1, ∆2)
Regola 3 (Assoc. Comp). comp(∆1, comp(∆2, ∆3)) ≡ comp(comp(∆1, ∆2), ∆3)
Regola 4 (Assoc. Pipeline). pipe(∆1, pipe(∆2, ∆3)) ≡ pipe(pipe(∆1, ∆2), ∆3)
1.2 Misure di Performance
Avendo a che fare con computazioni parallele, le misure di performance as-sumono particolare rilevanza, sia in termini di tempo impiegato che di risorse utilizzate. E' interessante infatti sapere quale performance si può ottenere usan-do un particolare pattern, prima di iniziare a scriverne il codice applicativo. In secondo luogo, va tenuto conto dell'overhead aggiuntivo causato dall'implemen-tazione, ovvero quanto la performance in pratica sarà diversa di quella teorica. In ogni caso, abbiamo bisogno di un modello di performance che misuri la bontà dell'applicazione su una data architettura, in funzione di un certo numero di parametri dipendenti sia dall'applicazione in sè, che dalla macchina stessa [4].
1.2.1 Misure basate sul tempo
Siamo interessati a due tipi distinti di indicatori:
• Quelli che misurano il tempo assoluto speso nel calcolo di un singolo risultato.
• Quelli che misurano il numero di risultati ottenuti nell'unità di tempo. Indicatori del primo tipo sono:
• Latenza (L) il tempo trascorso da quando l'applicazione riceve l'input xi al momento in cui la stessa restituisce l'output corrispondente oi.
• Tempo di completamento (Tc) la latenza totale di un'applicazione
calcolata su tutto lo stream in input, dall'arrivo del primo input xi alla
disponibilità dell'ultimo output oj.
• Tempo di servizio (Ts): il tempo che intercorre nella restituzione di
due output consecutivi (o, analogamente, nell'accettazione di due input consecutivi).
• Banda (B), la capacità del sistema, espressa come il numero di elementi che passano in un secondo per un determinato canale. E' l'inverso del tempo di servizio.
Oltre agli indicatori di base appena de niti, indicando con n il grado di parallelismo e Tid =
Tseq
n il tempo di servizio ideale (o di completamento)
del-l'applicazione parallela che utilizza n risorse, siamo interessati ad alcune misure di performance derivate:
• Speedup s(n) = Tseq
Tpar(n). Fornisce una misura di quanto si guadagna
intro-ducendo il parallelismo rispetto alla migliore computazione sequenziale. Al caso ottimo si ha s(n) = n.
• Scalabilità scalab(n) = Tpar(1)
Tpar(n). Misura quanto migliora
l'implementazio-ne parallela aumentando il grado di parallelismo. Al caso ottimo si ha scalab(n) = n.
• E cienza (n) = Tid
Tpar(n). Misura la capacità dell'applicazione a fare buon
uso delle risorse disponibili. Al caso ottimo si ha (n) = 1.
In generale, capire quali misure di performance massimizzare dipende da cosa si vuole ottenere con l'introduzione del parallellismo. Nel caso di un sistema parallelo che opera su uno stream, ridurre il tempo di servizio è cruciale per minimizzare anche il tempo di completamento. Infatti se lo stream di input ha lunghezza m, si ha:
Tc= mTs se m >> n. (1.1)
Analisi performance degli skeletons
In questa sezione saranno analizzate le performance relative agli skeletons di interesse evidenziati nella sezione precedente. Nell'analisi saranno trascurati i costi relativi alla comunicazione, come tempi di interarrivo e tempi di trasmis-sione, grazie all'assunzione che siano molto minori del tempo speso nel calcolo eettivo. Il tempo di servizio di una pipeline è
Ts−pipe= max stagei
(Ts−stagei)
in cui Ts−stagei è il tempo di servizio dell'i-esimo stadio della pipeline.
Dato che il tempo di servizio dipende dallo stage più lento, le performance della pipeline possono degradare nel caso in cui gli stadi non siano bilanciati. Riguardo al tempo di completamento invece, l'Equazione (1.1) non tiene conto di un tempo di riempimento della pipeline, necessario a tutti gli stadi per avere un task da calcolare. Tenendo conto di questo fattore si ha:
Tc−pipe=
X
stagei
In cui Lstagei è la latenza dello stadio i-esimo.
Per quanto riguarda la farm, essa può essere vista come una pipeline a tre stadi. Di conseguenza:
Ts−f arm= max(Temitter,
Tcal
Nw
, Tcollector).
La formula sopra suggerisce che il fattore che può essere abbattuto avendo mag-giori risorse è Tcal
Nw (essendo il numero di workers della farm un parametro
li-bero), quindi a nchè le prestazioni siano migliorabili è necessario che il fattore dominante sia quest'ultimo, e quindi
Ts−f arm=
Tcal
Nw
(1.2) in cui Nw è il numero di workers e Tcal il tempo di servizio di un worker.
In caso contrario emitter e collector sarebbero collo di bottiglia per l'intera farm, ponendo di fatto un limite al miglioramento delle prestazioni. Il tempo di completamento di una farm è
Tc−f arm= NwTemitter+ m
Tcal
Nw
+ Tcollector
che grazie all'assunzione m >> n > Nw dell'Equazione (1.1) diventa
Tc−f arm≈ m
Tcal
Nw
= mTs−f arm
Per il nodo comp, in ne, il tempo di servizio ed il tempo di completamento sono rispettivamente uguali alla somma dei tempi di servizio e di completamento degli stadi che lo compongono.
Capitolo 2
Reti Neurali su Dati
Strutturati: Tree ESN
Le Reti Neurali Ricorrenti [33] (RNNs) sono una classe di modelli usati per elaborare sequenze. A tale scopo, viene fatto uso di funzioni che operano su se-quenze, dette trasduzioni [5]. In particolare, il Reservoir Computing (RC) [34, 35] è una denominazione per una classe di RNNs caratterizzate da una di-visione concettuale tra un livello ricorrente e dinamico (reservoir), ed un livello di output sso e non ricorrente (readout) [34]. La caratteristica chiave di queste reti è che il livello ricorrente della rete non viene allenato dopo l'inizializzazione, perchè soddisfa alcune condizioni di facile veri ca, riguardanti la stabilità delle dinamiche sviluppate. E' noto che una rete ricorrente tende, durante l'apprendi-mento, ad organizzare il suo stato interno in modo che stati simili corrispondano a sequenze di input altrettanto simili tra di loro. In altre parole, assumendo di avere due sequenze diverse con un su sso comune, gli stati della rete corri-spondenti alle due sequenze saranno vicini tra di loro proporzionalmente alla lunghezza del su sso (Markovian architectural bias) [7, 36, 37]. Seguendo una particolare inizializzazione, questa proprietà si veri ca in assenza di apprendi-mento [7]. Quindi se la natura del problema da risolvere è compatibile con tale caratterizzazione Markoviana, il modello discrimina intrinsecamente tra die-renti sequenze di input senza adattare i parametri del reservoir. Appartengono a questa classe di modelli le Echo State Networks (ESNs) [38, 39], Liquid State Machines [41, 42], ed altri approcci come Evolino [40, 42]. Questo capito-lo sarà focalizzato sulle ESNs su sequenze temporali in un primo momento, poi verranno introdotte le TreeESNs per operare su dati strutturati ad albero.
2.1 Echo State Network
Una ESN, la cui architettura è illustrata in Figura 2.1, è caratterizzata da tre livelli: il livello di input, il reservoir, ed il readout (livello di output). Il reservoir è formato di solito da un gran numero di neuroni, connessi tra di loro in maniera casuale e sparsa. Se indichiamo con NU la dimensione dell'input,
quest'ultima è de nita come
τ : RNU × RNR → RNR
è implementata dall'equazione
x(n) = τ (u(n), x(n − 1)) = f (Winu(n) + ˆW x(n − 1)) (2.1)
in cui u(n) è un elemento della sequenza s(u) = [u(1), . . . , u(n)], Win∈ RNR×(NU+1)
(in cui il NU + 1comprende un peso per ciascuna feature in input più il bias,
avente input ssato pari ad 1) e ˆW ∈ RNR×NR sono rispettivamente la matrice
dei pesi del livello di input e quella del reservoir, mentre f indica l'applicazione (elemento per elemento) della funzione di attivazione dei neuroni del reservoir. In questa sezione assumeremo f = tanh. La versione iterata dell'Equazione (2.1) è ˆ τ : (RNU)∗× RNR→ RNR ∀s(u) ∈ (RNU)∗ , ∀x ∈ RNR: ˆ τ (s(u), x) = ( x s(u) = []
τ (u(n), ˆτ ([u(1), . . . , u(n − 1)], x)) s(u) = [u(1), . . . , u(n)] (2.2) in cui (RNU)∗ denota l'insieme di tutte le possibili sequenze di lunghezza nita
su RNU e ˆτ(s(u), x) è lo stato della rete dato dalla sequenza s(u) partendo dallo
stato iniziale x ∈ RNR, che solitamente è inizializzato al vettore nullo di RNR .
Il readout è un livello lineare non ricorrente, nonchè l'unico sottoposto ad apprendimento. L'output di una ESN è dato da
y(n) = Woutx(n)
in cui Wout∈ RNY×(NR+1)(come sopra la dimensione aggiuntiva sta ad indicare
il bias del reservoir) è la matrice dei pesi dai neuroni del reservoir al readout.
2.1.1 Contrattività ed Echo State Property
Come anticipato nell'introduzione, caratteristica principale del reservoir è di avere un gran numero di neuroni ricorrenti, che non necessitano di apprendi-mento, preservando il potere predittivo della rete, con guadagno in e cienza. Questo grazie alla Echo State Property (ESP)[39, 42], la quale garantisce che lo stato di una ESN asintoticamente dipenda solo dal segnale di input, carat-teristica che dà il nome al modello ("Echo State"), e come vedremo garantisce la stabilità del sistema dinamico. Quindi dopo un periodo transiente iniziale necessario per ridurre la dipendenza dello stato dall'inizializzazione casuale, lo stato iniziale in uisce sempre meno sulle dinamiche della rete. Formalmente
∀sn = [u(1), . . . , u(n)] ∈ (RNU)n,
∀x, x0∈ RNR :
lim
n→∞||ˆτ (sn(u), x) − ˆτ (sn(u), x
u(n) Win Input NU Wout Output NY y(n) ˆ W Reservoir NR
Figura 2.1: Schema di una Echo State Network.
Ai nostri ni, è importante cercare delle condizioni su cienti per l'ESP, che siano di facile veri ca. Vedremo come, indicando con σ il massimo valore singolare di una matrice, la condizione
σ( ˆW ) =|| ˆW ||2< 1 (2.3)
è su ciente a garantire l'ESP. Inanzitutto de niamo la contrattività di una funzione di transizione di stato τ sulla base della seguente condizione
∃C ∈ R, 0 ≤ C < 1, ∀u ∈ RNU, ∀x, x0∈ RNR:
||τ (u, x) − τ (u, x0)|| ≤ C||x − x0|| (2.4) dove C è il grado di contrattività. In altre parole, τ deve essere Lipschitziana e continua con parametro C inferiore all'unità. Si può dimostrare [5] che se τ è contrattiva con parametro C < 1 (in qualsiasi norma), vale la ESP. Questo, in aggiunta al fatto che
Equazione (2.3) =⇒ Equazione (2.4)
dimostra che, nel caso si usi la funzione di attivazione tanh, l'Equazione (2.3) è su ciente per garantire l'ESP. Questa condizione assicura la stabilità globale del sistema [5], anche se nella pratica viene spesso usata la condizione necessaria (ma non su ciente) data da
ρ( ˆW ) < 1.
in cui la funzione ρ restituisce l'autovalore di modulo massimo di una matrice (raggio spettrale). Quando questa condizione non vale, il reservoir è localmente instabile attorno allo stato nullo e la ESP non è garantita se la sequenza nulla è ammissibile in input. σ( ˆW ) è detto coe ciente di contrattività. Il raggio spettrale ed il massimo valore singolare della matrice di ricorrenza del sistema sono, in generale, i parametri usati per controllare il grado di contrattività del sistema stesso.
2.1.2 Inizializzazione ed addestramento
L'inizializzazione dei pesi della rete, ragionando per livelli, è organizzata come segue:
• I pesi della matrice Winsono scelti in modo casuale da una distribuzione
uniforme sull'intervallo [−win, win], in cui winè uno dei parametri liberi
della rete (input scaling), e viene ssato in fase di validazione.
• La matrice del reservoir viene inizialmente scelta in modo casuale W = Wrandom. Anche in questo caso i pesi della matrice sono scelti in modo
casuale da una distribuzione uniforme sull'intervallo [−w, w], in cui w è detto input scaling e costituisce un altro parametro libero del modello. La matrice ottenuta viene successivamente scalata in modo da veri care la condizione per l'ESP: ˆW = Wrandomρ( ˆWρdesired
random), in cui ρdesired è il
raggio spettrale desiderato, che costituisce un ulteriore parametro libero del modello. Si osservi che al posto di ρ può essere usato anche l'altro coe ciente di contrattività σ.
Discorso a parte merita il livello di output della rete, che viene sottoposto ad addestramento. Se le sequenze prese in considerazione sono lunghe N, prima vengono prodotti e scartati Ntransient stati iniziali (washout), il cui numero è
un parametro libero del modello che dipende da quanto la rete "dimentica" velocemente le condizioni iniziali. Poi collezionando gli stati del reservoir ed i valori target (che indicheremo con il vettore z), si costruiscono le matrici
X = [x(Ntransient+1), . . . , x(N )] Ytarget= [z(Ntransient+1), . . . , z(N )] (2.5)
e la fase di addestramento si riduce alla risoluzione di un problema dei minimi quadrati
min||WoutX − Ytarget||22
risolvibile usando la Pseudo-inversa di Moore-Penrose oppure la Ridge Regres-sion con un parametro di regolarizzazione λr:
Wout = YtargetXT(XXT + λrINR)
−1. (2.6)
in cui INR è la matrice identità di ordine NR.
La diversa formulazione dello stato presente in letteratura è la Leaky Integrator ESN (LI-ESN) [23], in cui compare un parametro a ∈ [0, 1] (leaking rate), con l'introduzione del quale lo stato interno della rete diventa
x(n) = (1 − a)x(n − 1) + af (Winu(n) + ˆW x(n − 1)).
Il leaking rate controlla la velocità delle dinamiche del reservoir. Un leaking rate più piccolo implica che il reservoir reagisca più lentamente all'input. Si evince da quanto detto sopra che lo spazio costituito dai parametri liberi del modello è molto ampio [43]:
• Dimensione del reservoir NR. L'idea generale è che più grande è il
reser-voir, migliore è la performance potenziale ottenibile, con opportune misure di regolarizzazione per contrastare l'over tting [43].
• Grado di connettività del reservoir wconn. Ha l'eetto di rendere più
e ciente il processo di calcolo dello stato (Equazione (2.1)). In generale la sparsità del reservoir non incide molto nella performance predittiva della ESN. Pertanto, questo parametro va ottimizzato con bassa priorità rispetto ad altri.
• Raggio spettrale ρ (o massimo valore singolare σ). Uno dei parametri più importanti di una ESN, che scala la matrice W, in modo da soddisfare l'E-SP. Determina la capacità di memoria della ESN, ovvero con quale velocità l'in uenza di un input viene meno nelle dinamiche del reservoir. Valori grandi di questo parametro possono portare alla violazione dell'ESP. E' importante ricordare che l'ESP vale anche con grado di contrattività mag-giore o uguale ad uno, per input diversi da zero. Questo signi ca che nella pratica, in presenza di input non zero, il valore ottimo per questo para-metro può essere trovato anche per valori signi cativamente più grandi di 1 [43].
• Intervallo per l'inizializzazione dei pesi della matrice Win (wscal). Esso
determina, insieme al bias, il grado di non linearità della rappresentazione del reservoir, e l'eetto relativo dell'input u(n) corrente sullo stato attuale x(n).
• Parametro di regolarizzazione λ. E' un parametro di controllo della com-plessità del modello, utile a regolarizzare il readout, evitando l'over tting (Equazione (2.6)).
• Parametro leaking rate a. Questo parametro determina la velocita' delle dinamiche di aggiornamento di stato, in reazione all'input esterno. Un va-lore basso di a, crea un modello che reagisce lentamente all'input, causando l'incremento della memoria a breve termine della ESN.
I valori per ciascun parametro vengono selezionati tramite model selection. La model selection è uno standard nell'uso e cace di reti neurali, che consiste in una strategia per scegliere, tra tutte le combinazioni di parametri possibili, quella il cui modello corrispondente generalizza meglio il task in esame. Il metodo più usato per implementare questa fase è la grid search, che prova tutte le combinazioni di parametri scegliendoli automaticamente da una griglia. Nella grid search vengono valutate, usando un validation set, con gurazioni della rete corrispondenti a valori degli iper-paramtri scelti da un insieme nito. Il modello con le performance migliori, risultato della model selection, viene poi utilizzato come modello nale per eettuare la fase di test, che costituisce la valutazione nale delle performance della rete.
2.1.3 Fattore Markoviano di una ESN
Parlando del Markovian architectural bias [5], sono state fatte delle indagini per cercare una relazione tra tale fattore, ed il grado di contrattività del reservoir [5]. Prendiamo in considerazione una ESN con funzione di stato τ avente grado di contrattività C < 1 rispetto ad uno spazio RNR, e supponiamo che il
sottoin-sieme degli stati che il reservoir assume sia limitato con diametro diam. Allora, partendo da due stati diversi, ed assumendo di avere due sequenze con un su s-so comune, gli stati calcolati dal reservoir per ciascuna sequenza saranno tanto
Figura 2.2: Natura Markoviana dell'organizzazione degli stati del reservoir. più simili quanto maggiore è la lunghezza del su sso comune, come dettagliato nel seguente teorema (enunciato e dimostrato in [5])
Teorema 1. Se l'operatore · indica la concatenazione di sequenze, comunque presi due pre ssi di input s(v), s(w) ∈ (RNU)∗, un su sso comune [u(1), . . . , u(n)]
ed una coppia di stati iniziali x, x0 ∈ RNR, la distanza tra gli stati calcolata dal
reservoir per le due sequenze s(v) · [u(1), . . . , u(n)] e s(w) · [u(1), . . . , u(n)], con stati iniziali rispettivamente x ed x0, è limitata superiormente da un fattore
proporzionale a Cn, dove C ∈ R è il grado di contrattività:
||ˆτ (s(v) · [u(1), . . . , u(n)], x) − ˆτ (s(w) · [u(1), . . . , u(n)], x0)|| ≤ Cndiam
Questo implica che simboli di input passati hanno in uenza decrescente sullo stato del reservoir. Quindi se due sequenze condividono un su sso lungo n, la distanza tra gli stati corrispondenti è limitata da un fattore che decresce esponenzialmente con n. Perciò un reservoir con funzione τ contrattiva è in grado di discriminare sequenze che hanno su ssi diversi, senza bisogno di ap-prendimento. Questa organizzazione dello spazio degli stati rende il modello più utile per task in cui target più vicini tra di loro sono associati a sequenze con su sso comune più lungo (Figura 2.2) [5].
2.1.4 Varianti architetturali e modelli avanzati
In letteratura sono state proposte molte estensioni della ESN classica, riassumi-bili nelle seguenti categorie:
• Varianti architetturali nell'organizzazione del reservoir. In [22], si fa uso di reservoir multipli che competono tra di loro tramite sinapsi inibitorie, e combinano il loro stato interno per calcolare l'output. In questo modo, l'eetto di accoppiamento tra i neuroni del singolo reservoir, così come la correlazione tra le dinamiche dei diversi reservoir vengono ridotti, e vengono generati più stati interni decorrelati ed in cooperazione tra loro.
In [25], il reservoir della rete contiene solo interi ad n bits per ogni neurone (intESN). Il calcolo dello stato ricorrente viene eettuato tramite shift ciclico piuttosto che moltiplicazione, incrementando di molto l'e cienza. L'architettura intESN dimostra una performance confrontabile con quella della ESN standard per alcuni task tipici della branca del RC.
• Adattività delle dinamiche del reservoir. In [20, 21] viene mostrato che una regola di apprendimento biologicamente plausibile e computazionalmente e ciente (Intrinsic Plasticity rule) può migliorare la capacità di codi ca del reservoir, e la sua abilità ad adattare le dinamiche al task dato in maniera non supervisionata.
• Uso di readout alternativi, come per esempio l'uso di Support Vector Machines per l'implementazione del readout [24].
Nonostante le dinamiche del reservoir siano governate dal fattore Markoviano evidenziato in precedenza, ci sono altri fattori, relativi all'architettura del reser-voir che possono in uenzare le dinamiche e le performance di una ESN. Infatti ESNs con lo stesso coe ciente di contrattività ma con diversa topologia possono portare a risultati dierenti sullo stesso task [5].
Fattori di dierenziazione tra le unità
Per quanto detto, nella letteratura riguardante il RC sono presenti molte varianti architetturali, e molte di queste sono fornite come risultato dello studio dei fattori di dierenziazione delle unità. Seguendo la trattazione in [5], sono state identi cati quattro fattori architetturali che possono avere impatto sulla performance di una ESN:
• Variabilità dell'input. E' la capacità di ogni unità del reservoir di vedere l'input da dierenti prospettive. La con gurazione senza variabilità dell'input è ottenuta ssando allo stesso valore i pesi della matrice Win.
Viceversa, la variabilità dell'input è implementata scegliendo un valore casuale per i pesi di Win.
• Dinamiche con scale temporali multiple. Si riferisce alla possibi-lità per le unità del reservoir di comportarsi come sistemi dinamici con dierenti scale temporali. Questo equivale nella pratica ad unità del re-servoir con dierenti coe cienti di contrattività. Dato che le dinamiche contrattive sono governate, come detto, da σ =|| ˆW ||2, segue che dierenti
neuroni possono esibire dierenti dinamiche se la matrice ˆW è diagonale. In questo caso
σ = max
i=1,...,NR
σi
dove σi è il coe ciente di cotrattività del neurone i. L'uso di
dieren-ti pesi auto-ricorrendieren-ti può portare a diverse dinamiche per ogni neurone. Questo fattore architetturale è cruciale per ottenere una buona variabilità nelle dinamiche della funzione di transizione, arricchendo la rappresen-tazione dell'informazione temporale fornita dal reservoir, e può facilita-re l'addestramento del facilita-readout, risultando in una migliorata capacita' di predizione.
• Interazione non lineare tra le unità. E' implementato strutturando ˆ
W in modo che abbia valori extra diagonali non nulli, cioè le unità sono mutuamente connesse. Si osservi che utilizzando connettività di questo tipo insieme a connettività auto ricorrenti, le dinamiche su dierenti scale temporali sono arricchite con combinazioni non lineari delle dinamiche di ogni unità. Fin dal primo lavoro sulle ESNs [38], anche questo fattore si aerma come responsabile per la produzione di "ricche" dinamiche del reservoir.
• Regressione in uno spazio delle features aumentato. Questo fattore evidenzia quanto un reservoir non lineare e di grandi dimensioni in uenzi le performance. Questo punto dipende anche molto dal readout della ESN. La congettura infatti è che un readout lineare abbia migliori performance in presenza di uno spazio delle features non lineare e di grandi dimensioni. Varianti architetturali
I fattori identi cati nel paragrafo precedente danno luogo a varianti archi-tetturali del modello ESN standard. In particolare, consideriamo le seguenti architetture [5]:
• ESN full. Corrisponde all'ESN standard descritta in questa sezione, dove ˆ
W è caratterizzato da piena connettività.
• ESN sparse. Come sopra, ma ˆW è una matrice sparsa. Questa distin-zione è utile per studiare gli eetti delle interazioni non lineari tra unità del reservoir anche in presenza di un numero molto piccolo di neuroni connessi.
• DESN. Acronimo per Diagonal Echo State Network, nella quale ˆW è una matrice diagonale con elemento diagonale generico |wii| = σ, ∀i =
1, 2, . . . , NR, che corrisponde ad un reservoir con connessioni auto
ricor-renti e positive:
xi(n) = f (Winu(n) + σxi(n − 1)) ∀i = 1, 2, . . . , NR
I neuroni di una DESN implementano sistemi dinamici governati dalle stesse proprietà contrattive. In particolare, in assenza di variabilità del-l'input, tutti i neuroni nel reservoir di una DESN sono identici (come avere quindi un reservoir con un singolo neurone). Se la variabilità del-l'input viene aggiunta, ogni neurone del reservoir può dierenziare le sue dinamiche e quindi ci si aspetta che le sue performance predittive siano migliori.
• RDESN. Random Diagonal Echo State Network, che consiste in una DESN con la possibilità di dierenziare i pesi auto ricorrenti, che sono scelti secondo una distribuzione uniforme nell'intervallo [−σ, σ], che è un parametro sottoposto a model selection. Questa variante è usata prevalen-temente per valutare l'in uenza di dinamiche con diverse scale temporali sulle performance del modello, comparandole con l'architettura DESN.
Figura 2.3: Architettura di una ϕ-ESN, con tre unità di input, due unità di output. La parte dinamica del reservoir contiene quattro unità ricorrenti, mentre quella statica contiene dieci unità feed-forward. Immagine presa da [5].
• ϕ-ESN. L'idea che sta alla base di questa variante viene dal Teorema di Cover [44] sulla separabilità dei pattern, il quale aerma che un proble-ma di classi cazione è linearmente separabile con proble-maggiore probabilità se proiettato non linearmente in uno spazio delle features molto ampio. La ϕ-ESN proietta lo stato ricorrente del reservoir in uno spazio di grandi dimensioni, attraverso una funzione ssa e non lineare. La funzione di transizione di stato τ calcolata dal reservoir di una ESN può essere vista come la decomposizione in una funzione di codi ca τ0 ed una funzione ϕ:
τ = ϕ ◦ τ0 ϕ : RNR→ RNϕ
in cui RNϕ è il nuovo spazio aumentato. Il reservoir è quindi diviso in una
parte ricorrente, che implementa τ0 ed agisce come il reservoir standard,
ed una parte statica non ricorrente che implementa ϕ: ϕ(x(n)) = fϕ(Wϕx(n))
dove Wϕ∈ RNϕ×(NR+1)è la matrice dei pesi per le connessioni dalla parte
ricorrente a quella statica del reservoir. Wϕviene inizializzata
casualmen-te e non viene sottoposta ad addestramento. In Figura 2.3 è illustrata l'architettura di una ϕ-ESN. Si osservi che la parte ricorrente può essere organizzata secondo una delle architetture viste precedentemente. La funzione ϕ implementata dalla parte statica del reservoir incrementa la non linearità della funzione di transizione di stato τ, facilitando il readout
Figura 2.4: ESN con readout multipli. Essi sono attivati in modo adattivo tramite moduli di controllo separati.
per task che richiedono maggiori capacità di mapping non lineare. Tuttavia è importante osservare che ϕ-ESN non introduce dinamiche ri-correnti, nè un apprendimento non lineare (dato che il readout rimane lineare).
• Readout multipli. Relativamente alle dinamiche con scale temporali multiple, i sistemi con dinamiche complesse possono essere approssimati meglio utilizzando più di un readout [13]. In questo caso, se lo stato del reservoir al tempo n è il vettore x(n), possiamo scrivere l'output y(n) della rete come somma delle predizioni dei singoli readout
y(n) =X
i
pi(n)yi(n)
in cui pi(n) ∈ [0, 1]è un peso dipendente dal tempo, e yi(n)rappresenta la
predizione fatta dal readout i-esimo al tempo n. Per ogni readout si ha la predizione yi(n) = Woutix(n)in cui Wouti è il vettore dei pesi del readout
i. I pesi pi(n)implementano un modulo di controllo tramite la funzione
softmax:
pi(n) =
exp(x(n)wi)
P
jexp(x(n)wj)
in cui wi denota il vettore dei pesi per la softmax di ogni modulo
(Figu-ra 2.4).
Con questa formulazione, quando pi(n)avrà valore elevato, il modulo
cor-rispondente dominerà la predizione globale y(n). Questo consente ai di-versi readout di specializzarsi nella predizione dell'output a determinate epoche, mentre il loro contributo poco accurato verrà ignorato nelle epoche restanti in cui pi(n)assumerà valore basso. In Figura 2.4 è illustrato uno
schema dell'architettura. I pesi wi e Wouti possono essere sottoposti ad
apprendimento congiunto tramite discesa del gradiente, anche se in pra-tica i wi vengono inizializzati casualmente, ed i Wouti allenati risolvendo
un problema dei minimi quadrati. Infatti yp(n) = Xp(n) ˆW in cui W = [ ˆWoutT 1, ˆW T out2, . . . , ˆW T outn] T mentre Xp(n) = [p1(n)x(n), p2(n)x(n), . . . , pn(n)x(n)]
I pesi wisono inizializzati casualmente da una distribuzione uniforme
sul-l'intervallo [−1, 1] e poi moltiplicati per una costante, la cui scelta è fon-damentale per avere buona variabilità dei pi(n)nel tempo ed ottenere una
buona performance.
Si osservi in ne che questa variante funziona bene almeno quanto la nor-male architettura con singolo readout. Se infatti tutti i Wouti venissero
posti uguali al singolo modulo Wouts, la performance prodotta dalla
nuo-va rete sarebbe equinuo-valente a quella prodotta dal solo Wouts, perchè i pesi
pi(n)si sommano all'unità per ogni timestep [13].
Reservoir basato su matrici di permutazione
Un'importante metodo di inizializzazione è quello che caratterizza le ESNs aventi matrice di connettività ˆW del reservoir ortogonale ( ˆW ˆWT = I). Intuitivamente
con una tale architettura, ciascun input viene mappato in una direzione orto-gonale distinta, dando luogo ad una maggiore capacità di memoria del modello [29]. Sono presenti in letteratura tre classi di modelli [26] di questo tipo, con topologie mostrate in Figura 2.5:
• Delay line reservoir (DLR), composto da unità organizzate in linea. Solo gli elementi sulla sub-diagonale inferiore della matrice ˆW del reservoir hanno valori non nulli ( ˆWi+1,i= ri, i = 1, . . . , N − 1).
• DLR con feedback (DLRB), che ha la struttura analoga al modello DLR ma ogni unità è connessa anche al neurone precedente. Gli elementi non nulli di ˆW sono sulle sub-diagonali superiore ed inferiore ( ˆWi+1,i=ri e
ˆ
Wi,i+1= bi).
• Simple cycle reservoir (SCR), nel quale le unità sono organizzate ad anel-lo. Gli elementi non nulli sono sulla sub-diagonale inferiore ( ˆWi+1,i=ri) e
sull'elemento nell'angolo superiore destro ( ˆW1,N = rN).
Nel caso di utilizzo delle architetture appena viste, tutte le connessioni della matrice Win vengono inizializzate allo stesso valore γ > 0, mentre il loro segno
è determinato casualmente tramite una distribuzione di Bernoulli di media 1/2. Il valore di γ è sottoposto a validazione.
Per evidenziare i pregi che giusti cano l'esistenza dei modelli appena introdotti, vanno premesse alcune de nizioni. In [27], viene quanti cata la capacità di una rete ricorrente di rappresentare gli eventi passati. La memory capacity, dato il ritardo k, misura il coe ciente di correlazione quadratica (indicato con ρ) tra il segnale di input ritardato di k unità di tempo ed il segnale di output dell'unità del readout addestrata a riprodurre il segnale di input con ritardo k:
Figura 2.5: (a) DLR. (b) DLRB. (c) SCR.
quindi se u(n) è l'input, l'output atteso per l'unità k-esima (avente output yk(n))
è u(n-k).
La short term memory globale della rete è data da [27] M C =
∞
X
k=1
M Ck.
Sotto l'assunzione di avere un input indipendente ed identicamente distribui-to (i.i.d.), è stadistribui-to dimostradistribui-to [27] che per una rete con NR neuroni ricorrenti
M C ≤ NR.
Per le architetture con reservoir ortogonale si può dimostrare che la short term memory può essere portata arbitrariamente vicino ad N [26].
Le ragioni che stanno alla base dei vantaggi apportati da questa particolare organizzazione del reservoir risiedono nei di fenomeni critici dei sistemi dina-mici.
I fenomeni critici sono eventi che si veri cano in prossimità di una transizio-ne tra due fasi di un sistema dinamico. Tale transiziotransizio-ne può essere de nita in funzione di alcuni parametri del sistema (che individuano un punto di tran-sizione). Tipicamente, intorno al punto di transizione, il sistema assume un comportamento caotico, ed in questo stato le capacità predittive di una ESN possono essere migliori di quelle delle ESN ordinarie [28]. Per individuare sotto quali condizioni una ESN viene portata nello stato critico, trascuriamo l'eetto dell'input, in modo che l'evoluzione temporale dello stato al tempo n sia de-scritta solo da ˆWn. Sia pn la proporzione di elementi non nulli in ˆWn, e qn
il numero di elementi non nulli della stessa matrice. Quindi qn = NR2pt dove
NR è il numero di neuroni del reservoir. Quando t → ∞, pn può convergere,
crescere, decrescere, o variare intorno al suo valore medio, che assumiamo essere p∞. De niamo, seguendo la trattazione in [28] o = pp∞0 come un parametro
ap-propriato per determinare il punto critico di una ESN. Prove empiriche hanno permesso di de nire tale punto critico come pc= p0= p∞(o = 1). Inoltre vale
la stima pc≈ N1R, da cui segue qc≈ NR(dato che qc = NR2pc). In particolare, la
condizione qc = NR (exact critical structure) è soddisfatta se ogni riga ed ogni
colonna del reservoir contengono un elemento non nullo (matrice ortogonale). In tal caso, la rete si trova nella sua regione critica, nella quale l'evoluzione tem-porale del reservoir non perde tutte le sue connessioni (fase zero) nè acquisisce piena connettività (fase di saturazione). E' possibile che la struttura non abbia convergenza per t → ∞: possono veri carsi occorrenze di strutture periodiche o prive di ripetizioni, che aiutano nella predizione di serie temporali periodiche o aperiodiche. Si congettura quindi che per le ESN ortogonali, la probabilità che si trovi una rete con ottime capacità predittive è molto più alta rispetto alle ESN ordinarie.
Figura 2.6: Gra co della recti er. Recti er
L'uso di funzioni di attivazioni alternative alla tangente iperbolica e' stato inve-stigato il letteratura. Per quel che riguarda la ESN, in [45] viene mostrato che l'uso di funzioni di attivazione non monotone, sono responsabili del miglioramen-to della performance, causando il decremenmiglioramen-to del numero di condizionamenmiglioramen-to della matrice degli stati. In questo contesto, è stato preso in considerazione nella tesi l'uso di recti er come funzione di attivazione. La recti er [32] è una funzione di attivazione de nita come la parte positiva del suo argomento (gra co in Figura 2.6):
f (x) = x+= max(0, x)
Un neurone che usa questa funzione viene anche chiamato recti ed linear unit (ReLU). Usando la recti er è facile ottenere rappresentazioni sparse. Per esempio, supponendo un'inizializzazione uniforme dei pesi, circa il 50% delle unità nascoste hanno output nullo. Oltre ad essere biologicamente plausibile, la sparsità ha anche vantaggi legati all'e cienza ed alla lineare separabilità dei dati. Per ogni input solo un sottoinsieme di neuroni è attivo, e la computazione è lineare su tale sottoinsieme: una volta che esso viene selezionato, l'output è funzione lineare dell'inpupt. Pertanto la funzione calcolata da ogni neurone o dall'intera rete è lineare "per parti". In questa ottica il modello può essere visto come un numero esponenziale di modelli lineari che condividono parametri[32]. A causa di questa linearità, il gradiente ha valore costante, in contrasto con il gradiente di funzioni non lineari come la sigmoide (che diventa sempre più piccolo man mano che il segnale di input cresce, dando luogo al fenomeno del
gradient vanishing). Il gradiente costante generalmente da luogo ad un appren-dimento migliore.
Con queste argomentazioni si evince che l'uso di questa funzione permette una fase di apprendimento più veloce ed e cace nel caso di architetture neurali deep (caratterizzate da tre o più livelli), in cui il fenomeno del gradient vanishing è più frequente, dovendo propagare il gradiente su più livelli. L'uso di recti er è ormai il metodo di apprendimento standard, soprattutto per task appartenenti alla computer vision e speech recognition [32]. Nonostante in RC non ci sia calcolo del gradiente per i pesi ricorrenti, dato che i pesi del reservoir non sono sottoposti ad addestramento, resta interessante valutare gli eetti della sparsi-tà nella rappresentazione di stato, inerentemente indotti dall'uso della recti er. Questo rende interessante investigare l'uso di tale funzione in combinazione con la ESN.
2.2 Tree Echo State Network
Il modello Tree Echo State Network (TreeESN) [6] estende l'applicabilità del-l'approccio basato su ESN a dati strutturati in forma di alberi. L'architettura di una TreeESN è basata su quella di una ESN. La TreeESN calcola lo stato per ogni nodo dell'albero in modo ricorsivo, che corrisponde ad un processo in cui il reservoir viene applicato in modo bottom-up dalle foglie alla radice. Per modellare funzioni in cui strutture di input sono mappate in vettori non strutturati, lo stato calcolato dal reservoir può essere trasformato in un dato di dimensione ssa secondo diverse funzioni di state mapping [6]. Le caratte-ristiche di contrattività dello stato del reservoir sono ereditate dalla ESN per sequenze.
2.2.1 Trasduzioni ricorsive su alberi
Il concetto di trasduzione strutturale [6] e l'estensione del dominio di input sono la base per estendere il paradigma RC per sequenze a dati strutturati ad albero. Con riguardo alla notazione, un albero è rappresentato con t ed il suo insieme di nodi è N(t), dove |N(t)| è il numero di nodi in t. La radice dell'albero è indicata con root(t), il glio i-esimo del nodo n è chi(n). In ne il sottoalbero
radicato nel nodo n è t(n). In una de nizione ricorsiva, un albero k-ario può essere de nito come l'albero vuoto, indicato con nil, oppure come il nodo radice n ed i k sottoalberi radicati nei suoi gli, denotato come n(t(ch1(n), . . . , chk(n)))
(si noti che qualcuno dei gli può essere assente, dando luogo al sottoalbero vuoto) [6]. Dati RNU come dominio di input ed RNY come dominio di output,
siamo interessati a funzioni in cui tali domini siano alberi: T : (RNU)]k → (RNY)]k
in cui (RNU)]k e (RNY)]k indicano i domini estesi e strutturati per alberi di
arietà k. Esistono trasduzioni di diversi tipi. T è una trasduzione da albero ad albero se il suo output è isomorfo all'input (Figura 2.7). T è una trasduzione da albero ad elemento se ha come output un singolo vettore, ed il dominio di output si riduce allo spazio vettoriale di dimensione ssa RNY (Figura 2.8).
Una trasduzione T è detta causale se l'output calcolato per ogni nodo n di un albero in input dipende solo da n e dai suoi discendenti. Questa
condi-Figura 2.7: Trasduzione da albero ad albero.
Figura 2.8: Trasduzione da albero ad elemento.
zione è necessaria e su ciente per ammettere trasduzioni ricorsive. In alcune applicazioni questa assunzione non è su ciente, e sono stati sviluppati modelli contestuali [30], per tenere conto del contesto nel quale il nodo è posiziona-to. T è stazionaria se il mapping applicato ad ogni nodo è indipendente dal nodo stesso. In ne, una trasduzione adattiva è quella ottenuta in seguito all'ap-prendimento. Assumeremo di avere sempre a che fare con trasduzioni causali e stazionarie [6].
Dato l'approccio ricorsivo sugli alberi, siamo interessati a considerare trasduzio-ni che permettono una formulazione ricorsiva dello stato. A tal proposito, una trasduzione T può essere decomposta come T = Tout◦ Tenc :
• Tenc : (RNU)]k → (RNR)]k, trasduzione di codi ca che mappa un albero
di input in un albero isomorfo avente per ogni nodo le features dello stato corrispondente (x(t) = Tenc(t))
• Tout : (RNR)]k → (RNY)]k, trasduzione di output, che mappa la
rappre-sentazione strutturata dello stato di un albero, nell'output corrispondente y(t) = Tout(x(t)).
La trasduzione di codi ca si risolve in una funzione che opera nodo per nodo τ : RNU × RkNR → RNR
implementata dall'equazione
x(n) = τ (u(n), x(ch1(n)), . . . , x(chk(n))) (2.7)
che descrive la relazione tra lo stato corrispondente ad un nodo n e gli stati relativi ai suoi gli. Si noti che se uno dei gli fosse assente, verrebbe usato lo
stato xnil = 0 ∈ RNR. In maniera analoga alla trattazione della ESN, anche
qui viene introdotta una versione iterata sull'intero albero (che prima era una sequenza, Equazione (2.2)), denotato da ˆτ [6]:
ˆ τ : (RNU)]k× RNR → RNR ponendo tk(n) =t(chk(n))si ha ˆ τ (t, xnil) = ( xnil t = nil
τ (u(n), ˆτ (t1(n)), xnil), . . . , ˆτ (tk(n)), xnil)) t = n(t1(n)), . . .tk(n))
dove lo stato della radice è
x(root(t)) = ˆτ(t, xnil). (2.8)
Quindi il calcolo dello stato corrispondente ad un albero di input, cioè la costru-zione di Tenc(t), consiste nell'applicazione di ˆτ a t. In accordo con l'assunzione
di stazionarietà, l'Equazione (2.7) è applicata per ogni nodo n, prendendo in input l'etichetta di n e gli stati già calcolati per i gli di n.
Per quanto riguarda la trasduzione di output, distinguiamo due casi. Nel caso di una trasduzione da albero ad elemento, una funzione di mapping χ è applicata al risultato di Tenc, per ottenere uno stato di dimensione ssa, rappresentativo
dell'intera struttura di input: χ : (RNR)]k → RNR. L'intera trasduzione in
que-sto caso diventa T = Tout◦ χ ◦ Tenc. Nel seguito ci focalizzeremo su trasduzioni
da albero ad elemento.
2.2.2 Descrizione del modello
Una TreeESN implementa trasduzioni causali, stazionarie ed adattive su domini strutturati. Il reservoir corrisponde ad una trasduzione di codi ca ssa, mentre il readout ad una trasduzione di output adattiva [6]. Le sottosezioni seguenti descrivono le componenti di una TreeESN.
Reservoir di una TreeESN
In accordo a quanto detto n qui, lo stato corrispondente ad un nodo n di un albero t è calcolato come
x(n) = f (Winu(n) + k X i=1 ˆ W x(chi(n)))
in cui le matrici sono de nite come nella Sezione 2.1, ed f = tanh. In pratica, l'equazione precedente viene applicata ricorsivamente ad ogni nodo dell'albero, seguendo la topologia di t. Questo corrisponde all'implementazione della fun-zione ˆτ (Equafun-zione (2.8)). Un esempio della procedura è mostrato in Figura 2.9. L'obiettivo di una TreeESN è di codi care un insieme di strutture di input -nite, non un segnale di input di natura temporale, come avviene con la ESN standard [6].
Figura 2.9: Esempio del processo di codi ca del reservoir di una TreeESN. Le etichette dei nodi sono codi cate mediante 1-of-k encoding (immagine presa da [6]).
State Mapping
Avendo a che fare con trasduzioni da albero ad elemento, il readout non può essere applicato direttamente allo stato calcolato dal reservoir. Infatti la rappre-sentazione dello stato è isomorfa all'input, mentre il numero dei parametri del readout (pesi della matrice Wout) è sso. Quindi la rappresentazione strutturata
di un albero x(t) è trasformata in uno spazio di dimensione ssa NR tramite
la funzione χ (Sezione 2.2.1). Prenderemo in considerazione due possibili scelte per implementare tale funzione [6]:
• Root State Mapping consiste nella selezione dello stato della radice di t:
χ(x(t)) = x(root(t)) (2.9)
• Mean State Mapping calcola la media sugli stati dei nodi in t: χ(x(t)) = 1
|N (t)| X
n∈N (t)
x(n) (2.10)
Usando il mean state mapping, la rappresentazione risultante dipende in egual modo dallo stato di tutti i nodi dell'albero, invece che solo da un nodo par-ticolare. La scelta della funzione di state mapping dipende ovviamente dalla natura del problema in esame. Nel seguito, chiameremo la TreeESN che fa uso di root state mapping TreeESN-R, e quella che adopera il mean state mapping TreeESN-M.
Readout di una TreeESN
Il readout consiste in NY unità lineari. Per trasduzioni albero ad albero, esso è
applicato allo stato di ogni nodo della struttura in input y(n) = Woutx(n).
Per trasduzioni albero ad elemento, il readout è applicato all'output della state mapping function χ
y(t) = Woutχ(x(t)) (2.11)
Il readout viene sottoposto ad apprendimento in modo analogo a quanto vi-sto per la ESN su sequenze. Se la trasduzione è albero ad albero, uno stato collezionato nella matrice X (Equazione (2.5), senza però scartare il washout), corrisponde ad un nodo. Diversamente se la trasduzione è albero ad elemento (Equazione (2.11)) uno stato collezionato in X corrisponde ad un intero albero [6].
2.2.3 Markovanità di una TreeESN
Per la TreeESN valgono le stesse considerazioni fatte per l'approccio ESN sem-plice (contrattività, ESP, condizioni necessarie e su cienti). Sono però necessari degli adattamenti per adeguare i risultati descritti in precedenza alla nuova na-tura dei dati in input.
In particolare, la funzione di transizione di stato diventa τ : RNU × RkNR→ RNR
e la contrattività dell'Equazione (2.4) vale, se esiste un parametro non negativo C < 1tale che per ogni u ∈ RNU e per ogni x
1, . . . , xk, x01, . . . , x0k∈ R
NR valga
||τ (u, x1, . . . , xk) − τ (u, x01, . . . , x0k)|| ≤ C max
i=1,...,k||xi− x 0
i||. (2.12)
Vale analogamente il Teorema 1 (sull'albero generico t piuttosto che su sequen-za), sotto le stesse ipotesi dell'approccio ESN, purchè il concetto di su sso venga adeguato alla nuova natura dei dati. Infatti il su sso di altezza h ≥ 0 di un albero t, indicato con Sh(t), è l'albero ottenuto da t rimuovendo ogni nodo
la cui profondità è maggiore di n [6] (ponendo sempre tk(n) =t(chk(n))):
Sh(t) =
(
nil h = 0 o t = nil
n(Sh−1(t1(n)), . . . , Sh−1(tk(n))) n > 0 e t = n(t1(n), . . . ,tk(n))
Quindi, supponendo che il sottoinsieme degli stati che sono assunti dal reservoir della TreeESN è limitato con diamotro diam, dati due alberi t, t' che condivi-dono un su sso di lunghezza n, cioè è Sh(t) = Sh(t'), e due stati x, x0 ∈ RNR
il risultato del Teorema 1 diventa
||ˆτ (t, x) − ˆτ(t', x0)|| ≤ Chdiam.
In Figura 2.10 è illustrato il concetto di Markovianità esteso ad alberi, e quindi l'organizzazione dello spazio degli stati del reservoir in una TreeESN.
Per concludere, vediamo come cambia la condizione su ciente per la con-trattività dell'Equazione (2.3). Se assumiamo che la distanza Euclidea sia una metrica su RNR, allora per ogni etichetta in input u ∈ RNU e stati dei nodi gli
Figura 2.10: Esempio gra co dell'organizzazione degli stati del reservoir di una TreeESN. Alberi con su ssi comuni corrispondono a punti vicini nello spazio degli stati del reservoir RNR.
x1, . . . , xk, x01, . . . , x0k∈ RNR si ha:
||τ (u, x1, . . . , xk) − τ (u, x01, . . . , x0k)||2 (Def. stato del reservoir)
=||tanh(Winu + k X i=1 ˆ W xi) − tanh(Winu + k X i=1 ˆ
W x0i)||2 (tanh continua, monotona)
≤|| ˆW k X i=1 (xi− x0i)||2 ||AB|| ≤||A||||B|| ≤|| ˆW ||2 k X i=1 ||xi− x0i||2 (De nizione di massimo) ≤k|| ˆW ||2 max i=1,...,k||xi− x 0 i||2 σ = k|| ˆW ||2 =σ max i=1,...,k||xi− x 0 i||2
Quindi in accordo con l'Equazione (2.12) la contrattività vale se σ < 1, che è condizione su ciente per l'ESP di una TreeESN. Questo risultato fornisce un procedimento per scalare la matrice ˆW del reservoir di una TreeESN in modo che valgano le proprietà sulla stabilità del processo di calcolo dello stato indi-pendentemente dall'input [6].
Anche se la funzione τ non fosse contrattiva usando la norma Euclidea, potreb-be esserlo usando un'altra norma, e le argomentazioni sopra sarebpotreb-bero comun-que valide. Per comun-questa ragione, nella pratica, sono utilizzati anche valori di σ leggermente maggiori di uno [6]. In questa tesi viene estesa l'analisi con una impostazione più pratica in cui, uniformandosi al caso comune delle ESN, viene
scalato il raggio spettrale ρ della matrice del reservoir.
Si osservi inoltre che TreeESN è una generalizzazione dell'approccio ESN stan-dard. Infatti, se i dati di input sono sequenze e non alberi (k=1, alberi unari), l'Equazione (2.7) si riduce all'Equazione (2.1) del caso ESN standard, fornendo quindi un framework unitario per il RC.
2.2.4 Risultati sperimentali TreeESN
La TreeESN e' stata applicata con successo a problemi real-world su domini di alberi, ad esempio nell'area di elaborazione di documenti e nella tossicologia computazionale [6].
In [6] viene studiata la relazione tra le due funzioni di state mapping, viste nei paragra precedenti, e le proprietà Markoviane. Gli eetti di tale relazione sono stati investigati attraverso esperimenti su task reali, e su task arti ciali creati ad-hoc. In particolare, TreeESN-R, che preserva l'organizzazione Markoviana delle dinamiche del reservoir, ha delle performance proporzionali al grado di Markovianità del task. Invece TreeESN-M raggiunge performance promettenti su task con caratterizzazione non-Markoviana, rivelandosi uno strumento utile avendo a che fare con task di cui non è chiaro il grado di Markovianità. La TreeESN è stata utilizzata in un task di regressione lineare, con l'obietti-vo di predire il tempo di completamento di applicazioni parallele implementate usando i pattern visti nel Capitolo 1 [1], i cui risultati hanno messo le basi per il lavoro descritto in questa tesi.
I risultati ottenuti sono stati confrontati con quelli del modello analitico della Sezione 1.2.1, con particolare enfasi sulle applicazioni che evidenziavano eccesso di parallelismo. Con un procedimento simile a quello che si vedrà nel Capitolo 3, è stato generato un insieme di programmi paralleli, etichettato con i target desi-derati e rappresentato in un dataset. Sempre in [1], sono state prodotte dierenti rappresentazioni del dataset originario, alcune delle quali includono informazio-ni proveinformazio-nienti dal modello analitico, per investigare l'in uenza di quest'ultimo sulle capacità predittive del modello. Dopo l'usuale processo di validazione e test, i risultati ottenuti dal dataset originario non erano soddisfacenti, raggiun-gendo un errore del 19%. Viceversa il dataset con le informazioni sul modello dei costi ha mostrato ottimi risultati, con un errore del 3.2% [1].
Sul dataset analizzato la TreeESN si è mostrata capace di catturare la relazione esistente tra alberi e target anche nei casi in cui il modello dei costi non poteva essere applicato.
Capitolo 3
Approccio TreeESN per
l'High Performance
Computing
In questo capitolo verrà analizzata la costruzione di un task di apprendimento automatico, dalla generazione del dataset, all'addestramento e stima del rischio del modello TreeESN. L'obiettivo è ottenere un modello predittivo di regressione lineare supervisionata, che prenda in input uno skeleton tree, predicendone il tempo di completamento oppure il consumo di energia attesi. Verranno utiliz-zati come baseline i risultati descritti nella Sezione 2.2.4, che sono stati ottenuti nella tesi in [1], la quale fornisce anche una prima implementazione della TreeE-SN, e di conseguenza delle rappresentazioni per i dati, che verranno tuttavia rigenerati. In questa sede verranno evidenziate solo le novità introdotte duran-te la costruzione del task, per una descrizione dettagliata dell'implementazione della TreeESN si veda [1].
3.1 Analisi del problema e stato dell'arte
In questa sezione verranno analizzati i motivi per cui un approccio di machine learning è interessante per il problema in esame, e citati alcuni dei risultati più rilevanti presenti in letteratura.
Per quanto riguarda il tempo di completamento, abbiamo a disposizione un modello analitico dei costi, descritto nella Sezione 1.2. Il modello non presenta riferimenti al massimo numero di risorse a disposizione nell'architettura in uso, e tutta la trattazione viene fondata sulla seguente assunzione [4]:
Assunzione 1. L'architettura sottostante soddisfa il grado di parallelismo ri-chiesto dallo skeleton tree del programma che viene eseguito. (difetto di paral-lelismo)
Il caso opposto, indicato come eccesso di parallelismo, non viene quindi preso in considerazione dal modello analitico. Per questo motivo la costruzione di un modello di apprendimento predittivo per il tempo di completamento di-venta interessante, ai ni di valutarne il comportamento nelle zone ombra, cioè i casi che non vengono trattati adeguatamente dal modello analitico.
Con riguardo allo stato dell'arte, possiamo dividere gli approcci in due macro-categorie:
• Approcci basati sulla simulazione, in cui la predizione vera e propria è preceduta da una fase di simulazione che prevede l'esecuzione (parziale) dell'applicazione in esame, o di sue con gurazioni.
A tal proposito, in [14], partendo dall'idea che molti codici paralleli sono iterativi, presenta un API che permette la predizione delle performance basandosi sull'osservazione di esecuzioni parziali. Con esecuzioni brevi che impiegano al più l'1% del tempo di esecuzione totale, viene ottenuta un'accuratezza del 97%.
In [16], si utilizza un approccio basato sulla simulazione per predire il consumo di energia di applicazioni basate su MPI [19]: utilizzando e ca-librando tre modelli per rappresentare tempi di comunicazione, tempi di computazione ed energia consumata, viene dimostrato che la predizione del consumo energetico è molto vicina a quello eettivo. I modelli svilup-pati vengono poi integrati nel toolkit di simulazione SimGrid [17]. • Approcci puramente predittivi, in cui le che riguardano i programmi
e le loro caratteristiche vengono utilizzate per costruire un modello pre-dittivo, che sia in grado di stimare le performance di un programma "sco-nosciuto" senza il bisogno di eseguirlo. In [12] viene proposto un metodo basato sulla regressione lineare per determinare tempo di completamento ed energia consumata di un'applicazione (response), dato il numero di core e la loro frequenza (predictors). In particolare, viene usata l'interpolazione partendo da valori ottenuti con delle osservazioni su poche con gurazioni, per costruire un modello analitico che permette di predire le performances sulle con gurazioni non viste, con un'accuratezza del 96%.
Un primo esempio di approccio che fa uso di apprendimento automatico (Random Forest Modeling) è mostrato in [18], con l'obiettivo di stimare il consumo energetico di applicazioni OpenMP durante la compilazione. L'approccio è stato testato usando applicazioni OpenMP come NAS, mol-tiplicazione di matrici e computazioni basate sul pattern stencil, variando la dimensione del problema. L'approccio proposto stima l'energia consu-mata da diverse varianti della stessa applicazione con un valore del coef- ciente di determinazione R2pari a 0.998, con le variazioni di energia nel
dataset comprese tra 0.024 e 150.23 Joules.
In ne, in [15] viene proposto un approccio simile a quello di questa tesi, che fa uso di reti neurali non ricorrenti per creare un modello predittivo per il tempo di completamento di una speci ca applicazione (SMG2000), ottenendo un errore intorno al 5%.
3.2 Generazione dei dataset
In questa Sezione, verrà descritto il procedimento per la creazione di tutti gli alberi che costituiranno il dataset, dalla scelta dei "problemi giocattolo" che costituiscono le foglie dei nostri skeleton trees, all'acquisizione dei target (tempo di completamento e consumo di energia) di ciascuna istanza. Ogni albero è
annotato con i parametri ritenuti utili per migliorare la predizione. Ogni istanza del dataset contiene informazioni riguardanti:
• i sub-skeletons per la farm e la pipeline (che de niscono la struttura ad albero).
• il numero di workers per le farm.
• il tempo di servizio per lo skeleton sequenziale.
La strategia adottata per la generazione è basata sulle regole di riscrittura viste in Sezione 1.1.2. Per acquisire la misurazione del tempo di completamento, i programmi creati sono eseguiti su Ninja, una macchina con 64 processori Intel Xeon Phi 7210 (1.30GHz, 64 core, 4 way hyper-threading). Per la generazione dei dati relativi al consumo di energia è stata utilizzata la macchina Phiask, in quanto su Ninja non è stato possibile accedere ai contatori del processore che stimano l'energia consumata. Phiask è dotata di due processori Intel Xeon E5-2630 (2.30GHz, 2x6 core, two way hyper-threading), basata su un architettura Intel Sandy Bridge. Si osservi che il processo di generazione è analogo sia per il target energia, che per il tempo di completamento.
3.2.1 Scelta del codice sequenziale
Le foglie di ogni skeleton tree sono delle porzioni di codice sequenziale (business logic code [4]). Esse dipendono ovviamente dal particolare problema che si intende risolvere ricorrendo all'uso del parallelismo. Per gli scopi di questa tesi, ai ni di generare delle applicazioni più possibile simili ai casi pratici, sono stati scelti programmi sequenziali operanti su matrici. Variando l'ordine della matrice diventa possibile variare il comportamento del programma, in termini di tempo di esecuzione e di accessi in memoria. In particolare sono stati scelti il metodo di Jacobi per la risoluzione di sistemi lineari, ed il calcolo di AN data una matrice
A. Sono stati scelti problemi dierenti così da avere dati più realistici possibile su cui fare apprendimento supervisionato.
Analisi dei problemi giocattolo
Il metodo di Jacobi [3] è un metodo iterativo per la risoluzione di sistemi lineari Am = b, che calcola la soluzione dopo un numero teoricamente in nito di passi. Per calcolare la soluzione il metodo utilizza una successione m(k) che converge
verso la soluzione esatta del sistema lineare e ne calcola progressivamente i valo-ri arrestandosi quando due passi consecutivi della successione sono abbastanza simili tra di loro (criterio di convergenza). Scrivendo la matrice A come die-renza A = M − N, dove M è una matrice invertibile, allora la soluzione m di Am = b risolve anche le equazioni
M m = N m + b =⇒ m = M−1(N m + b)
partendo da un qualunque vettore m(0) si può allora costruire una successione
di vettori m(k)come
