Il modello Poe per la sintesi di reti neurali

Il modello POE per la sintesi di reti neurali                                                         1 INTRODUZIONE 
Genetico (per l’evoluzione della specie delle reti neurali), un L-system (per 
lo sviluppo dell’individuo rete neurale) e l’EBP (Error Back Propagation, 
per l’apprendimento della rete neurale). 
Prendendo spunto dal lavoro di Boers e Kuiper [1] e di Sipper [2], in questa 
tesi, si è analizzato un metodo per la generazione automatica di reti neurali 
multi-level feed-forward. Il lavoro si suddivide in due fasi.  
 
 
 
 
Fig 1b Diagramma a blocchi della prima fase del lavoro di tesi 
 
La prima fase è consistita nell’analisi del piano OE (Fig. 1b), individuando 
una grammatica (L-System) in grado di rappresentare un generico individuo 
di rete neurale multi-level feed-forward. Individuata la grammatica, in grado 
di generare un numero indeterminato di reti neurali per diversi problemi 
come Xor e Parità a 4, si è cercato un modo per rappresentarle 
numericamente nell’algoritmo di addestramento EBP. Verificata la possibilità 
di addestrare le reti neurali generate dalla grammatica L-System considerata 
in partenza, nella seconda fase del lavoro di tesi, si è integrato un algoritmo 
L-system 
Rete Neurale 
Il modello POE per la sintesi di reti neurali                                                         1 INTRODUZIONE 
genetico (analisi spaziale POE) per generare automaticamente un L-system 
per individuare una rete neurale migliore rispetto alle altre secondo prefissati 
attributi associati alle reti quali ad esempio numero di neuroni, errore 
commesso ecc... 
In questo modo si e’ realizzata una catena ciclica costituita dalle 
seguenti parti: Algoritmo Genetico, L-System e Rete neurale (Fig 1). 
 
 
 
 
 
 
Fig.1  Diagramma a blocchi della seconda fase  del lavoro di tesi 
 
Tale processo, ripetuto per un numero finito di volte cercherà la soluzione 
migliore rispetto a quelle precedenti.  
Algoritmo Genetico 
L-system 
Rete Neurale 
Il modello POE per la sintesi di reti neurali                                          2 GRAMMATICHE L-SYSTEM 
2. GRAMMATICHE L-SYSTEM 
 
Prima di definire la grammatica L-System è necessario dare qualche 
informazione generica sulle grammatiche. 
2.1. Le Grammatiche 
Una grammatica serve a descrivere un linguaggio, ad esempio si ha quella 
che descrive la lingua italiana, quella descrive il linguaggio di 
programmazione Pascal e così via. 
Formalmente una grammatica si definisce nel seguente modo: 
Una grammatica G è una quadrupla (X, V, S, P), dove: 
- X è detto alfabeto dei simboli terminali e rappresenta l’insieme dei 
simboli che la grammatica descrive. 
- V è detto alfabeto dei simboli non terminali. 
- S è detto simbolo di partenza, o anche assioma della grammatica. S 
appartiene all’insieme dei simboli non terminali ed è il simbolo da cui partire 
nella derivazione delle frasi del linguaggio. 
- P è detto insieme delle produzioni e rappresenta le regole che permettono 
di derivare le frasi del linguaggio L (G) (con L (G) si indica l’insieme delle 
frasi che è possibile derivare da G utilizzando P). 
Il modello POE per la sintesi di reti neurali                                          2 GRAMMATICHE L-SYSTEM 
Un esempio di grammatica è il seguente: 
X = { ( , ) } 
V = { S } 
P = {  1.S → ()  
          2.S → (S)  
          3.S → SS  
} 
Questa grammatica genera frasi del seguente tipo: 
(), (( )), (( ... )), (( ... )( ... )), ... 
Infatti se si vuole derivare la parola “(()())” si procede in questo modo: 
S => (S) => (SS) => (()S) => (()()). 
Per eseguire questa derivazione sono state utilizzate nell’ordine le produzioni 
n. 2 - 3 - 1 - 1. 
Tale grammatica descrive il cosiddetto linguaggio delle parentesi ben 
formate. Esistono diversi tipi di grammatica a seconda il modo di comporre 
le regole di produzione. Nel 1956 Chomsky ne diede una classificazione 
gerarchica. 
1) Grammatiche di tipo 0: 
Il modello POE per la sintesi di reti neurali                                          2 GRAMMATICHE L-SYSTEM 
    a questa classe appartengono le grammatiche le cui produzioni sono del 
tipo: 
  v → w     dove     w∈(X∪V)*   e   v∈(X∪V)+ 
2) Grammatiche di tipo 1 (dette anche: dipendenti dal contesto): 
    a questa classe appartengono le grammatiche le cui produzioni sono del 
tipo: 
A∈V 
  yAz → ywz     dove     (y,z)∈(X∪V)*  e  w∈(X∪V)+ 
 oppure: 
  S → λ   purché S non compaia a destra di qualche produzione. 
3) Grammatiche di tipo 2 (dette anche: libere dal contesto): 
    a questa classe appartengono le grammatiche le cui produzioni sono del 
tipo: 
  v → w     dove     v∈V  e  ∈(X∪V)* 
4) Grammatiche di tipo 3 (dette anche: lineari destre): 
    a questa classe appartengono le grammatiche le cui produzioni sono del 
tipo: 
  A → bC     dove     A,C∈V     e     b∈X 
Il modello POE per la sintesi di reti neurali                                          2 GRAMMATICHE L-SYSTEM 
 oppure 
  A → b      dove     A∈V        e      b∈X∪{λ} 
Da questa classificazione gerarchica si può dimostrare che, indicando con Li  
per i=0...3 la classe del linguaggio descritto dalla grammatica di tipo i, che: 
L3   ⊆  L2   ⊆  L1   ⊆  L0 
Dato qualche cenno di teoria delle grammatiche si passa a definire alcuni 
concetti riguardanti gli L-System. 
2.2. Definizione e tipi di grammatiche L-system 
Gli L-system sono stati proposti nel 1968 da A. Lindenmayer come un caso 
di studio per lo sviluppo di semplici organismi unicellulari per poi 
investigare le piante. 
Le piante hanno, nella maggior parte dei casi, una forma quasi simmetrica. 
La struttura del tipo di rete neurale che stiamo considerando ha, pure, una 
forma quasi simmetrica ed è quindi ovvio cercare di applicare i principi di 
un L-system per la loro generazione. 
Un L-system, per definizione, è una terna G = (V, ω , P) 
dove 
 V è un alfabeto 
Il modello POE per la sintesi di reti neurali                                          2 GRAMMATICHE L-SYSTEM 
 P ⊂ VxV* ciò significa che ad ogni elemento v∈V si associa una 
frase          x∈V*. 
 ω  è lo scopo, oppure assioma, della grammatica e ω∈V+. 
Una produzione (a,χ)∈P si denotata con   a → χ. 
Definiamo ora il concetto di derivazione di un L-system. 
Consideriamo µ = a1....am come arbitraria parola sull’insieme V. 
La parola v=χ1...χm ∈V* è direttamente derivata da (oppure generata da) µ, 
denotato con µ => v, se e solo se ai → χi per i=1.m. 
Esistono diversi tipi di L-system: 
2.3. DOL-System 
Queste grammatiche hanno la caratteristica di essere deterministiche e 
context-free da ciò il nome DOL-System. 
Il significato di context-free è lo stesso visto per le grammatiche di 
Chomsky, mentre il determinismo è dovuto al fatto che per ogni simbolo di 
V esiste una ed una sola regola di riscrittura. 
Se non si considera il determinismo, si possono avere più regole di 
riscrittura per ogni simbolo, tali grammatiche si chiamano OL-system. Un 
banale esempio di DOL-system è il seguente: 
  ω : a 
Il modello POE per la sintesi di reti neurali                                          2 GRAMMATICHE L-SYSTEM 
  p1: a → ab 
  p2: b → a 
In quest’esempio si può constatare che ogni elemento dell’alfabeto {a,b} è 
riscritto solo con una regola di produzione. 
2.4. Stochastic L-system 
Una stochastic OL-system è una quadrupla Gpi = (V, ω , P, pi). 
L’alfabeto V, l’assioma ω  e l’insieme delle produzioni P sono definiti come 
in una OL-system. La funzione pi: P → (0,1], chiamata distribuzione di 
probabilità, associa ad ogni produzione una probabilità. Si assume che ad 
ogni lettera a di V, la somma delle probabilità delle produzioni che hanno 
come parte sinistra la a  sia uguale a 1. 
Un semplice esempio di Stochastic L-system è il seguente: 
  ω : A 
  p1: A →(.33) A 
  p2: A →(.33) AA 
  p3: A →(.33) AAA 
Ogni produzione può essere selezionata con una probabilità prossima ad 
1/3. 
Il modello POE per la sintesi di reti neurali                                          2 GRAMMATICHE L-SYSTEM 
2.5. Context-sensitive L-system 
Le produzioni in OL-system sono libere da contesto. 
Negli L-system le regole di produzione sono applicate considerando il 
contesto precedente. Esistono diversi tipi di context-sensitive L-system. Il 
2L-system utilizza produzioni nella seguente forma: 
  al < a > ar → χ , 
dove la lettera a può produrre la parola χ se e solo se è preceduta dalla 
lettera al  seguita dalla lettera ar .In questo modo le lettere al  e ar formano 
rispettivamente il contesto sinistro e destro di quella produzione. 
Gli 1L-system hanno il contesto solo da un lato, il sinistro oppure il destro, 
perciò le regole di produzione hanno la seguente forma: 
  al < a → χ , 
  a > ar → χ . 
Le grammatiche L-system context-sensitive 1L-system e 2L-system si usa 
indicarle con IL-sysstem. 
E’ possibile rendere gli L-system parametrici, individuando così un nuovo 
tipo di L-system che non è descritto in questa sede. 
2.6. Differenze tra le grammatiche di Chomsky e gli 
 L-system 
La sostanziale differenza tra le grammatiche di Chomsky e gli L-system è nel 
Il modello POE per la sintesi di reti neurali                                          2 GRAMMATICHE L-SYSTEM 
modo di applicare le regole di produzione. Nelle grammatiche di Chomsky 
le regole di produzione sono applicate in sequenza, mentre negli L-system 
sono applicate in parallelo e simultaneamente sostituendo tutte le lettere in 
una data parola. Un’altra differenza tra le grammatiche di Chomsky e gli L-
system è che per questi ultimi non esiste una stringa finale, che indica 
quando fermarsi, non essendoci l’insieme dei simboli terminali. Il criterio di 
stop è costituito da un numero massimo di cicli. La Fig.2 mostra la relazione 
tra la classe dei linguaggi di Chomsky e quella delle grammatiche L-system. 
Il modello POE per la sintesi di reti neurali                                          2 GRAMMATICHE L-SYSTEM 
 
 
 
 
 
 
 
 
  
 
 
Fig.2 Relazione tra la classe dei linguaggi di Chomsky e la classe dei linguaggi generati dagli L-system. 
I simboli OL e IL denotano le classi dei linguaggi generati rispettivamente da L-system liberi da contesto 
e contestuali. 
 
2.7. Utilizzo degli L-system 
In questa tesi è utilizzato uno Stochastic OL-system. 
Osservando la struttura di una rete neurale si possono distinguere tre strati: 
input, hidden, output. Gli strati input e output sono costituiti da un solo 
livello mentre lo strato hidden può essere formato da un numero di livelli 
OL 
Finite 
Regular 
IL 
Context -free 
Context -sensitive 
Recursively enumerable 
Il modello POE per la sintesi di reti neurali                                          2 GRAMMATICHE L-SYSTEM 
imprecisato. Questa considerazione è stata utilizzata nella ricerca di un L-
system affinché fosse il più generale possibile. Con ciò si intende affermare 
che lo stesso L-system possa essere utilizzato per cercare reti neurali che 
risolvono, in teoria, tutti i problemi.  
Infatti, si è pensato di costruire tre L-system diversi uno per ogni strato. 
E’ ovvio che un L-system con una formulazione più semplice è quello 
riguardante l’output mentre quello più complesso è l’hidden. 
Prima di presentare gli L-system costruiti è necessario dare un esempio di 
come sarà codificata la struttura di una rete neurale. 
Consideriamo come esempio il problema del Xor. 
Si è verificato che una delle strutture della rete neurale che risolve il 
problema del Xor è la seguente: 
Il modello POE per la sintesi di reti neurali                                          2 GRAMMATICHE L-SYSTEM 
STRATO  HIDDEN 
STRATO  INPUT 
 
 
 
 
  
 
Fig. 3 Struttura di una rete neurale che risolve il problema del Xor. 
 
Come si può osservare dalla Fig. 3, gli input della rete sono completamente 
connessi con i nodi hidden con ciò s’intende che ogni nodo input è 
collegato ad ogni nodo hidden. Lo stesso discorso vale per i nodi hidden 
che sono completamente connessi con il nodo di output. 
Il problema è quello di cercare un metodo per rappresentare la struttura di 
una rete neurale. L’operazione più semplice che si può pensare è quella di 
costruire una specie di codice che possa rappresentare in maniera univoca 
una rete neurale. 
Bisogna stabilire alcuni principi: 
1) il codice va letto da sinistra verso destra e la codifica della rete va fatta 
dal basso verso l’alto; 
2) attribuire ad ogni nodo una lettera che l’identifichi come nodo che non sia 
a 
a a 
a STRATO  OUTPUT 
a 
Il modello POE per la sintesi di reti neurali                                          2 GRAMMATICHE L-SYSTEM 
necessariamente la stessa; 
3) se due nodi non sono collegati nel codice essi sono separati da una 
virgola; 
4) Si definisce salto di n il numero n di nodi che si ignorano, scandendo la 
stringa codificata da sinistra verso destra. 
5) un nodo può effettuare all’interno del codice un salto, rappresentato da 
una cifra accanto alla lettera. 
6) due nodi possono essere collegati in due modi: 
 - collegamento diretto, se i due nodi sono affiancati 
 - collegamento da salto, se un nodo precedente effettua un salto per   
   collegarsi 
7) Si individua l’entità modulo se alcuni nodi hanno delle caratteristiche in 
comune, come ad esempio i nodi con cui sono collegati. Il modulo è 
individuato tra parentesi quadre. 
8) Tutte le regole prima definite per i nodi sono valide anche per i moduli 
prestando attenzione ai loro collegamenti poiché sono insiemi di nodi.  
Date le regole che definiscono il codice si può codificare la rete Xor prima 
illustrata. 
Ogni nodo di input della rete è collegato ad ogni nodo dello strato hidden ed