Tesi Di Laurea - Reti Neurali Neural Networks

Universit degli Studi di Palermo FACOLT DI SCIENZE LAUREA IN FISICA

RETI NEURALI: MODELLI E ASPETTI APPLICATIVI

Ricerca di: RELATORE:

_____________________________________________________________ Anno 2004 - 2005

SOMMARIO

1. - INTRODUZIONE 1.1 - DEFINIZIONE DEL PROBLEMA 1.2 - CONTENUTO DEI CAPITOLI SUCCESSIVI 2. - COMPUTAZIONE CLASSICA E MODELLI CONNESSIONISTICI 2.1- INTRODUZIONE 2.2 - ALGORITMI E MACCHINE DI TURING 2.3 - I NEURONI FORMALI DI MC CULLOCK E PITTS 2.4 - L'ELABORATORE DI VON NEUMANN 2.5 - LIMITI DELL'ARCHITETTURA DI VON NEUMANN 2.6 - CERVELLO E CALCOLATORI 2.7 - SISTEMA NERVOSO, CERVELLO E NEURONI 2.8 - NATURA E COMPUTAZIONE 3. - MODELLI DI RETI NEURALI 3.1 - INTRODUZIONE 3.2 - ORIGINE DELLE RETI NEURALI 3.3 - ARCHITETTURA ASTRATTA DI UNA RETE NEURALE 3.4 - DEFINIZIONE DI RETE NEURALE 3.5 - CLASSIFICAZIONE DELLE RETI NEURALI 4. - RETI DI HOPFIELD E MACCHINA DI BOLTZMANN 4.1- INTRODUZIONE 4.2 - MODELLO DISCRETO DELLA RETE DI HOPFIELD 4.3 - CONSIDERAZIONI ENERGETICHE SULLA RETE DISCRETA DI HOPFIELD 4.4 - REGOLA DI APPRENDIMENTO DI HEBB E APPLICAZIONI C.A.M. DEL MODELLO DISCRETO DI HOPFIELD 4.5 - MODELLO CONTINUO DELLA RETE DI HOPFIELD 4.6 - ANNEALING E ANNEALING SIMULATO 4.7 - MACCHINA DI BOLTZMANN 4.8 - REGOLA DI APPRENDIMENTO PER LA MACCHINA DI BOLTZMANN

Reti Neurali: modelli e aspetti applicativi

3

5. - ALTRI MODELLI: PERCEPTRONI E RETI DI KOHONEN 5.1 - INTRODUZIONE 5.2 - PERCEPTRONE A SINGOLO STRATO 5.3 - LIMITI DEL PERCEPTRONE A SINGOLO STRATO 5.4 - PERCEPTRONI MULTISTRATO 5.5 - REGOLA DI APPRENDIMENTO BACK-PROPAGATION 5.6 - RETI AUTO-ORGANIZZANTI DI KOHONEN 6. - APPLICAZIONI DELLE RETI NEURALI 6.1 - INTRODUZIONE 6.2 - RAPPRESENTAZIONE DEI DATI 6.3 - APPLICAZIONE DEL MODELLO CONTINUO DI HOPFIELD 6.3.1 - CONVERTITORE ANALOGICO/DIGITALE 6.3.2 - SCOMPOSIZIONE DI SEGNALI ANALOGICI 6.3.3 - IL PROBLEMA DEL COMMESSO VIAGGIATORE (TSP) 6.3.4 - PROGRAMMAZIONE LINEARE 6.3.5 - IL PROBLEMA DI HITCHCOCK 6.3.6 - SISTEMA DI EQUAZIONI LINEARI 6.4 - COMPLESSIT COMPUTAZIONALE DI UNA RETE NEURALE 6.5 - APPLICAZIONE DI PERCEPTRONI MULTISTRATO CON REGOLA BACKPROPAGATION: RETE NETTALK 7. - MEMORIE ASSOCIATIVE BASATE SUL MODELLO DISCRETO DI HOPFIELD E NUOVI ALGORITMI DI MEMORIZZAZIONE 7.1 - INTRODUZIONE 7.2 - PROBLEMI ALEATORI E MEMORIE ASSOCIATIVE 7.3 - CONSIDERAZIONI SUL MODELLO DISCRETO DI HOPFIELD 7.4 - NUOVI ALGORITMI DI MEMORIZZAZIONE 7.5 - ALGORITMO DI MEMORIZZAZIONE DI S.H. OH 7.6 - SIMULAZIONI AL CALCOLATORE DI MEMORIE ASSOCIATIVE 7.6.1 - SIMULAZIONE 1 7.6.2 - SIMULAZIONE 2 7.6.3 - SIMULAZIONE 3 7.6.4 - SIMULAZIONE 4 7.6.5 - SIMULAZIONE 5

7.7 - MEMORIE OTTICHE ASSOCIATIVE 7.8 - CONCLUSIONI 8. - BIBLIOGRAFIA

9. - INDICE DELLE FIGURE


5

1. - INTRODUZIONE1.1 - DEFINIZIONE DEL PROBLEMA

Esiste una vasta gamma di problematiche nelle quali i convenzionali computer digitali ad architettura Von Neumann rivelano i loro limiti. Si tratta di problemi come il riconoscimento di forme, la comprensione del linguaggio naturale e la rappresentazione della conoscenza, che sono qualitativamente diversi da quelli classicamente implementabili nei computer. Ad esempio i problemi posti dal riconoscimento delle forme costituiscono un sottoinsieme dei problemi detti aleatori. Anche la classe dei cosiddetti problemi di ottimizzazione combinatoria non si presta ottimizzazione combinatoria il solo modo sono caratterizzati ad una soddisfacente soluzione algoritmica se implementata nei computer tradizionali. Sia i problemi aleatori, sia quelli di da un altissimo numero di soluzioni, e per risolverli di ridurre drasticamente tale numero. I metodi di riduzione

utilizzati sono noti come metodi euristici, e non sono applicabili in generale a tutti i problemi. I metodi euristici richiedono quasi sempre un grandissimo sforzo computazionale da parte dei calcolatori e spesso i tempi di risoluzione di un problema sono completamente inaccettabili. ci si Da un po di tempo per la soluzione dei problemi ad alto numero di soluzioni

rivolti ad algoritmi ed architetture completamente differenti. Molti ricercatori, provenienti da diversi settori, hanno studiato e progettato innovative macchine ad architettura parallela, emulanti l'organizzazione e le funzioni del cervello, che si sono dimostrate in grado di risolvere sia i problemi aleatori sia quelli di ottimizzazione combinatoria non alla portata dei computer attuali. Tali macchine sono comunemente chiamate reti o sistemi neurali. La loro architettura definisce i cosiddetti modelli connessionistici o modelli di elaborazione parallela distribuita (Parallel Distributed Processing - P.D.P.). Le reti neurali si basano sull'idea di realizzare un processo di computazione attraverso l'interazione di un grande numero di semplici elementi chiamati neuroni. La novit principale di tali modelli rispetto i computer tradizionali la non necessita di programmazione. Quest'ultima viene sostituita dalla possibilit di impostare sulla rete neurale una sorta di apprendimento che pu essere spontaneo o guidato attraverso esempi. L'approccio mediante reti neurali consente sia di realizzare sistemi computazionali che posseggono caratteristiche simili a quelle dei fondamentali dell'intelligenza del sistemi biologici, sia di impostare in modo nuovo i problemi

artificiale. La teoria delle reti neurali si propone anche di riorganizzare i rapporti tra lo studio astratto e formale delle funzioni mentali (scienza cognitiva), e quello concreto

cervello dagli

visto sviluppi

come

una

macchina

fisica

(neuroscienze).

I segni di un ravvicinamento tra scienza cognitiva e neuroscienze sono giustificati sia tecnologici, che consentono la costruzione dei sistemi neurali, sia dai progressi delle ricerche, condotte da fisici, psicologi e neurofisiologi, sullo studio fisico del cervello . La tesi si propone di fornire un quadro generale degli studi attuali sulle reti neurali, con particolare riguardo alle applicazioni computazionali e alla costruzione di memorie associative. Le memorie associative sono dei dispositivi in grado di recuperare i dati memorizzati mediante la presentazione di copie incomplete o distorte di questi ultimi. E' facile comprendere che l'argomento delle reti neurali, interessando svariati campi della ricerca, assume vastissime proporzioni, pertanto la tesi ha focalizzato i principali modelli di una teoria ancora giovane cercando di evidenziare le applicazioni a problemi reali.

1.2 - CONTENUTO DEI CAPITOLI SUCCESSIVI

Il lavoro inizia evidenziando l'origine comune tra i primi modelli neurali, la macchina algoritmica di Turing e l'elaboratore di Von Neumann. Un breve accenno alla struttura e al funzionamento del cervello, necessario per capire il calcolo vi si ispirano, conclude il secondo senso con cui le nuove macchine di descrizione dell'architettura capitolo. La

generale e delle propriet dei sistemi neurali, insieme a una sommaria classificazione, costituisce l'argomento del terzo capitolo. Il quarto e il quinto capitolo si soffermano sulla teoria delle reti di Hopfield, dei perceptroni e delle reti di Kohonen. Una collezione di applicazioni computazionali delle reti di Hopfield e dei perceptroni presentata nel quinto capitolo. Tale capitolo lascia intravedere la vastit dei possibili orizzonti applicativi. Nel sesto e ultimo capitolo sono raccolte una serie di simulazioni al calcolatore fatte dall'autore. Le simulazioni riguardano memorie associative basate sulle reti di Hopfield e su diverse regole di funzionamento.

2. - COMPUTAZIONE CLASSICA E MODELLI CONNESSIONISTICI2.1- INTRODUZIONE

L'originale modello di rete di neuroni elaborato dai matematici Mc Cullock e Pitts negli anni di sviluppo della prima cibernetica, parallelamente allo studio da parte di Von Neumann


7 elaboratore. In questo secondo capitolo si evidenziano le si analizza l'architettura

della

sua

architettura

di

analogie tra la macchina di Turing, prototipo di macchina ideale e universale di calcolo, e le reti di neuroni formali di Mc Cullock e Pitts. Successivamente dell'elaboratore di Von Neumann, che deriva direttamente da quella della macchina di Turing. In conclusione i limiti dell'elaboratore di Von Neumann sono confrontati con le peculiarit del cervello. Il capitolo, partendo dai fondamenti della teoria matematica della computazione, arriva a generalizzare un processo di calcolo allevoluzione dinamica di sistemi fisici diversi dai calcolatori architetture. e intrinsecamente non programmabili, lasciando intuire la possibilit di nuove

2.2 - ALGORITMI E MACCHINE DI TURING

La

teoria

della

computabilit

studia

la

risolvibilit algoritmica di un problema.

Un algoritmo una procedura completamente definita, articolata in un numero finito di passi, eseguibili meccanicamente in un tempo finito, e corrispondente a un'espressione scritta in un determinato linguaggio. I problemi per la cui soluzione esiste un algoritmo definiscono la classe delle funzioni computabili. Le funzioni computabili possono essere espresse per mezzo di un tipo di definizione molto generale detta ricorsiva che sar definita pi avanti. Il problema di definire in maniera rigorosa la classe delle funzioni computabili porto nel 1930 il matematico Turing1 al progetto di una macchina di calcolo ideale descritta in figura 2.1. Gli elementi costituenti la macchina di Turing sono: 1. un unit esterna di memoria o nastro 2. una testina di lettura e scrittura 3. una unit di controllo A a stati finiti. Per la macchina di Turing definito un alfabeto esterno di simboli Xi, e un alfabeto interno di simbolo Qi . Gli ingressi della macchina sono i simboli dell'alfabeto esterno X, mentre l'uscita della macchina corrisponde ad un'operazione di scrittura di un simbolo sull'unit esterna di memoria oppure ad un movimento della testina sul nastro. Lo stato interno della macchina espresso mediante i simboli Qi dell'alfabeto interno della macchina. Il

funzionamento della macchina consiste nell'esecuzione di una serie di passi elementari, in ciascuno dei quali la macchina assume una configurazione totale determinata dallo stato in cui si trova la macchina, dalla cella in esame dall'unit di controllo e dal contenuto di ogni cella della memoria esterna. Si definisce computazione o calcolo di una macchina di Turing una sequenza di configurazioni totali che terminano in uno stato di halt Q0. Lo stato di halt non ammette una configurazione successiva. Il tipo d'algoritmo implementato da una che particolare macchina di Turing definito dalla tavola funzionale della macchina,

corrisponde al programma dell'unit logica. Il concetto di macchina di Turing pu essere esteso definendo una macchina di Turing universale in grado di eseguire gli algoritmi di1 A. Turing, On computable numbers, with an application to the entscheidungsproblem, Proceedings of the London Mathematical Society, Num. 2 Vol XLII, 1936.


9

una qualsiasi macchina di Turing dotata di una qualunque tavola funzionale. La macchina universale operer a partire da una configurazione iniziale che prevede la registrazione su nastro sia della matrice funzionale della macchina da imitare che della configurazione iniziale di questa. La macchina di Turing universale equivale concettualmente ad un computer Von Neumann general purpose. La caratteristica della ai macchina universale di avere tavole programmi e ai dati contenuti funzionali e simboli dell'alfabeto esterno memorizzati insieme nella memoria esterna equivale, nel caso di un elaboratore Von Neumann, contemporaneamente in memoria. Luniversalit della macchina di Turing viene evidenziata dalla tesi di Church, la quale restringe il concetto di computabilit a una classe precisa ma molto generale di funzioni, le funzioni parziali ricorsive. Una funzione di n-argomenti f(x1 ,x2 ,...,xn ) detta ricorsiva se definibile mediante le equazioni2 :

2.1 Nella 2.1 g e h sono funzioni note, S(x) la funzione successore definita come: S(x) = x + 1. La funzione ricorsiva f detta parziale quando essa non ha un valore definito per ogni n-upla di argomenti (x1 ,x2 ,...,xn ) ed quindi definita per un set limitato di argomenti. Un esempio di definizione ricorsiva di funzione riguarda l'operazione di addizione, indicando f col simbolo + si ha:

2.2 Nella 2.2 * si ha: +(x,S(y)) definito in termini di +(x,y) e della funzione nota successore (h = S). Anche l'operazione di moltiplicazione pu essere definita in tal modo, indicando f col simbolo

2.3 Nella 2.3 *(x,S(y)) definito in termini di *(x,y) e della funzione nota addizione (h = +). La tesi di Church afferma che qualunque algoritmo scritto con qualsiasi formalismo pu essere calcolato da una macchina di Turing. La formulazione forte di questa tesi dice che qualsiasi sistema fisico reale pu essere simulato da una macchina di Turing, con un grado di2 Robert McNaugthon, Elementary Computability, Formal Languages and Automata, Prentice Hall International 1982.

approssimazione arbitrariamente elevato, con l'ipotesi di poter ignorare i limiti di lunghezza del nastro della macchina e il tempo disponibile per la computazione. Questa tesi evidentemente non pu essere dimostrata, esistono per significativi argomenti a suo sostegno. Innanzitutto metodi alternativi elaborati per definire la computabilit hanno sempre portato a classi di funzioni computabili coincidenti con le funzioni parziali ricorsive. Per completare il discorso non si pu trascurare l'esistenza di funzioni che non sono parziali ricorsive, per la tesi di Church queste funzioni non sono Turing-calcolabili, e quindi sono ignorate dalla macchina di Turing. Un altro problema non risolvibile quello noto come problema dell'arresto di una macchina di Turing. Si consideri una macchina di Turing A con configurazione totale iniziale data da una tavola funzionale T e da una parola W contenuta nella memoria esterna, non esiste un'altra macchina di Turing B che con l'input di T e W possa calcolare se la computazione di T si ferma o cicla.

FIGURA 2.1 - Rappresentazione della Macchina di Turing, in alto il dispositivo A e l'unit di controllo, in basso si ha il nastro coi simboli dell'alfabeto esterno in ingresso, sopra il nastro in grigio e posizionata la testina di lettura. (FONTE COMMUNICATIONS OF ACM 5/85/M.CONRAD)


11

2.3 - I NEURONI FORMALI DI MC CULLOCK E PITTS

Il neurofisiologo Mc Cullock e il matematico Pitts nel 1943 introdussero il concetto di neurone formale3 che alla base del loro progetto di rete neuronica. Nel loro modello il neurone formale assume due possibili stati, uno attivo l'altro inattivo e definisce una classe di oggetti caratterizzati come segue: un numero r finito di ingressi ciascuno suscettibile di assumere i valori 0 o 1; un'unica uscita i cui valori possibili sono 0 o 1; un valore di soglia s intero positivo; una regola di funzionamento espressa da:

2.4 Mediante i neuroni formali si pu costruire una macchina detta semiautoma con un numero finito r di input x agli input e un numero finito s di stati q della macchina. Successivamente si e agli stati (vedi figura 2.2a). costruisce una matrice di neuroni formata da r righe e s colonne corrispondenti rispettivamente La programmazione di questa macchina consiste in un tipo di istruzione molto semplice, espressa nella forma generale q x q , la cui esecuzione consiste nel connettere tutti i neuroni della i-esima colonna col j-esimo neurone della k-esima colonna. Da notare che la rete di neuroni formali definita e caratterizzata da connessioni precostituite, senza alcuna possibilit di modifica successiva. Mc Cullock e Pitts dimostrarono che, per ogni funzione computabile da una macchina di Turing, esiste un semiautoma di neuroni formali in grado di calcolare la stessa funzione. Da quanto detto segue che il modello di Turing e il semiautoma composto da neuroni formali sono dal punto di vista computazionale equivalenti. Le capacit di calcolo del modello dipendono non tanto dalle caratteristiche dei singoli neuroni quanto dal modo in cui sono connessi.

3 W.S. McCullock e W. Pitts, A logical Calculus of the Ideas Immanent in Nervous Activity, Bullettin of Mathematical Biophysics, Num. 5 1943, pag. 115-133.

FIGURA 2.2a - (a) Neurone formale di Mc Cullock e Pitts (b) Rete di neuroni formali costituente un semiautoma strutturalmente programmabile. (FONTE COMMUNICATIONS OF ACM 5/85/M.CONRAD)

FIGURA 2.2b - Una rappresentazione pi generale della regola di funzionamento del neurone artificiale di McCullock e Pitts detto anche TLU (Threshold Logic Unit), x(i) sono gli ingressi, w(i) sono i pesi, il valore della soglia per la funzione di attivazione. Si noti che nella formula semplificata 2.4 i pesi w(i) sono tutti uguali a 1.


13

2.4 - L'ELABORATORE DI VON NEUMANN

I moderni computer digitali sono quasi tutti basati su un'architettura definita nel 1945 dal matematico John Von Neumann nel progetto dell'elaboratore EDVAC4 L'elaboratore di Von Neumann costituito da due organi di base, il processore e la memoria centrale (vedi figura 2.2c). Le operazioni di tutti i computer convenzionali possono essere modellate nellesecuzione del ciclo seguente: 1. preleva un istruzione dalla memoria 2. preleva i dati richiesti da tale istruzione dalla memoria 3. esegui listruzione 4. memorizza i risultati in memoria 5. vai al punto 1

FIGURA 2.2c - Semplice rappresentazione dellarchitettura di Elaboratore Von Neumann

4 John Von Neumann, Primo abbozzo di relazione sull'EDVAC (Electronic Discrete Variable Computer), Princeton University 1945.

Lelaboratore di Von Neumann una macchina di calcolo equivalente a quella di Turing, ed caratterizzata come segue5 : Linguaggi di programmazione. Tali linguaggi sono utilizzati per esprimere gli algoritmi e sono costituiti da statement che si ottengono applicando un insieme finito di regole di composizione a un numero finito di simboli base. Programmabilit. Si intende in tal modo la possibilit concreta di comunicare all'elaboratore il programma scritto alla macchina. Dal punto di vista dell'utente tale processo di comunicazione pu essere mediato da un compilatore. Universalit. Essendo equivalente a una macchina di Turing, un calcolatore Von Neumann pu calcolare qualsiasi funzione computabile e quindi, per la tesi di Church, simulare qualsiasi sistema fisico. Sequenzialit. Un computer di Von Neumann ha un architettura sequenziale, infatti una singola operazione elementare alla volta. Inefficienza. I computer di Von Neumann utilizzano in modo non ottimizzato le risorse di spazio, tempo ed energia. Il processore, a causa della sequenzialit con cui esegue le istruzioni, inattivo per la maggior parte del tempo. Programmabilit strutturale. Per spiegare questa caratteristica ci si deve riferire alla definizione di semiautoma vista in precedenza. Un calcolatore di Von Neumann si dice strutturalmente programmabile perch si pu dimostrare che sostanzialmente un semiautoma, cio il calcolatore pu essere rappresentato come un insieme elementi capaci di eseguire una operazione logica di switch o di semplice. La definizione esegue

programmabilit strutturale legata alla tesi forte di Church, e stabilisce che una macchina strutturalmente programmabile capace di simulare qualsiasi sistema fisico a condizione che le risorse di tempo e di spazio riservate alla computazione siano illimitate. Inoltre gli algoritmi, espressi in un calcolatore digitale in simboli primitivi di un linguaggio di alto livello, possono essere espressi direttamente in neuroni termini di primitive computazionali di switching, che corrispondono alla programmazione di una rete di formali. La programmabilit strutturale sar utile per analizzare i limiti generali dell'architettura di Von Neumann. La formulazione forte della tesi di Church, valida anche per gli elaboratori di Von Neumann, suggerisce un legame tra i modelli formali di computazione e i processi dinamici5 Michael Conrad, "On Design Principles for a Molecular Computer", Communications of the ACM 1, Vol. 28, Num. 5, Maggio 1985.


15 un sistema fisico come realizzazione di una

simulabili su un calcolatore. Pensare a computazione significa : 1. identificare gli argomenti o input

della

funzione computabile considerata con i

parametri di descrizione di un certo stato del sistema. 2. considerare i parametri di descrizione di un successivo stato del sistema il risultato della computazione cio l'output. L'elaboratore di Von Neumann una realizzazione fisica di un sistema formale che esegue semplici operazioni su stringhe di simboli. Si dice che un computer simula un sistema fisico, mediante le primitive computazionali sopra definite, se gli stati del computer possono essere associati agli stati del sistema con un alto grado di approssimazione, non necessario comunque che ogni stato della macchina corrisponda a uno stato del sistema. Si visto che un sistema fisico simulabile con l'elaboratore Von Neumann, tuttavia molti fenomeni computazionali osservati in natura fanno ritenere che possibile definire delle macchine di calcolo che incorporano il processo fisico stesso come primitiva computazionale. In tal caso si perde sia il carattere discreto delle primitive computazionali, sia la possibilit di comunicare queste ultime sotto forma di algoritmo alla macchina.

2.5 - LIMITI DELL'ARCHITETTURA DI VON NEUMANN

L'architettura dell'elaboratore di Von Neumann presenta dei limiti di applicabilit e di capacit di calcolo che non potranno essere superati dal solo progresso tecnologico, ossia dal miglioramento delle prestazioni dei processori e delle memorie. Tali limiti sono intrinseci al disegno stesso dell'elaboratore di Von Neumann, e sono di seguito esaminati: Irreversibilit operativa. La modalit in cui l'informazione perdita un computer tradizionale elabora

un processo irreversibile. La funzione logica AND un esempio di

di informazione in un computer. La tabella 2.5 mostra che non possibile,

esaminando le uscite della tabella, risalire agli ingressi che le hanno prodotte. Tabella della verit della Funzione Logica AND.INPUT 0 0 0 1 0 OUTPUT 0

1 1

0 1

0 1

Alta dissipazione termica. In un computer digitale i

segnali elettrici originano dei kT/q Volt dove k la

cambiamenti di potenziale in diverse regioni spaziali del sistema. Gli elettroni operano con un disturbo termico che in termini di potenziale circa costante di Boltzmann, T la temperatura Kelvin assoluta e q la carica dell'elettrone, a temperatura ambiente (290 K) kT/q = 0.025 Volt. Le operazioni logiche in un computer digitale devono avvenire con potenziali maggiori di 0.025 Volt. In definitiva si osserva che il valore alto di kT/q richiede un'alta dissipazione di potenza che caratterizza come processi irreversibili le operazioni logiche fondamentali di un computer digitale di Von Neumann. Lentezza operativa. Un risultato del modo di operare seriale dell'architettura di Von Neumann il cosiddetto "collo di bottiglia di Von Neumann". Esso originato dalla lentezza con cui il processore accede alla memoria. Il trasferimento di dati e istruzioni dalla memoria al processore, prima che quest'ultimo cominci il suo lavoro computazionale, comporta un intervallo di tempo in cui il processore inattivo. Alla fine della computazione il trasferimento dei risultati alla memoria origina un altro periodo di inattivit del processore. Alle inefficienze elencate si aggiunge un generale limite connesso alla programmazione strutturale, infatti una macchina di calcolo reale non dispone di risorse di tempo e di spazio illimitate come richiesto Costruire dalla una tesi forte di Church per macchine strutturalmente programmabile significa programmabili. macchina strutturalmente

essenzialmente convogliare lungo canali precisi il fenomeno utilizzato per ottenere la realizzazione fisica della computazione. Controllare un fenomeno fisico significa ridurre il numero di gradi di libert, e quindi di interazioni, del fenomeno stesso, riducendo in tal modo anche le risorse della computazione.


17

2.6 - CERVELLO E CALCOLATORI

Si esamineranno brevemente alcune differenze fondamentali tra il cervello e le architetture delle macchine di calcolo viste prima. Il cervello umano costituito da una rete di moltissimi neuroni (1011 1012 ) collegati tra loro da un numero elevato di connessioni dette sinapsi (103 104 sinapsi per ogni neurone). In totale il numero di sinapsi del cervello varia da circa 1014 a 1016 . Ogni sinapsi pu essere inibitoria o eccitatoria per cui il numero delle configurazioni possibili uguale a 2 elevato al numero totale di neuroni nel cervello :

Si pensa che questo altissimo numero di configurazioni sia responsabile delle eccezionali prestazioni del cervello. Bench moltissimi processi cerebrali non siano ancora noti o perfettamente compresi noto che l'apprendimento e la memoria a lungo termine si attuano con la formazione di nuove sinapsi. Sono elencate di seguito alcune peculiarit del cervello: Parallelismo e lentezza dei neuroni. Studi non tanto recenti hanno mostrato che il cervello elabora le informazioni in modalit parallela, questa affermazione nasce da semplici considerazioni. Un'operazione base viene effettuata da un neurone in tempi dell' ordine di decine di millisecondi, mentre il cervello in grado di risolvere complicatissimi problemi di visione e linguaggio in circa 500 ms. Tenendo conto dei tempi di ritardo di propagazione del segnale tra neuroni, si pu dire che il lavoro computazionale del cervello fatto in meno di 100 passi, e consiste nell'esecuzione in parallelo da parte di neuroni di operazioni base molto semplici. Bassa dissipazione termica. L'energia termica dissipata da un neurone in una elementare operazione di calcolo circa 3 x 10-3 erg che in confronto ai 3 x 10-14 erg dissipati in una porta logica di un computer convenzionale 11 ordini di grandezza superiore. L'intero cervello dissipa meno di 100 Watt. Elementi base di natura analogica. I neuroni sono degli elementi che operano in maniera analogica. Essi operano su un ingresso sinaptico e generano un uscita a valori continui. Alta ridondanza. Tale propriet permette al cervello di essere un sistema estremamente flessibile a superare disastri locali nella sua struttura senza perdita significativa di prestazioni. Molti neuroni muoiono ogni giorno e il cervello continua ad operare.

E' interessante paragonare il modello di cervello visto con le specifiche di un calcolatore elettronico: un supercomputer moderno dotato di almeno 1000 megabyte di memoria centrale, che corrispondono al massimo a 1010 transistor, e usa meno di 108 transistor in funzioni logiche. Un processore compie un operazione logica base in un ciclo di circa 10 -9 secondi. La potenza dissipata dal computer dell'ordine di 105 Watt. In un computer la tolleranza ai malfunzionamenti locali un fattore estremamente critico, vengono tollerati disastri solo in parti della memoria e mai nel processore. interconnessioni se recentemente Un'altra caratteristica del cervello umano che le tridimensionale con schema mentre di nella tra i neuroni interessano uno spazio sono stati costruiti chip di silicio

maggioranza dei computer le piastrine di silicio hanno uno schema di connessioni piano, anche connessioni tridimensionale. Si pu concludere osservando che i componenti base del cervello sono molto pi numerosi, pi connessi e pi lenti dei componenti di un computer.

2.7 - SISTEMA NERVOSO, CERVELLO E NEURONI

Sono qui sintetizzati alcuni concetti fondamentali sul sistema nervoso e sulla struttura del cervello. Il sistema nervoso si divide in due parti principali: periferico e centrale. Il primo svolge funzioni di interfaccia tra il sistema nervoso centrale e l'ambiente esterno. I segnali trattati comprendono gli ingressi sensoriali, le uscite si manifestano con stimoli motori, dolori, da talamo, immagini ipotalamo, gangli basali, visive, sistema percezioni limbico e varie. Il sistema nervoso centrale costituito dalla spina dorsale e dal cervello, formato a sua volta neocorteccia. L'unit costitutiva di tutto il sistema nervoso il neurone, la cui anatomia e mostrata in figura 2.3. Un neurone una cellula dotata di corpo cellulare dal quale si dipartono molte brevi ramificazioni di ingresso (dendriti) e una sola lunga ramificazione di uscita (assone). I neuroni comunicano tra loro mediante impulsi particolari detti spike, generati da processi elettrochimici. In condizione di riposo esiste una differenza di potenziale di circa -70 -90 milliVolt tra l'interno e l'esterno della membrana cellulare del neurone, ed dovuta alle diverse concentrazioni di ioni sodio e potassio tra le due pareti della membrana. Queste differenze sono causate da un apposito enzima-pompa capace di muovere gli ioni. Quando un evento esterno come la scarica di altri neuroni provoca una variazione del potenziale della membrana, viene aumentata la permeabilit della membrana stessa agli ioni di sodio. Questi ioni si riversano all'interno della cellula dove la loro concentrazione minore, causando una corrente elettrica. Contemporaneamente la differenza di potenziale tra l'interno e l'esterno


19

della membrana cambia di segno e diventa circa +40 +50 mV. Dopo il passaggio degli ioni sodio si apre in canale analogo anche per gli ioni potassio che ristabilisce la situazione di concentrazioni e potenziali precedente. La rapidissima inversione del potenziale di membrana origina lo spike o potenziale d'azione e costituisce il messaggio trasportato lungo l'assone. Il livello di tensione a cui la membrana da origine allo spike detto soglia di eccitazione. Lo spike si propaga, quasi senza attenuazione, lungo l'assone liberando energie locali. Sulla sinapsi lo spike provoca l'emissione di particolari sostanze dette neurotrasmettitori, i quali raggiungono i dendriti del neurone successivo e provocano una variazione della permeabilit della membrana, consentendo la trasmissione del segnale tra i neuroni connessi. In generale un singolo potenziale d'azione che raggiunge una sinapsi non sufficiente a generare la produzione di altri potenziali d'azione nel prossimo neurone. L'effetto additivo di pi potenziali d'azione sui dendriti del neurone postsinaptico e capace di superare la soglia di eccitazione del neurone, generando un potenziale d'azione. Il numero medio di potenziali d'azione nell'unit di tempo in funzione della corrente positiva in ingresso a un neurone rappresentato in figura 2.4. Questa funzione ha la forma di una sigmoide che va da 0 per correnti negative fino a un livello massimo di saturazione di 100 1000 spike per secondo per correnti positive molto alte.

FIGURA 2.3. - Anatomia di un sistema di tre NEUROPHYSIOLOGY:A PRIMER WILEY/1966/C.F. STEVENS)

neuroni

interagenti. (FONTE

FIGURA 2.4 - Grafico rappresentante il numero medio di potenziali d'azione nell'unit di tempo in funzione della corrente positiva in ingresso a un neurone. (FONTE PROCEDINGS OF THE NIELS BOHR CENTENARY SYMPOSIUM 10/85/J.J. HOPFIELD)


21

2.8 - NATURA E COMPUTAZIONE

In natura esistono fenomeni di trattamento delle informazioni diversi da quelli utilizzati

nella

costruzione dei calcolatori digitali a tecnologia elettronica. 6 Nella genetica molecolare si realizzano veri meccanismi di computazione, nei quali la computazione definita da tre elementi concettuali: un ingresso, un'uscita e una unit di calcolo. La traduzione del DNA nella struttura di una proteina, la costruzione di un complesso organismo dalle istruzioni del DNA sono esempi di computazione biologica. Il processo di creazione di pi proteine da parte di una cellula in crescita analogo alla computazione di una macchina di Turing (vedi figura 2.5). In questo processo l'informazione memorizzata nell'RNA messaggero (mRNA) utilizzata come istruzione per costruire la proteina. Il nastro con l'alfabeto esterno in ingresso costituito dall'mRNA, l'uscita finale la proteina che consiste in un polimero di amino-acidi con struttura tridimensionale. L'mRNA un polimero costituito da quattro tipi di unit A, U, G e C. La proteina un polimero fatto da venti tipi diversi di aminoacidi, glicina, alanina, tirosina,...etc. La sintesi della proteina fatta da un composto polimolecolare, formato da proteine e RNA detto ribosoma, che pu essere visto come l'unit di controllo della macchina di Turing del processo. Il ribosoma legge l'input dell'mRNA (nastro di ingresso) e inserisce sequenzialmente il corrispondente amminoacido nella proteina. Le operazioni logiche descritte sono fatte da particolari reazioni chimiche della cui logica non noto quasi nulla. Le operazioni logiche fatte sono descritte dalla sequenza: 1. Leggi le prossime tre celle dall'nRNA tape 2. Cerca l'aminoacido corrispondente nel dizionario genetico 3. Aggiungi l'aminoacido alla proteina 4. Muovi l'input tape di tre celle Il programma contiene anche una possibile istruzione di dal processo esaminato risulta esatta in quasi tutti i casi computazioni digitali, mentre accettabile per stop nel dizionario genetico.

La computazione biologica molto poco accurata rispetto quella digitale. La proteina formata con un livello di errore di circa computazioni biologiche. 1/3000. Questo livello di errori nel produrre l'output certamente molto alto nel caso di

6 J.J. Hopfield, "Physics, biological computation, and complementarity", Proceedings of Niels Bohr Centenary Symposium, Copenhagen 4 Ottobre 1985.

Le osservazioni fatte in relazione alla computazione biologica permettono di affermare che possibile definire i principi costruttivi di nuove macchine di calcolo capaci di superare i limiti degli elaboratori di Von Neumann, basate su fenomeni fisici diversi da quelli attualmente utilizzati, con particolare riguardo alla imitazione di strutture biologiche o fenomeni microbiologici. Pi avanti si approfondir lo studio di macchine di calcolo basate sulla imitazione strutturale di entit biologiche come il cervello umano. Queste macchine sono chiamate reti o sistemi neurali, mentre la loro architettura definisce i cosiddetti modelli connessionistici. Gli algoritmi su cui si basa l'intelligenza animale sono implementati nel cervello. Utilizzando questo particolare hardware il cervello raggiunge le altissime prestazioni che si conoscono. L'idea base dei sostenitori dei sistemi neurali che la specializzazione della nostra intelligenza sia una peculiarit dei sistemi biologici ad altissimo grado di connessione. La semplicit dei neuroni e delle sinapsi e la loro universalit biologica fa supporre che imitando tali componenti sia possibile costruire sistemi artificiali di analoghe prestazioni.

FIGURA 2.5 - Processo di creazione di pi proteine da parte di una cellula in crescita, analogo alla computazione di una macchina di Turing .Il nastro in uscita contiene gli amminoacidi costituenti la proteina.

3. - MODELLI DI RETI NEURALI3.1 - INTRODUZIONE

In questo capitolo, dopo una breve esposizione delle origini storiche delle reti neurali, vengono


23 che caratterizzano un sistema neurale, distinguendoli computer digitale ad architettura Von Neumann. che verranno utilizzati nelle

definiti

i

principi e gli

elementi

nettamente da quelli alla base di un Nell'ultimo applicazioni dei capitoli successivi.

paragrafo sono elencati i principali modelli

3.2 - ORIGINE DELLE RETI NEURALI

Lo studio delle reti neurali risale ai primi tentativi di tradurre in modelli matematici i principi dell'elaborazione biologica. Le pi antiche teorie del cervello e dei processi mentali sono state concepite dai filosofi Greci Platone (427-347 A.C) e Aristotele (384-322 A.C). Queste teorie furono riprese molto pi tardi da Cartesio (1586-1650) e nel XVIII secolo dai filosofi empiristi. Le prime realizzazioni di macchine cibernetiche, categoria alla quale appartengono i sistemi neurali, appaiono negli anni quaranta col nascere di una scienza nuova, la cibernetica. La cibernetica definita come scienza che studia i processi intelligenti e fu fondata da Norbert Wiener nel 1947. Ross Ashby, un altro padre della cibernetica, costruisce nel 1948 l'omeostato uno dei primi sistemi con connessioni interne regolabili, capace quindi di variare la sua configurazione interna adattandola a stimoli esterni. Il neurofisiologo W.S. MC Cullock e il matematico W.A. Pitts (1943) di Chicago sono stati i primi a formulare l'approccio cibernetico fondamentale alla struttura neurale. John Von Neumann, dopo del cervello elaborando il primo modello di rete formulato l'architettura base dei moderni aver

calcolatori, comincia nel 1948 lo studio delle reti di automi cellulari precursori di nuovi modelli computazionali. Nel 1949 il neurofisiologo Donald Hebb, dagli studi sul processo di apprendimento dei neuroni, dedusse la prima regola di apprendimento applicata nelle reti neurali. Contemporaneamente gli studi di Lashley sulla mente umana indicavano che l'organizzazione della conoscenza e la memoria si basava su rappresentazioni distribuite. Nei primi anni sessanta si costruiscono le prime macchine in grado di presentare primitive forme di apprendimento spontaneo e guidato, sono il Perceptron di Frank Rosemblatt della Cornell University e l'Adaline (Adaptive linear element) di Bernard Windrow di Stanford. Il Perceptron una rete neurale costituita da dispositivi logici in grado di risolvere semplici problemi strutture che di riconoscimento di forme. Esso rappresento un prototipo delle Italia si sviluppano iniziative vennero elaborate pi avanti. Anche in

particolarmente importanti. Eduardo Caianello, dellUniversit di Napoli, sviluppa la sua teoria sui processi e le macchine pensanti sulla base delle idee di Mc Cullock, Pitts e Hebb. A Genova viene realizzata da Augusto Gamba una macchina derivata dal Perceptron. Nel 1969

Marvin Minsky e Seymour Papert, del Massachusetts Institute of Technology, pubblicano un'analisi molto critica delle macchine tipo il Perceptron . Essi dimostrarono matematicamente le limitazioni delle reti neurali nel risolvere problemi quali la determinazione della parit di un numero binario, il calcolo di una funzione XOR di 2 bit o la classificazione delle immagini in base alla loro connettivit. Questi problemi potevano essere risolti solo da reti neurali omniconnesse in cui ogni neurone connesso con tutti gli altri neuroni della delle connessioni crescerebbe esponenzialmente rete, in una simile rete il numero

all'aumentare del numero di neuroni contrariamente a quanto avviene nei sistemi biologici nei quali le connessioni crescono linearmente. Minsky era uno dei sostenitori di un approccio rivale alle reti neurali, l'Intelligenza Artificiale (A.I.) classica basata su computer tradizionali. In seguito alle tesi di Minsky il campo delle reti neurali fu abbandonato dalla maggior parte degli studiosi, i quali si rivolsero dal fatto che la tecnologia allora disponibile al campo dell'A.I. apparentemente pi difficoltosa o addirittura promettente. Secondo chi scrive comunque, questo cambiamento di interessi fu causato anche rendeva molto impossibile la sperimentazione nel campo delle reti neurali, ne vi erano computer abbastanza veloci per simulare reti neurali complesse. Negli anni sessanta e settanta la ricerca continuo con contributi teorici e poche applicazioni. Alcuni ricercatori come Shunichi Amari, Kunihiko Fukushima e Shephen Grossberg tentarono di simulare il comportamento di neuroni cerebrali con reti di unit di calcolo operanti in modalit parallela. Inoltre formularono teorie matematiche ed architetture per individuare e classificare i tratti caratteristici delle forme da riconoscere e per costruire le prime memorie associative. In queste ultime vengono utilizzate informazioni parziali come chiavi per recuperare memorizzati. dati


25

L'interesse sviluppatosi nei primi anni 80 per i modelli neurali sicuramente dovuto a diversi fattori, che sono elencati di seguito: i progressi compiuti nella comprensione di alcuni fenomeni computazionali biologici, la disponibilit di potenti computer in grado di simulare i nuovi modelli neurali. lo sviluppo di tecnologie VLSI e ottiche che si prestano alla costruzione di circuiti di tipo neuronico. la determinazione dei limiti dell'A.I., i quali sono strettamente legati ai limiti dei computer seriali di Von Neumann. John Hopfield del California Institute of Technology propone nel 1982 un modello computazionale basato su concetti energetici e pertanto applicabile in svariati campi. Questo nuovo modello permise di studiare il comportamento globale di reti molto pi complesse dei perceptron, non analizzabili con metodi classici. In particolare era possibile studiare reti con neuroni nascosti. Con questo risultato termina la "preistoria" dello studio delle reti neurali e inizia la cronaca di un settore in rapida evoluzione. Nel 1987 la CEE promuove il progetto BRAIN (Basic research in adaptive intelligence and neurocomputing), inoltre si tiene a S.Diego la prima conferenza internazionale sulle reti neurali con 2000 partecipanti provenienti sia dalle universit sia dall'industria. Alla luce dei risultati ottenuti, Minsky e Papert rivedono le loro critiche e indicano nuove direzioni di sviluppo nell'area delle reti neurali. I principali settori cui la ricerca attuale indirizzata sono: la rappresentazione della conoscenza la visione il riconoscimento di forme la comprensione del linguaggio naturale le memorie associative la robotica e la sensorica l'inferenza la risoluzione di particolari problemi computazionali.

3.3 - ARCHITETTURA ASTRATTA DI UNA RETE NEURALE

Si descriver adesso l'architettura generale di un analizzando una serie di caratteristiche comuni: 1. unit di computazione base 2. stato delle unit 3. attivit della rete 4. insiemi di connessioni 5. funzione di attivazione 6. regola di apprendimento 7. topologia del modello 8. rappresentazione dei dati

modello di rete neurale, elencando e

- Unit di computazione base. Nel contesto di una rete neurale, l'unit base sulla quale costruito il modello un elemento computazionale semplice disposto in una architettura a rete . L'elemento accetta dei segnali in ingresso, li elabora secondo determinate regole, e sulla base di questi segnali, del proprio stato interno e degli stati precedenti calcola un segnale in uscita Vi , che viene inviato alle unit a cui esso risulta connesso. Il modo in cui avviene tale processo nella rete parallelo, tutte le uscite Vj dei neuroni nel j senso ai che quali molte unit lavorano simultaneamente. In generale l'ingresso di un neurone i rappresentato dalla sommatoria di connesso:

3.1 Tij lintensit della connessione, e si esaminer pi avanti. Le unit risultano divise in tre categorie: unit di ingresso, unit di uscita e unit nascoste. Le prime ricevono ingressi da sorgenti esterne al sistema, le unit di uscita inviano segnali all'esterno del sistema mentre le unit nascoste sono collegate solo con identificata col termine input e output interni. L'unit base pu essere neurone. Diversi autori hanno elaborato un modello dell'unit

fondamentale di calcolo di un sistema di neuroni, si pu dire che essa un emulazione semplificata delle funzioni del neurone biologico. I vari modelli di neuroni elaborati si distinguono generalmente per il tipo di risposta che essi presentano ingresso. In a uno stimolo in questa differenziazione i modelli di neurone rispecchiano i diversi tipi di


27

neurone biologico. - Stato dell'unit. Ad ogni unit associato un valore numerico detto stato dell'unit che generalmente viene fatto corrispondere al valore della variabile in uscita V (t). Per N unit lo stato Vi(t) un vettore di N componenti in cui ciascuna componente rappresenta

l'attivazione di un'unit. I valori dello stato possono essere continui o discreti. Lo stato della rete di neuroni al tempo t descritto dall'insieme di variabili che descrivono lo stato delle unit semplici. - Attivit della rete. L'attivit della rete il numero di neuroni attivi al tempo t:

3.2 - Insiemi di connessioni. Le unit sono interconnesse. In generale l'ingresso di un unit determinato dalla somma pesata delle uscite a cui essa risulta connessa. Lintensit della connessione tra due unit data dal generico peso Tij. Il peso Tij positivo se l'unit j esercita un'azione eccitatrice sull'unit i ed negativo in caso contrario. E' possibile associare ad un sistema di interconnessioni una matrice di pesi T nella quale il generico elemento Tij specifica lintensit della connessione tra l'unit j e l'unit i. L'insieme dei pesi delle connessioni determina come il modello risponder ad un ingresso arbitrario e di conseguenza costituisce la "conoscenza o memoria del sistema". Con una terminologia pi vicina ai sistemi biologici lintensit della connessione tra due unit neuroniche detta sinapsi.

FIGURA 3.1a Rappresentazione grafica della funzione di attivazione V(t+1), che dipende dall ingresso del neurone Ui e dallo stato Vi al tempo t.

- Funzione di attivazione. Una caratteristica importante delle unit di una rete neurale il modo in cui i vari segnali di ingresso vengono combinati per determinare il segnale complessivo. Una funzione di attivazione data da:

3.3 La funzione di attivazione associa allo stato e agli ingressi attuali un nuovo stato di attivazione. La Fi [ ] , nei casi pi semplici, la funzione identit, cio lo stato Vi dell'unit coincide con l'ingresso totale U , e la funzione Fi [ ] risulta lineare. In altri casi Fi [ ] una funzione a soglia per cui l'ingresso totale deve superare un determinato valore per contribuire al nuovo stato dell'unit. Alcune forme caratteristiche della funzione di attivazione sono visualizzate nella figura 3.1b . Si notino le tre forme base non lineari di F i [ ]: hard limiter, threshold logic e sigmoide. Un'altra caratteristica importante delle funzioni di attivazione il loro carattere che pu essere deterministico (stocastico) o non deterministico. Nel primo caso, un neurone cambia sempre il suo stato se l'input eccede una certa soglia. La dinamica della rete in questo caso definita markoviana, cio lo stato della rete al tempo t+ dipende solamente dallo stato della rete al tempo t, e non dagli altri stati precedenti. Nel secondo caso la funzione di attivazione probabilistica (macchina di Boltzmann), per cui anche se l'input supera il valore della soglia, non detto che il neurone cambi stato.

FIGURA 3.1b - Rappresentazione dell'ingresso pesato di un neurone e delle tre principali funzioni di attivazione. (FONTE IEEE ASSP MAGAZINE 4/1987 R.P. LIPPMANN

- Regola di apprendimento. Si detto che la conoscenza di un sistema neurale codificata dai


29

pesi delle connessioni tra le unit, per cui apprendere equivale a modificare i pesi di tali connessioni. A tal fine sono state elaborate varie regole che simulano elementari forme di apprendimento per diversi modelli di reti. I meccanismi di apprendimento possono essere con supervisione (guidati) o senza (spontanei) 7 . Nei primi un supervisore fornisce alla rete degli ingressi e confronta la risposta della rete con quella corretta nota a priori. In base a questo confronto vengono stabilite le modalit di modifica dei pesi di interconnessione. L'apprendimento guidato consente alla rete di imparare tramite i molti esempi forniti dal supervisore, in una modalit che ricorda l'apprendimento umano. La regola di apprendimento spontanea pi semplice quella definito da Hebb8 , la cui idea base Hebb di aumentare il peso T se l'unit i-esima riceve in ingresso l'uscita dell'unit j-esima e le due unit sono contemporaneamente attive. La regola di Hebb espressa come segue: 3.4 Le altre regole di apprendimento spontanee sono delle evoluzioni di quella di Hebb oppure si basano su altri principi. Un'altra fondamentale regole di apprendimento la regola back-propagation utilizzata universalmente in quasi tutte le reti di neuroni che incorporano livelli "nascosti". - Topologia. Fissate le caratteristiche delle singole unit si analizza adesso il modo in cui tali unit sono connesse tra loro cio la topologia della rete neurale. Alcuni esempi di topologie di reti neurali sono rappresentate in figura 3.2. In alcuni modelli le connessioni seguono schemi predeterminati, in altri schemi casuali. Molti modelli vengono organizzati in pi livelli di unit, oppure in diversi strati di connessioni tra unit. Analizzando una rete a pi livelli bisogna distinguere tra livelli "visibili", costituiti da unit di ingresso o uscita, e livelli "nascosti". Analizzando le connessioni tra le unit si possono distinguere modelli feedforward, nei quali esistono connessioni solo tra le uscite e gli ingressi di unit di livelli successivi, e modelli con meccanismi di retroazione detti anche modelli feedback (reti di Hopfield). In questi ultimi modelli si possono avere connessioni tra le uscite di unit di un livello e le entrate di unit di un livello precedente, inoltre, come si vede in figura 3.2, il tipo di feedback pu essere ordinato o amorfo. Nei modelli gating le uscite delle unit agiscono sui pesi delle connessioni. Altre distinzioni si possono fare riguardo la connettivit laterale, cio le connessioni di elementi dello stesso strato. Nel tipo7 T. J. Sejnowsky, "Neural Network Learning Algorithms", NATO ASI Series, Vol. F41, SpringerVerlag, Berlino 1988. 8 Donald O. Hebb, The Organization of Behavior, Wiley, New York 1949.

cooperativo-competitivo

ogni

elemento connesso ai suoi vicini mediante connessioni

alternativamente eccitatorie e inibitorie, nel tipo "on-center/off-surround" le connessioni laterali sono tutte inibitorie, nel tipo a campo ricettivo (reti di Kohonen) ogni ingresso ha una determinata distribuzione sull'intero livello e qualunque tipo. - Rappresentazione dei dati. Nei sistemi neurali i dati in ingresso sono rappresentati definendo lo stato di un particolare insieme di unit di ingresso. Ogni dato complesso viene rappresentato da un insieme di elementi subsimbolici e non dalla modifica arbitraria di un simbolo. Ad esempio le unit di ingresso possono rappresentare la presenza di una lettera in una determinata posizione in una parola, oppure lo stato di un ricettore immaginario su una retina artificiale. La scelta dello schema rappresentativo dei dati contribuisce a determinare la potenza computazionale del sistema. Analogamente l'uscita di una rete neurale viene definita dallo stato di un insieme predeterminato di unit. In molti modelli lo stato delle singole unit di uscita rappresenta la verit o falsit di una determinata proposizione. la connessione laterale pu essere di


31

FIGURA 3.2 - Tipi generali di architetture di reti neurali

3.4 - DEFINIZIONE DI RETE NEURALE

Una definizione generale di rete neurale potrebbe essere la seguente: una rete neurale un insieme di semplici unit di elaborazione (neuroni) altamente interconnesse tra di loro, che interagiscono tra loro e con gli oggetti del mondo esterno mediante lo scambio di segnali in modo simile alle strutture neurali biologiche. Le differenze tra una rete neurale e un computer digitale convenzionale sono state adeguatamente sintetizzate dal fisico Kohohen9 : I principi della logica digitale non sono applicabili a un sistema neurale. I neuroni non possono essere circuiti logici a soglia, perch ogni neurone ha migliaia di input variabili e la stessa soglia e dipendente dal tempo. L'accuratezza e la stabilita di un circuito normale non sufficiente a definire una variabile booleana. Inoltre i processi collettivi, che sono di fondamentale importanza nel calcolo neurale, non sono implementabili mediante semplici circuiti logici. I neuroni e le sinapsi non sono elementi di memoria bistabili come dei flip-flop. I neuroni sembrano comportarsi come dei sistemi integratori analogici di natura non lineare, le sinapsi sono delle connessioni la cui efficacia varia gradualmente. Una rete neurale non ha istruzioni o codici di controllo che regolano lo stato funzionale del sistema. Lo schema di interconnessione di un sistema neurale non permette il calcolo ricorsivo, per cui impossibile implementare algoritmi di calcolo.

9 Kohonen Teuvo. An Introduction to Neural Computing, Neural Networks, Vol. 1. 1988, pag 316.


33

3.5 - CLASSIFICAZIONE DELLE RETI NEURALI

Sebbene le reti neurali siano in rapida evoluzione possibile fare una classificazione dei principali modelli, continuo o riferendoci con essa a evidenziare i diversi approcci di vari autori. Una determinata dal tipo di regola di prima suddivisione pu essere fatta in base all'ingresso dei neuroni che pu risultare discreto. La successiva divisione apprendimento che pu essere con o senza supervisione. Un altro aspetto importante il tipo di funzione di attivazione che pu essere o non essere deterministica. Nei modelli deterministici e stocastici l'evolversi della dinamica del sistema spesso prevedibile a lungo termine (reti di Hopfield). Nei modelli non deterministici, che simulano pi da vicino i sistemi biologici, si ha una funzione d'attivazione probabilistica (Macchina di Boltzmann). La simmetricit della matrice delle connessioni origina una ulteriore suddivisione in reti simmetriche che sono tipicamente le reti di Hopfield, e asimmetriche come i perceptroni. Si formano a questo livello diverse famiglie di reti neurali .10 Nel presente lavoro saranno esaminati i seguenti modelli: Reti di Hopfield discrete e continue Macchina di Boltzmann Perceptrone e Perceptrone multistrato Reti auto-organizzanti di Kohonen

10 Richard P. Lippmann, "An Introduction to Computing with Neural Nets", IEEE ASSP Magazine, Aprile 1987, pag 4-22 .

4. - RETI DI HOPFIELD E MACCHINA DI BOLTZMANN4.1- INTRODUZIONE

Si esamineranno in questo capitolo le reti neurali simmetriche di Hopfield11 e la macchina di Boltzmann. Queste reti, come si vedr nel prossimo capitolo, sono particolarmente adatte alla risoluzione di problemi soluzioni, oppure alla di ottimizzazione combinatoria ad altissimo numero di di memorie associative. implementazione

Si comincer con l'originale modello discreto di Hopfield del 1982 basato su unit con ingressi binari e prototipo di successivi modelli. Una evoluzione del modello discreto di Hopfield il modello continuo, proposto dallo stesso Hopfield nel 1984 capace di ottime prestazione nella risoluzione di problemi particolarmente complessi. In tale modello i neuroni sono realizzati fisicamente da dispositivi elettronici ottimale del problema cui applicata. analogici. La macchina di Boltzmann, esaminata successivamente, permette al contrario dei modelli di Hopfield di avvicinarsi alla soluzione

4.2 - MODELLO DISCRETO DELLA RETE DI HOPFIELD

Il modello discreto di rete neurale proposto da Hopfield formato da N semplici unit di calcolo detti neuroni reciprocamente interconnessi (vedi Fig. 4.1). Ogni neurone pu assumere due stati interni descritti dalla variabile V :

4.1 Lo stato del neurone coincide col valore in uscita dell'unit stessa. Lo stato del sistema a un dato istante definito dall'insieme degli N valori della variabile di stato Vi per cui pu essere rappresentato da un vettore di stato di N bit, V = [V1 , V2 , ... ,VN]. L'ingresso di ciascun neurone espresso nella forma seguente:

4.211 J.J.Hopfield, "Neural Networks and Physical Systems with Emergent Collective Computational Abilities", Proc. Natl. Acad. Sci. 179, pag. 2554 (1982).


35 Tij un elemento di una matrice di

In tale relazione N il numero dei neuroni,

interconnessione T rappresentante l'intensit di connessione tra il neurone i e j, Vj esprime l'uscita del neurone j, mentre Ii un ingresso esterno che viene fornito al neurone i. interruttori SWj realizzazione Gli

commutano in modo asincrono con ritardi casuali e permettono la della retroazione tra le uscite e l'ingresso della rete.

Nelle simulazioni software del capitolo 7 si assume che la chiusura degli interruttori SW i sia sincronizzata. Quando l'i-esimo interruttore si chiude, lo stato interno dell'i-esimo neurone si evolve seguendo la funzione di attivazione seguente: Vi (t+1) = stp [Vi (t)] 4.3

Nella 4.3 il tempo t assume valori discreti, stp(x) una funzione a gradino uguale a 1 se x Si , 0 se x < S , S un valore definito soglia di attivit del neurone i. Senza nessuna perdita di generalit si possono assumere nulle le soglie di tutti i neuroni della rete. Con questa assunzione si pu definire la funzione d'attivazione nella forma:

4.4 Per le reti di Hopfield definita anche una regola di apprendimento che definisce il valore dei componenti della matrice di interconnessione T. La regola di apprendimento utilizzata da Hopfield la regola di Hebb, si esaminer in dettaglio pi avanti il legame tra tale regola e le applicazioni della rete. L'evoluzione del modello discreto di Hopfield nel suo spazio di configurazioni segue le leggi dinamiche dei processi stocastici, per cui lo stato della rete al tempo t+1 determinato unicamente dallo stato al tempo t precedente. Per determinare lo stato della rete al tempo t+1, non richiesta quindi alcuna informazione per tempi precedenti l'istante t.

FIGURA 4.1a - In alto mostrata la funzione di attivazione di una rete discreta di Hopfield, il cui schema mostrato in basso. (FONTE P.N.A.S. 79/1982 J.J. HOPFIELD)


37

4.3 - CONSIDERAZIONI ENERGETICHE SULLA RETE DISCRETA DI HOPFIELD

Hopfield ha definito per il suo modello una funzione energia che rivela propriet della

importanti

rete. Considerando una matrice T di pesi di connessione simmetrica e con

elementi diagonali nulli si definisce la funzione energia computazionale come segue:

4.5 Si consideri adesso la variazione di energia E dovuta alla variazione dello stato Vi di un neurone, si assuma la variazione del neurone i da uno stato inattivo a uno attivo, si ha:

4.6 La variazione di stato -Vi uguale a 1 nel caso considerato per cui si ha: Ei= -Vi Ui (t+1)= -Vi Vi (t+1) = -1 < 0 4.7

Si noti che nel caso di un neurone che passa da uno stato Vi(t) = 1 a uno stato Vi(t+1)=0 si ha

Vi = -1 , mentre per la 4.7 Ei = 0. La variazione totale di energia della rete :

se Ei 0

allora

E 0

4.8

Da queste considerazioni Hopfield concluse che l'energia computazionale, al variare dello stato del sistema neurale, decresce monotonicamente fino a raggiungere un minimo locale. Dalla simmetria della definizione dello stato di un neurone risulta che se un vettore corrisponde a uno stato stabile della rete allora anche il vettore complemento sar stabile. Se consideriamo lo stato dei neuroni espresso mediante le variabili i = 1 che sono legate alle Vi dalla relazione i = 2Vi - 1, i vettori rappresentanti lo stato della rete possono essere rappresentati nello spazio degli stati, tale spazio composto dalle N componenti i corrisponde a un ipercubo con coordinate 1 . I vettori che minimizzano E corrispondono ai vertici dell'ipercubo N-dimensionale. (vedi figura 4.3). Hopfield dimostr l'esistenza di una funzione di Ljapunov nello spazio degli stati della suo modello Ljapunov corrisponde di rete neurale, tale funzione di all'energia computazionale. Seguono adesso alcune importanti

definizioni legate alle funzioni di Ljapunov: Una funzione H : S detta di Ljapunov se, dato un qualunque s(to) S vale: ( t t0 ) : s(t + 1) s(t) s(t) = {si (t)} i=1,2,...n

H(s(t + 1)) H(s(t))

lo stato del sistema al tempo t

Un punto s S di equilibrio se: ( t ) : s(t) = s vale: s(t) = s

( t t ) s(t ) = s

Un punto s S di attrazione se di equilibrio ed esiste un intorno I di s tale che s I

( t t ) s(t ) = s

Hopfield studi il comportamento della rete mediante simulazioni software, verificando sia che la funzione energia fosse una funzione di Ljapunov, sia la presenza dei punti attrattori di energia minima verso i quali la rete evolveva.

FIGURA 4.1b - Sequenza di transizioni di un sistema fisico da uno stato iniziale V1 ad uno finale stabile V8, corrispondente ad un minimo di energia.


39

Come gi detto la rete di Hopfield corrisponde a un sistema fisico descritto nello spazio degli stati del sistema di coordinate V 1 ,V2 ,..VN e caratterizzato da punti di attrazione o iniziale V

minimi locali V1 ,V2. Se il sistema viene fatto partire da una

configurazione

sufficientemente vicina a una configurazione di attrazione, ad esempio V = V1 + , esso evolver nel tempo fino a raggiungere la configurazione stabile V1 (vedi figura 4.1b). Un sistema fisico la cui dinamica nello spazio delle configurazioni dominata da un certo numero di stati attrattori pu trovare applicazioni nel campo delle memorie indirizzabili per contenuto C.A.M. (Content Addressable Memory o Memorie Associative) o come si vedr pi avanti col modello memorizzata mentre continuo di Hopfield nella risoluzione di problemi di iniziale una conoscenza parziale ottimizzazione. Nel primo caso si vedr che gli stati attrattori corrispondono all'informazione la configurazione dell'informazione.

4.4 - REGOLA DI APPRENDIMENTO DI HEBB E APPLICAZIONI C.A.M. DEL MODELLO DISCRETO DI HOPFIELD Una C.A.M. o memoria associativa un nuovo modello di memoria capace di restituire l'informazione memorizzata in risposta ad un ingresso rappresentato da una conoscenza parziale dell'informazione (vedi fig 4.1c). Al contrario in un memoria convenzionale i contenuti sono ricavati tramite gli indirizzi delle locazioni dove sono memorizzati. Il modello discreto della rete di Hopfield si presta naturalmente ad implementare una memoria associativa . Si supponga di voler memorizzare un set di M vettori binari V(s) s=1,2,...,M , Hopfield suggerisce di utilizzare una rete neurale facendo corrispondere gli stati stabili della rete con i vettori da memorizzare. L'algoritmo di memorizzazione proposto la regola di apprendimento di Hebb, mediante la quale si costruisce una matrice T di pesi definita come segue:

4.9 Si deve avere inoltre Tii = 0 e T ij = Tji . Si noti che utilizzando le variabili di stato i= 1, la regola di Hebb viene espressa in una forma molto usata in alcuni lavori:

4.10 In generale una rete descritte di seguito: 1. Fase di apprendimento. Questa fase consiste nella costruzione della matrice di neurale operante come memoria associativa opera nelle due fasi

interconnessioni T. Vengono presentati in ingresso alla rete neurale gli M vettori binari V(s) che sono i dati da memorizzare, la rete setta le connessioni tra i neuroni in accordo alla regola di apprendimento descritta dalle equazioni 4.9 e 4.10. 2. Fase operativa della memoria. In questo periodo avviene il richiamo delle informazioni memorizzate. La rete viene inizializzata con un qualsiasi vettore in ingresso, e comincia in tal modo l'evoluzione temporale della rete nello rappresenta una parte di un dato memorizzato, spazio delle configurazioni,

seguendo la funzione di attivazione 4.4 definita in precedenza. Se il vettore iniziale la rete evolve raggiungendo una configurazione finale stabile di energia computazionale minima. La configurazione finale pu risultare uno dei vettori memorizzati oppure uno stato particolare detto metastabile, che un minimo locale di energia non corrispondente a nessuno dei vettori memorizzati. Nella rappresentazione nello spazio degli stati che rappresenta la superficie stabile. La rete di Hopfield utilizzata come memoria associativa presenta due limiti non trascurabili. Il primo limite fissa il numero massimo di vettori memorizzabili e richiamabili con sufficiente accuratezza. Hopfield ha mostrato che il numero massimo di vettori memorizzabili Mmax 0.15*N, N il numero di neuroni della rete. Un altro limite consiste nella difficolt di memorizzare vettori con molti bit in comune e vettori con forti sbilanci tra bit ad 1 e bit a 0. Tali limiti saranno esaminati nel capitolo 7. della rete uno stato metastabile rappresentato come tutti i minimi di energia da uno dei vertici dell'ipercubo N-dimensionale energetica. Per particolari condizioni iniziali la rete presenta un comportamento oscillatorio per cui non viene mai raggiunto uno stato finale


41

FIGURA 4.1c - In alto lo schema architetturale del modello discreto di Hopfield che implementa una memoria associativa, in basso si vede il proncipio di funzionamento

4.5 - MODELLO CONTINUO DELLA RETE DI HOPFIELD

Nel lavoro successivo Hopfield12 propone un nuovo modello di rete di neuroni basato su unit di elaborazione analogiche, che segue la dinamica di un sistema fisico in uno spazio di configurazioni continuo. Nel nuovo modello si ha un'analogia pi marcata tra i fenomeni fisici osservati nei neuroni biologici e descritti dalla neurodinamica classica e quelli che governano il funzionamento della rete artificiale. Lo stato del neurone descritto dalla variabile in ingresso U , la funzione di uscita continua e limitata: Vi (t) = gi (Ui (t)) Vi0 Vi (t) Vi1 g (- ) = 0 g(+ ) = 1 La funzione di uscita Vi (t) una sigmoide monotona crescente con asintoti Vi0 e Vi1.

La rete continua di Hopfield progettata per essere facilmente realizzabile fisicamente (si veda la figura 4.2). Le unit di elaborazione sono costruite mediante amplificatori operazionali con tempo di risposta trascurabile, e la cui caratteristica ingresso-uscita corrisponde alla funzione di uscita Vi (t) . In questo caso Vi (t) = gi (Ui (t)) la tensione di uscita del i-esimo amplificatore mentre Ui(t) la tensione in ingresso.

La connessione tra un amplificatore j e uno i realizzata mediante resistenze di conduttanza Tij . Ogni amplificatore dotato di due uscite, una normale e una inversa, in modo da realizzare connessioni eccitatrici e inibitrici. Il valore dell'uscita normale compreso tra 0 e 1, mentre l'uscita inversa da i valori tra 0 e -1. Tra l'ingresso di ciascun amplificatore e la massa inserito un gruppo parallelo, costituito da una resistenza i e una capacit Ci, che

definisce le costanti di tempo della rete. La corrente in ingresso totale di ciascun unit di elaborazione composta da due termini, il primo la sommatoria di tutte le correnti provenienti da tutte le unit connesse, il secondo una corrente di alimentazione esterna . A questo punto si pu descrivere la dinamica del sistema degli N amplificatori interagenti mediante le equazioni differenziali seguenti:

4.11

12 J.J Hopfield, Neuron with graded response have collective computational properties like two-state neurons, Proc. Natl. Acad Sci. 81, pag. 3088 (1984).


43

FIGURA 4.2a - In alto mostrata la funzione di attivazione di una rete continua di Hopfield, in basso mostrato lo schema elettrico della rete. (FONTE P.N.A.S. 81/1984/J.J. HOPFIELD)

FIGURA 4.2b - In alto mostrato lo schema elettrico di una rete continua di Hopfield.


45

dove Ri data dalla relazione :

4.12 i la resistenza in ingresso dell'amplificatore i, si assume che l'impedenza in uscita all'amplificatore sia nulla. L'interpretazione biologica del modello continuo di Hopfield quasi immediata. La neurodinamica classica porta alle seguenti considerazioni: 1. L'uscita Vi del unit computazionale i pu essere identificata col numero medio di

potenziali d'azione nell'unit di tempo emessi dal neurone i. 2. Il voltaggio in ingresso Ui all'unit i analogo al debole potenziale prodotto nel neurone i postsinaptico quando i potenziali d'azione dei neuroni presinaptici raggiungono la sinapsi e liberano i neurotrasmettitori chimici. L'input totale del neurone i j Tij Vi + Ii , dove Tij rappresenta l'efficienza della sinapsi tra il neurone i e il neurone j. 3. La resistenza e la capacit della membrana cellulare del neurone i sono espresse dalle costanti i e Ci . Le equazioni dinamiche che descrivono il modello neurale biologico definito sono quelle definite da Hopfield per il suo modello continuo di rete neurale. Queste equazioni omettono l'effetto della quantizzazione dei potenziali d'azione, inoltre considerano infinita la velocit di propagazione di tali potenziali. Conoscendo i valori delle tensioni Ui al tempo t = 0, le equazioni dinamiche permettono di ricavare una descrizione completa dell'evoluzione temporale dello stato del sistema. Analogamente al modello discreto, Hopfield ha trovato che, nell'ipotesi di simmetria della matrice di connessione, le equazioni dinamiche del modello continuo conducono alla convergenza verso stati stabili, cui dell'energia computazionale. Nell'ipotesi che la matrice T abbia gli elementi diagonali nulli e sia simmetrica l'energia computazionale definita come segue: corrispondono i minimi

4.13 Hopfield ha dimostrato che la derivata rispetto al tempo dell'energia computazionale

nell'ipotesi di una matrice T simmetrica, minore o uguale a zero, si ha infatti:

4.14 Dato che gi-1 (Vi ) una funzione monotona non decrescente e Ci sempre positivo, ogni termine della somma 4.14 non negativo per cui si ha: dE/dt 0 , dE/dt = 0 quando dVi /dt = 0 i Si pu affermare che l'energia computazionale una funzione di Ljapunov per il sistema. Inoltre se la curva di guadagno dell'amplificatore molto stretta l'ultimo termine di questa equazione nullo, per cui E espressa nella stessa forma del modello discreto. Il modello continuo di Hopfield deterministico, analogamente al modello stocastico lo stato della rete al tempo t determina unicamente lo stato della rete al tempo t + . Hopfield studiando il comportamento dei due modelli descritti ha osservato che il modello continuo deterministico continuo conserva le stesse propriet del modello discreto stocastico, ma si rivela pi veloce nel risolvere difficili problemi computazionali. Si vedranno adesso le relazioni tra gli stati stabili dei due modelli. Siano fatte per semplicit le seguenti assunzioni: gi (0) = 0, Vi0 = -1, Vi1 = 1, Ii = 0

indice i

L'energia per il caso considerato e:

4.15 Si ricercano adesso i massimi e i minimi del primo termine di E nel dominio dell'ipercubo definito mediante i vertici -1 V 1 i. Nel caso discreto stocastico l'energia E rappresentata solo dal primo termine della 4.15, e si detto che gli stati stabili corrispondono ai vertici dell'ipercubo N-dimensionale rappresentante lo spazio degli stati. Dato che E una funzione lineare di Vi con Vj costante, allora i minimi di energia del primo termine di E che ha variabili di stato continue nell'intervallo -1 V 1 corrispondono a quelli del caso discreto con variabili di stato i = 1. Il secondo termine di E altera tale interpretazione , consideriamo adesso la variabile Vi definita non pi da gi (Ui ) ma mediante il parametro (


47

si vedr che nella macchina di Boltzmann il parametro -1 assumer il significato virtuale di una temperatura), si ha: Vi = gi ( Ui) e Ui = (1/)g-1(Vi)

FIGURA 4.3 - In alto mostrata la superficie energetica nello spazio delle coordinate r ed E, in basso si ha la stessa superficie vista dall'alto. (FONTE P.N.A.S. 81/1984 J.J.HOPFIELD; PHYSICAL D 1986/J.S DENKER)

Il parametro cambia la forma della funzione sigmoide g(x) senza alterarne gli asintoti (vedi figura 4.4). Il secondo termine di E diventa:

4.16 L'integrale 4.16 nullo per Vi = 0 e positivo altrimenti, e assume un valore molto alto per Vi tendente a 1. Riferendosi alla figura 4.3 che rappresenta la superficie corrispondente alla funzione energia nello spazio di coordinate Vi rispetto i ed E, si ha che per >> 1 i minimi di vertici dell'ipercubo, al crescere di i

energia sono dislocati verso l'interno

minimi di E si spostano verso l'esterno tendendo a posizionarsi sui vertici dell'ipercubo. Nel limite (la sigmoide diventa una funzione a gradino come si vede in alto alla figura 4.4) tale termine diventa trascurabile e la posizione dei minimi di energia nello spazio degli stati la stessa del modello discreto stocastico. Nel limite opposto 0 seleziona un numero reale a caso h tra 0 e 1; 6. se exp(E/kT) < h conserva la configurazione attuale; 7. se exp(E/kT) h accetta la nuova configurazione; Le regole elencate vengono ripetute iterativamente molte volte, consentendo di campionare lo spazio delle fasi di un sistema a contatto con un termostato a temperatura T con una probabilit proporzionale alla densit degli stati. Come si vede nell'algoritmo di Metropolis il caso E > 0 viene trattato probabilisticamente: la probabilit che la nuova configurazione venga accettata P(E) = exp(E/kT). Tale scelta permette al sistema di evolvere seguendo la distribuzione di Boltzmann. La macchina di Boltzmann essenzialmente una rete discreta di Hopfield con una funzione di attivazione probabilistica, nella cui modalit operativa implementata una forma dell'algoritmo di Metropolis detta annealing simulato utilizzata per raggiungere l'equilibrio. Il termine annealing simulato deriva dall'analogia con il processo di annealing condizione14

fisico

canonico

di

N

particelle.

utilizzato per portare un sistema fisico nello stato pi basso del potenziale la di equilibrio termodinamico raggiunta massimizzando l'entropia e nella struttura

termodinamico corrispondente alle condizioni esterne imposte. In un sistema generico

minimizzando l'energia interna. Per un solido l'energia interna minima corrisponde a quella di un cristallo perfetto, ma un solido reale caratterizzato da difetti

14 C. Kittel , Introduzione alla Fisica dello Stato Solido, Boringhieri 1971, Terza edizione.


51

cristallina (vacanze di atomi o dislocazioni dei piani reticolari). A temperatura T si hanno degli effetti contrastanti, la formazione di difetti reticolari aumenta l'entropia del solido, mentre l'eliminazione dei difetti diminuisce l'energia interna: la condizione di equilibrio di un cristallo lo stato di energia libera di Helmholtz F=U-TS minima. In un cristallo si pu definire la concentrazione di difetti all'equilibrio ad una data temperatura Ndequ(T), la quale cresce con la temperatura. Se esiste una concentrazione di difetti in un cristallo, esister anche una diffusione di difetti, caratterizzata dalla costante di diffusione D(T). All'equilibrio i difetti saranno uniformemente distribuiti. Un atomo interstiziale o una vacanza pu diffondere, se riesce a superare una barriera di energia potenziale dovuta al reticolo. Se la temperatura alta la costante di diffusione D(T) sar anch'essa alta, e il cristallo raggiunger velocemente la concentrazione Ndequ(T). Per temperature basse la mobilita dei difetti ridotta, dato che pu risultare molto improbabile il superamento della barriera di potenziale del reticolo Ep . In questo caso la concentrazione dei difetti reale Nd potr essere maggiore di Ndequ(T). Per poter eliminare i difetti reticolari di un cristallo si ricorre alle tecniche di annealing: il solido viene portato quasi fino al punto di fusione, quindi viene ridotta lentamente la temperatura attraverso trasformazioni quasi reversibili. La rapidit con cui viene ridotta la temperatura deve consentire al sistema di mantenersi in equilibrio termodinamico, in modo che si abbia sempre Nd= Ndequ(T). Abbassando la temperatura T si abbassa anche Ndequ(T) e quindi anche l'energia libera F. Kirkpatrick ed altri hanno notato che trovare lo stato a di minima energia di un sistema essenzialmente un problema di la meccanica ottimizzazione simile a quelli di ottimizzazione combinatoria. I metodi che

statistica adotta per sistemi a molte particelle possono essere utili anche in problemi di ottimizzazione combinatoria, i quali sono caratterizzati da un altissimo numero di soluzioni corrispondenti al minimo globale di una funzione energia computazionale. 4.7 - MACCHINA DI BOLTZMANN

L'idea base della macchina di Boltzmann di introdurre nei processi di cambiamento stato dei neuroni una componente di casualit che generalizzi il concetto di temperatura. Questa di considerazione porta a incorporare nel processo decisionale del neurone dei contributi di rumore che permettono il cambiamento di stato del neurone con una funzione attivazione probabilistica, che classifica la macchina di Boltzmann nell'insieme di reti neurali non deterministiche. Allo scopo di definire la funzione di attivazione si consideri la rete di Hopfield. In tale modello la variazione di energia dovuta al cambiamento di stato di un

neurone e con correnti Ii nulle:

Se Ei il gap di energia tra lo stato 1 e lo stato 0 del neurone i della rete, la probabilit che il neurone i si setti allo stato 1 data dalla regola di decisione seguente:

4.18 tale probabilit indipendente dallo stato precedente del neurone. T un parametro che si comporta come la temperatura. La funzione probabilit pi mostrata nella figura 4.5.

FIGURA 4.5 - Funzione di attivazione probabilistica della macchina di Boltzman


53

Utilizzando le generalizzazioni espresse per le reti neurali, si pu esprimere lo stato Vi del neurone i mediante la funzione di attivazione probabilistica seguente:

4.19

4.20 La 4.20 la funzione di attivazione della macchina di Boltzmann, essa una sigmoide ed esprime la probabilit di attivazione del neurone i (vedi figura 4.4). La regola di probabilit espressa dalla funzione 4.18 uguale alla distribuzione di probabilit di un sistema fisico a due stati di energia A e B. Un sistema di particelle a contatto con un termostato a una data temperatura raggiunger l'equilibrio termico, e la probabilit di trovare il sistema in un dato stato globale segue la distribuzione di Boltzmann. In modo concorde una rete di neuroni che segue la regola di decisione 4.20, raggiunger uno stato di Boltzmann: pa/pb = exp(-Ea - Eb)/T) 4.21 equilibrio termico a temperatura T nel quale la probabilit relativa dei due stati della rete segue la distribuzione di

in tale relazione pa e pb sono rispettivamente le probabilit che il sistema si trovi nello stato A o B di energia Ea e Eb . Si noti che l'equilibrio termico corrisponde a una distribuzione di probabilit sugli stati stabile. Per un valore di T=0, il sistema si comporta come una semplice rete di Hopfield discreta, la 4.20 diventa una funzione a gradino come nella rete discreta di Hopfield. Per valori elevati di T, pi pari circa a 0.5 ed il sistema presenta stati di attivazione casuali. Gli stati metastabili della macchina di Bolzmann sono legati al parametro T della 4.20, infatti il loro numero cresce con la temperatura T. Per quanto detto possibile pensare ad una analogia tra gli stati metastabili della macchina di Boltzmann e la configurazione dei difetti reticolari. L'annealing simulato implementato nella macchina di Boltzmann non un vero algoritmo di apprendimento, piuttosto una procedura utilizzata nella fase di funzionamento della rete successiva all'apprendimento. La macchina di Boltzmann viene fatta funzionare presentando in ingresso un vettore e seguendo l'evoluzione

spontanea della rete fino alla produzione di un vettore finale di uscita. All'inizio della fase di funzionamento, analogamente al processo di annealing, la temperatura T ha un valore elevato. La funzione di attivazione in questo caso pari a 0.5, per cui se il sistema si trova in un minimo locale di energia (stato metastabile) , il valore elevato di T provoca un evoluzione casuale dello stato della rete favorendo l'allontanamento da tale minimo. Infatti lo stato della macchina di Boltzmann pu fluttuare anche per un vettore in ingresso costante corrispondente a uno stato metastabile. Questo comportamento analogo a quello degli atomi di un solido che per temperature elevate riescono a superare la barriera di potenziale , in modo da rendere uniforme la concentrazione di difetti Ndequ(T) . Ogni volta che la rete produce un uscita, quest'ultima viene retroazionata all'ingresso della rete, in questa fase viene ridotto il parametro temperatura della funzione di attivazione. In tal modo si riducono sia gli stati metastabili accessibili , sia le possibilit della macchina di uscire da uno stato metastabile raggiunto. In definitiva quando la temperatura T tende a 0, lo stato raggiunto dalla rete si avviciner di molto a un minimo globale dell'energia computazionale.

4.8 - REGOLA DI APPRENDIMENTO PER LA MACCHINA DI BOLTZMANN

Hinton ed altri hanno recentemente definito per la macchina di Boltzmann un algoritmo di apprendimento15 di tipo guidato, che consente alla rete di imparare come associare ad un determinato vettore in ingresso il corrispondente vettore di uscita. Si consideri la macchina di Boltzmann costituita da livelli di unit visibili e nascoste. L'apprendimento avviene in due fasi distinte, una positiva ed una negativa, seguite da un processo di modificazione dei pesi delle connessioni: 1. Fase positiva di training. Questa la fase di addestramento della rete. Vengono presentate alle unit visibili della rete, una alla volta, delle coppie di vettori ingressouscita. Ogni volta la rete viene gradualmente portata all'equilibrio termico, partendo da un alto valore di T fino a T = 1. All'equilibrio il sistema viene mantenuto per alcuni cicli. Alla fine di questa fase viene calcolata per ogni connessione la probabilit pij+ unit i e j siano entrambe attive durante l'equilibrio termico. 2. Fase negativa di test. questo caso vengono La fase di verifica dell'addestramento analoga, ma in ingresso e vengono calcolate presentati solo i vettori di che le

all'equilibrio le probabilit pij- . Se la rete alla fine delle due fasi presenta le stesse15 S.E. Fahlman G.E. Hinton. Connectionist Architectures for Artificial Intelligence. IEEE Computer, Gennaio 1987, pag. 100-109.


55 non viene effettuata nessuna modifica ai pesi di

distribuzioni

di probabilit pij+ e pij-

connessione. Se invece le probabilit pij+ e pij- sono diverse allora si deve modificare il peso della connessione. Precisamente indicando con G una misura teorica fra il della rete e quello desiderato, Ackley e Hinton hanno 4.22 comportamento effettivo dimostrato che :

G/ T = -(1/T) (pij+ - pij-)Da quanto detto chiaro che per per le quali risulta pij+ pijottenere il

comportamento desiderato dal sistema

necessario introdurre una regola di apprendimento in modo che i pesi di tutte le connessioni , si modifichino spontaneamente in modo da annullare la

derivata di G rispetto il peso. Il principale limite della macchina di Boltzmann la bassa velocit di convergenza al minimo globale dell'energia.

5. - ALTRI MODELLI: PERCEPTRONI E RETI DI KOHONEN 5.1 - INTRODUZIONE

In questo capitolo si approfondiranno gli sviluppi di uno dei primi modelli di rete di neuroni ad apprendimento spontaneo, il perceptrone di Rosemblatt. Il perceptrone nasce come un modello semplificato del sistema nervoso, di cui avrebbe dovuto duplicare le funzioni cognitive. Rosemblatt proponeva il modello non come un dispositivo logico equivalente alla macchina di Turing, bens come un sistema capace di effettuare associazioni fra stimoli simili. Le sue differenze rispetto un sistema logico erano notevoli, infatti le sue risposte a stimoli nuovi non erano a priori prevedibili, essendo determinate dai concetti appresi precedentemente, inoltre esso riusciva a funzionare anche in presenza di rumore sul segnale di ingresso. Saranno esposti pi avanti i principi di funzionamento del perceptrone semplice che deriva direttamente dal modello di Rosemblatt e dell'evoluzione successiva perceptrone Nell'ultimo paragrafo viene presentata la di reti neurali. multistrato. regola di apprendimento back-propagation, costituita dal

inizialmente applicata a perceptroni multistrato ed estesa recentemente a moltissimi modelli


57

5.2 - PERCEPTRONE A SINGOLO STRATO

L'originale modello di perceptrone proposto da Rosemblatt16 composta da unit di calcolo dette

una primitiva rete neurale

neuroni lineari a soglia (vedi figura 5.1 in alto).

I neuroni sono disposti generalmente a tre livelli e la topologia della rete e di tipo feedforward. Il primo livello la griglia retinica o retina (unit Si ) alla quale vengono presentati gli ingressi, il secondo livello (unit Ai ) svolge funzioni di classificazione o riconoscimento, il terzo livello (unit-R) presenta l'uscita discreta 0 o 1 prodotta dalla macchina. L'apprendimento del perceptrone si manifesta con la modifica dei pesi P delle connessioni tra il secondo e il terzo livello di neuroni, per tale caratteristica il modello detto anche singolostrato (single-layer). Le connessioni tra il livello d'ingresso e quello centrale rimangono sempre fisse e servono solo per dare una codifica ai dati di ingresso. Da quest'ultima osservazione risulta che possibile eliminare il livello di neuroni di ingresso senza In tal modo si pu definire un modello generalizzato di nessuna perdita di generalit.

perceptrone a singolo strato di connessioni e a due livelli di neuroni come si nota in basso alla figura 5.1. Il primo livello di neuroni riceve direttamente gli ingressi ed e connesso con sinapsi variabili al secondo livello (costituito per semplicit da un solo neurone) che produce l'output. La funzione di attivazione :

5.1 Si la soglia di attivit del neurone i, stp[x] una funzione non lineare limitata a gradino (hard-limiter). La funzione principale attuata da un perceptrone quella di classificatore di forme. Si consideri la semplice unit di figura 5.1, questo neurone computa la somma pesata degli input sottrae la soglia S i e tramite la funzione di attivazione produce un output +1 o 0. Il tipo di uscita permette di decidere, per convenzione, quale delle due classi A o B appartiene l'ingresso. Una utile tecnica per analizzare il comportamento di un perceptrone e di tracciare un grafico come quello di figura 5.1, nel quale sono mappate in uno spazio le cui coordinate sono gli ingressi del neurone i, le regioni di appartenenza degli input alle varie classi, separate da un iperpiano detto regione di decisione. La posizione dell'iperpiano, che nel caso di due variabili di ingresso della figura una retta, dipende dai16 Frank Rosemblatt, The perceptron, a probabilistic model for information storage and organization in the brain, Psychological review, 65 pag 386-408.

pesi di connessione Tij . I pesi delle connessioni e le soglie di un perceptrone possono essere scelte e modificate mediante diversi algoritmi. L'originale regola di apprendimento di un perceptrone fu sviluppata da Rosemblatt. Questa regola permette di attuare un tipo di apprendimento con supervisione in base al quale viene presentato al perceptrone una forma da classificare, la risposta della rete viene confrontata con quella nota a priori, l'eventuale differenza trovata viene utilizzata per modificare i pesi di connessione dei neuroni che forniscono una risposta scorretta. La regola delta : 5.2 Vi* l'uscita desiderata, un numero positivo minore di 1, Ui e Vi sono rispettivamente l'ingresso e l'uscita del perceptrone. La scelta di controlla la stabilit e la velocit di convergenza dell'apprendimento al giusto risultato. L'apprendimento avviene in modo iterativo secondo la procedura seguente: 1. Inizializzazione pesi e soglie. In questa fase vengono inizializzati a caso, a valori diversi da zero, i pesi e la soglia del neurone di uscita. 2. Fase di apprendimento. In questa fase viene presentato un nuovo ingresso al perceptrone ed calcolata l'uscita, in base alla quale viene applicata iterativamente la regola delta esposta. Nei casi semplici l'algoritmo converge, per cui dopo un certo numero di passi le modificazioni da apportare ai pesi sono nulle, e la risposta fornita dalla rete quella giusta. Una versione leggermente modificata della regola di Rosemblatt stata proposta da B. Widrow e M. Hoff 17 ed chiamata regola LMS. La regola LMS (Least Mean-Square) viene applicata al modello di perceptrone di Widrow noto come Adaline uguale nella struttura al perceptrone mostrato in figura 5.1. L'Adaline differisce dal per

Tesi Di Laurea - Reti Neurali Neural Networks

Documents

Transcript of Tesi Di Laurea - Reti Neurali Neural Networks