Download Mapas auto-organizativos - Info-FICH
Document related concepts
Transcript
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