Figura 1. Esempio di dati estratti dal database MNIST.
Per il corso di Sistemi Intelligenti (prof. Sperduti, A.A. 2007/2008, Università degli Studi di Padova) è stato sperimentato ed implementato un sistema che consente il riconoscimento di cifre manoscritte. Le soluzioni sono state sviluppate tramite la tecnologia FANN in linguaggio C.
Il riconoscimento automatico di cifre manoscritte è un importante problema, che si può riscontrare in molte applicazioni pratiche. Alcuni esempi di applicazioni di questa tecnica:
Ci sono stati diversi progressi, negli ultimi anni, in questo settore, principalmente dovuti all'introduzione di nuovi algoritmi per l'apprendimento, la disponibilità di nuovi training set sui quali poter fare l'apprendimento e, non in ultima istanza, l'aumento della potenza di calcolo a disposizione sui computer moderni.
Sia per l'apprendimento, sia per la validazione dei dati di input è stato utilizzato un archivio di immagini molto conosciuto nel settore: “The MNIST database of handwritten digits”. Questo è costituito da un training set di 60000 esempi, più un test set di 10000. Un esempio di dati, così come sono memorizzati nel file degli esempi è riportato in Figura 1.
Figura 1. Esempio di dati estratti dal database MNIST.
Il database originario è stato costruito dal NIST (National Institute of Standards and Technology). Le immagini di partenza erano in bianco e nero, ma successivamente, al fine di normalizzarle alla dimensione di 20×20 pixel, sono stati introdotti dei livelli di luminosità intermedi, dovuti all'effetto di anti-aliasing del filtro per il ridimensionamento. Successivamente, sono state centrate, nel centro di massa dei pixel, in un'area di 28×28 px, al fine di migliorare il processo di apprendimento.
L'intero databse è memorizzato in due file: uno contenente l'insieme con tutti i dati, ed uno con tutte le etichetti; i valori aspettati corrisponderanno all'immagine nella stessa posizione: l'immagine i-esima (ovvero quella che corrisponde all'insieme di 28×28 byte posti ad i×(28×28) dall'inizio del file con gli esempi) avrà come valore aspettato il valore i-esimo (ovvero il valore posto ad i posizioni dall'inizio del file delle etichette). La codifica del file con le etichette, così come quella del file con le immagini è decisamente semplice da essere utilizzata: i dati sono stati salvati come fosse un dump (ad eccezione di un breve header contenente il numero di esempi campionati e, per le immagini, il numero di righe e di colonne) in modo da facilitare al massimo la loro lettura, una volta conosciuta la codifica. Il file delle etichette è costruito in questa maniera:
[offset] [type] [value] [description] 0000 32 bit integer 0x00000801(2049) magic number (MSB first) 0004 32 bit integer 60000 number of items 0008 unsigned byte ?? label 0009 unsigned byte ?? label ... xxxx unsigned byte ?? label
Il file con gli esempi, invece, è strutturato secondo questo schema:
[offset] [type] [value] [description] 0000 32 bit integer 0x00000803(2051) magic number 0004 32 bit integer 60000 number of images 0008 32 bit integer 28 number of rows 0012 32 bit integer 28 number of columns 0016 unsigned byte ?? pixel 0017 unsigned byte ?? pixel ... xxxx unsigned byte ?? pixel
Come suggerito in [Russel03], si è sperimentalmente osservato che i risultati migliori si ottengono con una rete neurale costituita da un neurone in input per ciascun pixel dell'immagine da analizzare, un livello di neuroni nascosti con 300 unità e 10 neuroni in output (uno per ciascuna delle cifre in output).
Una rappresentazione grafica della rete che è stata modellata è riportata in Figura 2.
Figura 2. Struttura della rete neurale.
Dato che le immagini sono codificate in scala di grigi, ciascun pixel è rappresentato dal livello di luminosità in quel determinato punto. L'input per il neurone è quindi facilmente realizzabile, semplicemente considerando il valore del pixel come un intero. Come già detto, successivamente, il livello di input è connesso a 300 neuroni nascosti i quali, a loro volta, sono tutti collegati a 10 neuroni di output, ciascuno dei quali rappresenta la probabilità che l'input fornito alla rete rappresenti la cifra in considerazione.
Entrambe le sperimentazioni tecnologiche del problema sono state fatte utilizzando le librerie FANN (Fast Artificial Neural Networks).
Le librerie FANN sono un software free e open source per lo sviluppo di reti neurali multilayer. Sono scritte in C, e sono pensate per supportare sia reti fully connected, sia sparsely connected, inoltre sono cross-platform e adatte all'uso sia di valori interi che in virgola mobile, questa libreria, inoltre, comprende un framework per la gestione semplificata dei training set. Esistono porting per questa libreria in molti linguaggi, fra i quali: PHP, C++, .NET, Ada, Python, Delphi, Octave, Ruby, Prolog Pure Data e Mathematica. D'ora in avanti, si farà sempre riferimento alla versione originale della libreria, scritta in C. La documentazione è molto ben strutturata ed esauriente, ed è suddivisa per package. È correlata da un insieme di tutorial ed esempi che ne illustrano tutte le fasi del ciclo di vita, dall'installazione all'uso.
Gli algoritmi di apprendimento, che le librerie FANN implementano sono:
L'intero progetto è costituito da più software, ciascuno dei quali è orientato verso una attività specifica. In totale sono stati realizzati cinque programmi:
$ ./test Test della Rete =============== +----------------------------+ | | | | | | | | | ..XXXXXXX. | | XXXXXXXXX.. | | ..XXXX.. | | .XXXX | | .XX.. | | XXX. | | .XX....... | | XXXXXXXXXX. | | .XXXXXXXXXXX. | | . .XXXX | | XXX | | .XXX | | XXX. | | ..XXX. | | ... .XXXXXX. | | XXXX...XXXXXX.. | | .XXXXXXXXXXX.. | | XXXXXXXXXX. | | .XXXXXXX.. | | ..XXX.. | | | | | | | | | +----------------------------+ P(0) = 0.060623; P(1) = 0.114797; P(2) = 0.060783; P(3) = 0.083447; P(4) = 0.0134032; P(5) = 0.802559; P(6) = 0.0718292; P(7) = 0.0376242; P(8) = 0.029419; P(9) = 0.0565661; *** CORRETTO *** Esempio numero 35267 Aspettato: 5 Calcolato: 5
Per effettuare l'apprendimento, si è osservato che l'algoritmo Backpropagation è molto più lento di Quickprop, tuttavia, quando l'errore comincia ad essere sufficentemente basso, il primo si comporta decisamente meglio del secondo. Per questo motivo, si è pensato di combinare i due e di utilizzare Quickprop per raggiungere con estrema rapidità dei primi risultati grezzi, che sono poi stati raffinati tramite Backpropagation.
L'algoritmo Quickprop, secondo quanto l'autore dello stesso riporta in [Fahlman88], si differenzia dal Backpropagation nella funzione che ricalcola i pesi. La nuova funzione, infatti, assume che la funzione errore sia una parabola e calcola, di conseguenza, la derivata seconda al fine di raggiungere rapidamente il minimo della parabola stessa. Il gradiente è calcolato in questa maniera (con S si fa riferimento alla derivata parziale):
È stato provato anche un approccio differente al problema. Per ogni cifra si è costruito una rete a tre layer: un neurone di input per ogni pixel dell'immagine della cifra, da 20 a 80 neuroni nel layer nascosto e un unico neurone di output. La singola rete apprende a riconoscere la cifra associata: per esempio la rete associata alla cifra cinque apprende a restituire uno se la cifra in input è un cinque e zero altrimenti. Per riconoscere una cifra si calcola l'output delle diverse reti per una stessa immagine e la cifra riconosciuta è quella associata alla rete che ha l'output più alto.
Anche il software scritto per realizzare questo approccio è in C e fa uso della libreria FANN. I tool principali sono i seguenti:
Per ogni cifra si crea (con il programma create) una rete con 784 input, un opportuno numero di neuroni nascosti e un unico output. Ogni rete apprende con il programma train il database creato dalla seconda modalità di convert.py per un numero opportuno di epoche. A questo punto si può testare la bontà delle reti ottenute con test-final. Per automatizzare questo procedimento sono stati scritti anche alcuni shell script che combinano i tool di base.
In questa sezione verranno commentati i risultati ottenuti in base alle due tecnologie che si ha avuto modo di sperimentare, includendo alcuni commenti personali sugli strumenti che si sono usati.
Come già descritto pocanzi, nell'esempio che è stato realizzato tramite le librerie FANN sono stati utilizzati più algoritmi di apprendimento, alcune volte anche incrociandoli fra loro, al fine di migliorare le prestazioni. Si riportano, di seguito alcuni dei risultati raggiunti.
Tutti i vari test prevedevano il cambiamento solo dell'algoritmo di apprendimento, la struttura e la topologia della rete sono rimaste invariate. Anche il training set non è cambiato da ciascun test: esso è composto da un sottoinsieme del training set originario, in particolare contiene 30000 esempi, ovvero circa 3000 esempi per ciascuna delle cifre da apprendere.
In particolare, una rete, è stata allenata per un lungo periodo, nel provare diverse configurazioni. Tramite questa, è possibile raggiungere risultati che arrivano anche al 95/96% di esempi classificati correttamete. In [Russel03] si dice che, con questa struttura, si deve riuscire ad arrivare a risultati ancora maggiori: 98.4%. Data la brevità dei tempi di apprendimento accettati per questa sperimentazione, si pensa sia possibile raggiungere risultati come quelli promessi del citato articolo semplicemente aumentando il numero di epoche a disposizione dell'algoritmo. In [Russel03], infatti, il risultato è raggiunto con 7 giorni di apprendimento, e sfruttando l'intero training set.
Il primo test è stato fatto utilizzando l'algoritmo Backpropagation, nella sua variante batch, ovvero calcolando lo scarto quadratico dopo aver valutato tutti gli esempi.
| Esempi analizzati: | 30000 |
|---|---|
| Epoche apprendimento: | 200 |
| MSE raggiunto: | 0.01315 |
| Errori sul validation set: | 2101 su 2500 = 84% classificati correttamente |
| Tempo apprendimento: | ~1h 5m |
Rappresentazione dell'errore commesso dall'algoritmo nelle prime 200 epoche
Il secondo test è stato fatto utilizzando l'algoritmo Backpropagation, nella sua variante incrementale, ovvero calcolando lo scarto quadratico per ciascun esempio del training set.
| Esempi analizzati: | 30000 |
|---|---|
| Epoche apprendimento: | 173 |
| MSE raggiunto: | 0.04699 |
| Errori sul validation set: | 1792 su 2500 = 71% classificati correttamente |
| Tempo apprendimento: | ~17h |
Rappresentazione dell'errore commesso dall'algoritmo nelle prime 200 epoche
Il terzo test è stato fatto utilizzando l'algoritmo Quickprop. Questo esempio si riferisce ad uno con momentum a 0,9.
| Esempi analizzati: | 30000 |
|---|---|
| Epoche apprendimento: | 200 |
| MSE raggiunto: | 0.01094 |
| Errori sul validation set: | 2209 su 2500 = 88% classificati correttamente |
| Tempo apprendimento: | ~1h 20m |
Rappresentazione dell'errore commesso dall'algoritmo nelle prime 200 epoche
Il quarto, ed ultimo, test è stato fatto utilizzando l'algoritmo Quickprop, per le prime 50 epoche, poi, per 150 epoche, è stato usato Backpropagation, nella sua variante batch.
| Esempi analizzati: | 30000 |
|---|---|
| Epoche apprendimento: | 50 + 150 |
| MSE raggiunto: | 0.02107, 0.01300 |
| Errori sul validation set: | 2301 su 2500 = 92% classificati correttamente |
| Tempo apprendimento: | ~20m + ~1h = ~1h 20m |
Rappresentazione dell'errore commesso dall'algoritmo nelle prime 200 epoche
Sono state testate reti con 20, 30, 40, 60, 80 e 120 neuroni nascosti. L'apprendimento è stato per tutte di sole 60 epoche perché già dopo qualche decina di epoche si notavano fenomeni di overfitting o comunque l'apprendimento non procedeva sensibilmente. L'algoritmo backpropagation incrementale, che non funzionava nell'approccio con rete unica, si è rivelato veloce e stabile. Questa differenza si può ipotizzare dipendere dalla maggiore semplicità della funzione che approssimiamo, dato che deve riconoscere una sola cifra alla volta.
L'apprendimento è stato veloce, grazie alla convergenza rapida:
| Neuroni nascosti | Durata apprendimento |
|---|---|
| 20 | 14m 25s |
| 40 | 28m 2s |
| 60 | 41m 38s |
| 80 | 58m 25s |
| 120 | 94m 45s |
La tabella seguente mostra la percentuale di errore raggiunta dalle singole reti nel riconoscere la cifra corrispondente al variare del numero di neuroni nascosti. Le percentuali sono a coppie: la prima è la rete ottenuta alla fine dell'apprendimento e la seconda è quella che durante l'apprendimento ha raggiunto la precisione migliore. Come si vede il risultato migliore non è sempre raggiunto dalla rete con più neuroni nascosti: alcune cifre sono riconosciute meglio da reti più piccole, mentre altre cifre non sono riconosciute efficacemente neanche dalle reti più grandi. Questo indica come la difficoltà di riconoscere una cifra fortemente dalla rappresentazione grafica della stessa.
| Cifra | 20 fin/min | 30 fin/min | 40 fin/min | 60 fin/min | 80 fin/min | 120 fin/min |
|---|---|---|---|---|---|---|
| 0 | 2.20/1.55 | 1.66/1.50 | 1.71/1.61 | 1.18/1.18 | 1.71/1.71 | 2.63/1.61 |
| 1 | 1.34/1.02 | 1.39/1.44 | 1.39/1.06 | 1.25/1.11 | 1.39/1.20 | 1.34/1.39 |
| 2 | 3.93/3.57 | 3.11/3.11 | 3.36/3.16 | 3.36/3.36 | 3.01/3.11 | 3.47/3.21 |
| 3 | 5.10/4.63 | 4.95/4.11 | 6.09/5.52 | 5.21/4.58 | 4.89/5.15 | 4.79/4.37 |
| 4 | 3.32/3.00 | 3.32/3.27 | 3.37/3.05 | 3.59/3.59 | 4.13/3.21 | 3.43/3.48 |
| 5 | 4.48/4.48 | 3.83/3.60 | 3.89/4.07 | 4.31/4.43 | 4.66/3.89 | 4.31/4.48 |
| 6 | 2.81/2.70 | 2.59/2.48 | 3.03/2.81 | 3.08/2.86 | 3.14/3.08 | 2.48/2.42 |
| 7 | 2.92/2.92 | 2.51/2.62 | 3.39/3.39 | 2.98/2.98 | 3.69/3.13 | 3.08/3.03 |
| 8 | 6.93/6.65 | 7.03/6.82 | 6.38/5.46 | 7.47/6.98 | 6.60/6.22 | 7.14/6.82 |
| 9 | 5.91/6.12 | 6.60/6.23 | 6.96/5.81 | 6.23/6.02 | 7.07/7.17 | 6.12/5.81 |
La tabella seguente mostra la precentuale di errore raggiunta nel riconoscimento cifre usando dieci reti della stessa dimensione. Anche qui i risultati sono a coppie, un valore per le reti ottenute alla fine dell'apprendimento e una per quelle con l'errore minimo. La precisione migliore è raggiunta dalle dieci reti con 30 neuroni nascosti, quindi un numero di neuroni comparabili con quello usato nell'approccio a rete singola.
| 20 | 30 | 40 | 60 | 80 | 120 | |
|---|---|---|---|---|---|---|
| Precisione | 4.83 | 4.33 | 4.32 | 4.50 | 4.54 | 4.44 |
| Precisione(min) | 4.38 | 4.09 | 4.14 | 4.32 | 4.47 | 4.46 |
Per quanto riguarda la risoluzione del problema tramite le librerie FANN, l'esperienza è stata estremamente positiva: la potenza della tecnica delle Reti Neurali è stata addomesticata tramite queste librerie estremamente potenti e relativamente facili da utilizzare. È stato entusiasmante osservare sperimentalmente la piena riuscita della risoluzione del problema, tramite l'applicazione diretta delle tecniche teoriche viste durante il corso.
È stato possibile rendersi conto in maniera abbastanza rilevante della versatilità e delle potenzialità delle Reti Neurali e, dopo l'iniziale stupore sulla loro estrema efficacia si è cercato di capirne a fondo il loro funzionamento e le particolari sfumature degli algoritmi di apprendimento.
Ultima modifica al documento: 29 giu 2008.