Hopfield NetworksReti di Hopfield

A Hopfield network keeps a few binary patterns in the symmetric weights \(W\) of a fully connected network of \(N\) neurons with states \(s_i = \pm 1\), and recalls one of them from a corrupted copy by updating its neurons one at a time, each to the sign of its local field \(h_i = \sum_j w_{ij} s_j\). Every such update leaves the energy \(E(s) = -\tfrac12\, s^\top W s\) unchanged or lower, so that the dynamics is a descent method for a quadratic function on the vertices of the hypercube \(\{-1, 1\}^N\), which stops at a local minimum; the stored patterns are, as long as there are not too many of them, among these minima. Here \(N = 144\), the pixels of a glyph of \(12 \times 12\): a click on a glyph stores it or forgets it, a stroke on the state draws on it, and the figures follow the recall, the energy and the landscape on the plane of the first two principal directions of the stored glyphs.

Una rete di Hopfield conserva alcuni pattern binari nei pesi simmetrici \(W\) di una rete completamente connessa di \(N\) neuroni con stati \(s_i = \pm 1\), e ne richiama uno da una copia corrotta aggiornando i neuroni uno alla volta, ciascuno al segno del suo campo locale \(h_i = \sum_j w_{ij} s_j\). Ogni aggiornamento di questo tipo lascia l'energia \(E(s) = -\tfrac12\, s^\top W s\) invariata o più bassa, così che la dinamica è un metodo di discesa per una funzione quadratica sui vertici dell'ipercubo \(\{-1, 1\}^N\), che si ferma in un minimo locale; i pattern memorizzati sono, finché non sono troppi, fra questi minimi. Qui \(N = 144\), i pixel di un glifo di \(12 \times 12\): un clic su un glifo lo memorizza o lo dimentica, un tratto sullo stato vi disegna sopra, e le figure seguono il richiamo, l'energia e il paesaggio sul piano delle prime due direzioni principali dei glifi memorizzati.

The state of the network, ink for \(+1\) and ground for \(-1\) (grey in between, for the continuous states of the dense network); the gold frame is the neuron just updated, thicker when it flipped. Draw on it to make a cue of your own. Below, the 36 glyphs: the violet ones are stored, a click stores or forgets one, and the cue comes from the one framed in gold.Lo stato della rete, inchiostro per \(+1\) e sfondo per \(-1\) (grigio nel mezzo, per gli stati continui della rete densa); il riquadro d'oro è il neurone appena aggiornato, più spesso quando si è invertito. Disegnaci sopra per costruire un tuo indizio. Sotto, i 36 glifi: quelli viola sono memorizzati, un clic ne memorizza o ne dimentica uno, e l'indizio viene da quello incorniciato in oro.
The energy after every update: it never goes up, and for the classical networks it stays flat when the updated neuron agrees with its field.L'energia dopo ogni aggiornamento: non sale mai, e per le reti classiche resta piatta quando il neurone aggiornato concorda con il suo campo.
For the classical networks, the overlap \(m_\mu = \xi^{\mu\top} s / N\) of the state with every stored glyph (1 when equal, \(-1\) when opposite); for the dense one, the weights of the softmax, i.e., the attention that the state pays to each glyph. Gold is the glyph of the cue.Per le reti classiche, la sovrapposizione \(m_\mu = \xi^{\mu\top} s / N\) dello stato con ogni glifo memorizzato (1 se uguali, \(-1\) se opposti); per quella densa, i pesi della softmax, cioè l'attention che lo stato rivolge a ciascun glifo. In oro il glifo dell'indizio.
The energy on the plane through the mean \(c\) of the stored glyphs spanned by their first two principal directions \(u_1, u_2\). For the classical networks every point \(c + a u_1 + b u_2\) is rounded to the binary state of its signs, so that the surface is made of terraces; for the dense network it is the energy of the continuous state itself. The small balls are the stored glyphs, at their own energy (with more than three glyphs they lie, in general, only near the plane); the gold path is the run, projected on the plane, at the height of its true energy.L'energia sul piano per la media \(c\) dei glifi memorizzati generato dalle loro prime due direzioni principali \(u_1, u_2\). Per le reti classiche ogni punto \(c + a u_1 + b u_2\) è arrotondato allo stato binario dei suoi segni, così che la superficie è fatta di terrazze; per la rete densa è l'energia dello stato continuo stesso. Le piccole sfere sono i glifi memorizzati, alla loro energia (con più di tre glifi stanno, in generale, solo vicino al piano); il cammino d'oro è la corsa, proiettata sul piano, all'altezza della sua vera energia.

CapacityCapacità

With the Hebbian rule the field on neuron \(i\) at a stored pattern \(\xi^\nu\) is \(h_i = \xi^\nu_i + \frac1N \sum_{\mu \ne \nu} \xi^\mu_i\, \xi^{\mu\top} \xi^\nu\) up to a term of order \(p/N\): the pattern itself plus a crosstalk among the patterns, whose standard deviation for random patterns is about \(\sqrt{p/N}\). When the crosstalk becomes comparable to 1, some bits of the patterns flip, the flips spread, and the analysis of Amit, Gutfreund and Sompolinsky (1985) puts the collapse at \(p \approx 0.138\, N\), that is, about 20 patterns for \(N = 144\). The figure below measures the collapse by storing random patterns one at a time and starting the network both from each pattern and from a cue with 10% of its pixels flipped. Glyphs are far from random, since they share most of the ground, and the Hebbian network above merges them into mixtures already with a handful of them (add A to the five stored by default); the projection rule makes any set of linearly independent patterns a fixed point, at the cost of a rule that is no longer local.

Con la regola di Hebb il campo sul neurone \(i\) in un pattern memorizzato \(\xi^\nu\) è \(h_i = \xi^\nu_i + \frac1N \sum_{\mu \ne \nu} \xi^\mu_i\, \xi^{\mu\top} \xi^\nu\) a meno di un termine di ordine \(p/N\): il pattern stesso più un'interferenza fra i pattern, la cui deviazione standard per pattern casuali è circa \(\sqrt{p/N}\). Quando l'interferenza diventa paragonabile a 1 alcuni bit dei pattern si invertono, le inversioni si propagano, e l'analisi di Amit, Gutfreund e Sompolinsky (1985) colloca il collasso a \(p \approx 0.138\, N\), cioè circa 20 pattern per \(N = 144\). La figura qui sotto misura il collasso memorizzando pattern casuali uno alla volta e facendo partire la rete sia da ciascun pattern sia da un indizio con il 10% dei pixel invertiti. I glifi sono tutt'altro che casuali, poiché condividono gran parte dello sfondo, e la rete di Hebb qui sopra li fonde in miscele già con pochi di essi (aggiungi A ai cinque memorizzati all'inizio); la regola di proiezione rende punto fisso ogni insieme di pattern linearmente indipendenti, al prezzo di una regola che non è più locale.

The fraction of the stored patterns recalled (final overlap at least 0.95, on at most 40 of them for each \(p\)), against the number \(p\) of random patterns of \(N = 144\) pixels, for the classical Hebbian network and for the dense network with the \(\beta\) of the bar; the dashed lines mark \(0.138\, N\) and \(N\).La frazione dei pattern memorizzati richiamati (sovrapposizione finale almeno 0.95, su al più 40 di essi per ogni \(p\)), in funzione del numero \(p\) di pattern casuali di \(N = 144\) pixel, per la rete classica di Hebb e per la rete densa con il \(\beta\) della barra; le linee tratteggiate segnano \(0.138\, N\) e \(N\).
\(p\)0

Dense Associative Memories and AttentionMemorie associative dense e attention

The Hebbian energy is, up to a constant, \(-\frac1{2N} \sum_\mu (\xi^{\mu\top} s)^2\), a sum over the patterns of a quadratic function of the overlap. Krotov and Hopfield (2016) replaced the square by a function \(F\) that grows faster, so that near a pattern its own term dominates the crosstalk of the others, and for \(F(x) = x^n\) the number of patterns that can be stored grows as \(N^{n-1}\); Ramsauer et al. (2020) took the exponential, with a log-sum-exp that also admits continuous states \(\xi \in \mathbb{R}^N\), \[E(\xi) = -\beta^{-1} \log \sum_{\mu=1}^p \exp(\beta\, \xi^{\mu\top}\xi) + \tfrac12\, \xi^\top \xi + \beta^{-1} \log p + \tfrac12 M^2,\] with \(M\) the largest norm of a pattern. The concave-convex procedure applied to this energy, which linearizes the concave log-sum-exp at the current state and minimizes the convex rest exactly, gives the update \(\xi^{\text{new}} = X \operatorname{softmax}(\beta X^\top \xi)\), and the energy never goes up along it. This is the attention of the transformer, \(\operatorname{softmax}(\beta\, Q K^\top) V\), with the state as the query, \(Q = \xi^\top\), the stored patterns as both keys and values, \(K = V = X^\top\), and \(\beta = 1/\sqrt{d_k}\). With a large \(\beta\) the softmax is nearly one-hot and a single update retrieves the pattern, also with many more patterns than neurons (the gold curve of the capacity, up to \(p = 2N\)); with a small \(\beta\) the weights spread over the patterns that look alike and the update stops at a metastable state, their average, drawn in grey on the state (store all 36 glyphs, choose the dense network and lower \(\beta\) below 0.05).

L'energia di Hebb è, a meno di una costante, \(-\frac1{2N} \sum_\mu (\xi^{\mu\top} s)^2\), una somma sui pattern di una funzione quadratica della sovrapposizione. Krotov e Hopfield (2016) hanno sostituito il quadrato con una funzione \(F\) che cresce più in fretta, così che vicino a un pattern il suo termine domina l'interferenza degli altri, e per \(F(x) = x^n\) il numero di pattern memorizzabili cresce come \(N^{n-1}\); Ramsauer et al. (2020) hanno preso l'esponenziale, con una log-sum-exp che ammette anche stati continui \(\xi \in \mathbb{R}^N\), \[E(\xi) = -\beta^{-1} \log \sum_{\mu=1}^p \exp(\beta\, \xi^{\mu\top}\xi) + \tfrac12\, \xi^\top \xi + \beta^{-1} \log p + \tfrac12 M^2,\] con \(M\) la norma più grande di un pattern. La procedura concava-convessa applicata a questa energia, che linearizza la log-sum-exp concava nello stato corrente e minimizza esattamente il resto convesso, dà l'aggiornamento \(\xi^{\text{new}} = X \operatorname{softmax}(\beta X^\top \xi)\), lungo il quale l'energia non sale mai. È l'attention del transformer, \(\operatorname{softmax}(\beta\, Q K^\top) V\), con lo stato come query, \(Q = \xi^\top\), i pattern memorizzati come chiavi e come valori, \(K = V = X^\top\), e \(\beta = 1/\sqrt{d_k}\). Con un \(\beta\) grande la softmax è quasi un vettore indicatore e un solo aggiornamento richiama il pattern, anche con molti più pattern che neuroni (la curva d'oro della capacità, fino a \(p = 2N\)); con un \(\beta\) piccolo i pesi si distribuiscono sui pattern che si somigliano e l'aggiornamento si ferma in uno stato metastabile, la loro media, disegnata in grigio sullo stato (memorizza tutti i 36 glifi, scegli la rete densa e abbassa \(\beta\) sotto 0.05).