|
|
|
|
|
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” |
|
|
|
|
|
|
Definições Iniciais |
|
Algumas Medidas de Distância |
|
Distância no Espaço Euclidiano |
|
|
|
|
|
|
Definições Iniciais |
|
Algumas Medidas de Distância |
|
Distância no Espaço de Hamming |
|
|
|
|
|
|
|
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 |
|
|
|
|
|
|
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. |
|
|
|
|
|
|
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. |
|
|
|
|
|
|
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. |
|
|
|
|
|
|
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 |
|
|
|
|
|
|
|
|
|
|
|
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”. |
|
|
|
|
|
|
|
“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. |
|
|
|
|
|
|
|
|
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. |
|
|
|
|
|
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. |
|
|
|
|
|
Matemática da BAM |
|
Os neurônios calculam o net, como neurônios
“normais”: |
|
|
|
|
|
Matemática da BAM |
|
Os neurônios calculam o net, como neurônios
“normais”: |
|
|
|
|
|
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”. |
|
|
|
|
|
|
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. |
|
|
|
|
|
|
|
|
|
|
|
|
|
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? |
|
|
|
|
|
|
|
|
|
|
|
|
|
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? |
|
|
|
|
|
|
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. |
|
|
|
|
|
|
|
|
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. |
|
|
|
|
|
|
|
|
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. |
|
|
|
|
|
|
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. |
|
|
|
|
|
|
|
|
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. |
|
|
|
|
|
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: |
|
|
|
|
|
|
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. |
|
|
|
|
A Equação de Energia da 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 |
|