Inteligencia Computacional II - INAOE

Dra. Ma. del Pilar Gómez Gil

Ciencias Computacionales, INAOE pgomez@inaoep.mx

Inteligencia Computacional II

Mapas auto-organizados

Versión: 17-Junio-2015

1 (c) P. Gómez Gil. INAOE 2015

Auto-Organización

Capacidad de adaptación sin un profesor, a través de

confrontación con el medio ambiente.

(c) P. Gómez Gil. INAOE 2015 2

Principios intuitivos de la Auto-organización

• Como puede generarse organización

“autónoma”?

• En 1952, Turing realizó la siguiente

observación:

“Se puede obtener orden global a través de

interacciones locales”

(c) P. Gómez Gil. INAOE 2015 3

Redundancia

• El aprendizaje en sistemas auto-organizados debe llevarse a cabo con ejemplos que contengan redundancia en los patrones de activación alimentados a la red por el medio ambiente

La redundancia provee de conocimiento.

(c) P. Gómez Gil. INAOE 2015 4

Conceptos básicos en sistemas auto-organizativos

• El aprendizaje no supervisado consiste en modificar repetidamente los pesos de una RNA en respuesta a patrones de activación, y de acuerdo a reglas prescritas, hasta que una configuración final se desarrolle.

(c) P. Gómez Gil. INAOE 2015 5

Conceptos básicos en sistemas auto-organizativos (cont.)

• Un algoritmo de aprendizaje debe seguir una serie de reglas de naturaleza LOCAL

• Esto significa que los cambios aplicados a los pesos de un neurón están limitados a cambios que afectan solo a vecinos de dicho neurón.

• la auto-organización es un proceso cotidiano y fundamental en la organización cerebral.

(c) P. Gómez Gil. INAOE 2015 6

Algunas redes neuronales artificiales auto-organizacionales

• Red de HAMMIN y MAXNET. • Red de CONTRA-PROPAGACIÓN. • Mapas de características auto-organizacionales de

KOHONEN. • Redes ART (Adaptive Resonance Theory)

(c) P. Gómez Gil. INAOE 2015 7

El proceso de formación de grupos (clustering)

(c) P. Gómez Gil. INAOE 2015 8

El proceso de formación de grupos

(c) P. Gómez Gil. INAOE 2015 9

Teuvo Kohonen “Teuvo Kohonen recibirá el premio “Frank Rosenblatt” por sus contribuciones para el

avance de la teoría y aplicaciones de las redes neuronales, memorias asociativas y mapas autoorganizados, las cuales son herramientas de la IA que se usan actualmente en infinidad de aplicaciones en áreas de finanzas, ciencias naturales, lingüística, robótica, entre otras. Los mapas organizados creados por el Dr. Kohonen, conocidos como SOM, por sus siglas en inglés, son considerados como uno de los inventos más significativos en las ciencias computacionales. El Dr. Kohonen trabaja en la Universidad Tecnológica Helsinki, en Espoo, Finlandia.”

Columna Estado del I-Arte, Komputer Sapiens. Año 1, No. 1 Oct. 2008. pp.4. México

(c) P. Gómez Gil. INAOE 2015 10

El Modelo de Kohonen1

• Al parecer, el cerebro forma mapas para almacenar características, o atributos de alto nivel (semánticos), que son bi-dimensionales

• En 1982, Kohonen presentó un modelo con esta capacidad. Quiso mostrar que un estímulo externo (entrada), es capaz de forzar la formación de mapas, suponiendo una estructura determinada y una descripción funcional

(c) P. Gómez Gil. INAOE 2015 11

1 Material tomado de [Hilera & Martínez 2000 ] y [De los Santos 2003]

Tipos de redes de Kohonen

• Hay 2 variantes de este modelo: • LVQ: Learning Vector Quantization • TMP ó SOM: Topology preserving map o

Self-Organizing map.

(c) P. Gómez Gil. INAOE 2015 12

Modelo TPM o SOM • Este modelo trata de establecer una

correspondencia entre los datos de entrada y un espacio bidimensional, creando mapas topológicos, de manera que datos similares activen neuronas en zonas próximas.

• Esta red es de tipo auto-organizado, esto es, que se organiza por sí misma.

• Está concebida para clasificar conjuntos de datos para los que no se conoce a priori ningún tipo de organización.

(c) P. Gómez Gil. INAOE 2015 13

Modelo TPM o SOM (cont.)

• La red, a partir de un proceso de auto-organización, proporciona un resultado, que depende de la relación de similitud existente entre dichos patrones de entrada.

• El tipo de aprendizaje es no supervisado.

(c) P. Gómez Gil. INAOE 2015 14

Características • Los datos deben tener un grado de redundancia

elevado para realizar su clasificación. • La red divide el conjunto de datos en distintos

subconjuntos (clusters), cada uno de los cuales agrupa a datos similares, con algún tipo de característica en común (clustering).

(c) P. Gómez Gil. INAOE 2015 15

Características (cont.)

• El desarrollo de un método de clustering requiere elaborar alguna medida de la semejanza entre los datos (distancia euclidiana, Correlación, etc.).

• Cada cluster se representa por un prototipo • Es una red de tipo competitiva

(c) P. Gómez Gil. INAOE 2015 16

Red SOM

(c) P. Gómez Gil. INAOE 2015 17

[Hilera y Martínez 00]

Arquitectura • Cada una de las N neuronas de entrada se conecta a las M

neuronas de salida a través de conexiones hacia adelante (feedfoward).

• Entre las neuronas de la capa de salida, existen conexiones laterales de inhibición (peso negativo) implícitas,

• Aunque no estén conectadas, cada una de las neuronas van a tener cierta influencia sobre sus vecinas.

• El valor que se asigne a los pesos de las conexiones entre las capas de entrada y salida durante el proceso de aprendizaje de la red, va a depender precisamente de esta interacción entre vecinos.

(c) P. Gómez Gil. INAOE 2015 18

Aprendizaje • El objetivo del algoritmo de aprendizaje de SOFM es

almacenar una serie de patrones de entrada x X, a través de encontrar un conjunto de prototipos {wj | j = 1, 2…M} que representen al mejor mapa de características posible, que llamaremos , y que presente alguna estructura topológica. M es el número de prototipos deseados (neuronas en la red).

• El proceso de aprendizaje de SOM es estocástico, fuera de línea y no supervisado.

(c) P. Gómez Gil. INAOE 2015 19

Algoritmo de aprendizaje [Martín & Sanz 01 en De los Santos 02]

1. Inicialice los pesos con valores al azar: para i=1..M (número de neurones) 2. Escoja al azar un patrón del conjunto de

entrenamiento, para la iteración t. 3. Por cada neurona i en el mapa de características ,

calcule la similitud entre el conjunto de pesos y el patrón . Para esto puede usarse la distancia Euclidiana:

para i=1..M

(c) P. Gómez Gil. INAOE 2015 20

())0( randomiw

)(tx

iw)(tx

N

k

kik xwd1

22 )(x,w i

Aprendizaje de SOM (2)

4. Encuentre un neurona ganadora i* correspondiente a la que obtuvo la mínima distancia (máxima similitud)

5. Modifique los pesos de la neurona ganadora i* y los de sus vecinos:

corresponde a una función de vecindad

centrada en la neurona ganadora i* y es una función de proporción de aprendizaje, …

(c) P. Gómez Gil. INAOE 2015 21

)(j para )),()()(()()1( * tttttt i jjj wxww )(* ti

)(t

Aprendizaje de SOM (4)

(c) P. Gómez Gil. INAOE 2015 22

por ejemplo, definida como:

6. Regrese al paso dos, hasta que no existan mas cambios en el mapa de características o hasta que número máximo de iteraciones se alcance.

tt

tt

11)( ó

1)( 1

Uso de la red SOM

• Una vez entrenada, la red SOM puede recibir un patrón x y determinar la similitud de éste con todos los pesos en el mapa .

• La neurona ganadora será aquella con la mínima distancia Euclidiana entre sus pesos y el patrón.

• El patrón pertenece entonces al grupo definido por dicha neurona

(c) P. Gómez Gil. INAOE 2015 23

Ejemplo de zona de vecindad [Hilera & Martínez 00]

(c) P. Gómez Gil. INAOE 2015 24

La zona de vecindad puede cambiar en diferentes iteraciones…

Ejemplo: Creando mapas contextuales [Haykin 1999]

(c) P. Gómez Gil. INAOE 2015 25

Mapa generado

(c) P. Gómez Gil. INAOE 2015 26

Regiones formadas

(c) P. Gómez Gil. INAOE 2015 27

Una Aplicación de SOM

Reconocimiento de caracteres manuscritos y de imprenta antiguos

“The Role of Neural Networks in the interpretation of Antique Handwritten Documents.” Gómez-Gil, P., De-Los-Santos Torres G., Navarrete-García J. Ramírez-Cortés M. Hibrid Intelligent Systems. Analysis and Design Series: Studies at Fuzziness and Soft Computing. Vol. 208. Editors: Castillo, O. Melin, P. Kacprzyk W. 2007 Springer.. Pags. 269-281.

(c) P. Gómez Gil. INAOE 2015 28

Un ejemplo de escritura antigua: Telegrama de Porfirio Díaz

(c) P. Gómez Gil. INAOE 2015 29

Diferencias entre escritura del mismo escritor

(c) P. Gómez Gil. INAOE 2015 30

a

a

a

i

o

“a”, presenta diferente forma

Dependiendo de la posición de

La palabra y en diferentes palabras

carmelita

ruido

Indígena

Una letra se

puede confundir con

La conexión “i” y “n” están encimadas

Algunos mapas de características generados por

vocales

(c) P. Gómez Gil. INAOE 2015 31

Mapas de características utilizando 21 clases

(c) P. Gómez Gil. INAOE 2015 32

Como se clasifica usando un método no supervisado?

• La clasificación utilizando un método no supervisado implica el poder determinar cual es la mejor clase que puede asignarse al grupo (cluster) en el que se acomodó un ejemplo determinado

(c) P. Gómez Gil. INAOE 2008-2009 33

(c) P. Gómez Gil. INAOE 2008-2009 34

Evaluando una red SOM

Figura tomada de

[Hilera y Martínez 00]

Neurón ganador: i,j

Ejemplo a agrupar

(c) P. Gómez Gil. INAOE 2008-2009 35

Ejemplo: a que vocal corresponde cada grupo generado por estas redes SOM?

¿a? ¿u?

Figuras tomadas de [Gómez-Gil et al. 2007]

¿P(“a”) = 0.7 P(“u”) = 0.3?

Construcción de un clasificador utilizando métodos supervisados 1. Coleccionar un conjunto de n datos para entrenar el

clasificador. Estos datos están representados a través de un conjunto de características y una etiqueta que representa la clase asignada a ese ejemplo

2. Entrenar el clasificador utilizando estos datos 3. Validar la eficiencia del clasificador utilizando m datos

diferentes a los del conjunto de entrenamiento Continúa..

(c) P. Gómez Gil. INAOE 2008-2009 36

Construcción de un clasificador utilizando métodos supervisados (2)

4. Determinar el porcentaje de acierto de clasificador o alguna otra métrica de desempeño que se desee.

5. Si el desempeño es aceptable, fin; si no es aceptable, regresar al paso 2 ajustando el clasificador, usando otro, y/ó recolectando mas datos para entrenar

(c) P. Gómez Gil. INAOE 2008-2009 37

Construcción de un clasificador utilizando métodos no supervisados

1. Coleccionar un conjunto de n datos para entrenar el clasificador. Estos datos están representados a través de un conjunto de características y una etiqueta que representa la clase asignada a ese ejemplo. Aún y cuando se use un método no supervisado, se requiere la clase asignada para evaluar la eficiencia del clasificador.

continúa..

(c) P. Gómez Gil. INAOE 2008-2009 38

Construcción de un clasificador utilizando métodos no supervisados (2)

2. Agrupar los datos de entrenamiento en m grupos, utilizando un método de agrupamiento no supervisado. m es un número varias veces mayor que el número de clases que contiene el problema a resolverse.

3. Utilizar algún método probabilístico o la opinión de un experto a fin de asignar probabilidades de clases a cada uno de los grupos generados. Este paso puede implicar un proceso complejo de varios pasos.

continúa…

(c) P. Gómez Gil. INAOE 2008-2009 39

Construcción de un clasificador utilizando métodos no supervisados (3)

4. Validar la eficiencia del clasificador utilizando m datos diferentes a los del conjunto de entrenamiento, de la siguiente manera:

a) Para cada elemento del conjunto de validación, determinar el grupo al que este elemento pertenece.

b) Basándose en el método utilizado en le paso 3, asignar la clase de mayor probabilidad.

continúa…

(c) P. Gómez Gil. INAOE 2008-2009 40

Construcción de un clasificador utilizando métodos no supervisados (4)

5. En base a los resultados obtenidos en el paso 4, determinar el porcentaje de acierto del clasificador o alguna otra métrica de desempeño que se desee.

6. Si el desempeño es aceptable, fin; si no es aceptable, regresar al paso 2 ajustando o cambiando el método de agrupamiento, el método de selección de probabilidades de clases ó recolectando mas datos para entrenar.

(c) P. Gómez Gil. INAOE 2008-2009 41

Un ejemplo de clasificación no supervisada

(c) P. Gómez Gil. INAOE 2008-2009 42

Figura tomada de [Song et. al 2007]

Bibliografía 1. S. Grossberg. “How does the Brain Build a Cognitive Code”.

Phychological Review, 87, pp. 1-51- 1980 2. Hilera, José y Martínez, Víctor. Redes Neuronales Artificiales.

Alfaomega. 2000. 3. Germano, T. “Self-Organizing Maps” course material, Available at:

http://davis.wpi.edu/~matt/courses/soms/index.html#Java 4. Gómez-Gil, P. De-Los-Santos Torres G., Navarrete-García J., Ramírez-

Cortés M.“The Role of Neural Networks in the interpretation of Antique Handwritten Documents.” Hybrid Intelligent Systems. Analysis and Design Series: Studies at Fuzziness and Soft Computing. Vol. 208. Editors: Castillo, O. Melin, P. Kacprzyk W. 2007 Springer.. Pags. 269-281.

5. Gómez-Gil, P. Gutierrez-Pulido, R. Columna Estado del I-Arte, Komputer Sapiens. Año 1, No. 1 Oct. 2008. pp.4. México

6. Haykin, Simon. Neural Networks, a comprehensive foundation” Second Edition, Delhi, India. Pearson Education. 1999

(c) P. Gómez Gil. INAOE 2015 43