Download Mapas auto-organizativos - Info-FICH

Mapas auto-organizativos
Diego Milone y Leonardo Rufiner
Inteligencia Computacional
Departamento de Informática
FICH-UNL
Introducción
Arquitectura de la red
Entrenamiento
Organización
Introducción
Auto-organización
Inspiración biológica
Arquitectura de la red
SOM 2D
Entornos y realimentación lateral
Entrenamiento de un SOM
Caracterı́sticas principales
Algoritmo de entrenamiento
Convergencia y consideraciones prácticas
Formación de mapas topológicos
Cuantización vectorial con aprendizaje
Algoritmo LVQ1
LVQ1: velocidad de aprendizaje
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Organización
Introducción
Auto-organización
Inspiración biológica
Arquitectura de la red
SOM 2D
Entornos y realimentación lateral
Entrenamiento de un SOM
Caracterı́sticas principales
Algoritmo de entrenamiento
Convergencia y consideraciones prácticas
Formación de mapas topológicos
Cuantización vectorial con aprendizaje
Algoritmo LVQ1
LVQ1: velocidad de aprendizaje
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Auto-organización
• Autoorganización: es el proceso en el cual, por medio de
interacciones locales, se obtiene ordenamiento global
(Turing, 1952).
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Auto-organización
• Autoorganización: es el proceso en el cual, por medio de
interacciones locales, se obtiene ordenamiento global
(Turing, 1952).
• Ejemplo 1: evolución de la ubicación de los alumnos
asisten a un curso...
• Ejemplo 2: las celulas del cerebro se auto-organizan en
grupos de acuerdo a la información que reciben...
LVQ
Introducción
Arquitectura de la red
Entrenamiento
SOM: Inspiración biológica
Corteza motora y sensorial
Ante estı́mulos provenientes de sensores próximos entre sı́, se estimulan
neuronas del cerebro pertenecientes a una misma zona.
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Organización
Introducción
Auto-organización
Inspiración biológica
Arquitectura de la red
SOM 2D
Entornos y realimentación lateral
Entrenamiento de un SOM
Caracterı́sticas principales
Algoritmo de entrenamiento
Convergencia y consideraciones prácticas
Formación de mapas topológicos
Cuantización vectorial con aprendizaje
Algoritmo LVQ1
LVQ1: velocidad de aprendizaje
LVQ
Introducción
Arquitectura de la red
Entrenamiento
SOM: Arquitectura
• Arquitectura SOM 2D
x → wj → sj
LVQ
Introducción
Arquitectura de la red
Entrenamiento
SOM: Arquitectura
• Arquitectura SOM 2D
x → wj → sj
• Salidas: se activa sólo la ganadora j∗
j∗ (n) = G(x(n)) = arg mı́n {kx(n) − wj (n)k}
j
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Entornos de influencia o vecindades
• Formas básicas:
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Entornos de influencia o vecindades
• Formas básicas:
• Alcance ΛG :
• Entornos fijos
• Entornos variables
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Entornos de influencia o vecindades
• Formas básicas:
• Alcance ΛG :
• Entornos fijos
• Entornos variables
• Excitación asociadas al entorno:
• Excitatorias puras
• Inhibitorias puras
• Funciones generales de excitación/inhibición
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Funciones de excitación/inhibición lateral
• Uniforme (entorno simple):
ΛG (n) = 2 ⇒
hG,i = β(n) si |G − i| ≤ 2
hG,i = 0
si |G − i| > 2
siendo β(n) adaptable en función de las iteraciones n.
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Funciones de excitación/inhibición lateral
• Uniforme (entorno simple):
ΛG (n) = 2 ⇒
hG,i = β(n) si |G − i| ≤ 2
hG,i = 0
si |G − i| > 2
siendo β(n) adaptable en función de las iteraciones n.
• Gaussiana:
2
hG,i = β(n)e
−
|G−i|
2σ 2 (n)
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Funciones de excitación/inhibición lateral
• Uniforme (entorno simple):
ΛG (n) = 2 ⇒
hG,i = β(n) si |G − i| ≤ 2
hG,i = 0
si |G − i| > 2
siendo β(n) adaptable en función de las iteraciones n.
• Gaussiana:
2
hG,i = β(n)e
−
|G−i|
2σ 2 (n)
• Sombrero Mejicano: campos receptivos retina, inhibición
lateral
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Organización
Introducción
Auto-organización
Inspiración biológica
Arquitectura de la red
SOM 2D
Entornos y realimentación lateral
Entrenamiento de un SOM
Caracterı́sticas principales
Algoritmo de entrenamiento
Convergencia y consideraciones prácticas
Formación de mapas topológicos
Cuantización vectorial con aprendizaje
Algoritmo LVQ1
LVQ1: velocidad de aprendizaje
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Entrenamiento de un SOM
Caracterı́sticas principales:
• Entrenamiento NO-supervisado
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Entrenamiento de un SOM
Caracterı́sticas principales:
• Entrenamiento NO-supervisado
• Aprendizaje competitivo
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Algoritmo de entrenamiento
1. Inicialización:
• pequeños valores aleatorios con wji ∈ [−0,5, · · · , +0,5] o
también
• eligiendo aleatoriamente wj (0) = x` (` ∈ [1, · · · , L])
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Algoritmo de entrenamiento
1. Inicialización:
• pequeños valores aleatorios con wji ∈ [−0,5, · · · , +0,5] o
también
• eligiendo aleatoriamente wj (0) = x` (` ∈ [1, · · · , L])
2. Selección del ganador:
G(x(n)) = arg mı́n {kx(n) − wj (n)k}
∀j
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Algoritmo de entrenamiento
1. Inicialización:
• pequeños valores aleatorios con wji ∈ [−0,5, · · · , +0,5] o
también
• eligiendo aleatoriamente wj (0) = x` (` ∈ [1, · · · , L])
2. Selección del ganador:
G(x(n)) = arg mı́n {kx(n) − wj (n)k}
∀j
3. Adaptación de los pesos:
wj (n) + η(n) (x(n) − wj (n)) si yj ∈ ΛG (n)
wj (n + 1) =
wj (n)
si yj ∈
/ ΛG (n)
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Algoritmo de entrenamiento
1. Inicialización:
• pequeños valores aleatorios con wji ∈ [−0,5, · · · , +0,5] o
también
• eligiendo aleatoriamente wj (0) = x` (` ∈ [1, · · · , L])
2. Selección del ganador:
G(x(n)) = arg mı́n {kx(n) − wj (n)k}
∀j
3. Adaptación de los pesos:
wj (n) + η(n) (x(n) − wj (n)) si yj ∈ ΛG (n)
wj (n + 1) =
wj (n)
si yj ∈
/ ΛG (n)
4. Volver a 2 hasta no observar cambios significativos.
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Entrenamiento de un SOM
Consideraciones prácticas:
• ΛG (n) es generalmente cuadrado
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Entrenamiento de un SOM
Consideraciones prácticas:
• ΛG (n) es generalmente cuadrado
• hG,i (n) uniforme en i, decreciente con n
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Entrenamiento de un SOM
Consideraciones prácticas:
• ΛG (n) es generalmente cuadrado
• hG,i (n) uniforme en i, decreciente con n
• 0 < η(n) < 1 decreciente con n
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Entrenamiento de un SOM
Consideraciones prácticas:
• ΛG (n) es generalmente cuadrado
• hG,i (n) uniforme en i, decreciente con n
• 0 < η(n) < 1 decreciente con n
¿Cómo varı́an ΛG (n) y η(n)?
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Etapas del entrenamiento
1. Ordenamiento global (o topológico)
• ΛG (n) grande (≈ medio mapa)
• η(n) grande (entre 0.9 y 0.7)
• Duración 500 a 1000 épocas
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Etapas del entrenamiento
1. Ordenamiento global (o topológico)
• ΛG (n) grande (≈ medio mapa)
• η(n) grande (entre 0.9 y 0.7)
• Duración 500 a 1000 épocas
2. Transición
• ΛG (n) se reduce linealmente hasta 1
• η(n) se reduce lineal o exponencialmente hasta 0.1
• Duración ≈1000 épocas
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Etapas del entrenamiento
1. Ordenamiento global (o topológico)
• ΛG (n) grande (≈ medio mapa)
• η(n) grande (entre 0.9 y 0.7)
• Duración 500 a 1000 épocas
2. Transición
• ΛG (n) se reduce linealmente hasta 1
• η(n) se reduce lineal o exponencialmente hasta 0.1
• Duración ≈1000 épocas
3. Ajuste fino (o convergencia)
• ΛG (n) = 0 (sólo se actualiza la ganadora)
• η(n) = cte (entre 0.1 y 0.01)
• Duración: hasta convergencia (≈ 3000 épocas)
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Formación de mapas topológicos
• Ejemplo 1: R1 → R1 , 2 neuronas
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Formación de mapas topológicos
• Ejemplo 1: R1 → R1 , 2 neuronas
• Ejemplo 2: R2 → R1 , 4 neuronas
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Formación de mapas topológicos
• Ejemplo 1: R1 → R1 , 2 neuronas
• Ejemplo 2: R2 → R1 , 4 neuronas
• Ejemplo 3: R2 → R2 , 4 neuronas
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Formación de mapas topológicos
• Ejemplo 1: R1 → R1 , 2 neuronas
• Ejemplo 2: R2 → R1 , 4 neuronas
• Ejemplo 3: R2 → R2 , 4 neuronas
• Ejemplo 4: RN → R2 , M neuronas
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Formación de mapas topológicos
•
•
•
•
•
Ejemplo 1: R1 → R1 , 2 neuronas
Ejemplo 2: R2 → R1 , 4 neuronas
Ejemplo 3: R2 → R2 , 4 neuronas
Ejemplo 4: RN → R2 , M neuronas
Ejemplo 5: el “phonetic typewriter” (Kohonen)
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Formación de mapas topológicos
•
•
•
•
•
•
Ejemplo 1: R1 → R1 , 2 neuronas
Ejemplo 2: R2 → R1 , 4 neuronas
Ejemplo 3: R2 → R2 , 4 neuronas
Ejemplo 4: RN → R2 , M neuronas
Ejemplo 5: el “phonetic typewriter” (Kohonen)
Ejemplo 6: el experimento de los paı́ses (Kohonen)
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Formación de mapas topológicos
•
•
•
•
•
•
Ejemplo 1: R1 → R1 , 2 neuronas
Ejemplo 2: R2 → R1 , 4 neuronas
Ejemplo 3: R2 → R2 , 4 neuronas
Ejemplo 4: RN → R2 , M neuronas
Ejemplo 5: el “phonetic typewriter” (Kohonen)
Ejemplo 6: el experimento de los paı́ses (Kohonen)
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Formación de mapas topológicos
• Ejemplo 1: R1 → R1 , 2 neuronas
• Ejemplo 2: R2 → R1 , 4 neuronas
• Ejemplo 3: R2 → R2 , 4 neuronas
• Ejemplo 4: RN → R2 , M neuronas
• Ejemplo 5: el “phonetic typewriter” (Kohonen)
• Ejemplo 6: el experimento de los paı́ses (Kohonen)
• Ejemplo 7: ejemplos demo Matlab
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Agrupamiento y clasificación
¿Cómo utilizar un SOM para clasificar patrones?
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Agrupamiento y clasificación
¿Cómo utilizar un SOM para clasificar patrones?
• Entrenamiento no-supervisado
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Agrupamiento y clasificación
¿Cómo utilizar un SOM para clasificar patrones?
• Entrenamiento no-supervisado
• Etiquetado de neuronas
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Agrupamiento y clasificación
¿Cómo utilizar un SOM para clasificar patrones?
• Entrenamiento no-supervisado
• Etiquetado de neuronas
• Clasificación por mı́nima distancia
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Agrupamiento y clasificación
¿Cómo utilizar un SOM para clasificar patrones?
• Entrenamiento no-supervisado
• Etiquetado de neuronas
• Clasificación por mı́nima distancia
¿Cuál es la diferencia principal entre el SOM y otros métodos
de agrupamiento no-supervisado?
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Demostraciones online...
• Caracteres: http://fbim.fh-regensburg.de/
˜saj39122/begrolu/kohonen.html
• 1D: http://www.cis.hut.fi/research/
javasomdemo/demo1.html
• 2D: http://www.cis.hut.fi/research/
javasomdemo/demo2.html
• Otro 2D:
http://www.neuroinformatik.ruhr-uni-bochum.
de/VDM/research/gsn/DemoGNG/GNG.html
• 3D: http://www.sund.de/netze/applets/som/
som1/index.htm
• Buscador WEB: http://www.gnod.net/
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Organización
Introducción
Auto-organización
Inspiración biológica
Arquitectura de la red
SOM 2D
Entornos y realimentación lateral
Entrenamiento de un SOM
Caracterı́sticas principales
Algoritmo de entrenamiento
Convergencia y consideraciones prácticas
Formación de mapas topológicos
Cuantización vectorial con aprendizaje
Algoritmo LVQ1
LVQ1: velocidad de aprendizaje
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Cuantización vectorial con aprendizaje (LVQ)
Conceptos básicos:
• Cuantizador escalar: señales cuantizadas
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Cuantización vectorial con aprendizaje (LVQ)
Conceptos básicos:
• Cuantizador escalar: señales cuantizadas
• Cuantizador vectorial:
• centroides o prototipos
• diccionario o code-book
• el proceso de cuantización: de vectores a números enteros
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Cuantización vectorial con aprendizaje (LVQ)
Conceptos básicos:
• Cuantizador escalar: señales cuantizadas
• Cuantizador vectorial:
• centroides o prototipos
• diccionario o code-book
• el proceso de cuantización: de vectores a números enteros
• Ideas de cómo entrenarlo:
• algoritmo k-means etiquetado para clasificación
• SOM etiquetado como clasificador...
• algoritmo supervizado LVQ
LVQ
Introducción
Arquitectura de la red
Algoritmo LVQ1
1. Inicialización aleatoria
Entrenamiento
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Algoritmo LVQ1
1. Inicialización aleatoria
2. Selección:
c(n) = arg mı́n {kx(n) − mi (n)k}
i
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Algoritmo LVQ1
1. Inicialización aleatoria
2. Selección:
c(n) = arg mı́n {kx(n) − mi (n)k}
i
3. Adaptación:
mc (n + 1) = mc (n) + s(c, d, n)α [x(n) − mc (n)]
+1 si c(n) = d(n)
s(c, d, n) =
−1 si c(n) 6= d(n)
LVQ
Introducción
Arquitectura de la red
Entrenamiento
Algoritmo LVQ1
1. Inicialización aleatoria
2. Selección:
c(n) = arg mı́n {kx(n) − mi (n)k}
i
3. Adaptación:
mc (n + 1) = mc (n) + s(c, d, n)α [x(n) − mc (n)]
+1 si c(n) = d(n)
s(c, d, n) =
−1 si c(n) 6= d(n)
4. Volver a 2 hasta satisfacer error de clasificación
LVQ
Introducción
Arquitectura de la red
Entrenamiento
LVQ1: observaciones
• Interpretación gráfica
• Caso de clasificación correcta
• Caso de clasificación incorrecta
LVQ
Introducción
Arquitectura de la red
Entrenamiento
LVQ1: observaciones
• Interpretación gráfica
• Caso de clasificación correcta
• Caso de clasificación incorrecta
• No hay arquitectura neuronal
LVQ
Introducción
Arquitectura de la red
Entrenamiento
LVQ1: observaciones
• Interpretación gráfica
• Caso de clasificación correcta
• Caso de clasificación incorrecta
• No hay arquitectura neuronal
• Se puede ver al cuantizador como SOM lineal, sin entorno
y supervisado
LVQ
Introducción
Arquitectura de la red
Entrenamiento
LVQ1: observaciones
• Interpretación gráfica
• Caso de clasificación correcta
• Caso de clasificación incorrecta
• No hay arquitectura neuronal
• Se puede ver al cuantizador como SOM lineal, sin entorno
y supervisado
• Velocidad de aprendizaje
• ¿Existe un αc óptimo para cada centroide?
• ¿Se debe considerar un αc (n) óptimo para cada instante de
tiempo?
LVQ
Introducción
Arquitectura de la red
Entrenamiento
LVQ1: velocidad de aprendizaje
mc (n + 1) = mc (n) + s(n)α(n) [x(n) − mc (n)]
LVQ
Introducción
Arquitectura de la red
Entrenamiento
LVQ1: velocidad de aprendizaje
mc (n + 1) = mc (n) + s(n)α(n) [x(n) − mc (n)]
mc (n + 1) = mc (n) + s(n)α(n)x(n) − s(n)α(n)mc (n)
LVQ
Introducción
Arquitectura de la red
Entrenamiento
LVQ1: velocidad de aprendizaje
mc (n + 1) = mc (n) + s(n)α(n) [x(n) − mc (n)]
mc (n + 1) = mc (n) + s(n)α(n)x(n) − s(n)α(n)mc (n)
mc (n + 1) = [1 − s(n)α(n)] mc (n) + s(n)α(n)x(n)
LVQ
Introducción
Arquitectura de la red
Entrenamiento
LVQ1: velocidad de aprendizaje
mc (n + 1) = mc (n) + s(n)α(n) [x(n) − mc (n)]
mc (n + 1) = mc (n) + s(n)α(n)x(n) − s(n)α(n)mc (n)
mc (n + 1) = [1 − s(n)α(n)] mc (n) + s(n)α(n)x(n)
mc (n + 1) =
= [1 − s(n)α(n)]
{mc (n − 1) + s(n − 1)α(n − 1) [x(n − 1) − mc (n − 1)]}
+s(n)α(n)x(n)
x(n − 1) es afectado dos veces por α
LVQ
Introducción
Arquitectura de la red
Entrenamiento
LVQ1: velocidad de aprendizaje
Siendo α < 1 la importancia relativa de los primeros patrones
de entrenamiento siempre será menor que la de los últimos.
LVQ
Introducción
Arquitectura de la red
Entrenamiento
LVQ1: velocidad de aprendizaje
Siendo α < 1 la importancia relativa de los primeros patrones
de entrenamiento siempre será menor que la de los últimos.
Si queremos que α afecte por igual a todos los patrones
deberemos hacerlo decrecer con el tiempo.
LVQ
Introducción
Arquitectura de la red
Entrenamiento
LVQ1: velocidad de aprendizaje
Siendo α < 1 la importancia relativa de los primeros patrones
de entrenamiento siempre será menor que la de los últimos.
Si queremos que α afecte por igual a todos los patrones
deberemos hacerlo decrecer con el tiempo.
Se debe cumplir que:
αc (n) = [1 − s(n)αc (n)] αc (n − 1)
LVQ
Introducción
Arquitectura de la red
Entrenamiento
LVQ1-O: velocidad de aprendizaje
Demostrar que:
αc (n) =
(no sobrepasar α > 1)
αc (n − 1)
1 + s(n)αc (n − 1)
LVQ