Capacity of the Hopfield-Hebbian dynamics with correlated patterns

Introduction

The early spin-glass neural networks (NN) forms [29] were superseded by the Hopfield’s auto-associative memories propositions [14]. The main idea centers around the following concept: starting in a vicinity of an already stored/memorized pattern, an iterative dynamics remains trapped by local optima not far away and allows retrieval of the stored pattern. In other words, patterns possess the so-called basins of attraction that simple iterative dynamics can not escape ensuring that a pattern is properly retrieved (and not confused by an unwanted convergence to a different one). The memory capacity – defined as the maximum allowable number of the stored patterns for which the proper retrieval is possible – is the key feature that describes the effectiveness of these types of associative memories. As such, it has been thoroughly studied since the appearance of the Hopfield’s introductory paper [14]. We start by surveying some of the key achieved milestones. That will eventually allow us to properly contextualize our own results.

Prior work and contextualization

Trying to model cognitive type of thinking, Hebb considered an associative type of learning principle [13]. In [14], Hopfield further connected such learning principles to a basic iterative dynamics. Overwhelming numerical evidence suggested that the proposed dynamics might exhibit a remarkable convergence property, where (rather quickly) one ends up either in one of the $n$-dimensional stored binary patterns or in its a close proximity. In a way, provided that their number is not too high, the stored patterns are observed as stable and surrounded by sizeable basins of attraction, allowing for their efficient retrieval.

Utilizing a simple Gaussian noise argument and considering independent patterns, [14] showed that (with probability approaching 1 as $n \to\infty$) the networks associative capacity (maximal number of reliably stored patterns) is approximately $m \approx\frac{n}{2\log(n)}$. Hopfield observed an even more remarkable property: if a small fraction of errors is allowed in retrieved patterns, then the so-called linear capacity scaling $m \sim n$ is possible as well. Moreover, Gaussian noise arguments allowed for a very precise prediction of the underlying linear proportionality $\alpha\triangleq\lim_{n\to\infty}\frac{m}{n} \approx0.14$ achieved with only 0.4% of errors. Such a set of developments is truly remarkable and to this day remains one of the most fascinating analytical NN results.

As Hopfield’s predictions were basically indistinguishable from the results obtained simulating proposed dynamics, an avalanche of research regarding various related topics followed through the better part of the last four decades. Some of the most relevant analytical results that particularly relate to our own results are discussed below. As almost all of them consider binary patterns statistical context similar or identical to the one from [14], we skip reemphasizing it. Along the same lines, here and later on throughout the paper, we often skip repetitively stating that the known results hold with high probability (i.e., with probability approaching 1 as the patterns’ size/length $n \to\infty$).

Exact retrieval: Early Hopfield’s noise considerations, were followed by the memory capacity analysis via the statistical physics replica methods in [6]. Under the replica symmetry (RS) ansatz, the very same $m \approx\frac{n}{2\log(n)}$ estimate for exact retrieval were obtained. The very first set of mathematically rigorous results in this direction arrived with the appearance of [23], where sublinear exact retrieval scaling of [6, 14] was matched. In [11], the RS estimate $\frac{n}{2\log(n)}$ from [6] was established as a rigorous lower bound. Results of [23] were then in a way extended in [16] where existence of a nonzero basin of attraction around patterns is shown. Strong numerical evidence suggesting likely impossibility of exact retrieval in regimes with the number of patterns $m$ scaling stronger than $\sim\frac{n}{\log(n)}$ was presented in [23] as well. This effectively suggested that to achieve a linear scaling, consideration of approximate retrieval (where one allows for a small fraction of errors in retrieved patterns) might be needed. This again was in an excellent agreement with early Hopfield observations [14].

Approximate retrieval: As stated above, Hopfield’s rough analytical arguments coupled with strong numerical algorithmic evidence suggested that the precise value of the underlying linear proportionality in approximate retrieval is likely around $\alpha\triangleq\lim_{n\to\infty}\frac{m}{n} \approx0.14$. Existence of a basin of attraction around each of the stored patterns emerged as a key concept driving the success of Hopfield propositions.

The so-called AGS (Amit-Gutfreund-Sompolinsky) basin of attraction was analyzed in [6] via replica methods (assuming RS ansatz). It was obtained that Hopfield dynamics converges to a local energy (objective) minima within the basin of attraction (thereby staying trapped in a close vicinity of the stored pattern) provided that $\alpha\approx0.137906$. [6] further predicted that potential additional replica symmetry breaking (RSB) corrections might not necessarily be quantitatively substantial. This prediction was confirmed in [31], where negligibly better estimates $\alpha\approx0.138186$ and $\alpha\approx0.138187$ were obtained with 1RSB and 2RSB ansatz, respectively. The AGS basins were further analyzed in [11] where $\alpha\ge0.113$ estimate was obtained and in [38] where both RS and 1RSB estimates were matched via fully lifted RDT.

As an alternative to the above mentioned AGS basin, the NLT basin was considered in [19, 20, 21, 24]. In addition to the AGS type of energy well around patterns, MLT imposes that the local energy maximum within the well must not be smaller than the one already achieved by the pattern itself. Due to further restrictions, NLT basin capacity estimates are automatically lower bounds for the corresponding AGS ones. Initial NLT basin capacity estimate $\alpha\ge0.056$ obtained in [24] was first improved to $\alpha\ge0.071$ in [19, 20] and then to $\alpha\ge0.08$ in [45]. In [38], the corresponding first and second lifting level RDT estimates, $\alpha\approx0.1295$ and $\alpha\approx0.1298$, were obtained as well.

Different learning rules: If one deviates from the Hebbian learning principle, capacity can grow beyond linear $n$ scaling. The Hebbian rule assumes the quadratic (polynomial of degree 2) objective. Alternatively, utilizing an objective based on a general overlap power (polynomial of degree $p$), the capacity of exact and approximate retrievals scale as $m \sim\frac{n^{p-1}}{\log(n)}$ and $m \sim n^{p-1}$, respectively [1, 12, 17]. On the other hand, relying on the exponential interactions, allows for the exponential capacity growth [10, 22, 30, 46]. One the one hand, these results allow for a substantial increase of the associative capacity. On the other, the connection between the employed learning principles and the neurological behavior might not necessarily as clear as in model with the Hebbian rule.

Correlated/noisy patterns: Majority of the above works consider a common scenario, where the patterns are independent among themselves. Such an idealized context does provide a sufficiently simplified model that allows for analytical tractability. Moreover, results obtained for such models provide an intuition that is presumed to be useful for a better understanding of more complex NNs. In practice the datasets are not as ideal. Instead of being independent the patterns are likely correlated. Such correlations may act as a noise or even portray the presence of some intrinsic features (data redundancy or heterogeneity) that go beyond what can be captured through presumed pattern independence. Along the same lines, if one moves away from the simple pattern retrieval tasks and considers more challenging sequence retrieval, disentanglement, generalization or categorization, then again the idealistic nature of independent patterns might not suffice [2, 5, 8, 15, 18].

Analytical treatments of generic practical correlated scenarios are significantly more challenging. Nonetheless, as understanding of NN’s functioning deepened over the last several years, a lot of effort has been put towards achieving further progress. A particularly successful has been a line of work related to archetype/example patterns. As it is also very closely related to the topics that we study in this paper, we discuss it next in more detail.

Archetype/example patterns: A type of data often used to highlight the correlations effects assumes that to each pattern – called archetype or ground truth – from a set of independent patterns, one associates its $M$ slightly independently perturbed example versions. Perturbations are typically realized by multiplying original pattern elements by independent Bernoulli random variables of mean $r \in[0, 1]$ (for $r = 1$, one has the (redundant) standard Hopfield-Hebbian model with each pattern repeated $M$ types). When $r < 1$, the mathematical problems associated with approximate retrieval are then also tightly connected to generalization, inference, and disentanglement as well [3, 4, 5]. However, compared to plain (uncorrelated) scenarios, obtaining underlying statistical mechanics pictures is significantly more complicated.

Recently, spectral methods have emerged as particularly successful analytical alternatives to classical replica methods [3, 4]. The underlying ideas are truly remarkable and rely on spectral fragmentation (in a way resembling the famous BBP phase transition observed in the so-called spiked models [7]). As system parameters that govern correlations change, the spectrum of particularly designed relevant system matrices changes as well. The changes are of quantitative type until parameters’ values reach phase-transition regions, where a qualitative change – fragmenting of the spectrum from a single bulk structure into a two-pieces formation – happens. Onset of such a fragmentation is then predicted as a conceivably accurate approximation of the underlying retrieval phase-transition – in a direct analogy with the appearance of the so-called spectral outliers in BBP transitions considerations [7]. Moreover, not only are these ideas conceptually beautiful, they give excellent practical results as well. In particular, combining spectral and replica theory [4] obtained very elegant single line explicit expression that approximately characterizes impact of correlation parameters $M$ and $r$ on capacity phase-transitions. In case of so-called full rank ($\alpha M > 1$) and low correlated (smaller $r$) data, the approximations obtained in [4] very closely approach the true performance of the underlying retrieval dynamics. As correlations increase the predictive power decreases and they slowly deviate from the dynamics performance.

Our contributions

In this paper we consider the very same archetypes/examples set of correlated patterns. We develop Random Duality Theory (RDT) based framework for the analysis of the retrieval (or analogously inference/generalization) dynamics. Utilizing the first lifted level of the framework, we obtain retrieval capacity estimates that are explicit functions of both key correlation parameters $M$ and $r$. For concreteness, we focus on the full rank data (regime where spectral methods tend to show slight deviations from practical dynamics). Our results confirm that spectral predictions from [4] are indeed excellent approximations in the low correlations regimes (precisely as observed in [4]). Moreover, we also manage to close the gap for higher correlations. In particular, after practically running the dynamics, we observe that already for fairly small problem dimensions (on the order of $\sim1000$), simulation results are in an excellent agreement with our theoretical predictions in the entire $r \in[0, 1]$ range and for all $M$. Implementing the fully lifted RDT machinery (i.e. conducting the analysis and numerical evaluations on higher lifting levels) would keep closing the gap further. However, keeping in mind that in the ideal scenario (with $r = 1$ and $M$ redundant patterns), the capacity estimates obtained on the first ($\approx0.1379$) and second ($\approx0.1381$) lifting level differ by $\sim0.01\%$, no significant corrections on higher lifting levels are expected.

Mathematical preliminaries

We consider standard statistical Hopfield archetype/examples setup. To that end, let $\bar{\mathbf{g}}^{(i)} \in S_H^n$, $i = 1,2,\ldots,m$, be $m$ independently and uniformly randomly chosen binary patterns ($S_H^n$ is the unit $n$-dimensional Hamming sphere, i.e. $S_H^n \triangleq\left\{-\frac{1}{\sqrt{n}},\frac{1}{\sqrt{n}}\right\}^n$). We call these patterns archetypes and denote by $\bar{g}^{(i)}_j$, $j = 1,2,\ldots,n$, their $j$-th components. For a fixed correlation parameter $r \in[0,1]$, we associate with each $\bar{\mathbf{g}}^{(i)}$ $M$ correlated patterns (so-called examples), $\bar{\mathbf{g}}^{(i,k)}$, in the following way

$\eta^{(k)}_j$ are independent among themselves for any choice $j$ and $k$. For any $i$, we also set

Basically, $\bar{\mathcal{G}}^{(i)}$ is an array of $M$ patterns associated via correlation (1) with $\bar{\mathbf{g}}^{(i)}$. We further set

and consider the following Hopfield sequential dynamics

Here and throughout the paper, we adopt notational convention that $\mathcal{G}_{i,j}$ stands for the $ij$-th component of $\mathcal{G}$ and $\mathcal{G}_{i,:}$ is the $i$-th row of $\mathcal{G}$. Defining the energy objective as

we easily have that the above dynamics converges to its a local minimum. Taking $\bar{\mathbf{x}}$ as the dynamics converging point

we have for the local energy minimum achieved at $\bar{\mathbf{x}}$

Moreover,

Within the standard Hopfield retrieval, the main idea is that (provided “sufficient pattern orthogonality”) the converging point may exactly or approximately match one of the stored patterns. In other words, it may happen that $\bar{\mathbf{x}}^{T}\bar{\mathbf{g}}^{(i)}=1$ or $\bar{\mathbf{x}}^{T}\bar{\mathbf{g}}^{(i)}=1-2\delta$, for a small $\delta>0$. The same philosophy applies here as well. The difference though is that this time around the $\bar{\mathbf{g}}^{(i)}$ are not the patterns that one can access (it should be noted that they are not parts of $\mathcal{G}$ and do not participate in dynamics (4)). Instead they are the archetypes and one wonders whether these ground truth patterns can be recovered even though they can not be accessed. As we will see, analogously to [6, 11, 14, 23, 38] this will again turn out to be possible even in the linear scaling regime. However, the critical number of patterns for which it will be possible will be a function of underlying correlations parameters $M$ and $r$ that govern to what extent the ground truth archetypes, $\bar{\mathbf{g}}^{(i)}$, are hidden within their associated examples groups $\bar{\mathcal{G}}^{(i)}$.

Basin of attraction and dynamics capcity

The basin of attraction that we consider is conceptually similar to AGS [6]. However, there are also a few technical differences that we highlight below.

For concreteness and easiness of writing, we take without loss of generality $\mathbf{g}^{(1)}=\frac{1}{\sqrt{n}}$ as the targeted archetype pattern. Analogously to the AGS considerations from [6], one can define the capacity of the dynamics (4) as the largest $\alpha\triangleq\lim_{n\to\infty}\frac{m}{n}$ such that for some (small) $\delta>0$