1. No category

C261-69 Tópicos Avanzados:
Redes Neuronales Artificiales
Mapas Auto-Organizados
Dra. Pilar Gómez Gil
Coordinación de Computación
INAOE
Modified: 25-02-2016
(c) P. Gómez Gil. INAOE 2016
1
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 2016
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 2016
3
Principios de autoorganización en RNA
1. Las modificaciones en los pesos sinápticos
tienden a auto-amplificarse
2. La limitación de recursos lleva a la
competencia entre sinapsis y por lo tanto a
la selección de la sinapsis con el
crecimiento mas vigoroso, a expensas de
otras
3. Las modificaciones en los pesos sinápticos
tienden a cooperar entre sí.
(c) P. Gómez Gil. INAOE 2016
4
Redundancia
• El aprendizaje en sistemas autoorganizados 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 2016
5
Dilema EstabilidadPlasticidad en el Aprendizaje1
¿Cómo se puede diseñar un sistema de autoaprendizaje, de manera que permanezca
adaptivo o "plástico" en respuesta a cambios
significativos en su medio ambiente, y a la
vez sea "estable" ante eventos irrelevantes?
1. S. Grossberg. “How does the Brain Build a Cognitive Code”. Phychological
Review, 87, pp. 1-51- 1980
(c) P. Gómez Gil. INAOE 2016
6
Conceptos básicos en sistemas
auto-organizativos
• El propósito de un algoritmo de autoorganización es descubrir patrones
significativos o características en los datos
de entrada, haciendo este descubrimiento
sin un maestro.
(c) P. Gómez Gil. INAOE 2016
7
Conceptos básicos en sistemas
auto-organizativos (cont.)
• 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 2016
8
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 2016
9
Conceptos básicos en sistemas
auto-organizativos (cont.)
• Para conseguir esto, un algoritmo debe seguir
una serie de reglas de naturaleza local, donde
local 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
• Debe haber redundancia en los patrones de
activación alimentados a la red por el medio
ambiente, a fin de que exista auto-organización.
La redundancia provee conocimiento.
(c) P. Gómez Gil. INAOE 2016
10
Conceptos básicos en sistemas
auto-organizativos (cont.)
• La organización se lleva a cabo a través
de la interacción de 2 niveles de neuronas,
que interactúan entre sí por medio de
ciclos de retro-alimentación. Esta
interacción se lleva a cabo con 2 fases
principales:
– Activación: La red produce patrones "activos"
como respuesta a señales de entrada
– Conectividad: Las fuerzas de conexión (pesos
sinápticos) de la red se modifican en respuesta
a señales neuronales en los "patrones" activos,
debido a plasticidad sináptica.
(c) P. Gómez Gil. INAOE 2016
11
Algunas redes neuronales
artificiales auto-organizacionales
• Red de HAMMIN y MAXNET.
• Red de CONTRA-PROPAGACIÓN.
• Mapas de características autoorganizacionales de KOHONEN.
• Redes ART (Adaptive Resonance
Theory)
(c) P. Gómez Gil. INAOE 2016
12
El proceso de formación de grupos
(clustering)
(c) P. Gómez Gil. INAOE 2016
13
El proceso de formación de
grupos
(c) P. Gómez Gil. INAOE 2016
14
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 2016
15
El Modelo de Kohonen1
• Al parecer, el cerebro forma mapas para
almacenar características, o atributos de
alto nivel (semánticos), que son bidimensionales
• 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]
(c) P. Gómez Gil. INAOE 2016
16
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 2016
17
Modelo LVQ
• Los neurones de salida compiten
entre sí, a través de conexiones
laterales de inhibición (pesos
negativos).
• Cada neurona tiene influencia de sus
vecinas, y la magnitud de la
influencia la representa una función,
que normalmente es de tipo
“sombrero mexicano”
(c) P. Gómez Gil. INAOE 2016
18
Diagrama de una red LVQ
[Hilera y Martínez 00]
(c) P. Gómez Gil. INAOE 2016
19
Función de inhibición lateral
(c) P. Gómez Gil. INAOE 2016
20
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 2016
21
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 2016
22
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 2016
23
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 2016
24
Red SOM
[Hilera y Martínez 00]
(c) P. Gómez Gil. INAOE 2016
25
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 2016
26
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 2016
27
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)
w i (0)  random()
x(t )
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 w i y el patrón x(t ) . Para
esto puede usarse la distancia Euclidiana:
N
d w i , x    ( wik  xk )
2
2
para i=1..M
k 1
(c) P. Gómez Gil. INAOE 2016
28
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:
w j (t  1)  w j (t )   (t )(x(t )  w j (t )), para j  i* (t )
 i* (t ) corresponde a una función de
vecindad centrada en la neurona
ganadora i* y  (t ) es una función de
proporción de aprendizaje, …
(c) P. Gómez Gil. INAOE 2016
29
Aprendizaje de SOM (4)
por ejemplo, definida como:
1
 1
 (t ) 
ó  (t )  1 1  
t

t
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.
(c) P. Gómez Gil. INAOE 2016
30
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 2016
31
Ejemplo de zona de vecindad
[Hilera & Martínez 00]
La zona de vecindad puede
cambiar en diferentes iteraciones…
(c) P. Gómez Gil. INAOE 2016
32
Ejemplo: Creando mapas
contextuales [Haykin 1999]
(c) P. Gómez Gil. INAOE 2016
33
Mapa generado
(c) P. Gómez Gil. INAOE 2016
34
Regiones formadas
(c) P. Gómez Gil. INAOE 2016
35
Ejemplo:
agrupando puntos 1
• Utilizando una red de Kohonen, se desea agrupar
en 4 o en 100 grupos un conjunto de puntos, los
cuales fueron generados al azar en un espacio
cartesiano.
• Para realizar esto, se usará una red con 2 nodos
de entrada (las coordenadas de cada punto) y 4
o 100 nodos de salida, organizados en una
dimensión.
• Al final del entrenamiento, los pesos de cada
nodo del nivel de salida contendrán el “prototipo”
representante de cada grupo.
1. Tomado de Hilera J. y Martínez V. Redes Neuronales Artificiales. Alfaomega. 2000 pp. 261-266
(c) P. Gómez Gil. INAOE 2016
36
Arquitectura de la red del
ejemplo
x
y
(c) P. Gómez Gil. INAOE 2016
37
Casos de prueba del
ejemplo
• Se presentan los resultados con 3 casos:
– En el primer caso, se utilizaron 20 puntos al
azar, generados con una distribución uniforme
y se agrupan en 4
– En el segundo caso, se utilizaron 2,000 puntos
generados al azar con una distribución
uniforme y se agrupan en 100
– En el tercer caso, se utilizaron 200 puntos
generados al azar con una distribución taroidal
y se agrupan en 100
(c) P. Gómez Gil. INAOE 2016
38
Resultados
• En los siguientes 3 filminas, se muestran los
estados de la red en diferentes puntos del
entrenamiento para cada uno de los casos.
• Las gráficas muestran los puntos usados en el
entrenamiento, y los puntos prototipos generados
a ese momento del entrenamiento.
• Los puntos prototipos están dados por los valores
de los pesos de cada neurón de salida en dicho
momento de entrenamiento.
• Con los puntos prototipos se dibuja un diagrama
de Voronoi, que hace evidente las zonas de
pertenencia de los prototipos.
(c) P. Gómez Gil. INAOE 2016
39
Diagramas de Voronoi
• Cuando la medida de similitud que se
utiliza para asignar un patrón de entrada a
una determinada región es la distancia
Euclidiana, se produce un diagrama de
Voronoi.
• El conjunto de puntos de Rn que están
más cerca de un prototipo yi, que de los
restantes prototipos forma un poliedro
(polígono en el plano) que se denomina
diagrama de Voronoi [Reinoso 02].
(c) P. Gómez Gil. INAOE 2016
40
Diagrama de Voronoi
[Reinoso 02 en De los Santos 02]
(c) P. Gómez Gil. INAOE 2016
41
Resultados en 4 diferentes épocas del caso 1
[Hilera J. y Martínez V. 2000]
(c) P. Gómez Gil. INAOE 2016
42
Resultados en 4 diferentes épocas del caso 2
[Hilera J. y Martínez V. 2000]
(c) P. Gómez Gil. INAOE 2016
43
Resultados en 4 diferentes épocas del caso 3
[Hilera J. y Martínez V. 2000]
(c) P. Gómez Gil. INAOE 2016
44
Visualizando el aprendizaje
de SOM [Germano 1999]
Disponible en: http://davis.wpi.edu/~matt/courses/soms/applet.html
(c) P. Gómez Gil. INAOE 2016
45
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 2016
46
Un ejemplo de escritura antigua:
Telegrama de Porfirio Díaz
(c) P. Gómez Gil. INAOE 2016
47
Un ejemplo de libro antiguo
(c) P. Gómez Gil. INAOE 2016
48
El problema de reconocimiento de
caracteres/imprenta antigua
– Documentos dañados por el paso del
tiempo
– El proceso de digitalización requiere de
cuidados especiales, para proteger el
documento
– Reconocimiento es fuera de línea. No
hay información disponible sobre la
dinámica de la escritura
Cont..
(c) P. Gómez Gil. INAOE 2016
49
El problema de reconocimiento de
caracteres/imprenta antigua (2)
– Los estilos antiguos de escritura tienen
muchos ornamentos
– Los fonts no son uniformes. Esto es
particularmente fuerte en la escritura
manuscrita. El mismo caracter se ve
diferente en diferentes lugares de una
palabra
– La forma de la escritura manuscrita varia
en la misma persona, dependiendo de
factores del ambiente, estado de animo,
tipo de pluma, edad, etc.
Cont…
(c) P. Gómez Gil. INAOE 2016
50
Diferencias entre escritura del
mismo escritor
a
“a”, presenta diferente forma
Dependiendo de la posición de
La palabra y en diferentes palabras
carmelita
a
o
Una letra se
puede confundir con
La conexión
ruido
“i” y “n” están encimadas
a
i
Indígena
(c) P. Gómez Gil. INAOE 2016
51
El problema de reconocimiento de
caracteres/imprenta antigua (3)
• Por lo tanto:
– No hay prototipos evidentes que definan cada
clase
– La varianza entre miembros de una clase es
mayor que los valores deseados
– Las métricas comunes, como la Euclidiana, son
muchas veces inútiles, pues la distancia puede
ser mayor entre patrones pertenecientes a la
misma clase, de lo que es a patrones de
diferentes clases
(c) P. Gómez Gil. INAOE 2016
52
Un OCR para documentos manuscritos
1.
Digitizing
Digital Image
Original
Document
2.
Preprocessing
3.
Segmentation
of words
Clean image
Words
Parameters
for training
Character objects
6.
Recognition
of
characters
7.
Training
of
recognize
r
NN
knowledge
NN
knowledge
Character objects
Parameters
for training
8.
Identificatio
n of words
4.
Character
Segmentation
and feature
extraction
Possible characters
Segmentation
s for training
5.
Training of
segmentation
Possible words
Dictionary
9.
Editing
10.
Correction
of style
Words in text
(c) P. Gómez Gil. INAOE 2016
Transcription of
document
53
Redes auto-organizables
para reconocer caracteres
• Un reconocedor no supervisado puede
aprender y representar la ambigüedad
inmersa en los patrones a reconocer
• Utilizando mapas topológicos, es posible
representar las similitudes y diferencias en
cada clase de caracteres. Por lo tanto, es
posible representar mas información que
cuando se usan otros métodos de
reconocimiento
• Se construyó la red SOFM (Self Organized
Feature Map)
(c) P. Gómez Gil. INAOE 2016
54
Experimentos
• Se realizaron diferentes experimentos, utilizando
diferente número de clases, a fin de analizar
detalladamente y entender el comportamiento de
la red
• Empezamos con 3 clases y llegamos hasta 21.
Desafortunadamente, al momento de realizar
este trabajo, no se contaba con suficientes datos
para probar el alfabeto completo usando sus 27
clases
• Los resultados se compararon con un “algoritmo
de vecino mas cercano”, utilizando el algoritmo
“k-means” para obtener los prototipos necesarios
para usar el “vecino mas cercano”
(c) P. Gómez Gil. INAOE 2016
55
Algunos resultados
Número de
clases
Número de
patrones de
entrenamiento
3
13
5
21
56
86
Tipo de
reconocedor
Porcentaje de
reconocimient
o en el
conjunto de
entrenamiento
Nearest neighbor
84%
SOFM (3x3)
92%
Nearest neighbor
58%
SOFM (5x1)
58%
SOFM (5x2)
71%
SOFM (5x5)
73%
Nearest neighbor
6%
SOFM (5x12)
63%
SOFM (2x30)
70%
(c) P. Gómez Gil. INAOE 2016
56
Algunos mapas de características
generados por vocales
(c) P. Gómez Gil. INAOE 2016
57
Mapas de características
utilizando 21 clases
(c) P. Gómez Gil. INAOE 2016
58
Ejemplo: Minería sobre
datos biológicos (1/2)
(Stegmayer et al., 2012)
(c) P. Gómez Gil. INAOE 2016
59
Ejemplo: Minería sobre
datos biológicos (2/2)
(Stegmayer et al., 2012)
(c) P. Gómez Gil. INAOE 2016
60
Ejemplo: descubrimiento de
tipos de cáncer (1/2)
(Golub et al., 1999)
(c) P. Gómez Gil. INAOE 2016
61
Ejemplo: descubrimiento de
tipos de cáncer (2/2)
(Golub et al., 1999)
(c) P. Gómez Gil. INAOE 2016
62
Bibliografía
1.
2.
3.
4.
5.
6.
7.
8.
S. Grossberg. “How does the Brain Build a Cognitive Code”. Phychological Review, 87, pp. 1-511980
Hilera, José y Martínez, Víctor. Redes Neuronales Artificiales. Alfaomega. 2000.
Germano, T. “Self-Organizing Maps” course material, Available at:
http://davis.wpi.edu/~matt/courses/soms/index.html#Java
Golub, T. R., Slonim, D. K., Tamayo, P., Huard, C., Gaasenbeek, M., Mesirov, J. P., ... &
Bloomfield, C. D. (1999). Molecular classification of cancer: class discovery and class prediction
by gene expression monitoring. science, 286(5439), 531-537.
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.
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
Haykin, Simon. Neural Networks, a comprehensive foundation” Second Edition, Delhi, India.
Pearson Education. 1999
Stegmayer, G., Gerard, M., & Milone, D. H. (2012). Data mining over biological datasets: An
integrated approach based on computational intelligence. Computational Intelligence Magazine,
IEEE, 7(4), 22-34
(c) P. Gómez Gil. INAOE 2016
63