Memórias associativas. Redes de Hopfield.

Recordar é viver! Na linguagem comum, recordar algo consiste em associar uma ideia ou pensamento a uma sugestão sensorial. Por exemplo, se alguém menciona o nome de uma celebridade, lembramo-nos imediatamente de uma série de TV ou de um artigo de jornal sobre essa celebridade. Se alguém nos mostra uma imagem de um lugar que visitámos, essa imagem faz-nos recordar pessoas que conhecemos e experiências que vivemos nesse momento. O sentido do olfato também pode provocar memórias e é conhecido por ser especialmente eficaz em evocar recordações.

Uma memória associativa pode ser bastante poderosa. Suponhamos que armazenamos, numa rede neuronal (veremos em breve o que isto significa), informações codificadas sobre muitos cientistas famosos. Então, dado o padrão de partida “evolução”, a rede deve ser capaz de responder lembrando tudo sobre Darwin, enquanto que o padrão de partida “E = mc²” deve evocar Einstein. Outros exemplos comuns de aplicações das memórias associativas são a reconstrução de imagens corrompidas, o reconhecimento de números escritos à mão, a recuperação de informações bibliográficas a partir de referências parciais (como, por exemplo, o título incompleto de um livro), entre outros.

Problema. Construir uma rede neuronal (artificial), que, neste caso, chamar-se-á uma Rede de Hopfield, que armazene um conjunto de \(M\) padrões (ou memórias) \(P=p_1,p_2,\cdots,p_M\).

Cada padrão é descrito por atributos numéricos.

\(\mathrm{x}^p=(x_1^p,x_1^p,\cdots,x_1^p)\)

de tal forma a rede neuronal de Hopfield tem \(n\) neurónios.

Quando se apresenta um novo padrão \(p_{\mathrm{novo}}\), a rede responde associando a \(p_{\mathrm{novo}}\) o padrão armazenado, digamos \(\hat{p}\in P\), que mais se assemelha a \(p_{\mathrm{novo}}\).

A medida de semelhança é dada pela distância Hamming \(d_H\), definida por

\(d _ { H } ( p , q ) = \sum _ { i = 1 } ^{n} \delta ( x _ { i } ^{p} , x _ { i } ^{q} ) )\)

onde

\(\delta \left( a , b \right) = \left\{ \begin{array}{ll} { 1 } & { \mathrm { ~ s e ~ } \ a = b } \\{ 0 } & { \mathrm { ~ s e ~ } \ a \neq b } \end{array} \right.\)

Por exemplo, na FIGURA 1, a distância de Hamming entre as faces e é igual a:

\(d _ { H } ( \mathrm { f a c e ~ 2 , ~ f a c e ~ 7 } ) = d _ { H } \{ ( - 1 , - 1 , + 1 , - 1 ) , ( + 1 , + 1 , + 1 , + 1 ) \} = 3\)

Um exemplo simples.

Suponhamos que queremos armazenar, numa rede de Hopfield, as 10 faces (padrões ou memórias) que se mostram na figura seguinte.

Em primeiro lugar, notamos que cada face é caracterizada por 4 atributos: \(x_1\)= cabelo, \(x_2\)= olhos, \(x_3\)= nariz e \(x_4\)= boca.

Cada um destes atributos \(x_i\) tem dois valores possíveis: existem dois tipos de cabelo, dois tipos de olhos, dois tipos de narizes e dois tipos de boca.

Cada uma das 10 faces será, portanto, codificada por uma sequência ordenada de 4 valores \(±1\), usando o código da tabela da FIGURA 2. Na FIGURA 1, podemos ver a codificação de cada face através de um vetor de 4 entradas iguais a \(±1\).

Por exemplo, a face 1 é codificada pelo vetor:

\(x ^{\mathrm {face}1 } = ( + 1 , + 1 , + 1 , - 1 )\)

Porque o cabelo, os olhos e o nariz são todos de tipo \(+1\), enquanto que a boca é de tipo \(-1\), de acordo com o código da FIGURA 2.

Convém juntar o valor possível 0 a cada atributo, o que corresponde à ausência do atributo; por exemplo, ausência de nariz ou de cabelo, etc., o que traduz imagens corrompidas. Na FIGURA 3 vemos um exemplo:

Como cada face tem 4 atributos \(-x_1\)= cabelo, \(-x_2\)= olhos, \(-x_3\)= nariz e \(-x_4\)= boca — a rede de Hopfield tem 4 nós (neurónios), como na FIGURA 4. Cada um dos nós está ligado aos restantes, mas não a si próprio. As ligações são representadas por arestas bidirecionais, permitindo que a informação flua nos dois sentidos.

Se \(w_{ij}\) representa o peso associado à aresta que une o nó \(i\) ao nó \(j\), então os pesos são simétricos: \(w_{ij} = w_{ji}\) e \(w_{ii} = 0\).

A esta rede associamos o respetivo espaço de estados \(E\)— cada estado corresponde a uma face (padrão ou memória). Ao todo temos 3⁴ = 81 faces. O espaço de estados desta rede tem, portanto, 81 estados possíveis. Recorde-se que estamos a incluir faces corrompidas, a que falta um ou mais atributos (cabelo, nariz, etc.).

Em geral, o espaço de estados E de uma rede de Hopfield com n nós (neurónios), a cada um dos quais está associada uma variável binária \(x_i\), tem \(2^n\) estados. Por exemplo, se \(n=50\), #\(E\)= 1 125 899 906 842 624 estados.

Dinâmica no espaço de estados da Rede de Hopfield.

Para pesos dados, \(w_{ij} = w_{ji}\) e \(w_{ii} = 0\) (veremos à frente como calculá-los), definimos agora um sistema dinâmico no espaço de estados da seguinte forma: suponhamos que, no instante \(t\), o estado da rede é \(s(t) = (x_1(t), x_2(t), x_3(t), x_4(t))\). Então, no instante seguinte \(t+1\), cada nó \(i=1,2,3,4\), atualizará o seu valor de acordo com a seguinte regra:

\(\begin{array}{r} { x _ { i } ( t + 1 ) = \mathrm { sinal } \left( \sum _ { j } w _ { i j } \cdot x _ { j } ( t ) \right) } \end{array}\)

Vejamos um exemplo numérico concreto, supondo que os pesos são os indicados na figura seguinte.

isto é:

\(w_{12}=w_{21}=0,2$; $w_{13}=w_{31}=0,2$; $w_{14}=w_{41}=0,6$; $w_{23}=w_{32}=0,2$; $w_{24}=w_{42}=-0,2\)

Escolhendo o nó \(3\) para atualização, calculamos

\(\begin{array}{rl} & { x _ { 3 } ( 1 ) = \mathrm { sinal } \left( \sum _ { j } w _ { 3 j } \cdot x _ { j } ( t ) \right) } \\& { = \mathrm { sinal } \left( w _ { 31 } \cdot x _ { 1 } ( 0 ) + w _ { 32 } \cdot x _ { 2 } ( 0 ) + w _ { 34 } \cdot x _ { 4 } ( 0 ) \right) } \\& { = \mathrm { sinal } \left( 0 , 2 \cdot ( - 1 ) + 0 , 2 \cdot ( - 1 ) + ( - 0 , 2 ) \cdot ( - 1 ) \right) } \\& { = - 1 } \end{array}\)

Apenas atualizamos o nó \(3\). Os outros mantêm os valores que tinham. O novo estado que se obtém é, portanto, \((-1,-1,-1,-1)\), que corresponde à face \(3\). Assim, podemos dizer que, no espaço de estados, a face \(2\) é transformada na face \(3\). Note-se que a distância de Hamming entre as faces \(2\) e \(3\) é igual a \(1\), pois apenas o valor de \(x_3\) (nariz) mudou.

Dinâmica no espaço de estados da rede de Hopfield. Atualização assíncrona.

Inputs.

Um conjunto \(P\), com \(M\) padrões (memórias).

Cada padrão \(p\in P\) é descrito por \(n\) atributos (variáveis) \(\mathbf { x } ^{p} = \left( x _ { 1 } ^{p} , x _ { 1 } ^{p} , \cdots , x _ { 1 } ^{p} \right)\), que podem assumir os valores \(-1\) ou \(+1\).

Uma rede de Hopfield com \(n\) nós, \(i=1,2,\cdots,n\), construída para armazenar os \(M\) padrões de \(P\) (veremos à frente como).

O atributo \(x_i\) está associado ao nó \(i\).

Nestas condições, o espaço de estados \(E\) da rede de Hopfield tem \(N=3^n\) estados (padrões) possíveis. Em geral, \(N \gg M\). Por exemplo, se tivermos \(n=20\) atributos ternários (incluindo atributos corrompidos), então \(N=\neq E=3^{20}=\)3 486 784 401 estados.

Problema.

Pretende-se definir uma dinâmica, no espaço de estados \(E\), que simule o processo mental de associação; ou seja, quando temos um padrão novo \(p_{\text{novo}}\) (que pode ser um padrão corrompido, por exemplo), a dinâmica induz uma série de iterações que, partindo de \(p_{\text{novo}}\), associa o padrão memorizado \(p^*\in P\) que mais se assemelha a \(p_{\text{novo}}\).

Dinâmica.

A dinâmica é definida pelo processo de atualização assíncrona seguinte: dado um qualquer estado inicial \(\mathbf { x }(0)\) no espaço de estados \(E\):

\(\mathbf { x } \left( 0 \right) = \left( x _ { 1 } \left( 0 \right) , x _ { 2 } \left( 0 \right) , \cdots , x _ { n } \left( 0 \right) \right)\)

1. Escolha um nó \(i\) ao acaso e atualize-o de acordo com a regra

\(x _ { i } \left( 1 \right) = \operatorname { sinal } \left( \sum _ { j } w _ { i j } \cdot x_ { j } \left( 0 \right) \right)\)

Obtemos assim um outro estado \(\mathbf { x } = (x_1 (1), x_2 (1), \cdots, x_n (1)) \in E\). Dizemos então que \(\mathbf { x }_0\) muda para \(\mathbf { x } (1) : \mathbf { x } (0) \rightarrow \mathbf { x } (1)\).

2. Repita um número suficientemente grande de vezes o passo anterior, substituindo \(\mathbf { x } (0)\) por \(\mathbf { x } (1)\), escolhendo um nó ao acaso e atualizando-o pela regra anterior.

3. Repita para outros estados iniciais no espaço de estados.

Como fazemos a aprendizagem da rede?

Isto é, como calculamos os pesos \(w_{ij}\) para que a rede memorize as \(M=\) 10 faces?

As 10 faces ou padrões \(p_{1}, \cdots, p_{10} \in P\) devem ser atratores da dinâmica atrás definida; ou seja, quando atualizamos um qualquer dos seus atributos (nós), ele permanece inalterado:

\(x _ { i } ( 1 ) = \mathrm { sinal } \left( \sum _ { j } w _ { i j } \cdot x _ { j } ( 0 ) \right) = x _ { i } ( 0 ) , \forall i = 1 , 2 , 3 , 4\)

Suponhamos que temos apenas um padrão para memorizar. Uma forma de garantir isso é tomar os pesos na forma:

\(w _ { i j } = \frac { 1 } { n } x _ { i } ( 0 ) \cdot x _ { j } ( 0 )\)

De facto

\(\begin{array}{rl} { x _ { i } ( 1 ) = \operatorname { sinal } \left( \sum _ { j } w _ { i j } \cdot x _ { j } ( 0 ) \right) } & { { } } \\{ = \operatorname { sinal } \left( \sum _ { j } x _ { i } ( 0 ) \cdot x _ { j } ( 0 ) \cdot x _ { j } ( 0 ) \right) } & { { } } \\{ = \operatorname { sinal } \left( \sum _ { j } x _ { i } ( 0 ) \right) } & { { } } \\{ = x _ { i } ( 0 ) } & { { } } \end{array}\)

Já que \(x_{j}(0) \cdot x_{j}(0) = +1\). Além disso, também é óbvio que, mesmo que um número (menos da metade) dos atributos do padrão inicial esteja errado (ou seja, não iguais a \(x_{i}(0)\)), eles serão dominados na soma \(\sum_jw_{ij}\cdot x_j(0)\) pela maioria que está correta, e, portanto, \(x_i(1)=\mathrm{sinal}\left(\sum_jw_{ij}\cdot x_j(0)\right)\) ainda será uma configuração próxima da inicial (na distância de Hamming). Isto significa que a rede corrigirá erros conforme desejado, e podemos dizer que o padrão inicial é um atrator.

Quando temos \(M\) padrões \(p\in P\) para memorizar tomamos

\(w _ { i j } = \frac { 1 } { M } \sum _ { p \in P } x _ { i } ^{p} ( 0 ) \cdot x _ { j } ^{p} ( 0 )\)

Vamos examinar a estabilidade de um padrão \(p\in P\) particular. A condição de estabilidade:

\(x _ { i } ^{q} ( 1 ) = \mathrm { sinal } \left( \sum _ { j } w _ { i j } \cdot x _ { j } ^{q} ( 0 ) \right) = x _ { i } ^{q} ( 0 )\)

Na soma

\(\sum _ { j } w _ { i j } \cdot x _ { j } ^{q} ( 0 ) \ = \frac { 1 } { n } \sum _ { j } \sum _ { p } x _ { i } ^{p} ( 0 ) \cdot x _ { j } ^{p} ( 0 ) \cdot x _ { j } ^{q} ( 0 )\)

separamos a parcela do termo especial \(p = q\), das restantes parcelas:

\(\begin{array}{r} { \sum _ { j } w _ { i j } \cdot x _ { j } ^{q} ( 0 ) = \frac { 1 } { M } \sum _ { j } \sum _ { p } x _ { i } ^{p} ( 0 ) \cdot x _ { j } ^{p} ( 0 ) \cdot x _ { j } ^{q} ( 0 ) } \\{ = x _ { i } ^{q} ( 0 ) \frac { 1 } { M } \sum _ { j } \sum _ { p \neq q } x _ { i } ^{p} ( 0 ) \cdot x _ { j } ^{p} ( 0 ) \cdot x _ { j } ^{q} ( 0 ) } \end{array}\)

Se o segundo termo fosse zero, poderíamos concluir imediatamente que o padrão \(q\) é estável. Isso ainda é verdade se o segundo termo for suficientemente pequeno: se for menor que \(1\), não pode mudar o sinal e a condição de estabilidade continua satisfeita. Acontece que o segundo termo, a que chamamos de termo crosstalk, é menor do que \(1\) em muitos casos de interesse se \(M\) (o número de padrões) for suficientemente pequeno, o que vamos supor que acontece.

Então, os padrões armazenados são todos estáveis — se iniciarmos a dinâmica do sistema num deles, ele permanecerá sempre fixo. Além disso, uma pequena fração de atributos diferente de um padrão armazenado será corrigida da mesma maneira que no caso do padrão; esses atributos serão dominados na soma \(\sum_{j} w_{ij} x_{j}\) pela grande maioria dos atributos corretos. Um padrão que esteja próximo (na distância de Hamming) de um padrão memorizado \(p\) transformar-se-á nesse padrão \(p\). Isto mostra que os padrões memorizados são verdadeiros atratores do sistema, que assim funciona como uma memória associativa.

Função Energia no espaço de estados da Rede de Hopfield.

Dada a rede de Hopfield com pesos obtidos pelo algoritmo de aprendizagem anterior, vamos definir uma função \(E\) no espaço de estados \(E\) que, a cada estado (padrão ou memória), associa um número a que chamamos de energia \(E(x\)) do estado \(x\in E\).

Primeiro, definimos a energia (local) entre dois nós \(i\) e \(j\), ligados por uma aresta (bidirecional) de peso \(w_{ij} = w_{ji}\), através de:

\(e _ { i j } = - w _ { i j } \cdot x _ { i } \cdot x _ { j }\)

Assim, por exemplo, na face \(4=(+1,-1,-1,+1\))

\(e _ { 24 } = - w _ { 24 } \cdot x _ { 2 } \cdot x _ { 4 } = ( 0 , 2 ) \cdot ( - 1 ) \cdot ( + 1 ) = - 0 , 2\)

Para definir \(E(x)\) somamos estas energias para todas as arestas:

\(E ( \mathbf { x } ) = - \sum _ { \mathrm { ~ a r e s t a s ~ } ( i j ) } w _ { i j } \cdot x _ { i } \cdot x _ { j }\)

A propriedade central da função de energia é que ela sempre diminui (ou se mantém constante) à medida que o sistema evolui de acordo com a sua dinâmica. Assim, os atratores (padrões memorizados) correspondem aos mínimos locais da energia.

A dinâmica pode ser pensada como similar ao movimento de uma partícula na superfície da energia sob a influência da gravidade (puxando para baixo). Partindo de um qualquer estado inicial, a partícula desliza para baixo até descansar para sempre num desses mínimos locais — isto é, num dos atratores. As bacias de atração correspondem aos vales ou áreas de captação em torno de cada atrator.

É fácil mostrar que a dinâmica só pode diminuir a energia. De facto, seja \(x_i^{’}\) o novo valor de \(x_i^{’}\) dado por:

\(x _ { i } ^{\prime} = \mathrm { sinal } \left( \sum _ { j } w _ { i j } x _ { j } \right)\)

para algum nó \(i\), escolhido ao acaso para atualização. É claro que, se \(x_i^{’}=x_i\), a energia mantém- se. Suponhamos, então, que \(x_i^{’}=-x_i\). Destacando os termos que envolvem apenas \(x_i\), obtemos:

\(\begin{array}{rl} { E ( \mathbf { x } ^{\prime} ) - E ( \mathbf { x } ) = - \sum _ { j \neq i } w _ { i j } x _ { i } ^{\prime} x _ { j } + \sum _ { j \neq i } w _ { i j } x _ { i } x _ { j } } & { { } } \\{ = 2 x _ { i } \sum _ { j \neq i } w _ { i j } x _ { j } } & { { } } \\{ = 2 x _ { i } x _ { i } ^{\prime} = - 2 x _ { i } ^{2} = - 2 } & { { } } \end{array}\)

Portanto \(E(x') <\) \(E(x)\), neste caso.