Download Memorias asociativas

Modelos Computacionales
Memorias asociativas Dinámicas
Contenidos

Introducción

El asociador lineal

El asociador no lineal simple

La Red BSB

La memoria asociativa bidimensional
Introducción

Memoria asociativa: dispositivo para almacenar
información que permite recuperarla basándose sólo en un
conocimiento parcial de su contenido y no en el lugar de su
almacenamiento. La recuperación de la información se
consigue según el grado de similitud entre el patrón de
entrada(clave) y los patrones memorizados(referencias).
Patrón
clave
Memoria
Asociativa
Patrón de
referencia
Introducción

Usaremos la desviación cuadrática como medida de
semejanza:
Dk   xi*  xik 
N




xk
(xk1,
xk2,
i 1
xk3,...,
2
=
xkN) con k = 1,2, ... ,p son los patrones
de referencia
x* = (x*1, x*2, . . . , x*N) es el patrón de prueba
Si las componentes de los vectores son binarias ({0,1}), Dk
coincide con la distancia de Hamming.
Si los vectores son bipolares ({-1,1}) la distancia de
Hamming se calcula con Dk/4
Introducción

Tipos de memorias asociativas

Heteroasociativa: para un conjunto de pares de entradas y salidas
{ (x1,y1),(x2,y2), ... ,(xp,yp) },
xk N, ykM
establece una correspondencia  de N en M de tal manera que
(xi) = yi, para i=1,2,..,p y además si x está más próximo a xi que
a cualquier otro xj entonces (x) = yi .

Autoasociativa establece la misma correspondencia que la
memoria heteroasociativa pero siendo los patrones de entrada y de
salida los mismos, es decir. (xi) = xi .
El asociador lineal

Queremos memorizar p pares de patrones (entradas y
salidas),
{ (x1,y1),(x2,y2), ... ,(xp,yp) },
xk N, ykM.

Los vectores de entrada (claves) son ortonormales, es
decir, (xk)Txk = 1 y (xk)Txi = 0 , ki.

Un asociador lineal es una aplicación lineal de la forma
yi =(xi) = W · xi
El asociador lineal

Arquitectura



N unidades de entrada y M unidades de proceso independientes
Cada entrada se conecta a todas las unidades de proceso.
Ley de Aprendizaje:
p
W   y k (x k ) T
k 1

Dinámica de la computación:


Los resultados se obtienen instantáneamente, sin evolución en los
estados del sistema
La función de activación es la función identidad.
yi =(xi) = W · xi
El asociador lineal

¿Se devuelven los patrones de referencia correctos?
p
 ( x )  W · x   y k (x k )T x i  y i , i  1,2,..., p
i
i
K 1

¿Qué ocurre si perturbamos ligeramente la entrada?
p
 (x )   (x  d)  W ·(x  d)   y k (x k )T (x i  d)
i
i
p
k 1
 y i   y k ( x k )T d  y i   (d )
k 1

El asociador lineal interpola la salida
El asociador lineal

Ventaja:


Inconveniente:


Simplicidad
La condición de ortogonalidad de los patrones clave
Ejercicio:
Construir un asociador lineal que memorice los patrones
{(1000), (00)}, {(0110), (01)}, {(111), (11)}
Calcular la salida ante las siguientes entradas:
(1100)
Asociador no lineal simple

Deseamos memorizar p patrones
{ s1, s2, …,sp, },
sk N, k=1,2,…,p
mediante una memoria asociativa dinámica no lineal.

La salida del sistema se obtendrá tras un proceso de
computación. Es decir, la red comienza con la
configuración determinada por la entrada y los estados de
las neuronas van cambiando, hasta que llegamos a una
situación estable en la que podemos leer el resultado de la
computación.

La red habrá memorizado un patrón si se estabiliza en él.
Asociador no lineal simple

Arquitectura



N unidades de proceso.
Todas las neuronas conectadas con todas.
Ley de aprendizaje:
1 p k k
wij   si s j
N k 1

Regla de Hebb:

Aprendizaje iterativo: wij ( p  1)  wik ( p ) 
1 p 1 p 1
si s j
N
Asociador no lineal simple

Dinámica de la computación

Si(k) es el estado de la neurona i en el instante k de
ejecución. Será 1 si la neurona está activa y –1 si no lo
está. La actualización se realiza en tiempo discreto

La entrada s=(s1, s2, ..., sN)T, sirve para inicializar el
estado de las neuronas, es decir, Si(0) = si, 
i{1,2,...,N}

Cuando Si(k) = Si(k+1) = si k1, i{1,2,...,N},
diremos que la red se ha estabilizado.
N

Yi  Si (k  1)  sgn  wij S j ( K )
 j 1

Asociador no lineal simple

Para entender el funcionamiento de nuestro modelo
neuronal consideremos el caso particular en el que
queremos memorizar sólo un patrón, s=(s1, s2, ..., sN)T.

La regla de aprendizaje se particulariza a: wij  1 si s j
N

Con ese entrenamiento, ¿se memoriza el patrón?
N

N

N 1

S i (1)  sgn  wij S j (0)  sgn  wij s j   sgn  si s j s j   sgn si   si
 j 1

 j 1

 j 1 N

Asociador no lineal simple
Observación: wii = p/n
pues sisi=1
Sin embargo, se suele tomar wii = 0 ya que no supone
diferencia apreciable en la estabilidad de la red,
N

N

N

1
 N 1 
Si (1)  sgn  wij S j (0)  sgn  wij s j   sgn  si s j s j   sgn 
si   si




N
N


j 1
j 1
 j 1

 j i

 j i

1
wij  si s j ij
N
wii  0
Asociador no lineal simple

¿Qué ocurre ante entradas no memorizadas que difieren en
n componentes del patrón memorizado?
 si
ri  
s i
i  1,2,...,n
i  n  1, n  2,..., N
N
N

N

n

Si (1)  sgn  wij S j (0)  sgn  wijrj   sgn  wij (  s j )   wij s j 
j n 1
 j 1

 j 1

 j 1

N
n 1

1 n
1
1 N 
 sgn  ( si s j )(  s j )   ( si s j ) s j   sgn   si 
si 

N j n 1 
j n 1 N
 j 1 N

 N j 1
N n 
2n 
 n

 sgn 
si 
si   sgn (1  ) si 
N
N 
N


Asociador no lineal simple
 si
Si (1)  
 si
si n  N / 2
si n  N / 2

Junto al patrón que le enseñamos, la red ha aprendido por
cuenta propia el patrón opuesto.

Siguiendo el criterio de semajanza planteado el patrón
referencia que se recupera será uno u otro.
Asociador no lineal simple

¿Funciona igual de bien cuando queremos memorizar
varios patrones?
r r
r
Estado inicial: ( s1 ,s 2 ,...,s N )
1
hi (0) 
N
1

N
N
p
1
s
s
S
(
0
)


j
N
j 1 k 1
k
i
p
s
k 1
k r
N
k
i

j 1
k
j
p
N
1
s
s
s


N
k 1 j 1
k
i
k r
k
j
r
j
N
s
j 1
s kj s rj  sir
¿Cuál sería el siguiente estado Si(1)=sgn[hi(0)]?
r
i
s rj s rj
Asociador no lineal simple

Si los patrones se escogieron ortogonales, el estado de la
neurona se mantiene. Por tanto, la red se estabiliza y nos
devuelve el patrón correcto.

Otra posibilidad es utilizar un número de neuronas (N)
muy elevado en comparación con el número de patrones
que queremos memorizar (p). Esto no nos asegura
resultados esentos de error, pero sí “aceptables”.

Capacidad de almacenamiento de la red: cantidad de
información que se puede almacenar de tal forma que se
recupere sin error o con error despreciable.
Capacidad de un asociador no lineal

Indicadores de la capacidad de una red:

Considerando patrones almacenados (p) y total de neuronas (N)
C

En base a los patrones (p) y al número de conexiones (NW)
Cw 

p
N
p
Nw
Teorema:
La capacidad máxima de una red de Hopfield está acotada por
c
1
4 ln N
Asociador no lineal simple

¿Qué ocurre si almacenamos p patrones y la entrada difiere
en n componentes de alguno de los patrones memorizados?
1
hi (t) 
N

 n k r
s    s j s j 

k 1
 j 1
k r
p
k
i

 2n  r

s s   1-  si

 N
j  n 1

N
k
j
r
j
Cuanto menores sean n y p con respecto a N, más fiable
será la red en su función de memoria asociativa.
Asociador no lineal simple

Ejemplo:
Diseño de un asociador lineal que memorice los patrones
(1 -1 1) y (-1 1 -1). Probarla con la entrada (1 1 1).
(-1 1 1)
(-1 -1 1)
(1 -1 1)
(1 1 1)
(-1 -1 –1)
(1 -1 –1)
(-1 1 –1)
(1 1 –1)
Asociador no lineal simple

Nuestra red tendrá 3 unidades de proceso. Cada una de
ellas se encargará de procesar una componente del vector
de entrada.

La dinámica de la computación es la definida.

Empleando la regla de Hebb, calculamos la interacción
entre las neuronas
1
2
1
2
1
2
w12  (1  1)   , w13  (1  1)  , w23  (1  1)  
3
3
3
3
3
3
wii = 1/3(1+1) = 2/3
Asociador no lineal simple
Asociador no lineal
2/3
2/3
1
-2/3
2/3
2
-2/3
3
2/3
Asociador no lineal simple



Estado inicial: (1 1 1)
Computamos hasta que se estabiliza la red.
Estado final: (1 –1 1)
(-1 -1 1)
(-1 1 1)
(1 -1 1)
(1 1 1)
(-1 -1 –1)
(1 -1 –1)
(-1 1 –1)
(1 1 –1)
La red BSB

La red BSB(Brain-State-in-a-Box) se suele emplear como
memoria autoasociativa de conjuntos de patrones
{ s1, s2, …,sp, }, sk N, k=1,2,…,p

Arquitectura



N unidades de proceso.
Cada unidad está conectada a todas las demás.
Ley de aprendizaje

Regla de Hebb
1 p k k
wij   si s j
p k 1

Se suele fijar el peso sináptico wii=1, i=1,2,...,N
La red BSB

Dinámica de la computación:

Actualización en unidades de tiempo discretas.
 N


xi (k  1)  f   wij x j (k ) 
 j 1


La función de transferencia es la función rampa
 1

f (u i (k ))  u i (k )
- 1

si
u i (k )  1
si - 1  u i (k )  1
si
u i (k )  1
La red BSB

La ley de aprendizaje puede especificarse de forma
iterativa:
 r N

wij  s  s i   wik s kr 
k 1


r
j



 es la tasa de aprendizaje. Determina la facilidad para
aprender.
El entrenamiento se mantiene hasta
que se produzcan
p
salidas con un error aceptable  wijr  0
r 1
Con esos pesos la red se estabiliza en los patrones
memorizados.
N
s   wik s kr
r
i
k 1
La Memoria Asociativa Bidireccional (BAM)

1


xi (k  1)   xi (k )


- 1

m
si
m
ij
j 1
m
si
w
ij
j 1
m
si
w
j 1

1


y j (k  1)   y j (k )


- 1

n
w
ij
y j (k )   i
y j (k )   i
y j (k )   i
n
si
 w x (k )  
i 1
ij i
j
n
si
 w x (k )  
i 1
ij i
j
n
si
 w x (k )  
i 1
ij i
j
n
m
i 1
j 1
E (k )   wij xi (k ) y j (k )   i xi (k )   j y j (k )
i 1 j 1
La Memoria Asociativa Bidireccional (BAM)
Teorema 1.
Si seguimos una actualización paralela la función de energía computacional
decrece, o no cambia, en cada actualización, y la red alcanza un estado
estable (estado de equilibrio) después de un número finito de
actualizaciones.
n
m
n
m
i 1
j 1
E (k  1)  E (k )   wij xi (k ) y j (k  1)   i xi (k )   j y j (k  1)
i 1 j 1
n
m
n
m
i 1
j 1
  wij xi (k ) y j (k )   i xi (k )   j y j (k )
i 1 j 1
n
m


m

  wij xi (k ) y j (k  1)  y j (k )   j y j (k  1)  y j (k )
i 1 j 1
m
 
j 1

j 1

n

y j (k  1)  y j (k )  wij xi (k )   j 
 i 1


La Memoria Asociativa Bidireccional (BAM)
Determinación de los pesos sinápticos: Regla de Hebb
p
W   (x k ) T y k
k 1
Ejemplo: Memorizar los patrones y códigos siguientes:
(1 1 1 -1 1 -1 -1 1 -1)

(1 -1 -1)

(-1 -1 1)
(1 -1 -1 1 -1 -1 1 1 1)
La Memoria Asociativa Bidireccional (BAM)
Determinación de los pesos sinápticos: Regla de Hebb
p
W   (x k ) T y k
k 1
 0 2 0 


2
0

2


 2
0  2



2
0
2



 2
0  2 
 0
2
0 



2
0
2


 0 2 0 



2
0
2


Patrón a reconocer:
Actualización:
(-1 -1 1)
 0 2 0 


0  2
 2
 2
0  2



2
0
2



(1  1  1 1  1  1 1 1  1) 2
0  2   (8  2 8)
 0
2
0 


2 
 2 0
 0 2 0 



2
0
2


La Memoria Asociativa Bidireccional (BAM)
Actualización:
Patrón a reconocer:
 2
 0 2 0 
 


2
0

2
  4


  4
 2
0  2
 


2   1  4 
 2 0
 2
  1    4 
0

2

   
 0
2
0 1    2 
 


2 
 4
 2 0
 2
 0 2 0 
 


2 
 2 0
 4
(-1 -1 1)
Actualización:
(1 -1 -1 1 -1 -1 1 1 1)
La Memoria Asociativa Bidireccional (BAM)
Actualización:
(1 -1 -1 1 -1 -1 1 1 1)
(-1 -1 1)
 0 2 0 


0  2
 2
 2
0  2


2 
 2 0
(1  1  1 1  1  1 1 1 1) 2
0  2   (12  6 12)
 0
2
0 



2
0
2


 0 2 0 


2 
 2 0
Resultado final:
Patrón a reconocer:
(-1 -1 1)