Hopfield Networks is All You Need

Introduction

Contribution of this work: (i) introducing novel deep learning layers that are equipped with a memory via modern Hopfield networks, (ii) introducing a novel energy function and a 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 as associative memories that can store and retrieve patterns (Hopfield, 1982). A query pattern can retrieve the pattern to which it is most similar or an average over similar patterns. Hopfield networks seem to 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 on increasing the storage capacity of Hopfield networks. In a $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 a 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 is about $0.138d$ (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)$ (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)=x^{2}$. Modern Hopfield networks, also called “dense associative memory” (DAM) models, use an energy function with interaction functions of the form $F(x)=x^{n}$ and, thereby, achieve a storage capacity proportional to $d^{n-1}$ (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 $2^{d/2}$, where all stored binary patterns are fixed points but the radius of attraction vanishes (Demircigil et 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 ($\epsilon$-close to the fixed point) with an exponentially low error and has a storage capacity proportional to $c^{\frac{d-1}{4}}$ (reasonable settings for $c=1.37$ and $c=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 as 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 on different benchmark datasets and tasks like immune repertoire classification.

Modern Hopfield Nets with Continuous States

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 et al., 2017). We also propose a new update rule which can be proven to converge to stationary points of the energy (local minima or saddle points).

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).

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.

We assume a failure probability $0<p\leqslant 1$ and randomly chosen patterns on the sphere with radius $M:=K\sqrt{d-1}$. We define $a:=\frac{2}{d-1}(1+\ln(2\beta K^{2}p(d-1)))$, $b:=\frac{2K^{2}\beta}{5}$, and $c:=\frac{b}{W_{0}(\exp(a+\ln(b))}$, where $W_{0}$ is the upper branch of the Lambert $W$ function (Olver et al., 2010, (4.13)), and ensure $c\geq\left(\frac{2}{\sqrt{p}}\right)^{\frac{4}{d-1}}$. Then with probability $1-p$, the number of random patterns that can be stored is

Therefore it is proven for $c\geq 3.1546$ with $\beta=1$, $K=3$, $d=20$ and $p=0.001$ ($a+\ln(b)>1.27$) and proven for $c\geq 1.3718$ with $\beta=1$, $K=1$, $d=75$, and $p=0.001$ ($a+\ln(b)<-0.94$).

The next theorem states that the update rule typically retrieves patterns after one update. Retrieval of a pattern $\bm{x}_{i}$ for fixed point $\bm{x}_{i}^{*}$ and query $\bm{\xi}$ is defined via an $\epsilon$ by ${{\left\|f(\bm{\xi})\ -\ \bm{x}_{i}^{*}\right\|}}<\epsilon$, that is, the update is $\epsilon$-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 $\bm{x}_{i}$ we define its separation $\Delta_{i}$ to other patterns by:

The update rule retrieves patterns with one update for well separated patterns, that is, patterns with large $\Delta_{i}$.

For given $\epsilon$ and sufficient large $\Delta_{i}$, we have ${{\left\|f(\bm{\xi})\ -\ \bm{x}_{i}^{*}\right\|}}<\epsilon$, that is, retrieval with one update.

At the same time, the retrieval error decreases exponentially with the separation $\Delta_{i}$.

The retrieval error ${{\left\|f(\bm{\xi})\ -\ \bm{x}_{i}\right\|}}$ of pattern $\bm{x}_{i}$ is bounded by

and for ${{\left\|\bm{x}_{i}-\bm{x}_{i}^{*}\right\|}}\leqslant\frac{1}{2\ \beta\ M}$ together with ${{\left\|\bm{x}_{i}-\bm{\xi}\right\|}}\leqslant\frac{1}{2\ \beta\ M}$ by

The left part of Eq. (10) is the transformer attention. In the transformer self-attention $\bm{R}=\bm{Y}$, and $\bm{W}_{\bm{K}}\bm{W}_{\bm{V}}$ replaced by just $\bm{W}_{\bm{V}}$. 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 to explain these specific layers.

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: Hopfield, HopfieldPooling, and HopfieldLayer. 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 (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 et al., 2018; Ilse et al., 2018; Zhai et al., 2020),

attention-based learning (Vaswani et al., 2017a),

deep learning with associative memories (Graves et al., 2014; Weston et al., 2014; Ba et al., 2016a; b; Schlag & Schmidhuber, 2018; Schlag et 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).

We consider two types of feed-forward neural networks: (I) Neural networks that propagate an activation vector from the input layer to the output layer. Examples are fully-connected or convolutional neural networks. (II) Neural networks that propagate a set of vectors from the input layer to the output layer, where each layer applies the same operation to each element of the set 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 a set or a 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.

We introduce three types of Hopfield layers: Hopfield, HopfieldPooling, and HopfieldLayer. The continuous modern Hopfield network results in 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, or external data. Next, we provide three useful types of Hopfield layers. The implementation is available at: https://github.com/ml-jku/hopfield-layers

(1) Layer Hopfield for networks that propagate sets of vectors via state (query) patterns $\bm{R}$ and stored (key) patterns $\bm{Y}$. The layer Hopfield is the realization of formula (10). The memory of the Hopfield layer can be filled with sets from the input or 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 Hopfield 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 to be compared. This layer allows for different kinds of sequence-to-sequence learning, point set operations, and retrieval-based methods. The layer Hopfield with skip connections in a ResNet architecture is identical to the popular transformer and BERT models. In the experiments, we analyzed these Hopfield layers in transformer architectures. In our experiments in which we compare machine learning methods on small datasets of the UCI benchmark collection the layer Hopfield is also used.

(2) Layer HopfieldPooling for networks that propagate patterns via the stored (key) patterns $\bm{Y}$. This layer performs a pooling or summarization of sets $\bm{Y}$ obtained from queries in previous layers or the input. The memory of the HopfieldPooling layer is filled with sets from the input or previous layers. The HopfieldPooling layer uses the queries to search for patterns in the memory, the stored set. If more patterns are similar to a particular search pattern (query), then the result is an average over these patterns. The state (query) patterns of 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 HopfieldPooling enables fixed pattern search, pooling operations, and memories like LSTMs or GRUs. The static pattern functionality is typically needed if particular patterns must be identified in the data. A single HopfieldPooling 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 be two-dimensional, where standard convolutional filters can be constructed as in convolutional neural networks (CNNs). The HopfieldPooling layer can substitute pooling, averaging, LSTM, and permutation equivariant layers. See Fig. 4. The layer HopfieldPooling is used for experiments with multiple instance learning tasks, e.g. for immune repertoire classification in the experiments.

(3) Layer HopfieldLayer for networks that propagate a vector or a set of vectors via state (query) patterns $\bm{R}$. The queries $\bm{R}$ can be input vectors or queries that are computed from the output of previous layers. The memory of the HopfieldLayer layer is filled with a fixed set, which can be the training set, a reference set, prototype set, or a learned set (a 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 a 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 HopfieldLayer can substitute a fully connected layer, see Fig. 5. A 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 raw data $\bm{y}_{i}=(\bm{z}_{i},\bm{t}_{i})$ can be the concatenation of input $\bm{z}_{i}$ and target $\bm{t}_{i}$. In this case, the matrices $\bm{W}_{K}$ and $\bm{W}_{V}$ can be designed such that inside the softmax the input $\bm{z}_{i}$ is used and outside the softmax the target $\bm{t}_{i}$. Thus, the softmax provides a 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 HopfieldLayer layer, where the memory is filled with the encoder output set. In our experiments with the drug design benchmark datasets, the layer HopfieldLayer has been applied and compared to other machine learning methods.

The insights about energy, convergence, and storage properties provide all new Hopfield layers with additional functionalities: i) multiple updates to control how precise fixed points are found without additional parameters needed. ii) variable $\beta$ to determine the kind of fixed points such as the size of metastable states. The variable $\beta$ 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 $\beta$ 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 layernorm, the fixed point dynamics by the norm and shift of the patterns. For more details see appendix, Section A.6.

Experiments

We show that our proposed Hopfield layers can be applied successfully to a 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.

For multiple instance learning (MIL) (Dietterich et al., 1997), we integrate our new Hopfield network via the layer HopfieldPooling 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 a promising approach.

•Immune Repertoire Classification. The first MIL task is immune repertoire classification, where a deep learning architecture with HopfieldPooling (DeepRC) was used (Widrich et al., 2020a; b). Immune repertoire classification (Emerson et al., 2017) typically requires to extract few patterns from a large set of sequences, the repertoire, that are indicative for the respective immune status. The datasets contain $\approx$ 300,000 instances per immune repertoire, which represents one of the largest multiple instance learning experiments ever conducted (Carbonneau et al., 2018). 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 experimentally-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 instance learning (lMIL). On the real-world dataset DeepRC achieved an AUC of $0.832\pm 0.022$, followed by the SVM with MinMax kernel (AUC $0.825\pm 0.022$) and the burden test with an AUC of $0.699\pm 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 to further MIL datasets (Ilse et al., 2018; Küçükaşcı & Baydoğan, 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 a patch of a histopathological image of cancerous or normal tissue. The layer HopfieldPooling 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 HopfieldPooling is a set of embedded instances $\bm{Y}$. A trainable but fixed state (query) pattern $\bm{Q}$ is used for averaging over class-indicative instances. This averaging enables a compression of variable-sized bags to a fixed-sized representation to discriminate the bags. More details in appendix Sec. A.5.2. Our approach has set a new state-of-the-art and has outperformed other methods (Küçükaşcı & Baydoğan, 2018; Carbonneau et al., 2016) on the datasets Tiger, Elephant and UCSB Breast Cancer (see Table 1).

So far deep learning struggled with small datasets. However, Hopfield 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 Hopfield on the small datasets of the UC Irvine (UCI) Machine Learning Repository that have been used to benchmark supervised learning methods (Fernández-Delgado 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 to their size, number of features, and difficulties (Fernández-Delgado et al., 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 HopfieldLayer, where a self-normalizing net (SNN) maps the input vector to $\bm{Y}$ and $\bm{R}$. The output $\bm{Z}$ of HopfieldLayer enters a softmax output. We compared our modern Hopfield networks against deep learning methods (e.g. SNNs, resnet), RFs, SVMs, boosting, bagging, and many other machine learning methods of Fernández-Delgado et al. (2014). Since for each method, multiple variants and implementations 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 on the small datasets, setting a new state-of-the-art 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 HopfieldLayer, 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 $\beta$-secretase (BACE) inhibitors 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 HopfieldLayer, where the training data is used as stored patterns $\bm{Y}$, the input vector as state pattern $\bm{R}$, and the corresponding training label to project the output of the Hopfield layer $\bm{Y}\bm{W}_{V}$. Our architecture with HopfieldLayer has reached state-of-the-art for predicting side effects on SIDER $0.672\pm 0.019$ as well as for predicting $\beta$-secretase BACE $0.902\pm 0.023$. For details, see Table A.5 in the appendix.

Conclusion. We have introduced a modern Hopfield network with continuous states and the corresponding 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-art in 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 (LIT-2017-3-YOU-003), and AI-SNN (LIT-2018-6-YOU-214), the Medical Cognitive Computing Center (MC3), Janssen Pharmaceutica, UCB Biopharma, Merck Group, Audi.JKU Deep Learning Center, Audi Electronic Venture GmbH, TGW, Primal, S3AI (FFG-872172), Silicon Austria Labs (SAL), Anyline, FILL, EnliteAI, Google Brain, ZF Friedrichshafen AG, Robert Bosch GmbH, TÜV Austria, DCS, and the NVIDIA Corporation. IARAI is supported by Here Technologies.

Appendix 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.1 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 PyTorch implementation of layers based on the new Hopfield networks and how to use them.

In Section A.1 our new modern Hopfield network is introduced. In Subsection A.1.2 we present the new energy function. Then in Subsection A.1.3, our new update rule is introduced. In Subsection 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 or saddle points) of the energy function. In Section A.1.5, we consider the local convergence of the update rule and see that patterns are retrieved with one update. In Subsection A.1.6, we consider the properties of the fixed points that are associated with the stored patterns. In Subsection A.1.6.1, we show that exponentially many patterns can be stored. The main result is given in Theorem A5: For random patterns on a sphere we can 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, we analyze if the association is learned directly by a bilinear form. In Subsection A.1.7.3, we analyze if stored patterns and query patterns are mapped to the space of the Hopfield network. Therefore, we treat the architecture of the transformer and BERT. In Subsection A.1.8, we introduce a temporal component into the new Hopfield network that leads to a forgetting behavior. The forgetting allows us to treat infinite memory capacity in Subsection A.1.8.1. In Subsection A.1.8.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 on properties of the softmax, the log-sum-exponential, 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 of Krotov and Hopfield is binary, that is, a 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 A.3.1.1, we discuss neural networks that are enhanced by an 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 $\bm{x}_{1},\ldots,\bm{x}_{N}$ that are represented by the matrix

The query or state of the Hopfield network is $\bm{\xi}$.

We start by deriving the lower bound of zero. The pattern most similar to query or state $\bm{\xi}$ is $\bm{x}_{\bm{\xi}}$:

The energy is zero and, therefore, the bound attained, if all $\bm{x}_{i}$ are equal, that is, $\bm{x}_{i}=\bm{x}$ for all $i$ and $\bm{\xi}=\bm{x}$.

as the term involving the logarithm is non-positive.

Next we derive the second upper bound, for which we need the mean $\bm{m}_{\bm{x}}$ of the patterns

where for the first inequality we again applied Lemma A19 with $\bm{z}=(1/N,\ldots,1/N)$ and $\beta^{-1}\sum_{i}1/N\ln(1/N)=-\beta^{-1}\ln(N)$. This inequality also follows from Jensen’s inequality. The second inequality uses the Cauchy-Schwarz inequality. The last inequality uses

A.1.3 New Update Rule

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

where $C_{1}$ does not depend on $\bm{\xi}$.

Although the objective converges in all cases, it does not necessarily converge to a local minimum (Lipp & Boyd, 2016).

However the convergence proof of CCCP in Yuille & Rangarajan (2002; 2003) was not as rigorous as required. In Sriperumbudur & Lanckriet (2009) a rigorous analysis of the convergence of CCCP is performed using Zangwill’s global convergence theory of iterative algorithms.

In Sriperumbudur & Lanckriet (2009) the minimization problem

where $C_{2}$ does not depend on $\bm{\xi}$. Since we do not have constraints, $\bm{\xi}^{t+1}$ is defined as

Since we do not have constraints, $\bm{\xi}^{t+1}$ is the minimum of

For a minimum not at the border, the derivative has to be the zero vector

and the Hessian must be positive semi-definite

where $C_{3}$ does not depend on $\bm{\xi}$.

A.1.5 Local Convergence of the Update Rule: Fixed Point Iteration

For the proof of local convergence to a fixed point we will apply Banach fixed point theorem. For the rate of convergence we will rely on properties of a contraction mapping.

To analyze the local convergence of the iteration, we distinguish between the following three cases (see also Fig. A.1). Here we only provide an informal discussion to give the reader some intuition. A rigorous formulation of the results can be found in the corresponding subsections.

If the patterns $\bm{x}_{i}$ are not well separated, the iteration goes to a fixed point close to the arithmetic mean of the vectors. In this case $\bm{p}$ is close to $p_{i}=1/N$.

If the patterns $\bm{x}_{i}$ are well separated, then the iteration goes to the pattern to which the initial $\bm{\xi}$ is similar. If the initial $\bm{\xi}$ is similar to a vector $\bm{x}_{i}$ then it will converge to a vector close to $\bm{x}_{i}$ and $\bm{p}$ will converge to a vector close to $\bm{e}_{i}$.

If some vectors are similar to each other but well separated from all other vectors, then a so called metastable state between the similar vectors exists. Iterations that start near the metastable state converge to this metastable state.

We begin with a bound on the Jacobian of the iteration, thereby heavily relying on the Jacobian of the softmax from Lemma A24.

If $p_{\max}=\max_{i}p_{i}\geq 1-\epsilon$, then for the spectral norm of the Jacobian holds

With $m=\max_{i}p_{i}(1-p_{i})$, Eq. (476) from Lemma A24 is

The spectral norm ${{\left\|.\right\|}}_{2}$ is bounded by the Frobenius norm ${{\left\|.\right\|}}_{F}$ which can be expressed by the norm squared of its column vectors:

Therefore, we obtain the first statement of the lemma:

With $p_{\max}=\max_{i}p_{i}\geq 1-\epsilon$ Eq. (480) in Lemma A24 is

Using this inequality, we obtain the second statement of the lemma:

We now define the “separation” $\Delta_{i}$ of a pattern $\bm{x}_{i}$ from data $\bm{X}=(\bm{x}_{1},\ldots,\bm{x}_{N})$ here, since it has an important role for the convergence properties of the iteration.

We define $\Delta_{i}$, i.e. the separation of pattern $\bm{x}_{i}$ from data $\bm{X}=(\bm{x}_{1},\ldots,\bm{x}_{N})$ as:

The pattern is separated from the other data if $0<\Delta_{i}$. Using the parallelogram identity, $\Delta_{i}$ can also be expressed as

For ${{\left\|\bm{x}_{i}\right\|}}={{\left\|\bm{x}_{j}\right\|}}$ we have $\Delta_{i}=1/2\min_{j,j\not=i}{{\left\|\bm{x}_{i}\ -\ \bm{x}_{j}\right\|}}^{2}$.

Analog we say for a query $\bm{\xi}$ and data $\bm{X}=(\bm{x}_{1},\ldots,\bm{x}_{N})$, that $\bm{x}_{i}$ is least separated from $\bm{\xi}$ while being separated from other $\bm{x}_{j}$ with $j\not=i$ if

Next we consider the case where the iteration has only one stable fixed point.

We start with the case where no pattern is well separated from the others.

•Global fixed point near the global mean: Analysis using the data center.

is the covariance matrix of data $\bm{X}$ when its vectors are selected according to the probability $\bm{p}$:

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.

$\bm{m}_{\bm{x}}$ is the arithmetic mean (the center) of the patterns. $m_{\max}$ is the maximal distance of the patterns to the center $\bm{m}_{\bm{x}}$ .

The maximal distance to the center $m_{\max}$ allows the derivation of a bound on the norm of the Jacobian.

Next lemma gives a condition for a global fixed point.

For $\beta\ m_{\max}^{2}<1$ there exists a unique fixed point (global fixed point) of iteration $f$ in each compact set.

In order to bound the variance we compute the vector $\bm{a}$ that minimizes

The Hessian of $f$ is positive definite since

and $f$ is a convex function. Hence, the mean

minimizes $\sum_{i=1}^{N}p_{i}{{\left\|\bm{x}_{i}-\bm{a}\right\|}}^{2}$. Therefore, we have

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:

since $\bm{b}\bm{b}^{T}$ has eigenvector $\bm{b}/{{\left\|\bm{b}\right\|}}$ with eigenvalue ${{\left\|\bm{b}\right\|}}^{2}$ and otherwise zero eigenvalues.

We now bound the variance of the patterns:

Therefore, the tightness of the bound depends on 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 $\bm{X}=(\bm{x}_{1},\ldots,\bm{x}_{N})$, we consider the iteration

In particular normalization methods like batch normalization would promote the mean as a fixed point.

We consider the differences of dot products for $\bm{x}_{i}$: $\bm{x}_{i}^{T}\bm{x}_{i}-\bm{x}_{i}^{T}\bm{x}_{j}=\bm{x}_{i}^{T}(\bm{x}_{i}-\bm{x}_{j})$, for fixed point $\bm{m}_{\bm{x}}^{*}$: $(\bm{m}_{\bm{x}}^{*})^{T}\bm{x}_{i}-(\bm{m}_{\bm{x}}^{*})^{T}\bm{x}_{j}=(\bm{m}_{\bm{x}}^{*})^{T}(\bm{x}_{i}-\bm{x}_{j})$, and for the center $\bm{m}_{\bm{x}}$: $\bm{m}_{\bm{x}}^{T}\bm{x}_{i}-\bm{m}_{\bm{x}}^{T}\bm{x}_{j}=\bm{m}_{\bm{x}}^{T}(\bm{x}_{i}-\bm{x}_{j})$. Using the Cauchy-Schwarz inequality, we get

where we used ${{\left\|\bm{\xi}-\bm{0}\right\|}}\leqslant{{\left\|\bm{\xi}-\bm{m}_{\bm{x}}\right\|}}+{{\left\|\bm{m}_{\bm{x}}-\bm{0}\right\|}}$, ${{\left\|\bm{\xi}-\bm{m}_{\bm{x}}\right\|}}={{\left\|\sum_{i}p_{i}\bm{x}_{i}-\bm{m}_{\bm{x}}\right\|}}\leqslant\sum_{i}p_{i}{{\left\|\bm{x}_{i}-\bm{m}_{\bm{x}}\right\|}}\leqslant m_{\max}$, and $M=\max_{i}{{\left\|\bm{x}_{i}\right\|}}$. In particular

Let $i=\arg\max_{j}\bm{\xi}^{T}\bm{x}_{j}$, therefore the maximal softmax component is $i$. For the maximal softmax component $i$ we have:

Analogously we obtain for $i=\arg\max_{j}\bm{m}_{\bm{x}}^{T}\bm{x}_{j}$, a bound on the maximal softmax component $i$ if the center is put into the iteration:

Analog we obtain a bound for $i=\arg\max_{j}(\bm{m}_{\bm{x}}^{*})^{T}\bm{x}_{j}$ on the maximal softmax component $i$ of the fixed point:

The two important terms are $m_{\max}$, the variance or spread of the data and ${{\left\|\bm{m}_{\bm{x}}\right\|}}$, which tells how well the data is centered. For a contraction mapping we already required $\beta m_{\max}^{2}<1$, therefore the first term in the exponent is $2\beta m_{\max}^{2}<2$. The second term $2\beta m_{\max}{{\left\|\bm{m}_{\bm{x}}\right\|}}$ is small if the data is centered.

•Global fixed point near the global mean: Analysis using softmax values.

If $\bm{\xi}^{T}\bm{x}_{i}\approx\bm{\xi}^{T}\bm{x}_{j}$ for all $i$ and $j$, then $p_{i}\approx 1/N$ and we have $m=\max_{i}p_{i}(1-p_{i})<1/N$. For $M\leqslant 1/\sqrt{2\beta}$ we obtain from Lemma A2:

The local fixed point is $\bm{m}_{\bm{x}}^{*}\approx\bm{m}_{\bm{x}}=(1/N)\sum_{i=1}^{N}\bm{x}_{i}$ with $p_{i}\approx 1/N$.

We now treat this case more formally. First we discuss conditions that ensure that the iteration is a contraction mapping. We consider the iteration Eq. (57) in the variable $\bm{p}$:

With $m=\max_{i}p_{i}(1-p_{i})$, Eq. (476) from Lemma A24 is

Since $m=\max_{i}p_{i}(1-p_{i})<\max_{i}p_{i}=p_{\max}$, the previous bounds can be combined as follows:

where we used Eq. (170). ${{\left\|\bm{X}^{T}\bm{X}\right\|}}_{2}={{\left\|\bm{X}\bm{X}^{T}\right\|}}_{2}$, therefore ${{\left\|\bm{X}^{T}\bm{X}\right\|}}_{2}$ is $N$ times the maximal second moment of the data squared.

Obviously, $g(\bm{p})$ is a contraction mapping in compact sets, where

For the 1-norm, we use Lemma A24 and ${{\left\|\bm{p}\right\|}}_{1}=1$ to obtain from Eq. (115):

where $m=\max_{i}p_{i}(1-p_{i})$, $M_{1}={{\left\|\bm{X}\right\|}}_{1}=\max_{i}{{\left\|\bm{x}_{i}\right\|}}_{1}$, $M=\max_{i}{{\left\|\bm{x}_{i}\right\|}}$, ${{\left\|\bm{X}\right\|}}_{\infty}={{\left\|\bm{X}^{T}\right\|}}_{1}=\max_{i}{{\left\|[X^{T}]_{i}\right\|}}_{1}$ (maximal absolute row sum norm), and $M_{\infty}=\max_{i}{{\left\|\bm{x}_{i}\right\|}}_{\infty}$. Let us quickly mention some auxiliary estimates related to $\bm{X}^{T}\bm{X}$:

where the first inequaltiy is from Hölder’s inequality. We used

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 1-norm bound on $J_{s}$. Everything else follows from the fact that the 1-norm is sub-multiplicative as induced matrix norm.

We consider the minimal ${{\left\|\bm{p}\right\|}}$.

The solution to this minimization problem is $\bm{p}=(1/N)\bm{1}$. Therefore, we have $1/\sqrt{N}\leqslant{{\left\|\bm{p}\right\|}}$ and $1/N\leqslant{{\left\|\bm{p}\right\|}}^{2}$ Using Eq. (119) we obtain

We move on to the next case, where the patterns $\bm{x}_{i}$ are well separated. In this case the iteration goes to the pattern to which the initial $\bm{\xi}$ is most similar. If the initial $\bm{\xi}$ is similar to a vector $\bm{x}_{i}$ then it will converge to $\bm{x}_{i}$ and $\bm{p}$ will be $\bm{e}_{i}$. The main ingredients are again Banach’s Theorem and estimates on the Jacobian norm.

•Proof of a fixed point by Banach Fixed Point Theorem.

$\rightarrow$ Mapped Vectors Stay in a Compact Environment. We show that if $\bm{x}_{i}$ is sufficient dissimilar to other $\bm{x}_{j}$ then there is an compact environment of $\bm{x}_{i}$ (a sphere) where the fixed point iteration maps this environment into itself. The idea of the proof is to define a sphere around $\bm{x}_{i}$ for which points from the sphere are mapped by $f$ into the sphere.

We first need following lemma which bounds the distance ${{\left\|\bm{x}_{i}\ -\ f(\bm{\xi})\right\|}}$, where $\bm{x}_{i}$ is the pattern that is least separated from $\bm{\xi}$ but separated from other patterns.

For a query $\bm{\xi}$ and data $\bm{X}=(\bm{x}_{1},\ldots,\bm{x}_{N})$, there exists a $\bm{x}_{i}$ that is least separated from $\bm{\xi}$ while being separated from other $\bm{x}_{j}$ with $j\not=i$:

We now can bound ${{\left\|\bm{x}_{i}\ -\ f(\bm{\xi})\right\|}}$:

We define $\Delta_{i}$, i.e. the separation of pattern $\bm{x}_{i}$ from data $\bm{X}=(\bm{x}_{1},\ldots,\bm{x}_{N})$ as:

The pattern is separated from the other data if $0<\Delta_{i}$. Using the parallelogram identity, $\Delta_{i}$ can also be expressed as

For ${{\left\|\bm{x}_{i}\right\|}}={{\left\|\bm{x}_{j}\right\|}}$ we have $\Delta_{i}=1/2\min_{j,j\not=i}{{\left\|\bm{x}_{i}\ -\ \bm{x}_{j}\right\|}}^{2}$.

Next we define the sphere where we want to apply Banach fixed point theorem.

With $\bm{\xi}$ given, if the assumptions

data point $\bm{x}_{i}$ is well separated from the other data:

Using the Cauchy-Schwarz inequality, we obtain for $1\leqslant j\leqslant N$:

where we used the assumption (A1) of the lemma.

•Banach Fixed Point Theorem. Now we have all ingredients to apply Banach fixed point theorem.

We used that the spectral norm ${{\left\|.\right\|}}_{2}$ is bounded by the Frobenius norm ${{\left\|.\right\|}}_{F}$ which can be expressed by the norm squared of its column vectors:

The norm of Jacobian of the fixed point iteration is bounded

The separation of pattern $\bm{x}_{i}$ from data $\bm{X}=(\bm{x}_{1},\ldots,\bm{x}_{N})$ is

We can bound the spectral norm of the Jacobian, which upper bounds the Lipschitz constant:

Solving this inequality for $\Delta_{i}$ gives

In an environment around $\bm{x}_{i}^{*}$ in which Eq. (183) holds, $f$ is a contraction mapping and every point converges under the iteration $f$ to $\bm{x}_{i}^{*}$ when the iteration stays in the environment. After every iteration the mapped point $f(\bm{\xi})$ is closer to the fixed point $\bm{x}_{i}^{*}$ than the original point $\bm{x}_{i}$:

For large $\Delta_{i}$ the iteration is close to the fixed point even after one update. This has been confirmed in several experiments.

The proof concept is the same as for a single pattern but now for the arithmetic mean of similar patterns.

The Jacobian of the fixed point iteration is

is the covariance matrix of data $\bm{X}$ when its vectors are selected according to the probability $\bm{p}$:

It’s clear that 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.

Furthermore the variance goes to zero as one $p_{i}$ goes to one, since only one pattern is chosen and there is no variance.

The variance is reasonable small if all patterns are chosen with equal probability.

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 is smaller than one.

The first three issues have already been adressed. Now we focus on the last one in greater detail. We assume that the first $l$ patterns are much more probable (and similar to one another) than the other patterns. Therefore, we define:

The variance of the first $l$ patterns is

The spectral norm of an outer product of two vectors is the product of the Euclidean norms of the vectors:

since $\bm{b}\bm{b}^{T}$ has eigenvector $\bm{b}/{{\left\|\bm{b}\right\|}}$ with eigenvalue ${{\left\|\bm{b}\right\|}}^{2}$ and otherwise zero eigenvalues.

We now bound the norms of some matrices and vectors:

In order to bound the variance of the first $l$ patterns, we compute the vector $\bm{a}$ that minimizes

The Hessian of $f$ is positive definite since

and $f$ is a convex function. Hence, the mean

minimizes $\sum_{i=1}^{N}p_{i}{{\left\|\bm{x}_{i}-\bm{a}\right\|}}^{2}$. Therefore, we have

We now bound the variance on the first $l$ patterns:

Combining the previous two estimates immediately leads to Eq. (201).

Therefore, the tightness of the bound depends on eigenvalues which are not the largest. That is variations which are not along the strongest variation weaken the bound.

•Proof of a fixed point by Banach Fixed Point Theorem.

Without restricting the generality, we assume that the first $l$ patterns are much more probable (and similar to one another) than the other patterns. Therefore, we define:

•Mapped vectors stay in a compact environment. We show that if $\bm{m}_{\bm{x}}$ is sufficient dissimilar to other $\bm{x}_{j}$ with $l<j$ then there is an compact environment of $\bm{m}_{\bm{x}}$ (a sphere) where the fixed point iteration maps this environment into itself. The idea of the proof is to define a sphere around $\bm{m}_{\bm{x}}$ for which the points from the sphere are mapped by $f$ into the sphere.

We first need following lemma which bounds the distance ${{\left\|\bm{m}_{\bm{x}}\ -\ f(\bm{\xi})\right\|}}$ of a $\bm{\xi}$ which is close to $\bm{m}_{\bm{x}}$.

For a query $\bm{\xi}$ and data $\bm{X}=(\bm{x}_{1},\ldots,\bm{x}_{N})$, we define

Let $s=\arg\max_{j,j\leqslant l}\bm{\xi}^{T}\bm{x}_{j}$, therefore $\bm{\xi}^{T}\bm{m}_{\bm{x}}=\frac{1}{l}\ \sum_{i=1}^{l}\ \bm{\xi}^{T}\bm{x}_{i}\leqslant\frac{1}{l}\ \sum_{i=1}^{l}\ \bm{\xi}^{T}\bm{x}_{s}=\bm{\xi}^{T}\bm{x}_{s}$. For softmax components $j$ with $l<j$ we have

since $\bm{\xi}^{T}\bm{x}_{s}-\bm{\xi}^{T}\bm{x}_{j}\geq\bm{\xi}^{T}\bm{m}_{\bm{x}}-\bm{\xi}^{T}\bm{x}_{j}$ for each $j$ with $l<j$, therefore $\bm{\xi}^{T}\bm{x}_{s}-\bm{\xi}^{T}\bm{x}_{j}\geq c$

We now can bound ${{\left\|\bm{m}_{\bm{x}}\ -\ f(\bm{\xi})\right\|}}$:

where we applied Eq. (233) in the penultimate inequality. This is the statement of the lemma. ∎

The separation of the center (the arithmetic mean) $\bm{m}_{\bm{x}}$ of the first $l$ from data $\bm{X}=(\bm{x}_{l+1},\ldots,\bm{x}_{N})$ is $\Delta_{m}$, defined as

The center is separated from the other data $\bm{x}_{j}$ with $l<j$ if $0<\Delta_{m}$. By the same arguments as in Eq. (140), $\Delta_{m}$ can also be expressed as

For ${{\left\|\bm{m}_{\bm{x}}\right\|}}={{\left\|\bm{x}_{j}\right\|}}$ we have $\Delta_{m}=1/2\min_{j,l<j}{{\left\|\bm{m}_{\bm{x}}\ -\ \bm{x}_{j}\right\|}}^{2}$.

Next we define the sphere where we want to apply Banach fixed point theorem.

With $\bm{\xi}$ given, if the assumptions

the center $\bm{m}_{\bm{x}}$ is well separated from other data $\bm{x}_{j}$ with $l<j$:

the distance $m_{\max}$ of similar patterns to the center is sufficient small:

Using the Cauchy-Schwarz inequality, we obtain for $l+1\leqslant j\leqslant N$:

where we used the assumption (A1) of the lemma.

For the last but one inequality we used $2M\leqslant\max\{m_{\max},2M\}$.

•Banach Fixed Point Theorem. Now we have all ingredients to apply Banach fixed point theorem.

We assume that the first $l$ patterns are much more probable (and similar to one another) than the other patterns. Therefore, we define:

The variance of the first $l$ patterns is

From the last condition we require for a contraction mapping:

We want to see how large $\epsilon$ is. The separation of center $\bm{m}_{\bm{x}}$ from data $\bm{X}=(\bm{x}_{l+1},\ldots,\bm{x}_{N})$ is

A.1.6 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 do not appear. In the next subsection we look into the updates required and error when retrieving the stored patterns. For metastable states we can do the same analyses if each metastable state is treated as one state like one pattern.

We see a trade-off that is known from classical Hopfield networks and for modern Hopfield networks. Small separation $\Delta_{i}$ of the pattern $\bm{x}_{i}$ from the other patterns gives high storage capacity. However the convergence speed is lower and the retrieval error higher. In contrast, large separation $\Delta_{i}$ of the pattern $\bm{x}_{i}$ from the other pattern allows the retrieval of patterns with one update step and exponentially low error.

From Subsection A.1.5.3 need some definitions. We assume to have $N$ patterns, the separation of pattern $\bm{x}_{i}$ from the other patterns ${{\left\{\bm{x}_{1},\ldots,\bm{x}_{i-1},\bm{x}_{i+1},\ldots,\bm{x}_{N}\right\}}}$ is $\Delta_{i}$, defined as

The pattern is separated from the other data if $0<\Delta_{i}$. The separation $\Delta_{i}$ can also be expressed as

The maximal length of a pattern is $M=\max_{i}{{\left\|\bm{x}_{i}\right\|}}$.

We next define what we mean with storing and retrieving a pattern.

the inequality follows from following master inequality

Therefore, we have using the Cauchy-Schwarz inequality:

The last inequality is a contraction to Eq. (302) if we assume that

For simplicity and in accordance with the results of the classical Hopfield network, we assume all patterns being on a sphere with radius $M$:

Under assumption Eq. (305) we have only to show that the master inequality Eq. (307) is fulfilled for each $\bm{x}_{i}$ to have a separate fixed point near each $\bm{x}_{i}$.

We defined $\alpha_{ij}$ as the angle between $\bm{x}_{i}$ and $\bm{x}_{j}$. The minimal angle $\alpha_{\min}$ between two data points is

therefore it is sufficient to show the master inequality on the sphere:

Under assumption Eq. (305) we have only to show that the master inequality Eq. (307) is fulfilled for $\Delta_{\min}$. 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 $\Delta_{\min}$ is ensured. Then we move on to random patterns on a sphere, where $\Delta_{\min}$ 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.

We assume $\beta=1$ and patterns on the sphere with radius $M$. If $M=2\sqrt{d-1}$ and the dimension $d$ of the space is $d\geq 4$ or if $M=1.7\sqrt{d-1}$ and the dimension $d$ of the space is $d\geq 50$, then the number of patterns $N$ that can be stored (fixed point with attraction basin near pattern) is at least

For random patterns on the sphere, we have to show that the master inequality Eq. (311) holds:

We now place the patterns equidistant on the sphere where the pattern are separated by an angle $\alpha_{\min}$:

points on the sphere. In a spherical coordinate system a pattern differs from its most closest patterns by an angle $\alpha_{\min}$ and there are $d-1$ angles. Solving for $\alpha_{\min}$ gives

The number of patterns that can be stored is determined by the largest $N$ that fulfils

We set $N=2^{2(d-1)}$ and obtain for Eq. (317):

The last inequality can be fulfilled with $M=K\sqrt{d-1}$ and proper $K$. For $\beta=1$, $d=4$ and $K=2$ the inequality is fulfilled. The left hand side minus the right hand side is $4(d-1)-1/2^{2(d-1)-1}-\ln(8(d-1))-4(d-1)\ln 2$. Its derivative with respect to $d$ is strict positive. Therefore, the inequality holds for $d\geq 4$.

For $\beta=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/2^{2(d-1)-1}-\ln(5.78(d-1))-4(d-1)\ln 2$. Its derivative with respect to $d$ is strict positive. Therefore, the inequality holds for $d\geq 50$.

If we want to store considerably more patterns, then we have to increase the length of the vectors or the dimension of the space where the vectors live. The next theorem shows results for the number of patterns $N$ with $N=2^{3(d-1)}$.

We assume $\beta=1$ and patterns on the sphere with radius $M$. If $M=5\sqrt{d-1}$ and the dimension $d$ of the space is $d\geq 3$ or if $M=4\sqrt{d-1}$ and the dimension $d$ of the space is $d\geq 13$, then the number of patterns $N$ that can be stored (fixed point with attraction basin near pattern) is at least

We set $N=2^{3(d-1)}$ and obtain for Eq. (317):

The last inequality can be fulfilled with $M=K\sqrt{d-1}$ and proper $K$. For $\beta=1$, $d=13$ and $K=4$ the inequality is fulfilled. The left hand side minus the right hand side is $4.686292(d-1)-1/2^{3(d-1)-1}-\ln(32(d-1))-6(d-1)\ln 2$. Its derivative with respect to $d$ is strict positive. Therefore, the inequality holds for $d\geq 13$.

For $\beta=1$, $d=3$ and $K=5$ the inequality is fulfilled. The left hand side minus the right hand side is $7.32233(d-1)-1/2^{3(d-1)-1}-\ln(50(d-1))-6(d-1)\ln 2$. Its derivative with respect to $d$ is strict positive. Therefore, the inequality holds for $d\geq 3$.

•Storage capacity for random patterns on the sphere.

Next we investigate random points on the sphere. Under assumption Eq. (305) we have to show that the master inequality Eq. (311) is fulfilled for $\alpha_{\min}$, where now $\alpha_{\min}$ is now a random variable. We use results on the distribution of the minimal angles between random patterns on a sphere 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 on the unit sphere. Proposition 3.5 in Brauchart et al. (2018) gives a lower bound on the probability of the minimal angle being larger than a given constant. We require this proposition to derive the probability of pattern having a minimal angle $\alpha_{\min}$. Proposition 3.6 in Brauchart et al. (2018) gives the expectation of the minimal angle.

We will prove high probability bounds for the expected storage capacity. We need the following tail-bound on $\alpha_{\min}$ (the minimal angle of random patterns on a sphere):

Let $d$ be the dimension of the pattern space,

and $\delta>0$ such that $\frac{\kappa_{d-1}}{2}\delta^{(d-1)}\leqslant 1$. Then

The statement of the lemma is Eq. (3-6) from Proposition 3.5 in Brauchart et al. (2018). ∎

Next we derive upper and lower bounds on the constant $\kappa_{d}$ since we require them later for proving storage capacity bounds.

For $\kappa_{d}$ defined in Eq. (323) we have the following bounds for every $d\geq 1$:

We use for $x>0$ the following bound related to Stirling’s approximation formula for the gamma function, c.f. (Olver et al., 2010, (5.6.1)):

Using Stirling’s formula Eq. (326), we upper bound $\kappa_{d}$:

For the first inequality, we applied Eq. (326), while for the second we used $(1+\frac{1}{d})^{d}<e$ for $d\geq 1$.

Next, we lower bound $\kappa_{d}$ by again applying Stirling’s formula Eq. (326):

where the last inequality holds because of monotonicity of $(1+\frac{1}{d})^{d}$ and using the fact that for $d=1$ it takes on the value 2. ∎

We require a bound on $\cos$ to bound the master inequality Eq. (311).

For $0\leqslant x\leqslant\pi$ the function $\cos$ can be upper bounded by:

We use the infinite product representation of $\cos$, c.f. (Olver et al., 2010, (4.22.2)):

for $|x|\leqslant\pi$ and $n\geq 2$, we can get the following upper bound on Eq. (330):

The last but one inequality uses $x\leqslant\pi$, which implies $x/\pi\leqslant 1$. Thus Eq. (329) is proven.

•Exponential storage capacity: the base $c$ as a function of the parameter $\beta$, 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 $c>1$ and an exponent linear in $d$. We derive constraints on he base $c$ as a function of $\beta$, the radius of the sphere $M$, the probability $p$ that all patterns can be stored, and the dimension $d$ of the space. With $\beta>0$, $K>0$, and $d\geq 2$ (to ensure a sphere), the following theorem gives our main result.

We assume a failure probability $0<p\leqslant 1$ and randomly chosen patterns on the sphere with radius $M:=K\sqrt{d-1}$. We define

where $W_{0}$ is the upper branch of the Lambert $W$ function (Olver et al., 2010, (4.13)) and ensure

Then with probability $1-p$, the number of random patterns that can be stored is

Therefore it is proven for $c\geq 3.1546$ with $\beta=1$, $K=3$, $d=20$ and $p=0.001$ ($a+\ln(b)>1.27$) and proven for $c\geq 1.3718$ with $\beta=1$, $K=1$, $d=75$, and $p=0.001$ ($a+\ln(b)<-0.94$).

We consider the probability that the master inequality Eq. (311) is fulfilled:

Therefore, with probability $1-p$ the storage capacity is largest $N$ that fulfills

For Eq. (339) to be fulfilled, it is sufficient that

If we insert the assumption Eq. (334) of the theorem into Eq. (335), then we obtain $N\geq 2$. We now apply the upper bound $\kappa_{d-1}/2<\kappa_{d-1}<1$ from Eq. (325) and the upper bound $\frac{2}{\beta N}\leqslant\frac{1}{\beta}$ from $N\geq 2$ to inequality Eq. (341). In the resulting inequality we insert $N=\sqrt{p}c^{\frac{d-1}{4}}$ to check whether it is fulfilled with this special value of $N$ and obtain:

Dividing by $p$, inserting $M=K\sqrt{d-1}$, and exponentiation of the left and right side by $\frac{2}{d-1}$ gives:

After some algebraic manipulation, this inequality can be written as

We determine the value $\hat{c}$ of $c$ which makes the inequality Eq. (344) equal to zero. We solve

where $W_{0}$ is the upper branch of the Lambert $W$ function (see Def. A6). Hence, the solution is

The solution exist, since the Lambert function $W_{0}(x)$ (Olver et al., 2010, (4.13)) is defined for $-1/e<x$ and we have $0<\exp(a+\ln(b)$.

Since $\hat{c}$ fulfills inequality Eq. (344) and therefore also Eq. (342), we have a lower bound on the storage capacity $N$:

Next we aim at a lower bound on $c$ which does not use the Lambert $W$ function (Olver et al., 2010, (4.13)). Therefore, we upper bound $W_{0}(\exp(a+\ln(b))$ to obtain a lower bound on $c$, therefore, also a lower bound on the storage capacity $N$. The lower bound is given in the next corollary.

We assume a failure probability $0<p\leqslant 1$ and randomly chosen patterns on the sphere with radius $M=K\sqrt{d-1}$. We define

Using the omega constant $\Omega\approx 0.56714329$ we set

Then with probability $1-p$, the number of random patterns that can be stored is

Examples are $c\geq 3.1444$ for $\beta=1$, $K=3$, $d=20$ and $p=0.001$ ($a+\ln(b)>1.27$) and $c\geq 1.2585$ for $\beta=1$ $K=1$, $d=75$, and $p=0.001$ ($a+\ln(b)<-0.94$).

We lower bound the $c$ defined in Theorem A5. According to (Hoorfar & Hassani, 2008, Theorem 2.3) we have for any real $u$ and $y>\frac{1}{e}$:

To upper bound $W_{0}(x)$ for $x\in$, we set

See for these equations the special values of the Lambert $W$ function in Lemma A31. We have the upper bound on $W_{0}$:

At the right hand side of interval $$, we have$u=0$and$\exp(u)=1$ and get:

Therefore, the bound is tight at the right hand side of of interval $$, that is for$\exp(u)=1$, i.e.$u=0$. We have derived an bound for$W_{0}(\exp(u))$with$\exp(u)\in$or, equivalently,$u\in[-\infty,0]. We obtain from Hoorfar & Hassani (2008, Corollary 2.6) the following bound onW_{0}(\exp(u))$for$1<\exp(u)$, or, equivalently$0

A lower bound on $\hat{c}$ is obtained via the upper bounds Eq. (357) and Eq. (355) on $W_{0}$ as $W_{0}>0$. We set $u=a+\ln(b)$ and obtain

We insert this bound into Eq. (347), the solution for $\hat{c}$, to obtain the statement of the theorem.

•Exponential storage capacity: the dimension $d$ of the space as a function of the parameter $\beta$, the radius of the sphere $M$, and the probability $p$.

We express the number $N$ of stored patterns by an exponential function with base $c>1$ and an exponent linear in $d$. We derive constraints on the dimension $d$ of the space as a function of $\beta$, the radius of the sphere $M$, the probability $p$ that all patterns can be stored, and the base of the exponential storage capacity. The following theorem gives this result.

We assume a failure probability $0<p\leqslant 1$ and randomly chosen patterns on the sphere with radius $M=K\sqrt{d-1}$. We define

where $W$ is the Lambert $W$ function (Olver et al., 2010, (4.13)). For $0<a$ the function $W$ is the upper branch $W_{0}$ and for $a<0$ we use the lower branch $W_{-1}$. If we ensure that

then with probability $1-p$, the number of random patterns that can be stored is

We consider the probability that the master inequality Eq. (311) is fulfilled:

Therefore, with probability $1-p$ the storage capacity is largest $N$ that fulfills

For Eq. (365) to be fulfilled, it is sufficient that

If we insert the assumption Eq. (360) of the theorem into Eq. (361), then we obtain $N\geq 2$. We now apply the upper bound $\kappa_{d-1}/2<\kappa_{d-1}<1$ from Eq. (325) and the upper bound $\frac{2}{\beta N}\leqslant\frac{1}{\beta}$ from $N\geq 2$ to inequality Eq. (367). In the resulting inequality we insert $N=\sqrt{p}c^{\frac{d-1}{4}}$ to check whether it is fulfilled with this special value of $N$ and obtain:

Dividing by $p$, inserting $M=K\sqrt{d-1}$, and exponentiation of the left and right side by $\frac{2}{d-1}$ gives:

This inequality Eq. (369) can be reformulated as:

We determine the value $\hat{d}$ of $d$ which makes the inequality Eq. (372) equal to zero. We solve

where $W$ is the Lambert $W$ function (see Def. A6). For $a>0$ we have to use the upper branch $W_{0}$ 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 to ensure that $-1/e\leqslant a\exp(-b)$ for a solution to exist. For $a=0$ we have $\hat{d}=1+\exp(-b)$.

Since $\hat{d}$ fulfills inequality Eq. (369) and therefore also Eq. (368), we have a lower bound on the storage capacity $N$:

We assume a failure probability $0<p\leqslant 1$ and randomly chosen patterns on the sphere with radius $M=K\sqrt{d-1}$. We define

then with probability $1-p$, the number of random patterns that can be stored is

Setting $\beta=1$, $K=3$, $c=2$ and $p=0.001$ yields $d<24$.

For $a<0$ the Eq. (359) from Theorem (A6) can be written as

From Alzahrani & Salem (2018, Theorem 3.1) we get the following bound on $W_{-1}$:

for $u>0$. We apply Eq. (381) to Eq. (380) with $u=-\ln(-a)+b-1$.

•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, we will use the following bound on the expectation of $\alpha_{\min}$ (minimal angle), which gives also a bound on the expected of $\Delta_{\min}$ (minimal separation):

We have the following lower bound on the expectation of $\alpha_{\min}$:

The bound is valid for all $N\geq 2$ and $d\geq 2$.

Let us start with some preliminary estimates. First of all we need some asymptotics for the constant $C_{d-1}$ in Eq. (383):

The following estimate holds for $d\geq 2$:

The recursion formula for the Gamma function is (Olver et al., 2010, (5.5.1)):

We use Eq. (325) and the fact that $d^{\frac{1}{d}}\geq 1$ for $d\geq 1$ to obtain:

where in the last step we used the elementary inequality $\exp(x)\geq 1+x$, which follows from the mean value theorem. ∎

The next theorem states the number of stored patterns for the expected minimal separation.

We assume patterns on the sphere with radius $M=K\sqrt{d-1}$ that are randomly chosen. Then for all values $c\geq 1$ for which

holds, the number of stored patterns for the expected minimal separation is at least

The inequality Eq. (387) is e.g. fulfilled with $\beta=1$, $K=3$, $c=2$ and $d\geq 17$.

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 $\Delta_{\min}$:

For this expectation, the master inequality Eq. (311) becomes

We want to find the largest $N$ that fulfills this inequality.

We apply Eq. (329) and Jensen’s inequality to deduce the following lower bound:

Now we use Eq. (383) and Eq. (384) to arrive at

for sufficiently large $d$. Thus in order to fulfill Eq. (390), it is enough to find values that satisfy Eq. (387).

Retrieval of a pattern $\bm{x}_{i}$ for fixed point $\bm{x}_{i}^{*}$ and query $\bm{\xi}$ is defined via an $\epsilon$ by ${{\left\|f(\bm{\xi})\ -\ \bm{x}_{i}^{*}\right\|}}<\epsilon$, that is, the update is $\epsilon$-close to the fixed point. The update rule retrieves a pattern with one update for well separated patterns, that is, $\Delta_{i}$ is large.

For given $\epsilon$ and sufficient large $\Delta_{i}$, we have ${{\left\|f(\bm{\xi})\ -\ \bm{x}_{i}^{*}\right\|}}<\epsilon$, that is, retrieval with one update.

After every iteration the mapped point $f(\bm{\xi})$ is closer to the fixed point $\bm{x}_{i}^{*}$ than the original point $\bm{x}_{i}$:

We want to estimate how large $\Delta_{i}$ is. For $\bm{x}_{i}$ we have:

The variance of the separation of two points with normally distributed components is

The expected value for the separation of two random vectors gives:

The retrieval error decreases exponentially with the separation $\Delta_{i}$.

The retrieval error ${{\left\|f(\bm{\xi})\ -\ \bm{x}_{i}\right\|}}$ of pattern $\bm{x}_{i}$ is bounded by

and for ${{\left\|\bm{x}_{i}-\bm{x}_{i}^{*}\right\|}}\leqslant\frac{1}{2\ \beta\ M}$ together with ${{\left\|\bm{x}_{i}-\bm{\xi}\right\|}}\leqslant\frac{1}{2\ \beta\ M}$ by

We compute the retrieval error which is just ${{\left\|f(\bm{\xi})\ -\ \bm{x}_{i}\right\|}}$. From Lemma A4 we have

For ${{\left\|\bm{x}_{i}-\bm{x}_{i}^{*}\right\|}}\leqslant\frac{1}{2\ \beta\ M}$ and ${{\left\|\bm{x}_{i}-\bm{\xi}\right\|}}\leqslant\frac{1}{2\ \beta\ M}$ Eq. (404) gives

A.1.7 Learning Associations

We consider three cases of learning associations, i.e. three cases of how sets are associated. (i) Non of the sets is mapped in an associative space. The raw state pattern $\bm{r}_{n}$ is the state (query) pattern $\bm{\xi}_{n}$, i.e. $\bm{\xi}_{n}=\bm{r}_{n}$, and the raw stored pattern $\bm{y}_{s}$ is the stored pattern (key), i.e. $\bm{x}_{s}=\bm{y}_{s}$. (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. $\bm{\xi}_{n}=\bm{r}_{n}$, and raw stored patterns are mapped via $\bm{W}$ to the space of the state patterns, i.e. $\bm{x}_{s}=\bm{W}\bm{y}_{s}$. (iib) The stored patterns are equal to the raw patterns, i.e. $\bm{x}_{s}=\bm{y}_{s}$, and raw state patterns are mapped via $\bm{W}$ to the space of the stored patterns, i.e. $\bm{\xi}_{n}=\bm{W}^{T}\bm{r}_{n}$. (iic) The matrix $\bm{W}$ is an association matrix. We will compute the derivative of the new state pattern with respect to $\bm{W}$, which is valid for all sub-cases (iib)–(iic). (iii) Both set of patterns are mapped in a common associative space. A raw state pattern $\bm{r}_{n}$ is mapped by $\bm{W}_{Q}$ to a state pattern (query) $\bm{\xi}_{n}$, that is $\bm{\xi}_{n}=\bm{W}_{Q}\bm{r}_{n}$. A raw stored pattern $\bm{y}_{s}$ is mapped via $\bm{W}_{K}$ to stored pattern (key) $\bm{x}_{s}$, that is $\bm{x}_{s}=\bm{W}_{K}\bm{y}_{s}$. We will compute the derivative of the new state pattern with respect to both $\bm{W}_{Q}$ and $\bm{W}_{K}$.

The sets are associated via their raw patterns, i.e. the raw state pattern $\bm{r}_{n}$ is the state (query) pattern $\bm{\xi}_{n}$, i.e. $\bm{\xi}_{n}=\bm{r}_{n}$, and raw stored pattern $\bm{y}_{s}$ is the stored pattern (key), i.e. $\bm{x}_{s}=\bm{y}_{s}$. There is no mapping in an associative space.

The derivative with respect to $\bm{\xi}$ is

The derivative with respect to $\bm{X}$ is

These derivatives allow to apply the chain rule if a Hopfield layer is integrated into a deep neural network.

Only one of the sets $\bm{R}$ or $\bm{Y}$ is mapped in the space of the patterns of the other set. Case (a): the state patterns are equal to the raw patterns $\bm{\xi}_{n}=\bm{r}_{n}$ and raw stored patterns are mapped via $\bm{W}$ to the space of the state patterns, i.e. $\bm{x}_{s}=\bm{W}\bm{y}_{s}$. Case (b): the stored patterns are equal to the raw patterns $\bm{x}_{s}=\bm{y}_{s}$ and raw state patterns are mapped via $\bm{W}$ to the space of the stored patterns, i.e. $\bm{\xi}_{n}=\bm{W}^{T}\bm{r}_{n}$. Case (c): the matrix $\bm{W}$ associates the sets $\bm{R}$ and $\bm{Y}$. This case also includes that $\bm{W}^{T}=\bm{W}_{K}^{T}\bm{W}_{Q}$, which is treated in next subsection. The next subsection focuses on a low rank approximation of $\bm{W}$ by defining the dimension $d_{k}$ of associative space and use the matrices $\bm{W}_{K}^{T}$ and $\bm{W}_{Q}$ to define $\bm{W}$, or equivalently to map $\bm{R}$ and $\bm{Y}$ into the associative space.

From a mathematical point of view all these case are equal as they lead to the same update rule. Therefore, we consider in the following Case (a) with $\bm{x}_{s}=\bm{W}\bm{y}_{s}$ and $\bm{\xi}_{n}=\bm{r}_{n}$. Still, the following formula are valid for all three cases (a)–(c).

For multiple updates this update rule has to be used. However for a single update, or the last update we consider a simplified update rule.

The derivative with respect to $\bm{W}$ is

We have the product of the 3-dimensional tensor $\frac{\partial(\bm{W}^{T}\bm{\xi})}{\partial\bm{W}}$ with the vector $\bm{a}$ which gives a 2-dimensional tensor, i.e. a matrix:

To obtain the derivative of the full update rule Eq. (412) we have to add the term

Both sets $\bm{R}$ and $\bm{Y}$ are mapped in an associative space. Every raw state pattern $\bm{r}_{n}$ is mapped via $\bm{W}_{Q}$ to a state pattern (query) $\bm{\xi}_{n}=\bm{W}_{Q}\bm{r}_{n}$. Every raw stored pattern $\bm{y}_{s}$ is mapped via $\bm{W}_{K}$ to a stored pattern (key) $\bm{x}_{s}=\bm{W}_{K}\bm{y}_{s}$. In the last subsection we considered a single matrix $\bm{W}$. For $\bm{W}^{T}=\bm{W}_{K}^{T}\bm{W}_{Q}$ we have the case of the last subsection. However in this subsection we are looking for a low rank approximation of $\bm{W}$. Toward this end we define the dimension $d_{k}$ of associative space and use the matrices $\bm{W}_{K}^{T}$ and $\bm{W}_{Q}$ to map to the associative space.