Anotações
Estrutura de tópicos
Redes Neurais Artificiais
Memórias Associativas
Conceitos Básicos - Memória Associativa
É um conceito “intuitivo”.
Parece ser uma das funções primárias do cérebro.
Facilmente ASSOCIAMOS a face de um amigo com seu nome, ou um nome a um número de telefone.
Também serve para reconstituir padrões “corrompidos” ou incompletos.
Se olharmos uma foto com os lábios da Natasha Kinsky, logo recompomos todo o seu rosto.
Se vemos um amigo que normalmente não usa óculos, com eles, ainda assim, reconhecemos a face como sendo da pessoa em questão.
Recuperação de informação pelo “conteúdo”
Redes Neurais Artificiais
Memórias Associativas
Definições Iniciais
Algumas Medidas de Distância
Distância no Espaço Euclidiano
Redes Neurais Artificiais
Memórias Associativas
Definições Iniciais
Algumas Medidas de Distância
Distância no Espaço de Hamming
Redes Neurais Artificiais
Memórias Associativas
Definições Iniciais
Distância de Hamming X Distância Euclidiana
Dados dois pontos (xi,yi) Î{-1,+1}
Distância Euclidiana
(x1-x2)2 Î{0,4}
Distância Euclidiana: d = Ö4(# “desencontros”)
Distância de Hamming
Distância de Hamming: h = # “desencontros”
d = 2Öh
Redes Neurais Artificiais
Memórias Associativas
Memórias Associativas - Definição Formal
Associadores Lineares
Suponha que tenhamos L pares de vetores, {(X1,Y1),(X2,Y2),...,(XL,YL)}, com XiÎÂn, e YiÎÂm.
Chamamos a estes vetores exemplares.
O que desejamos com os Associadores Lineares é fazer um “mapeamento” F de X para Y.
Podemos distinguir então 3 tipos de MEMÓRIAS ASSOCIATIVAS.
Redes Neurais Artificiais
Memórias Associativas
Memórias Heteroassociativas
Implementa um mapeamento F de X para Y tal que F (Xi) = Yi. Se X for o mais próximo (menor distância de Hamming) de Xi do que qualquer Xj, j=1,2,...,L, então F (X) = Yi.
Memórias Associativas Interpolativas
Implementa um mapeamento F de X para Y tal que F (Xi) = Yi. Mas se o vetor de entrada X diferir de um exemplar Xi  por um vetor D, de forma que X=Xi+D, então a saída da memória também  difere dos exemplares de saída por um vetor E, ou seja:
F (X) = F (Xi+D) = Yi +E.
Redes Neurais Artificiais
Memórias Associativas
Memórias Autoassociativas
Assume que Xi = Yi e implementa um mapeamento F de X para X tal que F (Xi) = Xi. Se X for o mais próximo (menor distância de Hamming) de Xi do que qualquer Xj, j=1,2,...,L, então F (X) = Xi.
Redes Neurais Artificiais
Memórias Associativas
Implementação Matemática
Construir uma memória associativa não é difícil se introduzirmos a restrição de que os vetores exemplares devam ser “ortonormais” entre si (vetores dos vértices de um Cubo de Hamming).
XiT.Xj=dij, onde dij= 1 se i=j, e dij=0 se i¹j.
F (X) = (Y1X1T + Y2X2T + ... + YLXLT).X
Exemplo
F (X2) = (Y1X1T + Y2X2T + ... + YLXLT).X2
F (X2) = Y1X1T X2 + Y2X2T X2 + ... + YLXLTX2
F (X2) = Y1d12 + Y2 d 22 + ... + YL d L2
dij=0  i¹j,  dij=1  i=j
F (X2) = Y2
Redes Neurais Artificiais
Memórias Associativas
Implementação por Redes Neurais (Elementos Processadores Distribuídos)
A MEMÓRIA BAM
(Bidirectional Associative Memory)
Consiste de duas camadas de neurônios que estão completamente conectados entre as camadas. Cada neurônio está conectados a si mesmo.
O peso das conexões é determinado  a-priori, baseado nos vetores de “treinamento”.
Redes Neurais Artificiais
Memória BAM
Redes Neurais Artificiais
Memória BAM
“Treinamento” da BAM
A matriz de pesos W é construída utilizando o modelo de Associador Linear.
Dados L pares de vetores que constituem o conjunto de exemplares que desejamos armazenar,
W= Y1X1T + Y2X2T + Y3X3T + ... + YLXLT
fornece os pesos das conexões da camada X para a camada Y.
WT
fornece os pesos das conexões da camada Y para a camada X.
Redes Neurais Artificiais
Memória BAM
Processamento da BAM
Cálculo das Matrizes de Pesos
Recuperação da Informação
 Aplicar um par de vetores iniciais (X0,Y0).
 Propagar a informação de X para Y (multiplicar X0 pela matriz W) e atualizar Y.
 Propagar a informação atualizada de Y para X (multiplicar Y pela matriz WT) e atualizar X.
 Repetir os passos 2 e 3 até não haver mudança nos valores dos neurônios.
Dado X0 o resultado será Xi com a menor distância de Hamming de X0.
Redes Neurais Artificiais
Memória BAM
Algumas Considerações
É este algoritmo que fornece à BAM suas características bi-direcionais.
Os termos “entrada” e “saída” dependem da direção atual de propagação.
Após algumas iterações a rede irá estabilizar em um estado estável.
Não sobrecarregar demais a memória com muita informação, ou ela irá estabilizar em um “estado espúrio” (crosstalk).
O Crosstalk ocorre quando os padrões exemplares estão muito “próximos” uns dos outros.
Redes Neurais Artificiais
Memória BAM
Matemática da BAM
Os neurônios calculam o net, como neurônios “normais”:
Redes Neurais Artificiais
Memória BAM
Matemática da BAM
Os neurônios calculam o net, como neurônios “normais”:
Redes Neurais Artificiais
Memória BAM
Matemática da BAM
O valor da saída para cada neurônio depende do valor do net e do valor da saída “anterior”.
Redes Neurais Artificiais
Memória BAM
Alguns exemplos
Redes Neurais Artificiais
Memória BAM
Exemplo - continuação
Tomemos X0=[-1,-1,-1,1,-1,1,1,-1,-1,1]T
h(X0,X1)=1 e h(X0,X2)=7 (distância de Hamming)
Fazemos Y0 igual a um dos vetores exemplares (ou usamos um vetor bipolar aleatório) Y0=Y2=[1,1,1,1,-1,-1]T.
Propagamos de X para Y, já que a “chave” é X0.
netY=W.X0=[4,-12,-12,-12,4,12]T
Calculamos o novo vetor Y, Ynew=[1,-1,-1,-1,1,1]T
Propagamos agora de Y para X.
netX=[4,-8,-8,8,-4,8,4,-8,-4,8]T
Calculamos o novo vetor X, Xnew=[1,-1,-1,1,-1,1,1,-1,-1,1]T
Novas propagações não alterarão o resultado e portanto consideramos a memória estabilizada e com o padrão X1 recuperado.
Redes Neurais Artificiais
Memória BAM
Exemplo 2
Tomemos X0=[-1,1,1,-1,1,1,1,-1,1,-1]T e Y0=[-1,1,-1,1,-1,-1]T
h(X0,X1)=7 e h(X0,X2)=5 (distância de Hamming)
h(Y0,Y1)=4 e h(Y0,Y2)=2
Propagamos de X para Y, já que a “chave” é X0.
netY=W.X0=[-4,4,4,,4,-4]T
Calculamos o novo vetor Y, Ynew=[-1,1,1,1,1,-1]T
Propagamos agora de Y para X.
netX=[-4,8,8,-8,4,-8,-4,8,4,-8]T
Calculamos o novo vetor X, Xnew=[-1,1,1,-1,1,-1,-1,1,1,-1]T
Novas propagações não alterarão o resultado e portanto consideramos a memória estabilizada.
Qual foi o padrão recuperado?
Redes Neurais Artificiais
Memória BAM
Exemplo 2 - continuação
O padrão recuperado foi o “complemento” de X1.
Propriedade básica da BAM: Se armazenamos um padrão (X,Y), automaticamente armazenamos o complemento do padrão.
Não é comum uma criança dizer “apaga” a luz quando na verdade quer acender a luz?
Redes Neurais Artificiais
Memória BAM
A Equação de Energia da BAM
Uma “conversa” a respeito de ESTABILIDADE e CONVERGÊNCIA.
O processamento de sistemas neurais artificiais é governado tipicamente por duas áreas da matemática: a ESTABILIDADE GLOBAL e a CONVERGÊNCIA.
ESTABILIDADE GLOBAL é a eventual estabilização de todas as ativações dos neurônios a partir de uma entrada inicial.
CONVERGÊNCIA é a eventual minimização do erro entre as saídas calculadas e desejadas.
Redes Neurais Artificiais
Memória BAM
Uma “conversa” a respeito de ESTABILIDADE e CONVERGÊNCIA.
Durante o processo de treinamento, nas redes diretas com neurônios estáticos, os pesos formavam um sistema dinâmico. Isto é, os pesos se alteravam em função do tempo, e estas alterações podiam ser representadas por um conjunto de equações diferenciais.
Para a BAM, uma situação diferente ocorre. Os pesos são calculados anteriormente e não fazem parte do sistema dinâmico. Por outro lado, a rede pode levar vários “passos” até se estabilizar. Neste caso os vetores X e Y mudam em função do tempo e formam um sistema dinâmico.
Redes Neurais Artificiais
Memória BAM
Uma “conversa” a respeito de ESTABILIDADE e CONVERGÊNCIA.
A questão então para os sistemas dinâmicos representados por redes neurais artificiais é se o sistema vai CONVERGIR para uma SOLUÇÃO ESTÁVEL.
Infelizmente muitos modelos de redes neurais não possuem provas para a convergência.
Quanto a estabilidade, na teoria de sistemas dinâmicos, um teorema pode ser provado no que diz respeito a existência de estados estáveis.
Este teorema utiliza o conceito de uma função chamada FUNÇÃO DE LYAPUNOV.
Redes Neurais Artificiais
Memória BAM
Uma “conversa” a respeito de ESTABILIDADE e CONVERGÊNCIA.
FUNÇÃO DE LYAPUNOV
Definição: um ponto fixo c é estável no sentido de Lyapunov se para todo e > 0 existir um d > 0 tal que se ||x(t0)- c ||< d, então ||x(t)- c ||< e para todo t >=t0. Se além disso toda vizinhança de x(t0) tende para c quando t vai a µ, dizemos que c é assintoticamente estável.
Redes Neurais Artificiais
Memória BAM
FUNÇÃO DE LYAPUNOV
Se pudermos encontrar uma função limitada das variáveis de estado de um sistema dinâmico, de tal modo que toda mudança de estado resulte em uma diminuição do valor da função, então o sistema possui uma solução estável.
Esta função é chamada de Função de Lyapunov ou Função de Energia.
Redes Neurais Artificiais
Memória BAM
A Equação de Energia da BAM
No caso da BAM, a Função de Lyapunov existe e é chamada função de energia da BAM e possui a forma:
E(X,Y) = -YT.W.X
ou em termos dos seus componentes:
Redes Neurais Artificiais
Memória BAM
A Equação de Energia da BAM
Teorema de Cohen-Grossberg de Estabilidade da BAM
1. Qualquer mudança em X ou Y durante o processamento da BAM resulta em uma diminuição de E.
2. E é limitada inferiormente por Emin = -Sij|wij|.
3. Quando E muda, ela deve mudar de valores finitos.
Itens 1 e 2 provam que E é uma função de Lyapunov. Item 3 restringe a possibilidade que as mudanças em E sejam infinitesimais, o que levaria a um tempo de convergência infinito.
Redes Neurais Artificiais
Memória BAM
A Equação de Energia da BAM
Redes Neurais Artificiais
Memória BAM
A Equação de Energia da BAM
Exemplo
Para o exemplo 1 visto anteriormente:
Emin = -Sij|wij| = - 64
para X0=[-1,-1,-1,1,-1,1,1,-1,-1,1]T  e Y0=[1,1,1,1,-1,-1]T
E = -Y0TWX0 = - 40
para X0=[-1,-1,-1,1,-1,1,1,-1,-1,1]T  e Ynew=[1,-1,-1,-1,-1,1]T
E = -YTnewWX0 = - 56
para Xnew=[1,-1,-1,1,-1,1,1,-1,-1,1]T  e Ynew=[1,-1,-1,-1,-1,1]T
E = -YTnewWXnew = - 64