Overparameterized Neural Networks Implement Associative Memory
Adityanarayanan Radhakrishnan Mikhail Belkin Caroline Uhler


Stability dependence of local structural heterogeneities of stable amorphous solids
    Grzegorz Szamel
    today
===================================================================================




Identifying computational mechanisms for memorization and retrieval of data is a long-standing problem at the intersection of machine learning and neuroscience.  Our main finding is that standard overparameterized deep neural networks trained using standard optimization methods implement such a mechanism for real-valued data.  Empirically, we show that: (1) overparameterized autoencoders store training samples as attractors, and thus, iterating the learned map leads to sample recovery; (2) the same mechanism allows for encoding sequences of examples, and serves as an even more efficient mechanism for memory than autoencoding.  Theoretically, we prove that when trained on a single example, autoencoders store the example as an attractor.  Lastly, by treating a sequence encoder as a composition of maps, we prove that sequence encoding provides a more efficient mechanism for memory than autoencoding.




§ INTRODUCTION

Developing computational models of associative memory, a system which can recover stored patterns from corrupted inputs, is a long-standing problem at the intersection of machine learning and neuroscience.  An early example of a computational model for memory dates back to the introduction of Hopfield networks <cit.>.  Hopfield networks are an example of an attractor network, a system which allows for the recovery of patterns by storing them as attractors of a dynamical system.  In order to write patterns into memory, Hopfield networks construct an energy function with local minima corresponding to the desired patterns.  To retrieve these stored patterns, the constructed energy function is iteratively minimized starting from a new input pattern until a local minimum is discovered and returned. 

While Hopfield networks can only store binary patterns, the simplicity of the model allowed for a  theoretical analysis of capacity <cit.>.  In order to to implement a form of associative memory for more complex data modalities, such as images, the  idea of storing training examples as the local minima of an energy function was extended by several recent works <cit.>.  Unlike Hopfield networks, these modern methods do not guarantee that a given pattern can be stored and typically lack the capacity to store patterns exactly; see e.g. <cit.>.  

Our main finding is that standard over-parameterized neural networks trained using standard optimization methods can implement associative memory.  In contrast to energy-based methods, the storage and retrieval mechanisms are automatic consequences of training and do not require constructing and minimizing an energy function.  

Interpolation Alone is Not Sufficient for Implementing Associative Memory. While in recent machine learning literature (e.g., <cit.>) the term  memorization is often used interchangeably with interpolation, the ability of a model to perfectly fit training data, note that memorization is stronger and also requires a model to be able to recover training data. In general, interpolation does not guarantee the ability to recover training data nor does it guarantee the ability to associate new inputs with training examples. Fig. <ref>a shows an example of a function that interpolates training data, but does not implement associative memory: there is no apparent method to recover the training examples from the function alone.  On the other hand, Fig. <ref>b gives an example of a function that implements memory: the training examples are retrieved as the range of the function. 






While it has been observed (e.g., <cit.>) that over-parameterized networks can interpolate the training data, there is no apriori reason why it should be possible to recover the training data from the network.  In this work, we show that, remarkably, the retrieval mechanism also follows naturally from training: the examples can be recovered simply by iterating the learned map. A depiction of the memorization and retrieval mechanisms is presented in Fig. <ref>c and <ref>d. More precisely, given a set of training examples {x^(i)}_i=1^n⊂ℝ^d and an overparameterized neural network implementing a family of continuous functions ℱ = {f : ℝ^d →ℝ^d}, we show that minimizing the following autoencoding objective with gradient descent methods leads to training examples being stored as attractors:

    min_f ∈ℱ ∑_i=1^n f(x^(i)) - x^(i)^2

Interestingly, attractors arise without any specific regularization to the above loss function.  We demonstrate this phenomenon by presenting a wealth of empirical evidence, including a network that stores 500 images from ImageNet-64 <cit.> as attractors.  In addition, we present a proof of this phenomenon for over-parameterized networks trained on single examples.  

Furthermore, we show that a slight modification of the objective (<ref>) leads to an implementation of associative memory for sequences.  More precisely,  given a sequence of training examples {x^(i)}_i=1^n⊂ℝ^d, minimizing the following sequence encoding objective with gradient descent methods leads to the training sequence being stored as a stable limit cycle:

    min_f ∈ℱ ∑_i=1^n  f(x^((i n) + 1))) - x^(i)^2.


Multiple cycles can be encoded similarly (Appendix <ref>).  In particular, we provide several examples of networks storing video and audio samples as limit cycles.  Interestingly, these experiments suggest that sequence encoding provides a more efficient mechanism for memorization and retrieval of training examples than autoencoding.  By considering a sequence encoder as a composition of maps, we indeed prove that sequence encoders are more contractive to a sequence of examples than autoencoders are to individual examples. 



§ RELATED WORK


Autoencoders <cit.> are commonly used for manifold learning, and the autoencoder architecture and objective (Eq. (<ref>)) have been modified in several ways to improve their ability to represent data manifolds.  Two variations, contractive and denoising autoencoders, add specific regularizers to the objective function in order to make the functions implemented by the autoencoder contractive towards the training data <cit.>.  However, these autoencoders are typically used in the under-parameterized regime, where they do not have the capacity to interpolate (fit exactly) the training examples and hence cannot store the training examples as fixed points.   

On the other hand, it is well-known that over-parameterized neural networks can interpolate the training data when trained with gradient descent methods <cit.>. As a consequence,  over-parameterized autoencoders can store training examples as fixed points. In particular, recent work empirically studied over-parameterized autoencoders in the setting with one training example <cit.>. 

In this paper, we take a dynamical systems perspective to study over-parameterized autoencoders and sequence encoders. In particular, we show that not only do over-parameterized autoencoders (sequence encoders) trained using standard methods store training examples (sequences) as fixed points (limit cycles), but that these fixed points (limit cycles) are attractors (stable), i.e., they can be recovered via iteration. While energy-based methods have also been shown to be able to  recall sequences as stable limit cycles <cit.>, the mechanism identified here is unrelated and novel: it does not require setting up an energy function and is a direct consequence of training an over-parameterized network. 



§ BACKGROUND FROM DYNAMICAL SYSTEMS


We now introduce tools related to dynamical systems that we will use to analyze autoencoders and sequence encoders.




Attractors in Dynamical Systems. Let f: ℝ^d →ℝ^d denote the function learned by an autoencoder trained on a dataset X = {x^(i)}_i=1^n⊂ℝ^d. Consider the sequence {f^k(x)}_k ∈ℕ where f^k(x) denotes k compositions of f applied to x ∈ℝ^d. A point x∈ℝ^d is a fixed point of f if  f(x) = x; in this case the sequence {f^k(x)}_k ∈ℕ trivially converges to x. 

Since overparameterized autoencoders interpolate the training data, it holds that f(x^(i)) = x^(i) for each training example x^(i)∈ X; hence all training examples are fixed points of f.[To ensure f(x^(i)) ≈ x^(i), it is essential to train until the loss is very small; we used ≤ 10^-8.]  We now formally define what it means for a fixed point to be an attractor and provide a sufficient condition for this property. 


A fixed point x^* ∈ℝ^d is an attractor of f:ℝ^d→ℝ^d if there exists an open neighborhood, 𝒪, of x^*, such that for any x ∈𝒪, the sequence {f^k (x)}_k ∈ℕ converges to x^* as k →∞.  The set S of all such points is called the basin of attraction of x^*.  




A fixed point x^* ∈ℝ^d is an attractor of a differentiable map f if all eigenvalues of the  Jacobian of f at x^* are strictly less than 1 in absolute value. If any of the eigenvalues are greater than 1, x^* cannot be an attractor.  




Proposition <ref> is a well-known condition in the theory of dynamical systems (Chapter 6 of <cit.>).  The condition intuitively means that the function f is “flatter” around an attractor x^*.  Since training examples are fixed points in over-parameterized autoencoders, from Proposition <ref>, it follows that a training example is an attractor if the maximum eigenvalue (in absolute value) of the Jacobian at the example is less than 1.  Since attractors are recoverable through iteration, autoencoders that store training examples as attractors guarantee recoverability of these examples.  Energy-based methods also allow for verification of whether a training example is an attractor.  However, this requires checking the second order condition that the Hessian is positive definite at the training example, which is more computationally expensive than checking the first order condition from Proposition <ref>.




Discrete Limit Cycles in Dynamical Systems.  Discrete limit cycles can be considered the equivalent of an attractor for sequence encoding, and a formal definition is provided below.



A finite set X^* = {x^(i)}_i=1^n⊂ℝ^d is a stable discrete limit cycle of a smooth function f : ℝ^d →ℝ^d if: (1) f(x^(i)) = x^(i n) + 1 ∀ i ∈{1, … n} ; (2) There exists an open neighborhood, 𝒪, of X^* such that for any x ∈𝒪, X^* is the limit set of {f^k(x)}_k=1^∞.   


The equivalent of Proposition <ref> for verifying that a finite sequence of points forms a limit cycle is provided below. 



Let network f: ℝ^d →ℝ^d be trained on a given sequence x^(1), … , x^(n) such that f(x^(i))=x^((i  n) + 1). Then the sequence {x^(i)}_i=1^n forms a stable discrete limit cycle if the largest eigenvalue of the Jacobian of f^n(x^(i)) is (in absolute value) less than 1 for any i.  


This follows directly by applying Proposition <ref> to the map f^n, since x^(i) = f^n(x^(i)) and f(x^(i))=x^((i  n) + 1).  Before presenting our results, we provide the following important remark. 



Why the Emergence of Attractors in Autoencoders is Notable. Proposition <ref> states that for a fixed point to be an attractor, all eigenvalues of the Jacobian at that point must be less than 1 in absolute value. Since the number of eigenvalues of the Jacobian equals the dimension of the space, this means that the angle of the derivative is less than π/4 in every eigendirection of the Jacobian. This is a highly restrictive condition, since intuitively, we expect the “probability” of such an event to be 1/2^d. Hence, a fixed point of an arbitrary high-dimensional map is unlikely to be an attractor. Indeed, as we show in Corollary 1, fixed points of neural networks are not generally  attractors.
While not yet fully understood, the emergence and, indeed, proliferation of attractors in autoencoding is not due solely to architectures but to specific inductive biases of the training procedures.




§ EMPIRICAL FINDINGS




Training Examples are Stored as Attractors in Over-parameterized Autoencoders. 
In the following, we present a range of empirical evidence that attractors arise in autoencoders across common architectures and optimization methods. For details on the specific architecures and optimization schemes used for each experiment, see Appendix, Fig <ref>.



Storing Images as Attractors. In Fig. <ref>, we present an example of an over-parameterized autoencoder storing 500 images from  as attractors.  This was achieved by training an autoencoder with depth 10, width 1024, and cosid nonlinearity <cit.> on 500 training examples using the Adam <cit.> optimizer to loss ≤ 10^-8.  We verified that all 500 training images were stored as attractors by checking that the magnitudes of all eigenvalues of the Jacobian matrix at each example were less than 1. Indeed, Fig. <ref>a demonstrates that iteration of the trained autoencoder map starting from corrupted inputs converges to individual training examples. 
A common practice for measuring recoverability of training patterns is to input corrupted versions of the patterns and verify that the system is able to recover the original patterns.  From Proposition <ref>, provided that a corrupted example is in the basin of attraction of the original example, iteration is guaranteed to converge to the original example.  In examples (5) and (6) Fig. <ref>a, the corrupted images are not in the basin of attraction for the original examples, and so iteration converges to a different (but contextually similar) training example. Fig. <ref>b provides further examples of correct recovery from corrupted images.  Fig. <ref>c presents a quantitative analysis of the recovery rate of training examples under various forms of corruption.  Overall, the recovery rate is remarkably high: even when 50% of the image is corrupted, the recovery rate of the network is significantly higher than expected by chance.

Examples of autoencoders storing training examples as attractors when trained on 2000 images from MNIST <cit.> and 1000 black-and-white images from CIFAR10 <cit.> are presented in the Appendix Fig. <ref>, Fig. <ref>, respectively.  The MNIST autoencoder presented in Appendix, Fig. <ref> stores 2000 training examples as attractors.  Note that one iteration of the learned map on test examples can look similar to the identity function, but in fact, iterating until convergence yields a training example (see Appendix Fig. <ref>).



Spurious Attractors. While in these examples, we verified that the training examples were stored as attractors by checking the eigenvalue condition, there could be spurious attractors, i.e. attractors other than the training examples.  In fact, spurious attractors are known to exist for Hopfield networks <cit.>.  To investigate whether there are additional attractors outside of the training examples, we iterated the map from sampled test images and randomly generated images until convergence. More precisely, we declared convergence of the map at iteration k for some image x when f^k+1(x) - f^k(x) _2 < 10^-8 and concluded that f^k(x) had converged to the training example x^(i) if f^k(x) - x^(i)_2 < 10^-7. 



In general, spurious attractors can exist for over-parameterized autoencoders, and we provide examples in the Appendix Fig. <ref>.  However, remarkably, for the network presented in Fig. <ref>, we could not identify any spurious attractors even after iterating the trained map from 40,000 test examples from ImageNet-64, 10,000 examples of uniform random noise, and 10,000 examples of Gaussian noise with variance 4.







Attractors Arise across Architectures, Training Methods & Initialization Schemes.  We performed a thorough analysis of the attractor phenomenon identified above across a number of common architectures, optimization methods, and initialization schemes. Starting with fully connected autoencoders, we analyzed the number of training examples stored as attractors when trained on 100 black and white images from CIFAR10 <cit.> under the following nonlinearities, initializations, and optimization methods:

    
  * Nonlinearities: ReLU, Leaky Relu, SELU, cosid (cos x - x), Swish <cit.>, and sinusoidal (x + (sin10x)/5).
    
  * Optimization Methods: Gradient Descent (GD), GD with momentum, GD with momentum and weight decay, RMSprop, and Adam (Ch. 8 of <cit.>).
    
  * Initialization Schemes: Random uniform initialization, namely U[-a, a], per weight for a∈{0.01, 0.02, 
 0.05, 0.1, 0.15}.  These initialization schemes subsume the PyTorch (Version 0.4) default, Xavier initialization, and Kaiming initialization <cit.>.





In Appendix, Fig. <ref> and <ref>, we provide the number of training examples stored as attractors for all possible combinations of (a) nonlinearity and optimization method listed above; and (b) nonlinearity and initialization scheme listed above.  These tables demonstrate that attractors arise in all settings for which training converged to a sufficiently low loss within 1,000,000 epochs.  In Appendix Figures <ref>, <ref> and Appendix <ref>, we also present examples of convolutional and recurrent networks that store training examples as attractors, thereby demonstrating that this phenomenon is not limited to fully connected networks and occurs in all commonly used network architectures.  



Visualizing Attractors in 2D. In order to better understand the attractor phenomenon, we present an example of an over-parameterized autoencoder storing training examples as attractors in the 2D setting, where the basins of attraction can easily be visualized (Fig. <ref>).  We trained an autoencoder to store 6 training examples as attractors. Their basins of attraction were visualized by iterating the trained autoencoder map starting from 10,000 points on a grid until convergence. The vector field indicates the direction of motion given by iteration. Also in this experiment, we found no spurious attractors.  Each training example and corresponding basin of attraction is colored differently. Interestingly, the example in Fig. <ref> shows that the metric learned by the autoencoder to separate the basins of attraction is not Euclidean distance, which would be indicated by a Voronoi diagram. 







Over-parameterized Sequence Encoders Store Training Examples as Stable Limit Cycles and are More Efficient at Memorizing and Retrieving Examples than Autoencoders.  We have thus far analyzed the occurrence of attractors in over-parameterized autoencoders.  In this section, we demonstrate via various examples that by modifying the autoencoder objective to encode sequences (Eg. [<ref>]), we can implement a form of associative memory for sequences. For details on the specific architectures and optimization schemes used for each experiment, see Appendix Figure <ref>. 



Storing Sequences as Limit Cycles.
We trained a network to encode 389 frames of size 128 × 128 from the Disney film “Steamboat Willie” by mapping frame i to frame i+1  389.  Fig. <ref>(a) and the attached video[Located at: <https://github.com/uhlerlab/neural_networks_associative_memory>] show that iterating the trained network starting from random noise yields the original video. 

As a second example, we encoded two 10-digit sequences from MNIST: one counting upwards from digit 0 to 9 and the other counting down from digit 9 to 0. The maximal eigenvalues of the Jacobian of the trained encoder composed 10 times is 0.0034 and 0.0033 for the images from the first and second sequence, respectively.  Hence by Proposition <ref>, both sequences form limit cycles. Indeed, as shown in Fig. <ref>(b), iteration from Gaussian noise leads to the recovery of both training sequences.  

Finally, in Fig. <ref>(c), we visualized the vector field and basins of attraction for four cycles in the 2-dimensional setting.  Unlike autoencoding where points near a training example are pushed towards it via iteration, the points now move following the cycles.  In Appendix <ref>, we also trained a sequence encoder that stores 10 seconds of speech as a limit cycle.  The attached audio file demonstrates that iterating the trained network from random noise recovers the original audio. 

 




Efficiency of Sequence Encoding. In Fig. <ref>, we analyze the network sizes (width and depth) needed to store and retrieve 100 training images from MNIST using fully connected autoencoders and sequence encoders.
Interestingly, our experiments indicate that memorization and retrieval of training examples can be performed more efficiently through sequence encoding than autoencoding. In particular, Fig. <ref>(a) shows the number of training examples (out of 100) that are attractors for different width and depth of the network. Note that a depth of 31 and width of 512 is needed to store almost all (99) training examples. If we instead encode the same data using 20 sequences of length 5, all 20 sequences (and thus all 100 examples) can be recovered using a much smaller network with a depth of 6 and 512 hidden units per layer (Fig. <ref>(b)). Extending this idea further (Fig. <ref>(c)-(e)), if we chain all 100 examples as a single sequence, the entire sequence is stored using a network with only 1 hidden layer and 512 hidden units.  



Increasing Depth and Width leads to more Attractors/Limit Cycles.
The experiments in Fig. <ref> indicate that increasing network depth and width leads to an increase in the number of training examples / sequences stored as attractors / limit cycles. For over-parameterized autoencoders, this implies that the maximum eigenvalue of the Jacobian is less than 1 for a greater number of training examples upon increasing network depth and width (see Proposition <ref>),  i.e., the network becomes more contractive around the training examples. Indeed, by analyzing the histogram of the maximum eigenvalue of the Jacobian at each of the training examples, we observed that as network depth and width increases, the mode of these histograms shifts closer to zero (Appendix Fig. <ref>). Additionally, when considering the distribution of the top 1% of Jacobian eigenvalues, we find that as network width increases, the variance of the distribution of Jacobian eigenvalues decreases, and when depth increases, the mode of the distribution shifts closer to zero (Appendix Fig. <ref>). In the following, we prove this phenomenon for a single training example, i.e., we prove that autoencoders trained on a single example become more contractive at the training example with increasing depth and width.






§ THEORETICAL ANALYSIS OF SPECIAL CASES


We now provide theoretical support for our empirical findings. Complete proofs are given in Appendix <ref>-<ref>.



Proof that when trained on a single example, over-parameterized autoencoders store the example as an attractor. We outline the proof for the 1-hidden layer setting. The complete proof for the multi-layer setting is given in the Appendix <ref>. 

Let f(z) = W_1 ϕ(W_2 z) represent a 1-hidden layer autoencoder with elementwise nonlinearity ϕ and weights  W_1 ∈ℝ^k_0 × k and W_2 ∈ℝ^k × k_0, applied to z ∈ℝ^k_0.  We analyze the function learned by gradient descent with learning rate γ by minimizing the following autoencoding loss on 1 training example x:

    ℒ(x, f) = 1/2 x - f(x) _2^2.

Let W_1^(t), W_2^(t) denote the values of the weights after t steps of gradient descent. To prove that x is an attractor of f after training, we solve for W_1^(∞), W_2^(∞) and compute the top eigenvalue of the Jacobian of f at x (denoted λ_1(𝐉(f(x)))).  

In order to solve for W_1, W_2, we first identify two invariants of gradient descent (proved in Appendix <ref>):  



Invariant 1:  If W_1 and W_2 are initialized to be rank 1 matrices of the form x u^(0)^T and v^(0) x^T respectively, 
then W_1^(t) = xu^(t)^T  and W_2^(t) = v^(t) x^T for all time-steps t>0. 



Invariant 2: If, in addition, all weights in each row of W_1 and W_2 are initialized to be equal,  they remain equal throughout training.



Invariant 1 implies that autoencoders trained on 1 example produce outputs that are multiples of the training example.  Generalizing this result, in Appendix <ref>, we prove that autoencoders trained on multiple examples produce outputs in the span of the training data.  Invariant 2 reduces gradient descent dynamics to the 1-dimensional setting. Using the Invariants 1 and 2 combined with gradient flow (i.e. taking the limit as the learning rate γ→ 0), we can solve for W_1^(∞) and W_2^(∞).



Let f(z) = W_1 ϕ(W_2 z) denote a 1-hidden layer network with elementwise nonlinearity ϕ and weights W_1 ∈ℝ^k_0 × k and W_2 ∈ℝ^k × k_0, applied to z ∈ℝ^k_0. Let x ∈ℝ^k_0 be a training example with x_2 = 1. Assuming ϕ(z)/ϕ'(z) < ∞ ∀ z ∈ℝ, then under Invariants 1 and 2, gradient descent with learning rate γ→ 0 applied to minimize the autoencoding loss in Eq. (<ref>) leads to a rank 1 solution W_1^(∞) = xu^T and W_2^(∞) = vx^T with u, v ∈ℝ^k satisfying:

    u_i^2 - u_i^(0)^2/2   = ∫_v_i^(0)^v_iϕ(z)/ϕ'(z) dz   and  
      u_i ϕ(v_i) = 1/k,

and u_i = u_j, v_i = v_j for all i, j ∈ [k], where u^(0) and v^(0) are such that W_1^(0) = x u^(0)^T and  W_2^(0) = v^(0) x^T. 


Theorem <ref> allows us to compute the top eigenvalue of the Jacobian at x, denoted by λ_1(𝐉(f(x))). 



Under the setting of Theorem <ref>, it holds that

    λ_1(J(f(x))) = ϕ'(v_i)v_i/ϕ(v_i).
 


Using Theorem <ref>, we can explicitly determine whether a training example x is an attractor, when given a nonlinearity ϕ, initial values for u^(0) and v^(0), and the width of the network k.  We note that for all non-piecewise nonlinearities used thus far, we can make any training example an attractor by selecting values for u^(0), v^(0) and k appropriately.  




Example. Let x be a training example in ℝ^k_0.  Suppose ϕ(z) = 1/1+e^-z for z ∈ℝ, k=2, and u_i^(0) = v_i^(0) = 1 for all i.  Then by Theorems <ref> and <ref>, it holds after training that

    u_i^2 - 1/2 = ∫_1^v_i(1/1 - ϕ(z)) dz   and  u_i/1 + e^-v_i  = 1/2

with u_i ≈ .697, v_i ≈ .929 and λ_1(𝐉(f(x))) ≈ .263. Since λ_1(𝐉(f(x))) < 1, x is an attractor. We also confirmed this result (up to third decimal place) experimentally by training a network using gradient descent with learning rate 10^-4. 




Importantly,  the analysis of Theorem <ref> implies that attractors arise as a result of training and are not simply a consequence of interpolation by a neural network with a certain architecture; see the following corollary. 



Corollary 1.   Let x ∈ℝ^k_0 with x_2 = 1 and  f(z) = xu^T ϕ(vx^T z), where u, v ∈ℝ^k and ϕ is a smooth element-wise nonlinearity with ϕ'(z)/ϕ(z) < ∞ for all z ∈ℝ, |ϕ'(z) z/ϕ(z)| > 1 for z in an open interval 𝒪⊂ℝ.  Then there exist infinitely many v ∈ℝ^k, such that f(x) = x and x is not an attractor for f.

The condition, |ϕ'(z) z / ϕ(z)| > 1 for z in an open interval, holds for all smooth non-linearities considered in this paper. The proof is presented in Appendix <ref>.  

We note that while the linear setting with ϕ(z) = z has been studied extensively using gradient flow <cit.>, our results extend to the non-linear setting and require novel tools. 

Remarks on the Multiple Sample Setting. While we extend Invariant 1 to the multiple example setting in Appendix <ref>, a similar extension of Invariant 2 is required in order to generalize Theorem 1 to multiple examples.  We believe such an extension may be possible for orthonormal training examples.  Under random initialization, it may be possible to prove the attractor phenomenon by analyzing autoencoders in the Neural Tangent Kernel (NTK) regime <cit.>. However, the disadvantage of such an analysis is that it relies on computing a closed form for the NTK in the limiting case of network width approaching infinity.  On the other hand, Theorem 1 holds for a general class of non-linearities and for finite width and depth.



Remarks on Similarity to Power Iteration. The attractor phenomenon identified in this work appears similar to that of Fast Independent Component Analysis <cit.> or more general nonlinear power iteration <cit.>, where every “eigenvector" (corresponding to a training example in our setting) of a certain iterative map has its own basin of attraction. In particular, increasing network depth may play a similar role to increasing the number of iterations in those methods.  While the mechanism may be different, understanding this connection is an important direction for future work.





Proof that sequence encoding provides a more efficient mechanism for memory than autoencoding by analyzing sequence encoders as a composition of maps. We start by generalizing Invariants 1, 2, and Theorem <ref> to the case of training a network to map an example x^(i)∈ℝ^k_0 to an example x^(i+1)∈ℝ^k_0 as follows. 




Let f(z) = W_1 ϕ(W_2 z) denote a 1-hidden layer network with elementwise nonlinearity ϕ and weights W_1 ∈ℝ^k_0 × k and W_2 ∈ℝ^k × k_0, applied to z ∈ℝ^k_0. Let x^(i), x^(i+1)∈ℝ^k_0 be training examples with x^(i)_2 = x^(i+1)_2 = 1. Assuming that ϕ(z)/ϕ'(z) < ∞ ∀ z ∈ℝ and there exist u^(0), v^(0)∈ℝ^k such that W_1^(0) = x^(i+1)u^(0)^T and W_2^(0) = v^(0)x^(i)^T with u_i^(0) = u_j^(0), v_i^(0) = v_j^(0) ∀ i, j ∈ [k], then
gradient descent with learning rate γ→ 0 applied to minimize

    ℒ(x, f) = 1/2 x^(i+1) - f(x^(i)) _2^2

leads to a rank 1 solution
W_1^(∞) = x^(i+1) u^T and W_2^(∞) = v x^(i)^T with u, v ∈ℝ^k satisfying

    u_i^2 - u_i^(0)^2/2   = ∫_v_i^(0)^v_iϕ(z)/ϕ'(z) dz,   and  
      u_i ϕ(v_i) = 1/k,

and u_i = u_j, v_i = v_j for all i, j ∈ [k].



The proof is analogous to that of Theorem <ref>.  Sequence encoding can be viewed as a composition of individual networks f_i that are trained to map example x^(i) to example x^((i  n)+1). The following theorem provides a sufficient condition for when the composition of these individual networks stores the sequence of training examples {x^(i)}_i=1^n as a stable limit cycle.



Let {x^(i)}_i=1^n be n training examples with x^(i)_2 = 1  for all i ∈ [n], and let {f_i}_i=1^n denote n 1-hidden layer networks satisfying the assumptions in Theorem <ref> and trained on the loss in Eq. (<ref>).  Then the composition f = f_n ∘ f_n-1∘…∘ f_1 satisfies:

    λ_1(𝐉(f(x^(1)))= ∏_i=1^n( ϕ'(v_j^(i)) v_j^(i)/ϕ(v_j^(i))).



The proof is presented in Appendix <ref>. Theorem <ref> shows that sequence encoding provides a more efficient mechanism for memory than autoencoding.  If each of the networks f_i autoencoded example x_i for i ∈ [n], then Theorem <ref> implies that each of the n training examples is an attractor (and thus recoverable) if each term in the product in Eq. (<ref>) is less than 1.  This in turn implies that the product, itself, is less than 1 and hence all training examples are stored by the corresponding sequence encoder, f, as a stable limit cycle. 




§ DISCUSSION


We have shown that standard over-parameterized neural networks trained using standard optimization methods implement associative memory.  In particular, we empirically showed that autoencoders store training examples as attractors and that sequence encoders store training sequences as stable limit cycles.  We then demonstrated that sequence encoders provide a more efficient mechanism for memorization and retrieval of data than autoencoders.  In addition, we mathematically proved that when trained on a single example, nonlinear fully connected autoencoders store the example as an attractor.  By modeling sequence encoders as a composition of maps, we showed that such encoders provide a more efficient mechanism for implementing memory than autoencoders, a finding which fits with our empirical evidence.  We end by discussing implications and possible future extensions of our results.  




Inductive Biases.  In the over-parameterized regime, neural networks can fit the training data exactly for different values of parameters.  In general, such interpolating auto-encoders do not store data as attractors (Corollary 1). Yet, as we showed in this paper, this is typically the case for parameter values chosen by  gradient-based optimization methods. Thus, our work identifies a novel inductive bias of the specific solutions selected by the training procedure. 
Furthermore, increasing depth and width leads to networks becoming more contractive around the training examples, as demonstrated in Figure <ref>.  

While our paper concentrates on the question of implementing associative memory, we employ the same training procedures and similar network architectures to those used in standard supervised learning tasks.  We believe that our finding on the existence and ubiquity of attractors in these maps may shed light on the important question of inductive biases in interpolating neural networks for classification <cit.>.








Generalization.  While generalization in autoencoding often refers to the ability of a trained autoencoder to reconstruct test data with low error <cit.>, this notion of generalization may be problematic for the following reason.  The identity function achieves zero test error and thus “generalizes”, although no training is required for implementing this function.  In general, it is unclear how to formalize generalization for autoencoding and alternate notions of generalization may better capture the  desired properties. An alternative definition of generalization is the ability of an autoencoder to map corrupted versions of training examples back to their originals (as in Fig. <ref>a,b). Under this definition, over-parameterized autoencoders storing training examples as attractors generalize (Fig. <ref>c), while the identity function does not generalize.  Given this issue with the current notion of generalization for autoencoding, it is an important line of future work to provide a definition of generalization that appropriately captures desired properties of trained autoencoders.  Lastly, another important direction of future work is to build on the properties of autoencoders and sequence encoders identified in this work to understand generalization properties of networks used for classification and regression.









Metrics Used by Nonlinear Networks. 
In Figure <ref>, we provided a visualization of how the basins of attraction for individual training examples subdivide the space of inputs.  The picture appears very different from the Voronoi tessellation corresponding to the 1-nearest-neighbor (1-NN) predictor, where each input is associated to its closest training point in Euclidean distance. Yet, this may be different in high dimension.  In Appendix Fig <ref>, we compare the recovery rate of our network from Figure <ref> to that of a 1-NN classifier and observe remarkable similarity, leading us to conjecture that the basins of attraction of high-dimensional fully connected neural networks may be closely related to the tessellations produced by 1-NN predictors.  Thus, understanding the geometry of attractors in high-dimensional neural networks is an important direction of future research.  



Connection to Biological Systems. Finally, another avenue for future exploration (and a key motivation for the original work on Hopfield networks <cit.>) is the connection of autoencoding and sequence encoding in neural nets to  memory mechanisms in  biological systems.  Since over-parameterized autoencoders and sequence encoders recover stored patterns via iteration, the retrieval mechanism presented here is biologically plausible.  However, back-propagation is not believed to be a biologically plausible mechanism for storing patterns  <cit.>. An interesting avenue for future research is to 
identify storage mechanisms that are biologically plausible 
and to see whether similar attractor phenomena arise in other, more biologically plausible, optimization methods.   




Materials and Methods. An overview of all experimental details including datasets, network architectures, initialization schemes, random seeds, and training hyperparameters considered in this work are provided in Appendix Fig. <ref>, <ref>, and <ref>. Briefly, we used the PyTorch library <cit.> and two NVIDIA Titan Xp GPUs for training all neural networks. In our autoencoding experiments on the image datasets ImageNet-64 <cit.>, CIFAR10 <cit.>, and MNIST <cit.>, we trained both, fully connected networks and U-Net convolutional networks <cit.>. For Fig <ref>, <ref>b, <ref>c, and <ref> as well as for training sequence encoder models on audio and video samples[Link to video and audio samples: <https://github.com/uhlerlab/neural_networks_associative_memory>], we used fully connected networks. For all these experiments we used the Adam optimizer with a learning rate of 10^-4 until the mean squared error dropped below 10^-8. 

For Appendix Fig. <ref> and <ref>, we fixed the architecture width and depth while varying the initialization scheme, optimization method, and activation function.












§ ACKNOWLEDGEMENTS


The authors thank the Simons Institute at UC Berkeley for hosting them during the summer 2019 program on “Foundations of Deep Learning” , which facilitated this work. A. Radhakrishnan and C. Uhler were partially supported by the National Science Foundation (DMS-1651995), Office of Naval Research (N00014-17-1-2147 and N00014-18-1-2765), IBM, and a Simons Investigator Award  to C. Uhler. M. Belkin acknowledges support from NSF (IIS-1815697 and IIS-1631460) and a Google Faculty Research Award.  The Titan Xp used for this research was donated by the NVIDIA Corporation.


plain




§ ENCODING MULTIPLE SEQUENCES


Given sequences of training examples {x_i^(j)}∈ℝ^d for i ∈ [n], j ∈ [k_i], k_i ∈ℤ_≥ 0, minimizing the following sequence encoding objective with gradient descent methods leads to training sequences being stored as limit cycles:

    min_f ∈ℱ ∑_i=1^n ∑_j=1^k_if(x_i^(j  k_i) + 1) - x_i^(j)_2^2.





§ PROOFS OF INVARIANTS, THEOREM 1, AND THEOREM 2


We present the full proof of Invariants 1 and 2, Theorem 1, and Theorem 2 below.  To simplify notation, we use A to represent W_1 and B to represent W_2.







Let f(z) = A ϕ(B z) represent a 1-hidden layer network with elementwise, differentiable nonlinearity ϕ, z ∈ℝ^k_0, B ∈ℝ^k × k_0, and A ∈ℝ^k_0 × k.  Suppose that gradient descent with learning rate γ is used to minimize the following loss for the autoencoding problem with 1 training example x:

    ℒ(x, f) = 1/2 x - f(x) _2^2.

Gradient descent updates on A and B are as follows:

    A^(t+1)   = A^(t) + γ (x - A^(t)ϕ(B^(t)x)) ϕ(B^(t)x)^T 
    
        B^(t+1)   = B^(t) + γ(ϕ'(B^(t) x)) A^(t)^T (x - A^(t)ϕ(B^(t)x)) x^T,

where (ϕ'(B^(t) x)) = [ ϕ'(B_1, :^(t)x)                                ;                               ⋱                ;                                 ϕ'(B_k, :^(t)x) ] with B_i, :^(t) representing row i of matrix B^(t).



In the following, we restate and prove Invariant 1 formally:
 
    
    If A^(0) = x a^(0)^T and B^(0) = b^(0) x^T for a^(0), b^(0)∈ℝ^k, then for all time-steps t, A^(t) = x a^(t)^T and B^(t) = b^(t) x^T for a^(t), b^(t)∈ℝ^k.  
           


We provide a proof by induction.  The base case follows for t = 0 from the initialization.  Now we assume for some t that A^(t) = x a^(t)^T and B^(t) = b^(t) x^T.  Then for time t+1 we have:

    A^(t+1)   = A^(t) + γ (x - A^(t)ϕ(B^(t)x)) ϕ(B^(t)x)^T  
       = x a^(t)^T + γ (x - x a^(t)^T ϕ(B^(t)x)) ϕ(B^(t)x)^T 
       = x [ a^(t)^T + γ (1 - a^(t)^T ϕ(B^(t)x)) ϕ(B^(t)x)^T ] 
       = x a^(t+1)^T

and similarly,

    B^(t+1)   = B^(t) + γ(ϕ'(B^(t) x)) A^(t)^T (x - A^(t)ϕ(B^(t)x)) x^T 
       = b^(t) x^T + γ(ϕ'(B^(t) x)) A^(t)^T (x - A^(t)ϕ(B^(t)x)) x^T 
       = [b^(t) + γ(ϕ'(B^(t) x)) A^(t)^T (x - A^(t)ϕ(B^(t)x))] x^T 
       = b^(t+1) x^T.

Hence, since the statement holds for t+1, it holds for all time steps.  


Under the initialization in Invariant <ref>, outputs of the network are multiples of the training example.  Generalizing this result, in Materials and Methods <ref>, we prove that autoencoders trained on multiple examples produce outputs in the span of the training data.  

Using Invariant <ref>, any interpolating solution satisfies the following condition.   



Under the initialization in Invariant <ref>, if x_2 = 1 and A^(∞), B^(∞) yield zero training error, then A^(∞) = x a^T, B^(∞) = b x^T for a, b ∈ℝ^k such that a^T ϕ(b) = 1.   



From Invariant <ref>, it holds that A^(∞) = xa^T, B^(∞) = bx^T.  If the loss is minimized to zero, then f(x) = x, and thus:

    x = xa^T ϕ(bx^T x) = xa^T ϕ(b) → a^T ϕ(b) = 1,

which completes the proof.


Using Proposition <ref>, we can compute the maximum eigenvalue of the Jacobian at training example x (denoted λ_1(𝐉(f(x))). This is done in the following result.



Let the Hadamard product ⊙ denote coordinate-wise multiplication. Then λ_1(J(f(x))) = a^T ϕ'(b) ⊙ b. 


 Note that

    𝐉(f(z))    = x a^T (ϕ'(b x^T z) ⊙ b) x^T  = x a^T(ϕ'(b) ⊙ b) x^T,

and hence 𝐉(f(x)) x = x a^T(ϕ'(b) ⊙ b). This implies that x is an eigenvector of 𝐉(f(x)) with eigenvalue a^T(ϕ'(b) ⊙ b). Since x a^T(ϕ'(b) ⊙ b) x^T is rank 1, the remaining eigenvalues of 𝐉(f(x)) are all zero, which completes the proof.


We now prove Invariant <ref>, which states that if, in addition to Invariant 1, all weights in each row of A, B are initialized to be equal, then they remain equal throughout training.



Let x_2 = 1 and A^(0) = x a^(0)^T, B^(0) = b^(0) x^T for vectors a^(0), b^(0)∈ℝ^k. If a_i^(0) = a_1^(0), b_i^(0) = b_1^(0), then a_i^(t) = a_1^(t), b_i^(t) = b_1^(t) for all i ∈ [k].  


From the proof of Invariant <ref>, we have that:

    a^(t+1)^T    = a^(t)^T + γ (1 - a^(t)^T ϕ(b^(t))) ϕ(b^(t))^T  
    
    b^(t+1)   = b^(t) + γ(ϕ'(b^(t))) a^(t)^T (1 - a^(t)^T ϕ(b^(t))).

Now, if  a_i^(t) = a_1^(t), b_i^(t) = b_1^(t), then from the above this implies that a_i^(t+1) = a_1^(t+1), b_i^(t+1) = b_1^(t+1) and the proof follows by induction.  


Using Invariants <ref> and <ref>, we can now prove Thoerem 1. 



Let f(z) = A ϕ(B z) denote a 1-hidden layer network with elementwise nonlinearity ϕ, z ∈ℝ^k_0, B ∈ℝ^k × k_0, and A ∈ℝ^k_0 × k.  Let A, B be initialized as in Invariant 1, 2.  Gradient descent with learning rate γ is used to to minimize the following loss for 1 training example x ∈ℝ^k_0 with x_2 = 1 

    ℒ(x, f) = 1/2 x - f(x) _2^2.

Assuming ϕ(z)/ϕ'(z) < ∞ ∀ z ∈ℝ, then as the learning rate γ→ 0, it holds that A^(∞) = xa^T and B^(∞) = bx^T with a, b ∈ℝ^k such that

    a_i^2 - a_i^(0)^2/2   = ∫_b_i^(0)^b_iϕ(z)/ϕ'(z) dz   ;  
      a_i ϕ(b_i) = 1/k

for all i ∈ [k] with a_i = a_j, b_i = b_j for all i, j ∈ [k].  



From Invariants <ref> and <ref>, we have that:

    a_1^(t+1)   = a_1^(t) + γ (1 - k a_1^(t)ϕ(b_1^(t))) ϕ(b_1^(t))  
    
    b_1^(t+1)   = b_1^(t) + γϕ'(b_1^(t)) a_1^(t) (1 - k a_1^(t)ϕ(b_1^(t))).

Rearranging the above, we obtain

    a_1^(t+1) - a_1^(t)/ϕ(b_1^(t))   = b_1^(t+1) - b_1^(t)/a_1^(t)ϕ'(b_1^(t))
     a_1^(t)da_1^(t)/dt   = ϕ(b_1^(t))/ϕ'(b_1^(t))db_1^(t)/dt    as γ→ 0
    ∫_0^t' a_1^(t)da_1^(t)/dt dt   = ∫_0^t'ϕ(b_1^(t))/ϕ'(b_1^(t))db_1^(t)/dt dt 
    a_1^(t')^2 - a_1^(0)^2/2   = ∫_b_1^(0)^b_1^(t')ϕ(z)/ϕ'(z) dz,

wich completes the proof.


Using Proposition <ref> and Theorem <ref> above, we can calculate the values of a_1, b_1 explicitly.  After computing b_1, the following result can be used to compute λ_1(𝐉(f(x))).



Under the setting of Theorem <ref> it holds that

    λ_1(J(f(x))) = ϕ'(b_1)b_1/ϕ(b_1).
 



From Theorem <ref>, if ϕ(z) = e^2z, then the values of a_1, b_1 are given by solving:

    a_1^2    = b_1, 
    √(b_1) e^2 b_1   = 1/k.

From Theorem <ref>, the top eigenvalue of the Jacobian at the training example is 2b_1.  Note that the above equation implies b_1 decreases as k increases. At k = 1, λ_1 = .6, at k=2, λ_1 = .28, and at k=3, λ_1 = .16.  This nonlinearity guarantees that training example is an attractor.  Moreover, as there are no fixed points other than the training example, there are no spurious attractors.  


Remark.  The analysis of Theorem <ref> implies that attractors arise as a consequence of training and are not simply consequences of interpolation by a neural network with a certain architecture; see the following corollary. 

  Let x ∈ℝ^k_0 with x_2 = 1 and  f(z) = xa^T ϕ(bx^T z), where a, b ∈ℝ^k and ϕ is a smooth element-wise nonlinearity with ϕ'(z)/ϕ(z) < ∞ for all z ∈ℝ, |ϕ'(z) z/ϕ(z)| > 1 for z in an open interval 𝒪⊂ℝ.  Then there exist infinitely many b ∈ℝ^k, such that f(x) = x and x is not an attractor for f.



If a_i = a_j and b_i = b_j for all i, j ∈  [k], then Propositions <ref> and <ref> imply that f(x) = x if:

    a_i ϕ(b_i)    = 1/k
    λ_1(𝐉(f(x)))    = ϕ'(b_i) b_i/ϕ(b_i).

However, for any value of b_i such that ϕ(b_i) ≠ 0, we can select a value of a_i such that a_i ϕ(b_i) = 1/k.  Hence, we just select appropriate a_i such that a_i ϕ(b_i) = 1/k for b_i ∈𝒪.

 



§ ANALYSIS OF DEEP AUTOENCODERS WITH 1 TRAINING EXAMPLE


Let f(z) = W_d ϕ(W_d-1ϕ(W_d-2…ϕ(W_1 z) … ) ) represent a d-1 hidden layer network with elementwise nonlinearity ϕ with z ∈ℝ^k_0, W_i ∈ℝ^k_i × k_i-1, and k_d = k_0.  We again consider the setting where gradient descent with learning rate γ is used to minimize the square loss on 1 training example x.  As in the 1 hidden layer case, we derive invariants of training that allow us to derive a closed form solution when training on 1 example in the gradient flow setting.  

Firstly, the following invariant (analogous to Invariant <ref>) holds in the deep setting.  



If W_d^(0) = xa^(0)^T and W_1^(0) = b^(0)x^T for b^(0), a^(0)∈ℝ^k_1, ℝ^k_d-1 respectively, then for all time-steps t, W_d^(t) = xa^(t)^T and W_1^(t) = b^(t)x^T for b^(t), a^(t)∈ℝ^k_1, ℝ^k_d-1 respectively. 


The proof is analogous to that of Invariant <ref>.  Now that we have invariants of training for layers W_d, W_1, we still need to find an invariant for the intermediate layers W_2, …, W_d-1.  The following invariant extends Invariant <ref> to the deep setting.



Assume x_2 = 1 and W_d^(0) = xa^(0)^T, W_1^(0) = b^(0)x^T for b^(0), a^(0)∈ℝ^k_1, ℝ^k_d-1 respectively.  Let 1_m × n denote the m × n matrix of all 1's.  If a_j^(0) = a_1^(0), b_l^(0) = b_1^(0), W_i^(0) = w_i^(0)1_k_i × k_i-1 with w_i^(0)∈ℝ, then for all time-steps t, a_j^(t) = a_1^(t), b_l^(t) = b_1^(t), W_i^(t) = w_i^(t)1_k_i × k_i-1 for j ∈ℝ^k_d-1, l ∈ℝ^k_1, and i ∈{2, …, d-1}.   


That is, in the deep setting, the intermediate layers remain rank 1 throughout training, if they are initialized to be a constant times the all 1's matrix.  The proof follows by induction and is analogous to the proof of Invariant <ref>.  


Let f(z) = W_d ϕ(W_d-1ϕ(W_d-2…ϕ(W_1 z) … ) ) denote a d-1 hidden layer network with elementwise nonlinearity ϕ, with z ∈ℝ^k_0, W_i ∈ℝ^k_i × k_i-1, and k_d = k_0.  Let {W_i}_i=1^d be initialized as in Invariants 3, 4.  Gradient descent with learning rate γ is used to to minimize the following loss for 1 training example x ∈ℝ^k_0 with x_2 = 1:


    ℒ(x, f) = 1/2 x - f(x) _2^2


Assuming ϕ(z)/ϕ'(z) < ∞ ∀ z ∈ℝ, then as the learning rate γ→ 0, we have the following relationships between the weights a_1^(t), b_1^(t), w_i^(t)∈ℝ for i ∈{1, … d-2}:

    w_1^(t')^2 - w_1^(0)^2/2   = ∫_b_1^(0)^b_1^(t')ϕ(b_1)/ϕ'(b_1) k_2 db_1, 
    w_i+1^(t)^2 - w_i+1^(0)^2/2   = ∫_w_i^(0)^w_i^(t)ϕ(w_i k_i ϕ(w_i-1 k_i-1…ϕ(b_1) …))/ϕ'(w_i k_i ϕ(w_i-1 k_i-1…ϕ(b_1) …))1/ϕ(w_i-1 k_i-1…ϕ(b_1) …) k_i+1 dw_i, 
    a_1^(t)^2 - a_1^(0)^2/2   = ∫_w_d-1^(0)^w_d-2^(t)ϕ(w_d-1 k_d-1ϕ(w_d-2 k_d-2…ϕ(b_1) …))/ϕ'(w_d-1 k_d-1ϕ(w_d-2 k_d-2…ϕ(b_1) …))1/ϕ(w_d-2 k_d-2…ϕ(b_1) …) dw_d-1.




The proof is analogous to the proof of Theorem <ref>.  In addition, analogously to Theorem <ref>, we can explicitly compute the maximum eigenvalue of the Jacobian at the training example x using the following corollary.


Under the setting of the theorem above, it holds that

    λ_1(𝐉(f(x))) = (∏_i=2^d-1ϕ'(w_i k_i-1ϕ(w_i-1 k_i-2…ϕ(b_1) …))w_i k_i-1) ϕ'(b_1) b_1/ϕ(w_d-1 k_d-2ϕ(w_d-2 k_d-3… (ϕ(b_1)) …))




The proof is analogous to that of Theorem <ref>.  Note that in the theorem above, the integration for later layer weights becomes increasingly complicated, since the integration depends on the values of the previous weights.  Fortunately, for certain nonlinearities, the integral is tractable; see the example below.  


Let ϕ(x) = x^m and assume k_i = 1 for i ∈ [d-1].  Then from the theorem above, it holds that:

    w_i+1^2 = w_i^2/m ` ∀ i ∈ [d-1]

From the corollary above, λ_1(𝐉(f(x))) = m^d-1.  Hence if m < 1, then x becomes an attractor.  


Remarks. In the 1 hidden layer setting, regardless of how large the width, λ_1(𝐉(f(x))) = m when using ϕ(z) = z^m.  Thus, the example above demonstrates that depth can make over-parameterized autoencoders more contractive even when width cannot.  




§ TRAINED AUTOENCODERS PRODUCE OUTPUTS IN THE SPAN OF THE 
TRAINING DATA


In the following section, we generalize Invariant 1 to the setting with multiple training examples and thus, demonstrate that trained autoencoders produce outputs in the span of the training data.




    Let f(z) = A ϕ(B z) represent a 1-hidden layer network with elementwise, differentiable nonlinearity ϕ, z ∈ℝ^k_0, B ∈ℝ^k × k_0, and A ∈ℝ^k_0 × k.  Suppose that gradient descent with learning rate γ is used to minimize the following loss for the autoencoding problem with n training examples {x^(i)}_i=1^n:

    ℒ(x, f) = 1/2 x^(i) - f(x^(i)) _2^2.

    If A^(0) = ∑_i=1^nx^(i)a_i^(0)^T and B^(0) = ∑_i=1^nb_i^(0)x^(i)^T for vectors a_i^(0), b_i^(0)∈ℝ^k, then for all time-steps t, it holds that A^(t) = ∑_i=1^nx^(i)a_i^(t)^T and B^(t) = ∑_i=1^nb_i^(t)x^(i)^T for some vectors a_i^(t), b_i^(t)∈ℝ^k.  



The proof exactly follows the proof of Invariant <ref>.  For completeness, we show the proof for A^(t) below.  We again provide a proof by induction.  The base case follows for t = 0 from the initialization.  Now we assume for some t that A^(t) = ∑_i=1^nx^(i)a_i^(t)^T and B^(t) = ∑_i=1^nb_i^(t)x^(i)^T.  Then for time t+1 we have:

    A^(t+1)   = A^(t) + γ∑_i=1^n(x^(i) - A^(t)ϕ(B^(t)x^(i))) ϕ(B^(t)x^(i))^T  
       = ∑_i=1^nx^(i)a_i^(t)^T + γ∑_i=1^n(x^(i) - ∑_j=1^nx^(j)a_j^(t)^T ϕ(B^(t)x^(i))) ϕ(B^(t)x^(i))^T 
       = ∑_i=1^n x^(i) [ a_i^(t)^T + γ (1 - ∑_j=1^na_i^(t)^T ϕ(B^(t)x^(j))) ϕ(B^(t)x^(j))^T ] 
       =  ∑_i=1^n x^(i)a_i^(t+1)^T.

The proof for B^(t) follows analogously.  Hence, since the statement holds for t+1, it holds for all time steps, which completes the proof. 




§ PROOFS OF THEOREM 3 AND 4


By analyzing sequence encoders as a composition of maps, we prove that sequence encoding provides a more efficient mechanism for memory than autoencoding.  We begin by restating Theorem <ref> below.



Let f(z) = W_1 ϕ(W_2 z) denote a 1-hidden layer network with elementwise nonlinearity ϕ and weights W_1 ∈ℝ^k_0 × k and W_2 ∈ℝ^k × k_0, applied to z ∈ℝ^k_0. Let x^(i), x^(i+1)∈ℝ^k_0 be training examples with x^(i)_2 = x^(i+1)_2 = 1. Assuming that ϕ(z)/ϕ'(z) < ∞ ∀ z ∈ℝ and there exist u^(0), v^(0)∈ℝ^k such that W_1^(0) = x^(i+1)u^(0)^T and W_2^(0) = v^(0)x^(i)^T with u_i^(0) = u_j^(0), v_i^(0) = v_j^(0) ∀ i, j ∈ [k], then
gradient descent with learning rate γ→ 0 applied to minimize

    ℒ(x, f) = 1/2 x^(i+1) - f(x^(i)) _2^2

leads to a rank 1 solution
W_1^(∞) = x^(i+1) u^T and W_2^(∞) = v x^(i)^T with u, v ∈ℝ^k satisfying

    u_i^2 - u_i^(0)^2/2   = ∫_v_i^(0)^v_iϕ(z)/ϕ'(z) dz,   and  
      u_i ϕ(v_i) = 1/k,

and u_i = u_j, v_i = v_j for all i, j ∈ [k].


The proof exactly follows that of Theorem <ref>, since updates to u, v do not depend on the data x^(i), x^(i+1).      



Let {x^(i)}_i=1^n be n training examples with x^(i)_2 = 1  for all i ∈ [n], and let {f_i}_i=1^n denote n 1-hidden layer networks satisfying the assumptions in Theorem <ref> and trained on the loss in Eq. (<ref>).  Then the composition f = f_n ∘ f_n-1∘…∘ f_1 satisfies:

    λ_1(𝐉(f(x^(1)))= ∏_i=1^n( ϕ'(v_j^(i)) v_j^(i)/ϕ(v_j^(i))).




From Theorem <ref>, each of the f_i for i ∈ [n] have the following form after training:

    f_i(z) = x^(i n + 1)u^(i)^T ϕ(v^(i)x^(i)^T z)

with u^(i)^T ϕ(v^(i)) = 1 and u_l^(i) = u_j^(i), v_l^(i) = v_j^(i) for l, j ∈ [k] and i ∈ [n].

Hence the composition f is given by:

    f(z)    = (f_n ∘ f_n-1∘…∘ f_1)(z) 
       = x^(1)u^(n)^T ϕ(v^(n)x^(n)^T x^(n)u^(n-1)^T ϕ(v^(n-1) x^(n-1)…ϕ(v^(1)x^(1)^T z) …)) 
       = x^(1)u^(n)^T ϕ(v^(n)u^(n-1)^T ϕ(v^(n-1)…ϕ(v^(1)x^(1)^T  z) …))     since x^(i)_2 = 1 for all i ∈ [n].


We now compute the Jacobian of f at the example x^(1).  Since u_i k ϕ(v_i) = 1 for all i ∈ [n] and x^(1)_2 = 1, it holds that

    𝐉(f(x^(1))) = x^(1)(∏_i=1^n u_j^(i) k ϕ'(v_j^(i)) v_j^(i)) x^(1)^T.


However, we know that u_j^(i) = 1/k ϕ(v_j^(i)), and so we have that

    λ_1(𝐉(f(x^(1)))= ∏_i=1^n( ϕ'(v_j^(i)) v_j^(i)/ϕ(v_j^(i))),

which completes the proof.






§ LIMIT CYCLES IN RECURRENT NEURAL NETWORKS


In order to demonstrate that recurrent neural networks (RNNs) can also memorize and recall sequences, we trained a vanilla RNN (whose architecture is detailed in Appendix Figure <ref>) to encode the following sentence from our introduction: “Hopfield networks are able to store binary training patterns as attractive fixed points.”  When training the RNN, we encoded each word using 1-hot representation i.e., since there are 13 words in the sentence, we represented each word with a vector of size 13 and placed a “1” in the index corresponding to the word.  

We trained such that each word is mapped to the next modulo 13 using the Cross Entropy Loss (as is done in practice).  Unlike the other settings considered in this work, RNNs are used to generate new sentences after training by sampling a new word from the vector output given a previous word[This process is usually started from inputting the all zero vector.].  Under our architecture, we found that repeatedly choosing the highest probability word given the previous word consistently output the entire training sentence regardless of the number of times this sampling process was repeated.  




§ SEQUENCE ENCODING AUDIO


In order to demonstrate that fully connected networks can memorize high dimensional sequences, we captured an audio clip of an 8 second recording from the Donald Trump talking pen.  Each second of the audio contains 22,050 frequencies, and we trained a fully connected network to map from the frequencies in second i to second i+1  8.  We have attached an audio sample[Located at: <https://github.com/uhlerlab/neural_networks_associative_memory>] titled “trump_quote_recovered_from_noise.mp3” demonstrating that iteration from random noise leads to recovery of the entire quote.  The full architecture used is provided in Appendix Figure <ref>. 


























































