1 MEMORIAS AUTOASOCIATIVAS

2 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) Memoria (Matriz) Estímulo (Vector) a Respuesta (Vector) b Pueden ser: - Lineales/No lineales - Autoasociativas/Heteroasociativas Un MLP o una RBF adecuadamente entrenados pueden funcionar como memorias no lineales

3 MEMORIAS Una vez entrenada, la memoria puede recuperar un patrón a partir de información parcial o ruidosa

4 Queremos una estructura lineal que “memorice” el siguiente problema: MEMORIAS LINEALES EstímulosRespuestas Los estímulos y las respuestas son patrones (vectores) de dimensión p La memoria lineal ha de ser una matriz de dimensión pxp

5 MEMORIAS LINEALES Una posibilidad sencilla consiste en emplear una matriz que contenga las correlaciones entre estímulos y respuestas La matriz puede reescribirse como Y obtenerse de forma recursiva como Correlation Matrix memory

6 ASOCIACION Cuando a una memoria lineal de correlación se le presenta unos de los patrones almacenados, responde de la siguiente manera Si los estímulos (patrones) tienen energía unidad Escalar Respuesta deseada Interferencia o ruido

7 ASOCIACION Si el conjunto de patrones a almacenar es ortonormal no existe interferencia entre patrones, entonces la respuesta al patrón es 0 CAPACIDAD DE ALMACENAMIENTO :¿Cuántos patrones ortogonales se pueden almacenar?

8 PREPROCESADO Memoria Lineal Respuesta (Ort. Gram- Schmidt) Estimulo

9 MEMORIAS ADAPTATIVAS Si en el instante n-ésimo la matriz de asociación es, el error al presentar un nuevo patrón es Y podemos actualizar la matriz mediante un algoritmo tipo LMS Si buscamos una memoria autoasociativa, y los patrones son ortogonales, entonces el procedimiento adaptativo consigue una autoasociación perfecta Los son lo autovectores de la matriz

10 UN EJEMPLO Patrones a almacenar ortonormales La memoria asocia perfectamente Ante un patrón ruidoso obtiene la respuesta más cercana

11 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

12 LA RED DE HOPFIELD GRUPO DE TRATAMIENTO AVANZADO DE SEÑAL (GTAS) UNIVERSIDAD DE CANTABRIA

13 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

14 LA RED DE HOPFIELD CONTINUA Ecuación de los nodos: Salidas: En forma matricial: ¡¡ La matriz de pesos de conexión entre neuronas ha de ser simétrica!! W

15 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 ya que la función de activación es monótonamente creciente, por lo tanto La red convergerá si: En ese caso las salidas de la red evolucionan de tal manera que la Energía disminuya

16 CONVERGENCIA CONCLUSION: La Red de Hopfield siempre alcanza un punto de equilibrio en el que 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 simplicidad del comportamiento dinámico del la Red de Hopfield es debida en gran medida a la simetría del acoplamiento entre neuronas La Red es determinista, por lo tanto, el punto estable alcanzado sólo depende del punto inicial

17 LA RED DE HOPFIELD DISCRETA La dinámica de la Red discreta es equivalente a la de la contínua Los elementos del vector x se pueden actualizar síncronamente (todos a la vez) o asíncronamente (cada vez uno elegido aleatoriamente) o W

18 HOPFIELD COMO MEMORIA ASOCIATIVA El objetivo 1 se puede conseguir para un número limitado de patrones El objetivo 2 sólo se puede conseguir de forma aproximada Queremos que la Red memorice una serie de P patrones N-dimensionales 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

19 HOPFIELD COMO MEMORIA ASOCIATIVA Una posibilidad sencilla consiste en seleccionar la matriz de pesos comc 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, los elementos de la diagonal principal valen cero.

20 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]; 1 1 Espacio de estados para la Red de Hopfield (1 -1) (-1, 1)a(1) a(2)

21 UN EJEMPLO EN MATLAB % Diseñamos la Red de Hopfield net=newhop(T); % 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

22 UN EJEMPLO EN MATLAB a_mat=cell2mat(a); % Pasamos a notación matricial estándar Y_mat=cell2mat(Y); estado=[a_mat Y_mat]; plot(estado(1,:),estado(2,:),'b') -0.500.51 -0.5 0 0.5 1 Evolución del estado de la Red de Hopfield

23 UN EJEMPLO EN MATLAB Zonas de atracción para los puntos estables

24 MEMORIAS ESPUREAS En una Red de Hopfield es inevitable la presencia de estados estables espúreos (memorias falsas) 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 1 1

25 MEMORIAS ESPUREAS Pueden ser puntos estables espúreos: - Un inverso de un patrón (la función de energía es la misma para y para ) - Una combinación de un número impar de patrones 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

26 FUNCIONAMIENTO DE LA RED Un patrón arbitrario de entrada puede expresarse como En la primera iteración formamos Si tomamos la matriz de pesos como Mide la correlación entre los patrones i y j N = es el número de neuronas (longitud del vector) P = es el número de patrones

27 FUNCIONAMIENTO DE LA RED Si el patrón inicial no tiene ruido y los patrones almacenados son ortogonales 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 Recuperamos el patrón en la primera iteración En cualquier otro caso: - Si y(1) está mas cercano a x j que la version ruidosa original z, la red convergerá hacia x j - La red puede recuperar otro de los patrones almacenados si y(1) está mas cercano a x k - La red puede converger a una memoria falsa

28 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 Cada una de las componentes del vector de ruido es una v. a. Gaussiana de media nula y varianza La probabilidad de recuperación correcta de un bit será

29 CAPACIDAD DE ALMACENAMIENTO La probabilidad de recuperar correctamente un patrón de N bits será 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 Por ejemplo, si N=256, P 12 ¡ Capacidad de almacenamiento muy limitada!

30 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

31 APLIC.1: RECONOCIMIENTO DE CARACTERES Los caracteres están codificados como matrices de tamaño 7x5 de 1s y -1s -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 1 Los patrones no son ortogonales

32 RECONOCIMIENTO DE CARACTERES Consideramos únicamente el almacenamiento de 2 caracteres. La matriz M tiene dimensiones 35x35 EntradaIteracion 1Iteracion 2Iteracion 3

33 APLIC. 2: OPTIMIZACIÓN COMBINATORIAL D A C E B ¡¡¡¡HAY N ! POSIBILIDADES!!! 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?

34 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

35 Orden de visita Ciudades REPRESENTACIÓN DE SOLUCIONES Necesitamos N 2 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 Una determinada neurona representa una determinada ciudad visitada en un determinado lugar

36 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 Tiene un valor mínimo cuando sólo hay una neurona activa por fila y columna Va acumulando las distancias entre ciudades SiguienteAnterior Tiene un valor mínimo cuando todas las neuronas están activas: evita que el término E b lleve todas las neuronas a cero Típicamente a, b c son constantes cercanas a 1 (distancias normalizadas); además

37 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

38 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

39 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 Cambiamospor y la probabilidad viene dada por 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”

40 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 Como matriz de pesos se emplea N números La salida de todas las neuronas converge a cero excepto una

41 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