Capacity of the Hebbian-Hopfield network associative memory
Mihailo Stojnic
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
$\alpha_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}
  \alpha_c^{(AGS,1)} = \left ( \max_{\delta\in \left ( 0,\frac{1}{2}\right )
}\frac{1-2\delta}{\sqrt{2} \mbox{erfinv} \left ( 1-2\delta\right )} -
\frac{2}{\sqrt{2\pi}} e^{-\left ( \mbox{erfinv}\left ( 1-2\delta \right )\right
)^2}\right )^2 \approx \mathbf{0.137906} \end{equation}
  \begin{equation}
  \alpha_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{\pi}x}+\frac{2e^{-2x^2}}{\pi}=0.
\end{equation}
  A substantial numerical work gives on the second level of lifting
$\alpha_c^{(AGS,2)} \approx \mathbf{0.138186}$ and $\alpha_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}.