Utilizzo di reti neurali per il riconoscimento di volti da foto

Università Politecnica delle Marche
FACOLTA‘ DI INGEGNERIA
Corso di Laurea in Ingegneria Informatica e dell‘Automazione
Utilizzo di reti neurali
per il riconoscimento di volti da foto
Relatore:
Prof. Aldo Franco Dragoni
Tesi di Laurea di:
Marco Favi Borgognoni
Anno accademico 2009/2010
INDICE
1 INTRODUZIONE......................................................................................................................... 1
1.1 ANALISI PROBLEMA ......................................................................................................................... 2
1.2 STRUTTURA TESI ............................................................................................................................. 3
2 TECNICHE DI RICONOSCIMENTO DEL VOLTO ............................................................................ 5
2. 1 RAPPRESENTAZIONE E CONFRONTO ................................................................................................. 5
2.2 PRINCIPAL COMPONENT ANALYSIS PCA .......................................................................................... 6
2.3 HIDDEN MARKOV MODEL (HMM) ................................................................................................ 10
2.4 RICONOSCIMENTO ATTRAVERSO RETI NEURALI .............................................................................. 13
3 RETI NEURALI ........................................................................................................................14
3.1 STORIA DELLE RETI NEURALI........................................................................................................... 15
3.2 STRUTTURA DI UN NODO, FUNZIONI DI ATTIVAZIONE...................................................................... 18
3.3 TIPI DI ARCHITETTURA ................................................................................................................... 19
3.4 TIPI DI APPRENDIMENTO................................................................................................................. 23
3.5 BACKPROPAGATION ........................................................................................................................ 24
3.6 TIPI DI RETE .................................................................................................................................... 27
3.6.1 Percettrone .................................................................................................................................... 27
3.6.2 SOM ................................................................................................................................................... 28
3.6.3 Growing Neural Gas (GNG) ...................................................................................................... 30
3.6.4 LVQ ..................................................................................................................................................... 32
3.7 RETI NEURALI MODULARI ................................................................................................................ 36
4 LOGICA FUZZY E SISTEMI NEURO-FUZZY ...............................................................................39
4.1 STORIA DELLA LOGICA FUZZY.......................................................................................................... 39
4.2 CONCETTI FONDAMENTALI .............................................................................................................. 40
4.3 FUNZIONI DI APPARTENENZA .......................................................................................................... 42
4.4 OPERAZIONI SUGLI INSIEMI ............................................................................................................. 42
4.4.1 Negazione ...................................................................................................................................... 43
4.4.2 Unione (OR) .................................................................................................................................. 43
4.4.3 Intersezione (AND) .................................................................................................................... 44
4.5 SISTEMI FUZZY ................................................................................................................................ 44
4.5.1 Fuzzificazione .............................................................................................................................. 45
4.5.2 Defuzzificazione.......................................................................................................................... 46
4.6 SISTEMI IBRIDI ................................................................................................................................ 47
5 FACE RECOGNITION SYSTEM ..................................................................................................51
5.1 ARCHITETTURA SISTEMA................................................................................................................. 52
5.2 ESTRAZIONE FEATURE ..................................................................................................................... 53
5.3 RETI NEURALI .................................................................................................................................. 53
5.4 CONDIZIONAMENTO BAYESIANO ..................................................................................................... 55
5.5 FUNZIONI DI SINTESI........................................................................................................................ 56
5.5.1 Inclusion based e ottimizzazioni .......................................................................................... 56
5.5.3 Algoritmo pesato ........................................................................................................................ 57
5.6 MODULO PER LA RETROAZIONE ....................................................................................................... 58
6 DATABASE DI FOTO ................................................................................................................60
6.1 CREAZIONE DATABASE .................................................................................................................... 61
6.2 PROBLEMATICHE RISCONTRATE ...................................................................................................... 62
7 CONCLUSIONI E SVILUPPI FUTURI ...........................................................................................64
CONCLUSIONI....................................................................................................................................................... 64
SVILUPPI FUTURI ................................................................................................................................................. 64
RINGRAZIAMENTI ......................................................................................................................66
BIBLIOGRAFIA ...........................................................................................................................67
1
Capitolo 1
Introduzione
Sistemi sofisticati di sicurezza sono divenuti molto importanti nella vita di tutti i giorni,
specialmente per quanto riguarda l‘identificazione di una persona. Esistono diverse
tecniche per identificare un individuo, che possono essere classificate in due categorie:
tecniche biometriche, e tecniche non biometriche [1].
Esistono invece molti sistemi biometrici, che utilizzano caratteristiche proprie di ogni
individuo, come ad esempio l‘iride, l‘impronta digitale, la voce, la firma e il volto per
l‘identificazione, e alcuni di questi hanno raggiunto un alto livello di precisione [2]. Alcuni
sistemi come ad esempio il riconoscimento dell‘iride o dell‘impronta digitale, sono molto
intrusivi, e richiedono la cooperazione dell‘utente oltre che equipaggiamenti costosi
(scanner particolari) [2]. I sistemi di riconoscimento del volto invece, hanno bisogno di
attrezzature poco costose (ad esempio una telecamera di video sorveglianza) e sono in
grado di catturare le caratteristiche del soggetto senza nessuna cooperazione di
quest‘ultimo. Per questo motivo hanno recentemente ricevuto notevole attenzione e le
ricerche in questo settore sono aumentate notevolmente in questi ultimi anni.
Le modalità di riconoscimento utilizzate nelle tecnologie biometriche possono essere
distinte in: autenticazione (one-to-one matching) e identificazione (one-to-many matching).
Da notare che allo stato attuale, oltre ai volti, solo le impronte digitali e l‘analisi dell‘iride
consentono un efficace riconoscimento one-to-many.
Alcuni esempi di utilizzo possono essere [3]:
Login su computer
Autenticazione dell‘accesso ai siti web
Verifica di tessere personali: carte di credito, passaporti, patenti di guida, carta
d‘identità
CAPITOLO 1: INTRODUZIONE
2
Identificazione in ambienti (affollati) da proteggere, e sorveglianza notturna: negozi,
banche, stazioni, aeroporti, ecc.
Accesso ad aree riservate: ospedali, uffici governativi o militari
Accesso a sportelli bancari automatici ATM (Automatic Teller Machine)
Sistemi di apprendimento a distanza. Ad esempio nei corsi di laurea on-line, oltre al
reperimento di appunti e lezioni in Internet, sarebbe anche possibile sostenere gli
esami senza necessariamente raggiungere la sede universitaria.
In ambito finanziario, sia per le operazioni di borsa sia per le vendite di prodotti via
Internet, la possibilità di riconoscere con certezza l‘utente collegato in un dato
momento assume una importanza vitale. Fino ad ora, questo tipo di servizi si limitava
a verificare che l‘utente collegato fosse in possesso di una data informazione
(password) o di un determinato oggetto (tesserino magnetico) e di una informazioni
ad esso associata (codice pin). Il livello di sicurezza offerto da questo tipo di
autenticazione si è dimostrato in più occasioni inadeguato.
Identificazione rapida di segnalazioni fotografiche (es.: criminali)
Interfacciamento uomo-macchina per le più svariate applicazioni interattive
Sono state svolte nei campi del riconoscimento e del rilevamento del volto,
moltissime ricerche negli ultimi anni. Molte ricerche però si basano su precise
precondizioni, e solo pochi sistemi sono stati utilizzati su ambienti reali per testare le
loro reali capacità [2].
1.1 Analisi problema
Il problema del riconoscimento del volto consiste nella verifica dell‘identità di un
individuo attraverso l‘analisi delle caratteristiche del suo viso. Il riconoscimento per
l‘uomo è un processo mentale istintivo, che avviene senza il minimo sforzo apparente.
Biologicamente ogni memorizzazione visiva consiste nell‘eccitazione di una ―traccia‖ di
neuroni della corteccia cerebrale. Ogni percezione visiva genera una nuova ―traccia‖ o ne
rafforza una esistente. Al ripresentarsi di uno stimolo visivo già memorizzato nel passato il
CAPITOLO 1: INTRODUZIONE
3
cervello recupera le informazioni (associazione immagine-entità) in maniera tanto più
rapida quanto più la traccia è rimasta impressionata sulla corteccia. Il cervello umano,
durante il riconoscimento, lavora per schemi associativi ed è proprio su questo che
l‘intelligenza artificiale si basa per tentare di riprodurre tale comportamento nelle
macchine. Per un sistema automatico il problema può essere schematizzato come segue:
data un‘immagine o una sequenza video, identificare uno o più soggetti presenti nella
scena utilizzando un database di volti [3]. Anche se per un uomo il problema sembra
banale non vale lo stesso per un sistema di riconoscimento. Innanzi tutto le immagini o i
video contengono numerosi fattori interferenti, quali: ampie variazioni cromatiche, angoli
di vista differenti e risoluzioni diverse [1]. Nella fattispecie del riconoscimento di un volto
le cose si complicano ulteriormente: il volto deve essere riconosciuto anche se l‘individuo
presenta una diversa pettinatura, porta gli occhiali, cambia espressioni, è voltato, non ha
più la barba, è illuminato diversamente, ecc.
Da un punto di vista tecnico il riconoscimento facciale non è altro che un particolare
problema di ―object recognition‖ nel quale gli oggetti da riconoscere presentano particolari
proprietà che li accomunano (es. posizione di occhi, bocca e naso) ed altre, più sottili, che
permettono di distinguerli (es. lineamenti e forma del viso).
1.2 Struttura tesi
Nel capitolo due viene analizzato il problema del riconoscimento del volto e vengono
discussi alcuni possibili approcci con i quali risolvere il problema.
Il capitolo tre offre una descrizione dettagliata delle reti neurali. Prima viene introdotta un
po‘ di storia delle reti neurali, successivamente vengono descritti i parametri fondamentali
delle reti, come le funzioni di attivazione, il tipo di apprendimento e il tipo di architettura
(ricorsiva e non). Infine vengono brevemente presentati alcuni tipi di reti neurali.
Il capitolo quattro offre una panoramica sulla logica fuzzy, con i concetti fondamentali, il
concetto di FIT, e il procedimento per trattare questo tipo di dati (fuzzificazione,
defuzzificazione). Viene inoltre presentata una veloce panoramica sui vantaggi e gli
svantaggi dei sistemi ibridi neuro-fuzzy.
CAPITOLO 1: INTRODUZIONE
4
Il capitolo cinque parla del sistema usato per il riconoscimento dei volti, con la struttura di
base e un approfondimento per ogni singolo passaggio.
Nel capitolo sei troviamo la parte relativa alla creazione del database di foto da usare per il
sistema descritto nel capitolo precedente.
Infine nel capitolo sette si riportano le conclusioni ed una discussione degli sviluppi futuri.
5
Capitolo 2
Tecniche di riconoscimento del volto
L‘uomo riesce a riconoscere un volto senza nessuno sforzo apparente, ma i calcoli eseguiti
dal sistema nervoso visivo sono enormemente complessi. Il problema apparentemente
banale di trovare e identificare un volto è il risultato di milioni di anni di evoluzione e noi
siamo ancora lontani dal comprendere appieno come il nostro cervello realizza questo
compito.
Ancora oggi non è stata trovata una soluzione completa che permetta un riconoscimento
automatico di un volto in un‘immagine.
In questo capitolo verranno mostrati i più comuni approcci utilizzati per risolvere questo
problema.
2. 1 Rappresentazione e confronto
Il successo nel riconoscimento del volto dipende dalla soluzione di due problemi:
rappresentazione e confronto.
A livello elementare, l‘immagine di un volto è un array bidimensionale di numeri che può
essere espresso in tre modi alternativi:
1. x = {xi, i S} dove S una griglia quadrata.
2. x = [x1,….xk]T dove x è un vettore colonna costituito da righe di pixel concatenate, n
è il numero totale di pixel nell‘immagine e quindi x è un punto nello spazio euclideo
n-dimensionale.
3. f(x) = [f1(x),….fm(x)]T dove f(x) è detto vettore di features e dove fm(x) sono funzioni
lineari o non lineari.
CAPITOLO 2: TENICHE DI RICONOSCIMENTO DEL VOLTO
6
Per una data rappresentazione sono importanti il potere discriminante, e l‘efficienza. Il
potere discriminante rappresenta la distanza tra rappresentazioni di volti diversi, mentre
l‘efficienza indica quanto è compatta la rappresentazione. E‘ importante notare che
un‘efficiente rappresentazione non ha necessariamente un buon potere discriminante.
La fase del confronto si occupa di rintracciare un volto candidato x nell‘insieme dei K
campioni ci . Ci sono molti metodi per comparare il nuovo volto con i campioni: calcolo
della distanza euclidea, calcolo della distanza di Mahalanobis, confronto basato su misure
di correlazione o di covarianza.
A causa di molti fattori, come ad esempio l‘illuminazione o l‘espressione del soggetto,
l‘immagine del volto di una persona può avere delle variazioni casuali e quindi può essere
modellata in maniera più corretta come un vettore random. In questo caso viene spesso
usato il confronto per somiglianza massima (ML maximum likelihood).
2.2 Principal Component Analysis PCA
PCA (Principal Component Analysis) è una delle tecniche maggiormente utili nei campi
del riconoscimento e della compressioni delle immagini. PCA è un metodo statistico il cui
scopo è la riduzione di un numero più o meno elevato di variabili in alcune variabili latenti,
che possiamo utilizzare per descrivere tutti i dati.
Una generica immagine I(x,y), può essere rappresentata sia da una matrice a due
dimensioni NxN, sia da un vettore monodimensionale di grandezza N 2 o in egual modo da
un punto in uno spaio di N2 dimensioni. Un insieme di immagini quindi può essere
mappato in un insieme di punti di questo enorme spazio. Tutte le immagini che contengono
un volto sono simili e quindi non sono distribuite casualmente in questo enorme spazio.
Sfruttando questa proprietà possiamo rappresentarle con una bassa percentuale di errore
adoperando un sub spazio con molte meno dimensioni. Questa è la principale idea
dell‘analisi delle componenti principali, che intende trovare dei vettori che rappresentano
nel miglior modo possibile le immagini dei volti all‘interno dell‘intero spazio delle
immagini. Questi vettori quindi definiranno un sottospazio chiamato ―spazio dei volti‖.
CAPITOLO 2: TENICHE DI RICONOSCIMENTO DEL VOLTO
7
Prendiamo in considerazione un insieme di immagini di volti x1, x2,…..xM di dimensione N
(N = larghezza x altezza immagine originale). Se indichiamo con pj il valore di un pixel
dell‘immagine, avremo che:
xi = [p1,…pN]T i=1,….M
Definiamo ora il volto medio come:
Ogni volto differisce dal volto medio di una quantità pari a wi = xi – m.
L‘obbiettivo di PCA è quello di trovare un insieme di M vettori ei che esprimano al meglio
la distribuzione delle immagini iniziali. Questi vettori devono essere ortonormali e devono
essere scelti in modo tale che la quantità
ortogonalità:
i
1
M
è massimizzata tenendo conto del vincolo di
M
(eiT wn )2
i 1
i
I vettori ei e gli scalari
i
1
M
M
(eiT wn )2
i 1
sono gli autovettori e autovalori della matrice di covarianza C =
WWT dove W è una matrice in cui le colonne sono i vettori wi. La grandezza di C è N x N
che potrebbe essere enorme. Anche per immagini estremamente piccole ad esempio 64x64
la matrice di covarianza avrebbe dimensioni 4096 x 4096, rendendo il problema del calcolo
degli autovettori intrattabile computazionalmente. Pertanto è necessario trovare un modo
più efficiente per trovare questi autovettori. Se il numero di immagini è molto più basso
delle dimensioni dello spazio delle immagini (M < N2) , ci saranno soltanto M-1
autovettori. I restanti autovettori saranno associati ad autovalori nulli. Fortunatamente è
possibile ottenere ei e
i
utilizzando gli autovalori e gli autovettori della matrice MTM che
ha grandezza M x M. Indicando con di e μi gli autovettori e gli autovalori della matrice
WTW sappiamo che: WTWdi = μidi. Moltiplicando entrambe le parti della precedente
equazione per W
WWT (Wdi) = μi(Wdi)
I primi M-1 autovettori ei e i relativi autovalori
i
di WWT possono essere calcolati quindi
rispettivamente da Wdi e μi. Wdi devono essere normalizzati per essere uguali a ei. In questo
modo abbiamo ridotto la quantità di calcoli, che prima era dell‘ordine di N (numero di
pixel dell‘immagine), all‘ordine del numero di immagini del training set. Gli autovettori
CAPITOLO 2: TENICHE DI RICONOSCIMENTO DEL VOLTO
8
trovati possono essere ordinati in modo decrescente a seconda gli autovalori ad essi
associati [4].
Gli autovettori ai quali sono associati gli autovalori più grandi sono quelli più utili nella
caratterizzazione delle immagini ed è possibile farne uso come base per descrivere le varie
immagini dei volti. Inoltre per avere una descrizione accurata delle immagini, che permetta
di attuare il riconoscimento, è sufficiente sfruttare un numero più basso di autovalori M‘,
utilizzando soltanto gli autovettori ai quali sono associati gli autovalori più grandi [4].
Ogni immagine viene trasformata nelle sue componenti, chiamate eigenface, attraverso una
semplice operazione:
vi
Il vettore dei pesi
eiT wi i con i = 1,.....,M‘.
= [v1,v2...vM‘ ]T descrive il contributo di ogni eigenface nella
rappresentazione dell‘immagine originale. Questo vettore viene utilizzato come pattern,
nell‘algoritmo di riconoscimento, per trovare a quale classe di volti appartiene l‘immagine
in ingresso.
Il metodo più semplice per trovare a quale classe di volti appartiene l‘immagine è quello di
trovare la classe k che minimizza la distanza euclidea
k
dove
k
|| (
k
) ||
è il vettore che descrive il k-esima volto. Se
k
è minore di una certa soglia
prefissata allora il volto in ingresso è classificato con la k-esima classe. Se per nessuna
lasse la distanza scende al di sotto della soglia allora il volto è classificato come
sconosciuto, e opzionalmente si può creare una nuova classe. Distanze molto grandi
indicano invece che l‘immagine presentata in input non è un‘immagine di un volto.
Riassumendo, l‘approccio PCA per il riconoscimento del volto, è composto da due fasi [5]:
• Inizializzazione del sistema:
1. Acquisire l‘insieme di immagini caratteristiche dei volti di individui
conosciuti. Questo insieme di deve includere un adeguato numero di immagini
per persone, con qualche variazione di luce e espressione.
CAPITOLO 2: TENICHE DI RICONOSCIMENTO DEL VOLTO
9
2. Calcolare a partire dalla matrice di WTW gli autovalori e autovettori della
matrice di covarianza. Scegliere M‘ autovettori ai quali sono associati gli
autovalori più grandi.
3. Per ogni individuo conosciuto calcolare il vettore di classe k. Scegliere
inoltre la soglia al disotto della quale un pattern è considerato della classe, e la
soglia con quale considerare un immagine non di un volto.
• Funzionamento del sistema:
1. Calcolare il vettore dei pattern.
2. Determinare se l‘immagine è un volto (conosciuto o no) controllando se
l‘immagine è sufficientemente chiusa nello spazio dei volti.
3. Se l‘immagine è un volto confrontare i pesi con quelli dei volti salvati per
trovare se la persona è conosciuta o no.
Il metodo più famoso il letteratura che applica gli eigenface è quello proposto
da Turk and Pendland [6], che si basa sull‘espansione di Karhunenmain.
Successivamente sono state proposte numerose ottimizzazioni del metodo,
utilizzabili in diverse applicazioni [7,8].
CAPITOLO 2: TENICHE DI RICONOSCIMENTO DEL VOLTO
10
Figura 2.1: Metodo PCA
2.3 Hidden Markov Model (HMM)
Questo modello, inizialmente usato per l‘analisi ed il riconoscimento di segnali vocali e di
testo, è stato applicato al dominio dei volti umani in [9]. I modelli HMM sono usati per
caratterizzare le proprietà statistiche di un segnale; per fare questo il modello HMM è
costituito da due processi indipendenti: una catena di Markov a stati finiti, un insieme di
densità di probabilità associate ad ogni stato della catena. Con l‘uso delle catene di Markov
per il processing delle immagini come fatto in [10], si è visto che le stesse possono essere
utili per processare anche immagini di volti umani, il tutto abbastanza velocemente.
Ogni catena di Markov è costituita da una serie di elementi: N numero degli stati del
modello, S è l‘insieme degli stati, S = {S1,S2,….SN}, M è il numero di simboli osservati.
CAPITOLO 2: TENICHE DI RICONOSCIMENTO DEL VOLTO
11
Se V è l‘insieme di tutti i possibili simboli (il codebook) allora V = {v1,v2,….vm}.
Possiamo esprimere una catena di Markov attraverso un tripla:
( A, B, )
dove A = (aij) è la matrice delle probabilità di transizione ed ogni suo elemento aij indica la
probabilità, per un certo istante, di passare dallo stato i, nell‘istante successivo, nello stato
j.
aij
con il vincolo che 0 ai , j
P[qt
S j | qt
N
1 e che
Si ],1 i, j
1
a
j 1 ij
1,1 i
N
N.
B = {bj(k)} è la matrice delle probabilità dei simboli osservati, in cui
b j (k )
con vincoli 1
j
N ,1 k
P | [Ot
vk | qt
Sj]
M , dove Ot è il simbolo osservato al tempo t.
è la distribuzione iniziale degli stati,
i
={
i
} dove
P[q1 Si ],1 i
N
Per le immagini frontali possiamo individuare cinque regioni facciali che sono
significative: i capelli, la fronte, gli occhi il naso e la bocca. Esse appaiono in quest‗ordine
analizzando un‘immagine dall‘alto in basso, ma appaiono sempre in quest‘ordine anche se
l‘immagine è ruotata. Ognuna di queste regioni è assegnata ad uno stato di una catena di
Markov monodimensionale. La struttura di questa catena è visibile nella successiva
immagine.
Estrazione feature In considerazione del fatto che ogni immagine ha una larghezza Q e
un‘altezza H, per l‘estrazione delle feature si divide l‘intera immagine in blocchi di altezza
L e larghezza W. I blocchi saranno sovrapposti di una grandezza P. il numero di blocchi
estratti da ogni singola immagine è pari a
T
H L
L P
1
CAPITOLO 2: TENICHE DI RICONOSCIMENTO DEL VOLTO
12
e la scelta di parametri P e L va fatta con molta attenzione perché influiscono pesantemente
sulla velocità di estrazione.
Figura 2.2: HMM per il riconoscimento facciale
Figura 2.3: Estrazione feature per il riconoscimento facciale con HMM
Training del modello Ogni elemento nel database iniziale di immagini è rappresentato da
un modello HMM associato (
( A, B, )) ed è inizializzato opportunamente. Si cercano i
coefficienti della catena massimizzando P(O | ) finché un certo valore di soglia C risulta
accettabile,
| P(O |
( k 1)
)
P(O |
(k )
)| C
Test riconoscimento con HMM Per associare un‘identità ad una nuova immagine, su cui
non è stato addestrato il sistema in precedenza, si deve valutare l‘equazione
P (O ( t )| k )
max n P(O ( t ) |
Dove t è la nuova immagine, e k è la faccia identificata.
n
CAPITOLO 2: TENICHE DI RICONOSCIMENTO DEL VOLTO
13
2.4 Riconoscimento attraverso reti neurali
Una rete neurale è formata da una serie di unità parallele di elaborazione, detti neuroni (o
nodi). Questi nodi sono interconnessi con dei rami che mutuano il funzionamento del
cervello degli esseri viventi, infatti i neuroni biologici sono interconnessi attraverso le
sinapsi. Nel caso dei neuroni artificiali, ad ogni connessione è associato un coefficiente, un
peso, per il quale viene moltiplicato il valore che attraversa quella connessione. Il
riconoscimento facciale attraverso reti neurali è stata una delle prime dimostrazioni
dell‘impiego pratico di reti neurali in [11] si dimostra come una semplice rete neurale
poteva essere addestrata a riconoscere un volto contenuto in un‘immagine normalizzata ed
allineata. Il tipo di rete adoperata in quell‘esempio ha analizzato una faccia a partire da una
sua rappresentazione compressa, attraverso cioè l‘uso degli auto vettori della matrice di
autocorrelazione dell‘immagine. Tale modalità di rappresentare un‘immagine in forma
sintetizzata è stata adoperata in altre analisi, che non coinvolgevano per forza le reti
neurali. Questi auto vettori, infatti, sono conosciuti col nome di ―eigenface‖ o auto facce,
nella versione italiana del termine, e sono usati da algoritmi come il PCA.
Il sistema di Kohonen, applicato a questo dominio, non ha avuto un successo pratico
immediato, a causa della necessità di quella implementazione di dover allineare
un‘immagine per normalizzarla. Nel capitolo successivo si analizzeranno varie tipologia di
reti neurali, e per questo, se ne rinvia a quelle pagine una descrizione più approfondita.
14
Capitolo 3
Reti Neurali
I sistemi di elaborazione dell‘informazione anno portato l‘automazione nei processi che
sono stati per molti anni di esclusiva pertinenza degli umani, ad esempio la conservazione
di documenti o il calcolo matematico. Con l‘intelligenza artificiale si tende a spingere oltre
i limiti delle sole operazioni ripetitive, rendendo possibile l‘automazione del ragionamento
simbolico e la creazione di sistemi esperti, che sono in grado, cioè, di sostituirsi a provati
esperti del settore nel caso in cui si debba risolvere un problema.
Nonostante queste interessanti applicazioni, ancora molto deve essere fatto affinché le
macchine esprimano un comportamento paragonabile a quello di un umano. La mente
umana è infatti il frutto di un processo evolutivo durato migliaia di secoli e replicare
l‘esatto funzionamento del cervello, usando modelli matematici di calcolo simbolico, è
abbastanza difficile. Ci sono una serie di casi in cui l‘uso di algoritmi classici, basati
sull‘elaborazione
simbolica,
risultano
poco
adatti.
Pensiamo,
ad
esempio,
al
riconoscimento del testo o all‘estrazione automatica di semantica da un documento.
Per questi ed altri problemi non è facile associare, attraverso un algoritmo, un significato e,
quindi, una caratterizzazione simbolica ad un particolare ingresso. Per questo, sono stati
introdotti modelli di calcolo che non sono necessariamente basati sul concetto di algoritmo,
come sequenza di elaborazione simbolica degli ingressi. Per alcuni compiti specifici questo
approccio classico risulta complicato da realizzare, se non impossibile.
Per l‘architettura delle reti neurali artificiali si è preso spunto dalla natura, dove l‘unità
base che costituisce il sistema nervoso centrale di un essere vivente è il neurone. Sebbene il
funzionamento del cervello nel suo insieme ancora sia oggetto di studi, anatomicamente si
conosce già la struttura dell‘encefalo. Il componente fondamentale è appunto il neurone
che, attraverso dei processi elettrochimici è in grado di generare segnali elettrici.
Il neurone è composto da un corpo principale, detto soma, e due rami, i dendriti e l‘assone.
In un cervello umano ci sono più di100 miliardi di neuroni, ciascuno connesso a circa altri
CAPITOLO 3: RETI NEURALI
15
10.000. Nelle interconnessioni che ogni cellula neuronale ha avviene la sinapsi, che è un
processo elettrochimico che rinforza o inibisce l‘interazione cellulare tra i due neuroni che
la condividono. Questi segnali elettrici sono perfettamente rilevabili e misurabili attraverso
l‘uso di opportune strumentazioni e. secondo molti studiosi di scienze cognitive, sarebbero
proprio questi segnali il segreto della capacità cognitiva. Inoltre, vari esperimenti hanno
evidenziato come le strutture cerebrali e le sinapsi siano influenzate dalle esperienze del
soggetto e dell‘ambiente in cui vive: è quindi la particolare architettura dei legami e delle
interconnessioni tra le cellule cerebrali che definisce le capacità funzionali di porzioni di
cervello.
3.1 Storia delle reti neurali
La ricerca sulle reti neurali artificiali cominciò negli anni ’40, ispirata da considerazioni
sulla fisiologia del cervello umano [12].
Nel 1943 Warren Mc-Culloch e Walter Pitts introdussero il primo modello per il neurone
artificiale, basato su assunzioni che permettevano di costruire elementi propri dei circuiti
logici quali AND e OR. Le assunzioni di Mc-Culloch e Pitts si possono riassumere in una
serie di semplici proposizioni:
Un neurone è un circuito a scatto che può essere o attivo o inattivo;
Ciascun neurone ha una determinata tensione di soglia;
Un neurone riceve input da sinapsi eccitatrici dello stesso peso;
Un neurone riceve input addizionale da sinapsi inibitrici con un effetto "tutto nulla": una sola sinapsi può inibire l'attivazione del neurone;
Vi è un intervallo di tempo finito per il processing del segnale d'ingresso; se
non vi è alcuna sinapsi inibitrice attiva, gli ingressi eccitatori sono sommati fra
loro e il neurone diventa attivo se la somma eccede la tensione di soglia.
CAPITOLO 3: RETI NEURALI
16
In realtà il neurone di Mc-Culloch e Pitts corrisponde ad un neurone naturale in maniera
molto limitata. Vi sono vari aspetti fisiologici che non sono presi in considerazione. Il
neurone è una piccola stazione elettrochimica: nello stato di riposo mantiene sulla sua
membrana una tensione di –70mV. Ciò è causato dalla concentrazione degli ioni sodio che
è 10 volte più alta fuori dal neurone che dentro di esso. Se il neurone è attivato cresce la
permeabilità della membrana cellulare agli ioni sodio, che fluiscono dentro la cellula. Allo
steso tempo ioni potassio fluiscono fuori dalla cellula. Per un millisecondo l‘interno della
cellula diviene positivo (raggiunge una tensione di +40mV) rispetto all‘ambiente
circostante. Dopo che l'energia è stata consumata gli ioni sodio sono rimossi dall‘interno
della cellula. Nell‘assone avviene un processo simile.
Inoltre il neurone di Mc-Culloch e Pitts non è in grado di spiegare il meccanismo grazie al
quale il sistema nervoso umano è in grado di apprendere e ragionare.
Fig. 3.1: Il neurone di McCulloch e Pitts
Le prime idee a questo riguardo furono formulate nel 1949 da Donald O. Hebb, il quale
postulò che il processo d'apprendimento rafforza le connessioni fra due neuroni se il
neurone pre-sinaptico e quello post-sinaptico sono attivi contemporaneamente. Questo
meccanismo è noto con il nome di "plasticità sinaptica" e, nell‘ambito delle moderne teorie
sulla natura neurofisiologica dell‘apprendimento, è un modello universalmente accettato.
Negli anni ‘50 e ‘60 si arrivò allo sviluppo delle prime reti neurali artificiali con la capacità
di apprendere nel senso indicato da Hebb. Il modello di neurone usato era il "percettrone",
introdotto da Frank Rosemblatt nel 1958. Le unità di processing erano simili al neurone di
Mc-Culloch e Pitts, mentre le sinapsi erano costituite da connessioni di diverso peso, che
poteva essere cambiato durante il processo d'apprendimento. Per questo tipo di reti si può
provare che il processo d'apprendimento conduce ad un successo se la soluzione del
CAPITOLO 3: RETI NEURALI
17
relativo problema sussiste in una ben determinata forma (teorema di convergenza per il
percettrone)
Nel 1960 Bernard Widrow e Marcian Hopf svilupparono il modello ADALINE (Adaptive
Linear Neuron). Come il percettrone questo è in grado di imparare ad eseguire
classificazioni su insiemi di dati omogenei sulla base di una regola d'apprendimento
denominata "delta rule".
In realtà i due modelli citati consistono di un singolo strato di neuroni con ingressi multipli
pesati e un solo output. Il neurone computa le somme pesate degli input e sulla base di
questo calcola il suo valore di attivazione. E‘ poi semplice estendere il modello ad un
modello a due strati, nel quale il primo strato ha l‘unico scopo di raccogliere una serie di
valori e di propagarla verso lo strato di uscita.
Fu nel 1969 che Marvin Minsky e Seymour Papert mostrarono che il modello ad uno strato
non è capace di risolvere problemi che appartengono alla classe dei problemi "non
separabili", della quale è un esempio significativo il problema di implementare la funzione
XOR. Furono questi due autori che mostrarono che a questo scopo è necessario almeno
uno strato nascosto di neuroni. Inoltre essi mostrarono che il percettrone è formalmente
equivalente al calcolo di un predicato logico e svilupparono un'analisi esauriente relativa ai
problemi delle reti neurali su questa base. Fu grazie a loro che si fece un grosso passo
avanti nello stabilire quali problemi sono solubili da parte di una rete neurale e quali no.
Allo stato attuale delle ricerche gli studi più attuali e significativi sono dovuti a David E.
Rumelhart, Geoffrey E. Hinton e Ronald J. Williams che (1986) estesero la "delta rule" di
Widrow e Hopf ai percettroni multistrato con funzioni di attivazione continue e
differenziabili, sviluppando il metodo di apprendimento detto della "backpropagation".
Questo consiste nel propagare l‘errore relativo ad un certo target che la rete produce in
output a ritroso, usandolo per aggiustare i pesi della rete neurale.
CAPITOLO 3: RETI NEURALI
18
3.2 Struttura di un nodo, funzioni di attivazione
Il neurone Artificiale è il modello matematico semplificato del neurone biologico. La sua
struttura base (detta nodo) è l‘unita di calcolo elementare nelle reti neurali. Il
funzionamento è piuttosto semplice, e viene descritto dalla seguente figura.
Fig. 3.2: Struttura di un nodo base
Come si evince, ciascuna unità esegue una computazione semplice: riceve i segnali dai
suoi collegamenti di ingresso e calcola un nuovo livello di attivazione che invia lungo tutti
i suoi collegamenti di uscita. Il calcolo del livello di attivazione è basato sul valore di
ciascuno dei segnali di ingresso ricevuti dai nodi vicini e sui pesi (indicati con la lettera w)
di ciascuno dei collegamenti di ingresso. Il calcolo è suddiviso tra due componenti. In
primo luogo una componente lineare, chiamata funzione di ingresso calcola la somma
pesata dei valori d'ingresso del nodo. In secondo luogo una componente non lineare
chiamata funzione di attivazione (indicata spesso con la lettera g), trasforma la somma
pesata nel valore finale che funge da valore di attivazione per l'unità (indicato con a). In
genere tutti i nodi di una rete utilizzano la stessa funzione di attivazione.
L‘ingresso pesato totale è dato dalla somma dei prodotti delle attivazioni in ingresso
(indicate con la lettera x) per i rispettivi pesi (indicati con w):
n
I
wi xi
i 1
Ad ogni passo elementare di calcolo, ciascuna unità calcola il suo nuovo valore di
attivazione applicando la funzione di attivazione g al risultato ottenuto per la funzione di
ingresso.
CAPITOLO 3: RETI NEURALI
19
Usando funzioni diverse come g si possono ottenere modelli differenti. Tre scelte comuni
sono la funzione a gradino, la funzione di segno e la sigmoide. La funzione a gradino ha
una soglia t tale che il risultato è 1 quando l‘ingresso supera questa soglia ed è 0 altrimenti.
La motivazione biologica è che 1 rappresenta l‘emissione di un impulso lungo l‘assone
mentre uno 0 rappresenta l‘assenza di una tale emissione. La soglia individua l‘ingresso
pesato minimo che fa in modo che il neurone invii l‘impulso. Si possono definire versioni
dotate di soglia anche per le funzioni di segno e sigmoidale.
In molti casi risulta più conveniente sostituire la soglia con un peso d‘ingresso extra.
Questo consente di avere un elemento di apprendimento più semplice in quanto ci si deve
preoccupare solo di modificare dei pesi piuttosto che modificare anche le soglie. Quindi
invece di avere una soglia t, si considera per ciascun nodo un ingresso aggiuntivo, la cui
attivazione è fissata a -1. Il peso extra associato ricopre il ruolo della soglia t; in questo
modo tutte le unità possono avere una soglia fissata a 0.
Fig 3.3: funzioni di attivazione classiche
3.3 Tipi di architettura
Esiste una notevole varietà di strutture possibili per le reti, ciascuna delle quali conduce a
proprietà computazionali molto diverse. La prima distinzione da fare è quella tra reti
alimentate in avanti e ricorrenti. In una rete alimentata in avanti i collegamenti sono
unidirezionali e non ci sono cicli. In una rete ricorrente i collegamenti possono formare
CAPITOLO 3: RETI NEURALI
20
configurazioni arbitrarie. Da un punto di vista tecnico una rete alimentata in avanti è un
grafo diretto aciclico. In genere avremo a che fare con reti organizzate in strati.
In una rete alimentata in avanti stratificata ciascuna unità è connessa unicamente a unità
dello strato successivo: non ci sono collegamenti tra unità di uno stesso strato né
all'indietro verso uno strato precedente, e inoltre non ci sono collegamenti che saltano uno
strato.
Fig. 3.4: Esempio di rete a 3 strati
La figura mostra un esempio molto semplice di rete alimentata in avanti stratificata. Questa
rete ha due strati. Poiché le unità di ingresso (nodi in) servono semplicemente a passare le
attivazioni allo strato successivo, essi non sono considerati nel conto (anche se alcuni
autori attribuirebbero a questa rete tre strati). L'assenza di cicli e significativa perché
implica che la computazione può procedere uniformemente dalle unità di ingresso alle
unità di uscita. Le attivazioni in intervalli di tempo precedenti non svolgono alcun ruolo
nel calcolo in quanto non vengono inviate all'indietro. Una rete alimentata in avanti,
quindi, si limita semplicemente a calcolare una funzione dei valori di ingresso che dipende
dalla distribuzione dei pesi — non ha alcuno stato interno diverso dai pesi stessi. Tali reti
possono implementare versioni adattive di semplici agenti con riflessi o possono servire
come componenti in agenti più complessi.
Ovviamente il cervello non può essere una rete alimentata in avanti in quanto in questo
caso non avremmo memoria a breve termine. Alcune regioni del cervello sono largamente
CAPITOLO 3: RETI NEURALI
21
alimentate in avanti e in qualche modo stratificate, ma ci sono anche delle evidenti
connessioni all'indietro. Nella nostra terminologia, il cervello è una rete ricorrente. Poiché
l'attivazione viene ripassata indietro alle unità che l'hanno provocata, le reti ricorrenti
hanno uno stato interno immagazzinato sotto forma di livelli di attivazione delle unità.
Questo significa che la computazione tende ad essere molto meno ordinata che nelle reti
alimentate in avanti. Le reti ricorrenti possono diventare instabili, oscillare o comportarsi
in modo caotico. Dati dei valori di ingresso può servire molto tempo per calcolare un'uscita
stabile e l'apprendimento e reso molto più difficile. D'altro canto le reti ricorrenti possono
implementare agenti più complessi e possono modellare sistemi dotati di stato.
Riguardo alle reti alimentate in avanti, c'è un'altra importante distinzione da fare. Si
esamini la figura 1, che mostra la topologia di una rete neurale molto semplice. In basso ci
sono le unità di input. Il valore di attivazione di ciascuna di esse è determinato
dall'ambiente. In alto nella rete c'e un'unità di output. Tra di esse i nodi nel livello centrale
non hanno connessioni dirette con l'esterno. Questi sono chiamati unità nascoste, perché
non possono essere osservati direttamente tenendo sotto controllo il comportamento di
input/output della rete. Alcune reti, per esempio i percettroni, non hanno unità nascoste.
Questo significa da un lato che l'apprendimento diventa un problema molto più semplice e
dall'altro che i percettroni sono molto limitati in ciò che possono rappresentare. Le reti con
uno o più strati di unità nascoste sono chiamate reti multistrato. Con uno strato
sufficientemente grande di unità nascoste si può rappresentare qualsiasi funzione continua
degli ingressi. Con due strati si possono rappresentare anche funzioni discontinue.
Con una struttura fissa e funzioni di attivazione g fissate le funzioni rappresentabili da una
rete alimentata in avanti sono limitate ad avere una specifica struttura parametrizzata. I pesi
scelti per la rete definiscono quale di queste funzioni è effettivamente rappresentata. Si
osservi che poiché le funzioni di attivazione g sono non lineari, l'intera rete rappresenta una
complessa funzione non lineare. Se si pensa ai pesi come a parametri o coefficienti di
questa funzione allora l'apprendimento diventa semplicemente un processo di
aggiustamento dei parametri in modo da farli corrispondere ai dati nell'insieme di
addestramento — un procedimento che gli statistici chiamano regressione non lineare. Da
un punto di vista statistico questo è quello che le reti neurali fanno.
In base alla configurazione delle connessioni di rete, le diverse architetture possono essere
raggruppate in due classi:
CAPITOLO 3: RETI NEURALI
22
le reti ad alimentazione in avanti (feed-forward) in cui il grafo non contiene
spire formate con rami di ritorno all‘indietro;
le reti ricorrenti con reazione (recurrent or feedback) in cui si formano spire di
reazione a causa di connessioni orientate all‘indietro.
Diversi modi di collegare a rete i neuroni, cioè connettività diverse, corrispondono
comportamenti di rete diversi.
In generale si può dire che le reti feed-forward sono statiche nel senso che esse forniscono
solo un insieme di valori di uscita piuttosto che una sequenza di valori per un dato
ingresso. Queste reti danno una risposta che è indipendente dallo stato precedente
all‘applicazione del segnale di ingresso, in un certo senso si può quindi dire che non hanno
memoria del loro stato (non però del loro approfondimento, come si vedrà).
Viceversa le reti feedback sono sistemi dinamici. Quando si presenta una nuova
configurazione del segnale di ingresso, le uscite dei neuroni vengono calcolate tenendo
conto dei cammini di reazione. Questi contribuiscono a modificare gli ingressi dei neuroni
il che conduce la rete ad assumere un nuovo stato.
Non necessariamente il progettista di una rete neurale deve diventare un teoricomatematico di queste reti, perché la conoscenza sperimentale operativa dei pro e dei contro
relativi alle differenti architetture, può aiutare a scegliere quella più adatta a risolvere lo
specifico problema che interessa.
Il modo in cui i neuroni vengono connessi a rete è però strettamente correlato all‘algoritmo
di apprendimento da usare per addestrare la rete. Differenti architetture richiedono
algoritmi di apprendimento differenti perché gli insiemi dei pesi che risolvono un dato
problema sono generati seguendo l‘algoritmo di apprendimento.
Il modello di rete ad alimentazione in avanti più famoso è senz'altro il percettrone (o
Perceptron)
I modelli più noti di reti ricorrenti con reazione sono le Reti di Hopfield e le macchine di
Boltzmann.
CAPITOLO 3: RETI NEURALI
23
3.4 Tipi di apprendimento
Vi sono tre grandi paradigmi di apprendimento, ciascuno corrispondente ad un particolare
compito astratto di apprendimento. Si tratta dell'apprendimento supervisionato,
apprendimento non supervisionato e l'apprendimento per rinforzo. Di solito un tipo di
architettura di rete può essere impiegato in uno qualsiasi di tali compiti.
Apprendimento Supervisionato (supervised learning): qualora si disponga di un
insieme di dati per l'addestramento (o training set) comprendente esempi tipici
d'ingressi con le relative uscite loro corrispondenti: in tal modo la rete può imparare
ad inferire la relazione che li lega. Successivamente, la rete è addestrata mediante un
opportuno algoritmo (tipicamente, la backpropagation che è appunto un algoritmo
d'apprendimento supervisionato), il quale usa tali dati allo scopo di modificare i pesi
ed altri parametri della rete stessa in modo tale da minimizzare l'errore di previsione
relativo all'insieme d'addestramento. Se l'addestramento ha successo, la rete impara a
riconoscere la relazione incognita che lega le variabili d'ingresso a quelle d'uscita, ed
è quindi in grado di fare previsioni anche laddove l'uscita non è nota a priori; in altri
termini, l'obiettivo finale dell'apprendimento supervisionato è la previsione del valore
dell'uscita per ogni valore valido dell'ingresso, basandosi soltanto su un numero
limitato di esempi di corrispondenza (vale a dire, coppie di valori input-output). Per
fare ciò, la rete deve essere infine dotata di un'adeguata capacità di generalizzazione,
con riferimento a casi ad essa ignoti. Ciò consente di risolvere problemi di
regressione o classificazione.
Apprendimento non Supervisionato (unsupervised learning): basato su algoritmi
d'addestramento che modificano i pesi della rete facendo esclusivamente riferimento
ad un insieme di dati che include le sole variabili d'ingresso. Tali algoritmi tentano di
raggruppare i dati d'ingresso e di individuare pertanto degli opportuni cluster
rappresentativi dei dati stessi, facendo uso tipicamente di metodi topologici o
probabilistici. L'apprendimento non supervisionato è anche impiegato per sviluppare
tecniche di compressione dei dati.
Apprendimento per rinforzo (reinforcement learning): Un opportuno algoritmo si
prefigge lo scopo di individuare un certo modus operandi, a partire da un processo
d'osservazione dell'ambiente esterno; ogni azione ha un impatto sull'ambiente, e
CAPITOLO 3: RETI NEURALI
24
l'ambiente produce una retroazione che guida l'algoritmo stesso nel processo
d'apprendimento. Tale classe di problemi postula un agente, dotato di capacità di
percezione, che esplora un ambiente nel quale intraprende una serie di azioni.
L'ambiente stesso fornisce in risposta un incentivo o un disincentivo, secondo i casi.
Gli algoritmi per il reinforcement learning tentano in definitiva di determinare una
politica tesa a massimizzare gli incentivi cumulati ricevuti dall'agente nel corso della
sua esplorazione del problema. L'apprendimento con rinforzo differisce da quello
supervisionato poiché non sono mai presentate delle coppie input-output di esempi
noti, né si procede alla correzione esplicita di azioni sub-ottimali. Inoltre, l'algoritmo
è focalizzato sulla prestazione in linea, la quale implica un bilanciamento tra
esplorazione di situazioni ignote e sfruttamento della conoscenza corrente.
Il sistema di reti neurali che verrà presentato nel capitolo cinque usa l’apprendimento
supervisionato, quindi riteniamo opportuno approfondire ulteriormente la tecnica di
backpropagation nel paragrafo successivo.
3.5 Backpropagation
Questa tecnica si basa sulla valutazione dell‘errore commesso dalla rete neurale in
funzione dei parametri della rete stessa e sulla sua diminuzione tramite una modifica dei
parametri operata nella direzione del gradiente della funzione errore. Per via della necessità
di calcolare il gradiente della funzione calcolata dalla rete neurale, tale tecnica può essere
utilizzata solo se la funzione di attivazione dei neuroni è derivabile rispetto ai parametri da
configurare [13].
L‘algoritmo modifica i parametri di configurazione in base al contributo che essi danno
alla diminuzione dell‘errore. A ogni passo di apprendimento, si presenta un esempio agli
ingressi della rete neurale, si calcola la relativa uscita prodotta dalla rete, e la si confronta
con il valore di uscita atteso. La differenza tra il valore di uscita dell‘esempio e il valore di
risposta della rete neurale costituisce l‘errore commesso dalla rete stessa. Procedendo a
ritroso dall‘uscita della rete verso i neuroni più interni, si calcola il gradiente dell‘errore
CAPITOLO 3: RETI NEURALI
25
rispetto ai parametri dei neuroni considerati e lo si utilizza per modificare i parametri stessi
in modo da far diminuire l‘errore.
Per esempio, si consideri una rete feed-forward multistrato a due strati nascosti per
l‘approssimazione di una funzione reale definita sull‘insieme dei numeri reali (quindi, con
un neurone di ingresso ed uno di uscita). L‘insieme di addestramento sarà composto da un
insieme di coppie di numeri reali, (xi, yi) , quale descrizione del comportamento di tale
funzione. Il neurone dello strato di ingresso funge da distributore del valore presentato in
( 0)
ingresso e ha funzione di attivazione lineare ( S1
x ). L‘uscita dei neuroni del primo
strato sarà:
S (1)
j
f (1)
wk(1) x
(1)
j
k
Tali valori costituiscono l‘ingresso del secondo strato nascosto, che fornirà in uscita:
Si(2)
f (2)
(1)
wi(2)
,j Sj
(2)
i
j
Infine, lo strato finale (per semplicità un neurone lineare) produrrà l’uscita della rete
neurale:
wi(3) Si(2)
y
i
La presentazione alla rete dell‘esempio (x,y) comporta un errore di approssimazione E pari
a
E
y
~
y
2
L‘errore viene usualmente calcolato utilizzando il quadrato della distanza tra l‘uscita attesa
e l‘uscita reale in modo da ottenere un valore indipendente dal segno e facilmente
derivabile.
L‘algoritmo di backpropagation, sfruttando la proprietà della derivata di funzioni
composte, aggiorna i pesi sinaptici con le seguenti regole:
wi(3)
E
wi(3)
E y
y wi(3)
CAPITOLO 3: RETI NEURALI
wi(2)
,j
w(1)
j
26
E y Si(2)
y Si(2) wi(2)
,j
E
wi(2)
,j
E
w(1)
j
(1)
E y Si(2) S j
y Si(2) S (1)
w(1)
j
j
Dove η è il fattore di adattamento (o tasso di apprendimento) che controlla la velocità con
cui si cerca di discendere verso il minimo dell‘errore. Analoghe formule possono essere
derivate per gli altri parametri della rete (per esempio per le soglie) [14].
L‘algoritmo di backpropagation soffre di alcuni problemi. Il più grave è l‘incapacità di
riuscire a evitare i minimi locali della funzione errore. Quando si verifica questa
situazione, si ha che piccole variazioni dei parametri fanno aumentare l‘errore, mentre una
variazione dei parametri di ampia entità consentirebbe di diminuirlo, ma il valore di η
adottato non consente di spostarsi a sufficienza. Inoltre, l‘algoritmo di backpropagation
non dà garanzie sul numero di iterazioni necessarie per giungere nel minimo dell‘errore.
Per questi motivi, sono generalmente adottate alcune varianti dell‘algoritmo di
backpropagation, quali il simulated annealing e l‘uso dei momenti. Il simulated annealing
prende il nome da una tecnica utilizzata in metallurgia, che consiste nel riscaldare un
metallo e poi raffreddarlo seguendo una ben determinata curva di raffreddamento che
consente di orientare i cristalli in maniera ottimale. Nell‘algoritmo di backpropagation, il
simulated annealing consiste nell‘aggiungere nella funzione errore un termine casuale che
la renda priva di minimi locali all‘inizio dell‘addestramento. Il valore di questo termine si
riduce progressivamente con il procedere dell‘addestramento, facendo emergere pian piano
la vera forma dell‘errore.
L‘ipotesi su cui si fonda questa tecnica è che il minimo globale emerga prima degli altri
minimi e che la rete riesca a individuarlo prima che emergano gli altri minimi locali. Lo
svantaggio principale è il notevole incremento del costo computazionale. La tecnica dei
momenti consiste nell‘aggiungere un termine moltiplicativo al tasso di apprendimento, η,
in modo che quest‘ultimo aumenti se si sta seguendo un percorso che riduce l‘errore, ma
che diminuisca se invece l‘errore tende a crescere.
CAPITOLO 3: RETI NEURALI
27
3.6 Tipi di rete
Nei prossimi paragrafi verranno ora presentati alcuni tipi fondamentali di reti neurali: il
percettrone (modello base), la SOM, la GNG e la LVQ (il tipo di rete utilizzata nel nostro
sistema, in una delle sue varianti). Infine verrà presentato un paragrafo relativo alle reti
neurali modulari.
3.6.1 Percettrone
Il percettrone è un caso particolare di rete neurale, in cui una qualsiasi uscita della rete è
completamente indipendente dalle altre perché ciascun peso influenza solo uno degli
output. Questa caratteristica rende una rete neurale basata sui percettroni di ―semplice‖
analisi. Nella figura successiva viene mostrato un esempio di rete a singolo strato; si può
osservare come ogni uscita sia calcolata indipendentemente dalle altre, infatti non esistono
archi (e dunque pesi) che legano la computazione di un‘uscita ad un‘altra.
Fig. 3.5: reti di percettroni
Le funzioni di trasferimento dei vari nodi sono funzioni a gradino, di conseguenza ogni
singolo percettrone può produrre in uscita solo due valori: 0 e 1. Le unità elementari
possono facilmente rappresentare le funzioni booleane semplici AND, OR e NOT. Per
poter rappresentare funzioni più complesse, per esempio lo XOR, un singolo percettrone
CAPITOLO 3: RETI NEURALI
28
non è sufficiente, ma bisogna affidarsi ad una rete multistrato ottenuta mettendo in cascata
più percettroni.
L‘addestramento di queste reti è un addestramento supervisionato. Esiste un algoritmo per
percettrone in grado di apprendere qualsiasi funzione linearmente separabile a condizione
che gli vengano forniti abbastanza esempi di prova. Inizialmente la rete ha dei pesi
assegnati; essa viene quindi aggiornata nel tentativo di renderla consistente con gli esempi
attraverso piccole modifiche dei pesi, in modo da ridurre la differenza tra i valori previsti e
quelli effettivamente misurati, finché non si ottiene la convergenza alla soluzione corretta.
Generalmente il processo d‘apprendimento (quindi l‘aggiornamento dei pesi) viene
suddiviso in epoche, nelle quali si aggiornano tutti i pesi tenendo conto di tutti gli esempi
forniti all‘algoritmo d‘apprendimento. Per i percettroni la regola d‘apprendimento è
abbastanza semplice: viene di fatto calcolato l‘errore come differenza tra il valore
auspicato per il singolo esempio e il valore realmente calcolato dal percettrone e riportato
in output:
Errore (E) = Valore corretto (T) – Output percettrone (Y)
Se l‘errore E è positivo, l‘algoritmo di apprendimento deve far crescere Y, viceversa se E è
negativo. Esiste un teorema che ci assicura che se il problema è risolvibile da un
percettrone allora questo algoritmo condurrà alla soluzione in un numero finito di passi.
3.6.2 SOM
La rete SOM (Self Organizing Maps) è un tipo di rete sviluppata da Teuvo Kohonen nel
1982 [15]. In questo tipo di rete l‘apprendimento non è supervisionato, quindi non bisogna
conoscere a priori le classi in uscita (sarà la rete, dopo essere stata addestrata, a dirci a
quale cluster appartiene l‘input). Topologicamente questa rete si caratterizza per uno
schema a due strati, uno di input ed uno di output (quest‘ultimo comunemente chiamate
strato di Kohonen). I neuroni dei due strati sono completamente connessi fra loro, mentre i
neuroni dello strato di output sono connessi ciascuno con un ―vicinato‖ di neuroni, secondo
un sistema di inibizione laterale definito a ―cappello messicano‖.
CAPITOLO 3: RETI NEURALI
29
Fig. 3.6: cappello messicano
Le interazioni laterali intorno al neurone vincitore sono funzioni della distanza: si eccitano
i neuroni più vicini, si inibiscono quelli più lontani.
Anche se esistono versioni più complesse, nella versione più semplice c‘è un solo vincitore
e l‘apprendimento è di tipo competitivo. Il vincitore è il nodo che risulta avere il suo
vettore dei pesi più simile al vettore in ingresso; questa modalità di scegliere il nodo
vincitore è nota con il nome di winner takes all. Nella fase di addestramento, una volta
scelto il vincitore, si regolano i pesi per avvicinarli ancora di più al vettore in ingresso. Le
SOM a differenza delle altre reti adottano una funzione di contorno per preservare le
proprietà topologiche dello spazio dei dati input.
La SOM definisce un mapping dallo spazio dei dati di input x1…xn ad un array
monodimensionale o bidimensionale di nodi. Il mapping è eseguito in modo che la
relazione topologica nello spazio n-dimensionale di ingresso si mantiene constante quando
associata alla SOM. Inoltre, la densità locale dei dati in ingresso si riflette anche sulla
mappa: le zone dello spazio dei dati in input che sono rappresentati da più informazioni
vengono mappati su una maggiore superficie della SOM.
CAPITOLO 3: RETI NEURALI
30
Fig. 3.7: Architettura SOM
Ogni nodo sulla mappa è definito da un vettore di pesi wij che è modificato durante la fase
di training, che è molto semplice e si riduce ai seguenti passi:
1.
Si selezione un oggetto dal training-set
2.
Si trova il nodo che è più vicino ai dati, ad esempio usando la distanza tra il wij e il
vettore in ingresso
3.
Si regolano i vettori dei pesi del nodo vincitore e dei nodi che rientrano nel suo
vicinato, in modo che il suo wij si muova verso il dato in ingresso
4.
Si ripete dal passo 1 per un numero prefissato di passi. In ogni passo però si riduce
sia il tasso di apprendimento sia la dimensione del vicinato (bolla).
3.6.3 Growing Neural Gas (GNG)
L‘algoritmo GNG, pubblicato da Bern Fritzke nel 1994 [16], è un algoritmo di clustering
non supervisionato competitivo. Dati in input una serie di dati distribuiti in Rn, GNG in
modo incrementale crea un grafo, o rete di nodi, distribuiti anch‘essi in R n. GNG può
essere utilizzato oltre che per la clusterizzazione dei dati, anche per trovare la struttura
topologica dei dati presentati in ingresso. E‘ anche capace di adattarsi a piccoli
cambiamenti nella distribuzione dei dati che possono verificarsi nel tempo, muovendo i
suoi nodi in modo da rappresentare la nuova distribuzione.
CAPITOLO 3: RETI NEURALI
31
L‘algoritmo è suddiviso in tre fasi principali, l’addestramento (o inizializzazione), la fase
di presentazione e la fase di valutazione.
Fase di inizializzazione: In questa fase viene inizializzata la rete e vengono settati i
parametri dell‘addestramento.
Costruzione di un elenco che contiene i nomi (indici) delle unità di categorizzazione
presenti nella rete in ogni dato istante. Inizialmente ci sono due unità.
Assegnazione casuale a queste unità di vettori di pesi delle connessioni. Questi
vettori contengono tanti elementi quanti sono gli elementi contenuti nei vettori di
ingresso che verranno mostrati alla rete nella fase di addestramento.
Ad ogni unità di categorizzazione viene assegnato un valore numerico chiamato
errore locale inizialmente posto a 0.
Scelta della durata dell‘apprendimento T e di un sottomultiplo n di T. Dopo n
presentazioni si controlleranno gli errori locali delle varie unità di categorizzazione e
si deciderà se incrementare il loro numero.
Scelta del fattore di apprendimento dei pesi che fanno capo all‘unità vincitrice in
corrispondenza di un particolare esempio di addestramento.
Scelta del fattore di apprendimento dei pesi che fanno capo alle unità che sono in
relazione di vicinato con l‘unità vincitrice in corrispondenza di un particolare
esempio di addestramento.
Scelta di un parametro amax, ovvero della massima età di una relazione di vicinato,
oltre la quale tale relazione viene cancellata.
Scelta del tasso di diminuzione dell‘errore locale accumulato dalle unità di
categorizzazione quando la relazione di vicinato tra loro viene modificata inserendo
una nuova unità.
Scelta del tasso di diminuzione dell‘errore locale accumulato da tutte le unità
presenti al termine di ogni singolo passo di apprendimento.
Fase di funzionamento: inizialmente si calcola il numero totale di epoche di
apprendimento e per ognuna di queste epoche si hanno due sotto fasi [16]:
CAPITOLO 3: RETI NEURALI
32
Fase di presentazione: vengono presentati gli elementi che fanno parte del training
set e per ognuno di questi elementi si calcolano le distanze euclidee tra il vettore v
(pattern in ingresso) e i singoli vettori dei pesi delle varie unità di categorizzazione
presenti i quel momento. Successivamente si ordineranno in modo crescente queste
unità a seconda della rispettiva distanza euclidea calcolata. Se esiste una relazione di
vicinato tra le prime due unità si assegna ad essa un‘età pari a 0 mentre se non esiste
si crea aggiungendola alla tabella. Si aggiungerà poi all‘errore locale accumulato
dall‘unità vincente una quantità pari al quadrato dalla distanza euclidea tra il vettore
v e il vettore dei pesi. Verranno poi modificati sia i pesi dell‘unità vincitrice che delle
unità che hanno relazioni di vicinato con essa. Infine si aumenta di uno l‘età di
ciascuna delle relazioni di vicinato che coinvolgono l‘unità vincitrice e si
elimineranno quindi quelle relazioni che hanno un‘età superiore ad amax. Unità
rimaste isolate vengono rimosse.
Fase di valutazione: in questa fase vengono esaminati gli errori locali accumulati
dalle singole unità di categorizzazione. Si determina quale unità ha il massimo valore
dell‘errore locale accumulato che indichiamo con q (Eq errore di q e Wq i pesi). Tra
le unità che hanno relazioni di vicinato con q si determina quale di esse ha il
massimo errore locale e la indichiamo con f. Si aggiungerà alle unità di
categorizzazione una nuova unità r che avrà come pesi la media dei pesi di f e q. Si
toglierà dalle relazioni di vicinato la relazione fra f e q e si aggiungeranno le
relazioni fra r e f e r e q. Si decrementeranno infine gli errori delle unità q e f.
L‘errore locale di r sarà pari alla media dell‘errore di q e f.
3.6.4 LVQ
Le reti Learnig Vector Quantization (LVQ), ideate da Teuvo Kohonen nel 1989 [17], sono
dei classificatori multinomiali di tipo probabilistico con algoritmo di apprendimento
competitivo e
supervisionato. In quanto classificatori
multinomiali,
sono reti
supervisionate sottoposte ad una fase di training durante la quale devono visionare vettori
di input allo scopo di classificarli correttamente. I vettori di input del set di training sono
articolati in classi; per ogni vettore di input la classe di appartenenza costituisce il target
della rete. In quanto reti di tipo probabilistico, funzionano come classificatori decisionali
CAPITOLO 3: RETI NEURALI
33
Bayesiani e, inoltre, definiscono i bordi delle classi di regioni nello spazio dei dati in input.
A tal fine ogni regione viene sotto articolata per permettere che si costituiscano delle sotto
classificazioni dei vettori di input. Ad ogni classe vengono quindi assegnati alcuni vettori
chiamati codebook e tramite il metodo della Quantizzazione Vettoriale (VQ) si permette la
approssimazione dei vettori più vicini nello spazio degli input secondo la regola KNearest-neighbor.
In quanto reti competitive le LVQ si basano sul principio ―Winner takes all‖, che si traduce
nella possibilità di limitare a correzione al solo codebook più simile all‘input. L‘operatività
delle LVQ è espressa nelle due fasi di training e di testing; laddove la prima è utilizzata per
addestrare la rete a classificare un campione di pattern secondo target prestabiliti, la
seconda è utilizzata per far classificare alla rete pattern nuovi sprovvisti di target nelle
classi precedentemente impostate.
Il principio base sul quale è stata formulata la LVQ è il metodo della quantizzazione
vettoriale (VQ) per la codifica dei segnali. La VQ determina una approssimazione alla
funzione di densità di probabilità p(x) di una variabile continua stocastica x
uso di un numero finito di vettori mi
Rn , facendo
R n , i=1,2,…k, denominati ―codebook‖. Nel metodo
classico il segnale x in arrivo è confrontato con tutti i codebook presenti per misurarne la
distanza vettoriale ed è quindi mappato nel codebook mc più simile tra gli mi.
In sintesi nelle LVQ tale metodo è articolato nel modo seguente: i segnali di input del
training set, in generale una distribuzione di vettori X=(x 1,x2,…xn) di variabili continue in
uno spazio Rn sono associati ad un numero finito di classi; ad ogni classe sono assegnati un
numero finito di codebook delle stesse dimensioni dei vettori X di input. Mediante un
processo iterativo, in cui vengono a turno presentati in pattern di input, sono minimizzate
le distanze tra i codebook e i vettori di input.
L‘architettura base delle LVQ prevede tre strati unidimensionali di nodi: uno strato di input
(I), uno strato intermedio chiamato ―di Kohonen‖ (K) e uno strato di Output (O).
CAPITOLO 3: RETI NEURALI
34
Fig. 3.8: Architettura base di una rete LVQ
Il numero N di nodi di Input è relativo al numero dei tratti con cui sono stati codificati i
pattern, X=(x1 , x2 , ..., xN ). Lo strato di input non compie alcuna funzione di
preprocessamento dei dati in ingresso, ma li registra su vettore. Il numero di nodi che
vengono assegnati allo strato intermedio K fa parte della progettazione dell‘architettura
della rete. Questo è un compito particolarmente delicato in quanto ogni nodo dello strato K
rappresenta un codebook i cui valori sono le connessioni che ogni nodo K intrattiene con i
nodi di input. Il generico nodo dello strato K verrà indicato come Kj , con j = (1,2,. . . ,M).
Lo strato K è lo strato effettivo della rete. L‘attivazione di ogni suo nodo è calcolata, ad
ogni ciclo, come distanza vettoriale di tipo euclideo, nella formulazione più comune, tra il
vettore dei pesi connessi a quel nodo e il vettore del pattern di input.
Lo strato O di output ha un numero C di nodi di output equivalente al numero di classi. Il
generico nodo dello strato O verrà indicato come O z , con z = (1,2,...,C). Secondo la
formulazione base, ad ogni ciclo viene attivato solo il nodo di output connesso con il nodo
Kj la cui attivazione è minore, cioè il cui codebook è più simile al vettore di input. Esistono
unicamente connessioni verticali tra strati adiacenti. Le connessioni sono totali tra gli n
nodi dello strato I e gli m nodi dello strato K e quindi la matrice dei pesi W sarà composta
da n × m valori, mentre le connessioni sono dedicate tra i p × c nodi dello strato K e i c
nodi dello strato O. Nella logica del funzionamento di questa rete, il vettore in W j che
CAPITOLO 3: RETI NEURALI
35
contiene i pesi delle connessioni tra il j-esimo nodo dello strato K e l‘input rappresenta il
―codebook‖ dell‘input.
In quanto reti competitive le LVQ hanno un addestramento che si basa sul principio
―Winner Take All‖ (WTA), che si traduce nella possibilità di limitare la correzione dei
pesi, al solo nodo più simile all‘input [58]. Quando viene mostrato alla rete un nuovo
pattern, il nodo che viene attivato nello strato output sarà quello connesso al codebook più
vicino al pattern in input. Se la classe a cui appartiene il nodo è la stessa del pattern in
ingresso allora viene premiato muovendo il codebook verso il pattern. Nel caso contrario il
nodo viene punito allontanando il codebook dal pattern in ingresso.
Fig. 3.10: modifiche pesi neurone vincente
Oltre alla versione ―base‖, esistono varianti della LVQ che si basano sull‘idea che il
vettore in ingresso è approssimativamente alla stessa distanza sia dal vincitore che dal
secondo vincitore, e quindi entrambi i vettori dei pesi dovrebbero essere aggiornati.
LVQ 2
La principale di idea di questa variazione è che quando il nodo vincitore non rappresenta la
categoria corretta, mentre il secondo vincitore la rappresenta, si addestrano entrambi.
Questo avviene soltanto se la distanza dc tra il nodo vincitore e l‘input e la distanza dr tra il
secondo vincitore e l‘input sono simili. Quindi se
dc
dr
1
dr
dc
costante che dipende dal numero dei campioni dell‘addestramento.
Se questa condizione è verificata allora:
1
dove
è una
CAPITOLO 3: RETI NEURALI
36
wrnew
wrold
(x p
wrold ) nodo vincitore
wcnew
wcold
(x p
wcold ) secondo vincitore
Quindi praticamente viene avvicinato al vettore input il codebook del secondo vincitore, e
allontanato dal vettore input il codebook del nodo vincitore.
LVQ 2.1
In una ulteriore procedura di ottimizzazione del LVQ la condizione per cui il nodo
vincitore non deve appartenere alla stessa classe del pattern mostrato in input viene
abbandonata. Quindi vengono addestrati in ogni caso sia il vincitore sia il secondo
vincitore, con le medesime regole utilizzate in LVQ
LVQ 3
In quest‘ottimizzazione si considerano i due codebook più vicini presi dal pattern in
ingresso. Prima di modificare i vettori di questi due nodi deve verificarsi che:
min[
dc1 dc 2
,
]
dc 2 dc1
(1
)(1
)
Se uno dei due vettori appartiene alla stesa classe del vettore di ingresso, e l‘altro vettore
appartiene ad un‘altra classe si ritorna a LVQ 2.1. Se entrambi i vettori appartengono alla
stessa classe, i pesi si aggiornano come segue:
wcnew
wcold
(x p
wcold ) dove
m . La costante m solitamente è settata tra i valori
0.1 e 0.5.
3.7 Reti neurali modulari
L‘ispirazione per i modelli modulari di reti neurali è dovuta a ragioni che sono
principalmente biologiche e fisiologiche. Si è scoperto, oramai da molti anni, che la chiave
del funzionamento efficiente di un sistema nervoso risiede anche nella sua modularità.
All‘inizio del capitolo abbiamo scritto che il cervello lavora come una black box: elabora
gli stimoli ambientali e fornisce le risposte adatte per raggiungere un obiettivo o una
CAPITOLO 3: RETI NEURALI
37
risposta; inoltre la conoscenza dell‘ambiente è integrata nel sistema nervoso grazie ai
collegamenti neurali che si formano nel processo di sviluppo.
Se da un lato possiamo considerar, quindi, un cervello come un‘entità elaborativa
centralizzata, sappiamo che in realtà non è proprio così: molti esperimenti in
neuropsicologia indicano che un cervello con lesioni circoscritte può portare ad avere
specifici problemi (es. una disfunzione del linguaggio) ma lasciare intatte le altre funzioni
cognitive. Ciò ci suggerisce che il cervello è organizzato in moduli funzionali, in cui ogni
regione svolge compiti specifici.
In generale si può definire come ―modulare‖ un sistema che può essere separato in due o
più parti, nelle quali possono essere identificati gli input e gli output che sono relativi solo
a quel sottosistema. La risposta complessiva del sistema modulare dipende da come le
risposte dei singoli sottosistemi sono combinate.
Un sistema modulare offre vari vantaggi rispetto ad un sistema centralizzato: una maggiore
semplicità progettuale, una più elevata efficienza computazionale, una certa tolleranza agli
errori ed una maggiore possibilità di espansione. Un altro grande vantaggio dei sistemi
modulari è che permettono di risolvere problemi complessi, dividendoli in diversi sottoproblemi di ù facile soluzione. I sotto-problemi sono elaborati da moduli diversi,
specializzati ognuno su quello specifico ambito e, quindi, ogni modello computazionale
locale risulta di molto semplificato rispetto al modello globale e centralizzato. Grazie a
queste sue caratteristiche il paradigma della modularità di reti neurali è adatto al problema
del riconoscimento biometrico [18].
In ogni caso i singoli moduli presentano sempre una lista di caratteristiche:
I moduli hanno un loro dominio specifico, che ne detta l‘architettura per rispondere
ad un dato compito, che è solo una parte di quello generale
Ogni modulo è indipendente dagli altri per il suo funzionamento e non è influenzato
dagli altri
L‘architettura dei singoli moduli è in genere più semplice di quella del sistema
globale ed anche grazie a questa caratteristica, la risposta di un singolo modulo è più
veloce rispetto a quella di un singolo sistema monolitico
CAPITOLO 3: RETI NEURALI
38
Le risposte dei singoli moduli sono semplici ma devono essere combinate da un
qualche meccanismo di coordinamento, per formulare una risposta del sistema nel
suo insieme
I vantaggi che rendono uno schema modulare di reti neurali più apprezzato rispetto ad un
tradizionale sistema monolitico sono tanti, e di ovvia comprensione; alcuni di questi sono
la robustezza, la scalabilità, la riduzione della complessità, l‘efficienza computazionale e
l‘economia dell‘apprendimento.
39
Capitolo 4
Logica Fuzzy e sistemi Neuro-Fuzzy
In questo capitolo verranno introdotti i fondamenti della logica fuzzy, un tipo di logica
polifunzionale che estende la logica booleana. Anche definita ―logica sfumata‖, viene
spesso utilizzata parallelamente alle reti neurali, per creare dei sistemi ibridi che cercano di
unire i vantaggi di tutte e due le strutture, minimizzando gli svantaggi. Prima verrà fatta
una panoramica sulla storia della logica fuzzy, dalla sua introduzione a metà degli anni 60
fino ai tempi recenti; successivamente vengono spiegate le regole base, e i processi di
trattazione dei dati; infine, verranno elencati vantaggi e svantaggi dei sistemi neuro fuzzy.
4.1 Storia della logica Fuzzy
Nei primi anni sessanta, Lofti A. Zadeh, professore all‘università di Berkeley, cominciò ad
avvertire che le tecniche tradizionali di analisi dei sistemi erano eccessivamente ed
inutilmente accurate per molti dei problemi tipici del mondo reale. L‘idea di grado
d‘appartenenza, il concetto divenuto poi la spina dorsale della teoria degli insiemi sfumati,
fu da lui introdotta nel 1964, e ciò portò in seguito (nel 1965) alla pubblicazione di un
primo articolo, ed alla nascita della logica fuzzy [19,20]. Il concetto di logica sfumata
attirò le aspre critiche della comunità accademica; ciononostante, studiosi e scienziati di
tutto il mondo (dai campi più diversi) cominciarono a compiere ricerche su questo
argomento.
In particolare in Giappone la ricerca sulla logica fuzzy cominciò con 2 piccoli gruppi
universitari fondati sul finire degli anni settanta: uno a Tokyo e uno a Kanasai. Al pari dei
ricercatori americani, questi studiosi si scontrarono nei primi tempi con un‘atmosfera
fortemente avversa alla logica sfumata; alla fine i più importanti contributi alla ricerca
vennero proprio da questi due gruppi di studio.
CAPITOLO 4: LOGICA FUZZY E SISTEMI NEURO FUZZY
40
Nel 1974, in Gran Bretagna, venne sviluppato il primo sistema di controllo di un
generatore di vapore, basato sulla logica fuzzy. Nel 1976 si ebbe la prima applicazione
industriale di questa logica, per il controllo di una fornace per la produzione di cemento.
Nel corso degli anni 80, diverse importanti applicazioni industriali della logica fuzzy
furono lanciate con pieno successo. La logica sfumata ha avuto anche importanti
applicazioni in campo finanziario, come la compravendita azionaria (sempre in Giappone),
rivelandosi molto efficiente; infine dal 1994 è disponibile il Toolbox per la logica fuzzy nel
programma MATLAB, che permette a tutti di comprendere meglio e utilizzare la logica
sfumata [21].
4.2 Concetti fondamentali
Il concetto alla base della logica introdotta da Zadeh è il concetto relativo agli ―insiemi
fuzzy‖. Infatti nei fuzzy set, che sono oggi la base della moderna fuzzy logic, la veridicità
di una proposizione può assume valori compresi nell'intervallo tra 0 e 1 e non solo nei suoi
estremi. Tale logica può essere definita in contrapposizione alla logica tradizionale.
Quest‘ultima si basa su concetti quali il principio di non contraddizione, o il principio del
terzo escluso.
Nella logica classica degli insiemi dati due insiemi A e !A (non-A) il principio di non
contraddizione stabilisce che ogni elemento appartenente all‘insieme A non può
contemporaneamente appartenere anche a !A; secondo il principio del terzo escluso, d‘altro
canto, l‘unione di un insieme A e del suo complementare costituisce l‘universo del
discorso.
La logica sfumata invece, prevede il concetto di ―grado di appartenenza‖ di una funzione
ad un insieme; in‘altre parole, la veridicità di una proposizione può assumere valori
compresi nell‘intervallo tra 0 e 1 e non solo nei suoi insiemi. Prendiamo ad esempio una
serie di 3 classi di temperature: Bassa, Media e Alta. La classificazione della temperatura
può essere allora espressa "classicamente" da una stringa di tre bit ognuno dei quali
esprime la verità; con la quale la temperatura appartiene alla corrispondente classe: ad
esempio una temperatura T sotto la prima soglia di bassa sarà associata alla stringa [1 0 0];
viceversa per una temperatura media si avrà [0 1 0] e per una alta [0 0 1].
CAPITOLO 4: LOGICA FUZZY E SISTEMI NEURO FUZZY
41
Nel caso fuzzy i bit vengono rimpiazzati da valori (detti Fit=Fuzzy digit) che variano con
continuità da zero a uno perché così; viene espressa la misura di verità degli enunciati,
ovvero il grado di appartenenza dei valori di temperatura alle varie classi. La stessa
temperatura T può quindi appartenere contemporaneamente a varie classi, con gradi di
verità differenti: ad esempio [0.4 0.6 0] per una temperatura medio bassa o [0 0.6 0.4] per
una temperatura medio alta.
Si intuisce subito come la descrizione della realtà sia migliore; Quello che era un paradosso
se descritto in modo binario viene quindi risolto da una descrizione fuzzy nella quale esso
costituisce un enunciato "vero a metà". Più in generale l'opposto di una stringa di verità
fuzzy è costituita dalla stringa dei complementi ad uno di tali valori di verità. [21]
Se rappresentiamo i valori di veridicità tra 0 e 1 come nel grafico nella figura seguente, si
vede subito che con la logica classica possiamo rappresentare solo i vertici del cubo,
mentre con la logica sfumata possiamo rappresentare l‘intero volume della figura.
Fig. 4.1: Logica Fuzzy
CAPITOLO 4: LOGICA FUZZY E SISTEMI NEURO FUZZY
42
4.3 Funzioni di appartenenza
Un insieme o classe fuzzy A in X è; un insieme di coppie ordinate della forma (μ A(x),x)
dove il secondo termine è un elemento appartenente a X, mentre il primo rappresenta
l'appartenenza
di
tale
elemento
con
l'insieme
A.
L'appartenenza di x in A può quindi non essere totale, e variare in modo continuo tra
appartenenza nulla e appartenenza al 100%. Per convenzione si considera l'appartenenza
come una funzione che associa ad ogni elemento del dominio un valore compreso in [0,1].
La notazione per indicare che A è un insieme fuzzy su un dominio non fuzzy X (o
equivalentemente A è sottoinsieme fuzzy di X) è A if X. L'appartenenza di un generico
elemento x con un insieme fuzzy A può quindi essere formalizzata mediante la nozione di
funzione di appartenenza (membership function) μA(x) dell'insieme fuzzy A così definita:
A
( x) : X
[0,1]
cioè μA associa ad ogni punto x in X un valore compreso tra 0 e 1 che rappresenta il grado
di appartenenza di x in A. Più questo valore si avvicinerà ad uno, e più sarà alto il grado di
appartenenza di x in A. I casi limite di zero e uno rappresentano i valori assunti dalla
funzione caratteristica per insiemi nel senso ordinario. Questi ultimi vengono detti insiemi
crisp e conseguentemente la logica classica su di essi fondata diventerà logica crisp. L'idea
che segue da queste prime definizioni è che questi ultimi insiemi (e, come si vedrà, con
essi la logica) rappresentino un caso particolare della più generale logica fuzzy.
4.4 Operazioni sugli insiemi
Dato che i valori di verità degli enunciati non sono più binari, risulta necessario ridefinire
gli operatori logici elementari (AND, OR, NOT) [22]; di seguito verranno presentati le
funzioni ridefinite
CAPITOLO 4: LOGICA FUZZY E SISTEMI NEURO FUZZY
43
4.4.1 Negazione
La negazione si può definire intuitivamente come il complementare della funzione di
appartenenza:
nonA
( x) 1
A
( x)
Di cui si può avere una interpretazione geometrica nella figura seguente
Fig. 4.2: Fuzzy NOT
4.4.2 Unione (OR)
La formula per effettuare l‘unione è la seguente
AorB
( x)
max(
A
( x);
B
( x))
Alternativamente si possono usare anche le seguenti formule
AorB
( x)
A
( x)
AorB
( x)
min(
B
A
( x)
( x)
A
B
( x)
B
( x)
( x);1)
Fig. 4.3: Fuzzy OR
CAPITOLO 4: LOGICA FUZZY E SISTEMI NEURO FUZZY
44
4.4.3 Intersezione (AND)
Infine l‘intersezione si può rappresentare con
AandB
( x)
min(
A
( x);
B
( x))
Anche per l‘AND, come per l‘unione, esistono formule alternative che possono essere
usate nei vari casi, e sono
AandB
( x)
A
( x)
AandB
( x)
max(
B
A
( x)
( x)
B
( x) 1;0)
Fig. 4.4: Fuzzy AND
4.5 Sistemi Fuzzy
Le idee ispirate della logica fuzzy hanno trovato vasto impiego nell'ambito dei sistemi di
regolazione e controllo dei processi industriali nonché nel campo degli algoritmi
dell'intelligenza artificiale per la simulazione di processi decisionali umani. Inoltre i
cosiddetti sistemi di inferenza fuzzy, ovvero sistemi di controllo basati sulla logica fuzzy,
sono stati applicati con successo in campi quali il controllo automatico, la classificazione
dei dati, l'analisi decisionale, sistemi esperti, e computer vision. In questo capitolo vediamo
come funziona un generico sistema di inferenza fuzzy, avvalendoci dell'esempio di una
semplice regolazione di temperatura. Generalmente lo schema tipico di un sistema fuzzy è
quello riportato nella figura seguente
CAPITOLO 4: LOGICA FUZZY E SISTEMI NEURO FUZZY
45
Fig. 4.5: Schema base sistema fuzzy
Generalmente lo schema tipico di un sistema fuzzy è quello riportato nella figura
precedente. Le grandezze fisiche misurate vengono "fuzzificate" in base a certe predefinite
funzioni di appartenenza allo scopo di derivarne una rappresentazione fuzzy. Queste
vengono poi elaborate in base ad una serie di regole del tipo IF ... THEN allo scopo di
determinare la forma fuzzy della variabile d'uscita del ragionamento. Infine questa viene
defuzzificata allo scopo di ricavare un valore numerico deterministico ("crisp") da
assegnare alla variabile d'uscita (y). Vediamo ora più in dettaglio i processi di
fuzzificazione e defuzzificazione.
4.5.1 Fuzzificazione
Parlando di fuzzificazione si intende l procedimento attraverso il quale le variabili di
ingresso vengono convertite in misure fuzzy della loro appartenenza a determinate classi
come ad esempio Nulla, Bassa, Media, Alta, Molto Alta. Tale conversione da grandezze
deterministiche a fuzzy viene effettuata attraverso le funzioni di appartenenza predefinite
per quelle classi. Data una membership function μ A e rilevato un valore x° la conversione
di x° in un insieme fuzzy consiste nel complemento dell'alpha-cut dell'insiema A alla quota
alpha=μA(x°) ovvero nell'insieme:
A ' {x |
A'
( x)
min(
A
( x ),
A
( x))}
CAPITOLO 4: LOGICA FUZZY E SISTEMI NEURO FUZZY
46
Dato che il valore x° può "intercettare" più di una funzione di appartenenza esso genera più
insiemi fuzzy ciascuno rappresentato dalla associata membership function decapitata alla
quota corrispondente proprio all'intercetta.
Fig. 4.6: Fuzzificazione
4.5.2 Defuzzificazione
La forma fuzzy dell'uscita non costituisce però un valore molto utile, specialmente per un
attuatore come un'elettrovalvola. Occorre pertanto riconvertirlo in valore deterministico
attraverso un'operazione detta di "defuzzificazione". Per ottenere questo risultato sono stati
proposte diverse metodologie di calcolo, le più utilizzate delle quali sono le seguenti:
Media dei massimi: Il valore dell‘uscita viene ottenuto come media aritmetica dei valori
di y in corrispondenza dei quali è massima l‘altezza del fuzzy set inferito dalle regole. Sia
cioè B‘ il fuzzy set e hgt ( B ') { y |
B'
( y) sup B ' ( y)} l‘insieme dei valor di y per i quali
y B'
è massima l‘altezza mB‘(y). Si ha allora che:
ydy
Yout
hgt ( B ')
dy
hgt ( B ')
CAPITOLO 4: LOGICA FUZZY E SISTEMI NEURO FUZZY
47
Fig. 4.7: significato geometrico della media dei massimi
Media pesata dei centri: Il valore dell'uscita viene ottenuto come rapporto tra la somma
dei centri dei fuzzy set d'uscita pesati con i corrispondenti valori inferiti per essi dalle
regole e la somma di tali pesi. Siano cioè b i i valori inferiti dalle regole per i diversi fuzzy
set relativi alla variabile di uscita e siano yi i centri dei diversi fuzzy set; matematicamente
si può allora scrivere:
yi bi
Yout
i
bi
i
Fig. 4.8: Significato geometrico della media pesata dei centri
I diversi calcoli di defuzzificazione devono essere plausibili, nel senso che il risultato deve
essere conforme a quanto desiderato in fase di sintesi dell‘algoritmo; essi possono essere
considerati in base alla valutazione di differenti criteri:
Continuità: un piccolo cambiamento di valore degli ingressi non deve portare ad un
enorme mutamento nel valore dell‘uscita
Complessità computazionale
Accuratezza
4.6 Sistemi Ibridi
I sistemi basati sulla logica fuzzy si fondano sull'osservazione delle modalità con cui il
cervello tratta l' informazione "incerta" o approssimata. Laddove invece le reti neurali
rappresentano una modellizzazione della tipica architettura fisica del cervello. Sebbene,
CAPITOLO 4: LOGICA FUZZY E SISTEMI NEURO FUZZY
48
dunque, l'ispirazione originale sia essenzialmente differente, vi sono in realtà molte
potenzialità accomunabili fra i due modelli. Sin dalla prima apparizione ufficiale della
logica fuzzy, la sua efficacia dipese dalla scelta cruciale delle sue funzioni di appartenenza,
dalle regole di controllo e dal meccanismo dell'inferenza fuzzy.
L'uso delle reti neurali per automatizzare e sintetizzare la progettazione di un sistema
decisionale, basato sulla logica fuzzy, rappresenta allora un approccio innovativo ed una
soluzione alle principali difficoltà insite nel processo di ottimizzazione del sistema.
Principalmente, il concetto di reti neurali addestrabili sintetizza l'idea di impiegare le loro
capacità di apprendimento per imparare ad estrapolare in maniera automatica i principali
parametri che caratterizzano un sistema basato su logica fuzzy, dalle funzioni di
appartenenza, alle regole del controllo fuzzy.
Fondamentalmente, la logica fuzzy, come abbiamo visto, nasce come strumento per
rappresentare e manipolare l'informazione incerta e per provvedere alla gestione ed utilizzo
dell'incertezza ed imprecisione nelle applicazioni legate al mondo reale. Viceversa le reti
neurali nascono come strumento per formalizzare ed implementare in sistemi artificiali le
capacità computazionali, il principio di autoriparazione, e le capacità di apprendimento dei
sistemi biologici. L'unione in un unico modello artificiale delle due tecniche rafforza ed
amplifica queste loro peculiarità. Infatti le reti neurali forniscono la struttura
connessionista, mentre la logica fuzzy fornisce le regole semantiche con cui dirigere il
flusso delle informazioni all'interno della struttura, dotando le reti neurali di potenti e
flessibili regole decisionali del tipo IF ... ELSE
con cui codificare ed interpretare i
"mattoni" del ragionamento e del pensiero dell'intero modello artificiale.
Questa fusione fra i due modelli identifica dunque la soluzione al tentativo di unificare le
capacità di apprendimento a basso livello con le capacità di pensiero e ragionamento a più
alto livello, che, nel modello biologico, rappresentano l'essenza del concetto di
intelligenza. In questo senso essi condividono la comune abilità nel potenziare
l'intelligenza di sistemi interagenti in un ambiente incerto, impreciso e rumoroso. Entrambi
i modelli hanno mostrato elevate capacità di modellizzazione di processi complessi reali
con arbitrari livelli di accuratezza.
Di conseguenza, le due tecnologie possono essere reciprocamente complementari, con le
reti neurali poste a garantire la necessaria potenza di calcolo per interpretare grandi
quantità di dati sensoriali e la logica fuzzy adibita al ruolo di amplificatore delle capacità di
CAPITOLO 4: LOGICA FUZZY E SISTEMI NEURO FUZZY
49
interpretazione dell'informazione preselezionata a più basso livello. Dunque la maggior
parte dei modelli neuro-fuzzy esistenti sono essenzialmente identificabili come sistemi
basati su regole fuzzy, in cui le reti neurali sono utilizzate per l'apprendimento e
l'adattamento.
Logica fuzzy e reti neurali sono entrambi approcci alla modellizzazione dei sistemi che si
possono fare rientrare nella vasta categoria dei metodi propri del soft computing.
Sia le reti neurali sia gli algoritmi fuzzy risolvono problemi propri del loro dominio
sfruttando una loro caratteristica capacità di approssimazione di funzioni. In tutti questi
casi manca un modello matematico del problema in esame e non e' necessaria una forma di
conoscenza "a priori".
La rete neurale è una "black box", cioè non si sa cosa succeda all'interno del modello, e
non si possono trovare regole logiche per descrivere i suoi stati finali. Inoltre non è
possibile insegnare alla rete nulla anche nel caso si abbia un bagaglio di conoscenza
preesistente. Un ulteriore svantaggio è il fatto che il processo di apprendimento può essere
lungo e non convergere. Un aspetto che va annoverato fra i vantaggi delle reti neurali e' la
tolleranza ai cambiamenti di input e di struttura. Tuttavia, se questi cambiamenti sono
sensibili, a volte è necessario rieseguire l'addestramento, con conseguente ulteriore perdita
di tempo e risorse.
Un sistema fuzzy può essere usato per risolvere un problema se si possiede una conoscenza
della soluzione in termini di regole "if-then": dopo avere definito fuzzy set adatti, si può
creare un sistema fuzzy da queste regole. Non si necessita quindi di un modello formale del
sistema e nemmeno di dati di training. Tuttavia, se non si e' in grado di esprimere
l'algoritmo in termini di regole "if-then", l'algoritmo fuzzy non può essere programmato.
Per quanto riguarda la robustezza del sistema, può accadere che un "tuning" non preciso
per un solo fuzzy set abbia conseguenze gravi su tutto il processo.
Come detto nella sezione introduttiva, quindi, la ragione più importante che porta a
combinare reti neurali e sistemi fuzzy è la possibilità di realizzare sistemi che
"apprendono". Dalla tabella si vede peraltro che una combinazione dei due metodi può
portare a soluzioni che uniscono, per quanto possibile, i vantaggi dei due metodi,
evitandone gli svantaggi.
CAPITOLO 4: LOGICA FUZZY E SISTEMI NEURO FUZZY
50
VANTAGGI
RETI NEURALI
Non è richiesto alcun modello
matematico del processo
SISTEMI FUZZY
Non è richiesto alcun modello
matematico del processo
Sono disponibili diversi algoritmi per il
training
Può essere usata conoscenza "a
priori"
Semplicità di realizzazione
SVANTAGGI
RETI NEURALI
Scatola nera
Non si possono estrarre le regole alla
fine dell'apprendimento
Può essere difficile l'adattamento a
diverse situazioni e necessario un nuovo
training
Il processo di apprendimento può non
convergere
SISTEMI FUZZY
Devono essere disponibili regole del
tipo "if-then"
Non possono apprendere
Non esistono metodi formali per il
tuning dei fuzzy set
L'adattamento a diverse situazioni
può essere difficile
Il tuning può non avere successo
51
Capitolo 5
Face Recognition System
In questo capitolo viene brevemente descritto il sistema di riconoscimento facciale usato
nel nostro sistema e progettato dallo studente Pasquale Sconciafurno; per un dettaglio
migliore, si rimanda alla sua tesi [23].
Il sistema di riconoscimento facciale (FRS) qui proposto è un sistema ibrido, basato
sull‘analisi delle feature del volto con un criterio olistico, che usa un insieme di reti neurali
per l‘analisi delle caratteristiche delle immagini dei volti, unito ad un sistema di
condizionamento Bayesiano. Le reti neurali sono addestrate a riconoscere le feature del
volto e, ad ognuna di esse, è associata un‘affidabilità a priori, a seconda del tipo di zona del
volto da analizzare. In base alle performance che la rete dimostra di avere ed ai conflitti
che la sua risposta causa con quelle delle altre reti, vengono ricalcolati i valori di
affidabilità, usando la regola di Bayes. Le nuove affidabilità, con gli insiemi
massimamente consistenti delle risposte delle singole reti, sono poi usate per il calcolo
della risposta complessiva del gruppo di reti neurali attraverso l‘uso di un algoritmo di
sintesi. Se un soggetto evolve nel tempo per una sua caratteristica il sistema si auto
aggiorna, attraverso il modulo della retroazione, per continuare a riconoscere quella
caratteristica nonostante sia cambiata. Si pongono come vincoli di progettazione alcune
limitazioni sul tipo di immagini dei volti e sulle condizioni di luminosità delle immagini da
riconoscere, in quanto si immagina che, una volta a regime, il sistema sia installato su di
una postazione fissa e che le condizione di illuminazione siano costanti nella fase di cattura
delle immagini.
CAPITOLO 5: FACE RECOGNITION SYSTEM
52
5.1 Architettura sistema
Il sistema è caratterizzato da una struttura modulare, questa caratteristica ne garantisce da
un lato l‘espandibilità e dall‘altro permette un maggiore controllo sul funzionamento dei
singoli blocchi. I blocchi principali del sistema sono i seguenti:
Estrazione feature: Questo blocco si occupa di estrarre le immagini delle
caratteristiche del volto da una immagine complessiva dello stesso, che va ad essere
analizzato.
Reti Neurali: In questa sezione le varie immagini delle feature del volto sono passate
alle reti neurali che svolgono il compito del riconoscimento delle caratteristiche.
Ogni rete fornirà come risposta una lista di soggetti ordinata in base al grado di
confidenza di quel soggetto con l‘immagine in input. Il primo soggetto sarà quello
che per la rete è il più simile, l‘ultimo quello meno probabile.
Condizionamento Bayesiano: In questo blocco sono analizzate le risposte delle reti
per costruire gli insiemi massimamente consistenti ed aggiornare così le affidabilità a
posteriori delle reti.
Funzione di sintesi: E‘ in questa fase che sono combinati i risultati delle reti e delle
loro affidabilità, per stabilire qual è il soggetto finale identificato dal sistema. Sono
stati usati due algoritmi diversi, l‘Inclusion Based (nelle due versioni, quella pesata e
quella non pesata) e l‘Algoritmo Pesato.
Retroazione: Se un soggetto cambia stabilmente una sua caratteristica il sistema deve
essere in grado di aggiornare la sua conoscenza, il compito è svolto da questo
modulo.
CAPITOLO 5: FACE RECOGNITION SYSTEM
53
Fig. 5.1: Schema a blocchi del sistema di riconoscimento facciale
5.2 Estrazione feature
Il primo blocco si occupa di estrarre dalle immagini complete del volto i frammenti che
rappresentano le feature. Usiamo per l‘analisi le sole feature, perché in questo modo si
riduce la quantità dei dati da analizzare, mantenendo solo quella parte che risulta utile ai
fini dell‘identificazione dei soggetti: i passi successivi, così facendo, sono eseguiti più
velocemente ed il sistema risulta più snello.
Nel nostro caso si è deciso di estrarre cinque caratteristiche dai volti: la fronte, l‘occhio
sinistro, l‘occhio destro, il naso e la bocca. Ad ogni frammento del volto corrisponderà una
rete neurale addestrata a riconoscere i soggetti, analizzando quella specifica feature. La
scelta del numero di feature è un parametro di progettazione importante perché, aumentare
il numero di feature, consente di aumentare anche gli esperti che pronunciano sul problema
dell‘identificazione. In generale più alto sarà il numero, minore sarà la sensibilità al rumore
del sistema, dovuto alle variazioni locali dell‘immagine del soggetto.
5.3 Reti neurali
Per la classificazione delle immagini delle feature si è ricorso alle reti LVQ. Le Learning
Vector Quantization sono spesso usate in quei problemi di classificazione in cui si conosce
il numero di classi che fanno parte del sistema. Nel nostro caso una classe è rappresentata
dall‘identità di un soggetto.
CAPITOLO 5: FACE RECOGNITION SYSTEM
54
Le reti LVQ hanno un‘architettura basata su tre strati: uno di input, uno intermedio
nascosto e uno di output. Lo strato di ingresso è totalmente connesso con quello intermedio
(detto di Kohonen) e la sua dimensione dipende dalla grandezza del pattern in ingresso;
quello intermedio ha un numero variabile di collegamenti con lo strato di uscita e dipende
dal numero di vettori codebook associati ad ogni classe, classi che sono poi rappresentate
dal numero di nodi di uscita.
Nel nostro caso i pattern in ingresso sono le immagini del volto, da una immagine di
dimensioni n x m si passa ad un vettore con la stessa lunghezza ottenuto dalla
concatenazione delle colonne dell‘immagine.
Il numero di elementi di input sarà diverso per ogni rete, visto che è pari alla grandezza
dell‘immagine che deve classificare e le varie reti hanno immagini di grandezze diverse. Il
numero di neuroni dello strato di uscita, invece, è costante per tutte le reti ed è pari al
numero di soggetti da riconoscere. Ad ogni neurone nello stato intermedio è associato un
vettore chiamato ―codebook‖, composto dai valori dei pesi delle connessioni tra il neurone
e gli elementi dello strato di input. Visto che, nel nostro caso, ogni codebook è associato
univocamente ad una sola classe, il numero dei nodi dello strato intermedio coincide con
quello dello strato di uscita.
La classificazione di nuovi vettori in ingresso avviene confrontandoli con il vettore
codebook associato ad ogni classe. In questo modo si ottiene una lista ordinata in base alla
distanza euclidea tra vettore in ingresso i-esimo codebook della classe i. Il primo nodo
nella lista corrisponde al soggetto che la rete identifica come quello più probabile, l‘ultimo
della lista è il soggetto meno simile.
L‘addestramento della rete LVQ, come descritto in precedenza nel paragrafo 3.6.4, è di
tipo supervisionato e competitivo; consiste nel presentare alla rete le coppie ―immaginisoggetto‖, regolando i pesi della rete in modo che il nodo vincitore sia quello che
rappresenta la classe del soggetto. I pesi sono regolati in modo che, se la classe associata a
quell‘input è la stessa del pattern di ingresso, allora viene premiato il nodo vincitore,
muovendo il codebook verso il pattern; nel caso contrario, il nodo viene punito
allontanando il codebook dal pattern.
Per l‘addestramento delle reti è stato usato l‘algoritmo LVQ 2.1 che consente di aggiornare
i codebook del primo e del secondo nodo vincitore, diminuendo i tempi di addestramento.
CAPITOLO 5: FACE RECOGNITION SYSTEM
55
5.4 Condizionamento Bayesiano
Il condizionamento Bayesiano è usato per risolvere i conflitti tra gli esperti assegnando un
nuovo valore di affidabilità sulla base dei soggetti identificati da ogni rete neurale. Dal
momento che ognuna di esse analizza una caratteristica facciale diversa, è possibile che le
risposte non convergano su di un unico soggetto: è sufficiente, infatti, che due soggetti si
assomiglino per una loro caratteristica per indurre in errore una rete. Ad esempio, due
soggetti che indossino lo stesso paio di occhiali possono essere confusi dalle reti deputate
al riconoscimento degli occhi.
Un primo passo da fare è quello di stabilire il numero massimo di soggetti da prendere in
considerazione dalla lista di ogni LV. In base a questo parametro si generano, infatti, più o
meno conflitti. Il limite massimo dei conflitti si ha quando si prende tutta la lista dei
soggetti: in questo caso abbiamo un numero di conflitti pari al numero dei soggetti; se
invece decidessimo di selezionare solo il primo soggetto nella lista di ogni rete, allora il
numero massimo di conflitti sarebbe pari al numero delle reti, nel caso ogni rete
identificasse un soggetto diverso. Il numero dei soggetti per ogni rete è, quindi, un
fondamentale parametro di progettazione. Una volta stabilito il numero dei livelli di
soggetti per ogni rete si usa il condizionamento Bayesiano:
1. Si trovano tutti i sottoinsiemi minimali delle fonti in contraddizione;
2. Si trovano tutti i super insiemi che li contengono;
3. Vengono sommate in Rcontraddizione le affidabilità di tali insiemi;
4. Viene posta a zero l‘affidabilità di tali insiemi;
5. Si divide l‘affidabilità di ogni insieme delle fonti non contraddittorie per1Rcontraddizione;
6. Per ottenere l‘affidabilità a posteriori delle singole reti si sommano tutte le
affidabilità revisionate di ogni sottoinsieme delle massime consistenze in cui quella
specifica sorgente informativa è contenuta.
CAPITOLO 5: FACE RECOGNITION SYSTEM
56
5.5 Funzioni di sintesi
una funzione di sintesi è necessaria per stabilire quale insieme dei Good sia più credibile
per il sistema, sulla base delle affidabilità a posteriori delle reti, ricalcolate grazie al
condizionamento Bayesiano.
Esistono due algoritmi per effettuare questa operazione: L‘inclusion Based (nella sua
versione non pesata e in quella pesata) e l‘Algoritmo Pesato.
5.5.1 Inclusion based e ottimizzazioni
Questo algoritmo di sintesi utilizza le nuove affidabilità delle reti in base al
condizionamento bayesiano e gli insiemi delle massime consistenze per stabilire un
vincitore univoco per tutto il sistema. I passi che seguono questo algoritmo sono i seguenti
[24]:
1. Vengono selezionati tutti li insiemi massimamente consistenti che contengono la rete
con l‘affidabilità più alta;
2. Se l‘insieme è unico, allora l‘algoritmo si arresta e si seleziona il soggetto associato a
quell‘insieme come risultato per il sistema;
3. Altrimenti, se esistono più insiemi, vengono selezionati tutti quelli in cui è presente
la seconda rete in ordine di maggiore affidabilità e si ripete il passo 2;
Un problema che può presentare l‘Inclusion Based è la dipendenza della soluzione finale
dall‘ordinamento usato per le reti. Per eliminare questa dipendenza, esiste una
ottimizzazione dell‘algoritmo, chiamato Inclusion Based pesato. Questa versione calcola la
distanza euclidea tra i codebook dei nodi delle reti ed i pattern in ingresso, usando questa
informazione aggiuntiva per ordinare le reti in base a un peso che gli viene associato.
Il metodo funziona come segue:
1. Viene associato un peso P(st) ad ogni insieme Good trovato
st
S P( st )
N
i 1
diC ( st )
CAPITOLO 5: FACE RECOGNITION SYSTEM
57
2. Vengono ordinate le reti secondo la loro affidabilità a posteriori. Nel caso più reti
avessero la stessa affidabilità, allora per ognuna di esse viene calcolato un peso:
min{ P( st ) con st : niC ( st )
pi
st
3. Si applica l‘Inclusion Based con il nuovo ordinamento delle reti.
5.5.2 Algoritmo pesato
una caratteristica negativa dell‘Inclusion Based è che nel calcolo degli insiemi
massimamente consistenti non viene considerata solo l‘affidabilità delle sorgenti. In questo
modo non si usa una parte molto importante delle convinzioni delle reti, ovvero le
preferenze tra i soggetti selezionati nelle prime posizioni. Un metodo che cerca di usare
anche questa informazione è l‘Algoritmo pesato che assegna un punteggio che è
inversamente proporzionale alla distanza del codebook della classe del vettore in ingresso.
Sia il sistema composto da N reti neurali e si debbano identificare NC soggetti: indichiamo
con dik la distanza euclidea tra il nodo della i-esima rete associato alla k-esima classe e con
S l‘insieme dei Good trovati con le risposte. C(st) indica la classe associata all‘t-esimo
insieme Good trovato. Inoltre indichiamo con Ri il vettore dei nodi della rete i-esima,
ordinato secondo la distanza euclidea tra i suoi nodi ed il pattern mostrato in ingresso, un
suo elemento, ri0, conterrà la prima risposta della rete: la classe che ha il codebook più
vicino al pattern in input. Con Ai indichiamo l‘affidabilità a posteriori dell‘i-esima rete.
Il metodo consiste nei seguenti passi:
1. A tutte le risposte delle reti ri0 (risposta dell‘i-esima rete nella posizione o-esima)
viene associato un peso così calcolato:
rio (1 i
n, 1 o
NC ) pio
1
o
Il peso di ogni risposta è inversamente proporzionale alla posizione occupata nel
vettore delle risposte Ri. Più lontana dalla cima della lista sarà la posizione della
risposta e minore sarà il peso associato a quella risposta.
2. Viene associata una coppia di pesi anche ad ogni insieme Good:
st
S
Pa ( st )
rio st
Ai pio
N
CAPITOLO 5: FACE RECOGNITION SYSTEM
st
S
58
Pa ( st )
N
i 1
diC ( st )
Pa è pari alla somma dei prodotti tra i pesi delle risposte e l‘affidabilità della rete che
ha dato quella risposta presenti nell‘insieme Good. Il secondo peso Pd è lo stesso
usato nel metodo Inclusion Based ottimizzato.
3. Il Good più credibile secondo questo algoritmo è quello associato al peso Pa
maggiore. Nel caso in cui più insiemi Good hanno lo stesso valore Pa allora la scelta
del Good ricade in quello a cui è associato il peso Pd minore.
5.6 Modulo per la retroazione
Questo componente si occupa di aggiornare la conoscenza delle singole reti sulla base
dell‘output generato dalla funzione di sintesi utilizzata. Come abbiamo visto fino ad ora,
l‘FRS qui proposto usa i contributi di diverse reti neurali per formulare una risposta di
sintesi sull‘identità di un soggetto. Per la sua architettura il sistema è poco sensibile ai
cambiamenti limitati ad una sola caratteristica del soggetto. Infatti grazie al
condizionamento Bayesiano una rete che sbaglia nel riconoscimento vedrà man mano
diminuire la sua affidabilità. Dato che poi l‘affidabilità delle reti è usata negli algoritmi di
sinesi per la risposta, il contributo della rete che sta sbagliando sarà sempre minore e
tenderà, con il passare del tempo, a zero.
Ciò se da un lato consente al sistema di riconoscere soggetti che cambiano una loro
caratteristica, rende lo stesso poco incline a gestire un ambiente in evoluzione. Se ad
esempio un soggetto, in fase di training della rete deputata al riconoscimento della bocca,
ha la barba corta e, successivamente, decide di farla crescere, si arriverà ad un punto in cui
l‘immagine della sua bocca non sarà più associata a lui, ma ad un altro soggetto,
precisamente a colui che ha il codebook, associato al nodo di uscita più vicino a quella
nuova immagine.
Se le altre reti continuassero ad associare il soggetto alla giusta identità, nonostante il
cambiamento sulla zona bocca, allora non ci sarebbero più problemi di identificazione. Per
questo sarebbe più utile aggiornare il sistema con la nuova conoscenza rappresentata
dall‘immagine che assunto il soggetto. Allo stesso tempo si deve, però escludere la
CAPITOLO 5: FACE RECOGNITION SYSTEM
59
possibilità che il sistema aggiorni la sua conoscenza con troppa frequenza. Una eccessiva
attenzione su di una caratteristica, che risulta molto mutabile nel tempo, potrebbe causare
un numero esagerato di riaddestramenti, e questo non sempre è un fatto positivo;
pensiamo, ad esempio, ad un soggetto che a giorni alterni indossi occhiali da vista e lenti a
contatto. In questo caso non si dovrebbe aggiornare la conoscenza, perché la caratteristica
non cambia stabilmente nel tempo, ma ha una semplice variabilità. Riaddestrare in questo
caso sarebbe poco utile o addirittura deleterio: non riaddestrando si avrebbe un
riconoscimento nel 50% delle volte; riaddestrando ad ogni cambiamento, invece, non si
identificherebbe mai la feature di quel soggetto, visto che si aggiorna la conoscenza che la
riguarda ma essa è già cambiata nel frattempo.
Per tenere conto dei soli cambiamenti ―stabili‖ si è usato un approccio basato sul concetto
di finestra temporale: si tiene traccia di ogni cambiamento per ogni feature e,
contemporaneamente, si controlla se, nelle successive analisi dello stesso soggetto, quella
caratteristica mantiene la sua modifica, si riaddestra solo nel caso in cui la modifica duri
per un tempo maggiore o uguale all‘ampiezza della finestra temporale stabilita. In questo
modo evitiamo il caso dell‘esempio precedente, con il soggetto in possesso di una
caratteristica molto variabile, limitando il numero di riaddestramenti, che sono comunque
abbastanza onerosi in termini di tempo di calcolo e di sforzo computazionale.
60
Capitolo 6
Database di foto
Nel capitolo precedente è stato descritto in poche parole il sistema utilizzato per il
riconoscimento facciale; per le prime versioni sono stati utilizzati due database, il
database ORL e il database FERET.
L‘ORL è stato creato dall‘ Olivetti Research Laboratory dell‘università di Cambridge e
contiene le immagini di volti scattate tra l‘aprile del 1992 e l‘aprile del 1994. Ci sono 10
immagini differenti di 40 soggetti distinti. Per alcuni soggetti le foto sono state scattate in
tempi differenti, con differenti luci ed espressioni del volto (occhi chiusi/aperti, sorridenti
non sorridenti). Tutte le immagini hanno lo stesso sfondo nero, e contengono soltanto il
volto in posizione frontale (con una piccola tolleranza nello spostamento laterale). Tutti i
file sono in formato PNG e hanno una dimensione di 92x112 pixels, con 256 livelli di
grigio.
Il database FERET è un database standard di volti utilizzato per lo sviluppo e il testing
degli algoritmi di riconoscimento. Il programma FERET è sponsorizzato dal dipartimento
della difesa americano attraverso la Defense Advanced Research Projects Agency
(DARPA). Le immagini sono state scattate in 15 sessioni diverse tra l‘agosto del 1993 e
giugno 1996. Ogni sessione durava uno o due giorni. Per mantenere la consistenza delle
immagini di tutto il database la locazione e la posizione dei soggetti è rimasta invariata in
tutte le foto.
Nonostante questi database, si è deciso di crearne un altro, con delle caratteristiche che si
adattino meglio all‘FRS e che apporti dei vantaggi tra i quali:
Nessun problema di licenza
Facilità di aggiornamento
CAPITOLO 6: DATABASE FOTO
61
6.1 Creazione database
Fortunatamente l‘FRS si è dimostrato molto flessibile, quindi c‘è stata ampia possibilità di
scelta delle specifiche tecniche del database.
Il set è composto da poco meno di 700 fotografie; i soggetti per il momento sono 12, 7
maschi e 5 femmine, tutti di età compresa tra i venti e i trent‘anni.
Le foto sono state scattate tutte nella stessa postazione e con la stessa attrezzatura; come
macchina fotografica è stata scelta una Nikon Reflex D60, che permette un vasto range di
opzioni per rendere le foto più aderenti alle nostre specifiche; inoltre è stato usato un
treppiede, per evitare il più possibile il movimento e la sfocatura. Per ampliare
ulteriormente la scelta, è stato deciso di prendere gli scatti in tre posizioni differenti;
frontale , profilo destro e profilo sinistro. In questo modo possiamo avere un solo database,
oppure 3 sottodatabase in base a come vogliamo testare il sistema.
La qualità degli scatti è medio bassa, in quanto non è richiesta un dettaglio altissimo per le
applicazioni in cui il sistema dovrebbe lavorare; inoltre l‘FRS si è dimostrato molto
affidabile anche con questo tipo di dettaglio e in questo modo si risparmia molto spazio di
memoria fisica. Le immagini hanno tutte una risoluzione di 1936 X 1296 pixel; anche se
queste dimensioni sono troppo grandi per il sistema, c‘è la possibilità di ridimensionarle in
pochissimo tempo, e in questo modo non si perde troppo di dettaglio. Ogni immagine
―pesa‖ tra i 200 e i 300 kB, per un impiego di memoria fisica totale di circa 150 MB.
Una volta definite le specifiche tecniche si è passati alla creazione del database; nel
prossimo paragrafo verranno descritte le problematiche principali riscontrate nella
creazione del database
CAPITOLO 6: DATABASE FOTO
62
6.2 Problematiche riscontrate
Nella creazione del set di immagini, a parte i problemi di logistica e di ―reperimento‖ dei
soggetti, abbiamo incontrato 2 problemi tecnici principali:
Cambio di luci ed ombre nello scatto delle foto
Difficoltà di classificazione
Nelle prime immagini scattate, infatti, ci sono stati dei problemi con le ombre del profilo
del volto sullo sfondo neutro utilizzato. L‘FRS considerava le ombre come una parte del
volto, e aveva problemi a riconoscere le immagini. Per risolvere questo inconveniente si è
dapprima cercato di modificare la luce con ulteriori lampade di supporto, purtroppo senza
successo. Infine, avendo riscontrato che non utilizzando il flash (o lampeggiatore)
incorporato nella macchina fotografica le ombre non si proiettavano sullo sfondo, si è
deciso di scattare le foto senza l‘ausilio del flash.
Questo modalità di acquisizione delle immagini ha risolto il problema delle ombre, ma la
non uniformità della luce ha fatto sì che permangano variazioni del colore di sfondo,
dovuto al fatto che ovviamente le immagini sono state scattate a ore diverse, in giorni
diversi, e in condizioni atmosferiche variabili. Comunque la flessibilità del sistema di
riconoscimento facciale è molto elevata, e il cambio di luce sullo sfondo non crea un
problema per il riconoscimento dei volti (come spiegato nel paragrafo 5.2, la divisione del
volto in sezioni permette di isolare i disturbi che non riguardano i contorni delle
immagini). Quindi il primo problema tecnico è stato superato senza ulteriori difficoltà.
Il secondo problema riscontrato non è di carattere puramente tecnico, ma di fruibilità del
sistema. Infatti il database è stato ordinato in 12 cartelle, ognuna delle quali contiene tutte
le foto di un solo soggetto.
I file delle immagini sono nominati con un codice creato dal software della macchina
fotografica, con una sigla iniziale fissa ed un codice numerico sequenziale creato in base
alla data di scatto delle foto (es. DSC_0001 per la prima foto scattata, DSC_0500 per la
cinquecentesima). Rinominare le foto una per una non avrebbe avuto senso, e d‘altro canto
scegliere una a una le foto da inserire nei training set avrebbe un costo di tempo troppo
elevato. Per risolvere questo problema, e contemporaneamente per arricchire di contenuto
CAPITOLO 6: DATABASE FOTO
63
il database, si è scelto di classificare le foto con un software specifico, creando un sistema
di ―tag‖ che renda la selezione e la scelta delle foto molto più rapida.
Il software scelto per l‘etichettatura (o taggatura) delle immagini è Picasa, sviluppato dalla
società Google Inc. Il software è stato scelto per i seguenti motivi:
Licenza freeware
Supporto multipiattaforma (MS Windows, Linux, Mac OS X)
Facilità di utilizzo
Aggiornamento costante
Le immagini sono state etichettate secondo certi parametri: innanzitutto il nome del
soggetto (per evitare problemi si usano le sigle S1, S2, etc.) e il sesso (MX, FM). Un‘altra
etichetta è dovuta alla posizione di scatto della foto: se di profilo (destro o sinistro) oppure
se scattata in posizione frontale (FRONTALE, PR SX, PR DX) e infine le caratteristiche
aggiuntive della foto. Infatti le immagine sono state prima acquisite ―al naturale‖, cioè è
stato scattata una sequenza di foto senza modifiche tra l‘una e l‘altra, che possono servire
per addestrare bene il Face Recognition System, successivamente sono state scattate
immagini con modifiche leggere (capelli legati diversamente, occhiali da vista, barba
leggera). Infine, per testare il sistema in casi particolarmente estremi, sono state prese
immagine di casi limite, in cui il volto è difficilmente riconoscibile. Per queste
caratteristiche aggiuntive sono state aggiunte etichette come BASE, oppure CAPELLI,
CAPPELLO, OCCHIALI.
Etichettare le foto in questo modo ha reso la ricerca delle foto giuste da inserire nel training
set molto più rapida. Infatti è possibile eseguire grazie a Picasa una rapida ricerca in base
alle caratteristiche che si vogliono utilizzare per creare un sotto-database da usare come
training set. Il software crea autonomamente selezioni di foto scelte con particolari ―tag‖,
che possono essere copiate in una cartella specifica creata appositamente.
L‘ultima caratteristica del software (e un altro dei motivi per cui è stato scelto) consiste nel
fatto che con Picasa è possibile creare degli efficienti album online, rendendo fruibile il
database anche a distanza (come scritto nel paragrafo precedente, il peso del sistema è di
150 MB, facilmente trasferibile con le moderne tecnologie di trasferimento dati sul WEB).
64
Capitolo 7
Conclusioni
Con questo lavoro di tesi si è proposto una panoramica sull‘uso dei sistemi ibridi (e in
particolare sull‘utilizzo delle reti neurali) per il riconoscimento dei volti partendo da una
immagine. Come abbiamo visto nell‘introduzione questa tecnica può essere utile in
tantissime applicazioni operative, più o meno approfondite. Questa tesi inoltre propone un
lavoro teorico approfondito sulle reti neurali e sulle loro varianti, sulla logica fuzzy e
sull‘unione di queste due tecniche per la creazione di sistemi ibridi. Infine questo lavoro di
tesi propone una panoramica non approfondita sul sistema di riconoscimento facciale
progettato dal dipartimento, e una descrizione dettagliata del database di foto su cui testare
e migliorare il sistema, del quale sono stato responsabile della creazione e della
classificazione.
Sviluppi futuri
Gli sviluppi futuri possono riguardare sia il sistema di riconoscimento facciale sia il
database di foto. L‘FRS è già una evoluzione di un sistema precedente sempre creato
all‘interno del dipartimento, di cui conserva la stessa struttura ma aggiunge il modulo
fondamentale della retroazione. Comunque un altro passo potrebbe essere quello di
aumentare il numero delle reti neurali, includendo il riconoscimento di nuove
caratteristiche sempre associate al soggetto come il profilo del volto o delle orecchie.
Grazie alla struttura ibrida neuronale simbolica si possono includere nel gruppo delle reti
neurali anche reti specializzate su altre caratteristiche non direttamente collegate con
l'analisi facciale, come l'analisi vocale o delle impronte digitali. In questo modo, inoltre, il
sistema potrebbe analizzare una moltitudine di caratteristiche che non sono influenzate le
une dalle altre, rendendo il riconoscimento ancora più attendibile; ad esempio, la foto di un
volto potrebbe essere tutta sovraesposta o sottoesposta, ciò potrebbe causare problemi a
tutte le reti addestrate al riconoscimento delle immagini, invece se ci fosse anche un
CAPITOLO 7: CONCLUSIONI
65
modulo per l'analisi vocale, il campione audio non sarebbe coinvolto dagli stessi disturbi
che affliggono tutte le immagini, la registrazione vocale in questo caso non soffrirebbe di
alcuna perdita qualitativa e quel modulo identificherebbe in maniera corretta il soggetto.
Per quanto riguarda il database di immagini, invece, abbiamo ritenuto sufficiente per le
nostre esigenze il numero di foto acquisite. In ogni caso, si potrebbe ampliare il numero di
soggetti senza alcuna difficoltà, visto che le specifiche tecniche e il sistema di etichettatura
non sono assolutamente restrittivi. Inoltre il set potrebbe essere ampliato da terzi, tramite il
posizionamento online del sistema. Infine, non bisogna dimenticare che in caso di
difficoltà a reperire soggetti disposti a farsi fotografare, si può sempre utilizzare
programmi di editing quali Photoshop o simili, per creare a partire dai soggetti già presenti,
ulteriori modifiche più o meno evidenti.
Ringraziamenti
Giunto alla fine della stesura di questo lavoro di tesi, mi sembra opportuno e doveroso
esprimere la mia riconoscenza nei confronti di chi mi ha aiutato e supportato in questi anni
di studi universitari.
Innanzitutto desidero ringraziare il Professor Aldo Franco Dragoni, relatore di questa tesi,
per la disponibilità e per l‘aiuto fornito, e l‘Ingegner Germano Vallesi che anche se non
indicato come correlatore, di fatto lo è stato, per i preziosi consigli e la pazienza dimostrata
durante tutto l‘arco di tempo relativo al tirocinio e alla stesura della tesi.
In secondo luogo, desidero ringraziare i miei genitori e i miei parenti per il loro aiuto
morale ed economico grazie ai quali ho potuto raggiungere questo traguardo.
Infine, desidero ringraziare i miei compagni di corso con i quali ho condiviso anni di studio
per preparare gli esami e i vari progetti, e gli amici di una vita con i quali sono cresciuto,
che non mi hanno mai fatto mancare il loro sostegno; è anche grazie a loro se sono riuscito
a raggiungere questo obiettivo.
Bibliografia
[1] R. Chelappa, P.J. Philipd, A. Rosenfeld, W. Zhao, Face Recognition: A
Literature Survey.: ACM Computing Surveys, 2003.
[2] M. Nappi, D. Riccio, G. Santino, A.F.Abate, 2D and 3D Face recognition: A
Survey.: Elsevier B.V., 2007.
[3] C. Wilson, S. Sirobey, R. Chelappa, Human and machine recognition of faces:
A Survey.: IEEE, 1995.
[4] K. Kim, Face Recognition using Principle Component Analysis.: Elsevier B.V.
[5] K. Baek,M. Stewart Bartlett, J.Ross Beveridge, B.A. Draper, Recognizing
Faces with PCA and ICA.: Computer Vision and Image Understunding, 2003.
[6] A.P. Pentland, M.A. Turk, Face Recognition using Eigenfaces.: IEEE, 1991.
[7] A. Pentland, B. Moghaddam, An Automatic System for Model-Based Coding of
Faces.: IEEE, 1995.
[8] S.B. Yung, J.W. Kwon, S.H.Hong, S.J.Lee, Face Detection and Recognition using
PCA.: IEEE, 1999.
[9] M.H. Hayes, A.V. Hefian, Hidden Markov Model for Face Recognition., 1998.
[10] O.E. Agazzi, S.S. Kuo, Keyword spotting in poorly printed documents., 1994.
[11] T.Kohonen, Self-organization and associative memory: 3rd edition.:
Springer-Verlag, 1989.
[12] L. Fausett, Fundamentals of Neural Networks.: Prentice-Hall, 1994.
[13] Yu Chi Ho, A.E. Bryson, Applied optimal control : optimization, estimation
and control.: Halsted Press, 1975.
[14] P. Norvig, S. Russel, Artificial Intelligence: A Modern Approach.: PrenticeHall, 2003.
[15] T. Kohonen, The Basic SOM "Self-Organizing Maps". Berlin: Springer.
[16] B. Fritzke, Growing cell structures - a self-organizing network for
unsupervised and supervised learning, Neural Networks., 1994.
[17] T. Kohonen, Learning Vector Quantization. Berlin: Springer.
[18] Y. Li D. Zhang, Modular Neural Networks and Their Applications in
Biometrics. Berlin: Springer, 2007.
[19] L.A. Zadeh, "Fuzzy Set. Information and Control," vol. 8, pp. 338-353, 1965.
[20] L.A.Zadeh, "Fuzzy Algorithms," pp. 94-102, 1968.
[21] B. Kosko, Il fuzzy-pensiero. Teoria e applicazioni della logica fuzzy. Milano:
Baldini & Castoldi, 2000.
[22] A. Visoli, M. Veronesi, Logica Fuzzy: teoria e applicazioni. Milano: Franco
Angeli, 2000.
[23] P. Sconciafurno, "Sistema ibrido per l'apprendimento continuo di reti
neurali," , Ancona, 2009.
[24] C. Cayrol, D. Dubois, J. Lang,H. Prade, S. Benferhat,.: Morgan Kauffman,
1993, pp. 640-645.