Download Sin título de diapositiva

MEMORIAS AUTOASOCIATIVAS
MEMORIAS
•
Memoria: sistema con capacidad de recordar ciertos estímulos y responder
ante ellos con ciertos patrones almacenados durante el proceso de
aprendizaje (memorización)
a
•
Estímulo
Memoria
Respuesta
(Vector)
(Matriz)
(Vector)
b
Pueden ser:
- Lineales/No lineales
- Autoasociativas/Heteroasociativas
•
Un MLP o una RBF adecuadamente entrenados pueden funcionar como
memorias no lineales
MEMORIAS
Una vez entrenada, la memoria puede
recuperar un patrón a partir de información
parcial o ruidosa
MEMORIAS LINEALES
• Queremos una estructura lineal que “memorice” el siguiente problema:
Estímulos
Respuestas
k  1,... N
bk
ak
• Los estímulos y las respuestas son patrones (vectores) de dimensión p



ak  ak1  akp T

bk  ak1  akp T
• La memoria lineal ha de ser una matriz de dimensión pxp
bk  Mak
a k1
ak 2
bk1
bk 2

akp

bkp
MEMORIAS LINEALES
• Una posibilidad sencilla consiste en emplear una matriz que contenga las
correlaciones entre estímulos y respuestas
N



N  bk1 


ˆ  bk aT     ak1  akp
M
k
k 1
k 1 b 
 kp 
La matriz puede reescribirse como
 aT 
 1 
ˆ  b1  bN     BAT
M
a T 
 N
Y obtenerse de forma recursiva como
ˆk M
ˆ k 1  bk aT ,
M
k
k  1,,N

Correlation
Matrix memory
ASOCIACION
• Cuando a una memoria lineal de correlación se le presenta unos de los
patrones almacenados, responde de la siguiente manera
ˆaj 
bM
 bk aTk a j   aTk a j bk
N
N
k 1
k 1


b  a Tj a j b j 
 aTk a j bk
N
k 1
k j
Si los estímulos (patrones) tienen energía unidad
b  bj 
Respuesta
deseada
 aTk a j bk
N
k 1
k j
Interferencia o
ruido
Escalar
ASOCIACION
• Si el conjunto de patrones a almacenar es ortonormal
1, k  j
aTk a j  
0, k  j
no existe interferencia entre patrones, entonces la respuesta al patrón a j es
b  bj 
0
aTk a j bk  b j

N
k 1
k j

• CAPACIDAD DE ALMACENAMIENTO :¿Cuántos patrones ortogonales se
pueden almacenar?
Rango(Μ )  p
PREPROCESADO
aj
Estimulo
cj
(Ort. GramSchmidt)
Memoria
Lineal
k 1 T
c a
ck  a k   i k
 T
i 1 ci ci


c ,
i

k  1, N
bj
Respuesta
MEMORIAS ADAPTATIVAS
ˆ (n) , el error al presentar
• Si en el instante n-ésimo la matriz de asociación es M
un nuevo patrón es
ˆ ( n)a k
ek (n)  bk  M
• Y podemos actualizar la matriz mediante un algoritmo tipo LMS


ˆ (n  1)  M
ˆ (n)   bk  M
ˆ (n)ak aT
M
k
a k  a k , y los patrones son
procedimiento adaptativo consigue una
• Si buscamos una memoria autoasociativa
ortogonales,
entonces
el
autoasociación perfecta
ˆ ()ak  ak
M
Los ak son lo autovectores de la matriz
ˆ ()
M
UN EJEMPLO
Patrones a
almacenar
ortonormales
1
0 0 0T  5 1 0T
0
1 0 0T   2 1 6T
0
0 1 0T   2 4 3T
5  2  2 0 
M  1 1
4 0


0 6
3 0
• La memoria asocia perfectamente Mak  bk
• Ante un patrón ruidoso obtiene la respuesta más cercana
 0.8 
5

2

2
0


  4 

0
.
15
1 1
   1.25 
4 0 

  0.15  

0 6
3 0 
  0.45

0
.
20


CONCLUSIONES
•
Una forma muy sencilla de conseguir la asociación entre patrones es
mediante una memoria lineal
•
Si los patrones son ortonormales mediante una matriz NxN podemos
almacenar N patrones y recuperarlos sin error
•
Si los patrones no son ortogonales existe interferencia entre ellos en el
proceso de recuperación
•
Es posible entrenar la memoria lineal mediante un LMS
LA RED DE HOPFIELD
GRUPO DE TRATAMIENTO AVANZADO DE SEÑAL (GTAS)
UNIVERSIDAD DE CANTABRIA
FUNCIONES DE ENERGIA COMO MEMORIAS
• Un sistema dinámico regido por una cierta función de energía evoluciona para
alcanzar estados de energía mínima
• Si conseguimos almacenar ciertos patrones en los valles de una función de
energía, el correspondiente sistema dinámico, empezando en un punto
cualquiera, evolucionará hacia una de estos patrones: es decir, el sistema
“recuerda” los patrones
LA RED DE HOPFIELD CONTINUA
v1
v2
v3
v4



x1 (t )
y2 (t )
y3 (t )




Ecuación de los nodos:
y1 (t )

y4 (t )
x2 ( t )
x3 (t )
Cj
dy j
dt
N
yj
 wij ( y j )  R

i 1
i j
x4 ( t )
j
 v j,
Salidas:
x j  (y j )
En forma matricial:
Cy  Gy  Wx  v
W
¡¡ La matriz de pesos de conexión entre neuronas ha de ser simétrica!!
WT W
wij  w ji
j 1,N
FUNCION DE LIAPUNOV
• Para el sistema dinámico que describe una Red de Hopfield podemos definir la
función de Liapunov o función de energía como
N
N
1
1 x j 1
E    wij xi x j     ( x j )dx j   v j x j
2 i j
R 0
j 1 j
j 1
• La red convergerá si: dE  0
dt
• En ese caso las salidas de la red xi evolucionan de tal manera que la Energía
disminuya
N
x
dE
T
  y x   yi2 i
dt
yi
i 1
xi
  ' ( yi )  0
yi
ya que la función de activación es monótonamente creciente,
por lo tanto dE  0
dt
CONVERGENCIA
• CONCLUSION: La Red de Hopfield siempre alcanza un punto de equilibrio
x   1,1Nen el que dE  0
dt
• A pesar de la realimentación presente en una Red de Hopfield, todos los
atractores
son
puntos
fijos
estables.
No
existen
ciclos
límite
ni
comportamiento caótico del sistema dinámico.
• La Red es determinista, por lo tanto, el punto estable alcanzado sólo depende
del punto inicial
• La simplicidad del comportamiento dinámico del la Red de Hopfield es debida
wij  w ji
en gran medida a la simetría del acoplamiento entre neuronas
LA RED DE HOPFIELD DISCRETA
z 1
z 1
z 1
z
v1
v2
v3
v4

y1(k )


y(k )  Wx(k )
o
1
x1(k  1)
y2 ( k )
y3 (k )
x2 (k  1)
x3 ( k  1)
y4 ( k )

x4 (k  1)
y(k )  Wx(k )  v
x(k  1)    y(k ) 
 1 v  0
-1 v  0
 ( y )  sgn( y )  
WT W
W
• Los elementos del vector x se pueden actualizar síncronamente (todos a la vez)
o asíncronamente (cada vez uno elegido aleatoriamente)
• La dinámica de la Red discreta es equivalente a la de la contínua
HOPFIELD COMO MEMORIA ASOCIATIVA
• Queremos que la Red memorice una serie de P patrones N-dimensionales
xi   1 1 1   1  1T
i  1,,P
• El problema es obtener una matriz de pesos W, tal que:
1.- los patrones a almacenar estén en los puntos de equilibrio
2.- los patrones más cercanos en distancia de Hamming a estos, pertenezcan a
su zona de atracción
• El objetivo 1 se puede conseguir para un número limitado de patrones
• El objetivo 2 sólo se puede conseguir de forma aproximada
HOPFIELD COMO MEMORIA ASOCIATIVA
• Una posibilidad sencilla consiste en seleccionar la matriz de pesos comc
1 P
W   xi xiT  PI
N i 1
0  1
1.-
Es simétrica
2.-
Los elementos de la diagonal principal del sumatorio suman P; el segundo
término, por lo tanto, disminuye la realimentación de una neurona consigo misma
3.-
Con   1, los elementos de la diagonal principal valen cero.
UN EJEMPLO EN MATLAB
% Queremos diseñar una Red de Hopfield con dos puntos estables (dos neuronas)
% situados en los puntos dados por T
T =[-1 1; 1 -1];
Espacio de estados para la Red de Hopfield
(1 -1)
1
a(2)
-1
-1
a(1)
1
(-1, 1)
UN EJEMPLO EN MATLAB
% Diseñamos la Red de Hopfield
net=newhop(T);
1 P
W   xi xiT  PI
N i 1
% La matriz de pesos incluye un término de bias
% Comprobamos si los patrones son puntos estable
[Y,Pf,Af]=sim(net,2,[],T)
Y=T
% Para comprobar la evolución dinámica de la Red de Hopfield, empleamos
notación “cell array”
a={rands(2,1)}
[Y,PF,Af]=sim(net,{1 40},{},a)
40 iteraciones
UN EJEMPLO EN MATLAB
% Pasamos a notación matricial estándar
a_mat=cell2mat(a);
Y_mat=cell2mat(Y);
estado=[a_mat Y_mat];
Evolución del estado de la Red de Hopfield
1
plot(estado(1,:),estado(2,:),'b')
0.5
0
-0.5
-1
-1
-0.5
0
0.5
1
UN EJEMPLO EN MATLAB
• Zonas de atracción para los puntos estables
1
0.5
0
-0.5
-1
-1
-0.5
0
0.5
1
MEMORIAS ESPUREAS
• En una Red de Hopfield es inevitable la presencia de estados estables
espúreos (memorias falsas)
1
-1
-1
1
• Para el ejemplo visto antes, en el (0,0) existe un punto estable de la dinámica
de la red de Hopfield: todos los puntos sobre la diagonal convergen al (0,0)
• En este caso el (0,0) no es absolutamente estable; cualquier perturbación lleva
a la red a alguno de los dos patrones almacenados
MEMORIAS ESPUREAS
• Pueden ser puntos estables espúreos:
- Un inverso de un patrón (la función de energía es la misma para xi y para  xi )
- Una combinación de un número impar de patrones
si  sgn( x1  x2  x3 )
• En general, pueden existir muchos más estados estables espúreos que
patrones almacenados:
- El número de memorias espúreas puede ser tan grande como exp(N)
- El número de patrones almacenados es como mucho N
FUNCIONAMIENTO DE LA RED
• Un patrón arbitrario de entrada puede expresarse como
z  xj n
• En la primera iteración formamos
y (1)  Wz  Wx j  n1
• Si tomamos la matriz de pesos como
P = es el
número de
patrones
N = es el
número de
neuronas
(longitud del
vector)
1 P
W   xi xiT
N i 1


Mide la correlación entre
los patrones i y j
1 P
1 P
T
y (1)   xi xi x j  n1   cij xi  n1
N i 1
N i 1
1 P
y (1)  x j   cij xi  n1  x j  n2  n1
N i 1
i j
FUNCIONAMIENTO DE LA RED
• Si el patrón inicial no tiene ruido y los patrones almacenados son ortogonales
n1  0,
N , i  j
cij  
 0, resto

  y (1)   x j
Recuperamos el patrón en
la primera iteración
• Mientras el término de ruido no cambie el signo de las componentes del patrón
  y (1)    x j  n1  n2   x j
Recuperamos el patrón en
la primera iteración
• En cualquier otro caso:
- Si y(1) está mas cercano a xj que la version ruidosa original z, la red convergerá
hacia xj
- La red puede recuperar otro de los patrones almacenados si y(1) está mas
cercano a xk
- La red puede converger a una memoria falsa
CAPACIDAD DE ALMACENAMIENTO
•¿ Cuántos patrones pueden ser almacenado en una red con N neuronas?
• Suponemos un caso sin ruido externo, el ruido es debido únicamente a la falta
de ortogonalidad entre patrones
1 P
y (1)  x j   cij xi
N i 1
Cada una de las componentes
del vector de ruido es una v. a.
Gaussiana de media nula y
varianza ( P  1) / N
i j
SNR 
varianza señal
1
N


varianza ruido ( P  1) / N P  1
• La probabilidad de recuperación correcta de un bit será
 N 

Pr ob yk  0 | x j ,k  1  1  Q
 P 1 


CAPACIDAD DE ALMACENAMIENTO
• La probabilidad de recuperar correctamente un patrón de N bits será

 N 
 
Prec  1  Q
P

1



N
• Fijando una probabilidad de recuperación del 99%, y haciendo algunas
aproximaciones adicionales, se obtiene que el número máximo de patrones
que pueden ser correctamente almacenados es
P
Por ejemplo, si N=256, P  12
N
4 ln( N )
¡ Capacidad de almacenamiento muy
limitada!
SINCRONA vs ASINCRONA
• En una actualización síncrona todos los nodos (neuronas) son actualizados
simultáneamente
• En una actualización asíncrona cada vez actualizamos una neurona elegida al
azar
• El tipo de actualización no cambia la función de energía: la red tiene los
mismos puntos estables
• Si que cambia, sin embargo, la dinámica de la red; es decir, el camino de
descenso por la superficie de energía
• En general, se ha comprobado que una actualización asíncrona tiene un mejor
comportamiento en cuanto a estabilidad y convergencia
APLIC.1: RECONOCIMIENTO DE CARACTERES
• Los caracteres están codificados como matrices de tamaño 7x5 de 1s y -1s
Patrón
x1
-1 -1 -1 -1 -1 -1 1 1 ... 1 1 -1 -1 -1 -1
Patrón
x2
1 -1 -1 -1 1 1 1 -1 ... -1 1 1 -1 -1 1
• Los patrones no son ortogonales
x1T x1  xT
2 x2  35
x1T x2  5
RECONOCIMIENTO DE CARACTERES
• Consideramos únicamente el almacenamiento de 2 caracteres.
• La matriz M tiene dimensiones 35x35
Entrada
Iteracion 1
Iteracion 2
Iteracion 3
APLIC. 2: OPTIMIZACIÓN COMBINATORIAL
• En los problemas de optimización combinatorial, la solución que minimiza la
función de coste requiere la búsqueda exhaustiva en un espacio que crece
combinatorialmente con el tamaño del problema
• Un ejemplo es el problema del viajante: ¿En que orden debe un viajante visitar
N ciudades para recorrer la mínima distancia, visitando cada ciudad una
única vez y empezando y terminando en el mismo punto?
A
C
A
B
C
D
E
A
B
0
0.175
0.195
0.893
0.275
B
0.175
0
0.207
0.793
0.175
C
0.195
0.207
0
1.0
0.195
D
0.893
0.793
1.0
0
0.814
E
0.275
0.175
0.195
0.814
0
E
D
¡¡¡¡HAY N ! POSIBILIDADES!!!
OPTIMIZACIÓN COMBINATORIAL
• El problema del viajante es un problema NP-completo:
- Los mejores algoritmos para encontrar la solución óptima necesitan un tiempo
que crece exponencialmente con el tamaño del problema
- Existen algoritmos subóptimos que corren un un tiempo polinómico
• La red de Hopfield permite obtener una solución subóptima de una forma muy
eficiente; para ello:
1) Hace falta una forma para representar soluciones (recorridos) como salidas de
la Red de Hopfield
2) Hace falta encontrar una matriz de pesos W y un vector de entrada v que den
origen a una función de energía cuyos mínimos correspondan a recorridos de
mínima longitud que cumplan las restricciones
y(k )  Wx(k )  v
x(k  1)    y(k ) 
REPRESENTACIÓN DE SOLUCIONES
• Una determinada neurona representa una determinada ciudad visitada en un
Ciudades
determinado lugar
Orden de visita
A
B
C
D
E
1
x Aj  
0
1
2
3
4
5
xA1
xB1
xC1
xD1
xE1
xA2
xB2
xC2
xD2
xE2
xA3
xB3
xC3
xD3
xE3
xA4
xB4
xC4
xD4
xE4
xA5
xB5
xC5
xD5
xE5


Ciudad A visitada en lugar j - ésimo
Ciudad A no visitada en lugar j - ésimo
• Necesitamos N2 neuronas
• Empleamos una codificación con 1s y 0s en vez de 1s y -1s
• Para ser un recorrido válido debe existir una y sólo una neurona activa por fila
y por columna
FUNCIÓN DE ENERGÍA
•Una posible función de energía cuyos mínimos son soluciones “válidas” del
problema del viajante es la siguiente
E  Ea  Eb  Ec
2
2
 


 
a 
Ea    x Li  1     x Li  1 

 

2  L  i
 

i  L

Siguiente
Eb 

Anterior
b


d LK xLi xKi
 xKi


2 i L K L
Ec  
c
( xLi ) 2

2 i L

Tiene un valor mínimo cuando
sólo hay una neurona activa por
fila y columna
Va acumulando las distancias
entre ciudades x Li  0
Tiene un valor mínimo cuando
todas las neuronas están
activas: evita que el término Eb
lleve todas las neuronas a cero
Típicamente a, b c son constantes cercanas a 1 (distancias normalizadas); además c  2a
MATRIZ DE PESOS Y EXCITACIÓN
• A partir de la función de energía, la matriz de pesos W y el vector de excitación
v se obtienen como
1
v  2a 

1 N 2 1
a
b
c
W   Wa  Wb  Wc
2
2
2
A
I
Wa  


I
I
A  I

  

I  A N 2  N 2
I
2 1  1 
1 2  1 

A
   


1 1  2 N N

W AA W AB  W AN 
W
W BB  W BN 
BA

Wb  
 


 


W NA W NB  W NN  N 2  N 2
 0
d
 XY
W XY   0

 0
d XY
Wc   I
N 2N 2
I N N
d XY
0

0
d XY
0
d XY
0

0

0
0

d XY
d XY 
0 

 

d XY 
0  N  N
RESULTADOS
• Para un problema con 5 ciudades existe 5!=120 soluciones válidas
• La Red de Hopfield creada tiene 330 puntos de equilibrio, entre ellos están las
120 soluciones válidas
• Con una actualización aleatoria, en el 50 % de las veces la red alcanza como
punto de convergencia un recorrido no válido
• La búsqueda del mínimo absoluto de la función de energía puede mejorarse si
empleamos una red de Hopfield estocástica
RED DE HOPFIELD ESTOCASTICA
• En la Red de Hopfield determinista, las evoluciones de la red siempre
disminuyen la función de energía
• En la Red de Hopfield estocástica existe una probabilidad de ir a estados más
altos de energía
 1, y j  0
 1, y j  0
Cambiamos  ( y j )  
y la probabilidad viene dada por
por
p( y j ) 
 1, con probabilid ad p(y j )
 1, con probabilid ad 1-p(y j )
( y j )  
1
1 e
y j T
siendo T una variable (temperatura) que inicialmente toma un valor elevado
y disminuye progresivamente tras cada iteración
• Se trata de un algoritmo de optimización tipo “simulated annealing”
MAXNET
• Permite encontrar de una forma muy sencilla el máximo de entre una colección
de N números
• La topología de la Maxnet es idéntica a una Red de Hopfield
• La no linealidad (signo) es reemplazada por la siguiente función
y
f ( y)  
0
y0
y0
• Como matriz de pesos se emplea
1
 
W 
 

 


1










1 
0    1/ N
N números
• La salida de todas las neuronas converge a cero excepto una
CONCLUSIONES
•
La Red de Hopfield es un sistema dinámico cuyos puntos de equilibrio
representan los patrones que deseamos almacenar
•
La estabilidad de la Red está relacionada con la simetría de la matriz de pesos W
•
El objetivo de diseño de una Red de Hopfield es encontrar una matriz de pesos W
y un vector de excitación v, tales que:
- Los mínimos de la función de energía estén en los patrones a almacenar
- La región de atracción de los puntos estables incluya todos los puntos más
cercanos al patrón deseado
•
Puede funcionar como memoria asociativa o puede resolver problemas
combinatoriales
•
Sus limitaciones son su limitada capacidad de almacenamiento y la presencia de
un elevado número de memorias falsas
•
Variantes; Red de Hopfield estocástica, Maxnet