Download A lg o ritm o s g e n é tic o s y re d e s n e u ro n a le s Alg o ritm

UPM
Algoritmos genéticos y redes neuronales
Algoritmos genéticos
El Perceptrón
Descenso por gradiente y «regla delta»
Redes multicapa
Aprendizaje: Algoritmos genéticos y redes neuronales
Retropropagación
c 2010 DIT-ETSIT-UPM
• Algoritmos genéticos:
individuos = cadenas de bits
• Programación genética:
individuos = árboles sintácticos de los
programas
«Computación evolucionista:»
transp. 1
Actualmente, énfasis en otros mecanismos
genéticos, p. ej., entrecruzamiento de genes
(crossover)
Primeras ideas: Generación de mutaciones al
azar sobre el código binario de programas
(Frieldberg, 1958)
La evolución como modelo
población de individuos
competición por recursos
selección
combinación de adaptados
reproducción
mutaciones
c 2010 DIT-ETSIT-UPM
Aprendizaje: Algoritmos genéticos y redes neuronales
transp. 2
«Al fin y al cabo, no hay tantas técnicas informáticas que hayan demostrado su
valor a lo largo de 3.000 millones de años de pruebas de campo»
(Forsyth, 1986)
UPM
UPM
UPM
Optimización con algoritmos genéticos
Problema: encontrar el máximo/mínimo de f (x1 , . . . xn)
Población: valores de (x1 , . . . xn) en binario (genomas)
(miles de individuos)
Operadores genéticos:
• Mutación (cambio de un bit con probabilidad pequeña)
• Selección de las parejas reproductoras (probabilidad proporcional al
valor de la función)
• Entrecruzamiento de cromosomas en cada pareja
transp. 3
Nueva generacion: los hijos sustituyen a los individuos menos adaptados
Convergencia: cuando hay muchos valores iguales
Aprendizaje: Algoritmos genéticos y redes neuronales
La mutación sirve para resolver el problema de los
máximos/mínimos locales
c 2010 DIT-ETSIT-UPM
Inducción de reglas con algoritmos genéticos
Problema: encontrar las mejores reglas para una base de conocimentos
Población: la BC, con una medida de la bondad de cada regla
⇒ si A y D entones C
Operadores genéticos: sobre la codificación binaria de las reglas, o bien en
el nivel simbólico:
• Mutación:
si A y B entones C
• Entrecruzamiento (crossover):
⇒ si G y F entones H
transp. 4
si A y B y C entones D ⇒ si A y G entones H
si F y G entones H
⇒ si F y B y C entones D
• Inversión:
si F y G entones H
La medida de «bondad» o «fuerza» depende de la aplicación:
Aprendizaje: Algoritmos genéticos y redes neuronales
Clasificación: fallo o acierto
Predicción: cercanía al valor
Control: resultado de la acción de control
c 2010 DIT-ETSIT-UPM
Aplicación:
máscara:
00011110
Aprendizaje: Algoritmos genéticos y redes neuronales
transp. 5
01000101
11110110
Ejemplo de entrecruzamiento en binario
01010111
11100100
Reglas padres:
[A1=valor11][A2=valor12] → [R=R1]
[A1=valor21][A2=valor22] → [R=R2]
Codificación:
A1 A2 R
111 001 00
010 101 11
c 2010 DIT-ETSIT-UPM
Reglas hijas:
[A1=valor11][A2=valor22] → [R=R3]
[A1=valor21][A2=valor12] → [R=R4]
UPM
Sistema GABIL (DeJong et al., 1993)
Población: {reglas de orden 0+}
Evaluación de reglas:
f (r) = porcentaje de ejemplos
correctamente clasificados por r
En cada generación, p reglas (constante)
• a una fracción t se le aplica entrecruzamiento
y se sustituyen por los hijos
Aprendizaje: Algoritmos genéticos y redes neuronales
transp. 6
• a una fracción m (muy pequeña) se le aplica mutación
c 2010 DIT-ETSIT-UPM
ID3, AQ, C4.5. . . : 91,2 % – 96,6 %
GABIL: 92,1 %
Resultados: sobre 12 problemas sintéticos,
UPM
UPM
UPM
Operadores genéticos en GABIL
Selección aleatoria de (1 − t) · p reglas de la población actual
para añadir a la siguiente, con probabilidad:
f (ri)
P(ri) = p
∑ j=1 f (r j )
Entrecruzamiento entre t · p/2 pares de reglas de la población
actual (seleccionadas con la misma función), añadiendo el
resultado a la siguiente
Aprendizaje: Algoritmos genéticos y redes neuronales
transp. 8
transp. 7
Mutación de m · p reglas (con probabilidad uniforme) de la
población resultante
c 2010 DIT-ETSIT-UPM
GABIL: algoritmo
Inicio: P = {p reglas al azar}
Calcular f (ri), i = 1 . . . p
Mientras (máx f (ri) < umbral)
PS = 0/
PS = selecc(P,t)
PS = PS ∪ entrecruzamiento(P,t)
PS = mutac(PS , m)
P = PS
calcular f (ri)
Aprendizaje: Algoritmos genéticos y redes neuronales
Devolver r tal que f (r) es máxima
c 2010 DIT-ETSIT-UPM
UPM
1
x
1
x
2
x
3
3
e
1
m
1
e
n
i
i
U
2
1
x ·x ·x
1 2 3
x ·x ·x
1 2 3
e, i, s binarias
U (umbral) entero
x
1
x
2
x3
x
1
x
2
x
1
x
2
1
1
1
x ·x +x ·x
1 2 1 2
x +x +x
1 2 3
transp. 9
s=1 si ( ∑ ej ≥ U) y ( ∑ i k = 0)
Neurona formal (McCulloch y Pitts, 1943)
El modelo simula:
Sinapsis excitadoras e inhibidoras
Umbral de excitación
Aprendizaje: Algoritmos genéticos y redes neuronales
Sumación espacial
x ·x ·x
1 2 3
x
1
x
2
x3
x1
x
2
x3
1
Neuronas formales y lógica de proposiciones
c 2010 DIT-ETSIT-UPM
x
1
x
2
x3
1
x ·x ·x
1 2 3
c 2010 DIT-ETSIT-UPM
Aprendizaje: Algoritmos genéticos y redes neuronales
transp. 10
McCulloch, W. and Pitts, W. (1943): A logical calculus of the ideas immanent in nervous activity.
Bulletin of Mathematical Biophysics, 7:115 - 133.
UPM
1
wn
w1
x =−1
0
w
0
y=
w ·x
i i
s = 1 si y > 0
s = −1 si y <= 0
El Perceptron (Rosenblatt, 1958: 1943 + 15)
x
xn
Conjunto de entrenamiento: E = {hx1, x2, . . . xn, ri}
xi ∈ [−1, 1]; wi ∈ [0, 1]; r ∈ {−1, 1}
c 2010 DIT-ETSIT-UPM
x
1
xn
}
c 2010 DIT-ETSIT-UPM
w1
wn
Aprendizaje: Algoritmos genéticos y redes neuronales
w ·x
i i
s = 1 si y > 0
s = −1 si y <= 0
Algoritmo del Perceptron
x0 =−1
w0
y=
transp. 11
transp. 12
∆wie = K · (re − se) · xie
Aprendizaje: Algoritmos genéticos y redes neuronales
while (!ond_term) {
for (e=0; e<nEj; e++)
for (i=0; i<=n; i++) {
dw[i℄ = k*(r[e℄-s[e℄)*x[i℄[e℄;
w[i℄ = w[i℄ + dw[i℄;
}
Si s = 1 y r = −1 reducir los wi correspondientes a xi > 0 y
aumentar los correspondientes a xi < 0
Si s = −1 y r = 1 aumentar los wi correspondientes a xi > 0 y
reducir los correspondientes a xi < 0
Regla de entrenamiento basada en «castigo» de los wi
«culpables»:
UPM
UPM
algoritmo de
aprendizaje
Convergencia del Perceptron
1
2
x
x
x
n
extraccion de caracteristicas (features)
Aprendizaje: Algoritmos genéticos y redes neuronales
Condición de convergencia:
separabilidad lineal en el espacio (x1, x2, . . . xn)
c 2010 DIT-ETSIT-UPM
Minsky y Papert (1969)
UPM
transp. 13
w
1
E=
1
(re − w1 · x1e − w2 · x2e)2
2∑
e
Aprendizaje: Algoritmos genéticos y redes neuronales
transp. 14
: dirección de máximo crecimiento de E
i
E
Descenso (o ascenso) por gradiente: principio
«Neurona» lineal: s(~x) = y(~x) = ~
w ·~x
Error de una hipótesis, ~
w:
1
E(~w) =
(re − se)2; re, se ∈ [0, 1]
2∑
e
(e: índice de ejemplos)
h
∂E
∂E
.
.
.
∂w0
∂wn
Idea: acercarse al mínimo mediante
incrementos de ~
w proporcionales al
gradiente de −E
∇E =
∆~w = −K · ∇E
c 2010 DIT-ETSIT-UPM
w
2
Método clásico para optimización: hill climbing
UPM
∇E =
h
∂E
∂E
∂w0 . . . ∂wn
i
;
transp. 15
∆~w = −K · ∇E
Descenso por gradiente: adaptación de pesos
1
(re − se)2;
E(~w) =
2∑
e
Como se = ~
w ·~xe,
∂
∂E 1
=
(re − se)2 = − (re − se) · xie
∑
∂wi 2 ∑
e ∂wi
e
∆wi = K · ∑(re − se) · xie
e
Aprendizaje: Algoritmos genéticos y redes neuronales
Descenso por gradiente: algoritmo
x[i℄[e℄ es xie: valor de la entrada i para el ejemplo e
Aprendizaje: Algoritmos genéticos y redes neuronales
Comparar con el algoritmo del Perceptron
c 2010 DIT-ETSIT-UPM
transp. 16
while (!ond_term) {
for (i=0; i<=n; i++) dw[i℄ = 0;
for (e=0; e<nEj; e++)
for (i=0; i<=n; i++)
dw[i℄ = dw[i℄ + k*(r[e℄-s[e℄)*x[i℄[e℄;
for (i=0; i<=n; i++)
w[i℄ = w[i℄ + dw[i℄;
}
c 2010 DIT-ETSIT-UPM
Comparar con el Perceptrón: ∆wie = K · (re − se) · xie
UPM
UPM
Descenso incremental o «regla delta»
Variante del algoritmo del gradiente
(Widrow y Hoff, 1960: «adalines»):
No función error global, sino por ejemplo: Ee(~
w) = 21 (re − se)2
Iteración sobre los ejemplos, modificando wi para cada uno
}
c 2010 DIT-ETSIT-UPM
c 2010 DIT-ETSIT-UPM
Aprendizaje: Algoritmos genéticos y redes neuronales
transp. 17
transp. 18
Gradiente/Delta convergen asintóticamente a una hipótesis de
mínimo error aunque los ejemplos no sean linealmente
separables
Perceptron converge tras un número finito de iteraciones a una
hipótesis (~
w) que clasifica perfectamente los ejemplos siempre
que éstos sean linealmente separables
Perceptron usa el error (discreto) a la salida del umbral;
Gradiente/Delta, el error (continuo) de la combinación lineal de
entradas
Delta aproxima Gradiente para K suficientemente pequeño, y
requiere menos computación
Diferencias entre Perceptron, Gradiente y Regla Delta
Aprendizaje: Algoritmos genéticos y redes neuronales
while (!ond_term) {
for (e=0; e<nEj; e++)
for (i=0; i<=n; i++)
w[i℄ = w[i℄ + k*(r[e℄-s[e℄)*x[i℄[e℄;
Algoritmo (igual al del Perceptron, pero re, se ∈ [0, 1]):
UPM
UPM
UPM
UPM
c 2010 DIT-ETSIT-UPM
Redes multicapa: MLP
Aprendizaje: Algoritmos genéticos y redes neuronales
transp. 19
La separabilidad en las redes multicapa según Minsky
Perceptron y otras funciones de activación con una sola capa:
limitación por la condición de separabilidad lineal
¿Se pueden conseguir superficies no lineales con una red de
varias capas? Para funciones lógicas, sí (ejemplo típico: ORX)
Pero no con el algoritmo del gradiente ni la regla delta: la red
seguiría siendo lineal
¿Con funciones de activación no lineales?
(como el Perceptron)
Aprendizaje: Algoritmos genéticos y redes neuronales
transp. 20
«Nuestra opinión personal es que la extensión es estéril»
(Minsky y Papert, 1969: 1958 + 11)
c 2010 DIT-ETSIT-UPM
UPM
UPM
Aprendizaje: Algoritmos genéticos y redes neuronales
Separabilidad en las redes multicapa
c 2010 DIT-ETSIT-UPM
El entrenamiento de redes multicapa
transp. 21
transp. 22
Problema para el diseño de una estrategia de aprendizaje:
asignación de mérito (credit assignment)
ij
Mérito (o culpa, o responsabilidad) de un peso (wi j ):
∂E
medida de su contribución al error global ( ∂w
)
Dificultad con el Perceptron:
la función de activación no es diferenciable
Se necesita una neurona con función de activación
Aprendizaje: Algoritmos genéticos y redes neuronales
• no lineal, para conseguir superficies no lineales
∂E
• diferenciable, para poder calcular ∆wi j = −K · ∂w
ij
c 2010 DIT-ETSIT-UPM
x
x
1j
nj
x =-1
0j
w
0j
y=
j
w ·x
ij
("net ")
j
ij
1
-y
1+e
j
= s(y) · (1 − s(y))
s(y j) =
Neurona no lineal y diferenciable
w
1j
wnj
ds
dy
j
∂E
∂E
= ∂y
·
=
· xi j (contribución de wi j al error global)
∂y j
j ∂wi j
∂y
Con esta función sigmoidal (o «logística»),
∂E
∂wi j
transp. 23
Si se conoce r para un ejemplo e,
j
∂s
= ∂y∂ j ( 21 (r j − s j)2) = −(r j − s j) ∂y jj = −(r j − s j ) · s j · (1 − s j )
∂Ee
∂y j
∆wi j = K · δ j · xi j , con δ j = (r j − s j ) · s j · (1 − s j )
Aprendizaje: Algoritmos genéticos y redes neuronales
Notación para redes multicapa
1
Gradiente: E(~
w) =
∑(rle − sle)2
2∑
e l
Aprendizaje: Algoritmos genéticos y redes neuronales
1
(rle − sle)2
Regla delta: Ee(~
w) =
2∑
l
c 2010 DIT-ETSIT-UPM
transp. 24
Con varias neuronas de salida, error de una hipótesis ~
w:
wi j : peso de la conexión de la neurona i a la j
δ j : factor de error de la neurona j
e: índice sobre los ejemplos
l : índice sobre las neuronas de salida
h, r: índices sobre neuronas ocultas
xi j : entrada a la neurona j procedente de la i
(para la capa de entrada, entradas a la red)
c 2010 DIT-ETSIT-UPM
Pero r j sólo se conoce en la capa de salida
UPM
UPM
Ajuste de pesos en redes multicapa
ij
∂Ee
Considerando Regla Delta, ∆wi j = −K · ∂w
= K · δ j · xi j , con
e
δ j = − ∂E
∂y j
(whr · δr )
En neuronas de la capa c, igual:
r: capa c+1
δh = sh · (1 − sh) · ∑
Aprendizaje: Algoritmos genéticos y redes neuronales
algoritmo de retropropagación, 1985 (1969 + 16)
c 2010 DIT-ETSIT-UPM
transp. 25
En neuronas de la capa anterior a la de salida,
como no se conoce rh se estima el mérito en función de la
contribución de las siguientes: δh = sh · (1 − sh) · ∑l (whl · δl )
En neuronas de salida: δl = sl · (1 − sl ) · (rl − sl )
Para la función de activación sigmoidal resulta:
UPM
Algoritmo de retropropagación: adelante
c 2010 DIT-ETSIT-UPM
Aprendizaje: Algoritmos genéticos y redes neuronales
transp. 26
/* Se iniia w[℄[i℄[j℄ on números aleatorios pequeños */
iniiar(w);
while (!ond_term) {
for (ie=0; ie<nEj; ie++) { /* nEj: número de ejemplos */
for (j=0; j<nn[0℄; j++) { /* nn[℄: num. neuronas en apa */
for (i=0; i<nEnt; i++) /* nEnt: num. entradas a la red */
x[0℄[i℄[j℄ = e[ie℄[i℄;
s[0℄[j℄ = f(x[0℄[i℄[j℄, w[0℄[i℄[j℄); /*sigm(∑(w*x)):
bule en i*/
}
/* Se propaga haia adelante la entrada */
for (=1; <n; ++) {
/* n: número de apas */
for (j=0; j<nn[℄; j++) {
for (i=0; i<nn[-1℄; i++) /* nn[-1℄ = num.ent. apa */
x[℄[i℄[j℄ = s[-1℄[i℄;
s[℄[j℄ = f(x[℄[i℄[j℄, w[℄[i℄[j℄); /* bule en i */
}
} /* ya tenemos las salidas para el ejemplo ie */
UPM
Algoritmo de retropropagación: errores de salida
c 2010 DIT-ETSIT-UPM
Aprendizaje: Algoritmos genéticos y redes neuronales
transp. 27
En el caso de varias capas falta lo más interesante: propagar hacia atrás
los errores, modificando los pesos convenientemente
En el caso de una sola capa, hemos terminado
(falta cerrar el bucle de ejemplos y la condición de terminación)
/* Errores en la apa de salida (n-1) */
for (l=0; l<nn[n-1℄; l++) {
d[n-1℄[l℄ = s[n-1℄[l℄*(1 - s[n-1℄[l℄)*(r[ie℄ - s[n-1℄[l℄);
/* Ajuste de pesos de la apa de salida */
for (i=0; i<nn[n-2℄; i++) /* Si n = 1, nn[n-2℄ = nEnt */
w[n-1℄[i℄[l℄ = w[n-1℄[i℄[l℄ + K*d[n-1℄[l℄*x[n-1℄[i℄[l℄;
}
UPM
Algoritmo de retropropagación: atrás
Aprendizaje: Algoritmos genéticos y redes neuronales
transp. 28
/* Se propagan haia atrás los errores (si n > 1)*/
for (=n-2; >=0; --) {
for (h=0; h<nn[℄; h++) {
suma = 0;
for (r=0; r<nn[+1℄; r++)
suma = suma + w[℄[h℄[r℄*d[+1℄[r℄;
d[℄[h℄ = s[℄[h℄*(1 - s[℄[h℄)*suma;
/* y se van ajustando los pesos */
for (i=0; i<nn[-1℄; i++) /* Si =0, nn[-1℄ = nEntr */
w[℄[i℄[h℄ = w[℄[i℄[h℄ + K*d[℄[h℄*x[℄[i℄[h℄;
}
}
} /* ierra el bule de ejemplos */
} /* ierra la ondiión de terminaión */
c 2010 DIT-ETSIT-UPM
Atribuido generalmente a Rumelhart, Hinton y Williams (1985)
Idea original de Werbos (1974) redescubierta por Parker (1982)
(Widrow, Proc. IEEE, Sep. 1990)
UPM
F
2
1
F
UPM
UPM
Aplicaciones de retropropagación: ejemplo
Una capa oculta: superficies convexas
Dos capas ocultas: superficies arbitrarias
head
hid
who’d
hood
4000
2000
1000
500
heed
who’d
hid
head
F1 (Hz)
hawed
heard
hood
500
Aprendizaje: Algoritmos genéticos y redes neuronales
0
hud
had
hod
1000
transp. 29
1400
Ejemplo: reconocimiento de 10 sonidos vocales en el contexto
«h_d» (Huang y Lippmann, 1988)
c 2010 DIT-ETSIT-UPM
http://www-ra.informatik.uni-tuebingen.de/SNNS/
JavaNNS
Sucesor de SNNS, multiplataforma
http://www-ra.informatik.uni-tuebingen.de/
software/JavaNNS/welome_e.html
JOONE (Java Object Oriented Neural Engine)
http://www.joone.org/
Aprendizaje: Algoritmos genéticos y redes neuronales
Herramientas para minería de datos
c 2010 DIT-ETSIT-UPM
transp. 30
SNNS (Stuttgart Neural Network Simulator)
Simulador y GUI para Unix (portado tambén a Windows)
Incluye muchos algoritmos, además de retropropagación: conterprop,
quickprop, Rprop...
Software para redes neuronales
F2 (Hz)