Associação de padrões
•
A aprendizagem também pode ser entendida como um processo de
construção de associações entre padrões.
•
Caso geral: associar um padrão de entrada (representado por um
vector) a algum padrão já pré-especificado (memorizado).
•
Os padrões a associar podem ser de tipos diferentes
•
A memorização de um padrão (ou grupo de) também pode ser
considerada como associar o padrão a ele próprio.
Redes Neuronais
Associação de padrões
Departamento de Matemática
Universidade dos Açores
Hélia Guerra
[email protected]
http://www.uac.pt/~hguerra/Teaching/RN/RN.html
DM / UAç
Redes neuronais de memória associativa
•
Redes Neuronais 07/08
2
Redes neuronais de memória associativa
Uma associação é um par de padrões (s, t)
•
•
Consideramos redes simples, com um único nível, capazes de
aprender associações.
•
Os pesos são determinados de forma a que a rede possa armazenar
(memorizar) um conjunto de associações.
•
Para além de memorizar (aprender), a rede também é capaz de
responder com a associação correcta a um padrão de entrada
parecido com os que já foram memorizados,
Autoassociativas (s=t)
– Feedforward
– Recorrentes
•
Heteroassociativas (s≠t)
– Feedforward
– Recorrentes
DM / UAç
Redes Neuronais 07/08
3
DM / UAç
Redes Neuronais 07/08
4
Algoritmos de aprendizagem para associação de
padrões
Redes neuronais de memória associativa
•
Regra de Hebb
– Método mais simples e mais comum para determinar os pesos de uma
•
rede de memória associativa
Quantos padrões podem ser memorizados antes da rede se
– Utilizada com representações bipolares e binárias
“esquecer” dos que já tinha memorizado?
– Veremos algoritmo de treino e procedimento geral através do produto
exterior
•
Regra Delta
– Extensão da regra Delta anterior
– Função de activação sigmoide
– Utilizada com vectores de entrada linearmente independentes
DM / UAç
Redes Neuronais 07/08
Arquitecturas associativas
Redes Neuronais 07/08
6
Algoritmo de Hebb
0.
Atribuir valores iniciais aos pesos
wij=0, i=1,…,n, j=1,…,m;
1.
Repetir até esgotar as entradas (s:t)
I. Activar
xi=si, i=1,…,n
II. Fixar o impulso de resposta para cada unidade, j=1,…,m
yj=t
III. IV. Ajustar os pesos para cada unidade, j=1,…,m
11
1
1j
i1
1m
i
DM / UAç
5
ij
n1
wijnovo = wijvelho + y j xi , i = 1,..., n
im
nj
nm
n
DM / UAç
Redes Neuronais 07/08
7
DM / UAç
Redes Neuronais 07/08
8
Produto exterior
•
Memorização Hebbiana
•
O produto exterior dos vectores
s=[s1 s2 … sn] e t=[t1 t2 … tn]
Correlação entre a
unidade xi e a
unidade yj
é dado pela matriz
⎡ s1t1 K s1t j K s1t m ⎤
⎡ s1 ⎤
⎢
⎥
⎢... ⎥
K
⎢
⎥
⎢ ⎥
s T t = ⎢ si ⎥ × t1 ... t j ... t m = ⎢ si t1 K si t j K si t m ⎥
⎢
⎥
⎢ ⎥
K
⎢
⎥
⎢... ⎥
⎢ snt1 K snt j K snt m ⎥
⎢⎣ sn ⎥⎦
⎣
⎦
[
]
DM / UAç
Redes Neuronais 07/08
•
9
Memorização através da regra Delta
0.
Atribuir valores iniciais aos pesos e fixar coeficiente de aprendizagem α
wij=0, i=1,…,n, m=1,…,m; 0<α≤1
1.
Repetir até à convergência dos pesos e do pendor
Repetir os passos I-IV até esgotar as entradas (s:t)
I. Activar
xi=si, i=1,…,n
II. Fixar o impulso de resposta para cada unidade, j=1,…,m
yj=tj
III. Determinar a resposta e cada unidade, j=1,…,m
Para memorizar de um conjunto de associações { (s(p):t(p)): 1≤p≤P }, a
matriz dos pesos W={wij} é dada pelos elementos
P
wij = ∑ si ( p )t j ( p )
p =1
A resposta da rede com pesos W para o padrão x é y=x.W
DM / UAç
Redes Neuronais 07/08
10
Memorização através da regra Delta
IV. Ajustar os pesos, j=1,…,m
se f(yinj)≠tj
n
yin j = b j + ∑ xi wij
i =1
DM / UAç
wijnovo = wijvelho + α (t j − y j ) xi f ' ( yin j ), i = 1,..., n
Usar função de activação sigmóide
⎧ 1 se yin > θ j
j
⎪⎪
f ( yin j ) = ⎨ 0 se − θ j ≤ yin j ≤ θ j
⎪
⎩⎪− 1 se yin j < −θ j
Redes Neuronais 07/08
11
DM / UAç
Redes Neuronais 07/08
12
Função sigmóide binária e bipolar
f ( x) =
Rede de memória heteroassociativa
f ' ( x) = σf ( x)[1 − f ( x)]
1
1 + e −σx
1
1.4
1.2
0.8
1
0.6
11
1
0.8
1j
0.6
0.4
0.4
0.2
-4
i1
0.2
-2
2
-4
4
2
−1
g ( x) = 2 f ( x) − 1 =
1 + e −σx
-2
g ' ( x) =
σ
2
2
1m
4
[1 − g ( x)][1 + g ( x)]
ij
i
n1
1
1.4
im
1.2
0.5
1
nj
0.8
-4
-2
2
4
0.6
nm
0.4
n
-0.5
0.2
-1
DM / UAç
-4
-2
2
4
Redes Neuronais 07/08
DM / UAç
13
Algoritmo de exame à memória
Calcular os pesos W, recorrendo a regra de Hebb ou regra Delta
1.
Repetir para cada entrada de teste s
I. Activar
xi=si, i=1,…,n
II. Calcular o estímulo recebido por cada unidade, j=1,…,m
yinJ=x.W
III. Calcular a resposta (bipolar) de cada unidade unidade,
j=1,…,m
•
Para vectores de resposta binária
⎧⎪1
yj = ⎨
⎪⎩0
•
se
yin j > 0
se
yin j ≤ 0
Caso geral (com limiar)
⎧1 se yin j > θ j
⎪⎪
y j = ⎨ y j se yin j = θ j
⎪
⎩⎪− 1 se yin j < θ j
⎧1 se yin > 0
j
⎪⎪
y j = ⎨0 se yin j = 0
⎪
⎪⎩− 1 se yin j < 0
Redes Neuronais 07/08
14
Algoritmo de exame à memória
0.
DM / UAç
Redes Neuronais 07/08
15
DM / UAç
Redes Neuronais 07/08
16
Regra de Hebb
Rede de Hebb
•
A adequação da regra de Hebb a um problema especifico, depende
da correlação entre os vectores de treino.
•
Se os vectores forem ortogonais, a regra produzirá os pesos
correctos e a resposta da rede para entradas diferentes irá fazer
associações correctas.
•
Adequada quando os vectores de entrada forem linearmente
independentes – extensão da separabilidade linear a
vectores de saída
•
Se os vectores não forem ortogonais,
– Pode-se aplicar limiar para “atenuar” o efeito das correlações
– Pode-se normalizar pesos encontrados, recorrendo a um factor
de 1/n, onde n é o número de neurónios [Hertz, Krogh, Palmer,
1991]
DM / UAç
Redes Neuronais 07/08
17
Redes Autoassociativas
•
Caso particular das redes heteroassociativas anteriores
•
A aprendizagem consiste em memorizar informação, a relembrar
posteriormente
•
DM / UAç
Redes Neuronais 07/08
Rede de memória autoassociativa
11
1
i1
Um padrão memorizado pode ser lembrado a partir de um padrão
parecido
j
1n
ij
n1
O desempenho é avaliado pela habilidade em reproduzir um padrão
guardado, a partir de um padrão com ruído e distorcido
in
nj
•
Veremos processo de memorização pela Regra de Hebb, em que a
matriz dos pesos é submetida à anulação da diagonal
DM / UAç
Redes Neuronais 07/08
1
1j
i
•
18
19
n
nn
n
DM / UAç
Redes Neuronais 07/08
20
Algoritmo de Memorização (Hebb)
0.
Atribuir valores iniciais aos pesos
wij=0, i,j=1,…,n;
1.
Repetir até esgotar as entradas (s:s)
I. Activar
xi=si, i=1,…,n
II. Fixar o impulso de resposta para cada unidade, j=1,…,n
yj=si
III. IV. Ajustar os pesos para cada unidade, j=1,…,n
Memorização Hebbiana
•
pesos W={wij} é dada pelos elementos
Correlação entre a
unidade xi e a
unidade xj
wijnovo = wijvelho + y j xi , i = 1,..., n
DM / UAç
Redes Neuronais 07/08
Calcular a matriz dos pesos W
1.
Repetir para cada entrada de teste s
I. Activar
xi=si, i=1,…,n
II. Calcular o estímulo recebido por cada unidade, j=1,…,n
yinJ=x.W
III. Calcular a resposta (bipolar) de cada unidade unidade,
j=1,…,n
Redes Neuronais 07/08
p =1
A resposta da rede com pesos W para o padrão x é y=x.W
•
Capacidade de memorização corresponde ao número de padrões ( ou
pares de padrões) que podem ser guardados e recordados correctamente
DM / UAç
Redes Neuronais 07/08
22
Exemplo
•
Ao memorizar o vector [1 1 1 -1], obtém-se a matriz de pesos
⎡ 1 1 1 − 1⎤
⎢ 1 1 1 − 1⎥
⎥
W =⎢
⎢ 1 1 1 − 1⎥
⎢
⎥
⎣− 1 − 1 − 1 1⎦
•
Testar memória com padrões corrompidos (um erro)
– [-1 1 1 -1]
– [1 -1 1 -1]
⎧1 se yin > 0
j
⎪⎪
y j = ⎨0 se yin j = 0
⎪
⎪⎩− 1 se yin j < 0
DM / UAç
P
wij = ∑ si ( p ) s j ( p )
•
21
Algoritmo de exame à memória
0.
Para memorizar um conjunto de padrões { (s(p) : 1≤p≤P } , a matriz dos
•
Testar memória com padrões parcialmente definidos
– [0 0 1 -1]
– [0 1 0 -1]
•
― [1 1 -1 -1]
― [1 1 1 1]
― [0 1 -1 0]
― [1 0 0 -1]
Testar memória com padrão corrompido (dois erros)
– [-1 -1 1 -1]
23
DM / UAç
Redes Neuronais 07/08
24
Exemplo
•
•
Considerar a matriz de pesos anterior depois de submetida à anulação da
diagonal
1 1 − 1⎤
⎡ 0
⎢ 1 0
1 − 1⎥⎥
W0 = ⎢
⎢ 1 1 0 − 1⎥
⎥
⎢
⎣ − 1 − 1 − 1 0⎦
Memorizar [1 1 -1 -1], [-1 1 1 -1], [-1 1 -1 1]
0 −2
2⎤
⎡ 0
⎢ 0
−
0
0
2⎥⎥
W1 + W2 + W3 = ⎢
⎢− 2
0
0
0⎥
⎢
⎥
0
0⎦
⎣ 0 −2
― [1 1 -1 -1]
― [1 1 1 1]
•
Acrescentar [1 1 1 1 ]
⎡0
⎢0
W = W1 + W2 + W3 + W4 = ⎢
⎢0
⎢
⎣0
Testar memória com padrões parcialmente definidos
– [0 0 1 -1]
– [0 1 0 -1]
•
•
Testar memória com padrões corrompidos (um erro)
– [-1 1 1 -1]
– [1 -1 1 -1]
•
Exemplo
― [0 1 -1 0]
― [1 0 0 -1]
Testar memória com padrão corrompido (dois erros)
0 0 0⎤
0 0 0⎥⎥
0 0 0⎥
⎥
0 0 0⎦
– [-1 -1 1 -1]
DM / UAç
Redes Neuronais 07/08
•
•
Para m<n a matriz W é não singular. O valor próprio (n-m) tem
multiplicidade m a que correspondem os vectores próprios
a(1),…a(m).
Para m=n, zero é um valor próprio de multiplicidade n e não existem
vectores próprios não triviais.
•
Factorizar n: nkxm.
•
Construir vector de dimensão m vm(1)=[1 1 … 1]
•
Construir vectores ortogonais de dimensão 2m:
v2m(1)=[vm(1)+vm(1)],
26
Redes Neuronais 07/08
27
v2m(2)=[vm(1)-vm(1)]
•
Construir vectores ortogonais de dimensão 4m:
v4m(1)=[v2m(1)+v2m(1)],
v4m(2)=[v2m(1)-v2m(1)]
v4m(3)=[v2m(2)+v2m(2)],
v4m(4)=[v2m(2)-v2m(2)]
•
Continuar a construção até obter vn(1),…, vn(2k)
O número máximo de vectores bipolares ortogonais de dimensão n
que pode ser construído é 2k, com k=(n)1.
DM / UAç
Redes Neuronais 07/08
Algoritmo para construir vectores bipolares ortogonais
de dimensão n
Teorema de Szu
•
DM / UAç
25
DM / UAç
Redes Neuronais 07/08
28
Redes associativas iterativas
•
Rede de Hopfield
Adequadas em situações onde a rede não responde imediatamente
com o padrão correcto mas usa iterativamente a resposta obtida
como entrada para a iteração seguinte.
•
Hopfield 1982, Hopfield 1984 e Hopfield e Tank 1985
•
Rede de Hopfield (autoassociativa)
•
Cada neurónio está ligado a todos os outros
•
Rede BAM (heteroassociativa)
•
•
Os pesos são fixos e as activações é que se alteram
A matriz de pesos é simétrica (wij=wji)
•
Coloca-se a questão de saber se as activações convergem.
•
Não existe ligação de um neurónio para o próprio (wii=0)
DM / UAç
Redes Neuronais 07/08
DM / UAç
29
Arquitectura
Redes Neuronais 07/08
30
Rede de Hopfield
•
wn2
wn1
wni
Num determinado instante, cada neurónio actualiza a sua activação em
função dos estímulos recebidos pelos restantes neurónios e de um sinal
externo.
n
wi1
w2i
wi2
yini = xi + ∑ y j wij
win
j =1
w21
w2n
w12
x1
DM / UAç
w1n
w1i
xi
x2
Redes Neuronais 07/08
•
A actualização das activações é feita de modo assíncrono
•
Os neurónios não são rectroactivos mas são continuamente sensibilizados
pelo estímulo original
xn
31
DM / UAç
Redes Neuronais 07/08
32
Algoritmo de Memorização (Rede de Hopfield discreta)
•
Para memorizar um conjunto de P vectores binários s(p), p=1,…,P
a matriz de pesos W={wij} é dada por:
Algoritmo de exame à memória
0.
Repetir para cada entrada x
I. Activar
yi=xi, i=1,…,n
II. Repetir aleatoriamente para as unidades, i=1,…,n
a)
n
wij = ∑ (2 si ( p ) − 1)(2 s j ( p ) − 1), i ≠ j
P
p =1
wii = 0
•
Calcular a matriz dos pesos W (regra de Hebb)
1. Repetir até convergir
yini = xi + ∑ y j w ji
Para memorizar um conjunto de P vectores bipolares s(p),
p=1,…,P a matriz de pesos W={wij} é dada por:
=1
b) Calcular a jresposta
(binária)
⎧1 se yini > θ i
⎪
yi = ⎨ yi
se yini = θ i
⎪
⎩− 1 se yini < θ i
c) Alterar vector de activação
(enviar yi para todas as unidades yj, i≠j)
P
wij = ∑ si ( p ) s j ( p ), i ≠ j
p =1
wii = 0
DM / UAç
Redes Neuronais 07/08
DM / UAç
33
Observações
34
Convergência
•
Muitas vezes, utiliza-se o valor limiar 0
•
A ordem das actualizações dos neurónios é aleatória mas cada
neurónio tem que ser actualizado com a mesma frequência
•
Não é relevante se as entradas/activações são binárias ou bipolares
•
Não é relevante se o estímulo externo se mantém ou não após a
primeira iteração
•
Teorema de Lyapunov
Se relativamente a um sistema, existe uma função não crescente do
estado e limitada inferiormente, designada função de energia, então o
sistema evolui para estados de equilíbrio.
•
Hopfield mostrou que a rede de Hopfield discreta converge para um
estado limite, ao considerar a seguinte função de energia (de Lyapunov)
do sistema
E=−
– Em [Hopfield 1982] o estímulo externo não se mantém após a
primeira iteração
– Em [Hopfield 1984] o estímulo externo mantém-se durante
todo o processo
DM / UAç
Redes Neuronais 07/08
Redes Neuronais 07/08
35
DM / UAç
1
∑∑ yi y j wij − ∑i xi yi +∑i θi yi
2 i≠ j j
Redes Neuronais 07/08
36
Convergência
•
•
•
Capacidade de memorização
A variação ∆yi induz
•
⎛
⎞
∆E = −⎜⎜ ∑ y j wij +xi − θ i ⎟⎟
j
⎝
⎠
Hopfield (1984)
– O número de padrões binários que podem ser memorizados é
aproximadamente 15% do número de neurónios da rede.
⎛
⎞
∆E = −⎜⎜ ∑ y j wij +xi − θ i ⎟⎟∆yi
⎝ j
⎠
se ∆yi > 0, ∑ y j wij +xi − θ i > 0, ∆E < 0
j
•
se ∆yi = 0, ∑ y j wij +xi − θ i = 0, ∆E = 0
•
McEliece, Posner, Rodemich e Venkatesh, (1987)
j
se ∆yi < 0, ∑ y j wij +xi − θ i < 0, ∆E < 0
j
•
∆E≤0 e como a energia é limitada inferiormente, a rede tem que encontrar
um estado de equilíbrio
DM / UAç
Redes Neuronais 07/08
37
•
Kosko 1988
•
Rede de memória heteroassociativa (recorrente)
•
Tem dois níveis (camadas) de neurónios (X e Y) ligados através de
ligações bidireccionais
A rede envia, iterativamente, informação entre os dois níveis até
atingir o equilíbrio
•
Matriz dos pesos das ligações é simétrica (wij=wji)
•
Não existe ligação de um neurónio para o próprio (wii=0)
DM / UAç
Redes Neuronais 07/08
DM / UAç
Redes Neuronais 07/08
38
Arquitectura
Rede de Memória Associativa Bidireccional (BAM)
•
– O número de padrões bipolares que podem ser memorizados é
aproximadamente n/2log2n, onde n denota o número de
neurónios
39
n1
11
11
DM / UAç
i1
1j
ij
Redes Neuronais 07/08
ni
im
nm
40
BAM discreta
Algoritmo de Memorização (BAM discreta)
•
•
As duas formas da BAM bivalentes (bipolar/binária) são muito parecidas
Para memorizar um conjunto de P pares de vectores binários
s(p):t(p), p=1,…,P a matriz de pesos W={wij} é dada por:
wij = ∑ (2 si ( p ) − 1)(2t j ( p ) − 1), i ≠ j
P
•
A memorização é feita, tal como para a rede de Hopfield
–
p =1
soma dos produtos exteriores do formato bipolar dos pares de vectores
de treino
•
•
Para memorizar um conjunto de P pares de vectores bipolares
s(p):t(p), p=1,…,P a matriz de pesos W={wij} é dada por:
A função de activação é a função de Heaviside com a possibilidade do limiar
ser diferente de zero.
P
wij = ∑ si ( p )t j ( p ), i ≠ j
p =1
DM / UAç
Redes Neuronais 07/08
Função de activação
•
DM / UAç
41
0.
Calcular a matriz dos pesos W (regra de Hebb) e desactivar todas
as unidades (inicializar activações a 0)
1. Repetir para todos os vectores de estímulos s:t
I. Activar
⎧1 se xini > 0
⎪
xi = ⎨ xi
se xini = 0
⎪
⎩0 se xini < 0
yj=tj, j=1,…,m
xi=si, i=1,…,n
II. Repetir até convergir
n
y j = f yin j
a)
yin = xi wij
j
•
Bipolar
( )
∑
i =1
ecoar o sinal para o nível X
⎧1 se yin j > θ j
⎪⎪
y j = ⎨ y j se yin j = θ j
⎪
⎩⎪− 1 se yin j < θ j
DM / UAç
42
Algoritmo de exame à memória
Binária
⎧1 se yin j > 0
⎪⎪
y j = ⎨ y j se yin j = 0
⎪
⎪⎩0 se yin j < 0
Redes Neuronais 07/08
b)
⎧1 se xini > θ i
⎪
xi = ⎨ xi
se xini = θ i
⎪
⎩− 1 se xini < θ i
Redes Neuronais 07/08
m
xini = ∑ y j w ji
j =1
( )
xi = f xini
ecoar o sinal para o nível Y
43
DM / UAç
Redes Neuronais 07/08
44
Observações
•
BAM contínua
•
Transforma de forma contínua entradas em saídas no intervalo [0,1].
•
Estímulo recebido por cada unidade
Quando a entrada é igual ao limiar, a activação da unidade não se
altera
n
m
•
Algoritmo está feito para no inicio o sinal ser enviado do nível X para
o nível Y
Redes Neuronais 07/08
•
1
1+ e
− xini
DM / UAç
( )
y j = f yin j =
1
1+ e
Redes Neuronais 07/08
− yin j
46
Apagar memória
Função de energia é
(
r
r
1 r r
E = − x Wy T + y T W T x
2
r rT
= − x Wy
m
)
j =1 i =1
m
•
Seja x um vector bipolar. Vector complemento de x, denotado por
xc, é o vector que se obtêm de x substituindo os 1’s por -1’s e os -1’s
por 1’s.
•
Memorizar s:t é equivalente a memorizar sc:tc
•
Apagar s:t é equivalente a memorizar sc:t ou s:tc
n
= −∑∑ xi wij y j
n
≥ −∑∑ | wij | (para funções de activação binárias/bipolares)
j =1 i =1
•
xi = f xini =
45
Convergência
A função de activação é a função sigmóide
( )
O envio dos sinais entre os dois níveis não é feito simultaneamente
DM / UAç
i =1
j =1
•
•
yin j = b j + ∑ xi wij
xini = bi + ∑ y j w ji
[Kosko 1992] - a função E é decrescente á medida que se vai iterando,
quer para actualizações assíncronas ou síncronas.
DM / UAç
Redes Neuronais 07/08
47
DM / UAç
Redes Neuronais 07/08
48
Capacidade de memorização
•
O número de padrões que pode ser memorizado é min(n,m)
•
[Haines, Hecht-Nielsen 1988] : O número de padrões que pode ser
memorizado é min(2n,2m), desde que limiar seja diferente de zero
DM / UAç
Redes Neuronais 07/08
49