Capitolo 1 - Dipartimento di Fisica

Capitolo 1 Riconoscimento e ricostruzione di tracce In questo capitolo si introduce il problema che si affronterà nel corso della tesi, il riconoscimento e la ricostruzione di tracce. Si descrivono, quindi, le caratteristiche generali che deve presentare un algoritmo per il riconoscimento e vari criteri per valutarne le prestazioni, e si passano in rassegna i principali metodi utilizzati.

1.1 Il problema sperimentale Lo scopo di questo lavoro è il riconoscimento e la ricostruzione di tracce di particelle cariche dell’esperimento L3. Il rivelatore L3, montato sull’acceleratore a fasci incrociati LEP (Large Electron Positron collider), deve fornire tutte le informazioni necessarie alla ricostruzione degli eventi causati dallo scontro delle particelle appartenenti ai due fasci, ovvero e- (elettroni) ed e+ (positroni). Una componente fondamentale dell’analisi degli eventi è la ricostruzione delle tracce delle particelle cariche prodotte nella collisione ee+. Al fine di poter effettuare questa analisi varie parti (sottorivelatori) di L3, disposte con simmetria cilindrica intorno all’asse dei fasci, sono dedicate alla rivelazione del passaggio di particelle cariche; l’insieme di questo tipo di sottorivelatori viene chiamato rivelatore tracciante (una descrizione più approfondita del rivelatore tracciante di L3 e dei dati da esso forniti è riportata nei Cap. 3 e 4).

1.1 Il problema sperimentale

2

Per introdurre il lavoro svolto, riconoscimento e ricostruzione di tracce nella proiezione XY (quella, cioè, ortogonale all’asse dei fasci), è necessario soffermarsi brevemente sui dati forniti dal rivelatore tracciante di L3: questo è formato da vari sottorivelatori che funzionano con principi diversi e forniscono informazioni diverse (la camera ad espansione temporale, Cap.3; il rivelatore di microvertice al silicio, Cap.4;…). Da tutti i vari componenti del rivelatore tracciante è comunque possibile ottenere punti in coordinate xy (fig. 1.1), che possono essere divisi in tre categorie:

y

x

Fig. 1.1 Campione di evento reale (le unità indicate sugli assi sono arbitrarie).



Punti che segnalano il passaggio di particelle cariche provenienti dal vertice di interazione primario (il punto di collisione fra le particelle dei fasci) o di prodotti di decadimento secondario di particelle primarie.

1.1 Il problema sperimentale 

3

Punti che segnalano il passaggio di particelle spurie non appartenenti all’evento, e quindi di scarsa rilevanza per l’analisi fisica da effettuare (ad esempio particelle prodotte da collisioni con il gas residuo presente nel tubo a vuoto dell’acceleratore).



Punti di rumore (ad esempio il rumore intrinseco dei rivelatori).

Il sistema di ricostruzione dell’esperimento deve riuscire ad individuare i punti appartenenti alla prima categoria, e da questi individuare le tracce delle particelle cariche prodotte nell’evento, cioè la traiettoria che hanno percorso nel rivelatore. Benché la progettazione e la realizzazione di un sistema di ricostruzione siano estremamente dipendenti dal rivelatore per cui il sistema è ideato, il riconoscimento di tracce presenta molte caratteristiche generali che possono essere ritrovate in tutti i metodi. Nel paragrafo successivo si darà una descrizione schematica di questo problema di riconoscimento in maniera più generale, per individuare le caratteristiche fondamentali che un sistema di riconoscimento deve possedere e per definire criteri generali per valutarne le prestazioni.

1.2 Il riconoscimento e la ricostruzione Dato un insieme di misure in un rivelatore, il compito del riconoscimento di tracce (ref. [1]) è dividere l’insieme in classi tali che: 

Ciascuna classe contenga le misure che potrebbero essere causate dalla stessa particella.



Una classe (possibilmente vuota) contenga tutte le misure che non possono essere associate ad una particella con sufficiente certezza (rumore, punti ambigui).

Molti metodi di riconoscimento e di ricostruzione di tracce sono basati su due capacità complementari: innanzitutto, si cerca di trovare dei candidati a traccia, cioè insiemi di

1.2 Il riconoscimento e la ricostruzione

4

punti che potrebbero rappresentare la traiettoria di una particella carica; quindi li si prova rigorosamente con un fit ad un modello di traccia. Il modello di traccia viene costruito a partire dall’equazione di moto delle particelle cariche in presenza di un campo magnetico: nei rivelatori traccianti si fa spesso uso di un campo magnetico statico, perché questo permette la misura del momento delle particelle cariche dalla curvatura della loro traiettoria. La traiettoria di una particella carica in un campo magnetico statico è data dall’equazione di Lorentz:

dp dt

 qv  B 

q pB m

(1.1)

dove p è il momento della particella, q la carica, v la velocità, m la massa, B il valore del campo magnetico alla posizione x della particella, e  indica il prodotto vettoriale. Moltiplicando entrambi i membri per p si ottiene (ref. [2]):

d2 x q dx B 2  ds p ds

(1.2)

dove s è la lunghezza curvilinea dell’arco di traccia. L’eq. (1.2) può essere riscritta come: dx n ds

dn  an  B ds

(1.3)

dove n è il vettore unitario tangente alla traiettoria nel punto x e a è una costante. Con le unità di misura GeV/c, tesla e metri, e misurando la carica in multipli q’ della carica dell’elettrone, a diventa: a  0.2998

q p

dove la costante numerica è la velocità della luce nel vuoto.

(1.4)

1.2 Il riconoscimento e la ricostruzione

5

Questo sistema di equazioni di due equazioni differenziali ha cinque costanti di integrazioni, cioè xo, yo, nx, ny ad un dato zo, e a, o equivalentemente q’/||p||. In un campo magnetico omogeneo (B costante nello spazio), la soluzione della eq. (1.4) è un’elica che si avvolge attorno alla direzione di B (negli esperimenti di alte energie la situazione più comune, come avviene anche in L3, è quella in cui B può essere assunto costante e parallelo all’asse del fascio). I vari metodi procedono di conseguenza in due passi: primo, vengono selezionati i sottoinsiemi di misure che formano i candidati a traccia, eseguendo il riconoscimento propriamente detto; secondo, viene applicata una funzione di decisione per accettare o meno il candidato come traccia basandosi sul modello sopra descritto e facendo uso di tutta la conoscenza a priori delle prestazioni del rivelatore: risoluzione del rivelatore, errori sistematici e statistici. Tramite il fit, utilizzato per la funzione di decisione, si completa anche la ricostruzione, determinando i cinque parametri dell’espressione analitica delle tracce.

1.2.1 Qualità delle tracce Se due o più tracce sono incompatibili (ad esempio condividono alcuni punti) e una sola di queste deve essere scelta come quella corretta, è necessario avere una qualche misura della qualità della traccia. Una scelta abbastanza naturale è quella di usare il test del 2 del fit. D’altra parte questa è in molti casi una scelta arbitraria, perché, nonostante i valori di 2 siano distribuiti secondo una legge nota, un valore piccolo di 2 non indica con certezza che una traccia è “migliore” di un’altra con 2 più alto, finché questi valori si trovano all’interno dell’intervallo di confidenza considerato. Inoltre, se il modello di

1.2 Il riconoscimento e la ricostruzione

6

traccia non è completamente corretto, le tracce corte avranno in media un valore di confidenza più alto di quelle più lunghe. Il numero di punti e l’assenza di salti (regioni in cui dovrebbero essere presenti dei punti, ma che non vengono trovati) sono una misura piuttosto sicura di qualità. Questo porta in maniera naturale ad una ricerca gerarchica sulle tracce, in cui le tracce sono ricercate in ordine di lunghezza.

1.2.2 Lavorare con punti spaziali o nelle proiezioni Quando il rivelatore tracciante fornisce direttamente punti spaziali, con risoluzione confrontabile nelle tre dimensioni, la scelta dello spazio in cui lavorare è ovvia: il riconoscimento deve essere eseguito direttamente nello spazio. Nella maggior parte dei casi, però, i rivelatori traccianti forniscono solo una o due coordinate del punto di passaggio della particella con risoluzioni confrontabili. Per ricostruire la traiettoria di una particella nello spazio, in questi casi, ci sono due possibili scelte: 

Combinare varie proiezioni locali in punti spaziali (in 3 dimensioni) ed eseguire il riconoscimento di tracce sui punti spaziali ricostruiti.



Trovare le tracce indipendentemente nelle varie proiezioni (xy, xz, yz) e solo in seguito cercare delle associazioni.

La scelta della strategia da adottare è guidata da due aspetti: la topologia degli eventi e la realizzazione del rivelatore tracciante. Per eventi topologicamente semplici, lavorare in una proiezione (ad esempio la proiezione XY di L3) è sufficiente e veloce. Quando, però, gli eventi diventano più complessi, si preferisce lavorare nello spazio, perché le sovrapposizioni di tracce sono, in questo caso, abbastanza rare, ed il compito del

1.2 Il riconoscimento e la ricostruzione

7

riconoscimento elimina molte ambiguità. Lavorando in una proiezione, invece, le intersezioni sono molto comuni: come si può vedere nell’esempio di fig. 1.1, si ha un gran numero di sovrapposizioni fra le tracce; visualizzando l’evento in tre dimensioni, la maggior parte degli incroci fra le traiettorie delle particelle scomparirebbe. Non sempre, però, la ricostruzione di punti spaziali è una buona soluzione: l’efficienza di rivelazione di un punto è necessariamente più bassa che nelle proiezioni, essendo data dal prodotto delle efficienze di tutte le proiezioni utilizzate. Per concludere si può notare che il tempo di calcolo necessario per a lavorare nello spazio o su due proiezioni è equivalente: da una parte si devono ricostruire i punti tridimensionali e poi eseguire il riconoscimento, dall’altra si esegue il riconoscimento almeno due volte.

1.2.3 Efficienza Quando si cerca di ottimizzare un algoritmo, è opportuno avere una misura quantitativa delle sue prestazioni. Una definizione soddisfacente di efficienza per un sistema di riconoscimento è, però, estremamente dipendente dal rivelatore e dalle peculiarità dei dati che questo fornisce. In questa sezione, quindi, ci si limita a dare alcuni criteri per confrontare le prestazioni di sistemi di riconoscimento diversi su eventi con un numero noto di tracce (ad esempio per eventi simulati MonteCarlo). 

Per un numero di eventi con un numero fisso n di tracce ricostruibili per ciascuno, l’efficienza media per eventi di molteplicità n è E n  f

n , dove f è il numero di

tracce trovate correttamente in ciascun evento, e la media è eseguita su tutti gli eventi analizzati con molteplicità n. L’efficienza En, normalmente, decresce lentamente al crescere della molteplicità. A volte si cerca un’efficienza globale del

1.2 Il riconoscimento e la ricostruzione

8

metodo, basata cioè su un insieme di eventi con un numero variabile di tracce, ed in questo caso si definisce l’efficienza come E  E n 

f

n , dove la media su En

viene effettuata su tutti i possibili valori della molteplicità dell’evento. 

Può essere usata la frazione di eventi in cui tutte le n tracce sono ricostruite correttamente, cioè gli eventi in cui fn, ma questa è una misura molto severa, e decresce rapidamente con n.



La frazione di eventi in cui almeno una frazione minima (ad esempio il 90%) delle n tracce è stata ricostruita correttamente.



Una qualunque delle scelte precedenti, ma escludendo alcune tracce che sono difficili da riconoscere, come le tracce di particelle con un momento piccolo o le tracce in regioni particolari del rivelatore.

Tutti questi approcci, però, sono lontani dal fornire una definizione di efficienza che tenga conto di tutti i vari aspetti del problema del riconoscimento. Per essere utile, la definizione deve includere in qualche modo il numero di tracce ricostruite in maniera errata, cioè tracce costituite da punti appartenenti in realtà a tracce diverse, o contenenti punti spuri che non possono essere ragionevolmente associati con una traccia: più alto è il numero delle tracce non corrette, più bassa deve diventare l’efficienza.

A parte gli eventi con una molteplicità costante, è utile mettere in evidenza la dipendenza dell’efficienza dal numero di tracce n. Una buona definizione potrebbe essere, ad esempio:

En 



1 max 0, f  qw n



(1.5)

1.2 Il riconoscimento e la ricostruzione

9

dove n è la molteplicità, f il numero di tracce trovate correttamente, w è il numero di tracce errate, q è il fattore di “punizione” per le tracce errate e la media viene eseguita su tutti gli eventi di molteplicità . Un altro fattore importante è il tempo di calcolo del metodo, e qualche volta si cercano compromessi fra un metodo buono, ma molto lento, e uno veloce, ma meno efficiente. In molti casi, però, l’efficienza è la considerazione più importante, e normalmente si cerca di velocizzare un buon metodo piuttosto che usarne uno meno efficiente.

1.3 Metodi classici di riconoscimento di tracce Nel seguito si userà per i metodi di riconoscimento il termine algoritmo; i sistemi per il riconoscimento sono, in realtà, sistemi complessi di algoritmi, che chiamiamo algoritmi per comodità. I diversi metodi di riconoscimento di tracce possono essere classificati come globali o locali. I metodi locali sono caratterizzati dal fatto che la procedura a due tempi di riconoscimento dei candidati a traccia e di ricostruzione tramite il fit di decisione è spesso ulteriormente suddivisa. Viene selezionato un candidato a traccia alla volta, tipicamente cominciando con solo pochi punti (inizializzazione del candidato a traccia) in accordo al modello di traccia utilizzato, e quindi, basandosi sul modello di traccia, si determinano regioni in cui si dovrebbero trovare ulteriori punti. Se vengono trovati punti addizionali, questi vengono aggiunti al candidato, altrimenti questo viene abbandonato dopo un certo numero di tentativi. Poiché i metodi locali devono eseguire vari tentativi per trovare un candidato a traccia, e possono usare lo stesso punto in varie combinazioni, il tempo di calcolo cresce più che linearmente con il numero di punti.

1.3 Metodi classici di riconoscimento di tracce

10

Un metodo viene, invece, chiamato globale se tutti gli oggetti (nel nostro caso i punti) intervengono nell’algoritmo nello stesso modo e vengono esaminati simultaneamente. L’algoritmo può essere considerato come una trasformazione della totalità delle coordinate dei punti dell’evento. I metodi globali sono indipendenti dall’ordine in cui i punti entrano nell’algoritmo, mentre i metodi locali non lo sono, perché il trattamento di ciascun punto dipende dall’inizializzazione.

1.3.3 Metodi locali Metodo dell’inseguimento di traccia Il metodo dell’inseguimento di traccia (ref. [5], [6]) è applicato generalmente alle tracce di tipo “visibile”, quando cioè la traccia può essere più o meno facilmente riconosciuta da un occhio umano visualizzandone le coordinate. L’algoritmo inizia con la selezione (esaminando tutte le possibili combinazioni) di un segmento di traccia, costituito da pochi punti (da uno fino a tre o quattro). Il segmento viene normalmente scelto il più lontano possibile dalla regione di interazione, per far sì che le tracce siano in media ben separate. Al passo successivo, un punto viene predetto per estrapolazione in direzione del vertice. Questa estrapolazione può essere di ordine zero, se semplicemente si sceglie il punto più vicino, del primo ordine (linea retta), del secondo (parabola), o di ordini più alti sfruttando altre forme come le eliche. Quando le misure fornite dal sistema tracciante sono sufficientemente vicine, ed è presente un campo magnetico statico, l’estrapolazione parabolica è sufficiente nella maggior parte dei casi. Inoltre il metodo è molto veloce, perché una parabola attraverso tre punti può essere espressa come una funzione lineare in tre valori della y:

1.3 Metodi classici di riconoscimento di tracce

11

y  a1  x y1  a2  x y2  a3  x y3

(1.6)

dove



  x  x x  x 



ai  x   x  x j  x  x k 

i

j

i

k

(1.7)

e i  j , k ; j  k ; i, j, k=1, 2, 3. Questa formula è un caso speciale della formula di Lagrange, eq.(1.8), per polinomi di grado qualunque, la cui correttezza segue dal fatto che due polinomi di grado n sono identici se condividono n+1 punti: n

y j 0

 j  x

 

j xj

yj

(1.8)

dove

 j  x    x  x k  n

(1.9)

k 0 k j

Il procedimento di estrapolazione utilizzato nell’inseguimento di traccia non richiede un accurato modello della traiettoria delle particelle ed è sufficiente un buon modello locale della traccia: l’estrapolazione avviene su regioni di spazio molto limitate, cercando di prolungare il candidato a partire dagli ultimi punti aggiunti. D’altra parte, il metodo dell’inseguimento di traccia non è efficiente quando le distanze fra i punti forniti dal rivelatore diventano troppo grandi: il modello approssimato può non essere sufficientemente preciso, e a causa degli errori di misura un riconoscimento corretto basato sugli ultimi punti trovati risulta problematico. L’inseguimento di traccia viene largamente utilizzato anche nel fit delle tracce, e prende il nome di “filtro di Kalman” (ref. [7], [8]).

1.3 Metodi classici di riconoscimento di tracce

12

Metodo della strada di traccia Il metodo della strada di traccia (ref. [2]) non utilizza l’estrapolazione per predire ulteriori punti sulla traccia, ma una molto più precisa procedura di interpolazione. L’inizializzazione del candidato avviene usando un punto ad entrambe le estremità della traccia, e uno nel centro in caso di tracce curve (in presenza di un campo magnetico), punti scelti in maniera combinatoriale. L’algoritmo, quindi, basandosi sul modello di traccia scelto, determina la striscia di spazio in cui si dovrebbero trovare i punti interni della traccia. In linea di principio, migliore è il modello di traccia inserito nell’algoritmo, più stretta può essere la strada costruita, ma la larghezza della strada è limitata anche dalla risoluzione del rivelatore tracciante. Questo metodo è più lento del precedente, ma viene talvolta utilizzato quando la densità di punti forniti dal rivelatore non è sufficiente per l’utilizzo di metodi di estrapolazione. Metodo degli elementi di traccia Questo metodo (ref. [9]) è particolarmente utilizzato quando il rivelatore tracciante presenta delle suddivisioni naturali di difficile raccordo nella fase di riconoscimento: nel ricercare ogni traccia vengono costruiti tanti candidati (elementi di traccia) quanti sono i sottorivelatori del sistema tracciante, utilizzando procedure di estrapolazione o interpolazione. A questo punto gli elementi di traccia vengono condensati in “superpunti” su cui viene eseguita una nuova procedura di riconoscimento basata sui due metodi visti in precedenza. Per “super-punto” si intende, ad esempio, il punto iniziale dell’elemento e la direzione data dall’elemento di traccia nel suo insieme. Il grande vantaggio di questo metodo è la velocità, se confrontato con i metodi che usano direttamente tutti i punti per traccia. Uno degli svantaggi è rappresentato dal numero ridotto di punti e dalla loro ampia “spaziatura” nella seconda fase del

1.3 Metodi classici di riconoscimento di tracce

13

riconoscimento, ma questo è solitamente compensato dalla più alta precisione dei superpunti e dalla conoscenza della direzione della traiettoria in questi punti.

1.3.4 Metodi globali Metodo degli istogrammi In questo metodo (ref. [10]), si definisce un insieme di k differenti funzioni delle coordinate dei punti e si inseriscono i valori di ogni funzione in un istogramma. Quindi (se il metodo funziona correttamente), le tracce formano clusters o “picchi” sull’istogramma; è sufficiente trovarli ed il problema è risolto. Nell’esempio seguente si illustra il metodo per la parte che serve ai nostri scopi.

Fig. 1.2 Evento di esempio

Supponiamo che l’interazione avvenga sempre in uno spazio sufficientemente ristretto (il vertice di interazione) da poter essere considerato puntiforme, e che le tracce formino una stella attorno al punto di interazione. Questo potrebbe essere il caso di un

1.3 Metodi classici di riconoscimento di tracce

14

acceleratore a fasci incrociati, nella proiezione ortogonale alla direzione del fascio (ad esempio la proiezione XY di L3). Se per ogni punto si calcolano i valori:

i 

 yi  xi

yi xi

 i  tan 1 



   x2  y2  i   i

  

 i  sen 1 

yi

(1.10)

dove i=1,…,nH indica i punti misurati e si costruiscono gli istogrammi di i, i,i, i picchi dell’istogramma daranno alcuni parametri (i è ad esempio la pendenza della traccia) più probabili della traccia ed i punti corrispondenti realizzeranno una prima fase della classificazione di § 1.2 (fig. 1.3).

Fig. 1.3 Istogramma di i

Il metodo funziona bene in assenza di campo magnetico o per ricostruire tracce di particelle di alto impulso. Tracce molto curve non possono essere individuate. Nel caso sia presente un campo magnetico o si vogliano ricostruire traiettorie molto curve si utilizza la trasformazione conforme:

ui 

xi x  yi2 2 i

vi  

yi x  yi2 2 i

(1.11)

1.3 Metodi classici di riconoscimento di tracce

15

gli (ui, vi) si distribuiscono su linee rette nel piano uv, con un avvicinamento massimo all’origine d  1  2 R , dove R è il raggio della traccia (fig. 1.4). L’equazione di una circonferenza passante per l’origine è, infatti:

x 2  2 xx0  y 2  2 yy0  0 dove

(1.12)

x0 2  y0 2  r0 2 , con x0,y0 centro della circonferenza e r0 raggio della

circonferenza. Applicando la trasformazione in eq.(1.11) ai punti appartenenti a queste circonferenze, essi soddisferanno l’equazione lineare:

1  2 x 0 u i  2 y 0 vi  0

(1.13)

È importante notare che le tracce che non passano vicino al punto usato come origine della mappatura non danno picchi ben pronunciati nell’istogramma: questa risulta essere una debolezza del metodo, perché le tracce provenienti da un decadimento secondario non vengono riconosciute.

Fig 1.4 L’evento dopo l’applicazione della trasformazione conforme

1.3 Metodi classici di riconoscimento di tracce

16

Quando è necessario considerare molti istogrammi, riconoscere i clusters delle traccia risulta essere più difficile che trovare le tracce direttamente con un modello, quindi l’utilizzo di questo metodo è limitato a una o due proiezioni. Albero dei cammini minimi Per comprendere il metodo dell’albero del cammino minimo (MST, minimum spanning tree; ref. [12], [13]) è necessario richiamare qualche elemento di teoria dei grafi. Un grafo consiste di nodi e fili. Un nodo può rappresentare un qualunque oggetto, ed è spesso rappresentato graficamente da un punto (fig. 1.5). Un filo può essere rappresentato con una linea che connette due nodi, e simboleggia l’esistenza di una qualche ben definita relazione fra i due nodi. Se un peso positivo (derivante da un’opportuna metrica) è assegnato a ciascun filo, il grafo è chiamato a fili pesati. Un punto isolato è un nodo senza fili. Un grafo connesso è un grafo senza punti isolati. In un grafo totalmente connesso o completo, tutti i nodi sono direttamente connessi con tutti gli altri nodi.

Fig. 1.5 Un albero dei cammini: ogni nodo è connesso ad almeno un altro e da ogni nodo c’è un solo possibile cammino per ogni altro nodo.

1.3 Metodi classici di riconoscimento di tracce

17

Un sentiero fra due nodi è una sequenza di fili che li collega. Un anello o circuito è un sentiero chiuso che connette fra loro tutti i nodi che lo compongono. Un albero è un grafo senza anelli. Un albero dei cammini è un grafo connesso senza anelli. Un albero del cammino minimo è un albero dei cammini per il quale la somma dei pesi dei fili ha un minimo per una data configurazione del grafo. Se tutti i pesi sono diversi lo MST è unico. L’algoritmo MST, per il problema del riconoscimento di tracce, funziona schematicamente così: ad ogni segmento, costituito da una coppia di punti del rivelatore, si associa un nodo. I nodi vengono collegati con un filo quando i due segmenti condividono un punto ed hanno una direzione simile. Il valore del peso da assegnare al filo dipende dalla lunghezza dei due segmenti e dall’angolo fra le loro direzione. L’estrazione dell’albero del cammino minimo dal grafo così ottenuto dovrebbe risolvere il problema del riconoscimento, fornendo un sentiero per ogni traccia dell’evento. Per una ricerca veloce delle tracce ad alto impulso, viene usata una versione modificata dello MST, in cui la curvatura del segmento determina il peso del filo.

Capitolo 2 Le reti neurali artificiali ed i problemi di ottimizzazione Le reti neurali artificiali (ANN, Artificial Neural Networks) sono un metodo di calcolo che differisce sostanzialmente da quelli basati sulle architetture standard di Von Neumann. Le ANN, in genere, imparano dall’esperienza (par.), piuttosto che essere esplicitamente programmate secondo delle regole, come avviene nell’intelligenza artificiale (AI). Partendo da alcuni aspetti caratteristici delle reti biologiche, in questo capitolo si caratterizzano le reti neurali artificiali, e si espongono le proprietà di un tipo particolare di rete, le reti ricorsive. Per concludere si discute, con alcuni esempi, la formulazione dei problemi di ottimizzazione in termini di reti ricorsive: metodi di ottimizzazione basati su reti neurali artificiali saranno poi applicati alla ricostruzione di tracce nel sistema TEC-SMD di L3 (vedi Cap. 3,4).

2.1 Le reti neurali biologiche Le ANN sono ispirate alla struttura delle reti neurali biologiche, al loro modo di impostare e di risolvere un problema, e cercano di riprodurne le proprietà operative

2.1 Le reti neurali biologiche

19

principali. Sono qui riportate brevemente i principali aspetti organizzativi e computazionali del sistema nervoso centrale (CNS) dei vertebrati (ref. [14], [15]). 

Parallelismo di massa. Un vasto numero di semplici e lente unità di calcolo (i neuroni) sono organizzate per eseguire compiti in modo collettivo.



Alto grado di complessità delle connessioni. I neuroni hanno un gran numero di connessioni e quindi formano configurazioni di interconnessione complesse; di conseguenza il cervello ha un enorme numero di variabili.



Possibilità di apprendimento. I parametri di interazione fra neuroni (cioè le caratteristiche biologiche delle loro connessioni, §2.1.1) variano continuamente in seguito all’accumularsi delle esperienze sensoriali.



Stati binari e variabili collettive. Il potenziale di azione di un neurone (descritto nella sezione seguente) è un processo “tutto o niente”. Ciascun neurone ha due soli stati: a riposo o depolarizzato. Ci possono essere varie eccezioni (come nei neuroni retinici), ma la maggior parte dei neuroni ha una risposta binaria. D’altra parte le variabili del cervello (potenziali, aree sinaptiche, densità ionica, …) sono continue e variano con continuità nello spazio e nel tempo.



Numerosi tipi di neuroni e segnali. Il cervello usa vari tipi di neuroni con diversi tipi di segnali.



Complessa interazione fra i segnali. L’interazione degli impulsi ricevuti da un neurone è altamente non lineare e dipende da molti fattori (fisiologici, …).



Decomposizione fisica. Il cervello è organizzato come un mosaico di sottoreti, ed ognuna di esse è costituita da molte migliaia di neuroni densamente connessi. Queste sottoreti sono i moduli di base dei processi cerebrali.

2.1 Le reti neurali biologiche 

20

Decomposizione funzionale. Da un punto di vista funzionale il cervello è anche decomposto in varie zone: ciascuna area, o sottorete, è responsabile di una specifica funzione.

2.1.1 Proprietà biologiche dei neuroni Una rappresentazione schematica di un neurone si trova in fig. 2.1. Il soma è il corpo della cellula, da cui partono lunghi filamenti con diramazioni molto complesse, chiamati dendriti, che portano al soma i segnali provenienti dai neuroni connessi. Dal soma parte anche

una

lunga

fibra

chiamata

assone,

che

generalmente

si

suddivide

nell’arborizzazione assonale. Le punte dell’arborizzazione, le terminazioni nervose, si collegano ai dendriti, al soma o all’assone di altri neuroni, con delle connessioni dette sinapsi.

assone sinapsi assone sinapsi

dendrite

soma

assone

sinapsi

assone Fig. 2.1 Neurone biologico

I meccanismi che descrivono il comportamento dei neuroni sono complessi ed ancora poco conosciuti, anche se il singolo neurone non trasmette una grande quantità di informazione. Il comportamento collettivo di gruppi di neuroni che operano in modo largamente parallelo, piuttosto che l’azione dei singoli neuroni, è responsabile per la

2.1 Le reti neurali biologiche

21

trasmissione ed il trattamento dei segnali in una rete neurale. Per semplificare l’analisi di questa attività attraverso la costruzione di modelli è necessario fare varie assunzioni che non sono valide universalmente, anche se ampiamente utilizzate. In genere, si assume che la trasmissione dei segnali elettrici sia unidirezionale (dendriti soma - assone -terminazioni nervose), che l’attività del neurone sia un processo “tutto o niente” (modello di McCullochs e Pitts, ref. [16]), e che tutte le sinapsi siano o eccitatorie o inibitorie.

2.1.2 Il potenziale d’azione e la sua propagazione Il gradiente di concentrazione di cariche elettriche nel corpo cellulare e nel liquido circostante genera un potenziale (ref. [14]) attraverso la membrana del neurone di circa –70 mV (positivo all’esterno, negativo all’interno). Tramite le sinapsi, i dendriti raccolgono i segnali positivi generati dai neuroni collegati attraverso l’emissione di neurotrasmettitori da parte dei neuroni presinaptici. Quando questo movimento di ioni causa un aumento del potenziale di membrana di circa 15 mV (da –70 mV a –55 mV), il neurone “scarica”: gli ioni positivi sono in grado di penetrare dall’esterno la membrana cellulare, e questo causa un salto del potenziale (detto di depolarizzazione) a circa 35 mV. Viene così generato un impulso elettrico (il potenziale d’azione) che si propaga lungo l’assone e, attraverso le sinapsi dell’arborizzazione assonale, ai neuroni seguenti.

2.1.3 L’apprendimento nei sistemi biologici L’apprendimento

nei

sistemi

biologici

dipende

in

maniera

molto

forte

dall’accoppiamento fra le cellule tramite le giunzioni sinaptiche: si è visto che la trasmissione del segnale elettrico avviene attraverso lo scambio di neurotrasmettitori. La quantità fisica che viene modificata nell’apprendimento è proprio la “forza delle

2.1 Le reti neurali biologiche

22

connessioni”, cioè la quantità di neurotrasmettitore che viene rilasciata quando un segnale giunge alle terminazioni sinaptiche. La regola secondo cui questo cambiamento avviene è nota come “Regola di Hebb” (ref. [18]): una sinapsi che ripetutamente causa l’attivazione di un neurone post-sinaptico, o è vicina a farlo, cresce in forza, mentre le altre gradualmente si indeboliscono. Reti neurali biologiche

Computer convenzionali

Processo parallelo distribuito

Macchine di Von Neumann

Apprendimento (per esempi) tramite la Programmate con istruzioni (analisi semodifica delle connessioni allora basata sulla logica) La memoria e i processi sono collegati.

La memoria e i processi sono separati.

Parallele (discrete o continue) e asincrone.

Sono sequenziali sincroni.

o

seriali,

digitali,

Possono essere tolleranti agli errori, per la Non sono tolleranti agli errori. rappresentazione distribuita e la ridondanza di larga scala. Auto-organizzazione apprendimento.

nella

fase

di Dipendono dal software.

Il modo di processare è anarchico.

Il modo di processare è autocratico.

I cicli di tempo che governano la velocità I cicli di tempo hanno una durata di circa dei processi hanno una durata di circa un un ns. ms.

Tab 2.1 Confronto fra una rete neurale ed un computer convenzionale

2.2 Le reti neurali artificiali Il metodo di costruzione delle ANN è quello di astrarre qualche ingrediente chiave dalle reti neurali biologiche e da questi costruire semplici modelli matematici che implementino alcune delle caratteristiche citate in precedenza. Benché i modelli

2.2 Le reti neurali artificiali

23

proposti per il singolo neurone siano in genere piuttosto semplici, il comportamento di sistemi di neuroni è complesso: è, infatti, il comportamento colletivo dei neuroni che genera interessanti ed inaspettati metodi di “calcolo”.

2.2.1 Il neurone artificiale di McCullochs e Pitts Il primo modello di neurone artificiale è quello di McCullochs e Pitts, o Perceptron (ref. [17], fig. 2.2), è un semplice dispositivo a due stati, il cui valore {0,1} dipende unicamente dal valore dei suoi ingressi. x0

w0 w1

x1

w2

Unità

soglia

xn

… wn …

x2

output

a

Fig. 2.2 Neurone artificiale di McCullochs-Pitts

… Per determinare lo stato del neurone al tempo t+to (il tempo è assunto come una … variabile discreta a passi di to), si calcola il “potenziale d’azione” a(t) del neurone xn eseguendo la somma pesata degli ingressi:

a (t )   wi xi (t )

(2.1)

i

dove gli xi rappresentano o lo stato di altri neuroni connessi a questo o valori esterni di ingresso, e i pesi wi possono essere interpretati come la forza delle sinapsi, di vario valore |wi|, eccitatorie (se wi>0) o inibitorie (se wi0 e (xref,yref) all’interno del cerchio 