Hopfield Networks is All You Need
Authors: Hubert Ramsauer
Bernhard Schäfl
Johannes Lehner
Philipp Seidl
Michael Widrich
Lukas Gruber
Markus Holzleitner
Thomas Adler
David Kreil
Michael K Kopp
Günter Klambauer
Johannes Brandstetter
Sepp Hochreiter
Venue: ICLR 2021 Poster (2021)
Keywords: Modern Hopfield Network
Energy
Attention
Convergence
Storage Capacity
Hopfield layer
Associative Memory

Abstract: We introduce a modern Hopfield network with continuous states and a corresponding update rule. The new Hopfield network can store exponentially (with the dimension of the associative space) many patterns, retrieves the pattern with one update, and has exponentially small retrieval errors. It has three types of energy minima (fixed points of the update): (1) global fixed point averaging over all patterns, (2) metastable states averaging over a subset of patterns, and (3) fixed points which store a single pattern. The new update rule is equivalent to the attention mechanism used in transformers. This equivalence enables a characterization of the heads of transformer models. These heads perform in the first layers preferably global averaging and in higher layers partial averaging via metastable states. The new modern Hopfield network can be integrated  into deep learning architectures as layers to allow the storage of and access to raw input data, intermediate results, or learned prototypes.
These Hopfield layers enable new ways of deep learning, beyond fully-connected, convolutional, or recurrent networks, and provide pooling, memory, association, and attention mechanisms. We demonstrate the broad applicability of the Hopfield layers
across various domains. Hopfield layers improved state-of-the-art on three out of four considered multiple instance learning problems as well as on immune repertoire classification with several hundreds of thousands of instances. On the UCI benchmark collections of small classification tasks, where deep learning methods typically struggle, Hopfield layers yielded a new state-of-the-art when compared to different machine learning methods. Finally, Hopfield layers achieved state-of-the-art on two drug design datasets. The implementation is available at: \url{https://github.com/ml-jku/hopfield-layers}

HOPFIELD NETWORKS IS ALL YOU NEED
Hubert Ramsauer"
Bernhard Schäff"
Johannes Lehner*
Philipp Seidl"
Michael Widrich
Thomas Adler'
Lukas Gruber"
Markus Holzleitner"
David Kreil Michael Kopp' Günter Klambauer" Johannes Brandstetter*
Sepp Hochreiter*-1
"ELLIS Unit Linz, LIT AI Lab, Institute for Machine Learning. Johannes Kepler University Linz, Austria
i Institute of Advanced Research in Artificial Intelligence (IARAI)
Email: ( [ramsauer,schacl (ranssucrsssaall..rdddsttttrrrr brandstetter.hochreii @ ml.jku.at
ABSTRACT
We introduce modern Hopfield network with continuous states and correspond- ing update rule. The new Hopfield network can store exponentially (with the dimension of the associative space) many patterns, retrieves the pattern with update, and has exponentially small retrieval errors. It has three types of energy minima (fixed points of the update): (1) global fixed point averaging
all pat- terns, (2) metastable states averaging over a subset of patterns, and (3) fixed points which store a single pattern. The new update rule is equivalent to the attention mechanism used in transformers. This equivalence enables a characterization of the heads of transformer models. These heads perform in the first layers preferably global averaging and in higher layers partial averaging via metastable states. The new modern Hopfield network can integrated into deep learning architectures as layers to allow the storage of and access to raw input data, intermediate results, or learned prototypes. These Hopfield layers enable new ways of deep learning, beyond fullycconnected, convolutional, recurrent networks, and provide pooling, memory, association, and attention mechanisms. We demonstrate the broad appli- cability of the Hopfield layers across various domains. Hopfield layers improved state-of-the-ard on three out of four considered multiple instance learning problems well on immune repertoire classification with several hundreds of thousands of instances. On the UCI benchmark collections of small classification tasks, where deep learning methods typically struggle, Hopfield layers yielded a new state-of- the-art when compared to different machine learning methods. Finally, Hopfield layers achieved state-of-the-an on two drug design datasets. The implementation is available at: https: / / / thub. com/ m1- jikukjkuohoooo ff ield- layers
INTRODUCTION
The deep learning community has been looking for alternatives to recurrent neural networks (RNNs) for storing information. For example, linear memory networks use linear autoencoder for sequences as a memory (Carta et al., 2020). Additional memories for RNNs like holographic reduced represen- tations (Danihelka al., 2016). tensor product representations (Schlag Schmidhuber, 2018; Schlag et al,, 2019) and classical associative memories (extended to fast weight approaches) (Schmidhuber, 1992; Ba al., 201 6a;b; Zhang & Zhou, 2017; Schlag et al., 2021) have been suggested. Most approaches to new memories are based on attention. The neural Turing machine (NTM) is equipped with an external memory and an attention process (Graves et al., 2014). Memory networks (Weston et al., 2014) use an arg max attention by first mapping query and patterns into space and then retrieving the pattern with the largest dot product. End to end memory networks (EMN) make this attention scheme differentiable by replacing arg max through softmax (Sukhbaatar et al., 2015a;b). EMN with dot products became very popular and implement a key-value attention (Daniluk et al., 2017) for self-attention. An enhancement of EMN is the transformer (Vaswani al., 201200177 7agb) and its

---

extensions (Dehghani al., 2018). The transformer has had great impact the natural language processing (NLP) community, in particular via the BERT models (Devlin et al., 2018; 2019).
Contribution of this work: (i) introducing novel deep learning layers that are equipped with memory via modern Hopfield networks, (ii) introducing a novel energy function and novel update rule for continuous modern Hopfield networks that are differentiable and typically retrieve patterns after one update. Differentiability is required for gradient descent parameter updates and retrieval with one update is compatible with activating the layers of deep networks.
We suggest using modern Hopfield networks to store information or learned prototypes in different layers of neural networks. Binary Hopfield networks were introduced associative memories that can store and retrieve patterns (Hopfield, 1982). A query pattern can retrieve the pattern to which it most similar or an average over similar patterns. Hopfield networks seem be an ancient technique, however, new energy functions improved their properties. The stability of spurious states or metastable states was sensibly reduced (Barra et al., 2018). The largest and most impactful successes are reported increasing the storage capacity of Hopfield networks. In d-dimensional space, the standard Hopfield model can store d uncorrelated patterns without errors but only Cd/ log(d) random patterns with C < 1/2 for fixed stable pattern or C < 1/4 if all patterns are stable (McEliece et al., 1987). The same bound holds for nonlinear learning rules (Mazza, 1997). Using tricks-of of-trade and allowing small retrieval emrrr, the storage capacity is about 0. 1.13 (Crisanti et al., 1986; Hertz et al., 1991; Torres et al., 2002). If the learning rule is not related to the Hebb rule, then up to d patterns can be stored (Abu-Mostafa & StJacques, 1985). For Hopfield networks with non-zero diagonal matrices, the storage can be increased to Cd log(d) d) (Folli et al., 2017). In contrast to the storage capacity, the number of energy minima (spurious states, stable states) of Hopfield networks is exponential in d (Tanaka & Edwards, 1980; Bruck & Roychowdhury, 1990; Wainrib & Touboul, 2013).
The standard binary Hopfield network has an energy function that can be expressed as the sum of interaction functions F with F(x)= = z². Modern Hopfield networks, also called "dense associative memory" (DAM) models, use an energy function with interaction functions of the form F(x) = x and, thereby, achieve a storage capacity proportional to d (Krotov & Hopfield, 2016; 2018). The energy function of modern Hopfield networks makes them robust against adversarial attacks (Krotov & Hopfield, 2018). Modern binary Hopfield networks with energy functions based on interaction functions of the form F(x) exp(x) even lead to storage capacity of 2d/2, where all stored binary patterns are fixed points but the radius of attraction vanishes (Demircigil al., 2017). However, in order to integrate Hopfield networks into deep learning architectures, it is necessary to make them differentiable, that is, we require continuous Hopfield networks (Hopfield, 1984; Koiran, 1994).
Therefore, we generalize the energy function of Demircigil et al. (2017) that builds on exponential interaction functions to continuous patterns and states and obtain a new modern Hopfield network. We also propose a new update rule which ensures global convergence to stationary points of the energy (local minima or saddle points). We prove that our new modern Hopfield network typically retrieves patterns in one update step (e-close to the fixed point) with exponentially low error and has a storage capacity proportional to e - (reasonable settings for c = 1.37 and e 3.15 are given in Theorem 3). The retrieval of patterns with one update is important to integrate Hopfield networks in deep learning architectures, where layers are activated only once. Surprisingly, our new update rule is also the key-value attention used in transformer and BERT models (see Fig. 1). Our modern Hopfield networks can be integrated as a new layer in deep learning architectures for pooling, memory, prototype learning, and attention. We test these new layers different benchmark datasets and tasks like immune repertoire classification.
Hopfield Energy
New Emergy
Updatee Rule
Transformer
- eepp (Ise (1)
ls 1
softmax x²
softmax (/2 QK v
We generalize the energy of binary modern Hopfield networks to continuous states while keeping fast convergence and storage capacity properties. We also propose update rule that minimizes the energy. The new update rule is the attention mechanism of the transformer. Formulae modified to express softmax row vector. "="-sign means "keeps the properties".
Figure 1:
2

---

2 MODERN HOPFIELD NETS WITH CONTINUOUS STATES
New energy function for continuous state Hopfield networks. In order to integrate modern Hopfield networks into deep learning architectures, we have to make them continuous. To allow for continuous states, we propose a new energy function that is a modification of the energy of modern Hopfield networks (Demircigil al., 2017). We also propose new update rule which can be proven to converge to stationary points of the energy (local minima or saddle points).
We have N stored (key) patterns 2;; Rd represented by the matrix X ( xxx with the largest pattern M = max; ||,]]] The state (query) pattern is & E IRd, For exponential interaction functions, we need the log-sum-exp function (Ise) for 0 < B
N
(3) = -3-1log
Σ
exp((tr:)
(1)
which is convex (see appendix Eq. (461), and Lemma A22). The energy function F. of the modern
Hopfield networks for binary patterns 2; and binary state pattern & is E -En=1 F (g" a,)
(Krotov & Hopfield, 2016). Here, F(x) = x² is the interaction function, where = 2 gives the classical Hopfield network. The storage capacity proportional to d= (Krotov & Hopfield, 2016). This model was generalized by Demircigil et al. (2017) to exponential interaction functions F(z) exp(x) which gives the energy E =
(I, This energy leads to an exponential storage capacity of N = 24/2 for binary patterns. Furthermore, with a single update, the fixed point is recovered with high probability for random patterns. However, still this modern Hopfield network has binary states.
We generalize this energy function to continuous-value patterns while keeping the properties of the modern Hopfield networks like the exponential storage capacity and the extremely fast convergence (see Fig. 1). For the new energy we take the logarithm of the negative energy of modern Hopfield networks and add a quadratic term of the current state. The quadratic term ensures that the norm of the state vector remains finite and the energy is bounded. Classical Hopfield networks do not require to bound the norm of their state vector, since it is binary and has fixed length. We define the novel energy function as
1 - + 8 -og
1
E
1se(8, (ee(8)x))) x
log N + M
(2)
2
2
We have 0 & E & 2M2 (see appendix Lemma A1). Using p softmax (3 E), we define a novel update rule (see Fig. 1):
gnew
f(E) = Xp = x))
The next theorem states that the update rule Eq. (3) converges globally. The proof uses the Concave- Convex Procedure (CCCP) (Yuille & Rangarajan, 2002; 2003), which is equivalent to Legendre minimization (Rangarajan et al., 1996; 1999) algorithms (Yuille & Rangarajan, 2003).
Theorem 1. The update rule Eq. (3) converges globally: For g = f(E"), the energy E(g') - E(E*) fort and fixed point e"
Proof. The update rule in Eq. (3) is the CCCP for minimizing the energy E, which is the sum of the convex "/ and concave lIse (see details in appendix Theorem 1). Theorem in Yuille & Rangarajan (2002) yields the global convergence property. Also, in Theorem 2 in Sriperumbudur & Lanckriet (2009) the global convergence of CCCP is proven via a rigorous analysis using Zangwill's global convergence theory of iterative algorithms.
The global convergence theorem only assures that for the energy E(g') + E(E*) for t - oo but not e' E" The next theorem strengthens Zangwill's global convergence theorem (Meyer, 1976) and gives convergence results similar to those known for expectation maximization (Wu, 1983).
Theorem 2. For the iteration Eq. (3) have (g()) (E()) F. as f - co, for some and either { T converges or, in the other case, the set of limit points of ( J is connected and compact subset of L (E*), where L (a) = {E E C (E) = a) and C is the set of stationary points of the iteration Eq. (3). If C (E*) is finite, then any sequence {g' = generated by the iteration Eq. (3) converges some e E L (F*).
stationary point g" Furthermore, ||g++1 - 5'|l
3

---

For proof, see appendix Theorem 2. Therefore, all the limit points of any sequence generated by the iteration Eq. (3) are stationary points (local minima or saddle points) of the energy function E. Either the iteration converges or, otherwise, the set of limit points is connected and compact set.
The next theorem gives the results on the storage capacity of our new continuous state modern Hopfield network. We first define what we mean by storing and retrieving patterns using a modern Hopfield network with continuous states.
Definition (Pattern Stored and Retrieved). We assume that around every pattern æ; a sphere S₁ is given. We say T, is stored if there is a single fixed point xi E S; to which all points & E St converge, and S O S = 0 for + j. say æ, is retrieved for a given c if iteration (update rule) Eq. (3) gives point ã; that is at least c-close to the single fixed point z E S,. The retrieval error is [ zzll.
As with classical Hopfield networks, we consider patterns on the sphere, i.e. patterns with a fixed norm. For randomly chosen patterns, the number of patterns that can be stored is exponential in the dimension the space of the patterns (æ;; E IRd).
Theorem 3. We assume failure probability 0 < p & and randomly chosen patterns the sphere with radius M == -vddddl We define a == 21 (n(23K"p(d-1))) (1))))b:--)) b b: 2K*a and b Wo(csp(a+In(6))) where Wo is the upper branch of the Lambert W function (Olver et al., 2010,
5
a²1
(4.13)), and ensure c 2 can be stored
2 vD
Then with probability 1 - p, the number of random patterns that
N 2 vpc +
(4)
Therefore it is proven for 2 3.1554 with 8 = 1, K 3, d = 20 and p = 0.001 +a+ + (Inb) > 1.27)
and proven for e 2 1.3718 with 3 K 1, d 75, and p 0.001 (a + In(b) < -0.94).
For proof, see appendix Theorem A5.
The next theorem states that the update rule typically retrieves patterns after one update. Retrieval of a pattern æt; for fixed point æ. and query & is defined via an by (E) = < c, that is, the update is c-close to the fixed point. Retrieval with one update is crucial to integrate modern Hopfield networks into deep learning architectures, where layers are activated only once. First we need the concept of separation of a pattern. For pattern æ; we define its separation A, to other patterns by:
A min (x. x;
x,xx,) x
max xz
(5)
jifi
Jjj
The update rule retrieves patterns with one update for well separated patterns, that is, patterns with large A,
Theorem 4. With query &, after one update the distance of the new point f(E) the fixed point at and its 0g
is exponentially small in the separation A.. The precise bounds using the Jacobian J 05(E) value J in the mean value theorem are:
(E)
a;ll. | ll2 2 (N expl- 3 (A: max{ll æell, xx11} M))
aill ll < || ll
(6)
For given and sufficient large Ai we have (IS(E) xiil < that is, retrieval with one update.
See proof in appendix Theorem A8.
At the same time, the retrieval enror decreases exponentially with the separation A,
Theorem (Exponentially Small Retrieval Error). The retrieval error (I)(E) - xxil of pattern x; is bounded by
lIf(E) xx1l < 2 (N 1) exp(- B (A: 2 max maxill -xill ||=| xill M)) M (8)
and for ||,z, xf1 < 2 together with ||,| Ell < MØM M by
ax xill & 2 (N - 1) M exp(- 3 A.)
(9)
See proof in appendix Theorem A9.
4

---

Metastable states and one global fixed point. So far, considered patterns 2; that are well separated and the iteration converges to a fixed point which near a pattern 2;- If no pattern 2; is well separated from the others, then the iteration converges to a global fixed point close to the arithmetic mean of the vectors. this case the softmax vector p is close to uniform, that is, similar each other and well separated from all other vectors, then
ps 1/N. If some vectors metastable state near the similar vectors exists. Iterations that start near the metastable state converge this metastable state, also if initialized by one of the similar patterns. For convergence proofs to one global fixed point and to metastable states see appendix Lemma A7 and Lemma A12, respectively.
Hopfield update rule is attention of the transformer. The Hopfield network update rule is the attention mechanism used in transformer and BERT models (see Fig. 1). To see this, we assume N stored (key) patterns y: and S state (query) patterns r, that are mapped the Hopfield space of dimension dg. We set a;; Wky. & W Q ri and multiply the result of our update rule with Wy.
The matrices Y (y) ..... yN) and R (r 1r..... ..... rs)² combine the y; and r. as row vectors. We define the matrices X = K YWK, E" = Q = RWQ, and V ===Y =YW Wv = XxWW.. where WK E Idd xdy, Wq E R4,xd, Wv E Id xd. If 3 L/Vdk and softmax E R is changed a row vector, we obtain for the update rule Eq. (3) multiplied by Wy:
Z softmax (1/Vor (VVaQKK)) v =sofmmax (B R WQ WKY") Y WKWVV. (10)
The left part of Eq. (10) is the transformer attention. In the transformer self-attention R= Y, and W Wv replaced by just Wv. Besides the attention mechanism, Hopfield networks allow for other functionalities in deep network architectures, which we introduce via specific layers in the next section. The right part of Eq. (10) serves explain these specific layers.
3 NEW HOPFIELD LAYERS FOR DEEP LEARNING
Modern Hopfield networks with continuous states can be integrated into deep learning architectures, because they are continuous and differentiable with respect to their parameters. Furthermore, they typically retrieve patterns with one update, which is conform to deep learning layers that are activated only once. For these two reasons, modern Hopfield networks can serve as specialized layers in deep networks to equip them with memories. Below, we introduce three types of Hopfield layers: Hopf fnffies i 1 d, Hopf f i e dPool ng, and Hopf dlaa..r. Possible applications of Hopfield layers in deep network architectures comprise:
multiple instance learning (MIL) (Dietterich et al., 1997),
processing of and learning with point sets et et.,, 2017a;b; Xu al., 2018),
set-based and permutation invariant learning (Guttenberg et al., 2016; Ravanbakhsh et al., 2016; Zaheer et al., 2017; Korshunova et al., 2018; Ilse et al., 2018; Zhai et al., 2020),
attention-basee learning (Vaswani et al., 2017a),
deep learning with associative memories (Graves et al., 2014; Weston et al., 2014; Ba et al., 201 2016;;b; Schlag & Schmidhuber, 2018; Schlag al., 2019),
natural language processing (Devlin et al., 2018; 2019),
sequence analysis and time series prediction (Hochreiter, 1991; Hochreiter & Schmidhuber, 1997; Cho et al., 2014), and
storing and retrieving reference data, e.g. the training data, outliers, high error data points, prototypes or cluster centers, support vectors & border cases.
Hopfield network layers can substitute existing layers like pooling layers, permutation equivariant layers (Guttenberg et al., 2016; Ravanbakhsh et al., 2016), GRU (Cho et al., 2014) & LSTM (Hochreiter, 1991; Hochreiter & Schmidhuber, 1997) layers, and attention layers (Vaswani et al., 2017a;b; Bahdanau et al., 2014).
5

---

Types of neural networks. We consider two types of feed- forward neural networks: (I) Neural networks that propagate an activation vector from the imput layer to the output layer. Exam- ples are fully-connected or convolutional neural networks. (II) Neural networks that propagate set of vectors from the input layer to the output layer, where each layer applies the same operation to each element of the and the output layer may summarize the set via a vector. An example is the transformer. Recurrent neural networks are networks of type (I), which are iteratively applied to set or sequence, where intermediate results are stored in a memory and can be reused. Modern Hopfield networks can be integrated into both types of neural network architectures and enable to equip each of their layers with associative memories. See Fig. 2.
Figure 2: Left: A standard deep network with layers propagates either a vector or set of vectors from the input to the output. Right: A deep network, where layers results a plethora of new deep learning architectures, since we can (a) propagate sets or single vectors, (b) propagate queries, stored patterns, or both, (c) learn static queries or stored patterns, (d) fill the memory by training sets, prototypes, external data. Next, provide three useful types of Hopfield layers. The implementation available at: https: attps::/giihiie /github.ttt/tt cwwc m11 wttp///iiooooeeeeooeeeooo layers
Types of new Hopfield layers. We introduce three types of Hopfield layers: Hopfield, HopfieldPoola ling and Hopf ie dLayer. The continuous modern Hopfield network
are equipped with associative mem- ories via Hopfield layers
(1) Layer Hopfield for networks that propagate sets of vectors via state (query) patterns R and stored (key) patterns Y. The layer Hopfield the realization of formula (10). The memory of the Hopfield layer can be filled with sets from the input previous layers, see Fig. 3. The memory may be filled with a reference set, which is covered by providing the reference set as additional input. Thus, the layer Hopf e e allows the association of two sets. A prominent example of a layer that performs such association is the transformer attention mechanism, which associates keys and queries, e.g. two point sets that have be compared. This layer allows for different kinds of loquence-to-sqqueet Hopfield with skip connections in ResNet architecture is identical the popular transformer and BERT models. In the experiments, we analyzed these Hopfield layers in transformer architectures. In our experiments which we compare machine learning methods on small datasets of the UCI benchmark collection the layer Hopf f i l is also used.
methods. The layer learning, point set operations, and retrieval-basee
Z = softmax (B
R We
W
YT)
Y
Wv
Z
+
Y
= softmax
R
Figure 3: The layer Hopfield allows the association of two sets R and Y It can be integrated into deep networks that propagate sets of vectors. The Hopfield memory is filled with a set from either the input or previous layers. The output is set of vectors Z
(2) Layer Hopf ie dPool ing for networks that propagate patterns via the stored (key) patterns Y. This layer performs pooling or summarization of sets Y obtained from queries in previous layers or the input. The memory of the HopfieldPoot PeldPoooiiingggg layer is filled with sets from the input or previous layers. The Hopfie eeooooollllloo ing layer uses the queries to search for patterns in the memory, the stored set. If more patterns are similar to particular search pattern (query), then the result an average over these patterns. The state (query) patterns each layer are static and can be learned. Multiple queries supply a set to the next layer, where each query corresponds to one element of the set. Thus, the layer Hopfiel eeffeeld 1P colinc ing enables fixed pattern search, pooling operations, and memories like LSTMs GRUs. The static pattern functionality is typically needed if particular patterns must be identified the data.
A single Hopfie eooo ing layer allows for multiple instance learning. Static state (query)

---

patterns together with position encoding in the keys allows for performing pooling operations. The position encoding can two-dimensional, where standard convolutional filters can be constructed as in convolutional neural networks (CNNs).. The HapfieldPooli onnii layer substitute pooling, averaging, LSTTM, and permutation equivariant layers. See Fig. 4. The layer Hopfie i dPool ing used for experiments with multiple instance learning tasks, e.g. for immune repertoire classification in the experiments.
Z +
Z softmax (8
Q W YT)
Y
Wv
softmax
The layer Hopfie wwwddoooliii ling enables pooling or summarization of sets, which are obtained from the imput or frrm previous layers. The input Y (m) can be either set or sequence. The query patterns of each layer are static and can be learned. The output is set of vectors Z (.), where the number of vectors equals the number of query patterns. The layer HopfieldPool can realize multiple instance learning.
Figure 4:
(3) Layer Hopfie leppfielcee elddayer for networks that propagate a vector or a set of vectors via state (query) patterns R. The queries R can be input vectors queries that are computed from the output of previous layers. The memory of the Hopf ie dLayer layer is filled with a fixed set, which be the training set, reference set, prototype set, learned set learned matrix). The stored (key) patterns are static and can be learned. If the training set is stored in the memory, then each layer constructs new set of queries based on the query results of previous layers. The stored patterns can be initialized by the training set or a reference set and then learned, in which case they deviate from the training set. The stored patterns can be interpreted as weights from the state (query) to hidden neurons that have a softmax activation function (Krotov & Hopfield, 2020). The layer Hopf iell dLayer can substitute a fully connected layer, see Fig. 5. single HopfieldLayer layer also allows for approaches similar to support vector machines (SVMs), approaches similar to k-nearest neighbor, approaches similar to learning vector quantization, and pattern search. For classification, the data y; (z,, tx) can be the concatenation of input and target t, In this case, the matrices WK and Wv can be designed such that inside the softmax the input 2, is used and outside the softmax the target f. Thus, the softmax provides weighted average of the target vectors based on the similarity between the query and the inputs. Also SVM models, k-nearest neighbor, and learning vector quantization can be considered as weighted averages of the targets. The encoder-decoder attention layer of the transformers are a Hopf ie dLayer layer, where the memory is filled with the encoder output set. In our experiments with the drug design benchmark datasets, the layer methods.
1dLayer has been applied and compared to other machine learning
Z softmax (B
R
Wh
)
Wv
softmax
R
Figure 5: The layer Hopfi dLayer enables multiple queries of the training set, reference set, prototype set, or a learned set (a learned matrix). The queries for each layer are computed from the results of previous layers. The input is set of vectors R ()). The output is also set of vectors Z ()), where the number of output vectors equals the number of input vectors. The layer Hopfieldlayer can realize SVM models, k k-nearest neighbor, and LVQ.
Additional functionality of new Hopfield layers. The insights about energy, convergence, and storage properties provide all new Hopfield layers with additional functionalities: multiple updates
7

---

to control how precise fixed points found without additional parameters needed. ii) variable to determine the kind of fixed points such as the size of metastable states. The variable B controls over how many patterns is averaged. As observed in the experiments, the variable is relevant in combination with the learning rate to steer the learning dynamics. The parameter | governs the fixed point dynamics and can be learned, too. iii) controlling the storage capacity via the dimension of the associative space. The storage capacity can be relevant for tasks with a huge number of instances as in the immune repertoire classification experiment. iv) pattern normalization controls, like the layernomm the fixed point dynamics by the norm and shift of the patterns. For more details see appendix, Section A.6.
4 EXPERIMENTS
We show that our proposed Hopfield layers can be applied successfully to wide range of tasks. The tasks are from natural language processing, contain multiple instance learning problems, a collection of small classification tasks, and drug design problems.
Analysis of transformer and BERT models. Transformer and BERT models can be implemented by the layer Hopfield. The kind of fixed point of the Hopfield net is determined by how the pattern x; is separated from others patters.. (a) a global fixed point: no separation of a pattern from the others, (b) fixed point close to single pattern: pattern is separated from other patterns, (c) metastable state: some patterns are similar to each other and well separated from all other vectors. We observed that the attention heads of transformer and BERT models are predominantly in metastable states, which are categorized into four classes: (I) averaging over a very large number of patterns (very large metastable state or fixed point (a)). (II) averaging over a large number of patterns (large metastable state), (III) averaging over a medium number of patterns (medium metastable state), (IV) averaging over small number of patterns (small metastable state or fixed point (c)). For analyzing the metastable states, we calculated the minimal number lt of softmax values required to sum up to 0.90. Hence, indicates the size of a metastable state. To determine in which of the four classes a head is mainly operating, we computed the distribution of l across sequences. Concretely, for N tokens and for k as the median of the distribution, a head is classified as operating in class (I) if 1/2N < k, operating in class (II) if 1/8N < k & 1 1/2N, as operating in class (III) if 1/32N < k & 1/8N, and as operating in class (IV) if i & 1 /32N.. We analyzed pre-trained BERT models from Hugging Face Inc. (Wolf et al., 2019) according distribution of the pre-trained bert-base-cased model is depicted (for other models see appendix Section 1.5.1.4). Operating classes (II) (large metastable states) and (IV) (small metastable states) are often observed in the middle layers. Operating class (I) (averaging over a very large number of patterns) abundant in lower layers. Similar observations have been reported in other studies (Toneva & Wehbe, 2019;;;; Tay et al., 2020). Operating class (III) (medium metastable states) is predominant in the last layers.
these operating classes. In Fig. A.3 in the appendix the
Multiple Instance Learning Datasets. For multiple instance learning (MIL) (Dietterich et al., 1997), we integrate new Hopfield network via the layer Hopf el 1 ng into deep learning architectures. Recently, deep learning methods have been applied to MIL problems (Ilse et al., 2018), but still the performance on many datasets lacks improvement. Thus, MIL datasets still pose an interesting challenge, in which Hopfield layers equipped with memory are promising approach.
Immune Repertoire Classification. The first MIL task is immune repertoire classification, where deep learning architecture with Hopfie e 1eldd oo 1 ing (DeepRC) was used (Widrich et al., 2020a;b). Immune repertoire classification (Emerson et al., 2017) typically requires to extract few patterns from large set of sequences, the repertoire, that are indicative for the respective immune status. The datasets contain 300,000 instances per immune repertoire, which represents one of the largest multiple instance learning experiments ever conducted (Carbonneau et al., 2018 8). Most MIL. methods fail due the large number of instances. This experiment comprises real-world and simulated datasets. Simulated datasets are generated by implanting sequence motifs (Akbar et al., 2019; Weber et al., 2020) with low frequency into simulated or aaperimentalll-obeeeeee observed immune receptor sequences. The performance of DeepRC was compared with other machine learning methods: (i) known motif, (ii) SVM using k-mers and MinMax or Jaccard kernel, (iii) K-Nearest Neighbor (KNN) with k- mers, (iv) logistic regression with k-mers, (v) burden test with k-mers, and (vi) logistic multiple
8

---

Method
tiger
fox
clephant
UCSB
Hopfield (ours)
91.3 1 0.5
64.05 + 0.4
94.9 0.3
89.5 + 0.8
Path encoding (Küiçükaşe & Baydogan, 2018)
91.0 1 1.0
71.2 1.4*
94.1 0.7
88.0 1: 2.2
MInD (Cheplygina et al., 2016)
85.3 1.1
7.64
93.6 0.9
8.71
MILES (Chen ct al., 2006)
1.7
73.8
1..
92.7 0.7
83.3 2.6"
APR (Dietterich et al., 1997)
77.8 0.79
54.1 - 0.9
55.0 1.0
Eitatiin-kNN (Wang, 2000)
85.5 0.9
63.5 1.5
89.6 0.9
70.6 - 3.2
DD (Maron & Lozano-Pérez, 1998)
84.1
63.1
90.7
Table 1: Results for MIL datasets Tiger, Fox. Elephant, and UCSB Breast Cancer in terms of AUC. Results for all methods except the first are taken from either "(Kiçtikaaeı & Baydogan, 2018) or "CCarbonncau ct al., 2016), depending on which reports the higher AUC.
instance learning (IMIL). On the real-world dataset DeepRC achieved AUC of 0.832 = 0.022, followed by the SVM with MinMax kernel (AUC 0.825 = 0.022) and the burden test with an AUC of 0.699 + 0.041. Across datasets, DeepRC outperformed all competing methods with respect to average AUC (Widrich et al., 2020a;b).
MIL benchmark datasets. We apply Hopfield layers further MIL datasets (IIse et al., 2018; Küçükaşeı & Baydogan, 2018; Cheplygina et al., 2016): Elephant, Fox and Tiger for image annotation (Andrews et al., 2003). These datasets consist of color images from the Corel dataset that have been preprocessed and segmented. An image consists of a set of segments (or blobs), each characterized by color, texture and shape descriptors. The datasets have 100 positive and 100 negative example images. The latter have been randomly drawn from a pool of photos of other animals. Elephant comprises 1,391 instances and 230 features, Fox 1,320 instances and 230 features, and Tiger has 1,220 instances and 230 features. Furthermore, we use the UCSB breast cancer classification (Kandemir et al., 2014) dataset, which consists of 2,002 instances across 58 input objects. An instance represents patch of histopathological image of cancerous or normal tissue. The layer Hopfiel ool ing is used, which allows for computing a per-input-object representation by extracting an average of instances that are indicative for one of the two classes. The input to the layer Hopf i IdPoollnn ing is set of embedded instances Y. A trainable but fixed state (query) pattern Q is used for averaging over class-indicativy instances. This averaging enables a compression of variable-sized bags to fixed- sized representation to discriminate the bags. More details in appendix Sec. A.5.2. Our approach has set a new state-of-the- the and has outperformed other methods (Küçūkaşçı & Baydogan, 2018; Carbonneau et al., 2016) on the datasets Tiger, Elephant and UCSB Breast Cancer (see Table 1).
UCI Benchmark Collection. So far deep learning struggled with small datasets. However, Hop- field networks are promising for handling small datasets, since they can store the training data points or their representations to perform similarity-based nearest neighbor, or learning vector quantization methods. Therefore, we test the Hopfield layer Hopfiele on the small datasets of the UC Irvine (UCI) Machine Learning Repository that have been used to benchmark super- vised learning methods (Fermández-Delaado et al., 2014; Wainberg et al., 2016; Khan et al., 2018) and also feed-forward neural networks (Klambauer et al., 2017a; Wu et al., 2018), where our Hopfield networks could exploit their memory. The whole 121 datasets in the collection vary strongly with respect their size, number of features, and difficulties (Fernández-Dellee 2014), such that they have been divided into 75 "small datasets" with less than 1,000 samples and 45 "large datasets" with more than or equal to 1,000 samples in Klambauer et al. (2017a). On the 75 small datasets, Random Forests (RFs) and Support Vector Machines (SVM) are highly accurate, whereas on the large datasets, deep learning methods and neural networks are in the lead (Klambauer et al., 2017a;b; Wu et al., 2018). We applied a modern Hopfield network via the layer Hopfiell liieeddaas dlayeer where self- normalizing net (SNN) maps the input vector to Y and R. The output Z of HopfieldIa yer enters a softmax output. We compared our mod- Hopfield networks against deep learning
et al.,
Method
avg. rank diff.
p-value
Hopfield (ours)
-3.9
SVM
-3.23
0.15
SNN
-2.85
0.10
RandomForest
-2.79
0.05
Stacking
8.73
1.2e-11 11
Table 2: Results on 75 small datasets of the UCI benchmarks given as difference to average rank.

---

methods (e.g. SNNs, resnet), RFs, SVMs, boosting, bagging, and many other machine learning methods of Fernández- Delaadezz-eiiaddo et al. (2014). Since for each method, multiple variants and imple- mentations had been included, we used method groups and representatives as defined by Klambauer et al. (2017a). For each dataset, a ranking of the methods was calculated which is presented in Table 2. We found that Hopfield networks outperform all other methods the small datasets, setting a new state-of-the-an for 10 datasets. The difference is significant except for the first three runner-up methods (Wilcoxon signed rank test). See appendix Section A.5.3 for details.
Drug Design Benchmark Datasets. We test the Hopfield layer Hopf eenffielae eldaaer, on four drug design datasets. These datasets represent four main areas of modeling tasks in drug design, concretely to develop accurate models for predicting a) new anti-virals (HIV) by the Drug Therapeutics Program (DTP) AIDS Antiviral Screen, b) new protein inhibitors, concretely human 8-secretase (BACE) in- hibitors by Subramanian et al. (2016), c) metabolic effects as blood-brain barrier permeability (BBBP) (Martins et al., 2012) and d) side effects of a chemical compound from the Side Effect Resource (SIDER) Kuhn et al. (2016). We applied the Hopfield layer Hopfis leeffelllle elayer, where the training data is used as stored patterns Y. the input vector as state pattern R. and the corresponding training label to project the output of the Hopfield layer Y Wv. Our architecture with Hopfi e 1 dLayer has reached state-of- sate--of-the-ar for predicting side effects on SIDER 0.672 + 0.019 as well as for predicting B-secretase BACE 0.902 + 0.023. For details, see Table A.5 in the appendix.
Conclusion. We have introduced a modern Hopfield network with continuous states and the corre- sponding new update rule. This network can store exponentially many patterns, retrieves patterns with one update, and has exponentially small retrieval errors. We analyzed the attention heads of BERT models. The new modern Hopfield networks have been integrated into deep learning architectures as layers to allow the storage of and access to raw input data, intermediate results, or learned prototypes. These Hopfield layers enable new ways of deep learning, beyond fully-connected, convolutional, or recurrent networks, and provide pooling, memory, association, and attention mechanisms. Hopfield layers that equip neural network layers with memories improved state-of-the-arr three out of four considered multiple instance learning problems and on immune repertoire classification, and on two drug design dataset. They yielded the best results among different machine learning methods on the UCI benchmark collections of small classification tasks.
ACKNOWLEDGMENTS
The ELLIS Unit Linz, the LIT AI Lab and the Institute for Machine Learning are supported by the Land Oberösterreich, LIT grants DeepToxGen 111-2017-3-YOU-003 and AI-SNN (LIT- 2018-6- 2018-6-YOU-211 YOU-214), the Medical Cognitive Computing Center (MC3), Janssen Pharmaceutica, UCB Biopharma, Merck Group, AU Deep Learning Center, Audi Electronic Venture GmbH, TGW, Primal, S3AI (FFG-872172). Silicon Austria Labs (SAL), Anyline, FILL, EnliteAl, Google Brain, ZF Friedrichshafen AG, Robert Bosch GmbH, TÜV Austria, DCS, and the NVIDIA Corporation. IARAI is supported by Here Technologies.
10

---

A APPENDIX
This appendix consists of six sections (A.1-A.6). Section A.1 introduces the new modern Hopfield network with continuous states and its update rule. Furthermore, Section A. provides a thorough and profound theoretical analysis of this new Hopfield network. Section A.2 provides the mathematical background for Section A.1. Section A.3 reviews binary Modern Hopfield Networks of Krotov & Hopfield. Section A.4 shows that the Hopfield update rule is the attention mechanism of the transformer. Section A.5 gives details on the experiments. Section A.6 describes the Py Torch implementation of layers based the new Hopfield networks and how to them.
CONTENTS OF THE APPENDIX
A.I
Continuous State Modern Hopfield Networks (A New Concept)
12
A.1.1
Introduction
12
A.1.2
New Energy Function
13
A.1.3
New Update Rule
15
A.1.4
Global Convergence of the Update Rule
16
A.1.5
Local Convergence of the Update Rule: Fixed Point Iteration
19
A.1.6
Properties of Fixed Points Near Stored Pattern
44
A.1.7
Learning Associations
57
A.1.8 Infinite Many Patterns and Forgetting Patterss
60
A.1.9 Number of Spurious States
A.2
Properties of Softmax, Log-Sume Exponential, Legendre Transform, Lambert W Function
62
A.3
Modern Hopfield Networks: Binary States (Krotov and Hopfield)
70
A.3.1 Modern Hopfield Networks: Introduction
70
A.3.2
Energy and Update Rule for Binary Modern Hopfield Networks
71
A.4
Hopfield Update Rule is Attention of The Transformer
73
A.5
Experiments
73
A.5.1
Experiment I: Attention in Transformers described by Hopfield d dynamics
73
A.5.2
Experiment 2: Multiple Instance Learning Datasets.
78
A.5.3
Experiment 3: Classification on Small UCI Benchmark Datasets
81
A.5.4
Experiment 4: Drug Design Benchmark Datasets
83
A.6
PyTorch Implementation of Hopfield Layers
84
A.6.1
Introduction
84
A.6.2
Functionality
85
A.6.3
Usage
87
LIST OF THEOREMS
A1
Theorem (Global Convergence (Zangwill): Energy)
16
A2
Theorem (Global Convergence: Stationary Points)
18
A3 Theorem (Storage Capacity (M=2): Placed Pattems)
46
11

---

A4
Theorem (Storage Capacity (M=5): Placed Patterns)
47
A5
Theorem (Storage Capacity (Main): Random Patterns)
49
A6
Theorem (Storage Capacity (d computed); Random Patterns)
52
A7
Theorem (Storage Capacity (expected separation): Random Patterns)
55
A8
Theorem (Pattern Retrieval with One Update)
56
A9
Theorem (Exponentially Small Retrieval Error)
A10
Theorem (Storage Capacity for Binary Modern Hopfield Nets (Demircigil et al. 2017))
72
LIST OF DEFINITIONS
A1
Definition (Softmax)
62
A2
Definition (Log-Sum-FF)) Sunn-xum-xpp Function)
62
A3
Definition (Convex Conjugate)
66
A4
Definition (Legendre Transform)
66
A5
Definition (Epi-Sum)
66
A6
Definition (Lambert Function)
69
LIST OF FIGURES
A.1 The three cases of fixed points
19
A.2 From binary Hopfield network to transformer
73
A.4 Ridge plots of the distribution of counts
................................
76
A.5 Change of count density during training
77
A.6 Attentions of Gaussian averaging heads
78
A.7 A flowchart of the Hopfield layer
88
LIST OF TABLES
A.1 Results of immune repertoire classification across all datasets
79
A.2 Hyperparameter selection for MIL datasets
80
A.3 Hyperparameter selection for small UCI benchmark datasets
82
A.4 Hyperparameter selection for drug design datasets
83
A.5 Results on drug design benchmark datasets
A.1 CONTINUOUS STATE MODERN HOPFIELD NETWORKS (A NEW CONCEPT)
A.1.1 INTRODUCTION
In Section A.I our new modern Hopfield network introduced. In Subsection A.1.2 we present the new energy function. Then in Subsection 1.1.3, our new update rule is introduced. In Subsec- tion A. 1.4, we show that this update rule ensures global convergence. We show that all the limit points of any sequence generated by the update rule are the stationary points (local minima saddle points) of the energy function. In Section A.1.5, we consider the local convergence the update rule and see that patterns of the fixed points that are associated with the stored patterns, In Subsection 1.1.6.1, we show that exponentially many patterns be stored. The main result is given in Theorem A5: For random
retrieved with update. In Subsection A.1.6, consider the properties
12

---

patterns sphere store and retrieve exponentially (in the dimension of the Hopfield space) many patterns. Subsection A.1.6.2 reports that patterns are typically retrieved with one update step and that the retrieval error is exponentially small.
In Subsection A.1.7, we consider how associations for the new Hopfield networks can be learned. In Subsection A.1.7.2, analyze if the association is learned directly by bilinear form. In Subsection A. 1.1.7.3, we analyze stored patterns and query patterns are mapped to the space of the Hopfield network. Therefore, treat the architecture of the transformer and BERT. In Subsection A. 1.1.8, we introduce a temporal component into the new Hopfield network that leads to a forgetting behavior. The forgetting allows us treat infinite memory capacity in Subsection 1.1.8.1. In Subsection A. 1.2.2 we consider the controlled forgetting behavior.
In Section A.2, we provide the mathematical background that is needed for our proofs. In particular we give lemmas properties of the softmax, the log-sum cum-exxonential, the Legendre transform, and the Lambert W function.
In Section A.3, we review the new Hopfield network as introduced by Krotov and Hopfield in 2016. However in contrast to our new Hopfield network, the Hopfield network Krotov and Hopfield binary, that is, network with binary states. In Subsection A.3.1, we give an introduction to neural networks equipped with associative memories and new Hopfield networks. In Subsection 1.3.1.1, discuss neural networks that are enhanced by additional external memory and by attention mechanisms. In Subsection A.3.1.2, we give an overview over the modern Hopfield networks. Finally, in Subsection A.3.2, we present the energy function and the update rule for the modern, binary Hopfield networks.
A.1.2 NEW ENERGY FUNCTION
We have patterns T1, &N that are represented by the matrix
X (x (zI....,
(1I)
The largest norm of a pattern is
M = max |
(12)
The query or state of the Hopfield network is c.
The energy function E, in the new type of Hopfield models of Krotov and Hopfield is E E.", F F æ.)) for binary patterns æ; and binary state & with interaction function F(x) = x". where 2 gives classical Hopfield model (Krotov & Hopfield, 2016). The storage capacity is proportional to nn1 (Krotov & Hopfield, 2016). This model was generalized by Demircigil et al. (Demircigil et al., 2017) to exponential interaction functions F(x) exp(x:). which gives the en- xTE)),
ergy E = exp exp(Ise(1) (1, x {)). This energy leads to exponential storage capacity of N 24/2 for binary patterns. Furthermore, with a single update the fixed point is recovered with high probability. See more details in Section A.3.
In contrast to the these binary modern Hopfield networks, we focus on modern Hopfield networks with continuous states that store continuous patterns. We generalize the energy of Demircigil et al. (Demircigil et al., 2017) to continuous states while keeping the lse properties which ensure high storage capacity and fast convergence. Our energy F. for continuous query or state is defined
13

---

E = - -1eeB, xT
+ 1 2 + ---
+ 1
2 M
(13)
INN + 1 Z5T 2 M²
--3-1 In
- 3
Σ exp(BaxT()
(14)
- -33-1m In
N
exp (-z 3 (1==110:11)))
exp (-2 3 ||,; - -E(²))
(15)
First let us collect and prove some properties of E. The next lemma gives bounds on the energy E.
Lemma A1. The energy F. is larger than zero:
<
E.
(16)
For in the simplex defined by the patterns, the energy E is upper bounded by:
E < B InN
+ 2 M²
(17)
E 2
(18)
Proof.
We start by deriving the lower bound of zero. The pattern most similar to query or state g is
Zg:
Eg
Ik
k
arg max E" x2
(19)
We obtain
E = --1 In
Σ exp(3x 6)
+ In + 2
3 +
1
M²
(20)
2
8-8 In
Σ exp(3af() E)
+ 2
1
5- +
1
M2
N
2 8-1 In
1
Σ exp(3x((() k)
+ 2
1
t" +
1
a x
N
2
1 TT
2 8-1 In (exp(3xT()) ()) + 2
+
2 2
= a & + 1 E"EE +
1
xς xt
2
2
= (E - xạ) (E - xx) = 2 ||E xg 2 2 0.
The energy zero and, therefore, the bound attained, all æ, are equal, that is, a; = x for all and { T.
For deriving upper bounds on the energy E, we require the the query & to be in the simplex defined by the patterns, that is
E Σ Ps
Σ p:
1,
W: 0 & Ps
(21)
The first upper bound is.
N Σ exp((BaT 3)
す Eee + 8- InN + 1 M²
E - 3 In
(22)
1=1
N
ETE + InN 1 122
Σ
Pi (x. {)
1
St'S + g In N + 1 M² < B
+ 1 2
I
M²
2
2
14

---

For the first inequality applied Lemma A19 to -Ise(3,X with p giving
1sso(3,X'g
Σ ps (a E)
Pe Inps
Σ Pi (m)
(23)
as the term involving the logarithm is non-positive.
Next we derive the second upper bound, for which we need the mean my the patterns
N
m
2
(24)
We obtain
N
E = - 3-11n -33 In
Σ
exp(Bax
+
E +
n + M
(25)
2
2
1=1
N
Σ
2.
T
E
+
1
E"
1
.²2
N
2
2
-=1
1
m
+
5² g
+ M²
2
2
< |m |IE||
||
M
< 2 2
where for the first inequality again applied Lemma A19 with (1/N, ...,, 1/N) and 8 B-'E, Σ, 1/N (n11/N) = - In().. This inequality also follows from Jensen's 's inequality. The second inequality uses the Sauchy-Schware inequality. The last inequality uses
||ll|
Σ Pr wa
Σ Pi ||
& ΣnM M
(26)
and
mx ||
(L/N) 2
[(//N) |لر||| & Σ(1/N) M
(27)
A.1.3
NEW UPDATE RULE
We now introduce an update rule for minimizing the energy function F. The new update rule is
E new = Xp Xsoftmax(3X*1 {)
(28)
where we used
p (3x
(29)
The new state enew is in the simplex defined by the patterns, no matter what the previous state & was. For comparison, the synchronous update rule for the classical Hopfield network with threshold zero is
new
sgn (x)T)).
(30)
Therefore, instead of using the vector x as the classical Hopfield network, its softmax version softmax(8X* is used.
In the next section (Section A.1.4) we show that the update rule Eq. (28) ensures global convergence. We show that all the limit points of any sequence generated by the update rule the stationary points (local minima or saddle points) of the energy function E. In Section A. we consider the local convergence of the update rule Eq. (28) and that patterns are retrieved with one update.
15

---

A.1.4 GLOBAL CONVERGENCE OF THE UPDATE RULE
We are interested in the global convergence, that is, convergence from each initial point, of the iteration
gnew = ((E) = Xp = 23oftmax(3X'6
(31)
where we used
p softmax(3x'
(32)
We defined the energy function
1 M² IN + 25A
E Ise(B, X"E)
(33)
2
2
N
-
3-1 In Σ exp(Bat
3 +
1 5 M².
(34)
We will show that the update rule in Eq. (31) is the Concave-Conver Procedure (CCCP) for minimiz- ing the energy E. The CCCP is proven to converge globally.
Theorem A1 (Global Convergence (Zangwill): Energy). The update rule Eq. (31) converges globally: For t = f(Et), the energy (E(E)) + for oo and fixed point 8".
Proof. The Concave-Convex Procedure (CCCP) (Yuille Rangarajan, 2002: 2003) minimizes function that is the sum of a concave function and convex function. CCCP is equivalent to Legendre minimization (Rangarajan et al., 1996; 1999) algorithms (Yuille & Rangarajan, 2003). The Jacobian of the softmax is positive semi-definite according to Lemma A22. The Jacobian of the softmax is the Hessian of the lse, therefore lse is convex and -Ise a concave function. Therefore, the energy function E(E) is the sum of the convex function E (E) 1/2 & + C1 and the concave function E2(E) lse:
E(E)
EE(E) + Eg(E),
(35)
1 LETE + 8- In + M²
1
1 h Cr,
E, (E)
(36)
2
2
2
(E) (8, x²
(37)
where 11 does depend on
The Concave-Convex Procedure (CCCP) (Yuille & Rangarajan, 2002; 2003) applied to E is
EgEi (g*+1) = = = (5*)
(38)
which is
Ve 5 + Ci) (5t+2) = Velse(B, x
(39)
The resulting update rule is
gd =Xp' Xsoftmax(3x*
(40)
using
p' (3x"ma
(41)
This is the update rule in Eq. (31).
Theorem in Yuille & Rangarajan (2002) and Theorem Yuille Rangarajan (2003) state that the update rule Eq. (31) is guaranteed to monotonically decrease the energy E as function of time. See also Thcorem 2 in Sriperumbudur Lanckriet (2009).
Although the objective converges in all cases, does not necessarily converge to a local minimum (Lipp & Boyd, 2016).
16

---

However the convergence proof of CCCP in Yuille & Rangarajan (2002; 2003) was not rigorous as required. Sriperumbudur & Lanckriet (2009) a rigorous analysis of the convergence of CCCP is performed using Zangwill's global convergence theory of iterative algorithms.
In Sriperumbudur Lanckrict (2009) the minimization problem
min E1 + E2 c < 0, d( 0
(42)
ε
is considered with E, convex, - E2 convex, component-win convex function, and d affine function. The CCCP algorithm solves this minimization problem by linearization of the concave part and is defined in Sriperumbudur & Lanckriet (2009)
S c E arg min E1 (E) + E" V (s')
(43)
s.t. c(E) & 00, d(E) 0.
We define the upper bound Ecc the energy:
Ec (E) En (E) + E2 (5') (E 5¹)² PeFi2 (59) Ec is equal to the energy E (E*) for E = E::
(44)
Ec (5', E, (5") + E, (5') = E (5")
(45)
Since - E2 is convex, the first order characterization of convexity holds (Eq. 3.2 in Boyd & Vanden- berghe (2009)):
E2 (E) 2 (E9) --) EeE2 (E*)
(46)
that is
E2 (E) < Eg (E') (E 5t) " EgE2 (E')
(47)
Therefore, for & o g¹ the function Ec is an upper bound on the energy:
E (E) < Ec E") = Ei (E) + E2 (5') + (S Ve (g')
(48)
E, (E) Fe (5*) + C2
where C2 does not depend on g. Since we do not have constraints, g++ defined as
g++1 arg min Ec (E.E"),
(49)
&
hence Eg (gt+1, .() < Ec ( ( Combining the inequalities gives:
E ( 11) Eg (g (5)
Ec (5',E') (5
(50)
Since we do not have constraints, g++1 is the minimum of
Ee (5) E1 (E) + V (5") + Cz
(51)
as function of g.
For minimum not the border, the derivative has be the zero vector
UEc (E.E') + EgEz (E*) = E Sxofttmx(3xTTe
(52)
ag
and the Hessian must be positive semi-definite
(53)
oe²
17

---

The Hessian is strict positive definite everywhere, therefore the optimization problem is strict convex (if the domain is convex) and there exist only one minimum, which is global minimum. Eg can even be written quadratic form:
Ec EE)
(5 + VeE2(E)) (E + VgE2 (59) + Cs
(54)
where C3 does not depend on g. Therefore, the minimum is gh+ VgF2 Xsoftmax(xX"
(55)
it is in the domain as we assume.
Using M = max; ||, ed+1 is in the sphere S = {- ||=||| < M which is convex and compact set. Hence, if ęd E S. then the iteration defined by the iteration Eq. (55) is uniformly compact on S according to Remark 7 in Sriperumbudur Lanckriet (2009). Theorem 2 and Theorem in (Sriperumbudur Lanckriet, 2009) states that all the limit points of the iteration Eq. (55) are stationary points. These theorems follow from Zangwill's global convergence theorem: (1983).
mapping from S to S. Therefore, the point-set-map
Convergence Theorem A, page 91 in Zangwill (1969) and page 3 in Wu
The global convergence theorem only assures that for the sequence g(+1 = f(5*) and a function & we have ( + (E")) for - oo but not 5 - 5* However, if is strictly monotone with respect to 4, then we can strengthen Zangwill's ' global convergence theorem (Meyer, 1976). We set Φ = E. and show F1(g+t1== < F if g is not stationary point of F,, that is, is strictly monotone with respect to F.. The following theorem is similar to the convergence results for the expectation maximization (EM) algorithm in Wu (1983) which are given in theorems I to 6 in Wu (1983). The following theorem is also very similar to Theorem 8 in Sriperumbudur & Lanckriet (2009).
Theorem A2 (Global Convergence: Stationary Points). For the iteration Eq. (55) we have E. (g)) -> (EE) E* t + 00, for some stationary point E". Furthermore g E + O and either (= converges or, in the other case, the set of limil points of [ Ji=o a connected and compact subset of C (E*), where ((a = =E E C E (E) a} and L is the set of stationary points of the iteration Eq. (55). C (E*) is finite, then any sequence Jt=o generated by the iteration Eq. (55) converges to some 8* E C((E))
Proof. We have E (5') = E1 +2))) The gradient V&E2 (5') = -Velse(B, X² is continuous. Therefore, Eq. (51) has minimum in the sphere S, which is convex and compact set. If g++ * C,, then g was not the minimum of Eq. (48) as the derivative at g is not equal to zero. Eq. (53) shows that the optimization problem Eq. (48) is strict convex, hence it has only one minimum, which is a global minimum. Eq. (54) shows that the optimization problem Eq. (48) is even a quadratic form. Therefore, we have
E (g( < Ec (g'+1
Ec (5),5) E E(')
(56)
Therefore, the point-set-man defined by the iteration Eq. (55) (for definitions see (Sriperumbudur & Lanckriet, 2009)) is strictly monotonic with respect to E. Therefore, we can apply Theorem 3 in Sriperumbudur & Lanckriet (2009) or Theorem 3.1 and Corollary 3.2 in Meyer (1976), which give the statements of the theorem.
We showed global convergence of the iteration Eq. (31). We have shown that all the limit points of any sequence generated by the iteration Eq. (31) are the stationary points (critical points; local minima or saddle points) of the energy function E. Local maxima as stationary points are only possible the iterations exactly hits local maximum. However, convergence to a local maximum without being there is not possible because Eq. (56) ensures a strict decrease the energy E. Therefore, almost sure local maxima are not obtained stationary points. Either the iteration converges or, in the second case, the set of limit points is a connected and compact set. But what happens if gd is in an e-neighborhood around local minimum ? Will the iteration Eq. (31) converge to ? What is the rate of convergence? These questions are about local convergence which will be treated in detail in next section.
18

---

A.1.5 LOCAL CONVERGENCE OF THE UPDATE RULE: FIXED POINT ITERATION
For the proof of local convergence to fixed point will apply Banach fixed point theorem. For the rate of convergence we will rely on properties of contraction mapping.
A.1.5.1
General Bound on the Jacobian of the Iteration.
We consider the iteration
gnew
f(E) = Xp Xsootmax(3XX
(57)
using
p 2oftmax(3X'F
(58)
The Jacobian J is symmetric and has the following form:
((( B (diag(p) -ppppp'))))))))>>)) x XJ,X²
(59)
where J is Jacobian of the softmax.
To analyze the local convergence of the iteration, we distinguish between the following three cases (see also Fig. A.I). Here we only provide an informal discussion give the reader some intuition. rigorous formulation of the results can be found in the corresponding subsections.
a) If the patterns æ; are not well separated, the iteration goes to fixed point close to the arithmetic mean of the vectors. In this case is close p; 1/N.
b) If the patterns I; are well separated, then the iteration goes to the pattern to which the initial & is similar. If the initial & is similar
vector æ; then will converge vector close to e; and will converge to vector close to é;.
c) If some vectors are similar to each other but well separated from all other vectors, then called metastable state between the similar vectors exists. Iterations that start near the metastable state converge to this metastable state.
T m
m w.
m
m
S
B
=
8 0.2
pattern
fixed point
average pattern
Figure A.I: The three cases of fixed points. Stored patterns (fixed point single pattern): patterns are stored if they are well separated. Each pattern has single fixed point x; close to it. In the sphere S,, pattern x; is the only pattern and x the only fixed point. b) Metastable state (fixed point is average of similar patterns): æ; and æú are similar to each other and not well separated. The fixed point m is metastable state that is close to the mean my of the similar patterns. e) Global fixed point (fixed point is average of all patterns): no pattern is well separated from the others. A single global fixed point m exists that close to the arithmetic mean mz of all patterns. We begin with a bound on the Jacobian of the iteration, thereby heavily relying on the Jacobian of the softmax from Lemma A24.
Lemma A2. For patterns X = (æI...., NN), = softmax(33 3 M = max; || and max; p: pi), the spectral norm of the Jacobian J of the fixed point iteration is bounded:
||J|| < 2
1 m < 2 N M m. |
(60)
Puax max; pi 1 - e, then for the spectral norm of the Jacobian holds
|J]|| 2 N M
2 3 n M² 23 N M² 6.
(61)
19

---

Proof. With
p softmax(3X*
(62)
the symmetric Jacobian is (f(E)
B X (diag(p) pp" x XJ,X",
(63)
a
where J3 is Jacobian of the softmax.
With m max; Pt(1 - pt), Eq. (476) from Lemma A24 is
||ا|| |ddaa(p) ppp'l2 < 2 m B
(64)
Using this bound on |] obtain
||ل| < 3 || |Jall2 |X||2
2 m |
(65)
The spectral norm I1-Ilp is bounded by the Frobenius norm ||-11 which can be expressed by the norm squared its column vectors:
| &
|X
(66)
Therefore, we obtain the first statement of the lemma:
||]l < 3
| l m < 2 M m.
(67)
With Pmax max, P. 2 1 c Eq. (480) in Lemma A24 is
|Jا|| < 2 2 3 2.6
(68)
Using this inequality, we obtain the second statement of the lemma:
||lla & 2 3N
3 M < 2
(69)
We now define the "separation" A, of pattern æ; from data X = (æ1,.... xNn here, since it has an important role for the convergence properties of the iteration.
Definition 2 (Separation of Patterns). We define A., i.e. the separation of pattern from data X (1 11,...,,yy. NN) as:
A min (zf x
a. xz) x x;
max x x;
(70)
The pattern separated from the other data if Ds. Using the parallelogram identity, A can also be expressed as
[|<::112
|| + || =2,11²)
A = min
(71)
J.
2
1
xc 1|2
1
max (1æ0;112 ||20 22,13)
2
2 j.fii
For ||x ||æ have A, 1/2 min || a.,12
Analog we say for a query & and data (II x that x; is least separated from while being separated from other æ; with if
i arg max min (5T xz - _"T ..))) = arg max (5TTR
argmax
max E:
m.
(72)
1.
3.44
0 < = max min
(5T IDg gxx,,) max &
max E" 2z)
(73)
Jj
j.ik
Next consider the case where the iteration has only stable fixed point.
20

---

A.1.5.2 One Stable State: Fixed Point Near the Mean of the Patterns. We start with the where no pattern is well separated from the others.
Global fixed point near the global mean: Analysis using the data center.
We revisit the bound on the Jacobian of the iteration by utilizing properties of pattern distributions. We begin with probabilistic interpretation where consider ps as the probability of selecting the vector a4-- Consequently, we define expectations [x] Σ (a.).. In this setting the matrix
X (diag(p) pp") x )²
(74)
is the covariance matrix of data X when its vectors are selected according to the probability p: (diag(p)
X
- -ppp) x
(p)
Xppp xpp"X" x
(75)
N
N
Σ
Pi a. x.
Σ
Pi az Σ
(76)
i=1
Epp x²]
Exp(0] Eyp [ac
Varpla]
(77)
therefore we have
J Varplæ).
(78)
The largest eigenvalue of the covariance matrix (equal to the largest singular value) is the variance in the direction of the eigenvector associated with the largest eigenvalue.
We define:
m2g
(79)
Mmax
max
||:;
mm 1aml12-
(80)
1
me is the arithmetic mean (the center) of the patterns. Mmax is the maximal distance the patterns to the center m.
The variance of the patterns is
Varp [0]
Σ Pi Bi x?
Ps æ;
Σ Ps Wi
(81)
Σ
Pt
D
pids
pi
The maximal distance to the center Mmax allows the derivation of bound on the norm of the Jacobian.
Next lemma gives condition for a global fixed point.
Lemma A3. The
The following bound on the norm [J]| of the Jacobian of the fixed point iteration f holds independent of p or the query
|J]| < B m
(82)
For 33 m2 < 1 there exists unique fixed point (global fixed point) of iteration f in each compact set.
Proof. In order to bound the variance compute the vector that minimizes
f(a) = Σ pille;
all²
Σ
Pelae, ax;( a).
(83)
1=1
1=1
21

---

The solution
0s(a)
N
2
Σ
pi(a - x;i = 0
(84)
da
i=1
is
N
a
=
Σ i=1
P;tt
(85)
The Hessian of / is positive definite since
8 f(a)
N
Pi
21
(86)
da
and f is a convex function. Hence, the mean
N
Pi æz
(87)
minimizes Ei= pil|x; al?² Therefore, have
N
N pille;
Σ 1=1
Σ
mz 112 < m
(88)
Let us quickly recall that the spectral norm of an outer product of two vectors is the product of the Euclidean norms of the vectors:
|ab* ll2
v Ammxx(bal abT) ||a|| V Xmaxx (bbT) ||a|| |b|||
since 66" has cigenvector 6/||b|| with eigenvalue ||b]] and otherwise zero eigenvalues.
now bound the variance of the patterns:
||cos =x) (x; 3)"11
Varp
(90)
i=
p pill x0|
pil b||
mz 12 < m
The bound the lemma on [J]] follows from Eq. (78).
For [|J]|2 & 3 m maax < 1 we have a contraction mapping on each compact set. Banach fixed point theorem says there is a unique fixed point in the compact set.
Now let us further investigate the tightness of the bound on ||arpp ll via ||z =1|² we consider the trace, which is the sum Σi=1 es of the w.l.o.g. ordered nonnegative eigenvalues eμ of Var, [=x] The spectral norm is equal to the largest eigenvalue et, which is equal the largest singular value, as we have positive semidefinite matrices. We obtain:
Varp|ai]l2
Tr
Σ
pi (ar;
x)) (x) x)²)
Σ
Ck
(91)
d
Σ PrTr Tr (ax; x) (x, - x) x)7)
Σ
Ck
iml
Pil [ x01?
Ek
1
k=2
22

---

Therefore, the tightness of the bound depends eigenvalues which are not the largest. Hence variations which are not along the largest variation weaken the bound.
Next we investigate the location of fixed points which existence is ensured by the global convergence stated in Theorem A2. For N patterns X = , ,N.) we consider the iteration
&now
f(E)
Xp Xsoftmax(3X*
(92)
using
p softmax(3X*
(93)
nnow is in the simplex of the patterns, that is, Enew = =E, P: with P = and 0 & Hence, after one update È is the simplex the pattern and stays there. the center my is the zero vector mz O, that is, the data is centered, then the mean is a fixed point of the iteration. For & = m we have
p = 1/N1
(94)
and
Snew 1/N X1 = E
(95)
In particular normalization methods like batch normalization would promote the mean as fixed point.
We consider the differences of dot products for æ;; at x; 10;-22 2t aj (a: (a:--,))) for fixed point m (m+))² x; (m²))² = " az Using the Cauchy- Schharr inequality, we get
"(o; - æt)) and for the center m.z: m - m mn m (æ; - 2.
(x: æ5)) < |||| |
myyl & ||El| (Ila;; - mall + ||æ0 m2
(96)
2 Mmax ||E||
This inequality gives:
E (x; - æ;)]
< 2 Minax (Minxx + ||
(97)
r² (x; 2.)
< 2 Mamax M.
where we used ||8 0ll & || m= ll +
|m Oll || mx In particular
1E P.D. ma
Σ, pil|x x - mz & Mmaxx and max; |<:;||
3 mm (x. æz) 2 8 Mmax m
(98)
8 (m TT (ax æ;)l 3 Maax
m=
229 Munax (Mmmxx + |m=
(99)
B x (x: - 2;)] < 2 3 Mmax |
< 3 Maax (Maax + ||
(100)
Let i = arg max, &Tx,, therefore the maximal softmax component i. For the maximal softmax component we have:
[softmax (3 xT Ej exp(- B (ET TT E x,)))
(101)
EjØt exp(- 33 mmax (Mmax + m II)
I + (N - cxxpp( 2 3 Minax (Minxx + |
exp(2 mmax (Mmax + || (I))
exp(2 Mmax (Mmax + || II)) + (N - 1) 1/N exp(2 m.ax (Munxx mz Il))
23

---

Analogously obtain for i arg max, mz bound on the maximal softmax component i if the center is put into the iteration:
[softmax(3 X ma))e ): < 1/N exp(2 3 mmax ||
(102)
"a, Analog obtain bound for = arg max, (m ) 2y on the maximal softmax component of the fixed point:
[softmax(B x" xmm))): & 1/N exp(2 3 mmax || II)
(103)
1/N exp(2 8 mmax (70mxx +
|
The two important terms are maxx. the variance or spread of the data and || which tells how well the data is centered. For a contraction mapping we already required Bm 1, therefore the first term in the exponent is 2,m max < 2. The second term 23 m= Il is small if the data is centered.
Global fixed point near the global mean: Analysis using softmax values.
E x, se E æj for all i and j. then p; > 1/N and we have m max, Pa 10--p) p.) < 1/N. For M < 1/B23 we obtain from Lemma A2:
|| < 1.
(104)
The local fixed point is m ss mx (L/N) EI H; with pj 1/N.
We now treat this case more formally. First discuss conditions that ensure that the iteration is contraction mapping. We consider the iteration Eq. (57) in the variable
new
g(p) = voftmax(3xX Xp).
(105)
The Jacobian is
J(p) = Og(p)
x J.
(106)
Öp
with
(p (diag(p"ew) new gpew))
(107)
The version of the mean value theorem in Lemma A32 states for J J(Xp) d== X with the symmetric matrix J = (x()p) dA:
now =g(p) =g(0) + (Jm)TP s(0) J x 1/N1 + J X X p
(108)
With m max; pi(1 p.). Eq. (476) from Lemma A24
[p) || 3 ||iag(p) -pp"" I| < 2 m B.
(109)
First observe that Ap; - Ap;) & p. (1 p.) for ps 0.5 and À [0, 11, since p1 p.) - Ap,
Ap:) = (1 A)p:(1 (1 + A)p,) > 0. For max, pj < 0.5 this observation leads to the following bound for J
|| < 2 m 8
(110)
Eq. (479) Lemma A24 states that every J, is bounded by 1/23, therefore also the mean:
|
0.5 3
(1I1)
Since m max; pi(1 pt) max; Ps Pmax the previous bounds can be combined as follows:
J 1| < min(0.25, Prnax) B
(112)
24

---

Consequently,
||
< N M min Pmax }
(113)
where used Eq. (170). second moment of the data squared.
| X||
x therefore |x 1| is N times the maximal
Obviously, (()) is contraction mapping in compact sets, where
N M² min 00.25, Pmax B < 1.
(114)
S is the sphere around the origin 0 with radius one. For
new
g(p) 1/N 1 J p,
(115)
we have |pl|| < ||p|| = and [|peew| 1p || = Therefore, y maps points from S into g is
contraction mapping for
|J < N M 2 min(0.25, Pmax] 3 c 1.
(116)
According to Banach fixed point theorem g has a fixed point in the sphere S. Hölder's inequality gives:
lp 2
p'p <
1111111P11e = =|plloo
Pmax
(117)
Alternatvely:
|pl
Σ
p
Pmaa
Ps
Pt &
Pmax
Σ Pi
Pmax
(118)
Pmax
Let now be the sphere around the origin O with radius 1/VN + Pmax and let [|J" (p) & c < for p E S. The old p is in the sphere S (p E S) since Pmax Pmaxx for Pmax < 1. We have
Ip
L/VN + || lplll < 1/VN + VPmax
(119)
Therefore, g is mapping from into S and a contraction mapping. According to Banach fixed point theorem, fixed point exists in S.
For the 1-norm, we use Lemma A24 and ||p|| = 1 to obtain from Eq. (115);
Ip new
1/N 1|],
& ||"||| < 2.3 | M1
(120)
p new
1/N 1|]
< [|"*|]
< 2 m N Mo M1
(121)
Ip new
- 1/N 1|11 < [|]"
< 2 m N M
(122)
where m = max; (1 - p.). M, = |X||, = max; ||=|]], M max; | |X = X
||
max; ||[*"]||, (maximal absolute row sum norm), and Mxx = max, æ lloe Let us quickly mention some auxiliary estimates related to x
N
xxTXli = max
Σ
x
< max
|l00 ||æ
(123)
/=1
N
<
M Σ
Mi N Mso Mi
j=1
where the first inequaltiy is from Hölder's inequality. We used
N
x ||,
x
max
a
max
|m: ll |
(124)
N = M
j=1
25

---

where the first inequality is from Hölder's inequality (here the same as the Cauchy- Schwarz inequality). See proof of Lemma A24 for the I-norm bound on Jg. Everything else follows from the fact that the 1 1-norm is sub-uullin aub-mulippliative as induced matrix norm.
We consider the minimal |pp|.
min P
||p|
(125)
Ed:=
s.t.
41: pt 2 0.
The solution to this minimization problem is = (1/N)1. Therefore, we have 1/vN < |p|| and 1/N
|pl| Using Eq. (119) obtain
I/VN < |p new
< 1/VN
Vmaxx
(126)
Moreover
new 2 = (p (p"ww)= ) new
1/N + (p (p" p & 1/N + |J" lpll
T
(127)
< 1/N + ||
since p nee E S and S.
For the fixed point, we have
le 12 (p")Tp" = 1/N + (D')TTmm p-' & 1/N + || ll 10
(128)
and hence
1
| l J| 2
1/N < |p'1| < 1/N 1 1 = 1/N (1 +
(129)
Therefore, for small [J we have p" = (1/N)1.
A.1.5.3 Many Stable States: Fixed Points Near Stored Patterns. We move to the next case, where the patterns I; are well separated. In this case the iteration goes to the pattern to which the initial is most similar. If the initial is similar to vector æ; then it will converge æ;; and p will The main ingredients are again Banach's Theorem and estimates on the Jacobian norm.
be eG.
. Proof of fixed point by Banach Fixed Point Theorem.
+ Mapped Vectors Stay in a Compact Environment. We show that if æ; is sufficient dissimilar to other my then there is compact environment of æ; (a sphere) where the fixed point iteration maps this environment into itself. The idea of the proof is to define a sphere around a; for which points from the sphere are mapped by ff into the sphere.
We first need following lemma which bounds the distance ||æ:; - f(E) where æ; is the pattern that least separated from & but separated from other patterns.
Lemma A4. For query& & and data X (æ1,...., N.)), there exists æ; that is least separated from & while being separated from other æ. with j +
arg max min 1534
(ET
<Tx3')
arg max
E <T
max ET 334k
(130)
OEC= max min (ET x (Txx,) max ( J5fk
max E" 22 J.fk
(131)
For wi the following holds:
||:;
s(E) & 2 M.
(132)
where
M max |
(133)
(N -1 1) exp( 3c)
(134)
26

---

Proof. For the softmax component i we have:
|sottmax(3 xx
2
(135)
+ Eigi exp(3 (f" - {'xxi)
1 + Ejzz jzt exp 8 3c)
(N - 1) exp( - 8c)
(N 1) exp(- 3c) =
1 (N 1) exp(- c)
2 1 - (N - exp( - 3c = =1- -
For softmax components k * i we have
exp(8 (5" Lk g x'x1))
[softmax(3x* E)
& exp(-
I + Ejys exp(8 (f''r, {²'x;))
N -
(136)
The iteration f can be written as
f(E) Xsoftmax(3X'8
Σ æj |softmax(33" E)); ==
(137)
We now can bound ||a, [(E)|::
s(E)
F2;
softmax(33X E)]B Fg
(138)
/softmax/ (xx
E)ls) xz
Σ
[softmax (8X E)1 Zj
i 18
c
Σ
|
1
j=1.jzi
M
Σ
M
M
J=1
We define A, i.e. the separation of pattern æ; from data X (x ..,,, LNN
as:
A
min ju
x x4 x xz))
x
max xf æy 357i
(139)
The pattern is separated from the other data if 0 < A. Using the parallelogram identity, A, can also be expressed as
A min
(1l0;112
||>,112
|| 22,11²)
(140)
jj
= 2 | 2
[12;;11 - || 2;513)
max
2
5.44
For ||x:|| ||æ we have A, = 1/2 min || 2.,1?
Next we define the sphere where we want to apply Banach fixed point theorem. Definition (Sphere S,). The sphere Sy is defined as
{ E 1 xill
1
S.
(141)
3
Lemma A5. With & given, if the assumptions
27

---

A1: & is inside sphere: St.
A2: data point is well separated from the other data:
2
A Z
BN (N
(142)
hold, then f(E) is inside the sphere: f(E) E S,. Therefore, with assumption (A2), f is a mapping from S into S
Proof. We need the separation F, of f from the data.
Å min (E x, <²z²)
(143)
3372
Using the Cauchy-Schwand inequality, we obtain for
< j < N:
& x. x & ||E - x; ||ز < || - x; M.
(144)
We have the lower bound
Å 2 min
(<x, x;
IKE - xill M) (a. Φ3 + | - x;1l M))
(145)
= - 2 le - x;ll
M + min
(x) x;
x zz)) = A; 2 le - x; M
2 A N
where we used the assumption (A1) of the lemma.
From the proof in Lemma A4 we have
Pmax [softmax (3x* {)), 2 1 - (N -V-1] 1) exp(- 3 Å.) = - E.
(146)
Lemma A4 states that
xC; - f(E) < 22 = 2 (N - 1) exp( Ai) M
(147)
2
2 1) exp( (A:
B M
have
[2 f(E)ll
(148)
2
< 2 (N - 1) exp(- 3
+ In (2 (N - - N 3
BN )) M
3 N 3
2 (N -1) 1) exp(- (2 (N 1) 3 M2) M
1
N M
where we used assumption (A2) of the lemma. Therefore, f(E) is mapping from the sphere S; into the sphere S; If & E S; then (E) E S..
Contraction mapping.
For applying Banach fixed point theorem we need to show that f contraction in the compact environment S.
Lemma A6. Assume that
Al:
2
A
+
In
(149)
3
N
B
then f is contraction mapping in St-
28

---

Proof.
The version of the mean value theorem Lemma A32 states for J
J(E (1- A)x,))
dA:
F(E) - ((xi) J (E - x;)
(150)
Therefore
lIf(E) - f(x:)] < | l|5 - x;ll
(151)
We define g = AE (1 X) for some [0, 1]. From the proof in Lemma A4 we have
Pmax (
|softmaxx3 x E)] 1 (N - 1) exp(- - B A.) 1 E,
(152)
(N 1) exp(- 3 A,),
(153)
min JJ
5 æ; 5" ạ;
(154)
First compute upper bound on é. We need the separation Å, of & from the data. Using the Cauchy-Schward inequality, we obtain for < j & N:
E x! 2z
<
2e
||æ
< { 2; M
(155)
We have the lower bound on Â;:
A 2 min jUसi
[ x2;
- || s5:=il M) (a. æs + | - 2:1 ///aa))
(156)
= - E x;
M + min (x x; - af xz) = A. 2 ||E - æ: A1
jjfi
A,
x;il| M,
where we used
{ - x2
= a|ls - æ: < ||5 xill. From the definition of é in Eq. (152) we have
(N 1) exp(- -pp(-3 33 A.)
(157)
(N 1) exp (- 3 (A; - - x;il M))
(-8 A; 2
N ))
(N 1) exp
where we used & E S, therefore ||E - xil < N W
Next we compute an lower bound on ē. We start with an upper on A;;
Á < min 3,125
[x. x; + E 2. M) (xTar _ æe| M))
(158)
M + min (x xs - x7 x1)) = A: + =l| xz M
2
x;
júft
A;
æill M
where we used
{
x
= AllE - x & || æ.|l. From the definition of ē in Eq. (152) we have
= (N - 1) exp( - 3 A.)
(159)
(N 1) exp (- 3 (A; + 1| xill M))
(N 1) exp (-3
N ))
2
A; +
where we used & E St, therefore ||E - xill < N M
Now we bound the Jacobian. We can assume È < 0.5 otherwise (1 () < 0.5 in the following,
From the proof of Lemma A24 we know for Prnxx 3 > ē, then p:(g) & ē for p=(E) # Pmaxx (E).
29

---

Therefore, (1(E) - Pı(E)) & ē(1 2) for all Next use the derived upper and lower
bound on ? in previous Eq. (61) in Lemma A2:
|
< 2 N M 2 3 M
(160)
< 2 N M² (N 11 exp (-3
A, 3/
2
))
3N
2 (N 1)² exp (-288 2,3 A.
B ))
2
2
BN M
The bound Eq. (160) holds for the mean Jm too, since averages over J(E):
2 ))
| & N M (N - 1) exp - 8 A.
(161)
BN
2 (N - 1)2 exp 22 (A. Ai + 2 N
)) B MN
The assumption of the lemma is
A
+
In (2
(162)
B N
B
This is
2
A:
2 In (2
(163)
3 N
Therefore, the spectral norm []J[] can be bounded by:
|J 1l & 2 (N 1) exp (- 8 1 In 1I N M
(164)
2 (N- 15-11 1)2 exp (-2 A
)) BNM
23(N - 1)
N M²_
2(N 1) N 3 M
2 (N- - 1)2 exp (-2.3 A
B BN M²
B N
<1. I ))
2
= - 2 (N 1)² exp 2 A; +
BNMP
Therefore, f is contraction mapping in S:.
Banach Fixed Point Theorem. Now have all ingredients apply Banach fixed point theorem. Lemma A7. Assume that
AI:
2
+ 3 In
(165)
then f has a fixed point in S,.
Proof. We use Banach fixed point theorem: Lemma A5 says that f maps from S; into S,. Lemma A6 says that is contraction mapping in Sj.
[]
30

---

CContraction mapping with a fixed point.
We have shown that a fixed point exists. We want to know how fast the iteration converges to the fixed point. Let ot be the fixed point of the iteration f in the sphere Sy. Using the mean value theorem
Lemma A32, we have with J So J(AE + (1 - >)a=)) dλ: (E)
x; (E) f(x\)|l < || llE 2;
(166)
According Lemma A24, if Pmax max; pi 2 1 for all E XE + (1 A)af then the spectral norm of the Jacobian is bounded by
|| Il 2eB.
(167)
The norm of Jacobian is bounded
[|(())ll2 < 2 X 2 & 2 N c.
(168)
We used that the spectral norm I1-112 is bounded by the Frobenius norm ||-I|p which can be expressed by the norm squared of its column vectors:
|| < |X
| 1|
(169)
Therefore
N M
(170)
The norm of Jacobian of the fixed point iteration is bounded
|| la < B x 12 < 2BNM2c c.
(171)
The separation of pattern æ; from data X = (æ),.... (NN) is
A min (x) a; x,) x x
max x jJ
xj.
(172)
We need the separation A of ē dE (1 \)ar from the data:
Å min (a x, x= x2)
(173)
Jjj
We compute a lower bound on A. Using the Cauchy-Schwarz Schwarz inequality, we obtain for 1 < < N:
a æ3 - a! æz
< | æill ||>
< || - æ;| M
(174)
We have the lower bound
Å 2 min
((x) x;;
| xill M) (w) æj + || æ;1 M))
(175)
- 2 o
xill M
min (o) x; x xx) = D 2 |
xx|| M
foft
Since
11
æill
| (1 \)=; - xill
(176)
< A ||E - x;ll + (1- - A) || xill
maxflle - xill. ||= - x;11],
we have
Á 2 A, - 2 max || - xill. - xi M.
(177)
For the softmax component i we have:
1
[softmax(3 x"
(178)
1 1 Ejet exp(3 (TTx, - (Txx))
1 + J exp(- (A, - 2 maxill - rcill.103 - 2; M))
I + (N- - 1) exeep((-B (A: 2 maxile - æill, | - xill} M))
(N - 1) exp B (A, - 2 maxille - x, ll. || - xill) M))
= 1 1 + (N 1) expppp 3 (A, - 2 max(le - a:ll. 1|a7 - mell)) M))
2 1 - - (N-1) cxcxp(->i) 3 (A, - 2 max(lle - 2ill. || - 2xll M))
1 c.
31

---

Therefore
= -N exp(e (A: max Bi|1,1|a2 2;113 M))
(179)
We can bound the spectral norm of the Jacobian, which upper bounds the Lipschitz constant:
|| < 2 N M (N 1) expex 3 (A; max æx,1, ||= æx,1} M))
(180)
For contraction mapping we require
|| < 1
(181)
which can be ensured by
2 3 2 (N - cxp( (4: maxflle
xill. ||,
xill M))
< 1. (182)
Solving this inequality for A, gives
A, > 2 max [ - axil. || - asll) M + 3 (2
(183)
In environment around æ. in which Eq. (183) holds, f is contraction mapping and every point converges under the iteration f to xy when the iteration stays in the environment. After every iteration the mapped point f(E) is closer to the fixed point x than the original point 2;;
(I)(E) - =xill < |J IE
xill |E
x
(184)
Using (E) 1
< 1|
ll l1e
z11 < || 2l llE s(E)ll + 1|J 1l, lIf(E) æt||, (185)
we obtain
| l2
(E)
xill
<
llE
f(E)ll
(186)
1
| ll2
For large A; the iteration is close to the fixed point even after one update. This has been confirmed in several experiments.
A.1.5.4 Metastable States: Fixed Points Near Mean of Similar Patterns. The proof concept the same as for single pattern but now for the arithmetic mean similar patterns.
Bound on the Jacobian.
The Jacobian the fixed point iteration
J 8 X (diag(p) pp"" x
XJ,X².
(187)
we consider p. as the probability of selecting the vector æi, then we can define expectations as -N Ep]f(=)] = Ein (xx) ). In this setting the matrix
X (diag(p) pp") X
(188)
is the covariance matrix of data X when its vectors selected according to the probability p:
X (diag(p) - -ppp) x = xdiag(p) XT"
Xpp' x
(189)
N
N
N
r
=
Σ
Ps T; x..
ΣpL 1=1
Pi æs
Σ 2;
(190)
1=1
Ex x=1
Ep[x]]
Ep (x)"
Var
(191)
therefore we have
J = 3 |ar,
(192)
We now elaborate more on this interpretation variance. Specifically the singular values of J (or in other words: the covariance) should be reasonably small. The singular values are the key to ensure convergence of the iteration Eq. (57). Next present some thoughts.
32

---

1. It's clear that the largest eigenvalue of the covariance matrix (equal to the largest singu- lar value) is the variance in the direction of the eigenvector associated with the largest eigenvalue.
2. Furthermore the variance goes to zero as one Pt goes to one, since only one pattern is chosen and there is no variance.
3. The variance reasonable small if all patterns are chosen with equal probability.
4. The variance is small if few similar patterns are chosen with high probability. If the patterns are sufficient similar, then the spectral norm of the covariance matrix smaller than one.
The first three issues have already been adressed. Now we focus the last one in greater detail. We assume that the first patterns are much more probable (and similar to one another) than the other patterns. Therefore, we define:
M max
|
(193)
7
Σ pi &
(194)
i=++1
1-7 = Σ Pi 2 c,
(195)
i=1
P. =
Pi
< (1((1-))
(196)
1-7
Σ Pr = 1,
(197)
1=1
(198)
1
1=1 |
Mmnax
max 1614
m.
(199)
M is upper bound on the Euclidean norm of the patterns, which are vectors. is upper bound on the probability y of not choosing one of the first / patterns, while 1 - is a lower bound the probability (1 - 7) of choosing
of the first patterns. m. the arithmetic mean (the center) of the first / patterns. Mmax is the maximal distance of the patterns to the center m. P is the probability p normalized for the first / patterns.
The variance of the first patterns is
1
Varg[æ1ul]
Σ t=1
Di 2; xz
Σne
is wi
Σ
pi
w;
(200)
T
Σ peise
Σ
pi
x
Lemma A8. With the definitions in Eq. (193) to Eq. (200), the following bounds on the norm [J]] of the Jacobian of the fixed point iteration hold. The b-bound for [|J]|| is
|J & B ((1 - -7) maax + 22 7) M²)
(201)
and the c-bound for []]| is:
|1 < 3 (m maax + 2 e) M2)
(202)
33

---

Proof. The variance Varp[z1a] can be expressed as:
T
(1 (1 Varş|æinl
=
Σ
Pi
xs
1
Pi Vi
2
Σ i=1
Ps 2i
(203)
1
-
1
i=1
i=1
1
T
1
T
Σ 1=1
Σ
Σ
Σ
Σ
Ps Ty T.
-
Pi Di
Pi Ls
Ps Zi
Pi Di
1-1
1-7
1=1
1=1
E/ Pr
1
T
T
+
Σ
Pi xi
Σ
Pi xi
=
Σ
Pi
Li 22
1
Σ Pi xi
Σ
Pi C2
(1 7)2
1=1
i=1
i=1
T
T
Σ
Pi vi x²!
Σ Pi æi
Σ
Pi Li
+
(1 1
)
1
Σ Pi xi
Σ
Pi 3i
i=1
1=1
1=1
i=1
T
T
Σ Ps Tj T
Σ Pi xi
Σ
γ
Σ
Σ
Ps Lz
Ps Ts
1 1-7
i=
xm
Therefore, we have
1
T
Σ i=
Ps T. 2.
Σ Pi xi
E
ps Iss
(204)
1
T
(1 77) Varş(araa)
7
Σ Pi 0s
Σ
Pi 20
7
We now can reformulate the Jacobian J:
J= 3
Σ Ps D
+
Σ
Pi T!
(205)
i=1+1
N Σ
N
Σ
Σ
Σ
Pr Di +
Pi T.
Pi x; +
Pt Di
1=|+1
i=1+1
1
T
= 8
Σ
Pi Bi 2.
Σ
Pi Bi
Σ
Pi 3;;
i=1
N
N
T
Σ
Pi xc x.
Σ
Pi Xi
Σ
Pt Zz
<-/+1
iii+1
im|+1
N
T
N
T
Σ Pi
Σ
Σ
Σ
Pi ai
Ps ai
Pi
1=|-1
iil+1
i=1
T
8
(1-1) Varplæial
+
pi xi
Σ
Pi x,
1-7 7
N
N
N
T
Pi xg x
Σ
Pi Ci
Σ
Pi wi
1m1+1
imi+1
im++l
N
T
N
1
Σ Pi Di
Σ
Σ
Σ
Pi Di
Ps a;
pi oi
++1
34

---

The spectral norm of an outer product of two vectors is the product of the Euclidean norms of the vectors:
7 l12 v Xmaxx ab²)
||a]| Amax((b') (bb²) = ||a|| ||]]|
(206)
since bb" has eigenvector b/ ||b]] with eigenvalue ||b]| 2 and otherwise eigenvalues.
We now bound the norms of some matrices and vectors:
Pt
Pi ||ا
< (1-7) M
(207)
N
N
Σ
P: Z;
Σ
Pi
|
$ y YM,
(208)
1=++1
+++1
Σ Ps 3 x
Σ
x 11
Σ Ds |0 < Σ Pt M 7 M². (209)
Ps
In order to bound the variance of the first patterns, we compute the vector that minimizes
f(a) Σ ps Cplla all²
Σ pi(at a)² (x: a)
(210)
The solution
0s(a)
2 Σ
pi(a x.) = 0
(211)
da
1=1
is
N
a
Σ
p:
(212)
The Hessian of f is positive definite since
8 f(a)
ps I
21
(213)
da
and f is convex function. Hence, the mean
N Pi x2
(214)
minimizes Σ pillx, al2. Therefore, we have prlla 211 pilla, mull2 (1 - 7) m mmax
(215)
We now bound the variance on the first patterns:
(1 (17)) /Vars|oaalll
<
(x:: - x)) (x; x;/²
(216)
1=1
Pollac
2012
Pi [x m=/
< (1 7) m2
35

---

We obtain for the spectral norm of J:
|J]| < 3 ((1 7) |Vars[[zul]]
(217)
+
?
Σ Pt æi
Σ
Pi æi
1-?
N
+
Σ Pi Ds x
+
Σ
Pt Zi
Σ
Pr 2i
i=/+1
2
1
N
1
T
Σ
Σ Ps Vi
Σ pi ai
Σ
+
pi æz
Pi 0z
1=/+1
i=|+1
2
< 3 ((1 -)) /Var](=1=]11 112 + + (1-7) M2 + y M + 72 122
7 -7) M
+ + 7) M2)
3 ((1 -7) ||Varp[=1.]]l2
7 (2 -7) M²)
Combining the previous two estimates immediately leads Eq. (201).
The function h(x) = x2 - x) has the derivative (zx = 4(1 - x). Therefore, h(x) is monotone increasing for 1. For 0 < 7 < E < 1, we can immediately deduce that 72 7) < <2(2 E). Since e is larger than we obtain the following e-bound for ||J][2
|J]|| < 3 (maax + 2 e) M
(218)
We revisit the bound on (1 7) Varş(z1:l The trace Ed is the sum of the eigenvalues The spectral norm is equal to the largest eigenvalue e1, that is, the largest singular value. We obtain:
[arp[ TI Σ Pá (xt
x) (x. 8)")
(219)
k=
Σ ps Tr ((=; x) (x: 7)))
Σ
Ck
1=1
k=
d
Σ pillo - =x112 - Σ
k=2
Therefore, the tightness of the bound depends eigenvalues which not the largest. That is variations which are not along the strongest variation weaken the bound.
Proof of fixed point by Banach Fixed Point Theorem.
36

---

Without restricting the generality, we assumee that the first I patterns are much more probable (and similar to one another) than the other patterns. Therefore, we define:
M
max ||0
(220)
N
7
Σ
Pi E 6,
(221)
imb+1
1-7
Σ Pi 2 E,
(222)
iml
Dr
Pi
& pc((1 -),,
(223)
1-7
Σ Pr 1,
(224)
mmp
Σ
Di
(225)
i=1
Mmax
max 1
||
m
(226)
M is an upper bound on the Euclidean norm of the patterns, which are vectors. e is an upper bound on the probability 7 of not choosing one of the first / patterns, while 1 is a lower bound the probability (1 -7) of choosing one of the first patterns. mæ is the arithmetic mean (the center) of the first l patterns. mmax is the maximal distance of the patterns to the center my P is the probability p normalized for the first / patterns.
Mapped vectors stay in compact environment. We show that if mz is sufficient dissimilar to other zj with I < j then there is an compact environment of m2 (a sphere) where the fixed point iteration maps this environment into itself. The idea of the proof is define a sphere around m for which the points from the sphere are mapped by I into the sphere.
We first need following lemma which bounds the distance l|m. - f(E) of & which is close to m.-
Lemma A9. For a query & and data X = (N),...,,N), we define
< c
min (5" mz - 5²xrr)) 5" mm زز4L
max 5" æj.
(227)
The following holds:
m
f(E)ll & Minax 2 M & Mmaax + 2 M
(228)
where
M = max ||=:||
(229)
= (N () -x)xxx---1
(230)
Proof. Let s = arg maxj.igt 5 æj. therefore 5" e'mm= = Et=n 5" a; < 1 Et= Exx. = gxxx..
For softmax components j with j we have
exp( (ET mj x.))
doftmax(8x"Te)
En exp(3 (g xx xTxx))) & exp(= Bc) N
(231)
since 5f xr --x--5 5 æ; 2 5 m. - 5" a, for each j with I < j. therefore &Tx., ax - -5 a; 2 c
The iteration f can be written as
N
f(E) = Xsoftmax( (extmaxx3xxxg
=
Σ
xj Softmax(3x"!)
(232)
1=1
37

---

We p. (aatmmaxxxXXx_ee therefore El= Pi = y 1 and Σ Ei=l+1 Pi y E Therefore
Pj 23
Pj 7
(mx xz}}
(233)
7
j=1
Σ j=1,k=1
Pj
Pk
(mz Bzy) (mz xKa)
1 Y
Pj
(lmm æ351² + ||mm xxl1 -1123
xx 111
7
j=l,k=1
Σ
Pj
miz - -xi11²
1
Pj
Pk
1 Ix.1?
?
2 1=1,
- y
7
j=l
<
Pj
m
- =0i11² < mmax
5=1
follows that
Pj ?
mm
Mmax
(234)
We now can bound |mm
f(E)]l:
N Σ
m=
f(E)l
m2
Pj Fj
(235)
j=1
Σ
Σ
mx
Pj Bj
Pj aj
f=1
j=1+1
NN
m2
Pj
+
7
Σ Pj T
Σ
Pj Dj
j=l+1
mx
Σ
Pj L
+ 7
Σ Pj B
+
Pj Zz
7
1=1
j=1
j=1+1
m
Σ
1-9 I
Pj
+ 1 1-7 j=1
Σ
Pj M
Σ
Ps M
1=1
j=|+1
1
<
Ma
Σ
Pj 3
+ 2 M
j=1
Mmaxx
2- M < mmax + 2
where we applied Eq. (233) in the penultimate inequality. This is the statement of the lemma.
The separation of the center (the arithmetic mean) my of the first I from data X (21 ... σ.) is A defined as
Am min (m m
m m mz
max m æz.
(236)
j.KJ
38

---

The center is separated from the other data æ, with I < jf0 < Am. By the same arguments in Eq. (140), Am can also be expressed as
Am min Ju(c 2 (Imell? ||2y|1 + ||me -x,1²)
1
(237)
= 2 mz 112
||>51| 1| - 23 2351²²
max ر
2
For |mal] || || we have Am 1/2 min |m x:yl
Next we define the sphere where we want to apply Banach fixed point theorem. Definition (Sphere Sm). The sphere S.n. defined as
Sm = { 1I - mm <
(238)
Mmaxx
Lemma A10. With & given, if the assumptions
Al: & is inside sphere: & E Sm.
A2: the center ma is well separated from other data z.j with 1. < j:
2 M
1
1 m muax
In
(239)
B Mmmax
3
233 (N 1) M max (mmaxx: 2 M)
A3: the distance mmax of similar patterns the center sufficient small:
B m
(240)
hold, then f(E) Sm. Therefore, under conditions (A2) and (A3), f is mapping from Sm into S...
Proof. We need the separation Åm g from the rest of the data, which is the last data points X = (II+1...., DN).
Am min (s" mz - 5" 5²ax)) زJ3
(241)
Using the Cauchy-Schwarz inequality, obtain for 1 E N: |g - m xz,l & ||E - mx ||= & ||E - ma M
(242)
We have the lower bound
Â
min زز3ز
((m?
m
||5 mzll M) (m + || - mæll ([)
(243)
2 |
mæ M + min
(m mx - m= = Am - ||e m M
M
Am
2
M-ax
where we used the assumption (AI) of the lemma.
From the proof in Lemma A9 have
P 2 - -N- exp(- 3 Am)) = -,
(244)
1=1
N
Pt & (N - expl- 3 Am) = E.
(245)
1=++1
Lemma A9 states that
m
f(E)ll
Mmax
(246)
2N 1) exp(- B Am)) M
Mmax
M
Mmnxx
2N - exp(- (Am 2
)) M
B mmax
39

---

Therefore, have
(-B (Bm 2 mmaax
M
)
mz f(E)ll < maax
(NV - exp
M
(247)
2 M
Mmax + 2 (NV -1) exp 3
3 Mmax
1 In 3
1 m
M
M
2 (N - 1) M max [mmax 2 &M}
B Menax
mm
maxx
+ (N - 1) 23 (N 1) M max (max 2 M
B m
< Mmax
+
B mmax
B Mmax
where used assumption (A2) of the lemma. Therefore, f(E) is mapping from the sphere Sm into the sphere Sp..
Mmaxx
max [s
m
(248)
max gg
1/1 32
(249)
j=1
max 1sig!
1/1 > (zs Fz}
(250)
max
[ - 2.51
(251)
1EtjEL
max 1616
max
[x]]
(252)
2M
(253)
Contracctinn mapping.
For applying Banach fixed point theorem we need to show that contraction in the compact environment S,.
Lemma A11. Assume that
Al:
2 M
1 ln
1 B m 23 (N 1) M max (mmax 2 MM
Am
(254)
3 Mmax
and
A2:
3 m max
E 1
(255)
then f is contraction mapping in Sm.
Proof. The version of the mean value theorem Lemma A32 states for the symmetric J So J(XE --)mm)) dA:
f(E) = f(mx) + T (E - -mx)
(256)
In complete analogy to Lemma A6, we get:
(I((E) (mm))l
< | ||g mæ
(257)
40

---

We define & = xg (1 2 for some À [0, 1]. We need the separation Am of from the rest of the data, which is the last N data points (2144....,,2N)
Åm min وdاd
( m2 E" 2z))
(258)
From the proof in Lemma A9 have
č = (N- 1) exp(- 33 Am))
(2599
Pi(E) 2 (N-1) -1) exp(- B Am) 2,
(260)
N
Σ
(E( & (N -) exp(- 3 Am) = E.
(261)
i=#1
We first compute upper bound on č. Using the Cauchy- inequality, obtain for 1 + 1 <
j & N:
ETa m
[ mm
||a
j mx
M.
(262)
We have the lower bound Ām:
Åm 2 min
( (m mm
- I1E m- M)
(mit
+ || m
M)
(263)
-2
{ mx
M + min
(m T mx
x= Am
2 E
m2
M
2 Am
2 15
mx M.
where we used
{ m2
= A|E5 - mmzl
< ||5 mall- I|
We obtain the upper bound on č:
E (N 1) exp (- 3 (Am
m M))
(264)
< (N 1) exp (-8 Am
2 M
3 M
where we used that in the sphere S, holds:
| mm <
(265)
B Mmax
therefore
2 M
||E m
M
&
(266)
Myax
Next we compute lower bound on ē and to this end start with the upper bound on Ám using the same arguments as Eq. (158) in combination with Eq. (266).
Åm > min jجاز
|| mm M)
(m a. - || .mx M))
(267)
= 2 j m2
M + min (m ma m Am + 2 E mz M j.2y
2 Am
+ ||g
m M
where we used
j mm
m
< ||E mxxl ||. We obtain the lower bound on AllE m
ē 2 (N 1) exp (-8 Am
2 M
(268)
3 M.nax
where we used that in the sphere S, holds:
||g mm <
(269)
B Mmax
41

---

therefore
M Mmax
2 mx M <
(270)
From Lemma
A8 have
J(E) 1
< B mixx
+ (2
E) M²)
(271)
3 (miax
+ 24 M e² M²)
(N (I exp (-8 A
2 M
3 mmax
4 M2
B Mrmax
2 (N - 1)² exp (- 2 Am
2 M
M
3 mmax)
The bound Eq. (271) holds for the mean J too, since it averages over (E):
| < B mmax + (N 1) exp (-3 Am
2 M
4 M
(272)
3 Mmaxx
2 2N - 1)2 exp
22 Am +
2 M
M
B
Maaxx
The assumption of the lemma
2 M
B m max
Am
In
(273)
B Mmax
B
23 (N
1) M max maxx 2 M
Therefore, we have
2 M
1 In
B m
Am
(274)
3 Mmax
2 1) M max m MM}
Therefore, the spectral norm ||J" can be bounded by:
|J
(275)
3 m
8 m maax + (N cxp -
In
B
2 (N - 1) M max { Mimax. 2 M
M
1 - 2 2N ON-NN1 1)2 exp
- 2
Am +
M
B Mmax
= 3 mnnax 3mmaxx + (N--) 1)) exp
1
m2ax
In
2 (N - 1) M max (Mmax: 2 M)
M
2 - 2N -12 exp
2
Am + m
M²
1 B m
= B mmmax + (N Il)
4 M
2 (N - 1) M max max 2 M
2 (N -122 exp (-28 Am
2 AM
M²
mmmax
B m max
Bm
2 M
max (Miaxx
M)
2 M
32 (N--N) -12 exp 2 Am
M
mmax
< 3m3 max
+ 1 B m
32 (N
1)2 exp 2
Am +
2 M
M
B Mmmax
2 M
32 (N- - 1)2 exp
2 Am
212 <1.
B Mmax
42

---

For the last but one inequality used 2M & max mmxx 2M) Therefore, f a contraction mapping in Sm.
Banach Fixed Point Theorem. Now have all ingredients apply Banach fixed point theorem. Lemma A12, Assume that
Al:
2 M
1 In
1 B m
Am
(276)
B Mmmx
3
2 3 (N - 1) M max MMmax 2 M3
and
A2:
8 max
< 1
(277)
then f has a fixed point in Sm-
Proof. We use Banach fixed point theorem: Lemma A1 says that f maps from the compact set S.n. into the same compact set Sm. Lemma A1l says that f is a contraction mapping in S..
Contraction mapping with a fixed point.
We assume that the first patterss much more probable (and similar another) than the other patterns. Therefore, we define:
= max
|
(278)
7
Σ Pt &
(279)
i=111
1 1-7 = Σ
2 c,
(280)
i=1
P.
= pi
< p c),
(281)
1-7
Σ p. 1,
(282)
1=1
Mag =
Σ
0i
(283)
1=1
Mlaa
max Igi
m
(284)
M is an upper bound on the Euclidean norm of the patterns, which are vectors. e an upper bound on the probability 7 of not choosing one of the first / patterns, while 1 is a lower bound the probability (1 (1-7) of choosing one of the first patterns. mz is the arithmetic mean (the center) of the first / patterns. Mmax is the maximal distance of the patterns to the center my P is the probability p normalized for the first patterns.
The variance of the first patterns is
Varş[wia]]
Σ
ps C; x
Σ
Pi æ;
Σ
pi
3;
(285)
i=1
i=
T
Σ
Dj
2,,
1=1
1=1
1=1
43

---

We have shown that fixed point exists. We want to know how fast the iteration converges to the fixed point. Let m be the fixed point of the iteration f in the sphere Sm. Using the mean value theorem Lemma A32, we have with J .u JAE (1 - ))m dA:
(I((E)
m ll = ( - f(m))l
< || ll2 l|I - mi
(286)
According to Lemma A8 the following bounds the norm |Jl of the Jacobian of the fixed point iteration hold. The y-bbuud for ||]| is
|| < ((1 -7) miax + 22 - (3)0-maM M²)
(287)
while the e-bound for |J]|| is:
|J]| & 3 (m
2 (2 c) M2)
(288)
From the last condition we require for a contraction mapping:
B mmmx 1.
(289)
We want see how large iss. The separation of center my from data X- (x1+1
[NN) is
Am
min Jd33
(m m m. m² m m
max m 2.
(290)
jd<j
We need the separation Am of t= Xx (1 A)m from the data.
min j.kj
(* mz
x= xxxx) x,)
(291)
We compute lower bound on Am. Using the Cauchy-Schwarz Schwarz inequality, obtain for 1 & < N:
m² & || - -maell ||ر < || m M
(292)
We have the lower bound
Åm 2 min
(m mx
||
m M) (m + | - -mall M))
(293)
- 2 x - mm
M + min (m" m m Am 2 1 - m M jdرز
Since
| mz
| + + N)m= mxll
(294)
< IlE mm + (1 2) m mæ
maxflle- mall. l|m mzll].
we have
Åm Am max(lle mz Melll.1me lm= m= M
(295)
= -N1))expp B (Am 2 max(lls - -m Imm m 1 M))
(296)
1. PROPERTIES OF FIXED POINTS NEAR STORED PATTERN
In Subsection A.1.5.3 many stable states that are fixed points near the stored patterns are considered. We now consider this case. In the fist subsection we investigate the storage capacity if all patterns are sufficiently separated so that metastable states not appear. the next subsection we look into the updates required and error when retrieving the stored patterns. For metastable states can do the same analyses each metastable state is treated as one state like one pattern.
We see trade-off that is known from classical Hopfield networks and for modern Hopfield networks. Small separation A, of the pattern Φ; from the other patterns gives high storage capacity. However the convergence speed is lower and the retrieval error higher. In contrast, large separation A; of the pattern æ; from the other pattern allows the retrieval of patterns with one update step and exponentially low emror.
44

---

A.1.6.1 Exponentially Many Patterns can be Stored. From Subsection A.1.5.3 need some definitions. We assume to have N patterns, the separation of pattern æ; from the other patterns {o) 2, ..... Nv is A. defined as
A min (a) xx{²,) x. x; jj
max o æj.
(297)
JJ
The pattern is separated from the other data if D.. The separation A can also be expressed
A min (|02:11 - -|,,,11 + ||.; - 27,11 Ji
(298)
1
x 1|
1
max ||æح|| - ||=; - æ; 2z1²). jjjt
= 2
2
For ||r = | we have A, = 1/2 min jiate |a 2.yl .1... The sphere S, with center æ; is defined
as
S EElle xill & NN M
(299)
The maximal length of pattern is M max; ||=;||-
We next define what we mean with storing and retrieving a pattern.
Definition (Pattern Stored and Retrieved). We assume that around every pattern E; a sphere S₁ given. We say æ; is stored if there is single fixed point x; E S; to which all points & E S; converge, and S; ns, = 0 for i j. We say æ; retrieved for a given 6 if iteration (update rule) Eq. (92) gives point ã; that is at least c-close to the single fixed point n S, The retrieval error is ||;; æill.
The sphere S, around pattern æ, can be any sphere and do not have the specific sphere defined in Def. 3.
For query & E S, to converge to a fixed point of E S₁ we required for the application of Banach fixed point theorem and for ensuring contraction mapping the following inequality:
2 N In (2 N)
A
(300)
This is the assumption in Lemma A7 to ensure a fixed point in sphere S, Since replacing (N - 1)N by 22 gives
2 1
>
B
+ In (2
(301)
N
BN
the inequality follows from following master inequality
A
(n
(302)
N
3
If we assume that S;NS, with i j, then the triangle inequality with point from the intersection gives
2
| - æ3l1 <
(303)
BN
M
Therefore, have using the Cauchy- Schwwa-- inequality:
2
2
A c x④)
| ||= æ, M
(304)
IN
M
N
The last inequality is a contraction to Eq. (302) if we assume that
1 < 2 (N - 1) N 8 M² With this assumption. the spheres S; and Sy do intersect. Therefore, each o; has its separate fixed point in S, We define
(305)
A Amiu min A
(306)
I8i
45

---

to obtain the master inequality
2 BN
A min
2
+
In (2 B
(307)
Patterns on sphere.
For simplicity and accordance with the results the classical Hopfield network, we assume all patterns being on sphere with radius M:
|
M
(308)
Under assumption Eq. (305) we have only to show that the master inequality Eq. (307) is fulfilled for each æ;; to have a separate fixed point near each 2;:-
We defined oij the angle between e; and z.j. The minimal angle Ouiin between data points is
Omin min Aij
(309)
IEKjEN
On the sphere with radius M we have
Amin
min LEKsEN
22 cos(ar;)) = 21 cos(amin)),
(310)
therefore it sufficient show the master inequality on the sphere:
2 - coss(mmii)
B N 3 In 12
(311)
Under assumption Eq. (305) have only to show that the master inequality Eq. (307) is fulfilled for Amin. We consider patterns on the sphere, therefore the master inequality Eq. (307) becomes Eq. (311). First we show results when pattern positions on the sphere are constructed and Amin is ensured. Then we move on to random patterns on sphere, where A becomes a random variable.
Storage capacity for patterns placed on the sphere.
Next theorem says how many patterns we can stored (fixed point with attraction basin near pattern) if we are allowed to place them on the sphere.
Theorem A3 (Storage Capacity (M=2): Placed Patterns). We assume B 1 and patterns the sphere with radius M. If M 2 and the dimension d of the space is d > or if M = 1.7 and the dimension d of the space is d 2 50, then the number of patterns N that can be stored (fixd point with attraction basin near pattern) is at least
N 1d
(312)
Proof. For random patterns on the sphere, we have to show that the master inequality Eq. (311) holds:
1 In (2 (2 N2 M²)
M cos(amin))
(313)
N
now place the patterns equidistant on the sphere where the pattern are separated by an angle amin
Vi min Orj
Ommin
(314)
In d-dimensional space we can place
d-1
2m O'min
N
(315)
points on the sphere. In a spherical coordinate system pattern differs from its most closest patterns by an angle amin and there are angles. Solving for amin gives
2x
Ommin
Ni/(d-1)
(316)
46

---

The number of patterns that can be stored is determined by the largest N that fulfils
M (1 (1- cos
(
(NI/
2t
2 1
In (2 BM)
(317)
BN
B
We set N = 22(d-1) 1) and obtain for Eq. (317):
2 (1
cos
AT 2))
1)
2
+
3 (2
+ 1 3 4 1)
(318)
This incquality is equivalent to
M Z 22(0-1)-1 + In (2 + 4 - 1)
(319)
The last inequality can be fulfilled with M K avdvvaai and proper K. For 1, 1, = and K the inequality is fulfilled. The left hand side minus the right hand side is 4(d 1) 1/22(d-1)-1 In(8(d 1)) - 4(d - 1) In 2. Its derivative with respect to d is strict positive. Therefore, the inequality holds for d 4.
For B = 1, d = 50 and K = 1.7 the inequality is fulfilled. The left hand side minus the right hand side is 2.89(d - 1) 1/22(d-1)-1 - (idd-1) 1)) 4(d 1) In 2. Its derivative with respect to d strict positive. Therefore, the inequality holds for 2 50.
If we want to store considerably more patterns, then we have to increase the length of the vectors or the dimension the space where the vectors live. The next theorem shows results for number of patterns N with N 23(d-1).
Theorem A4 (Storage Capacity (M=5): Placed Patterns). We assume the sphere with radius M. If M 5 and the dimension d of the space is d > or if M = 4Vd - 1 and the dimension d of the space is d 2 13, then the number of patterns N that can be stored (fixed point with attraction basin near pattern) is at least
1 and patterns on
N = 23
(320)
Proof. We set N -23(d-1) and obtain for Eq. (317):
M (1 (1-com cos T (7) 2
2
+ In (2 +
1
1 6 (d (d-1)
(321)
1)
This inequality is equivalent to
3 2 (1 (1-
V2
Z 23(d-1)-1 In (2 + 6 (d- 1n2n2
(322)
2
The last inequality can be fulfilled with M Kvd- and proper For 1, d= 13 and
K = 4 the inequality is fulfilled. The left hand side minus the right hand side is 4.686292 1) 1/23(d-1)-1 ln(32 - 1)) 6(d - 1) In 2. Its derivative with respect to d is strict positive. Therefore, the inequality holds for 2 13.
For 1, == = 3 and K = 5 the inequality is fulfilled. The left hand side minus the right hand side is (d32233 1) 1 1/23(d-1)-1 - In(50(d - 1)) 6(d 1) In 2. Its derivative with respect to d is strict positive. Therefore, the inequality holds for
Storage capacity for random patterns on the sphere.
47

---

Next investigate random points the sphere. Under assumption Eq. (305) we have show that the master inequality Eq. (311) is fulfilled for Amin. where now Omin is now a random variable. We use results the distribution of the minimal angles between random patterns according to Cai et al. (2013) and Brauchart et al. (2018). Theorem 2 in Cai et al. (2013) gives the distribution of the minimal angle for random patterns the unit sphere. Proposition 3.5 in Brauchart et al. (2018) gives lower bound on the probability of the minimal angle being larger than given constant. We require this proposition to derive the probability of pattern having minimal angle Omin- Proposition 3.6 in Brauchart et al. (2018) gives the expectation of the minimal angle.
sphere
We will prove high probability bounds for the expected storage capacity. We need the following tail-bound on Ommnn (the minimal angle of random patterns on a sphere):
Lemma A A13 (Braachartt et al., 2018)). Let be the dimension of the pattern space,
T((d + 1)/2)
Rd = d dvT T(d/2)
(323)
and 8 > 0 such that Nd-1 5(d-1) < 1. Then
Pr(N Omin
8)
Kd-1 8d-1
(324)
Proof. The statement of the lemma is Eq. (3-6) from Proposition 3.5 in Brauchart al. (2018).
Next we derive upper and lower bounds on the constant Ka since we require them later for proving storage capacity bounds.
Lemma A14. For Ka defined in Eq. (323) we have the following bounds for every d 2 1:
1
exp(1/12)
cxp(1/6) Vend & Rd
(325)
V2 12 d
Proof. We use for a 0 the following bound related to Stirling's approximation formula for the gamma function, c.f. (Olver et al., 2010, (5.6.1)):
1 < ((x) (2 T) + * exp(x) < exp
(326)
12 σ
Using Stirling's formula Eq. (326), we upper bound Rd:
r((d + 1)/2)
exp
6(d+1)
exp (-
d+1
2
d+1
Ka d V r(d/2)
(327)
d VT
(4)
exp
1 d d
((d+T)
1
(1+
1
d
exp
(1)
exp
2 क Vd.
For the first inequality, we applied Eq. (326), while for the second we used (1 + 1)² for d Next, we lower bound Ki by again applying Stirling's formula Eq. (326):
1 I((d+1)/2)
d+1 exp (- +1
( 1
Rnd = d I(d/2)
(328)
d V exp (d) exp (-9) o)) (4)
1
d V exp
exp (1) Vend
(
where the last inequality holds because of monotonicity of (1 + 1)d and using the fact that for d = takes on the value 2.
We require bound on to bound the master inequality Eq. (311).
48

---

Lemma A15. For 0 & & i the function cos be upper bounded by:
x²²
cos(x:) < 1
(329)
Proof. We use the infinite product representation of cos, c.f. (Olver et al., 2010, (4.22.2)):
4 x
cos(1)
II n=
1
(330)
(2n
1)2 π
Since it holds that
4 x22
$ 1
(331)
(2n 1)2 x²
for |x|| < π and n 2 2, we can get the following upper bound on Eq. (330):
(os(2)) <
II
(2n - 1)
4 xx
=
(1
4 x
x²
(1
9 π
x
(332)
n=1
40 x22
16 16
40 x2
16 x?
+
+
9 22
9 9
9 9
9 π
24 x22
x
1
1
The last but one inequality uses & n, which implies x/N & 1. Thus Eq. (329) is proven.
Exponential storage capacity: the base as a function of the parameter B, the radius of the sphere M, the probability p, and the dimension d of the space.
We express the number N of stored patterns by an exponential function with base exponent linear in d. We derive constraints he base as function of 3, the radius of the sphere M, the probability p that all patterns can be stored, and the dimension d of the space. With B >
and an
K O, and d 2 2 (to ensure sphere), the following theorem gives main result.
Theorem AS (Storage Capacity (Main): Random Patterns). We assume failure probability 0 < & 1 and randomly chosen patterns on the sphere with radius M == K vd T. We define
a = d-1 (1 + ln K2 p (d 1))) b = K2
5
= Wolexp(a + In(b))
(333)
where Wo the upper branch of the Lambert W function (Olver et al., 2010, (4.13)) and ensure
+
(334)
/P
Then with probability 1 p. the number of random patterns that can be stored is
N 2 vp c
(335)
Therefore it is proven for 3.1546 with 8 1, K 3, d = 20 and p 0.001 (a + In(b) 1.27)
and proven for e 2 1.3718 with 3 = K = 1, d = 75, and p = 0.001 (a + In(b) < -0.94).
Proof. We consider the probability that the master inequality Eq. (311) is fulfilled:
Pr M1 cos((amin)))
2 1
In (2 N2 B MP)
1 p. (336)
B N
3
49

---

Using Eq. (329), we have:
1
1
(omn)
2
Omn
(337)
Therefore, with probability 1 p the storage capacity largest N that fulfills
Pr 2
2 amin
2
+
1
In (2
2 1 - p. (2N228M))
N2
(338)
5
BN
B
This inequality equivalent
Pr N
Ommn
+
1 ln
2 p.
(339)
M
B N
We use Eq. (324) to obtain:
No
amin
V5Na-
M
BN
B
1
In
(2 (2
(340)
2
Rd-
d-1 N M- (d-1)
2
+
In
(2 322228M2))
2
B
N
B
For Eq. (339) to be fulfilled, it is sufficient that
114 - -P P 0. BN + + (0(229
Ed-1 d-1 N2 (d-111)
(341)
2
If we insert the assumption Eq. (334) of the theorem into Eq. (335), then we obtain N 2 2. We now apply the upper bound Ka-1/2 Ka-1 < from Eq. (325) and the upper bound
2N < from
4=1
N 2 to inequality Eq. (341). In the resulting inequality we insert N = vpc it is fulfilled with this special value of N and obtain:
to check whether
(1 1
d-1 5 pc
-
M (dd1)
+ In (2pc BM²)
(342)
3
3
Dividing by p. inserting M = K Kv - 1, and exponentiation of the left and right side by 7-T gives:
2
5 1
3 + In (2
- K2 (d x22(d (d-
< 0.
(343)
K2 1d
After some algebraic manipulation, this inequality can be written
a + c In(e) b < 0,
(344)
where we used
2 a: d d-1 (1 + ln K2 p (d 1))) b 2 K3
We determine the value of which makes the inequality Eq. (344) equal We solve a è In() b
(345)
for è:
à + è ln(e) - = 0
(346)
2 + In(e) b/ē
# + In(b) + In(é/)) b/è
* b/c + in(b/2) a + In(b)
+ b/é exp(b/e) = exp(a + In(b))
t b/c Wo(exp(a + In()))
* ė Wolexp(a In(b))
50

---

where Wo is the upper branch of the Lambert W function (see Def. A6). Hence, the solution is (347)
è Wo(exp(a + In(b))
The solution exist, since the Lambert function Wo(x) (Olver et al., 2010, (4.13) is defined for -1/e < a and we have < exp(a In(b).
Since è fulfills inequality Eq. (344) and therefore also Eq. (342), we have lower bound on the storage capacity N:
N 2 vpct..
(348)
Next we aim at lower bound on e which does not use the Lambert W function (Olver et al., 2010, (4.13)). Therefore, we upper bound (exexp(a + [b)) obtain a lower bound on e, therefore, also a lower bound on the storage capacity N. The lower bound is given in the next corollary.
Corollary A1. We assume a failure probability < p < and randomly chosen patterns on the sphere with radius M kvd 1. We define
2
a = d (1 + In K Idd- b ==
5
Using the omega constant = 0.36714322 we set
exp(a + In(b)) +1 b In
for a + In(b) < 0,
Q !2)
(349)
bmdb)
b (a + In(b))
for a + In(b) > 0
and ensure
e M
(350)
Then with probability 1 p, the number of random patterns that can be stored is
N 2 -
1=1
(351)
Examples are > 3.1444 for 3 1, 3, d 20 and p 0.001 (a In(b) 1.27) and 2 1.2585 for = 1 K = 1, d = 75, and = 0.001 (a + In(b) < -0944).
Proof. We lower bound the e defined Theorem A5. According to (Hoorfar & Hassani, 2008, Theorem 2.3) we have for any real and ::
eex((u) + 1 In(y)
Wo(exp(u)) & In
(352)
To upper bound Wo(x) for E [0, 1), we set
y 11) 1/Ω expst 1/ Insl = 1.76322.
(353)
where the Omega constant
Ω = (1=
dt
-1
1 0.56714329
(354)
(et
t)²
+ n²
See for these equations the special values of the Lambert W function in Lemma A31, We have the upper bound on Wo:
Wo(exp(u)) In (exp(u) + 1/22
In Ω exp(u) + 1
(355)
+ In(1/2)
Ω 22)
51

---

At the right hand side of interval [0, 1], we have 0 and exp(u) 1 and get:
Ω + --1 (1) 92 + 2)
in (1)
In Therefore, the bound is tight at the right hand side of of interval [0. 1], that is for exp(u) = 1, i.c. We have derived an bound for Wo(exp(u)) with exp(u) E (0, 1] or, equivalently, u |-o0, 0].
in (12) = Ω = Wo(1).
(356)
We obtain from Hoorfar & Hassani (2008, Corollary 2.6) the following bound on Wc(exp(a)) for
1 < exp(u), or, equivalently u.
Wo(exp(u)) <
u
(357)
A lower bound on è is obtained via the upper bounds Eq. (357) and Eq. (355) on Wo as Wo 0. We
set u = a + lnbb and obtain
In Q exp(a In(O1) +1) (1 22) (a In(b))
for + In(6) 0,
Wo(exp(a + In(b)))
<
(358)
In(b) 1nt
for In(b)
We insert this bound into Eq. (347), the solution for é, to obtain the statement of the theorem.
Exponential storage capacity: the dimension d of the space as a function of the parameter 3, the radius of the sphere M, and the probability p.
We express the number N of stored patterns by an exponential function with base 1 and an exponent linear in d. We derive constraints on the dimension d of the space as function of B, the radius of the sphere M, the probability p that all patterns can stored, and the base of the exponential storage capacity. The following theorem gives this result.
Theorem A6 (Storage Capacity (d computed): Random Patterns). We assume a failure probability
< p E 1 and randomly chosen patterns on the sphere with radius -vdd- I. We define
a = In(e)
K2D 1 + (2p K2)
3c
d [1 W( exp( exp(-b)) for + 0,
(359)
1 exp(-b)
for 0,
where W is the Lambert W function (Olver et al., 2010, (4.13)). For 0 <, the function W is the upper branch Wo and for a < 0 we use the lower branch W-1- 1. If we ensure that
< - exp(-b),
c
(360)
e
then with probability p. the number of random patterns that can stored
N 2
(361)
Proof. We consider the probability that the master inequality Eq. (311) is fulfilled:
Pr M22 cos(amin)))
2 1
+
In N2 3 Mr2)
p.
(362)
8 N
3
Using Eq. (329), we have:
1
cos(omin
2 a
(363)
5
Therefore, with probability 1- p the storage capacity largest N that fulfills
Pr
2 amin
2 1
+
In (2
N2 3 M2)
p.
(364)
N
B
52

---

This inequality is equivalent to
Pr N amin
N 2
(
2
1
ln
7)
(365)
M
8N
We use Eq. (324) to obtain:
Pr
N N
Ommin
N=
M
BN
2
B In (eNNgaNP))
1
(366)
2 Kd- 1
N M
1)
2
+
In
3N
B
For Eq. (365) to be fulfilled, is sufficient that
Kd-1
N (d-1)
BN + (2 SM (M
P PPEO 0.
(367)
2
If we insert the assumption Eq. (360) of the theorem into Eq. (361), then we obtain N 2.
We now
apply the upper bound Ka-1/2 < Kg-1 < from Eq. (325) and the upper bound
2
< 3 from
BN
N to inequality Eq. (367). In the resulting inequality we insert N vpc to check whether is fulfilled with this special value of N and obtain:
d=1 5 DC
M (d-1))
1
+
1
In (2pc BM?) <
(368)
3
3
Dividing by p. inserting M KVd II, I, and exponentiation of the left and right side by d gives:
2
c 1
(28c² a K2 (d (d-1)) < 0.
(369)
K2 (2 (d
3
This inequality Eq. (369) can be reformulated as:
+ In (2p3c d K² (d (d- (d 1) K2
< 0.
(370)
5c
Using
In(c)
K2 B
:= 1 1 In (2 K2)
a 2
c
(371)
we write inequality Eq. (370) as
indd-1 a (d - 1) + b < 0.
(372)
We determine the value of d which makes the inequality Eq. (372) equal to zero. We solve
In(d 1) a (d- 1) + 0.
(373)
for d
For a # we have
In(d 1) + a (d 1) + b = 0
(374)
+ a (d-1) 1) In(d-1) ( 1) --b
* (d - 1) expla (d - 1)) = exp(-
$ a (d 1) 1)exp(a (d -1)
exp(- bb)
* a (d - 1) = W(a exp(-b))
* d -1
W(a exp(-b)
4 d = 1 +
W(a exp( (ap(-b))
53

---

where W is the Lambert W function (see Def. A6). For > 0 have the upper branch Wo of the Lambert W function and for a < 0 we use the lower branch W-1 of the Lambert W function (Olver et al., 2010, (4.13)). We have ensure that -1/e & exx((-b) for solution to exist. For we have d = 1 + cxp(-b).
Hence, the solution is
d 1 1 W(aexp(-b)) a
(375)
Since d fulfills inequality Eq. (369) and therefore also Eq. (368), we have lower bound on the storage capacity N:
N Z VDc
(376)
Corollary A2. We assume failure probability 0 < p & and randomly chosen patterns on the sphere with radius M- K KVd- I. We define
a = In(e) K" B
== 1 + In 2 5c
1
d
+ a
(- In(- + +b
(377)
and ensure
2
1
c 2
< exp(-b), 0,
(378)
vp)
then with probability 1 - p. the number of random patterns that can stored is
N 2 V
(379)
Setting 3 K = 3, c and = 0.001 yields d < 24.
Proof. For < 0 the Eq. (359) from Theorem (A6) can be written as + W exp (-(- In(-n)nn + 1))
d + W
(380)
From Alzahrani & Salem (2018, Theorem 3.1) we get the following bound on W-1: (u + 1) < W-1(- exp(-u - 1)) < - (u + 1). c c-1
(381)
for u > 0. We apply Eq. (381) to Eq. (380) with u = an(-a) ( - 1.
Since 0 get
d In(-a)) +
(382)
a
Storage capacity for the expected minimal separation instead of the probability that all patterns can be stored. In contrast to the previous paragraph, we want to argue about the storage capacity for the expected minimal separation. Therefore, will use the following bound on the expectation of amin (minimal angle), which gives also bound on the expected of Amin (minimal separation):
Lemma A16 (Proposition 3.6 in Brauchart et al. (2018)). We have the following lower bound on the expectation of Ommin
((
d
E
N
Ormin
2(d-1) 1) I(d
االهه
r(1
d-1
[ + 3
CJ-1- (383)
The bound is valid for all N 2 2 and d > 2.
54

---

Let us start with some preliminary estimates. First of all we need some asymptoties for the constant Ca-1 in Eq. (383):
Lemma A17. The following estimate holds for d 2 2:
Cd 2 1 In(d +
(384)
d
Proof. The recursion formula for the Gamma function (Olver et al., 2010, (5.5.1)):
7(x + 1) = x ((x).
(385)
We use Eq. (325) and the fact that d 2 for d obtain:
Ca (2 (d)arrr(++ + ) (d+
(2 (a) (d (d+1)-&
1- > (d (d+
(386)
r(2 +
exp(-3 In(d 1))
1 d
In(d In(d+1) + 1)
where the last step we used the elementary inequality exp(x) 2 + x, which follows from the mean value theorem.
The next theorem states the number of stored patterns for the expected minimal separation.
Theorem A7 (Storage Capacity (expected separation): Random Patterns). We assume patterns on the sphere with radius M = K cd that are randomly chosen. Then for all values e 2 1frrr which
5 (d-1) - In(d 1)
1 (d 1)
2
d-1 In (2
+
3 (d - 1) k²)
(387)
BCT
holds, the number of stored patterns for the expected minimal separation is at least
=
(388)
The inequality Eq. (387) is e.g. fulfille with B = 1. K 3. c= and 2 17.
Proof. Instead of considering the probability that the master inequality Eq. (311) is fulfilled we now consider whether this inequality is fulfilled for the expected minimal distance. We consider the expectation of the minimal distance Amin'
E mia = 21 cos(Omii)) ())) = 22 ([cos((mma)))
(389)
For this expectation, the master inequality Eq. (311) becomes
2 E(coo((mmin))
+
3 In (2 M²)
(390)
B N
want to find the largest N that fulfills this inequality. We apply Eq. (329) and Jensen's inequality to deduce the following lower bound:
1 - E[cos(amin))
>
5 E
a
min
N
5
E E[amin]
(391)
Now we use Eq. (383) and Eq. (384) to arrive at
2 N - (1 In(d 1) )²
E E[amin :2 N a amann 12
N
(392)
(d 1)
for sufficiently large d. Thus in order to fulfill Eq. (390), it is enough to find values that satisfy Eq. (387).
55

---

A.1.6.2 Retrieval of Patterns with One Update and Small Retrieval Error. Retrieval of pattern z; for fixed point x; and query & is defined via an e by l[f(E) x; || < c, that is, the update is e-close to the fixed point. The update rule retrieves pattern with one update for well separated patterns, that is, A; is large.
Theorem A8 (Pattern Retrieval with One Update). With query &, after one update the distance of the new point ( to the fixed point ot is exponentially small in the separation A The precise bounds 8f(E) and its value J in the mean value theorem are:
using the Jacobian J
0e
(lf(E) æill < | lla IIE - æill.
(393)
|J ll < 2 N (N - expep((222 3 (A; - max - mell 1|27 aill) M))
(394)
For given e and sufficient large Di we have II](E) - xill < 6, that is, retrieval with one update.
Proof. From Eq. (180) we have
|| 2 & 2,3 N 2 (N- - 1) exp(- (A; max æxll, || æx|l] M)) -
(395)
After every iteration the mapped point f(E) is closer to the fixed point at than the original point æ;:
[I xt || < || l|5 æ;
(396)
For given c and sufficient large A,, we have [f(() atll < c, since |J foes exponentially fast to zero with increasing A,,
We want to estimate how large A; is. For æ; we have:
A: min (x) x; of 2z)) af x; max a æj. j3
(397)
To estimate how large A is, assume vectors æ E Rd and y E R that have as components standard normally distributed values. The expected value of the separation of two points with normally distributed components is
E
a x x²y]
Σ E j=1
Σ
F
E [
= d.
(398)
The variance of the separation of two points with normally distributed components is
Var
( x
x²" "]
(a"
x
x² v)
d²
(399)
d
d Σ E
Σ
E
[+]]]]
+
Σ
E
[x
E [1
2
CE
1=1
j=1
2
Σ
[x [yne
[23] E [23] +
1= 1=1,,=1,, Kepp
1=1
E B[r 1y E [r
[yx]
d²
j=1.k=1. Kiy
3d d d (d 1) + d d² d
The expected value for the separation of two random vectors gives:
|| < 2 N 2 (N - 1) exp( 3 (d 2 max æ;1|, || - -x,1} M))
(400)
For the exponential storage we set M 2d 1. We see the Lipschitz constant [|J Iا decreases exponentially with the dimension. Therefore, []f((E) x is exponentially small after just one update. Therefore, the fixed point is well retrieved after one update.
The retrieval error decreases exponentially with the separation A.
56

---

Theorem A9 (Exponentially Small Retrieval Error). The retrieval error (If(E) xxi of pattern æ, bounded by
(I) a.11 < 2 (N - 1) exp(- 3 (A, - 2 max aills 1|= m.ll) M)) M (401)
and for ||ar; a; || < M logether with ||= - Ell < M0M by
|
xill & e (N - 1) M exp(- B Ai).
(402)
Proof. We compute the retrieval error which is just (E) - xz From Lemma A4 we have
||., [() M,
(403)
From Eq. (179) we have
(N -1) exp(x 8 (A; max 1111 x.ll3 M))
(404)
For ||:; 2;11 & 2 M and |1:;- - E < 2 Eq. (404) gives
E (N 1) M exp( A.)
(405)
A.1.7 LEARNING ASSOCIATIONS
We consider three cases of learning associations. i.e. three cases of how sets are associated. Non of the sets is mapped in an associative space. The raw state pattern Tn is the state (query) pattern En, i.e. En Tn, and the raw stored pattern y, the stored pattern (key). i.e. H, = ys- (ii) Either one of the sets is mapped to the space of the other set or an association matrix is learned. (iia) The state patterns are equal to the raw patterns, i.e. &, = Pyy and raw stored patterns are mapped via W to the space of the state patterns, i.c. T W y. (īib) The stored patterns are equal to the raw patterns, i.e. I. = Ye. and raw state patterns are mapped via W to the space of the stored patterns, ie. &.. W rn- (iic) The matrix W is association matrix. We will compute the derivative of the new state pattern with respect to W. which is valid for all sub-cases (iib)-(ie)) (iii) Both set of patterns mapped in common associative space. raw state pattern r, is mapped by Wo to state pattern (query) E., that is 6,, = Worn. A raw stored pattern ys is mapped via Wx to stored pattern (key) x,, that is v. W W.y.- We will compute the derivative of the state pattern with respect to both Wq and WK.
A.1.7.1 Association of Raw Patterns No Mapping in an Associative Space. The sets are associated via their raw patterns, i.e. the raw state pattern Tn is the state (query) pattern En. i.c. E, = Tn, and raw stored pattern ys is the stored pattern (key), i.e. x, ys- There is no mapping in an associative space.
The update rule
E nnow = XPp
(406)
where we used
p = softmax($ (3xg x E)
(407)
The derivative with respect to g is
Deuew
3 X (diag(p) -pp") x
(408)
ag
The derivative with respect to X
da T
gnew
a + 3 (diag(p) pp"") (E (Efa).
(409)
0X
These derivatives allow to apply the chain rule if a Hopfield layer is integrated into deep neural network.
57

---

A.1.7.2 Learning Association Matrix Only One Set is Mapped in an Associative Space. Only one of the sets or is mapped in the space of the patterns of the other set. Case (a): the state patterns
equal to the raw patterns &, Tn and the space of the state patterns, i.e. F; = W y.- Case (b): the stored patterns are equal to the raw patterns Fg Yys and raw state patterns
stored patterns are mapped via W to
mapped via W to the space of the stored patterns, i.e. E W Tm- Case (c): the matrix W associates the sets R and Y. This case also includes that W W QQ. which treated in next subsection. The next subsection focuses on low rank approximation of W by defining the dimension d2 of associative space and the matrices W and Wq to define W, or equivalently to map R and Y into the associative space.
From a mathematical point of view all these case are equal they lead the same update rule. Therefore, we consider in the following Case (a) with V. = W and En = Tn. Still, the following formula are valid for all three cases (a) (c).
The update rule is
5 <new WYP,
(410)
where we used
p = softmax (3 Y WTE)..
(411)
We consider the state (query) pattern & with result guow:
Suew W = W Y softmax Y w""g)
(412)
For multiple updates this update rule has to be used. However for a single update, or the last update consider simplified update rule.
Since new state vector guew is projected by a weight matrix Wy to another vector, we consider the simplified update rule:
new Y p Y softmax(3 Y (T
(413)
The derivative with respect to W is
da duew quew
Sewe
da f
fuew
Sene
O(W"(E) da enew
(414)
OW
OW
ngnew
3(WTE)
OW
Nenew
agnew ((WTE)
BY (diag(p) ppp) Y
(415)
Da DaTTmew gnew
a
(416)
Henew
a( E) OW
We have the product of the 3-dimensional tensor dimensional tensor, i.e. a matrix:
with the vector a which gives a 2-
O(WTE) Oa guew
guew
O(
OW a = 5F
(417)
aW agnew
da" T gnew
dw 3 Y (diag(p) - pp"") (T( = a)
(418)
where J is the Jacobian of the update rule defined in Eq. (59).
To obtain the derivative of the full update rule Eq. (412) we have to add the term
a p YT
(419)
and include the factor W to get
da" T gnew
a ap-xppr Y + 8 W Y (diag(p) pp-) Y (T(ETa)
(420)
OW
-ap'' + W (g
58

---

A.1.7.3 Learning Two Association Mappings Both Sets are Mapped in Associative Space. Both sets R and Y are mapped in an associative space. Every raw state pattern Tu is mapped via We to state pattern (query) S.. WT Every raw stored pattern y, is mapped via Wx to stored pattern (key) 2; W k y- In the last subsection we considered single matrix W. For W W Wo have the case of the last subsection. However in this subsection are looking for low rank approximation of W. Toward this end we define the dimension d₃ of associative space and use the matrices W and We map the associative space.
The update rule is
nnew X Xpp P
(421)
where we used
= softmax (3 x T)
(422)
We consider raw state patterns Tn that are mapped to state patterns &, Worn with Q = WaR and raw stored pattern ys that are mapped to stored patterns æ, WKys with KJ X WKY. Y. The update rule Euew
Wx Y WK Y sollmax(3 Y W W& r).
(423)
Since new state vector enew is projected by weight matrix Wy to another vector, we consider the simplified update rule:
nuew Y - Y softmax(3 Y W We r)
(424)
For the simplified update rule, the vector gnew does not live in the associative space but in the space of raw stored pattern y. However WK would map it to the associative space.
* Derivative with respect to Wo. The derivative with respect to Wq is
T g ng da @aTgneu agnow
( r) da? gnow OW
(425)
dW
aw ngnew r)
ngnew
a(Wa r) = BY (diag(p) - ppp') YJW?
(426)
Oa dal'geew. Denew
a
(427)
We have the product of the 3-dimensional tensor dimensional tensor, i.e. matrix:
WWr) WW
with the vector which gives 2-
a(Wer) r) da Tg a r)
a = raal.
(428)
IWQ agnew
dWQ
da_ T gnew
8 Y (diag(p)
pp") Y WF( JW
(429)
dWq
where the Jacobian of the update rule defined in Eq. (59).
To obtain the derivative of the full update rule Eq. (423) we have include the factor Wx. then get
da T gnew
dWa = B WK Y (diag(p) -p T (T = Wx J W Wr a)
(430)
Derivative with respect WK. The derivative with respect to WK is
0a
@new gnew
Sguew
da gnew
Sgnew
d(W K We r)
da guew denew
(431)
OW OW agnew
d WW
OW
59

---

e W WW = BY (diag(p) - -pp") y
(432)
da T guew
(433)
denew
We have the product of the 3-dimensional tensor tensor, i.e. matrix:
8 Wrr OWk
with the vector a which gives a 2-dimensional
a a K W r) da-gmme gnow
a a
WWr W
K
a = W
(434)
dWK
Dgnew
OW
Oa guew
OWK B Y (diag(p)
pp") Y (W3r" (W3 a)
(435)
where J the Jacobian of the update rule defined in Eq. (59).
To obtain the derivative of the full update rule Eq. (423) we have to add the term
pp'y YT
(436)
and to include the factor WK. then get
Oa gnew
OWK Y + W Y (diag(p) pp"" (z(Wor"aa)
(437)
Y + WK (WTr
1.1.8 INFINITE MANY PATTERNS AND FORGETTING PATTERNS
In the next subsection show how the new Hopfield networks can be used for auto-regressive tasks by causal masking. In the following subsection, we introduce forgetting to the new Hopfield networks by adding negative value to the softmax which is larger if the pattern observed more in the past.
A.1.8.1 Infinite Many Patterns. tasks, that is time series prediction and similar. Causal masking masks out the future by a large negative value in the softmax.
The new Hopfield networks can be used for auto-regressive
We assume have infinite many stored patterns (keys) #2,.2,.... that are represented by the infinite matrix
X (01, .2,...,,
(438)
The pattern index is now a time index, that is, we observe æ; at time t.
The pattern matrix at time is
X, = (x), Ø2, ..,,).,,;))))
(439)
The query at time is &
For Mt maxigie! || the energy function at time E,
1
E2 = - 13, X + 2 ET + I-'ttt Int + M?
(440)
2
3 ln Σ exp((axf si)
1 5/ Eo + 8-2 Int + M²
1
+
(441)
2
The update rule
nnew $1
X, P:
X, softmax( x((()
(442)
60

---

1 where we used
Pt softmax(B X E:)
(443)
We can use an infinite pattern matrix with an infinite softmax when using causal masking. The pattern matrix at time t is
X, (21, 22,.... St. -C -.......)
(444)
with the query & and a - 0c. The energy function at time / is E,
E, = - 1se(B, X Ei) + 2 + -----n + 2 M
(445)
2
|a]
- -- Σ exp(Barff Ei) +
Σ
exp(-Ba 100111
1 +
(446)
x=++1
8- 1 Int +
2 M2-
For and | this becomes
2 ST + Int + 1 M3
Eg 1sc( X,(
2 MM
(447)
= 3- In
exp(3xxf + of + Int
2 M2
(448)
A.1.8.2 Forgetting Patterns. We introduce forgetting to the new Hopfield networks by adding negative value in the softmax which increases with patterns that are more in the past.
We assume to have infinite many patterns 1i, .., that are represented by the infinite matrix
X (z) U2 ...)..)
(449)
The pattern index is now a time index, that is, we observe æ; at time t.
The pattern matrix at time is
X. (x). D2....,
(450)
The query at time is &x- The energy function with forgetting parameter y at time t is E,
1
F,
1se(3, E.
7tt 1, ...... 0) tt & + g-1ltt
Int + M2
(451)
2
T
- 3 In
Σ
exp(3xT
-(t--))) 1))
>(t
+ ETE + 8- Int + M₁.
(452)
2
The update rule is
<n
X, P: Xx (3
(453)
where we used
p. softmax(3x Ex)
(454)
1.1.9 NUMBER OF SPURIOUS STATES
The energy E is defined as
1 F + 3 + 1 M²
E = - Ise(B, x
(455)
2
1 In + E M²
- Σ exp(BBaT)
(456)
2
61

---

Since the negative exponential function is strict monotonic decreasing, exp(-E) E) has minima, where has maxima, and has maxima, where as has minima E.
1 exp(-E) exp(Ise(3, x) expl- 5
(457)
81
1
exp (Bx {)
exp(
=) a
2
N
8-
3 1
Σ exp(Sxx''
exp(-
2
8-1
Σ exp(8
25 -5TEE)
1
C
3 (E - x;)² - will) x-1
N
Σ expl
[ 3 x
x;
C
2
X(x,,)) 9) G(E: 1) 1r1 C.
where C a positive constant, X(x,, 3) = exp( x.) and G(E: a,, 8-11) I) is the Gaussian with mean I; and covariance matrix 3 I.
Since C' positive constant and x.3 exp(3-11na) mn)) strict monotonic for positive æ, the minima of E are the maxima of
N M(x B) G(E:,,, I).
(458)
In Carreira-Perpinán Williams (2003) was shown that Eq. (458) can have more than N modes, that is, more than N maxima.
A.2 PROPERTIES OF SOFTMAX, LOG-SUM- LEGENDRE TRANSFORM, LAMBERT W FUNCTION
For > 0, the softmax is defined Definition A1 (Softmax).
p = softmax (8x)
(459)
exp(3xx,
= [softmax(Bx))]
(460)
Σx k exp(pxxx (3zx))
We also need the log-sum-exp function (lse), defined as Definition A2 (Log-Sum-Exp Function).
1se(3, x)) -3-'mn
Σ exp(Br:))
(461)
62

---

We formulate the Ise in another base:
Ba = B
(462)
In a
N
1s0 x)) = 3-1 In
Σ
exp( (3 xii)
(463)
N
= (3a Ina) -aa--1n ana) In
Σ
exp(Ba lna
N
= (3a) loga
a
Bn
In particular, the base a = 2 can be used to speed up computations.
Next, give the relation between the softmax and the Isc function. Lemma A18. The softmax is the gradient of the lsc:
softmax(Ba) = V Valse(3,0) x))
(464)
In the next lemma report some important properties of the Ise function. Lemma A19. We define
L := xTx
8-1
24
In
(465)
1=1
with L xx.. The lse is the maximum of on the N-dimensional simplex with D
{z
Σ, žं = 1,0 & :
Ise(3, max 2²
-311
Σ z4 In 21
(466)
sED
The softmax p softmax(33r) is the argument of the maximum of on the N-dimensional simplex D with D = { >> 22 1,0 & zi:
p softmax(3x) arg max xJ x
B
Σ
In
(467)
1=1
Proof. Eq. (466) is obtained from Equation (8) in Gao & Pavel (2017) and Eq. (467) from Equa-
tion (11) Gao & Pavel (2017).
From a physical point of view, the Ise function represents the "free energy" in statistical thermody- namics (Gao & Pavel, 2017).
Next consider the Jacobian of the softmax and its properties.
Lemma A20. The Jacobian J, of the softmax softmax( (3x)) is
@softmax(32)) J. =
B (diag p) -pp")
(468)
Ox
which gives the elements
{ [ppi(1- - pi) fori jj
Joly =
(469)
-Bpppp
fori
Next we show that J. has eigenvalue 0.
Lemma A21. The Jacobian J, of the softmax function = softmax( (Bx) has a zero eigenvalue with eigenvector 1.
63

---

Proof.
J.1] = B pill -pi)- E Eppps
= Bp(11 - ΣnT) =0
pips
(470)
JJ3
3
Next we show that is the smallest eigenvalue of J., therefore J, is positive semi-definite but not (strict) positive definite. Lemma A22. The Jacobian J. of the softmax p softmax((BE) is symmetric and positive semi- definite.
Proof. For an arbitrary z, have
2
zJ (diag(p) ppp))==
Σ
Epizi
Pižz
(471)
Σ
Epizd
pizz
Σ Pi
Σ Pizz
0.
The last inequality hold true because the Cauchy-Schwarz inequality says (a" (b= 2 (a b)² which is the last inequality with a, 2ivP; and b, /Pi. Consequently (diag(p) pp") is positive semi-definite.
Alternatively E; - Piz,) can be viewed as the expected second moment minus the mean squared which gives the variance that larger equal zero
The Jacobian is < = times a positive semi-definite matrix, which is a positive semi-definite matrix.
Moreover, the softmax is monotonic map, described in the next lemma. Lemma A23, The softmax softmax(3z) is monotone for B > 0, that is,
(softmax(3x)) softmax(33'))) (x x 0.
(472)
Proof. We use the version of mean value theorem Lemma A32 with the symmetric matrix J fo (Ax (1 A)ær) dA:
softmax(#)) softmax(4') Jmh (x x²)
(473)
Therefore
(softmax(z)) softmax(x')) T (x: x') (x x²)² Jm (x x') 2 0,
(474)
since J is positive semi-definite. For all X the Jacobians (Ax + (1 - ))w') are positive semi-definite according to Lemma A22. Since
JT
xx J.(x + (1 A)æe) yd 2
(475)
an integral over positive values for every æ, J is positive semi-definite, too.
Next we give upper bounds on the norm of J,.
Lemma A24. For softmax p softmax with max, ps(1 ps), the spectral norm of the
Jacobian Jg of the softmax is bounded:
J 1 < 2 m B
(476)
| < 2 m B
(477)
J
< 2 m
(478)
64

---

In particular everywhere holds
1
||el|2 & 2 3
(479)
If Pmax = max; Pi 2 1 - 6 2 0.5, then the spectral norm of the Jacobian holds
||J.ll2
2 2 2 3 2 3
(480)
Proof.
We consider the maximum absolute column sum norm
All1 =
max
aijl
(481)
and the maximum absolute row sum norm
||
max Σ lay!
(482)
We have for A Jg B (diag(p) -pp")
Σ lail 3 Pi(1- (c(1-Pi) pi) Σ PiPj
pi (1
2p: + ED)
(483)
2 Pe (1 (ppp)) 2 3
Σ layl 8 Pj (1 (1-p)) + Σ PjP:
BB (1
2pg + Σ pt)
(484)
= 2 B p. (1 - (1-p,)
< 2 m B.
Therefore, we have
|Jدل| < 2 m 8
(485)
|| & 2 m 3
(486)
|Jدل]2 IJJ.lI & 2
(487)
The last inequality is a direct consequence of Hölder's inequality.
For p4 1, we have p1 - -p:) & 0.25. Therefore, m & 0.25 for all values of ps.
If Pmax 2 1 1- 2 0.5 (e < 0.5), then 1 - Pmax & e and for pt # Paax & E. The derivative 2x > 0 for x < 0.5, therefore xx1 x) increases with x for x 0.5. Using
0z(1 - /0/
Pmax and for p: * Pmax Ps. we obtain p, (1 p.) < c(1 - c) for all i. Consequently.
we have m < <(1 - e).
Using the bounds on the norm of the Jacobian, we give some Lipschitz properties of the softmax function.
Lemma A25. The softmax function = softmax( (3x) is -iipshhtt. The softmax function p = softmax(Bxr) is -23m))LLpsctiee in convex environment U for which maxxeu max; Pt P:). For Pinax = mingeU max; p; = 1-c, the functixn p = softmax (Bx) is (2isc)-ipseehitz. For 3 < 2m, the softmax p softmax(32.) is contractive in U which is defined.
Proof. The version of mean value theorem Lemma A32 states for the symmetric matrix J So J(Ax (1 A)x²) dA:
softmax(#) softmax(x') = J (x x') According to Lemma A24 for all Ax + (1 --)x²)
(488)
| < m B
(489)
65

---

where m max; Pa(1 p.). Since E U and x' U have ā U, since U is convex. For m = max max; P.(1 Ps) we have in & m for all m. Therefore, we have
|J.(
m
(490)
which also holds for the mean:
| & 2 m B
(491)
Therefore,
[softmax(x) softmax(2') (z))
< | ll | - 2'1l < 2 m 3 ||e æ'll
(492)
From Lemma A24 we know m & 1/4 globally. For Piaxx = min EU max; ps = 1 e we have according to Lemma A24: <
For completeness we present result about cocoercivity of the softmax:
Lemma A26. For m = maxæeu max; pi - -P;), cefimaxfunctiunn p softmax(3x)) is 1/(2m.)- cocoercive in U, that is.
1 |softma(()) softmax(z')] (493)
(softmax(xx) softmax(x")) (x x') 2
2 m B
In particular the softmax function p softmax( (Bx) is (2/3)-cocoerciive everywhere. With Pmax milleUt max; pi 1- e, the softmax function p sollmax(3ar) is
in U.
Proof. We apply the Haillon-Haddad theorem (e.g. Theorem in Gao & Pavel (2017)) together with Lemma A25.
Finally, introduce the Legendre transform and use it to describe further properties of the lse. We start with the definition of the convex conjugate.
Definition A3 (Convex Conjugate). The Convex Conjugate (Legendre-Fenchee transform) of function f from a Hilbert Space X to [-00, 00] is f which is defined
("(x") sup (xx Th x=" f(x)), x E
(494)
xeX
See page 219 Def. 13.1 Bauschke & Combettes (2017) and page 134 Garling (2017). Next we define the Legendre transform, which is more restrictive version of the convex conjugate.
Definition A4 (Legendre Transform). The Legendre transform of a convex function f from a conver ser X C R to (f B.) is f*, which defined as
fx sup (xT x f(x)), x' x'EX" EX"
(495)
xEX
sup (x s(x)) 00 60).
X xx R
(496)
mex
See page 91 in Boyd & Vandenberghe (2009).
Definition AS (Epi-Suum. Let f and g be two functions from X to (-00, oo), then the infimal
convolution (or epi-sum) of f and is
fīg + 20]. x x inf
(f(y) + g(x -0)=))) 8))
(497)
MEX
See Def. 12.1 1.1. in Bauschke & Combettes (2017).
Lemma A27. Let f and be functions from X to (-00, oo). Then the following hold:
1. Convex Conjugate of norm squared
1
1
2 1-11
(498)
66

---

2. Convex Conjugate of function multiplied by scalar 0 < E IR (ox f)" = (-/o).
(499)
3. Convex Conjugate of the sum of a function and a scalar R
(f + = B.
(500)
4. Convex Conjugate of affine transformation of the arguments. Let A be non-singular matrix and b a vector
(Ax + b))* = f (A-Tx") b" x
(501)
5. Convex Conjugate of epi-sums
(SD = S + g
(502)
Proof.
1. Since h(()) := is a non-negative convex function and h(t) = =
0 we have because of Proposition 11.3.3 in Garling (2017) that h ([=1)) = h" (1 II) Additionally, by example (a) on page 137 we get for < p 0o and
that
-- Putting all together get the desired result. The same result can also be P q deduced from page 222 Example 13.6 in Bauschke & Combettes (2017).
[1
2. Follows immediately from the definition since
x
-T= -f(x)) sup (x: x aaf())) (ar))((*)) xex
of
a sup #xX
a
3. (f 8) = supxEx (x" x² - f(x) - -3) =: f: 3
4.
(Ax bb)' (x") sup (x' x=' f(Ax +b))
#EX
sup (Ax + b)² A -T =T - (Ax b)) - A-
#EX
yEX A -T=" - (y)) - -b A TTx
sup (yTA
f" (A-Tx') - b" T
5. From Proposition 13.24 (i) in Bauschke & Combettes (2017) and Proposition 11.4.2 in Garling (2017) we get
(fLig) (x*) sup m
x x' inf (f(y) - g(x - 4))
weX
(xT x -f() - g(x - -y))
sup
2.EEX
(I"" -f())) + ((x
4))
sup
ævEx
= f("))) + + (x")
Lemma A28. The Legendre transform of the Ise is the negative entropy function, restricted to the probability simplex and vice versa. For the log- sum exponential
f(x) In Σ exp(xa)
(503)
67

---

the Legendre transform is the negative entropy function, restricted the probability simplex:
o In(at) for 0 E x3 and Ei=1 2 otherwise
(x(x")
(504)
00
For the negative entropy function, restricted to the probability simplex: the Legendre transform is the log-sum exponential
In(a;)
for 0 0 Iz and Eis I2 otherwise
f(x)
00
(505)
(x = In Σ exp(x;))
(506)
Proof. See page 93 Example 3.25 in Boyd & Vandenberghe (2009) and (Gao & Pavel, 2017).
is a regular convex function (lower semi-continuous convex function), then f according to page 135 Exercise 11.2.3 in Garling (2017). If f is lower semi-continuous and convex, then fo* f according to Theorem 13.37 (Fenchel-Moreau) in Bauschke & Combettes (2017). The
log-sum-exponential is continuous and convex.
Lemma A29, Let XXT be non-singular and a Hilbert space. We define
X = aalo & x (xx*) a, 1"xx axxx)'a=11
a
(507)
and
X faala X {EX}.
(508)
The Legendre transform of 1,e(3, with & E X
(1se( B3 x x)) (E*) = (1so(3,v)) v))* (x' (xx*) 5')
(509)
with E" E X* and X The domain of (1se(B, X x)) is X*.
Furthermore we have
(Ise(3, x² = Ise(3, (T)
(510)
Proof. We use the definition of the Legendre transform:
(1ee(3, x" {)) (g") = sup 5" - Ise(3, x ()
(511)
EEX
sup (xTE) x² (Xxx)-1 -1-- 1se(3,X' x ))
EEX
sup ve x (Xx*) -1 g" -Isc(B,
vex"
sup vba²" 10- ()0(3,0)
vEX-
(1se(3, b))" (v") 1))) (x" (XXx)- 5e)
where we used o² = XT (XXT) -1 g"
According to page 93 Example 3.25 in Boyd & Vandenberghe (2009), the equations for the maximum m TT V2' 1se(3, v) are solvable if and only if ( < v²' = x (XxT)-1 -' and 1 -T (XXT)- -1 g- =1 Therefore, we assumed g* E X".
The domain of (3 x" is X", since page 93 Example 3.25 in Boyd & Vandenberghe (2009) it was shown that outside X the supvex ot 0a 1se( v) is not bounded.
68

---

Using
p s0ftmax(3X" (3x
(512)
the Hessian of (00,,X"'
Ssec [3 xT
B X (diag(p)- - -ppp' X
(513)
is positive semi-definite since diag(p) pp" is positive semi-definite according to Lemma A22. Therefore, 1se( X E) is convex and continuous.
If f is regular convex function (lower semi-continuout convex function), then f = f according to page 135 Exercise 11.2.3 in Garling (2017). If f is lower semi-continuous and convex, then f f according to Theorem 13.37 Frenchel-Moraat in Bauschke & Combettes (2017). Consequently have
(iso(B,x")))
1s (3))
(514)
We introduce the Lambert W function and some of its properties, since it is needed derive bounds on the storage capacity of our new Hopfield networks. Definition A6 (Lambert Function). The Lambert W function (Olver et 2010, (4.13)) is the inverse function of
fly) ye"
(515)
The Lambert W function has an upper branch Wo. -1 & y and a lower branch f & -1. We use W if a formula holds for both branches. We have
((x)
ye" = x.
(516)
We present some identities for the Lambert W function (Olver et al., 2010, (4.13)):
Lemma A30. Identities for the Lambert W function are
(x) e (()) W W(xe") D;
T;
(517)
(518)
((w)) 2
(519)
(xx) (W())
W(z)
(520)
(w))
I
(521)
((x)
1
Wo (x Inx))
In
for x 2
(522)
1
W-1 (x Inx)
= In for x <
(523)
e
W(x) In W(x)
T for x 2
(524)
e
x
W
W(x) for n, > 0,
(525)
W (x))-1)
W xy W(x) + 1 w))))) for x. > 0,
1
W(x)
+ W(y)
(526)
Inx
Wo
x I for x ee,
(527)
In
W_1
In for x > c,
(528)
x
W(- Inx)
W(-
In
for 1.
(529)
Iux
69

---

We also present some special values for the Lambert W function (Olver et al., 2010, (4.13)):
Lemma A31.
W(0) 0
(530)
((e) = 1
(531)
W =
(532)
W (cl+a) =
(533)
W (2 = In2,
(534)
(11)
(535)
(11) W(1) In
In (1))..
(536)
W(1))
T = iπ 2
W
(537)
2
(-11) ~ 0..1883 1.33723i,
(538)
where the Omega constant
(1r (et 1)2 + n2
dt
Ω
1 R3 0.56714327
(539)
We need in some proofs version of the mean value theorem as given in the next lemma.
Lemma A32 (Mean Value Theorem). Let U C R be open, f U + R continuously differentiable,
and x E U as well as h E IR" vectors such that the line segment x + th for E 1 in U. Then the following holds:
f(x + h) f(x) = J(x + tt)dt) h,
(540)
where J is the Jacobian of f and the integral of the matrix is component-wise.
Proof. Let fi..... : fm denote the components of f and define 9i [0. - R by
g:(t) = fi(x + th).
(541)
then we obtain
filæ + 12) - fi(x)) = -9:(1) 9:(0) = S. )()
(542)
0f (x + t1) th) by dt Σ 5=1 Dxj
(
0f (x + h) dt hg
dz,
The statement follows since the Jacobian J has as entries 0f: Bay
A.3
MODERN HOPFIELD NETWORKS: BINARY STATES (KROTOV AND HOPFIELD)
A.3.1 MODERN HOPFIELD NETWORKS: INTRODUCTION
Additional Memory and Attention for Neural Networks. Modern Hopfield networks may serve as additional memory for neural networks. Different approaches have been suggested to equip neural networks with an additional memory beyond recurrent connections. The neural Turing machine (NTM) is neural network equipped with an external memory and attention process (Graves et al., 2014). The NTM can write to the memory and can read from it. memory network (Weston et al., 2014) consists of memory together with the components: (1) input feature map (converts the incoming input to the internal feature representation) (2) generalization (updates old memories given the new input), (3) output feature map (produces output), (4) response
A.3.1.1
70

---

(converts the output into the response format). Memory networks are generalized to an end-to- trained model, where the arg max memory call is replaced by a differentiable softmax (Sukhbaatar et al., 20;5a; Linear Memory Network use linear autoencoder for sequences memory (Carta et al., 2020).
To enhance RNNS with additional associative memory like Hopfield networks have been proposed (Ba et al., 201 6a;b). The associative memory stores hidden states of the RNN, retrieves stored states they are similar to actual ones, and has forgetting parameter. The forgetting and storing parameters of the RNN associative memory have been generalized to learned matrices (Zhang & Zhou, 2017). LSTMs with associative memory via Holographic Reduced Representations have been proposed (Danihelka et al., 2016).
Recently most approaches to new memories are based on attention. The neural Turing machine (NTM) is equipped with an external memory and an attention process (Graves et al., 2014). End to end memory networks (EMN) make the attention scheme of memory networks (Weston et al., 2014) differentiable by replacing arg max through softmax (Sukhbaatar et al., 2015a;b). EMN with dot products became very popular and implement a key-value attention (Daniluk et al., 2017) for self-attention. An enhancement of EMN is the transformer (Vaswani et al., 70;b) and its extensions (Dehghani et al., 2018). The transformer had great impact on the natural language processing (NLP) community
records in NLP benchmarks have been achieved (Vaswani et al., 2017a;b). MEMO uses the transformer attention mechanism for reasoning over longer distances (Banino et al., 2020). Current state-of-the-art for language processing is transformer architecture called "the Bidirectional Encoder Representations from Transformers" (BERT) (Devlin et al., 2018; 2019).
A.3.1.2 Modern Hopfield networks: Overview. The storage capacity of classical binary Hop- field networks (Hopfield, 1982) has been shown to be very limited. In a d-dimensional space, the standard Hopfield model can store d uncorrelated patterns without errors but only Cd/ In(d) random patterns with C < 1/2 for fixed stable pattern or C < 1/4 if all patterns are stable (McEliece et al., 1987). The same bound holds for nonlinear learning rules (Mazza, 1997). Using tricks-of-trade and allowing small retrieval errors, the storage capacity about 0.138d (Crisanti al., 1986; Hertz et al., 1991; Torres et al., 2002). If the learning rule is not related to the Hebb rule then up to d patterns can be stored (Abu-Mostafa & Stlaeques, 1985). Using Hopfield networks with non-zero diagonal matrices, the storage can be increased to Cn (d) (Folli et al., 2017). In contrast to the storage capacity, the number of energy minima (spurious states, stable states) of Hopfield networks is exponentially in d (Tanaka & Edwards, 1980; Bruck & Roychowdhury, 1990; Wainrib & Touboul, 2013).
Recent advances in the field of binary Hopfield networks (Hopfield, 1982) led to new properties of Hopfield networks. The stability of spurious states or metastable states was sensibly reduced by Hamiltonian treatment for the new relativistic Hopfield model (Barra et al., 2018). Recently the storage capacity of Hopfield networks could be increased by new energy functions. Interaction functions of the form F(x)= x" lead to storage capacity of a,,"'1, where on depends on the allowed error probability (Krotov & Hopfield, 2016; 2018; Demircigil et al., 2017) (see (Krotov & Hopfield, 2018) for the non-binary case). Interaction functions of the form F(x) x lead to storage gn-1 capacity of an en Ind for C, > 2(2n - 3)!! (Demircigil et al., 2017).
Interaction functions of the form F(x) exp(x) lead exponential storage capacity of 2d4/2 where all stored patterns are fixed points but the radius of attraction vanishes (Demircigil et al., 2017). It has been shown that the network converges with high probability after one update (Demircigil et al., 2017).
A.3.2 ENERGY AND UPDATE RULE FOR BINARY MODERN HOPFIELD NETWORKS
We follow (Demircigil et al., 2017) where the goal is to store a set of input data æ,,..., NN that are represented by the matrix
X (I), ........... xN)
(543)
The æ; is pattern with binary components Zzj E (-1, +1} for all and j. is the actual state of the units of the Hopfield model. Krotov and Hopfield (Krotov & Hopfield, 2016) defined the energy function E. with the interaction function F that evaluates the dot product between patterns æ; and the
71

---

actual state E:
E
Σ F (E ==1
(544)
with F(a) = a", where n = 2 gives the energy function of the classical Hopfield network. This allows to store a, a,, d patterns (Krotov & Hopfield, 2016). Krotov and Hopfield (Krotov & Hopfield, 2016) suggested for minimizing this energy an asynchronous updating dynamics = (T₃) for component Ey
(E)
sgn Σ (F +
Exn EaaE) Ei) F(- 2ÿj + Σ xa &)) (t)
(545)
bØ1
While Krotov and Hopfield used F(a) = a", Demircigil et al. (Demircigil et al., 2017) went step further and analyzed the model with the energy function F(a) exp(a), which leads to an exponential storage capacity of N = 24/2, Furthermore with a single update the final pattern is recovered with high probability. These statements are given in next theorem.
Theorem A10 (Storage Capacity for Binary Modern Hopfield Nets (Demircigil et al. 2017)). Con- sider the generalized Hopfield model with the dynamics described in Eq. (545) and interaction function F given by Fz)) = c². For a fixed 0 < a < ln(2)/2 / let N = exp (ad) + 1 and let 21,.... EN be N patterns chosen uniformly at random from { +11++13 Moreover fix E [0, 1/2). For any and any 3; laken uniformly at random from the Hamming sphere with radius ed centered in Ia S(x, gd), where ed is assumed to be an integer, holds that
Pr (3i 3j T3 (Tt.) + m2g) 0, if or is chosen dependence of Q such that
T(1 - -20)
2
with
1 I / a1) a) (1 In()))n11111111111 a))
Proof. The proof can be found in Demircigil et al. (2017).
The number of patterns N = exp (ad) + is exponential the number of components. The result Pr (3i Aj: T₃ (ã:) * mzy) + 0
means that one update for each component is sufficient to recover the pattern with high probability. The constraint a < 1(1-2g) on a gives the trade-off between the radius of attraction gd and the number N exp (ad) + of pattern that be stored.
Theorem A10 in particular implies that
Pr (3i Aj (x::) # xay)) + 0
as + xc, i.c. with a probability converging to 1, all the patterns are fixed points of the dynamics. In this case we can have a + 1(1) l222/22
Krotov and Hopfield define the update dynamics (E) in Eq. (545) via energy differences of the energy in Eq. (544). First we express the energy in Eq. (544) with F(a) = exp(a) (Demircigil et al., 2017) by the Ise function. Then we use the mean value theorem express the update dynamics T, (E) in Eq. (545) by the softmax function. For simplicity, we set 3 = 1 in the following. There exists
v E [-1, with
(E) sgm
EIEE =) + F(EE = -1)] sgn [exp(Ise(E) 1)) exp(Ise(EE) -1))
(2e,)² (ee VeB(E =w]] sgn Texp(Ise(E) = v)) (2e;)² Ise(E, v)
sgn
(546)
0g
eexp(Ise(E) = 1)) (2e,)² ( Xsoftmax(X X XTE(E b))] (oottaxxX"xff. w)}b} sgn [Xp(s) u)]}}
sgn
sgn
72

---

where e, is the Cartesian unit vector with at position j and zeros elsewhere, [-lj is the projection to the j-th component, and
p = softmax (X x7
(547)
A.4 HOPFIELD UPDATE RULE ATTENTION THE TRANSFORMER
The Hopfield network update rule is the attention mechanism used in transformer and BERT models
(see Fig. A.2) To see this, we assume N stored (key) patterns y; and state (query) patterns r; that are mapped to the Hopfield space of dimension d3. We set 2 W WKB yi. & W Q Ti. and multiply the result of our update rule with Wv. The matrices Y (y) yN T and R (r combine the y; and r; as row vectors. We define the matrices X
rs)
YW K. 3 Q
RWQ. Q. and V YWK Wv X" Wv. where WK Rdyxde, We Rdd Wy E Rdaxd. If 3 = 1/v da and softmax R is changed multiplied by Wv:
vector, obtain for the update rule Eq. (3)
softmax (1/v Q V = =oftmaa (3 RWQ WKY YWKWV.
(548)
The left part of Eq. (548) the transformer attention. Besides the attention mechanism, Hopfield networks allow for other functionalities in deep network architectures, which we introduce via specific layers in the next section. The right part Eq. (548) serves starting point for these specific layers.
Hopfeeld Enargy
New Energy
Update Rule
Transformer
exp (Ise (1)
1" x) e
softmaa (B xT X
softanna
QK"
V
Vil
Figure A.2: We generalized the energy of binary modern Hopfield networks for allowing continuous states while keeping fast convergence and storage capacity properties. We defined for the energy also a new update rule that minimizes the energy. The new update rule the attention mechanism of the transformer. Formulae are modified to express softmax vector for transformers. "="ssign means "keeps the properties".
A.5 EXPERIMENTS
A.5.1 EXPERIMENT I: ATTENTION IN TRANSFORMERS DESCRIBED BY HOPFIELD DYNAMICS
A.5.1.1 Analysis of operating modes of the heads of a pre-trained BERT model. We analyzed
pre-trained BERT models from Hugging Face Inc. (Wolf et al., 2019) according to these operating classes. In Fig. A.3 in the appendix the distribution of the pre-trained bert-base-cased model is depicted (for other models see appendix Section 1.4). Operating classes (II) (large metastable states) and (IV) (small metastable states) often observed in the middle layers. Operating class (I) (averaging over a very large number of patterns) abundant lower layers. Similar observations have been reported in other studies (Toneva & Wehbe, 2019a;b Tay al., 2020). Operating class (III (medium metastable states) is predominant in the last layers.
A.5.1.2 Experimental Setup. Transformer architectures are known for their high computational demands. To investigate the learning dynamics of such a model and at the same time keeping training time manageable, we adopted the BERT-small setting from ELECTRA (Clark et al., 2020). It has 12 layers, 4 heads and a reduced hidden size, the sequence length is shortened from 512 to 128 tokens and the batch size is reduced from 256 to 128. Additionally, the hidden dimension is reduced from 768 to 256 and the embedding dimension is reduced from 768 to 128 (Clark et al., 2020). The training of such a BERT-smal model for 1.45 million update steps takes roughly four days on a single NVIDIA V100 GPU.
73

---

Head
Heso
Head
Head
Head
Reso
Head
Head
Head
Head 10
Heso 11
Head 12
Layur
X02
Layer
151
235
Layer 10
13
20
24
32
33
33
55
55
67
Z26
Layer
103
2166
277
Layer
375
Layer
Layar
Layer 5
56
65
74
11
333
1.3
100
Layer
158
189
196
214
2
Layer
108
1.64
1/3
197
237
357
197
259
Layer
21
233
241
257
278
299
350
374
pattems
satterns
pattems
I pattems
patttenna
pattems
pattoms
pattirns
pattonms
pattems
pottems
patterna
Figure A.3: Analysis of operating modes of the heads of a pre-trained BERT model. For each head in each layer, the distribution of the minimal number & of patterns required to sum up the softmax values 0.90 is displayed as violin plot panel. indicates the size of metastable state. The bold number in the center of each panel gives the median of the distribution. The heads in each layer are sorted according k. Attention heads belong to class they mainly operate in. Class (IV) in blue: Small metastable state fixed point close to single pattern, which is abundant in the middle layers (6, 7, and 8). Class (II) in orange: Large metastable state, which is prominent in middle layers (3, 4, and 5). Class (I) in red: Very large metastable state global fixed point, which predominant in the first layer. These heads can potentially be replaced by averaging operations. Class (III) in green: Medium metastable state, which is frequently observed in higher layers. We hypothesize that these heads are used to collect information required to perform the respective task. These heads should be the main target improve transformer and BERT models.
74

---

As the code base use the transformers repository from Hugging Face, Inc (Wolf al., 2019). We aim to reproduce the dataset of Devlin et al. (2019) as close as possible, which consists of the English Wikipedia dataset and the Toronto BookCorpus dataset (Zhu et al., 2015). Due to recent copyright claims the later is not publicly available anymore. Therefore, the pre-training experiments use an uncased snapshot of the original BookCorpus dataset.
A.5.1.3 Hopfield Operating Classes of Transformer and BERT Models. To better understand how operation modes in attention heads develop, we tracked the distribution of counts k (see main paper) over time in BERT-small model. At the end of training we visualized the count distribution, grouped into four classes (see Figure A.4). The thresholds for the classes were chosen according to the thresholds of Figure 2 in the main paper. However, they are divided by a factor of 4 to adapt to the shorter sequence length of 128 compared to 512. From this plot it is clear, that the attention in heads of Class IV commit very early to the operating class of small metastable states.
A.5.1.4 Learning Dynamics of Transformer and BERT Models. To observe this behavior in the early phase of training, we created a ridge plot of the distributions of counts k: for the first 20, 000 steps (see Figure A.5 (a)). This plot shows that the attention in heads of middle layers often change the operation mode Class IV around 9, 000 to 10, 000 steps. At the same time the second big drop in the loss occurs. The question arises whether this is functionally important or whether it is an artefact which could be even harmful. To check if the attention mechanism is still able to learn after the change in the operation mode we analyzed the gradient flow through the softmax function. For every token we calculate the Frobenius norm of the Jacobian of the softmax over multiple samples. Then, for every head we plot the distribution of the norm (see Figure Ab)(. The gradients with respect to the weights are determined by the Jacobian defined in Eq. (59) as can be seen in Eq. (418), Eq. (429), and Eq. (435). We can see that the attention in heads of Class IV remain almost unchanged during the rest of the training.
A.5.1.5 Attention Heads Replaced by Gaussian Averaging Layers. The self-attention mecha- nism proposed in Vaswani et al. (2017a) utilizes the softmax function to compute the coefficients of convex combination over the embedded tokens, where the softmax is conditioned on the input. However, our analysis showed that especially in lower layers many heads perform averaging over very large number of patterns. This suggests that at this level neither the dependency on the input nor fine grained attention to individual positions is necessary. As an alternative to the original mechanism we propose Gaussian averaging heads which are computationally more efficient. Here, the softnax function is replaced by a discrete Gaussian kernel, where the location μu and the scale are learned. In detail, for a sequence length of N tokens we are given a vector of location parame- ters μ (H1....., :N.........."" AN) and vector of corresponding scale parameters subdivide the interval [-1,1] into N equidistant supporting points (8) IN where ON) We
(j - 1) 0.5 (N 1)
0.5 (N - 1)
The attention [A]ks from the i-th token to the j-th position is calculated as
1 exp
{
1
[A]
2
where 2; normalizes the i-th row of the attention matrix A to sum up to one:
1
83 mi 2 )²}
cxp
2 5
For initialization we uniformly sample location vector μ E [-1, 1\N and scale vector [0.75, 1.25]" N per head. A simple way to consider the individual position of each token at initialization is to the supporting points μ4 8; (see Figure A.6). In practice no difference to the random initialization was observed.
Number of parameters. Gaussian averaging heads can reduce the number of parameters significantly. For an input size of N tokens, there are 2-N parameters per head. In contrast, a standard self-attention head with word embedding dimension dy and projection dimension de has two weight matrices
75

---

Layer 12
Layer
23
11
Layer
Layer
Layer
Layer
12
19
$9
73
76
Layer
pattems
patterms
patterns
patterns
Figure A.4: Left: Ridge plots of the distribution of counts & over time for BERT-small Right: Violin plot counts after 1, 450000 steps, divided into the four classes from main paper. The thresholds were adapted to the shorter sequence length.
76

---

(a) Densities
(b) Norm Jacobian
Figure A.5: (a): change of count density during training is depicted for the first 20, 000 steps. (b): the corresponding distribution of the Frobenius norm of the Jacobian of the softmax function depicted. The gradients with respect to the weights are determined by the Jacobian J defined in Eq. (59) as can be seen in Eq. (418), Eq. (429), and Eq. (435).
77

---

Wo. WK Rdaxdy, which together amount to 2 d2 dy parameters. As a concrete example, the base model from Devlin al. (2019) has an embedding dimension dy = 768, projection dimension dę 64 and sequence length of N 512. Compared to the Gaussian head, in this case (2. 768 64)/(2 512) 95.5 times more parameters are trained for the attention mechanism itself. Only for very long sequences (and given that the word embedding dimension stays the same) the dependence on N may become a disadvantage. But of course, due to the independence from the input the Gaussian averaging head is less expressive in comparison to the original attention mechanism. A recently proposed input independent replacement for self-attention is the so called Random Synthesizer (Tay et al., 2020). Here the dditmax-attention is directly parametrized with an N X N matrix. This amounts to 0.5 N more parameters than Gaussian averaging.
0.012
0,010
0.008
attention
0.006
0.004
0.002
0.000
20
40
60
80
100
120
token
Figure A.6: Attentions of a Gaussian averaging head at initialization for sequence length N = 128. Every line depicts one Gaussian kernel. Here, the location parameters are initialized with the value of the supporting points f4, 84-
A.5.2
EXPERIMENT 2: MULTIPLE INSTANCE LEARNING DATASETS.
A.5.2.1 Immune Repertoire Classification. An architecture called DeepRC, is based on our modern Hopfield networks, for immune repertoire classification and compared to other machine learning approaches. For DeepRC, we consider immune repertoires as input objects, which are represented as bags of instances. In a bag, each instance is an immune receptor sequence and each bag can contain a large number of sequences. At its core, DeepRC consists network that extracts information from each repertoire. The stored patterns (keys) representations of the immune amino acid sequences (instances) that are obtained by an 1D convolutional network with position encoding. Each state pattern (query) is static and learned via backpropagation. For details see Widrich et al. (2020a;b).
modern Hopfield
Our new Hopfield network has been integrated into deep learning architecture for immune repertoire classification, a massive multiple instance learning task (Widrich et al., 2020a;b). Theorem states that modern Hopfield networks possess exponential storage capacity which enables tackle massive multiple instance learning (MIL) problems (Dietterich et al., 1997). Immune repertoire classification (Emerson al., 2017) typically requires extract few patterns from large set of sequences, the repertoire, that are indicative for the respective immune status. Most MIL methods fail due the large number of instances.
Data is obtained by experimentally observed immune receptors as well as simulated sequences sequence motifs (Akbar al., 2019; Weber et al., 2020) with low yet varying degrees of frequency are implanted. Four different categories of datasets are constructed: (a) Simulated immunosequencing data with implanted motifs, (b) immunosequencing data generated by long short-term memory (LSTM) with implanted motifs, (c) real-world immunosequencing data with implanted motifs, and (d) real-world immunosequencing data with known immune status (Emerson et al., 2017). Categories (a), (b), and (d) contain approx. 300,000 instances per immune repertoire. With over 30 billion sequences in total, this represents one of the largest multiple instance learning experiments ever conducted (Carbonneau et al., 2018). Despite the massive number of instances well the low frequency
78

---

of sequences indicative of the respective immune status, deep learning architectures with modern Hopfield networks outperform all competing methods with respect to average area under the ROC curve in all four categories, (a), (b), (c) and (d) (for details see Widrich et al. (2020a)).
We evaluate and compare the performance of DeepRC to a set of machine learning methods that serve as baseline, were suggested, or can readily be adapted immune repertoire classification. The methods comprise (i) known motif, which counts how often the known implanted motifs occur, (ii) Support Vector Machine (SVM) approach that uses fixed mapping from bag of sequences to the corresponding k-mer counts and used the MinMax and Jaccard kernel, (iii) k-Nearest Neighbor (KNN) with k-mer representation, transforming MinMax and Jaccard kernel to distances, (iv) logistic regression on the k-mer representation, (v) burden test that first identifies sequences or k-mers and then computes a burden score per individual, and (vi) logistic multiple instance learning (IMIL). On the real-world dataset DeepRC achieved an AUC of 0.832 + 0.022, followed by the SVM with MinMax kernel (AUC 0.825 0.022) and the burden test with an AUC of 0.699 + 0.041. Overall on all datasets, DeepRC outperformed all competing methods with respect to average AUC (see Widrich et al. (2020a;b)).
Table A. reports the average performance in the simulated immunosequencing datasets (last column) and the performance on datasets of the remaining three categories. DeepRC outperforms all competing methods with respect to average AUC. Across categories, the runner-up methods are either the SVM for MII. problems with MinMax kernel or the burden test.
Real-woord
weal-world data with implansed signals
L.TTM-generaii data
Simulased
CMV
OM 1%
OM 0.1%
MM 1%
MM 0.1%
10%
1%
0.5%
0.1%
0.05%
avg-
DeepRC
0.832 0.022 1.00 = 0.00 0.98+ O.B1 1.00
0.00 0.94
1.00 0.00
1.00
0.00
1,00+
0.00
1.00 0,00
1.00+ 0.00
0.846 0.223
SVM (MM)
0.825 0.022
1.00
0.58.L
0.00
0.5310:02
1.00. 0.00
1.00
1.00
0.00
0.99.
0.827.1 0,210
SVM (J)
0,546 + 0.021 0.99 = 0.00 0.53+ 0.02
1.00=
0.00 0.57+0002
0.98+ 0.04
1.00
0.00
1.00+
0.00
0.90+
0.04
0.77+ 0.07 0.550 0.080
KNN (MM)
0.679 0.076 0.74
0.49+ 0.03 0.67=
0.18 0.50+0002
0.70= 0.27
0.
0.72
0.26
0.73+ 0.26 0.54
0.16 0.52+ 0.35 0.634+ 0.129
KNN (1)
0.534 0.039 0.65 0.16 0.48.LL 0.03 0.70 0.20 0.51.10:03
0.70.1
0.29
0.61
0.24
0.52.1
0.06 0.55 0.19 0.54.L 0.19 0.501 0.007
Log. regr.
0.607 0.258 1.00 = 0.00 0.54+ 0.04
0.99:
12000 0.51
1.00= 0.00
1.00=
0.00
0.93+
0.15 0.60
0.19 0.43+ 0.36 0.826 0.211
Burden test
0.699 0.041 1.00
0.64.1 0.05
0.00 0.8910.02
1.00
1.00.1 0.00
0.79.L 0.549. 0.074
Log. MIL (KMER)
0,582 1: 0.065 0.54 1: 0.00 0,51 0.03
0.99
0,00 0.62.10.15
1.00 0.00
0.72.1
0.11
0.64.1 0.04
0.57.1
0.15 0.53 0.13 D. 0.665 0.224
Log. MIL (TCR3)
0.515 0.073 0.50 0.50 0.02
0.99
1,00 0.78=00.0
0.54#
2009)
0.17
0.47 0.05) 0.51
0.50= 0.32 0.501 0.16
Known motif b.
1.00 1 0,00 0.70.L 0.03
0.99 0.00
0.6210.04
1.00.1
0.00
1.00.1
0.00
1.00.L
0.00
1.00.
0.00
1.00.L 0.00 0.890 0.168
Known motif
0.92 0.00 0.56.1 0.03 0.65 0.00 0,5210.03
1.00.1 0.00 1.00.1 0.00
0.991 0.01 0.72.1 0.09 0.63.L. 0.09 0.738 0.200
Table A.I: Results immune repertoire classification across all datasets. Results are given in terms of AUC of the competing methods on all datasets. The reported errors are standard deviations across 5 cross- validation (CV) folds (except for the column "Simulateed). Real-world CMV: Average performance over 5 CV folds on the cytomegalovirus ( (CMV) dataset Emerson et al. (2017). Real-world data with implanted signals: Average performance over 5 CV folds for each of the four datasets. A signal was implanted with a frequency (=wittness rate) of 1% or 0.1%. Either a single motif ("OM") or multiple motif's ("MM") were implanted. LSTM-generated data: Average performance over 5 CV folds for each of the 5 datasets. In each dataset, signal was implanted with a frequency of 10%. 1%, 0.5%, 0.1%, and 0.05%, respectively. Simulated: Here we report the mean over 18 simulated datasets with implanted signals and varying difficulties. The error reported is the standard deviation of the AUC values across the 18 datasets.
A.5.2.2 Multiple Instance Learning Benchmark Datasets. Classical benchmarking datasets comprise UCSB breast cancer classification (Kandemir et al., 2014), and the Elephant, Fox, Tiger datasets (Andrews et al., 2003).
Elephant, Fox and Tiger are MIL datasets for image annotation which comprise color images from the Corel dataset that have been preprocessed and segmented. An image consists of a set of segments (or blobs), each characterized by color, texture and shape descriptors. The datasets have 100 positive and 100 negative example images. The latter have been randomly drawn from a pool of photos of other animals. Elephant has 1391 instances and 230 features. Fox has 1320 instances and 230 features. Tiger has 1220 instances and 230 features. Furthermore, we use the UCSB breast cancer classification (Kandemir et al., 2014) dataset, which consists of 2,002 instances across 58 input objects. An instance represents a patch of a histopathological image of cancerous or normal tissue. The layer Hopf fee dPool i ng is used, which allows for computing per-input-object representation by
79

---

parameter
values
learning rates
{10-3, 10-33
learning rate decay (Y)
{0.98, 0.96, 0.94]
embedding layers
(1.2.3)
layer widths
{32, 64, 256, 1024, 2048}
number of heads
{8, 12, 16, 16,32)
head dimensions
(16, 32, 64)
scaling factors hidden dimensions bag dropout
{0.1, 1.0, 10.0)
{32, 64, 128]
{0.0, 0.75)
Table A.2: Hyperparameter search-space of a manual hyperparameter selection on the respective validation sets of the Elephant, Fox, Tiger and UCSB breast cancer datasets.
extracting an average of instances that are indicative for one of the two classes. The input to the of embedded instances Y and a trainable but fixed state (query) pattern Q used for averaging of of variable-sizee bags to fixed-sized representation discriminate the bags. We performed manual hyperparameter search on validation set. In detail, we used the following architecture to perform the given task on the Elephant, Fox, Tiger and UCSCB breast cancer datasets: (I) we apply fully connected linear embedding layers with ReLU activation. (II) The output of this embedding serves as the input to our HopfieldPoo molling ing layer where the above described pooling operation is performed. (III) Thereafter we use 'ReLU- Linear blocks' the final linear output layers that perform the classification. Among other hyperparameters, different hidden layer widths (for the fully connected pre- and post-Hop ielddool in layers), learning rates and batch sizes were tried. Additionally our focus resided on the hyperparameters of the Hopfiell dP ool ing layer. Among those were the number of heads, the head dimension and the scaling factor P. All models were trained for 160 epochs using the Adam W optimizer (Loshchilov & Hutter, 2017) with exponential learning rate decay (see Table A.2), and validated by 10-fold nested cross validation repeated five times with different splits on the data sets. The reported ROC AUC scores are the average of these repetitions. As overfitting imposed quite problem, bag dropout was applied the regularization technique of choice.
HopfieldPool lin layer class-indicative instances. This averaging enables a compression
80

---

A.5.3 EXPERIMENT 3: CLASSIFICATION ON SMALL UCI BENCHMARK DATASETS
A.5.3.1 Motivation. Datasets with a small number of samples, like the UCI benchmark datasets, are particularly difficult for neural networks generalize on. In contrast to their performance on larger datasets, they are consistently outperformed by methods like e.g. gradient boosting, random forests (RF) and support vector machines (SVMs). Finding samples even learning prototypes that are highly indicative for the class of a sample (query) suggest the use of Hopfield networks. We applied modern Hopfield network via the layer Hopfiell aepfieldd eld. The input vector is mapped to R using a self-normalizing net (SNN) and W K is learned, where the dimension of WK (the number of stored fixed pattern) hyperparameter. The output Z of Hopfies ld enters the output layer.
A.5.3.2 Methods compared. Modern Hopfield networks via the layer Hopfield compared to 17 groups of methods (Fernández-Delgado et al., 2014; Klambauer et al., 2017a):
1. Support Vector Machines
2. Random Forest
3. Multivariate adaptive regression splines (MARS)
4. Boosting
5. Rule-based Methods
6. Logistic and Multinomial Regression (LMR)
7. Discriminant Analysis (DA)
8. Bagging
9. Nearest Neighbor
10. Decision Trees
11. Other Ensembles
12. Neural Networks (standard NN, BatchNorm, WeighNorm, MSRAinit, LayerNorm, ResNet, Self-Normalizing Nets)
13. Bayesian Methods
14. Other Methods
15. Generalized linear models (GLM)
16. Partial Least Squares and Principal Component Regression (PLSR)
17. Stacking (Wolpert)
A.5.3.3 Experimental design and implementation details. As specified in the main paper, consider 75 datasets of the UC Irvine Machine Learning Repository, which contain less than 1, 000 samples per dataset, following the dataset separation into large and small dataset in Klambauer et al. (2017a). On each dataset, we performed a grid-search to determine the best hyperparameter setting and model per dataset. The hyperparameter search-space of the grid-search is listed in Table A.3. All models were trained for 100 epochs with a mini-batch size of samples using the cross entropy loss and the PyTorch SGD module for stochastic gradient descent without momentum and without weight decay or dropout. After each epoch, the model accuracy was computed on separated validation set. Using early stopping. the model with the best validation set accuracy averaged over 16 consecutive epochs was selected as final model. This final model was then evaluated against a separated test set to determine the accuracy, as reported Tables and Table uci detta i led_rest resul ts. cav in the supplemental materials.
As network architecture, we use {0, 7} fully connected embedding layers with SELU Klambauer et al. (2017a) activation functions and {32, 128, 1024] hidden units per embedding layer. These embedding layers are followed by the layer Hopfield. The number hidden units is also used as number of dimensions for the Hopfield association space with number of [1, 32) heads. The layer Hopfield d is followed by a mapping to the output vector, which has as dimension the number of classes. Finally, the softmax function is applied obtain the predicted probability for class.
81

---

parameter
values
learning rates
{0.05)
embedding layers
{0, [0,1,7}
hidden units
{32, 128, 1024]
heads B # stored patterns
{1,32}
{1.0, 0.1, 0.001) {1,8} n classes
Table A.3: Hyperparameter search-space for grid-search on small UCI benchmark datasets. All models were trained for 100 epochs using stochastic gradient descent with early stopping based on the validation set accuracy and a minibatch size of 4 samples. The number of stored patterns is depending on the number of target classes of the individual tasks.
A.5.3.4 Results. We compared the performance of 25 methods based on their method rank. For this we computed the rank per method per dataset based on the accuracy on the test set, which was then averaged over all 75 datasets for each method to obtain the method rank. For the baseline methods we used the scores summarized by (Klambauer et al., 2017a).
82

---

parameter
values
beta
{0.0001, 0.001, 0.01, 0.1, 0.2, 0.3)
learning rates
{0.0002)
heads
{1,32, 32, 128, 512] {0.0, 0.1,0.0..022
dropout
state-pattern bias
{0.0, -0.125, 0.15, 0.23
association-aativation state- and stored-paad pateeerpparrnn static normalize state- and stored -toted-pateer normalize association projection learnable stored-pattern
[None, LeakyReLU } (False, True)
(False, True)
(False, True)
(False, True)
Table A.4:
Hyperparameter search-space for geir-hearch on HIV, BACE, BBBP and SIDER. All models were trained if applicable for epochs using Adam and batch size of sample.
A.5.4 EXPERIMENT 4: DRUG DESIGN BENCHMARK DATASETS
Experimental design and implementation details. We test Hopfield layers on 4 clas- sification datasets from MoleculeNet (Wu et al., 2017), which are challenging for deep learning methods. The first dataset is HIV, which was introduced by the Drug Therapeuties Program (DTP) AIDS Antiviral Screen. The second dataset is BACE, which has ICS0 measurements for binding affinities of inhibitors (molecules) to the human 3-secretase (BACE-1). The third dataset is BBBP (blood-brain barrier permeability), which stems from modeling and predicting the blood-brain barrier permeability (Martins et al., 2012). The fourth dataset SIDER (Side Effect Resource) Kuhn et al. (2016) and contains 1427 approved drugs. These datasets represent four areas of modeling tasks in drug discovery, concretely develop accurate models for predicting a) new anti-virals (HIV), b) new protein inhibitors (BACE), c) metabolic effects (BBBP), and d) side effects of a chemical compound (SIDER).
A.5.4.1
We implemented Hopfield layer Hopfie fe dlayer, in which we used the training-inpur as stored- pattern Y or key, the training-label pattern-pne pnttern-rojecctoo Y Wy or value and the input as state-pattern R query. As described in section A.6 by concatenation of input z; and target & the matrices W and Wy can be designed such that inside the softmax the input z; is used and outside the softmax the target t,
All hyperparameters were selected on separate validation sets and we selected the model with highest validation AUC on five different random splits.
A.5.4.2 Results. We compared the Hopfield layer Hopfieldlayer to Support Vector Ma- chines (SVMs) (Cortes & Vapnik, 1995; Schölkopf & Smola, 2002), Extreme Gradient Boosting (XGBoost) (Chen Guestrin, 2016), Random Forest (RF) (Breiman, 2001), Deep Neural Net- works (DNNs) (LeCun et al., 2015; Schmidhuber, 2015), and to graph neural networks (GNN) like Graph Convolutional Networks (GCNs) (Kipf Welling, 2016), Graph Attention Networks (GATs) (Veličković et al., 2018), 8), Message Passing Neural Networks (MPNNs) (Gilmer et al., 2017), and Attentive FP (Xiong et al., 2020). Our architecture with Hopfiel eeiaylde has reached state-of-thee art for predicting side effects SIDER 0.672 + 0.019 well for predicting 8-secretase BACE 0.902 + 0.023. See Table A.5 for all results, where the results other methods are taken from Jiang al. (2020).
83

---

Table A.5: Results on drug design benchmark datasets. Predictive performance (ROCAUC) on test set as reported by Jiang et al. (2020) for 50 random splits
Model
HIV
BACE
BBBP
SIDER
SVM
0.822 + 0.020
0.893 = 0.020
0.919 + 0.028
0.630 0.021 0.021
XGBoost
0.816 = 0.020
0.889 = 0.021
0.926 - 0.026
0.642 - 0.020
RF
0.820 + 0.016
0.890 = 0.022
0.927 = 0.025
0.646 0.022
GCN
0.834 + 0.025
0.898 = 0.019
0.903 0.027
0.634 0.026
GAT
0.826 + 0.030
0.886 = 0.023
0.898 0.033
0.627 + 0.024
DNN
0.797 + 0.018
0.890 = 0.024
0.898 + 0.033
0.627 + 0.024
MPNN
0.811 + 0.031
0.838 = 0.027
0.879 0.037
0.598 0.031
Attentive FP
0.822 + 0.026
0.876 = 0.023
0.887 + 0.032
0.623 0.026
Hopfield (ours)
0.815 0.023
0.902 = 0.023
0.910 0.026
0.672 + 0.019
A.6
PYTORCH IMPLEMENTATION OF HOPFIELD LAYERS
The implementation is available at: https: /gtgttttthttttggeggggegg....e
A.6.1 INTRODUCTION
In this section, describe the implementation of Hopfield layers in PyTorch (Paszke al., 2017; 2019) and, additionally, provide brief usage manual. Possible applications for a Hopfield layer in deep network architecture comprise:
multiple instance learning (MIL) (Dietterich et al., 1997),
processing of and learning with point sets (Qi et al., 2017a;b; Xu et al., 2018),
set- based and permutation invariant learning (Guttenberg et al., 2016; Ravanbakhsh et al., 2016; Zaheer et al., 2017; Korshunova al., 2018; Ilse et al., 2018; Zhai al., 2020),
attention-based learning (Vaswani et al., 2017a),
associative learning,
natural language processing,
sequence analysis and time series prediction, and
storing and retrieving reference or experienced data, e.g. to store training data and retrieve by the model or store experiences for reinforcement learning.
The Hopfield layer in deep neural network architecture can implement:
memory (storage) with associative retrieval (Danihelka et al., 2016; Ba al., 2016a),
conditional pooling and averaging operations (Wang al., 2018; Ilse et al., 2020),
combining data by associations (Agrawal et al., 1993),
associative credit assignment (e.g. Rescorla- Wagner model value estimation) (Sutton & Barto, 2018), and
attention mechanisms (Vaswani et al., 2017a; Babdanau et al., 2014).
In particular, a Hopfield layer can substitute attention layers in architectures of transformer and BERT models. The Hopfield layer is designed to be used as plug-in replacement for existing layers like
pooling layers (max-pul mmax-pooling or average pooling).
permutation equivariant layers (Guttenberg et al., 2016; Ravanbakhsh al., 2016),
GRU & LSTM layers, and
attention layers.
84

---

In contrast to classical Hopfield networks, the Hopfield layer is based the modern Hopfield networks with continuous states that have increased storage capacity, as discussed in the main paper. Like classical Hopfield networks, the dynamics of the single heads of Hopfield layer follow energy minimization dynamics. The energy minimization empowers our Hopfield layer with several advantages over other architectural designs like memory cells, associative memory, attention mechanisms. For example, the Hopfield layer has more functionality than transformer self-attention layer (Vaswani et al., 2017a) as described Sec. A.6.2. Possible use cases are given in Sec. A.6.3. Source code will be provided under github.
A.6.2 FUNCTIONALITY
Non-standard functionalities that are added by Hopfield layer are
Association of two sets,
Multiple Updates for precise fixed points,
Variable Beta that determines the kind of fixed points,
Dimension of the associative space for controlling the storage capacity,
Static Patterns for fixed pattern search, and
Pattern Normalization to control the fixed point dynamics by norm of the patterns and shift of the patterns.
A functional sketch of our Hopfield layer is shown in Fig. A.7.
Association of two sets. The Hopfield layer makes it possible to associate two sets vectors. This general functionality allows
for transformer-like self self-attention,
for decoder-encoder attention,
for time series prediction (maybe with positional encoding),
for sequence analysis,
for multiple instance learning,
for learning with point sets,
for combining data sources by associations,
for constructing a memory,
for averaging and pooling operations, and for many more.
The first set of vectors consists S raw state patterns R = (ri...., rT) with r, E Rd and the second set of vectors consists of N raw stored patterns Y (31 (y)..... yN) with y; R Both the raw state patterns and N raw stored patterns are mapped to an associative space in Rdz via the matrices We E Rdd and Wx E Rdd, respectively. We define matrix Q (= of state patterns & Worn in associative space Rd and matrix K (XT) of stored patterns æ; W ky. in the associative space Rdd
Q = RWQ.
(549)
K = X = Y
(550)
In the main paper, Eq. (3) defines the novel update rule:
new = f(E) = X softmax(3 x
(551)
For multiple patterns, Eq. (3) becomes:
E new
[()) X softmax(3 xT xT=)
(552)
85

---

where = = -E1,... ( is the matrix of N state (query) patterns, X is the matrix of stored (key) patterns, and geew is the matrix of new state patterns, which are averages over stored patterns. A new state pattern can also be very similar to single stored patter, in which case we call the stored pattern to be retrieved.
These matrices allow to rewrite Eq. (552) as:
(Quew? K softmax( K Q²).
(553)
For 3 = 1/ dy and changing in Eq. (553) softmax E R to a row vector (and evaluating a row vector), we obtain:
Q quew softmax(1//dd Q QK")& K,
(554)
where Quew is again the matrix of new state patterns. The new state patterns uee are projected via Wy to the result patterns Z ="ew Wv. where Wy Idd, xdv, With the pattern projection
V = KWv, we obtain the update rule Eq. (10) from the main paper:
Z softmax(1/ Q QK*V
(555)
Multiple Updates. The update Eq. (553) can be iteratively applied to the initial state & of every Hopfield layer head. After the last update, the new states neew are projected via Wy to the result patterns Z = = new Wy. Therefore, the Hopfield layer allows multiple update steps in the forward pass without changing the number of parameters. The number of update steps can be given for every Hopfield head individually. Furthermore, it is possible to set a threshold for the number of updates of every Hopfield head based on || 1- In the general case of multiple initial states E, the maximum over the individual norms is taken.
Variable 3. In the main paper, we have identified 3 as a crucial parameter for the fixed point dynamics of the Hopfield network, which governs the operating mode of the attention heads. In appendix, e.g. in Lemma A7 or in Eq. (102) and Eq. (103), we showed that the characteristics of the fixed points of the new modern Hopfield network are determined by: 3, M (maximal pattern norm), Mmax (spread of the similar patterns), and || m=zll (center of the similar patterns). Low values of B induce global averaging and higher values of 33 metastable states. In the transformer attention, the B parameter is set to = 1/vdd as in Eq. (555). The Hopfield layer. however, allows to freely choose 3 > O, since the fixed point dynamics does not only depend on the dimension of the associative space dg. Additionally, 33 heavily influences the gradient flow to the matrices Wq and WK- Thus, finding the right 3 for the respective application can be crucial.
Variable dimension of the associative space. Theorem AS says that the storage capacity of the modern Hopfield network grows exponentially with the dimension of the associative space. However higher dimension of the associative space also means less averaging and smaller metastable states. The dimension of the associative space trades off storage capacity against the size of metastable states, c.g. over how many pattern is averaged. In Eq. (550) and in Eq. (549), we assumed N raw state patterns
(ri...., TN)" )" and S raw stored patterns Y (y1 .... y ) that are mapped to a da-dimensional associative space via the matrices Wq E R dd and Wx E Rd xdv, respectively. In the associative space Rdd, we obtain the state patterns Q = ET RWQ and the stored patterns K = X = Y WK. The Hopfield view relates the dimension dy to the number of input patterns N that have to be processed. The storage capacity depends exponentially on the dimension de (the dimension of the associative space) and the size to metastable states is governed by this dimension, too. Consequently, d, should be chosen with respect to the number N' of patterns one wants to store and the desired size of metastable states, which is the number of patterns one wants to average over. For example, if the input consists many low dimensional input patterns, it makes sense to project the patterns into higher dimensional space to allow proper fixed point dynamics. Intuitively, this coincides with the construction of a richer feature space for the patterns.
Static Patterns. In Eq. (550) and Eq. (549), the N raw state patterns R (ri...., TT and S raw stored patterns Y = (y1....,,.. y are mapped to an associative space via the matrices Wq E R4, xdx and WK E IR Xde, which gives the state patterns Q =T RWQ and the stored patterns K x Y WK. We allow for static state and static stored patterns. Static pattern means that the pattern does not depend on the network input, i.e. it is determined by the bias weights and remains constant across different network inputs. Static state patterns allow to determine whether
86

---

particular fixed patterns among the stored patterns and vice versa. The static pattern functionality is typically needed particular patterns must be identified in the data, e.g. as described for immune repertoire classification in the main paper, where fixed dy -d-menniiooall state vector is used.
Pattern Normalization. In the appendix, c.g. in Lemma A7 or in Eq. (102) and Eq. (103), we showed that the characteristics of the fixed points of the new modern Hopfield network are determined by: 3, M (maximal pattern norm), mmax (spread of the similar patterns), and || mm (center of the similar patterns). We already discussed the parameter while the spread of the similar patterns mmax is given by the data. The remaining variables M and m. that both control the fixed point dynamics are adjusted pattern normalization. M is the maximal pattern norm and my the center of the similar patterns. Theorem A5 says that larger M allows for more patterns to be stored. However, the size of metastable states will decrease with increasing M. The vector my says how well the (similar) patterns are centered. If the norm ||>>] || is large, then this leads to smaller metastable states. The two parameters M and my are controlled by pattern normalization and determine the size and convergence properties of metastable states. These two parameters are important for creating large gradients if heads start with global averaging which has small gradient. These two parameters can shift head towards small metastable states which have largest gradient shown in Fig. A.5(b). We allow for three different pattern normalizations:
pattern normalization of the input patterns,
pattern normalization after mapping into the associative space,
no pattern normalization.
The default setting is a pattern normalization of the input patterns.
A.6.3 USAGE
As outlined in Sec. A. there are a variety of possible use cases for the Hopfield layer, e.g. to build memory networks transformer models. The goal of the implementation is therefore to provide an easy to use Hopfield module that can be used a wide range of applications, be it as part of a larger architecture or as standalone module. Consequently, the focus of the Hopfield layer interface is set on its core parameters: the association of two sets, the scaling parameter B, the maximum number of updates, the dimension of the associative space, the possible usage of static patterns, and the pattern normalization. The integration into the PyTorch framework is and the
built such that with all the above functionalities disabled, the EnoofieidEncoderlLyye both extensions of the Hopfield module, can be used as one-to-one plug-in replacement for the munnforrmerEncoder... the Py Torch transformer module.
"HHopfieldDecoderlLyyeee
and the Trunsfomerreccodeettayeer respectively, of
The Hopfield layer can be used to implement or to substitute different layers:
Pooling layers: We consider the Hopfield layer pooling layer if only one static state (query) pattern exists. Then, it is de facto a pooling over the sequence, which results from the softmax values applied on the stored patterns. Therefore, our Hopfield layer can act as a pooling layer.
Permutation equivariant layers: Our Hopfield layer can be used as plug-in replacement for permutation equivariant layers. Since the Hopfield layer is an associative memory assumes no dependency between the input patterns.
GRU & LSTM layers: Our Hopfield layer can be used as a plug-in in replacement for GRU & ..STM layers. Optionally, for substituting GRU& & L.TTM layers, positional encoding might be considered.
Attention layers: Our Hopfield layer can act as an attention layer, where state (query) and stored (key) patterns are different, and need to be associated.
Finally, the extensions of the Hopfield layer are able to operate as a self-attention layer (HopfieldEncoderl Layer) and as cross-attention layer (HopffeldDecaderrayyer)) as described in (Vaswani et al., 2017a). As such, it can be used building block of transformer-baee or general architectures.
87

---

yes
multiple no updates
MatMul
Softmax
Mask
Scale
MatMul
MatMul
K
no
no
no
LNorm
LNorm
LNorm
yes
yes
yes
normalize
normalize
normalize
no
no
W no
W o
W
k
yes
yes
yes
project
project
project
no
no
LNorm
LNorm
LNorm
yes
yes
yes
normalize
normalize
normalize
R
Figure A.7: A flowchart of the Hopfield layer. First, the raw state (query) patterns R and the raw stored (key) patterns Y are optionally normalized (with layer normalization), projected and optionally normalized (with layer normalization) again. The default setting is layer normalization of the input patterns, and no layer normalization of the projected patterns. The raw stored patterns Y can in principle be also two different input tensors. Optionally, multiple updates take place in the projected space of Q and K. This update rule is obtained e.g. from the full update Eq. (423) or the simplified update Eq. (424) in the appendix.
88

---

REFERENCES
Y. Abu-Mostafa and J.-M. Stacquee. Information capacity of the Hopfield model. IEEE Transactions on Information Theory, 31, 1985. doi: 10.1 1985.1057069
R. Agrawal, T. Imieliundefinedski, and A. Swami. Mining association rules between sets of items in large databases. SIGMOD Rec., 2202):00-2166, 1993, doi: 10. 10.1145/170036..1000
R. Akbar, P. A. Robert, M. Pavlović, J. R. Jeliazkov, Snapkov, A. Slabodkin, C. R. Weber, I.. Scheffer, E. Miho, I. H. Haff, al. A compact vocabulary of paratope-epitope interactions enables predictability of antibody-antigen binding. bioRxiv, 2019.
F. Alzahrani and A. Salem. Sharp bounds for the lambert function. Integral Transforms and Special Functions, 29( (9(1))9771 2018.
S. Andrews, I. Tsochantaridis, and T. Hofmann. Support vector machines for multiple-instanee learning. In Becker, S. Thrun, and K. Obermayer (eds.), Advances in Neural Information Processing Systems 15, pp. 577-584. MIT Press, 2003.
Ba, G. E. Hinton, V. Mnih, Z. Leibo, and C. lonescu. Using fast weights attend the recent past. In D. D. Lee, M. Sugiyama, U. V. Luxburg, Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems 29, pp. 4331-4339. Curran Associates, Inc., 2016a.
J. Ba, G. E. Hinton, V. Mnih, J. Z. Leibo, and C. Jonescu. Using fast weights to attend to the recent past. ArXiv, 1610.06258, 2016b.
D. Bahdanau, K. Cho, and Y. Bengio. Neural machine translation by jointly learning to align and translate. ArXiv, 1409.0473, 2014. appeared in ICRL. 2015.
A. Banino, A. P. Badia, R. Köster, M. J. Chadwick, V. Zambaldi, D. Hassabis, C. Barry, M. Botvinick, D. Kumaran, and C. Blundell. MEMO: deep network for flexible combination of episodic memories. ArXiv, 2001. 2020.
A. Barra, M. Beccaria, and A. Fachechi. A mechanical approach handle generalized Hopfield neural networks. Neural Networks, 106:205-222, 2018. doi: 10. n0166).. 8.07.010.
H. H. Bauschke and P. L. Combettes. Conver Analysis and Monotone Operator Theory in Hilbert Spaces. Cham: Springer International Publishing, 2nd edition, 2017. ISBN 978-3-319-48310-8.
doi: 3-1199788--319--411---55
Boyd and L. Vandenberghe. Convex Optinization. Cambridge University Press, 7th edition, 2009.
ISBN
Brauchart, Reznikov, Saff, Sloan, G. Wang, and S. Womersley, Random point sets the sphere hole radii, covering, and separation. Experimental Mathematics, 27(1): 62-81, 2018, doi: 10. N0.1000000586488 121..2
I.. Breiman. Random forests. Machine Learning, 45(1):5-32, 2001. doi: 10. 10.1023/A:110093344455
Bruck and V. Roychowdhury. On the number spurious memories in the Hopfield model. IEEE Transactions on Information Theory, 36(2):393-397, 1990.
T. Cai, Fan, and T. Jiang. Distributions of angles in random packing on spheres. Journal Machine Learning Research, 14(21):1837-1864, 2013.
M.-A. Carbonneau, V. Cheplygina, E. Granger, and G. Gagnon. Multiple instance learning: survey of problem characteristics and applications. Pattern Recognition, 77:329 353, 2018.
Marc-André Carbonneau, Eric Granger, Alexandre J. Raymond, and Ghyslain Gagnon. Ro- bust multiple-instanee learning ensembles using random subspace instance selection. Pat- tem Recognition, 58:83 99, 2016. ISSN 0031-3203. doi: http:://doiorg//1.0116/// wwtp:/eeeetttcccceeeeeeeeeeeeeee ctt.s//ceeee////etiiee......
2atcog.2016.03.355. URL http:/ wwtp://wwwweeeeeeee.e...... pi1//00313203113000
89

---

M. Carreira-Perpinie and C. K. I. Williams. An isotropic Gaussian mixture have modes than components, Technical Report EDI-INF-RR-0885, The University Edinburgh, School of Informatics, 2003.
A. Carta, A. Sperduti, and D. Bacciu, Encoding-bans memory modules recurrent neural networks. ArXiv, 2001. 1171,, 2020.
T. Chen and C. Guestrin. XGBoost: A scalable tree boosting system. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 785-794. ACM, 2016. doi: 10. N0.1145293997222999755
Y. Chen, J. Bi, and J. Z. Wang. MILES: Multiple-insterr instance learning via embedded instance selection.
IEEE Transactions on Pattern Analysis and Machine Intelligence,
2006.
Cheplygina, DM Tax, and M Loog. Dissimilarity-base ensembles for multiple instance learning. IEEE transactions neural networks and learning systems, (1(6))1179) 2016.
K. Cho, B. vanMerriënboer, Gulcehre, D. Bahdanau, Bougares, H. Schwenk, and Bengio. Learning phrase representations using RNN encoder-decoder for statistical machine translation. In Proceedings of the Conference on Empirical Methods Natural Language Processing (EMNLP), pp. 1724-1734. Association for Computational Linguistics, 2014. doi: 10.31 10.3115/v/D144-117
K. Clark, M.-T. Luong, Q V. Le, and C. D. Manning. ELECTRA: Pre-training text encoders as discriminators rather than generators. ArXiv, 2003.10555 2020. appeared in ICLR 2020.
C. Cortes and V. Vapnik. Support-vector networks. Machine learning, 20(3):273-297, 1995.
A. Crisanti, D. J. Amit, and H. Gutfreund. Saturation level of the Hopfield model for neural network. Europhysics Letters (EPL), 2(4):337-341, 1986. doi: 10. 1001000099550055/2/2
1. Danihelka, G. Wayne, B. Uria, N. Kalchbrenner, and A. Graves. Associative long short-term memory. In M. F. Balcan and K. Q. Weinberger (eds.), Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 1986-1994, New York, USA, 2016.
M. Daniluk, T. Rocktäschel, J. Welbl, and S. Riedel. Frustratingly short attention spans in neural language modeling. ArXiv, 1702.04521, 2017. appeared in 2017.
M. Dehghani, S. Gouws, O. Vinyals. J. Uszkoreit, and I.. Kaiser. Universal transformers. ArXiv, 000..03119, 2018. Published ICLR 2019.
M. Demircigil, J. Heusel, M. Löwe, S. Upgang, and F. Vermet. On a model of associative memory with huge storage capacity. Journal of Statistical Physics, 168(2):288-29)) 2017.
Devlin, M.-W. Chang, K. Lee, and K. Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding, ArXiv, 1810.04805, 2018.
Devlin, M.-W. Chang, K. Lee, and K. Toutanova. BERT: pre-training of deep bidirectional trans- formers for language understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguisties: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 4171-4186. Association for Computational Linguisties, 2019.
T. G. Dietterich, R. H. Lathrop, and T. Lozano-Pérez. Solving the multiple instance problem with axis axis-parallel rectangles. Artificial Intelligence, 89(1-2):31-7,, 1997.
R. O. Emerson, W. S. DeWitr, M. Vignali, J. Gravley, K. Hu, E. Osborne, C. Desmarais, M. Klinger, C. S. Carlson, J. A. Hansen, et al. Immunosequencing identifies signatures of cytomegalovirus exposure history and AlL--mediteed effects the T cell repertoire. Nature Genetics, 49655, 2017.
M. Fernández-Delgade E. Cemadas, S. Barro, and D. Amorim. Do need hundreds of classifiers to solve real world classification problems? The Journal of Machine Learning Research, 15(1): 3133-3181, 2014.
90

---

V. Folli, M. Leonetti, and G. Ruoeco. On the maximum storage capacity of the Hopfield model. Frontiers in Computational Neuroscience, 10(144), 2017. doi: 10.3889/mncom.216.0014444
B. Gao and L. Pavel. On the properties of the softmax function with application in game theory and reinforcement learning. ArXiv, 1704.00805, 2017.
D. J. H. Garling, Analysis on Polish Spaces and an Introduction to Optimal Transportation. London Mathematical Society Student Texts. Cambridge University Press, 2017. ISBN 1108421571. doi: 10.1017/9781 108377362.
Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning (ICML), volume 70, pp. 1263- 1272. JMLR.org, 2017.
A. Graves, G. Wayne, and I. Danihelka. Neural turing machines. ArXiv, 1410.5401, 2014.
N. Guttenberg, N. Virgo, O. Witkowski, H. Aoki, and R. Kanai. Permutation--quivaarinn neural networks applied to dynamics prediction. arXiv, 1612.04530, 2016.
J. Hertz, A. Krogh, and R. G. Palmer. Introduction to the Theory of Neural Computation. Addison- Wesley Longman Publishing Co., Inc., Redwood City, CA, 1991. ISBN 0201 9201503956.
S. Hochreiter. Untersuchungen zu dynamischen neuronalen Netzen. Diploma thesis, Institut für Infor- matik, Lehrstuhl Prof. Brauer, Technische Universität München, 1991. Advisor: J. Schmidhuber.
Hochreiter and J. Schmidhuber. Long short-term memory. Neural Comput., 93)):1335-1780, 1997.
A. Hoorfar and M. Hassani. Inequalities on the Lambert function and hyperpower function. Journal of Inequalities Pure and Applied Mathematics, 9-2):1-5, 2008.
J. J. Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences. 79(8)22554-2555 1982.
J. J. Hopfield. Neurons with graded response have collective computational properties like those of two-state neurons. Proceedings of the National Academy of Sciences, (110))308883002 1984. doi: 10. 10.1073/pnas.8 htt.//aaa.............. 11.10.30
M. Ilse, J. M. Tomezak, and M. Welling. Attention-based deep multiple instance learning. Interna- tional Conference on Machine Learning (ICML), pp. 3376-3391, 2018.
M. Ilse, J. M. Tomezak, and M. Welling. Deep multiple instance learning for digital histopathology. In Handbook of Medical Image Computing and Computer Assisted Intervention, pp. 521-546. Elsevier, 2020.
D. Jiang, Z. Wu, C.-Y. Hsieh, G. Chen, B. Liao, Z. Wang, C. Shen, D. Cao, J. Wu, and T. Hou, Could graph neural networks learn better molecular representation for drug discovery? comparison study deseriptor-based and graph-based models. Journal of Cheminformatics, 2020. doi: 10.21203/rs.3rrs 81439/v1.
M. Kandemir, C. Zhang, and F. A. Hamprecht. Empowering multiple instance histopathology cancer diagnosis by cell graphs. In International Conference on Medical Image Computing and Computer-Assister Intervention, pp. 228-2222222222 238.235.22 Springer, 2014.
M. M. R. Khan, R. B. Arif, M. A. B. Siddique, and M. R. Oishe. Study and observation of the variation of accuracies of KNN, SVM, LMÑN, ENN algorithms on eleven different datasets from UCI machine learning repository. In 4th International Conference on Electrical Engineering and Information & Communication Technology (iCEECCT), pp. 124-129. IEEE, 2018.
T. N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks, ArXiv, 1609.02907, 2016. in International Conference On Learning Representations (ICLR) 2017.
G. Klambauer, T. Unterthiner, A. Mayr, and S. Hochreiter. Self-normalizing neural networks. In Advances in Neural Information Processing Systems, pp. 971-980, 2017a.
91

---

G. Klambauer, T. Unterthiner, A. Mayr, and S. Hochreiter. Self-normalizing neural networks. ArXiv, 1706.02515, 2017b.
P. Koiran. Dynamics of discrete time, continuous state Hopfield networks. Neural Computation, 6(3): 459-468, 1994. doi: 10.1162/neco.
I. Korshunova, J. Degrave, Huszar, Y. Gal, A. Gretton, and J. Dambre. BRUNO: A deep recurrent model for exchangeable data. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 7190-7198. Curran Associates, Inc., 2018.
D. Krotov and J. J. Hopfield. Dense associative memory for pattern recognition. In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon, and R. Garnett (eds.), Advances in Neural Information Processing Systems, pp. 1172-1180. Curran Associates, Inc., 2016.
D. Krotov and Hopfield. Dense associative memory robust to adversarial inputs. Neural Computation, 30(12)3315133167 2018.
D. Krotov and J. J. Hopfield. Large associative memory problem in neurobiology and machine learning. ArXiv, 2008.06996, 2020.
E. Ş. Küçüüaaşcı and M. G. Baydogan. Bag encoding strategies in multiple instance learning problems. Information Sciences, 467:559-578. 2018.
M. Kuhn, I. Letunic, L. Jensen, and Bork. The SIDER database of drugs and side effects. Nucleic Acids Research, 44(D1):D1075-D107) 2016. doi: 10.1093/nar/gkv 1075.
Y. LeCun, Y. Bengio, and G. Hinton. Deep learning. Nature, 521:436 444, 2015.
T. Lipp and Boyd. Variations and extension of the convex-concave procedure. Optimization and Engineering. 17(2):263-287, 2016. doi: 10.1007/s1 1081--01-9--
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. arXiv preprint
171 2017.
O. Maron and Pézzzo-Pérez. A framework for multiple-instamd learning. In M. I. Jordan, M. J. Kearns, and S. A. Solla (eds.), Advances in Neural Information Processing Systems, pp. 570-576. MIT Press, 1998.
I. F. Martins, A. L. Teixeira, L. Pinheiro, and A. O. Falcao. A Bayesian approach to in silico blood-brain barrier penetration modeling. Journal of Chemical Information and Modeling, 52(6): 1686-1697, 2012. doi: 10.1021/ci3001 24c.
C. Mazza. On the storage capacity of nonlinear neural networks. Neural Networks, 10(4):593-597, 1997. doi: 10. 10.1006/50893-6000 000000888936080000000000----
R. J. McEliece, E. C. Posner, E. R. Rodemich, and S. S. Venkatesh. The capacity of the Hopfield associative memory. IEEE Trans. Inf. Theor, 33(4):461-45) 1987. doi: 18.110./TIT.1987. 1057328.
R. R. Meyer. Sufficient conditions for the convergence of monotonic mathematical programming algorithms. Journal of Computer and System Sciences, 1081):108-121, 1976. doi: 10.1016/ (0022-0000(6))80022-99
F. W. Olver, D. W. Lozier, R. F. Boisvert, and C. W. Clark. NIST handbook of mathematical fimctions. Cambridge University Press, 1 pap/cdr edition, 2010. ISBN 098800221122555
A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang. Z. Vetio, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer. Automatic differentiation in Py PoTchh Workshop Advances in Neural Information Processing Systems (NeurIPS), 2017.
A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein,
L. Antiga, et al. PyTorch: An imperative style, performaeee deep learning library. In Advances in Neural Information Processing Systems, pp. 8026-8037, 2019.
92

---

C. R. Qi, H. Su, M. Kaichun, and L. Guibas. PointNet:
Deep learning point sets for 3d classification and segmentation. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 77-85, 2017a. doi: 10. N0.1109/CVPR.2017..16
C. Qi, Yi, H. Su, and L. J. Guibas. PointNet++: Deep bierarchical feature learning on point sets in metric space. In st International Conference on Neural Information Processing Systems, pp- 5105-51 14. Curran Associates Inc., 2017b.
A. Rangarajan, S. Gold, and E. Mjolsness. A novel optimizing network architecture with applications. Neural Computation, 865):1441-1000, 1996. doi: 10.1 10.1162/neco.19% 1996.8.5.1041.
A. Rangarajan, A. Yuille, and Eric E. Mjolsness. Convergence properties of the softassign quadratic assignment algorithm. Neural Computation, 11(6): 4455-1474, 1999. doi: 10.1162/ 089976699330016313
S. Ravanbakhsh, Schneider, and B. Poczos. Deep learning with sets and point clouds. arXiv, 1611.04500, 2016.
I. Schlag and J. Schmidhuber. Learning to reason with third order tensor products. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 9981-9993. Curran Associates, Inc., 2018.
I. Schlag, P. Smolensky, R. Fernandez, N. Jojic, J. Schmidhuber, and J. Gao. Enhancing the transformer with explicit relational encoding for math problem solving. arXiv, 1910.06611, 2019.
I. Schlag, K. Irie, and J. Schmidhuber. Linear transformers are secretly fast weight memory systems. arXiv, 2102.11174 2021.
J. Schmidhuber. Learning control fast-weight memories: An alternative to dynamic recurrent networks. In Neural Computations, Volume: 4, Issue: 1, pp. 131 - 139. MIT Press, 1992.
Schmidhuber. Deep learning in neural networks: An overview, Neural Networks, 61:85-117, 2015. doi: 0..0016f..eunee.2014..00000
B. Schölkopf and A. J. Smola. Learning with Kernels Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge, MA, 2002.
B. K. Sriperumbudur and G. R. Lanckriet. On the convergence of the concave-convex procedure. In I. Williams, and Culotta (eds.), Advances in
Y. Bengio, D. Schuurmans, J. Lafferty, Neural Information Processing Systems 22, pp. 1759-1767 Curran Associates, Inc., 2009.
G. Subramanian, B. Ramsundar, V. Pande, and R. A. Denny. Computational modeling of 3-Secretase (BACE-1) inhibitors using ligand based approaches. Journal of Chemical Information and Modeling, 16(10):1936-1949 2016. doi: wa..00//aac.jcimm660000
S. Sukhbaatar, A. Szlam, Weston, and R. Fergus. End-to-end memory networks. In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett (eds.). Advances in Neural Information Processing Systems 28, pp. 2440-2448. Curran Associates, Inc., 2015a.
Sukhbaatar, Szlam, J. Weston, and Fergus. End-to-end memory networks. ArXiv, 1503.08895, 2015b.
R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. MIT Press, Cambridge, MA, 2 edition, 2018.
F. Tanaka and S. F. Edwards. Analytic theory of the ground state properties of spin glass. Ising spin glass. Journal of Physies F: Metal Physics, (0(12):7769277) 27788 1980. doi: 00.1088/0305-4008/000 12/017.
Y. Tay, D. Bahri, D. Metzler, D.-C. Juan, Z. Zhao, and C. Zheng. Synthesizer: Rethinking self- attention in transformer models. ArXiv, 2005.00743, 2020.
93

---

M. Toneva and L. Wehbe. Interpreting and improving natural-language processing (in machines) with natural Saaguage--rocesseee
(in the brain). In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Buu E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. 14954-1444 19954-14644. 14964. Curran Associates, Inc., 2019a.
M. Toneva and L. Wehbe. Interpreting and improving natural-language processing (in machines) with natural geeguagg-processingg (in the brain). arXiv, 1905.11833. 2019b.
Torres, L. Pantic, and Hilbert H. Kappen. Storage capacity of attractor neural networks with depressing synapses. Phys. Rev. E, 66:061910, 2002. doi: 10. 105/PhysRewE.66.061990
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polo- sukhin. Attention all you need.
Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, Advances in Neural Information Processing Systems 30, pp. 5998-6008 Curran Associates, Inc., 2017a.
S. Vishwanathan, and R. Gamett
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L.. Kaiser, and I. Polosukhin. Attention all you need. ArXiv, 1706.03762. 2017b.
Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. arXiv, 1710,10903, 2018. in International Conference On Learning Representations (ICLR) 2018.
M. Wainberg, B. Alipanahi, and B. J. Frey. Are random forests truly the best classifiers? The Journal of Machine Learning Rexearch, 17(1):3837-3841, 2016.
G. Wainrib and Touboul. Topological and dynamical complexity of random neural networks. Phys. Rev. Lett., 110:1 100:181011 18101, 2013. doi: 10. 10311/yyseeeeLet...II 10. 18101.
J. Wang. Solving the multiple-instance problem: lazy learning approach. In Proceedings of the 17th International Conference on Machine Learning (ICML), 2000.
X. Wang, Y. Yan, P. Tang, X. Bai, and W. Liu. Revisiting multiple instance neural networks. Pattern Recognition, 74:15 24, 2018.
C. R. Weber, R. Akbar, A. Yermanos, M. Pavlović, I. Snapkov, G. K. Sandve, S. T. Reddy, and V. Greiff. immuneSIM: tunable multi-feature simulation of B- and T-cell receptor repertoires for immunoinformatics benchmarking. Bioinformatics, 36(11):3594-359) 2020. doi: 10.1093/ bioinformaticss/taal..88
Weston, S. Chopra, and A. Bordes. Memory networks. ArXiv, 1410.3916, 2014.
M. Widrich, Schäfl, M. Pavlović, H. Ramsauer, L. Gruber, M. Holzleitner, Brandstetter, G. K. Sandve, V. Greiff, S. Hochreiter, and G. Klambauer. Modern Hopfield networks and attention for immune repertoire classification. ArXiv, 2007.13505. 2020a.
M. Widrich, Schäfl, M. Pavlović, Ramsauer, L. Gruber, M. Holzleitner, Brandstetter, G. K. Sandve, V. Greiff, S. Hochreiter, and G. Klambauer. Modern Hopfield networks and attention for immune repertoire classification. In Advances in Neural Information Processing Systems. Curran Associates, Inc., 2020b.
T. Wolf, L. Debut, V. Sanh, J. Chaumond, C. Delangue, A. Moi, P. Cistac, T. Rault, R. Louf, M. Funtowicz, and J. Brew. HuggingFace's transformers: State-of-the-art natural language processing. ArXiv, 1910.03771, 2019.
C. F. Wu. On the convergence properties of the em algorithm. Ann. Statist., 11(1):95-103, 1983. doi: 0..211///0///776346666
X. Wu, X. Liu, W. Li, and Q Wu. Improved expressivity through dendritic neural networks. In S. Bengio, Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), Advances in Neural Information Processing Systems 31, pp. 8057-8068. Curran Associates, Inc., 2018.
Z. Wu, B. Ramsundar, E. N. Feinberg, J. Gomes, C. Geniesse, A. S. Pappu, K. Leswing, and V. Pande. MoleculeNet: benchmark for molecular machine learning. arXiv, 1703.00564, 2017.
94

---

Z. Xiong, D. Wang.
X. Liu, F. Zhong, X. Wan, X. Li, Z. Li, X. Luo, K. Chen, H. Jiang, and M. Zheng. Pushing the boundaries of molecular representation for drug discovery with the graph attention mechanism. Journal Medicinal Chemistry, 63(16):8749-8766 2020. doi: 10. ja1002/aesjjeeddhhem..oboo
Y. Xu, T. Fan, M. Xu, L. Zeng, and Y. Qiao. SpiderCNN: Deep learning on point sets with parameterized convolutional filters. In V. Ferrari, M. Hebert, Sminchisescu, and Weiss (eds.), European Conference on Computer Vision (ECCV), pp. 90-105, Springer International Publishing. 2018.
A. L. Yuille and A. Rangarajan. The concave-convex procedure (CCCP). In T. G. Dietterich, S. Becker, and Z. Ghahramani (eds.). Advances in Neural Information Processing Systems 14, pp. 1033-1040. MIT Press, 2002.
A. L. Yuille and A. Rangarajan. The concave-convex procedure. Neural Computation, 15(4):915-936.
2003. doi: 10.1 1111666669996666655888888888888 1958.
M. Zaheer, Kottur, S. Ravanbakhsh, Poczos, R. R. Salakhutdinov, and A. Smola. Deep sets. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances Neural Information Processing Systems 30, pp. 3391-3401. Curran Associates, Inc., 2017.
W. Zangwill. Nonlinear programming: unified approach. Prentice Hall international series in management. Englewood Cliffs, N.J., 1969. ISBN 9780136235798.
S. Zhai, W. Talbott, M. A. Bautista, C. Guestrin, and J. M. Susskind. Set distribution networks: generative model for of images. arXiv, 2006. 10705, 2020.
W. Zhang and Zhou. Learning to update auto-associative memory recurrent neural networks for improving sequence memorization. ArXiv, 1709.06493, 2017.
Y. Zhu, R. Kiros, R. S. Zemel, R. Salakhutdinov, R. Urtasum, A. Torralba, and S. Fidler. Aligning books and movies: Towards story-like visual explanations by watching movies and reading books. Proceedings of the IEEE international conference on computer vision, pp- 19-27, 2015. arXiv 1506.06724.
95


Reviews:
[{"review_id": "z4pH0FlkxHI", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces a new Hopfield network which have continuous states and propose update rules for optimizing it. It also draws connections between the new model and attention mechanism used in transformers. Small scale empirical study is presented.\n\nOverall I like the technical contribution of the work but feel the paper could be revised to improve clarity about the optimization in the new proposed variant of hopfield networks. Below some specific comments:\n\nPros:\n- connecting hopfield networks to attention mechanism and drawing out the variants in section 3 (as hopfield layers) is useful\n- The exposition in section 1 and 2 where the authors describe the hopfield network with continuous states is written well (although I do feel the motivation behind update equations could be explained a bit better)\n\nCons:\n- As I mentioned earlier, I don't fully understand the intuition behind convergence in one update. Can the authors clarify this? Also the paper mentions update rule in eqn (5) converges after one update for well separated patterns. What happens to the updates / optimization when the patterns are not well separated? This should be discussed after equation (5). Maybe present different scenarios to make it clear.\n\n- Empirical study is limited in my opinion and can be improved. Is the trend in Fig 2 observed across more or less across all datasets? Can the authors comment on this? I like the visualization in the figure but it is bit hard to interpret (perhaps a more clearer label for it could help with that). \n\nOther comments:\n- The idea of separated patterns leads me to ask this question: is there any connection of this work to max-margin classifiers / kernel methods?\n\n- Did the authors consider what would happen if non-linear transformations (e.g. activation functions in DNNs) are applied on top of the inputs? How does the existing network change in that case?\n\n- Can the authors comment on the utility / challenges in applying their proposed method on datasets / tasks beyond the small scale UCI datasets used in their experiments? e.g. using them in large scale language modeling tasks where transformers are popular right now.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "d0DwejhNgq", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work extends the binary Hopfield network (Demircigil et al., 2017) to continuous patterns and states. Connections are drawn between the result model to the attention layers of the transformers, the pooling operation of LSTM, similarity search, and fully connected layers. Experimental results are briefly described for analyzing the attention of Bert models, multiple instance learning, and small UCI classification tasks.\n\nThe proposed model seems very interesting, and the proposed applications seem reasonable at a very high level. However, there is just not enough detail in this paper for me to understand how the models are implemented or why the model works better than other approaches.\n\nFor example, section 3 declared 3 types of Hopfield layers, but without any formal definitions to them, or how they are integrated to the proposed models. The experiment section compares performances with existing models, but lacks any analysis of why the proposed models work better. Similarly, there is a lack of motivation/intuition in the introduction section.\n\n## After author feedback ##\nThanks for the paper update, and now I have a better understanding of the proposed approach. I have updated my review to the following:\n\nPreviously Widrich+ (2020) showed that integrating transformer-like attention (or equivalently modern Hopfield networks based on softmax)  into deep learning architectures outperforms existing methods (kNN and logistic regression) for massive MIL such as immune repertoire classification. More specifically a pooling layer can be formed by attending over a repertoire of instances with a fixed (but learnable) query vector.\n\nThis work provides theoretical analysis of such a layer for its energy function, convergence of updates, and storage capacity, and points to directions of how such a layer can be understood and controlled. It extends the previous experiment:\n1) apply HopfieldPooling (attention with fixed learnable query Q) to more MIL datasets (animal image and breast cancer)  and achieve state of the art results. \n2) apply Hopfield (attention) to 75 small UCI benchmarks replacing feedforward nets. Here Selu units (Klambauer+ 2017) are used to map input to storage Y  and query R. The result is quite positive beating previous approaches including SVM, random forest, and SNN (Klambauer+ 2017)\n3) apply HopfieldLayer (attention with fixed training data Y as storage) to 4 drug design tasks  acting as an instance-based learning approach.\n\nThe result seems quite interesting indicating that general purpose layers such as  feedforward, pooling and nearest neighbors can be improved (in terms of robustness, learnability, or controllability) by adding attention like operations.\n\nI think the paper can talk less about existing results, and focus more on the new results and their analysis:\n- remove [Immune Repertoire Classification] result since it is from previous work.\n- move the Drug Design experiment details to the main text, and add some comment about under what condition Hopfield outperforms/underperforms RF.\n- for the UCI benchmark experiment the transformer layer (Vaswani+ 2017) seems to be a natural baseline and should be compared to. \n\nSuggestions for the presentation:\n- Should only in the future work section state that Hopfield can potentially substitute LSTMs or GRUs, since it is all hypothetical with no experiment result at this point.\n- The word \"implemented\"  in Section 4 seems misleading as there is nothing changed in the Bert model structure? \"Transformer and BERT models can be implemented by the layer Hopfield.\"  \n- Can be more specific in descriptions. For example in the description of (2) Layer HopfieldPooling and (3) Layer HopfieldLayer in Section 3, R and  W_K can be  referenced again for \"state (query) patterns \" and \"The stored (key) patterns\" respectively.\n- It is probably more informative to replace figure 1 with a table to directly compare the energy function and updating rules of different Hopfield nets--i.e., classical, exponential and attention.\n- Avoid using \"x\" in equation 1, since the symbol has already been used for the stored patterns.\n- \"HopfieldLayer\" seems to be a very strange name.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "DzD5Lil_BJT", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers a continuous version of the classical Hopfield network (HN) model.In contrast to well studied discrete models where the patterns (vectors) that are \nstored are discrete, this paper studied continuous vectors and a new continuous energy function.\nConvergence results to a fixed point are proven for the new rule, and it is shown that for the case of random patterns, the Hopfield network can memorize exponentially many patterns (with high probability).  Finally several implementations are given showing how incorporating the new Hopfield net in classification tasks can improve classification accuracy in regimes where \ndata is scarce and where neural networks do not fare well. \n\nThe paper is rather long and I did not verify all results. The description appears sound.The proofs appear non-trivial and rather technical. While the results here are nontrivial I was left me wondering about the \nadded value of this new model. One of the biggest advantages of HN was its simplicity and elegance. More recent results of Hopfield and others with higher degree energy functions managed to maintain this clarity and brevity. The new model however is significantly more involved. It was not clear to me what is gained by this greater complexity and whether the gains \njustify the larger complexity. In actual implementations very limited precision is often necessary.How does this discretization influence the continuous model? How robust is it to rounding errors? Don't we get \"old\" discrete models in disguise? \n\nThe (impressive) empirical results raise similar questions. Can't we use old discrete HN instead of the new model and achieve similar results? It would be perhaps more informative to compare different HN to the new model presented in this paper. It seems a bit strange that previous uses of HN (discrete ) did not achieve such an improvement in previous studies. It would be beneficial to add more on related work in this area. \n\n The authors might consider breaking their long paper to two different sections, one presenting the theoretical advantages of their new model and the other focusing on practical benefits. \n\nFinally, the nature of convergence to a fixed point wasn't clear to me. It seems likely that if patterns are not random convergence can take a long time as is the case for discrete HN. \nSome recent work about the complexity of finding fixed points of continuous functions may be relevant here:A converse to Banach's fixed point theorem and its CLS-completeness.\nMore specific comments:\n1) The paper starts with a rather lengthy discussion of previous work. \nI would recommend outlining the contributions of this paper earlier on. \n2) \"converge in one update step with exponentially low error and have storage capacity proportional to...\" It was not clear to me that random patterns are considered here. \n3) \"proven for c= 1.37andc= 3.15 in Theorem 3\" for what c exactly is the result proven? \n4) \"Furthermore, with a single update, the fixed point recovered with high probability\"I presume this is true for random patterns? \n5) Is beta>0?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The novelty of the paper are:
+ introduces a new Hopfield network with continuous states, hence can be learned end-to-end differentiation and back propagation.
+ derives efficient update rules
+ reveals a connection between the update rules and transformers
+ illustrate how the network can be used as a layer in deep neural network that can perform different functions

The presentation was clear enough for the reviewers to understand and appreciate the novelty, although there were a few points of confusion. I would recommend the authors to address several suggestions that came up in the discussions including:
- additional analysis to highlight when and how the networks is able to outperform other competing models
- intuitions about the proofs for the theorems (okay to leave the detailed derivation in the appendix)



Decision: Accept (Poster)