Download n - bienvenidos a comunidad itam

La Combinación de Redes
Neuronales y Algoritmos
Genéticos
Angel Kuri
Instituto Tecnológico Autónomo de
México
Octubre de 2001
22/10/01
Redes Neuronales
Una de las más populares alternativas es
el perceptrón multi-capa entrenado con
el algoritmo de retropropagación
(BMLP).
22/10/01
Perceptrón Multi-Capa de
Retropropagación (BMLP)
El BMLP se basa en la regla delta
generalizada:
∆w ji (n ) = α ∆w ji (n − 1) + ηδ j (n )y i (n )
que se ha usado con éxito para clasificar
y predecir
22/10/01
BMLP
Sin embargo, el BMLP impone varias
restricciones:
a) La función de activación debe ser
derivable
b) La derivada debe ser “fácil”
1
c) El error a minimizar es E = ∑ ( zi − oi )2
2
22/10/01
i
BMLP
d) La tasa de aprendizaje, momento, etc.
deben determinarse a priori
e) El entrenamiento no se garantiza
22/10/01
BMLP
Funciones de activación típicas son:
Función
Derivada
Lineal
Logística
Sigmoide
22/10/01
Redes Neuronales Genéticas
(RNG)
Una alternativa para superar las
limitaciones mencionadas es entrenar
la RNs usando un Algoritmo Genético.
A las redes así entrenadas las llamamos
“Redes Neuronales Genéticas”.
22/10/01
Algoritmo Básico de
Programación Evolutiva
t := 0
Genera P(0)
Mientras t < Máximo número de
Poblaciones
Evalúa P(t)
Selecciona µ individuos
22/10/01
Algoritmo Básico
Recombina
Muta
t := t+1
Fin mientras
22/10/01
(continúa)
Modelo Simple de AGs
El llamado modelo simple de algoritmos
genéticos (SGA) fue definido y
estudiado por Holland y considera:
l Representación genética haploide
l Selección proporcional
22/10/01
Modelo Simple
(continúa)
Elección aleatoria
l Cruzamiento lineal en locus
aleatorios
l Mutación con baja probabilidad
l
22/10/01
Algoritmos Genéticos
Sin elitismo
l Con cadenas binarias
l Con una población de tamaño
constante
l Con un número máximo de
poblaciones
l
22/10/01
Algoritmos Genéticos
El algoritmo,entonces, parte de una
colección de cadenas binarias
22/10/01
Algoritmos Genéticos
Cada una de estas cadenas
(correspondientes a una solución
candidata) es evaluada, como se ilustra
en la siguiente figura:
22/10/01
Algoritmos Genéticos
22/10/01
Algoritmos Genéticos
Las cadenas son ordenadas de mejor a
peor de acuerdo con su desempeño
22/10/01
Algoritmos Genéticos
A cada cadena se le asigna una probabilidad de selección proporcional a su desempeño
22/10/01
Algoritmos Genéticos
(...continúa Selección)
Individuo
Cadena 1
Cadena 2
Cadena 3
Cadena 4
Cadena 5
22/10/01
E valuac ión
5
4
3
2
1
15
P robabilidad
d e S e lec c ión
33.33%
26.67%
20.00%
13.33%
6.67%
100.00%
Algoritmos Genéticos
De esta manera, a la larga, los individuos
con mejor desempeño tienen una más
alta probabilidad de ser seleccionados
y sus mejores genes intervienen con
más frecuencia en el pool genético de
la población.
22/10/01
Algoritmos Genéticos
Se elige una pareja de individuos con las
probabilidades mencionadas y se
genera un punto de cruzamiento de
manera aleatoria, como se ilustra en la
siguiente figura.
22/10/01
Algoritmos Genéticos
22/10/01
Algoritmos Genéticos
Se intercambian los contenidos genéticos
22/10/01
Algoritmos Genéticos
Este proceso se repite m/2 veces dando
origen a m individuos que son
descendientes de los m individuos
originales.
22/10/01
Algoritmos Genéticos
La idea “genética” es que los mejores
genes se perpetúen en la población
dando origen a nuevos individuos
(genéticamente hablando) que se
desempeñen “mejor”.
22/10/01
Algoritmos Genéticos
Una vez que se tiene la nueva población,
se alteran ciertos genes de manera
aleatoria (se “muta”). La idea es que es
necesario dotar de cierta dosis de
novedad a la población.
22/10/01
Algoritmos Genéticos
Sin embargo, los porcentajes de
mutación son muy bajos (típicamente
del orden de 0.1% a 0.5%).
22/10/01
Algoritmos Genéticos
El conjunto de nuevos individuos
reemplaza al conjunto anterior y el
proceso se repite un cierto número de
veces hasta que se alcanza un criterio
de convergencia.
En nuestro caso, demandamos un
número de generaciones máximo.
22/10/01
Algoritmos Genéticos
El resultado neto de este proceso es que
el algoritmo nos entrega un conjunto
de valores que resuelven la función de
ajuste de manera óptima.
22/10/01
Redes Neuronales Genéticas
Aquí nos preguntamos si la norma
1
E = ∑ ( zi − oi )2
2 i
puede ser reemplazada por una más
apropiada, cuáles son las alternativas y
cómo determinar sus ventajas.
22/10/01
Algoritmo Genético Ecléctico
El AG que usamos no es el algoritmo
genético simple propuesto por Holland.
Usamos el llamado AG Ecléctico (AGE)
que incorpora:
a) Elitismo total
b) Selección determinística
c) Cruzamiento anular
22/10/01
Algoritmo Genético Ecléctico
d) Activación probabilística de un
EMA
e) Determinación autoadaptable de
Pc (probabilidad de cruzamiento)
Pm (probabilidad de mutación)
N (número de descendientes)
(prob. de activación del EMA)
22/10/01
ητ
Elitismo Total
22/10/01
Selección Determinista
22/10/01
Cruzamiento Anular
22/10/01
Representación
El genoma de la RNG se formó encadenando secuencias de bits de longitud
32. Cada cadena representa un peso en
−28
−28
(
8
2
)
(
8
2
)
−
−
≤
w
≤
+
−
el rango
i
Los pesos se inicializaron así:
−0.0625 ≤ wi ≤ +0.0625
22/10/01
Representación
22/10/01
Solución
La solución al problema es, por tanto, un
genoma de longitud 32 × w
donde w denota el número de
conexiones de la red. Al ser interpretados, estos pesos y la topología de la
RNG determinan la solución del
problema
22/10/01
PROBLEMAS DE PRUEBA
ARQUITECTURA
CAPAS
NEURONAS EN LA
CAPA DE
PRESENTACIÓN
NEURONAS EN LA
CAPA ESCONDIDA
FUNCIÓN
NEURONAS EN LA
CAPA DE SALIDA
FUNCIÓN
CONEXIONES
GENOMA
CONJUNTO DE
ENTRENAMIENTO
CONJUNTO DE
PRUEBA
22/10/01
LOGÍSTICO
3
3
PROBLEMA
CLASIFICACION
3
13
PREDICCIÓN
3
12
2
5
2
SIGMOIDE
2
SIGMOIDE
3
TANH
1
SIGMOIDE
14
448
54
SIGMOIDE
88
2816
160
LINEAL
29
928
108
12
18
12
Ejemplo de Pesos
BIAS
*
*
*
*
22/10/01
PESO
W[1]( 1, 1)
W[1]( 1, 2)
W[1]( 2, 1)
W[1]( 2, 2)
W[1]( 3, 1)
W[1]( 3, 2)
W[1]( 4, 1)
W[1]( 4, 2)
W[2]( 1, 1)
W[2]( 1, 2)
W[2]( 2, 1)
W[2]( 2, 2)
W[2]( 3, 1)
W[2]( 3, 2)
VALOR
-1.8574
2.9398
3.8708
-4.5245
-0.0062
0.3795
-0.2853
-1.5044
-1.5631
2.5868
7.9438
-7.7568
-7.7481
3.6868
Normas Alternativas
nL
1
O(i )− Z (i )
MEE = ∑ ∑ 10
s s i =1
nL
1
MAE = ∑ ∑ O(i ) − Z (i )
s s i =1
nL
1
MSE = ∑ ∑ (O(i ) − Z (i )) 2
s s i =1
SAE = max O(i ) − Z (i )
s, i
22/10/01
Problema Logístico
Rasgo 1
0.8421
0.5711
0.5605
0.8789
0.5816
0.3421
0.6947
0.3526
0.3000
0.3526
22/10/01
Rasgo 2
0.1917
0.2055
0.3202
0.2391
0.3656
0.0711
0.1008
0.0771
0.1403
0.0929
Rasgo 3
0.5722
0.4171
0.7005
0.6096
0.8075
0.4920
0.2995
0.4278
0.6257
0.6417
Vino A
Vino B
1
1
1
1
1
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
Problema de Agrupamiento
Rasgo 1
Rasgo 2
0.8421
0.5711
0.5605
0.8789
0.3421
0.6947
0.3526
0.3000
0.4868
0.4684
0.4395
0.4132
22/10/01
0.1917
0.2055
0.3202
0.2391
0.0711
0.1008
0.0771
0.1403
0.4447
0.3103
0.5553
0.3399
Rasgo3
0.5722
0.4171
0.7005
0.6096
0.4920
0.2995
0.4278
0.6257
0.5561
0.5561
0.5348
0.4492
...
...
...
...
...
...
...
...
...
...
...
...
...
Rasgo 13
0.5613
0.5506
0.6469
0.8573
0.2867
0.2511
0.1013
0.0549
0.1797
0.2011
0.2297
0.2974
Vino 1
Vino 2
Vino 3
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
Problema de Predicción
t-12
t-11
t-10
t-9
t-8
t-7
t-6
t-5
t-4
t-3
t-2
t-1
Venta
0.323
0.358
0.404
0.382
0.348
0.424
0.487
0.482
0.437
0.352
0.287
0.358
0.404
0.382
0.348
0.424
0.487
0.482
0.437
0.352
0.287
0.368
0.404
0.382
0.348
0.424
0.487
0.482
0.437
0.352
0.287
0.368
0.378
0.382
0.348
0.424
0.487
0.482
0.437
0.352
0.287
0.368
0.378
0.386
0.348
0.424
0.487
0.482
0.437
0.352
0.287
0.368
0.378
0.386
0.469
0.424
0.487
0.482
0.437
0.352
0.287
0.368
0.378
0.386
0.469
0.411
0.487
0.482
0.437
0.352
0.287
0.368
0.378
0.386
0.469
0.411
0.432
0.482
0.437
0.352
0.287
0.368
0.378
0.386
0.469
0.411
0.432
0.439
0.437
0.352
0.287
0.368
0.378
0.386
0.469
0.411
0.432
0.439
0.498
0.352
0.287
0.368
0.378
0.386
0.469
0.411
0.432
0.439
0.498
0.491
0.287
0.368
0.378
0.386
0.469
0.411
0.432
0.439
0.498
0.491
0.435
0.368
0.378
0.386
0.469
0.411
0.432
0.439
0.498
0.491
0.435
0.358
0.378
0.386
0.469
0.411
0.432
0.439
0.498
0.491
0.435
0.358
0.299
22/10/01
Resultados (Clasificación)
CONJUNTO DE ENTRENAMIENTO
(160/54 ELEMENTOS EN EL CONJUNTO)
Número de
Indice de
Número de
Indice de
Promedio
Respuestas Entrenamiento Respuestas Entrenamiento
Correctas en el
Correctas en
Problema de
el Problema
Agrupación
Logístico
Exponencial
148
92.50%
26
48.15%
70.32%
Media
159
99.38%
43
79.63%
89.50%
Absoluta
Media
146
91.25%
51
94.44%
92.85%
Cuadrática
MiniMax
159
99.38%
48
88.89%
94.13%
BMLP
155
96.88%
44
81.48%
89.18%
22/10/01
Resultados (Clasificación)
CONJUNTO DE PRUEBA
(18/12 ELEMENTOS EN EL CONJUNTO)
Número de
Indice de
Número de
Indice de
Promedio
Respuestas Generalización Respuestas Generalización
Correctas en el
Correctas en
Problema
el Problema
Logístico
Logístico
Exponencial
11
61.11%
7
58.33%
59.72%
Media
14
77.78%
6
50.00%
63.89%
Absoluta
Media
12
66.67%
8
66.67%
66.67%
Cuadrática
MiniMax
14
77.78%
9
75.00%
76.39%
BMLP
13
72.22%
9
75.00%
73.61%
22/10/01
Resultados (Predicción)
22/10/01
PRUEBA
(12 ELEMENTOS EN EL CONJUNTO)
Error Promedio
Exponencial
5.74%
Media Absoluta
9.34%
Media Cuadrática
10.04%
MiniMax
9.50%
BMLP
17.67%
ENTRENAMIENTO
(108 ELEMENTOS EN EL CONJUNTO)
Error Promedio
Exponencial
10.62%
Media Absoluta
5.27%
Media Cuadrática
5.26%
MiniMax
5.68%
BMLP
3.35%
Resultados (Predicción)
V
E
22/10/01
Resultados (Predicción)
22/10/01
Resultados (Predicción)
22/10/01
Resultados (Predicción)
22/10/01
Resultados (Entrenamiento)
22/10/01
Resultados (Predicción)
22/10/01
Conclusiones
è Entrenamiento
de RNs con AGs
l El entrenamiento genético es una
alternativa viable
l Se evitan los parámetros de BMLP
l Con un buen AG se garantiza la
convergencia
22/10/01
Conclusiones
è Normas
No-estándar
l RNs entrenadas con normas noestándar se desempeñan tan bien
como o mejor que las tradicionales
l En este conjunto de experimentos la
norma SAE resultó ser la más
efectiva
22/10/01
Conclusiones
l El
entrenamiento en modo de lotes
es más conveniente cuando se trabaja
con RNGs
22/10/01
Conclusiones
Este tipo de entrenamiento se puede
aplicar a cualquier RN que implique
optimización
Por ejemplo, podemos optimizar:
l Mapas Auto-Organizados (Redes de
Kohonen)
22/10/01
Conclusiones
l Máquinas
de Soporte Vectorial
l Máquinas de Funciones de Base
Radial
l Redes Auto-Organizadas Difusas
22/10/01
Evolución de Arquitecturas
Una interesante forma de interacción entre
RNs y AGs es la de evolucionar las redes (y
no los pesos, como en el primer caso
discutido).
Yao y Liu han propuesto un algoritmo basado
en programación evolutiva y no en AGs,
mismo que consideramos de interés y
comentamos a continuación.
22/10/01
EPNet
Genérese una población de M redes al azar. El
número de nodos escondidos y la densidad
de conexiones inicial se generan
uniformemente al azar dentro de ciertos
rangos. Los pesos iniciales aleatorios se
generan dentro de un rango restringido.
Se entrena cada una de las RNs parcialmente
durante un cierto número de épocas K0
usando un RP modificado (MRP) con
tasas de aprendizaje adaptables.
22/10/01
EPNet
El número de épocas K0 es especificado por el
usuario. El error E de cada RN se checa
después del entrenamiento parcial. Si E no
se ha reducido significativamente, se asume
que la RN ha sido atrapada en un óptimo
local y la RN se marca como “fracaso” (f );
de otra forma se marca como “éxito” (x).
3. Se ordenan las RNs de acuerdo con sus
errores de mejor a peor.
22/10/01
EPNet
4. Si la mejor RN es aceptable o se ha llegado al
máximo número de generaciones, ir al paso 11.
5. Usar selección basada en rango para seleccionar una RN padre de la población. Si es de
tipo x ir al paso 6; si no, ir al paso 7.
6. M1. Entrenar parcialmente la RN padre
durante K1 épocas usando MRP para obtener
una RN hija y marcarla como en el paso 2, en
donde K1 es un parámetro del usuario.
22/10/01
EPNet
Reemplazar la RN padre por la RN hija en la
población actual e ir al paso 3.
7. M2. Entrenar la RN padre usando un AG para
obtener una RN hija. Si el AG reduce el error E de
la RN padre significativamente, marcar la RN hija
con x, reemplace la RN padre con la hija e ir al
paso 3. De otra forma, descartar esta RN e ir al
paso 8.
8. M3. Decidir el número de nodos escondidos NE
que van a eliminarse generando un número
aleatorio entre 1 y un máximo del usuario. NE es,
normalmente, muy pequeño: no mayor de 3.
22/10/01
EPNet
Borrar ahora NE nodos de la red padre uniformemente al azar. Entrenar parcialmente la RN
podada con MRP para obtener una RN hija. Si
esta RN es mejor que la peor en la población,
reemplazar la peor con la hija e ir al paso 3; o
descartar a la RN hija e ir al paso 9.
9. M4. Calcular la importancia relativa de cada
conexión en la RN padre usando el método
noconvergente. Decidir el número de
conexiones a quitar de la misma forma como
se hizo en el paso 8.
22/10/01
EPNet
Aleatoriamente eliminar las conexiones de la RN
padre de acuerdo con la importancia calculada.
Parcialmente entrenar la red podada con MRP
para obtener una hija. Si esta RN es mejor que
la peor RN en la población, reemplazar e ir al
paso 3; o descartar esta RN e ir al paso 10.
10. M5. Decidir el número de conexiones que
deben ser agregadas igual que en el paso 8.
Calcular la importancia relativa de cada
conexión virtual con peso =0.
22/10/01
EPNet
Aleatoriamente agregar las conexiones a la RN
padre para obtener el descendiente 1 (D1) de
acuerdo con su importancia. La agregación de
nodos se implementa dividiendo un nodo
elegido aleatoriamente en la RN padre. La
nueva RN crecida es el descendiente 2 (D2).
Parcialmente entrenar a D1 y a D2 con MRP
para obtener un descendiente sobreviviente
(DS). Reemplazar la peor red en la población
con DS e ir al paso 3.
22/10/01
EPNet
11. Después del proceso evolutivo, terminar el
entrenamiento de la mejor red hasta que
converja con los conjuntos de entrenamiento y prueba.
22/10/01
Eliminación de Conexiones y el
Método no Convergente
Ciertas conexiones se eliminan probabilísticamente de acuerdo con su importancia. El
número máximo de conexiones que se
pueden eliminar se determina con un
parámetro de usuario. La importancia se
define con una prueba de significación para
la desviación del peso en el proceso de
actualización de los mismos.
22/10/01
Eliminación de Conexiones y el
Método no Convergente
Denotamos la actualización ∆wij = −η [δLt / δwij ]
por el gradiente local de la función lineal de
error L con respecto a la muestra t y el peso
T
n
wij, en donde L = ∑∑ Yi (t ) − Z i (t )
t =1 i =1
La significación de la desviación de wij de
cero se define por la variable de prueba:
22/10/01
Eliminación de Conexiones y el
Método no Convergente
T
test ( wij ) =
∑ξ
t =1
T
∑ (ξ
i =1
t
ij
t
ij
− ξi j )
2
t
t
ξ
=
w
−
∆
w
en donde ij
ij
ij y ξ ij denota el promedio sobre ξ ijt ; t=1,...,T
22/10/01
Eliminación de Conexiones y el
Método no Convergente
Un valor más alto de test(wij ) indica una
mayor importancia de la conexión con peso
wij.
La ventaja de este método es que no requiere
de que el método converja para probar las
conexiones.
22/10/01
Evolución de Arquitecturas
EPNet ha sido aplicado en varios problemas
prácticos con éxito.
En general, puede encontrar RNs quasióptimas; puede agregar y podar RNs
dinámicamente dependiendo de si la RN es
mayor o menor de los necesario. Además, el
ordenamiento de las cinco mutaciones ha
resultado en RNs muy compactas debido al
sesgo hacia la eliminación de conexiones y
nodos.
22/10/01
Evolución de Arquitecturas
Las conexiones se modifican más
frecuentemente que los nodos porque las
mutaciones a las conexiones causan menor
alteración que las mutaciones a los nodos.
El algoritmo puede producir redes con
buena capacidad de generalización.
22/10/01
Redes Neuronales de Kohonen
Las Redes de Kohonen, también llamadas Mapas
Auto-Organizados o SOMs (por sus siglas en
inglés) son sistemas de clasificación no
supervisada que permiten encontrar individuos
de una población que comparten características
comunes.
Esto los hace ideales para explorar espacios
vectoriales en los que se desconoce la
estructura de clasificación de los vectores.
22/10/01
Redes de Kohonen
En esta ilustración se muestra un SOM de dos
dimensiones. Las neuronas se representan...
22/10/01
Redes de Kohonen
...en el mapa bidimensional, mientras que
los vectores de datos
(representados por Xi)
están en la parte inferior. Cada neurona
“apunta” a los vectores, de manera que cada
neurona tiene tantas coordenadas como
rasgos hay en un vector.
22/10/01
Redes de Kohonen
Supongamos, por ejemplo, que cada vector de datos
tiene 13 rasgos y que el mapa tiene una estructura
de 4 X 4. La neurona (1,1) tiene 13 coordenadas:
22/10/01
Redes de Kohonen
Por otra parte, la neurona 16 (4,4) tiene las siguientes
13 coordenadas:
22/10/01
Redes de Kohonen
Nuestro problema consiste en encontrar los
valores de las coordenadas de c/u de las
neuronas del mapa de manera que, en el
espacio bidimensional de las neuronas, las
neuronas vecinas apunten a aquellos datos
que forman parte del mismo grupo.
Por ejemplo, en el caso anterior, cada dato es
una muestra de las componentes químicas
de alguno de tres medicamentos.
22/10/01
Mapas Auto-Organizados
En el mapa que se muestra, cada color identifica una de las tres medicinas; y cada círculo corresponde a una neurona.
Como puede verse, las
neuronas correspondientes a cada tipo de medicina son vecinas entre
si.
22/10/01
Mapas Auto-Organizados
Así, lo que pedimos de este tipo de redes, es
un mapa del espacio multidimensional (en
el ejemplo, de 13 dimensiones) al espacio
bi-dimensional de tal manera que haya una
cercanía geográfica entre las neuronas que
mapean a miembros del mismo grupo.
¿Cómo logramos eso? Kohonen propuso el
siguiente algoritmo:
22/10/01
Algoritmo de Kohonen
1. Todas las coordenadas de las neuronas reciben,
inicialmente, valores aleatorios.
2. Se inicializa un contador de épocas n ← 1
3. Se define la tasa de aprendizaje α (n) para la
época n. (Una época es la presentación de todas
las muestras).
4. Se define la función de retroalimentación rik(n) de
la neurona i a la neurona ganadora k en la época
2
n, dada por:
d
rik (n) = exp(−
22/10/01
ik
σ ( n)
2
)
Algoritmo de Kohonen
en donde σ (n) es el radio de aprendizaje para la
época n y d es la distancia (euclidiana) entre la iésima neurona y la k-ésima neurona (o neurona
ganadora, como se define más adelante).
5. Se define el factor de aprendizaje fα . Este tiene
un valor cercano a 1 (por ejemplo 0.99)
6. Se define el factor radial fσ . Este tiene,
asimismo, un valor cercano a 1 (p.e. 0.995).
7. Se presenta la muestra x(t) de entrenamiento a la
red.
22/10/01
Algoritmo de Kohonen
8. Se determina cuál de las neuronas está más cerca
de la muestra. Normalmente se calcula la distancia
euclidiana entre el vector de pesos de las neuronas
y el vector de entrenamiento. A esta neurona (la késima) se le denomina la neurona ganadora.
9. Los vectores de peso de c/u de las neuronas
perdedoras se modifican de acuerdo con:
wij (t + 1) = wij (t ) + α (n) ⋅ rik (n) ⋅ ( x (t ) − wij (t ))
10. Se ha cumplido una época?
Si: Se actualizan los los parámetros de aprendizaje, de acuerdo con:
22/10/01
Algoritmo de Kohonen
α (n + 1) = α (n) ⋅ fα
σ (n + 1) = σ (n) ⋅ fσ
11. Se cumple algún criterio de convergencia?
Si: Fin
No: Ir al paso 7
22/10/01
Algoritmo de Kohonen
Debe notarse que la transformación del
espacio M-dimensional (de los M rasgos o
elementos del vector de c/u de las muestras)
al espacio bidimensional de las N neuronas
se produce al encontrar la distancia
d ik 2
rik (n) = exp(−
)
2
σ ( n)
puesto que
d ik = i − k
= (i x − k x ) + (i y − k y )
2
22/10/01
2
Algoritmo de Kohonen
La distancia entre
dos neuronas vecinas es, convencionalmente, igual a
1, como se ilustra.
22/10/01
Algoritmo de Kohonen
Nótese que la expresión de rik es
similar a la de
una distribución
normal, centrada
en dik y con una
desviación ó(n)
como se ilustra.
22/10/01
Algoritmo de Kohonen
Lo anterior implica que el ajuste al peso wik
está en función de la diferencia que existe
entre la neurona ganadora y la i-ésima
ponderada por la desviación estándar para
esta época. Como en cada época
σ (n + 1) = σ (n) ⋅ fσ
la influencia de la neurona ganadora en sus
vecinas se reduce exponencialmente con el
número de época (n).
22/10/01
Algoritmo de Kohonen
σ (1) = fσ ⋅ σ (0) = fσ ⋅ σ 0
σ (2) = fσ ⋅ σ (1) = fσ ⋅ ( fσ ⋅ σ 0 )
=
2
fσ (σ 0 )
y, en general :
σ ( n) =
22/10/01
n
fσ
⋅σ 0
Algoritmo de Kohonen
Análogamente:
α (1) = fα ⋅ α (0) = fα ⋅ α 0
α (2) = fα ⋅ α (1) = fα ⋅ ( fα ⋅ α 0 )
=
2
fα (α 0 )
y, en general :
α (n) = fαn ⋅ α 0
22/10/01
Algoritmo de Kohonen
Este algoritmo garantiza que neuronas que
apuntan a datos similares sean vecinas en el
mapa de la red, pero no resuelve el problema
de cómo están sectorizadas (a qué grupo
pertenecen) las neuronas individuales.
En otras palabras, empezamos con un mapa de
neuronas disociadas de los vectores de datos y
las asociamos en las coordenadas del mapa.
Pero falta “pintar” los grupos.
22/10/01
Agrupamiento
Dado:
22/10/01
Obtener:
Agrupamiento (Labeling)
Al problema de encontrar los grupos a los que
pertenecen las neuronas se le llama
“etiquetamiento” (labeling) de las neuronas.
Este proceso se puede automatizar de manera
sencilla si se conocen, a priori, los grupos a
los que pertenecen los datos de
entrenamiento.
22/10/01
Algoritmo de Agrupamiento
Dadas N clases y un conjunto de objetos Oi
(muestras) cada uno de los cuales pertenece
a las clase C (i ) ∈ {1,..., N } se define una
matriz P de N X M elementos, en donde M
es el número de neuronas de la red. Los
elementos de P se inicializan a 0.
Entonces se puede aplicar el siguiente
procedimiento.
22/10/01
Algoritmo de Agrupamiento
1. Preséntese el objeto Oi de la clase C(i) a la
red y calcúlese la distancia Oi − w j de
todas las neuronas a este objeto.
1
2. Hágase P
=P
+
∀j
C ( i ), j
C ( i ), j
Oi − w j
3. Repetir los pasos 1-2 hasta que todos los
objetos hayan sido presentados a la red.
4. Calcular
I m = max {Pn,m } para m = 1,..., M
22/10/01
n =1,..., N
Algoritmo de Agrupamiento
5. Asigne la etiqueta de clase Im a la neurona
m.
Puede ser que no haya un máximo único ni
está garantizado que haya al menos una
neurona asignada a cada clase. En estos
casos es necesario aplicar algún heurístico
para desambiguar el sistema.
Adicionalmente, se requieren, al menos,
tantos objetos como neuronas haya en la
red.
22/10/01
Matriz de Distancia
22/10/01
Agrupamiento Automático
Cuando se desconocen los grupos a los que pertenecen las neuronas, el problema es considerablemente más complejo.
Debemos de determinar, en este caso, en dónde
están los límites de las vecindades entre las
neuronas del mapa.
22/10/01
El Problema de las Particiones
¿Es este el número
correcto de particiones?
¿Son adecuadas estas particiones?
22/10/01
Métrica de Clases
Para establecer un sistema que determine,
dado un número de clases, a qué clase
pertenece cada una de las muestras,
propusimos 4 métricas:
a) Distancia absoluta
b) Distancia absoluta agrupada
c) Distancia euclidiana
d) Distancia euclidiana agrupada
22/10/01
Métrica de Clases
Distancia Absoluta:
N
C
∑∑ max(dist )+ dist
i =1 j =1
22/10/01
j =1,...,C
j
k
k =1,...,C
k≠ j
Métrica de Clases
Distancia Absoluta Agrupada:
1
C ( j)
22/10/01
N
C
∑∑ max(dist
i =1 j =1
C ( j ) ) + dist k
k =1,...,C
j =1,...,C
k≠ j
Métrica de Clases
Distancia Euclidiana:
N
C
∑ ∑
i =1
22/10/01
j =1
(max(dist j )− dist k )
j =1,...,C
2
k =1,...,C
k≠ j
Métrica de Clases
Distancia Euclidiana Agrupada:
1
C ( j)
22/10/01
N
C
∑ ∑ (max(dist
i =1
j =1
C ( j ) ) − dist k )
k =1,...,C
j =1,...,C
k≠ j
2
Resultados Numéricos
En la figura se muestran los valores obtenidos de
muestrear valores aleatoriamente para los 4 tipos
de métrica.
22/10/01
Resultados Numéricos
Lo que se observa es el resultado de medir las
distancias entre los grupos cuando los
grupos son los conocidos (1a fila) y cuando
la agrupación se hace aleatoriamente.
Lo que buscamos es la métrica que nos
entregue el menor valor posible para una
agrupación aleatoria, de manera que
tratemos de encontrar la agrupación que
minimice ese valor.
22/10/01
Una Medida de Agrupamiento
El razonamiento anterior se deriva del hecho
de que una asignación aleatoria debe arrojar
distancias menores que aquellas obtenidas
del caso “real”.
Si logramos una métrica que tenga el
comportamiento deseado, nuestro problema
se convierte en uno de minimización de los
valores derivados de agrupar las muestras
según la métrica más adecuada.
22/10/01
Simulaciones
En la siguiente figura se muestra una tabla con
los resultados de aplicar las distintas
métricas a 5 grupos de 10, 15 y 20 muestras
cada uno.
En las 1as 4 columnas se muestra la
desviación.
En las últimas 4 se muestra el número de
veces que la métrica equivocó su
diagnóstico.
22/10/01
Simulaciones
22/10/01
Métricas Robustas
De la tabla se puede ver que, en principio, las
métricas 1 y 3 inducen errores.
Por otra parte las métricas 2 y 4 no se
“equivocan”. De estas, la mejor es la #4
cuya desviación es, consistentemente,
menor que el el caso de la #2.
Es decir, la métrica euclidiana agrupada se
desempeña mejor.
22/10/01
Elección de los Elementos del
Grupo
Una vez convencidos que la métrica mejor es
1
C ( j)
N
C
∑ ∑
i =1
j =1
(max(dist C ( j ) )− dist k ) 2
j =1,...,C
k =1,...,C
k≠ j
debemos encontrar un método para encontrar
la agrupación que minimice esta distancia.
22/10/01
El Problema de Minimización
Este problema es no trivial.
Supongamos que tenemos 160 muestras y 3
clases. ¿Cuántas formas de agrupar estas
160 muestras en 3 clases existen?
El número es O(2320) que es, aproximadamente, O(1096). Obviamente una búsqueda
exhaustiva es inaplicable.
Pero para un AG la solución de este problema
es trivial.
22/10/01
Genoma
Para resolver el problema de optimización
debemos de construir un genoma (binario)
que nos permita representar la solución.
Una posible forma de proponiendo una cadena
de números (un número por muestra) tal que
cada número indique a qué grupo
corresponde una muestra.
22/10/01
Genoma
Siguiendo con el ejemplo anterior, donde hay
160 muestras y 3 categorías, el genoma se
compone de 160 números entre 1 y 3.
Por ejemplo:
1232323231112323...123123
160 números
22/10/01
Genoma
Nosotros decidimos codificar en binario, de
manera que un individuo está representado
por 160 X 2 bits; es decir, asociando parejas
de bits representamos un número entre 0 y 2
(y no usamos la combinación “11”).
El genoma es de 320 bits y, por lo tanto, hay
del orden de 2320 posibles combinaciones de
individuos.
22/10/01
Solución al Problema
22/10/01
Solución al Problema
En la gráfica anterior se muestra el
comportamiento de los métodos de
Las líneas inferiores corresponden
a las mejores métricas.
22/10/01
Conclusiones
Estableciendo una métrica adecuada es
posible convertir el problema de
determinación de grupos en problemas de
clasificación a uno de minimización.
El problema de minimización se puede
resolver fácil y eficientemente usando AGs.
Para determinar el número de grupos se
requiere ir aplicando el AG consecutivamente para 2, 3, ..., N grupos.
22/10/01
Conclusiones
Los resultados obtenidos hasta el momento
son alentadores pero no definitivos ya que
el criterio de elección de la métrica más
adecuada no asegura que los grupos
encontrados sean los óptimos.
En el futuro inmediato buscaremos un modelo
matemático del comportamiento de la
métrica para garantizar sus adecuadas
propiedades matemáticas en todos los casos.
22/10/01