Capacity of the Hebbian-Hopfield network associative memory
This provides incremental improvements in understanding the theoretical limits of associative memory models, relevant for researchers in neural networks and statistical physics.
The paper tackles the capacity of the Hebbian-Hopfield network associative memory by deriving explicit capacity characterizations for two pattern basins of attraction, obtaining values like approximately 0.137906 and 0.129490, and showing fast convergence with numerical work yielding approximately 0.138186 and 0.12979.
In \cite{Hop82}, Hopfield introduced a \emph{Hebbian} learning rule based neural network model and suggested how it can efficiently operate as an associative memory. Studying random binary patterns, he also uncovered that, if a small fraction of errors is tolerated in the stored patterns retrieval, the capacity of the network (maximal number of memorized patterns, $m$) scales linearly with each pattern's size, $n$. Moreover, he famously predicted $α_c=\lim_{n\rightarrow\infty}\frac{m}{n}\approx 0.14$. We study this very same scenario with two famous pattern's basins of attraction: \textbf{\emph{(i)}} The AGS one from \cite{AmiGutSom85}; and \textbf{\emph{(ii)}} The NLT one from \cite{Newman88,Louk94,Louk94a,Louk97,Tal98}. Relying on the \emph{fully lifted random duality theory} (fl RDT) from \cite{Stojnicflrdt23}, we obtain the following explicit capacity characterizations on the first level of lifting: \begin{equation} α_c^{(AGS,1)} = \left ( \max_{δ\in \left ( 0,\frac{1}{2}\right ) }\frac{1-2δ}{\sqrt{2} \mbox{erfinv} \left ( 1-2δ\right )} - \frac{2}{\sqrt{2π}} e^{-\left ( \mbox{erfinv}\left ( 1-2δ\right )\right )^2}\right )^2 \approx \mathbf{0.137906} \end{equation} \begin{equation} α_c^{(NLT,1)} = \frac{\mbox{erf}(x)^2}{2x^2}-1+\mbox{erf}(x)^2 \approx \mathbf{0.129490}, \quad 1-\mbox{erf}(x)^2- \frac{2\mbox{erf}(x)e^{-x^2}}{\sqrtπx}+\frac{2e^{-2x^2}}π=0. \end{equation} A substantial numerical work gives on the second level of lifting $α_c^{(AGS,2)} \approx \mathbf{0.138186}$ and $α_c^{(NLT,2)} \approx \mathbf{0.12979}$, effectively uncovering a remarkably fast lifting convergence. Moreover, the obtained AGS characterizations exactly match the replica symmetry based ones of \cite{AmiGutSom85} and the corresponding symmetry breaking ones of \cite{SteKuh94}.