Apprendimento per rinforzo
..e algoritmi genetici
Definizione del problema:
• Non sempre è possibile modellare un problema di
apprendimento come la scelta ottimale di una funzione di
classificazione
• L’apprendimento per rinforzo modella (tipicamente) il caso di un
agente che percepisce ed agisce in un certo ambiente, il cui
obiettivo è di imparare a fare “la cosa ottimale” , o la cosa che lo
avvicina di più al suo obiettivo, dato un certo stato dell’ambiente
• Robotica, web assistent, in generale , sistemi ad agenti
Modello
Un agente si muove in un ambiente
rappresentabile mediant e un insieme S di stati;
L'agente è in g rado di percepire un vettore di
ingresso, o per cezione e, che informa l'agente
circa lo stato Xi in cui si trova.
A è un insieme di azioni eseguibili dall'agente.
L'esecuzione di un'azione ai di A produce una
transizione di stato. R è un insieme di ricompense
che l'agente può ricevere:
ri=r(ei,ai) ri  R, aiA , ei=f(Xi),
Modello (2)
L'obiettivo di apprendimento per rinforzo
consiste nell'identificare una politica ottima (X)
X A che massimizzi le ricompense accumulate
nel tempo.
Xi
ri
Sistema di
apprendimento
ai
Ambiente
a0
a1
a2
X 0 
r X1 
r X 2 
r .....
0
1
2
Varianti
• Ricompensa ritardata: a volte la ricompensa non corrisponde a
singole azioni, ma al raggiungimento di qualche obiettivo o
sotto-obiettivo (es. per il robot calciatore: fare goal, o una
“bella” azione)
• Esplorazione: l’apprendista può restare all’interno di ambienti
(stati) noti, o può decidere di esplorare stati non noti
• Percezioni parziali: l’agente può non percepire l’intera realtà
(ad esempio, degli ostacoli visivi non consentono di percepire
interamente una scena)
Il compito di apprendimento
• Apprendere una politica  XA tale che sia possibile
accumulare la ricompensa maggiore nel tempo (secondo , per
ogni stato X è data un’azione , e dunque lo stato successivo)
• Definiamo V  (Xt ) come il valore cumulativo acquisito tramite
una politica arbitraria partendo da uno stato arbitrario Xt:
 i
V ( Xt )    rt i
i 0

• 01 è una costante che determina il valore relativo di
ricompense non immediate. Ad esempio, se una ricompensa
(rt+i), è ricevuta dopo i passi dall’attuale stato, viene “scontata”
di un fattore i.
*  arg max V  ( X), X

• Il compito di apprendimento è definito dalla:

Es: Apprendimento passivo in ambiente noto.
3
+1
2
-1
1
START
1
2
3
4
1.0
0.5
0.5
0.33
0.33
0.33
1.0
• Un esempio: un robot deve
muoversi in una scacchiera.
Le azioni possibili sono n, s,
e, o (nord,sud, est,ovest)
• Lo stato (1,1) è lo stato di
partenza, (3,4) e (2,4) sono
terminali con ricompense +1
e -1. Lo stato (2,2) è
inaccessibile. In ogni stato le
probabilità di transizione
sono uguali. Le percezioni
coincidono con
l'identificazione dello stato in
cui il robot si trova.
Q-learning
• Ogni casella rappresenta uno stato, ogni mossa è un’azione.
• La funzione r(X,a) fornisce una ricompensa solo negli stati in
cui essa è prevista, e zero in tutti gli altri stati.
• Indichiamo con (X,a) lo stato in cui il sistema transita se parte
da X e esegue l’azione a *
*


 (X)  argmax r(X,a)  V ( ( X,a))
a
Dove V* è un’abbreviazione per V*
• Sfortunatamente, questo ha senso solo se il sistema conosce la
funzione r e la funzione di transizione (X,a) !!
Q-learning (2)
• L’input del sistema sono sequenze di transizioni, dette episodi.
Un episodio inizia in uno stato scelto a caso, e termina quando
l’agente raggiunge, dopo una serie di azioni, uno stato obiettivo.
*
• Definiamo la quantità: Q(X, a)  r( X,a)  V ( ( X,a))
possiamo perciò riscrivere la precedente equazione:
V * (X)  max Q( X,a' )
a'
Q(X, a)  r( X,a)   max Q( ( X,a),a' )
a'
• Il sistema deve dunque stimare le quantità Q, e indicheremo con Qˆ
le stime di Q. La precedente definizione ricorsiva di Q consente
di stimare le Qˆ mediante approssimazioni iterative.
• Inizialmente i valori di stima possono essere riempiti
casualmente
Q-learning (3)
• Per ogni (X,a) inizializza Qˆ (X, a)a zero (o a un valore random)
• Osserva lo stato corrente X
• Esegui:
– Seleziona un’azione possibile a in X ed eseguila
– Ricevi una ricompensa r
– Osserva il nuovo stato X’ cui si arriva eseguendo a
ˆ (X, a)  r   max Qˆ (X' ,a' )
Q
– Aggiorna le stime come segue:
a'
– XX’
Q-learning (4)
• Esempio (spostamenti di un agente in una griglia)
• Il sistema inizialmente pone a zero tutte le stime di Qˆ .
• In tal modo, non potrà fare cambiamenti nella tabella finchè,
eventualmente, non raggiunge uno stato che prevede una ricompensa
(primo episodio) (1,1)>(2,1)>(3,1)>(3,2)>(3,3)>(3,4)
• Questo ha l’effetto di far aggiornare il valore di ˆ per la sola
Q
transizione che porta allo stato obiettivo, ad esempio
Xk (3,3
nell’esempio).
(Q((3,3),aright) nell’esempio)
• Nel successivo episodio, se l’agente passa per Xk, il valore non nullo
di consentirà di aggiornare il valore di
per qualche transizione
due
e, se il numero di
Qˆ celle prima della cella obiettivo (cioèQˆ 3,4),
k
episodi è sufficiente, l’informazione si propaga all’indietro per tutti gli
stati.
Esempio di aggiornamento
Q(s,a) in t
R
Q(s,a) in t+1
100
66
90
66
81
R
100
81
Qˆ (s1,aright )  r   max Qˆ (s2,a' )  0  0.9max66,81,100  90
a'
Q/azione
A1
A2
…..
Q(S1,Ai)
Q(S2,Ai)
Q(S3,Ai)
…..
Le celle i,j sono inizialmente a zero tranne per le transizioni a
ricompensa non nulla. Appena si raggiunge uno di questi stati, si
modifica il Q della cella adiacente
S1
S2
S3
S4
R(S3,right)=9
R(S2,down)=10
S4 bloccante
Q/azione
A1=right
A2=left
A3=down
Q(S1,Ai)
0
-
0
Q(S2,Ai)
-
0
10
Q(S3,Ai)
9
-
-
Q(S4,Ai)
-
-
-

Q(S1,)  0   max(Q(S2,),Q(S2,))  0   max(0,10)
Q(S1,)  0   max(Q(S3,))  0   max(9)
Q/azione
A1=right
0,9x10
0,9x10
Q(S1,Ai)
A2=left
A3=down
-
0,9x9
Q(S2,Ai)
-
0
10
Q(S3,Ai)
9
-
-
Q(S3,Ai)
-
-
-
Eccetera..
Q-learning: converge?
• Si dimostra che l’algoritmo converge se:
– primo, il sistema può essere modellato come un processo di Markov (le
probabilità di transizione fra stati devono essere note a priori)
– Secondo, i valori di ricompensa sono limitati r(X, a)  c , dove c è una
costante
– Terzo (!!) l’agente deve selezionare le azioni in modo tale che ogni coppia
(X,a) sia visitata un numero infinito di volte
• In pratica, si dimostra che l’algoritmo funziona in condizioni
meno restrittive!
Algoritmi genetici
Algoritmi motivati da una analogia con l'evoluzione biologica.
Anziché generare ipotesi da generali a specifiche, o da semplici a
complesse , gli AG gene rano successori di un insieme di ipotesi,
producendo "perturbazioni" sulle ipotesi che, in una data fase di
elaborazione dell'algoritmo, producono risultati migliori.
Motivazioni:
 I sist emi evolutivi biologici hanno dimostrato di avere capacità di
adattarsi a variazioni ambientali
 Gli AG po ssono effettuare ricerche nello spazio di ipotesi aventi
elementi che interagiscono fra loro in modo complesso, laddove sia
difficile valutare l'impatto di ogni elemento descrittivo sull'intera
ipotesi.
 Gli AG sono facilmente parallelizzabili, e dunque si
avvantaggiano de i ridotti costi dell'hardw are.
Algoritmi genetici (2)
Dati:
 Una funzione Fitness che assegna un valore ad ogni ipotesi
h
 Una soglia di Fitness che specifica un c riterio di
terminazione
 p: il numero di ipotesi da includere nella pololazione
 r: la frazione di una popolazione che deve essere
rimpiazzarta dall'opreatore Crossover
 m: il tasso di mutazione
Algoritmo
 P p individui generati a caso
 hP, calcola Fitness(h)
 while maxh(Fitness(h)<F_TR do:
crea una nuova g enerazione Ps:
1) Select: seleziona (1-r)p ipotesi di P da aggiunger e a Ps. La
probabilità di selezionare una ipotesi hi è
data: Pr(h i )  pFitness(h i )
 Fitness(h j )
j1
2) Crossover: seleziona (rp)/2 coppie di ipotesi da P (sulla base
di P(hi)) . Per ogni copia (hi,hj) produci due manipolazioni
(dette offspring) applicando l'operatore Crossover. Agg iungi
gli elementi manipolati a Ps.
3) Mutazione: Seleziona m% elementi in Ps, con probabilità
uniforme, ed applica l'operatore di mutazione.
Esempio crossover
Crossover (per ipotesi rappresentate da stringhe
binarie):
Stringhe
iniziali
11101001000
00001010101
11101001000
00001010101
11101001000
00001010101
11101001000
Maschera di Offspring
CrossOver
11111000000 11101010101
00001001000
00111110000 11001011000
00101000101
10011010011 10001000100
01101011001
11101011000
Single-Point
Cross Over
Two-Point
Cross Over
Uniform
CrossOver
Point
mutuation
Queste operazioni creano dei discendenti di una coppia di
ipotesi, "mescolando" le caratteristiche di ogni parente.
L'operatore di mutazione crea un singolo discendente da
un'unica ipotesi, cambiando in maniera casuale il valore di
un bit.
Algoritmo (cont)
4)Aggiorna: PPs
5)Valuta: h P, calcola Fitness(h)
6)Restituisci l'ipot esi di P con valore di
Fitness più alto.
Cosa “si fa evolvere” con un algoritmo genetico?
• Diverse architetture G di rete neurale. Ogni architettura (definita
da un grafo ) rappresenta un’ipotesi e può essere rappresentata
(codificata) mediante una stringa binaria
• Regole espresse mediante forme normali congiuntive
c  (a1  a2 )  (a2 )
oppure:
IF (a1  a2 ) THEN c
IF a2 THEN c
La rappresentazione binaria è:
a1
10
a2
01
c
1
a1
11
a2
10
• Praticamente qualsiasi classe di ipotesi
c
0
Problemi
• Tempi di apprendimento molto lunghi
(necessario hw “ad hoc)
• Crowding: alcuni individui tendono a prendere
il sopravvento, riducendo drasticamente la
diversità della popolazione (soluzione: creare
perturbazioni o alterazioni della funzione di
selezione, una sorta di “roulette”)
Evoluzione in reale e simulata
(predatore e preda)
Evoluzione in Reale
(Kephera Robots)
Evoluzione in Simulazione
+ Test in Reale
[Floreano and Nolfi, 1998]
[Nolfi, Floreano, Miglino, Mondada 1994]
Evoluzione in simulazione
Ciascun sensore e motore può comportarsi in modo diverso a
causa di piccole differenze a livello elettronico o meccanico
1024
1024
768
768
y 512
y 512
0
256
20
0
320
20
x
80
4th IF sensor
z
0
256
20
0
140
200
x
z
260
8th IF sensor
I sensori producono valori imprecisi e i comandi inviati a motori
hanno effetti incerti.
Le caratteristiche del robot e dell’ambiente devono essere
riprodotte fedelmente nella simulazione
Esempio: discriminare oggetti
discriminare
sensori
avvicinarsi
motori
evitare
explorare
•Distinguere muri da cilindri
•Distinguere cilindri grandi da piccoli
•Una rete per ogni “abilità”
•Tuttavia, cattivi risultati
[Nolfi, 1996,1999]
Discriminare fra oggetti (2)
genotype
phenotype
Le cose funzionano meglio senza decomposizione!
[Nolfi, 1996]
Approfondimenti su evolutionary
computing
• The evolutionary computing homepage:
http://gral.ip.rm.cnr.it/evorobot/
• Stefano Nolfi home
page:http://gral.ip.rm.cnr.it/nolfi/