Source-linked AI summary
On a model of associative memory with huge storage capacity
Mete Demircigil, Judith Heusel, Matthias Löwe, Sven Upgang, Franck Vermet
TL;DR
The paper asks whether generalized interaction functions can increase associative-memory storage capacity beyond standard Hopfield limits. It proves polynomial-capacity claims and analyzes their formal exponential-interaction limit. The resulting model stores exponentially many random patterns while retaining attraction basins capable of correcting order-N errors.
Problem
The standard Hopfield model has limited storage capacity, motivating the question of whether generalized interaction functions can store more patterns while preserving retrieval stability.
Method
The paper proves the polynomial interaction claims and studies the formal limit n → ∞, corresponding to the exponential interaction F(x) = e^x.
Results
For 0 < α < log(2)/2, the exponential model stores M = exp(αN) + 1 uniformly random patterns and supports correction from Hamming-sphere perturbations.
Takeaways & Limitations
Exponential storage capacity does not require vanishing attraction basins: the dynamics can repair an amount of random errors of order N.
Takeaways & Limitations
The polynomial theorem's proof is constrained by the polynomial form of the model's energy, and the Hamming-ball extension is stated as an analogous consequence of the sphere result.
Abstract
from arXiv · showhide
In [7] Krotov and Hopfield suggest a generalized version of the well-known Hopfield model of associative memory. In their version they consider a polynomial interaction function and claim that this increases the storage capacity of the model. We prove this claim and take the "limit" as the degree of the polynomial becomes infinite, i.e. an exponential interaction function. With this interaction we prove that model has an exponential storage capacity in the number of neurons, yet the basins of attraction are almost as large as in the standard Hopfield model.
1. Introduction
The paper studies how generalized interaction functions affect associative-memory capacity, proving polynomial-capacity claims and extending them to exponential interactions. It shows that exponential storage can coexist with attraction basins large enough to correct order-N random errors.
- Motivation: The central question is how many independently and identically distributed patterns the generalized associative-memory model can store.Storage is defined through stability of a pattern under the retrieval dynamics.
- Existing capacity results: The standard Hopfield model stores M = C log N patterns when all patterns must be stable simultaneously, while allowing retrieval errors can yield M = αN with α < 0.138.The fixed-pattern threshold is stated separately as C < 1/4, whereas simultaneous stability uses C < 1/2.
- Generalized model: The generalized model replaces the standard updating dynamics with an interaction function F, including polynomial choices F(x) = x^n.For F(x) = x^2, the model reduces to the standard Hopfield model with quadratic crosstalk terms.
- Polynomial interactions: The paper proves that the polynomial model can store M = α^nN^(n−1) patterns with small retrieval errors and M = N^(n−1) / (c_n log N) patterns when a fixed pattern must be stable.The second result holds with probability converging to 1 and c_n > 2(2n − 3)!!.
- Exponential interaction: The paper then takes the formal n → ∞ limit, obtaining an exponential interaction F(x) = e^x and super-polynomial storage capacity.For 0 < α < log(2)/2, Theorem 1.3 considers M = exp(αN) + 1 uniformly random patterns.
- Attraction basins: Despite the capacity increase, the exponential model can repair random errors of order N, and the theorem extends analogously from Hamming spheres to Hamming balls.The sphere result bounds correction for arbitrary patterns in lower-radius spheres or balls.
2. Proofs
The proofs establish the polynomial capacity claim and show that exponential interactions support exponentially many patterns while correcting random errors. The arguments use large-deviation, moment-generating-function, union-bound, and signal-versus-noise estimates.
- Exponential interaction: Large-deviation bounds show that the probability of harmful overlap or noise events vanishes as N → ∞ under the theorem's parameter condition.The proof uses exponential Chebyshev bounds, continuity and concavity of the rate function, and demonstrates that both resulting terms converge to zero.
- Exponential interaction: The exponential-model proof reformulates the update rule so that a neuron remains correct whenever the noise term is smaller in magnitude than the signal term.A retrieval error therefore requires |E_noise| ≥ |E_signal|, which is then bounded probabilistically.
- Polynomial interaction: The polynomial-model proof bounds the relevant moment-generating function by splitting overlap contributions and controlling tail events with large-deviation estimates.The argument separates significant-overlap patterns, divides sums into two ranges, and uses estimates for binomial and symmetric ±1 variables.
- Exponential interaction: The proof concludes after establishing the auxiliary divergence p(M − 1) → ∞ and verifying the bounds required for the two overlap ranges.These estimates complete the argument for the exponential model's retrieval guarantee.