Inteligencia Computacional II - INAOE

Dra. Ma. del Pilar Gómez Gil

Ciencias Computacionales, INAOE [email protected]

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

http://asesoriaprof.tripod.com/images/organizacion.gif

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”


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.


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.


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.


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)


El proceso de formación de grupos (clustering)


El proceso de formación de grupos


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


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


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.


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.


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.


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).


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


Red SOM


[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.


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.


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


())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, …


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

)(t

Aprendizaje de SOM (4)


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


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


La zona de vecindad puede cambiar en diferentes iteraciones…

Ejemplo: Creando mapas contextuales [Haykin 1999]


Mapa generado


Regiones formadas


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.


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


Diferencias entre escritura del mismo escritor


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


Mapas de características utilizando 21 clases


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


Evaluando una red SOM

Figura tomada de

[Hilera y Martínez 00]

Neurón ganador: i,j

Ejemplo a agrupar


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..


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


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..


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…



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…



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.


Un ejemplo de clasificación no supervisada


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


http://davis.wpi.edu/~matt/courses/soms/index.html

http://www.springerlink.com/content/33661173371xm44j/



http://ccc.inaoep.mx/~ksapiens/archivos/KS11.pdf



