# Content addressable memory without catastrophic forgetting by
heteroassociation with a fixed scaffold

Sugandha Sharma  Sarthak Chandra  Ila R. Fiete

###### Abstract

Content-addressable memory (CAM) networks, so-called because stored items can
be recalled by partial or corrupted versions of the items, exhibit near-
perfect recall of a small number of information-dense patterns below capacity
and a ‘memory cliff’ beyond, such that inserting a single additional pattern
results in catastrophic forgetting of all stored patterns. We propose a novel
ANN architecture, Memory Scaffold with Heteroassociation (MESH), that
gracefully trades-off pattern richness with pattern number to generate a CAM
continuum without a memory cliff: Small numbers of patterns are stored with
complete information recovery matching standard CAMs, while inserting more
patterns still results in partial recall of every pattern, with an information
per pattern that scales inversely with the number of patterns. Motivated by
the architecture of the Entorhinal-Hippocampal memory circuit in the brain,
MESH is a tripartite architecture with pairwise interactions that uses a
predetermined set of internally stabilized states together with
heteroassociation between the internal states and arbitrary external patterns.
We show analytically and experimentally that MESH nearly saturates the total
information bound (given by the number of synapses) for CAM networks,
invariant of the number of stored patterns, outperforming all existing CAM
models.

Machine Learning, ICML

1 Department of Brain and Cognitive Sciences, Massachusetts Institute of
Technology; 2 Center for Brains, Minds and Machines; 3 McGovern Institute of
Brain Research; 4 K. Lisa Yang ICoN Center.

##  1 Introduction

Figure 1: (a) A fully recurrently connected Hopfield CAM network (Hopfield,
1982, 1984). (b) Bipartite CAM networks: Bipartite Expander Hopfield Network
(Chaudhuri & Fiete, 2019), Modern Hopfield Network (Krotov & Hopfield, 2020).
(c) Overparameterized tail-biting autoencoder as a CAM (Radhakrishnan et al.,
2020). (d) Schematic of the memory cliff exhibited by most CAM models:
addition of patterns beyond the critical capacity leads to catastrophic loss
of all patterns. (e) Theoretical upper-bound on information storage for CAM
networks with $N^{2}$ synapses (grey dashed line); existing networks each
approach the envelope at one point (i.e., for a specific number of patterns),
and otherwise remain far from it. (f) Tripartite architecture of MESH, our
proposed model. (g) The desired CAM continuum: a single network with
information storage paralleling the theoretical bound envelope regardless of
the number of stored patterns. Gray arrows: predetermined fixed weights; black
arrows: learned weights.

Content-addressable memory (CAM) networks are attractive models of long-term
human memory: Humans are experts at recognizing situations or items they have
encountered before, and often fill in the details from partial or noisy
information. When presented by a partial or corrupted version of a previously
seen input, a CAM maintains memories that can be reconstructed from corrupted
cues. Recurrently connected CAMs, for example the Hopfield network (XXX),
additionally encode the memorized states as fixed points of their dynamics.
They use their dynamics to drive the input state to one of the nearest fixed
points and keep it there. Dynamical fixed-point CAM networks can therefore
also function as short-term memory networks for the acquired long-term
memories. Therefore, CAMs are also powerful memory models for ANNs.

Several network architectures support CAM dynamics, including the Hopfield
network (Hopfield, 1982, 1984) (Fig. 1a), several variants of the Hopfield
network (Personnaz et al., 1985; Tsodyks & Feigel’man, 1988; Krotov &
Hopfield, 2020) (Fig. 1a,b), and overparametrized autoencoders (Radhakrishnan
et al., 2020) (Fig. 1c). However, all these CAM architectures exhibit a memory
cliff, beyond which adding a single pattern leads to catastrophic loss of all
patterns (Fig. 1d). The total information content of CAM networks is bounded
theoretically by $\mathcal{O}(N^{2})$, the number of synapses in the network
(Abu-Mostafa, 1989; Gardner, 1988), Fig. 1e, defining a total information
budget to be split between the number of stored patterns and information per
pattern. However, most CAM networks approach that bound only when storing a
fixed, specific number of pattterns (Fig. 1e): Different CAM networks (defined
by their inputs, architecture, or weight and activity update rules) touch this
total information envelope at different points, with some storing a small
number of maximally detailed memory states, others storing a larger number of
less-detailed states. None of these models have the flexibility to span the
memory envelope such that the information recalled per pattern is continuously
traded off for increasing numbers of stored patterns in an online way, while
preserving a constant total information that remains close to the information
envelope.

In this paper we propose a novel and biologically motivated memory
architecture, Memory Scaffold with Heteroassociation (MESH), that generates a
CAM continuum (see Fig. 1f for a schematic of the network architecture). MESH
breaks the problem of associative memory into two separate pieces: a part that
does memory through a pre-defined “ _memory scaffold_ ”, and a part that does
association through a “ _heteroassociative_ ” step. Inspired by the
Entorhinal-Hippocampal memory system in mammalian brains, MESH contains a
bipartite attractor network that stabilizes a large dictionary of well-
separated and pre-defined fixed points that serve as the memory scaffold.
Arbitrary dense patterns are then stored by heteroassociatively linking them
to the pre-defined scaffold states. This novel combination results in a CAM
continuum (CAMC) that approaches the theoretical upper-bound on information
storage in neural networks (Abu-Mostafa, 1989; Gardner, 1988) as shown
schematically in Fig. 1g. In this network, storage of information-dense
patterns up to a critical capacity results in complete recovery of all
patterns and storage of a larger number of patterns results in partial
reconstruction of the corresponding stored pattern. Partial reconstruction
continues up to an exponentially large number of patterns as a function of
total number of neurons in the network, ending in correct recognition of
exponentially many stored patterns. To our knowledge, this is the first model
of a CAM that automatically trades off pattern number and pattern richness. It
predicts that biological memory systems may exploit pre-existing scaffolds to
acquire new memories, potentially consistent with the preplay of hippocampal
sequences before they are used for representing new environments (Dragoi &
Tonegawa, 2011).

In the next section, we discuss existing CAM models and their dynamics. In
Section 3 we provide our central results on the memory continuum exhibited by
MESH. In Sections 4 and 5, we analyze how MESH works. In section 6 we extend
MESH to the case of continuous neural activations, apply it to a realistic
dataset, and show that it continues to exhibit the memory continuum even when
storing continuous patterns.

##  2 Existing CAM models lack a memory continuum

Here we review existing CAM architectures. Unless otherwise specified, we
consider networks with $N$ neurons and dense binary activations (i.e.,
$N$-dimensional vectors with activations of 1 or -1 in each entry).

Hopfield networks (Hopfield, 1982) (Fig. 1a) can store up to $\approx 0.14N$
random binary patterns. Beyond this capacity, the network demonstrates a
memory cliff (Nadal et al., 1986; Crisanti et al., 1986; Dominguez et al.,
2007) (Fig. A.1a). The recurrent weights in the Hopfield network may be set by
a pseudoinverse learning rule (Personnaz et al., 1985), where the network is
guaranteed to store up to $N$ linearly independent patterns. However, storing
more than $N/2$ patterns results in vanishing basins of attraction around each
fixed point (Personnaz et al., 1986; Kanter & Sompolinsky, 1987) (Fig. A.1b).
Bounded synapse models (Parisi, 1986; Fusi & Abbott, 2007; Van Rossum et al.,
2012) on the other hand, do not exhibit a memory cliff in the same sense as
the classic Hopfield network, however, attempted storage of a large number of
patterns results in complete loss of a large fraction of the stored patterns
with only $\approx 0.04N$ patterns correctly recalled (Fig. A.1c).

Hopfield networks with sparse inputs store sparse $\\{0,1\\}$ binary patterns
with a fraction $p$ of non-zero entries, instead of the usual dense
$\\{-1,1\\}$ patterns (Tsodyks & Feigel’man, 1988). They can store a larger
number of sparse patterns, given by $(p|\ln(p)|)^{-1}N$, such that the product
of number of patterns times information per pattern is constant. However, the
tradeoff between pattern number and pattern information here is due to the
input patterns rather than the network – each pattern is still fully recalled,
with a memory cliff at the pattern capacity (Fig. A.1d). The same network
operating on the same dataset does not exhibit a tradeoff between pattern
number and pattern information. Sparse Hopfield networks on the other hand,
have sparse connectivity (Dominguez et al., 2007), but store dense
$\\{-1,1\\}$ patterns. These networks present a narrow memory continuum (Fig.
A.1e), however they have a very low capacity.

The bipartite expander Hopfield network (Chaudhuri & Fiete, 2019) can be used
to perform robust label retrieval from noisy or partial pattern cues, for an
exponentially large number of arbitrary patterns (Fig. A.1b). However, the
nature of memory in this network is familiarity or labeling, not
reconstruction. Thus the information per pattern is very small, regardless of
the number of stored patterns.

Dense (‘Modern’) Hopfield networks are recently proposed variants of the
Hopfield model that involve higher-order interactions in place of the
conventional pairwise interactions. These present a memory capacity that grows
as $N^{K-1}$ or $\exp(N)$ dependent on the order of the interactions (Krotov &
Hopfield, 2016; Demircigil et al., 2017; Ramsauer et al., 2020). Though a
bipartite structure (Fig. 1b) with pairwise interactions can approximate
higher-order interactions (Krotov & Hopfield, 2020; Chaudhuri & Fiete, 2019),
the capacity of a CAM with this structure remains merely linear, rather than
exponential, in the number of hidden nodes (Krotov & Hopfield, 2020). In fact,
the number of hidden units must exactly equal the number of memories, thus
storage of a variable number of patterns requires a change of network
architecture, rendering the network inflexible and hence unable to exhibit a
memory continuum.

Overparameterized autoencoders can also act as a CAM, with patterns stored as
the fixed points of iterations of the learned map of the autoencoder
(Radhakrishnan et al., 2020) (Fig. 1c). A drawback of these CAMs is that
autoencoders require extensive training through backpropagation, in contrast
to the one-shot learning in associative memory models, including all CAM
models described above and MESH. Moreover, similar to other CAM models,
overparametrized autoencoders also exhibit a memory cliff (Fig. A.1f).

##  3 MESH exhibits near-optimal CAM continuum

Figure 2: (a) Mutual information per input bit between the stored and
recovered patterns in MESH, as a function of the number of patterns stored in
the network. Here $N_{L}=32$, $k=3$, $N_{H}=200$, $N_{F}=4960$. (b) Mutual
information (per input bit) in existing networks relative to MESH (see Fig.
A.2b for mutual information as a function of total information stored per
synapse). (c) Comparison of information per synapse across different networks
relative to MESH. In (b) and (c) all networks are chosen to have $\approx
5\times 10^{5}$ synapses, with MESH layer sizes: $N_{L}=18$, $N_{H}=300$,
$N_{F}=816$, and $k=3$ active bits in the label layer.

We present MESH, a memory architecture in which single networks, _without
reparametrization or restructring_ , can store few patterns with rich detail
and increasingly more patterns with continuously decreasing detail, and thus
inhabit the whole extent of the memory envelope, Fig. 1g. MESH consists of two
components, Fig. 1f: 1) A predefined “memory scaffold” that generates a set of
fixed points with large basins. The memory scaffold is a bipartite attractor
network with an $N_{L}$-dimensional label layer and an $N_{H}$-dimensional
hidden layer; and 2) a “heteroassociative” layer – an $N_{F}$-dimensional
input/readout layer whose arbitrarily specified patterns are hooked onto the
memory scaffold via hetroassociative learning. The network construction is
described in more detail in the following two sections. We first demonstrate
the capabilities of MESH.

To probe memory recovery in MESH, the feature layer is cued with a corrupted
version of a stored pattern. The retrieval dynamics (Fig. 1f) of the network
returns a cleaned up version of the cued pattern to the feature layer. MESH
perfectly reconstructs upto $N_{H}$ arbitrary stored patterns $N_{patts}$ of
size $N_{F}$ bits each. When $N_{patts}$ is increased beyond this number, the
network performs partial reconstruction of the stored patterns, with a smooth
decay in the quality of reconstructed patterns, Fig. 2a.

We next quantify the information stored in MESH against theoretical bounds
(Gardner, 1988; Abu-Mostafa, 1989). The theoretical bound for CAMs is given by
the total number of learnable synapses. For the layer sizes in MESH, this
bound is $MI_{total}^{*}={N_{H}(2N_{F}+N_{L})}$. In practice $N_{L}\ll N_{F}$,
so this bound can be approximated as $2N_{H}N_{F}$. For patterns of length
$N_{F}$, the CAM networks (Fig. A.1) with a matched number of synapses may at
best fully recall up to $2N_{H}$ patterns, but beyond exhibit a memory cliff.
However, if a CAM network were to exhibit an optimal memory continuum, it
should saturate the total information bound regardless of the number of stored
patterns, with information per pattern per bit theoretically bounded by:

$\displaystyle MI_{perinbit}^{*}$ $\displaystyle=$
$\displaystyle\frac{MI_{total}^{*}}{N_{patts}\cdot\text{\\# bits per
pattern}}$ (1) $\displaystyle=$
$\displaystyle\frac{N_{H}(2N_{F}+N_{L})}{N_{patts}N_{F}}\approx\frac{2N_{H}}{N_{patts}}.$
(2)

Experimentally, we find that MESH nearly saturates this theoretical bound
across a wide range in the number of stored patterns, Fig. 2a (bound in dashed
gray), without any architectural or hyperparameter changes. The per-input-bit
mutual information matches the best-performing CAM models when the number of
stored patterns is smaller than the traditional CAM capacity, and is
dramatically bigger when the number of stored patterns is larger, Fig. 2b
(also see Fig. A.2b,c). The number of stored and partially retrievable
patterns exceeds the traditional CAM pattern number capacity by orders of
magnitude. Consistent with this result, the information per synapse at large
pattern numbers in MESH is significantly larger than in existing CAM models,
Fig. 2c.

Asymptotically with an increasing number of stored patterns, the total
information per synapse in MESH approaches a constant (Fig. 2c) –
demonstrating that the total information that can be successfully recovered by
MESH in a network of fixed size is invariant to the number of stored patterns.
This invariance dictates the smooth trade-off between MI per pattern (pattern
richness) and number of patterns.

In sum, MESH stores a constant amount of total information that is invariant
to the number of stored patterns; this total information content is
proportional to the theoretical synaptic upper bound of total information
storage in CAMs and is distributed across patterns so that the information per
pattern degrades gracefully with no memory cliff as a function of the number
of stored patterns (see Fig. A.2a for the feature recovery error
distribution). Next, to understand the underlying mechanisms that permit this
flexible memory performance, we will examine the functional properties of the
two components of MESH: the memory scaffold in Section 4 and the
heteroassociative learning in Section 5.

##  4 Exponential memory scaffold

Figure 3: (a) Memory scaffold in our model — label-hidden state attractor
network. (b) Capacity of the memory scaffold ( with 20% input noise injected
in the hidden layer, and allowing up to a 3% recovery error measured via the
Hamming distance between the stored and recovered patterns). Different curves
show the capacity corresponding to different sizes of the label layer for
labels with a constant number of active bits ($k=3$). (c) Exponential capacity
of the memory scaffold, assuming a constant density ($k/N_{L}$) of stored
labels.

The memory scaffold is a network that recurrently stabilizes a large number of
prestructured states with large basins of attraction, and performs denoising
or clean-up of corrupted versions of these states. Specifically, we choose the
predefined label layer states to be the set of $k$-hot patterns (each label
state $l^{\mu}$ is a vector with exactly $k$ bits set to “1” and all other
bits set to “0”, where $\mu$ is the pattern index). These label states are
defined on a small $N_{L}$-dimensional label (L) layer that projects with
fixed dense random weights $W_{HL}$ to a much larger $N_{H}$-dimensional
hidden (H) layer, Fig. 3a. These weights are drawn independently from a normal
distribution with zero mean and unit variance.

${W_{HL}}_{ij}\sim\mathcal{N}(0,1).$ (3)

Return projections from the hidden (H) to the label (L) layer are learned
through pairwise Hebbian learning between the set of predetermined label layer
states, and the resulting hidden-layer activations
$h^{\mu}=\operatorname*{sgn}(W_{HL}l^{\mu})$ as given by Eq. 4, where $C$ is a
normalization term given by the number of predefined patterns,
$\binom{N_{L}}{k}$. We assume that the label layer implements attractor
dynamics through $k$-winners-take-all dynamics imposed by local recurrent
inhibition (Rutishauser et al., 2011; Wang & Slotine, 2003; Yang & Chen,
1997), enforcing through its dynamics that states remain $k$-hot at all times
through a “Top-k” nonlinearity (this Top-k nonlinearity can be replaced with a
fixed threshold across all patterns; however the threshold would then have to
be varied with $N_{H}$, Fig. A.3).

$W_{LH}=\frac{1}{C}\sum_{\mu=1}^{C}l^{\mu}(h^{\mu})^{T}=\frac{1}{C}\sum_{\mu=1}^{C}l^{\mu}\operatorname*{sgn}(W_{HL}l^{\mu})^{T}.$
(4)

Given a state $h(t)$, the memory scaffold states update as:

$\displaystyle l(t)$ $\displaystyle=\operatorname*{topk}[W_{LH}h(t)],$ (5)
$\displaystyle h(t+1)$ $\displaystyle=\operatorname*{sgn}[W_{HL}l(t)].$ (6)

The essential features thar we desire for a memory scaffold are: first, the
scaffold should have a large number of fixed points as compared with the size
of the network; and second, the basins of attraction for each of these fixed
points must be sufficiently large to accommodate any perturbations induced
while accessing the memory scaffold through the feature layer — as we show,
each of the $\binom{N_{L}}{k}$ predefined states will form robust fixed points
of the network with maximally large basins of attraction.

######  Theorem 4.1.

For $N_{H}$ larger than a critical number $N_{H}^{crit}$, all
$\binom{N_{L}}{k}$ predefined $k$-hot label states are fixed points of the
recurrent dynamics Eqs. (5,6).

While we do not provide a rigorous proof of this theorem, we provide a
heuristic justifying this result in Appendix A.5. Empirically,
$N_{H}^{crit}\ll\binom{N_{L}}{k}$ is independent of $N_{L}$ and grows linearly
with $k$ (Fig. A.4c). We obtain directly as a corollary (see Appendix A.6 for
the proof)

######  Corollary 4.2.

For $N_{H}>N_{H}^{crit}$, any vector $h(0)$ maps to a predefined scaffold
state $h^{\mu}$ for some $\mu$ within a single iteration.

As described in Sec. 3, the hidden layer $H$ serves as an access point onto
which the arbitrary patterns in the feature layer are hooked. Thus, we will
primarily be interested in the robustness of these fixed points to
perturbations to the hidden layer states $h^{\mu}$.

######  Theorem 4.3.

For $N_{H}>N_{H}^{crit}$, all fixed points are stable, with equal-volume
basins of attraction that are maximally large, i.e., the basin size is of the
order of the size of the Voronoi cell of each pattern,
$\text{Vol}[\\{-1,1\\}^{N_{H}}]/C$, where $C=\binom{N_{L}}{k}$ is the number
of predefined scaffold states.

While we prove this result in Appendix A.7, the presence of large volume
basins of attraction does not in itself imply robustness to perturbations.
However, we additionally show that these basins are convex in Appendix A.8,
which then guarantees strong robustness to noise. We also note that the
$k$-winners-take-all attractor dynamics of the label layer can recurrently
maintain the stability at the retrieved state with an additional update
equation of $l(t+\tau)=\operatorname*{topk}[l(t)]=l(t)$ for $\tau\geq 1$. In
this sense, the network is able to hold a retrieved state as a short-term
memory, as in Hopfield networks.

Corresponding to Theorem 4.1, we experimentally observe that this bipartite
memory scaffold can denoise states with high accuracy once the number of
hidden neurons exceeds a critical value $N_{H}^{crit}$. For a fixed value of
$k$, this critical number appears to be approximately independent of the
number of label neurons $N_{L}$ (Fig. 3b), and thus does not depend on the
number of stored patterns $C=\binom{N_{L}}{k}$. For constant $k$, one can
therefore increase $N_{L}$ (while $N_{L}<N_{H}$) to obtain a capacity that at
fixed $N_{H}$ grows rapidly with $N_{L}$ and $k$ as
$\binom{N_{L}}{k}\sim(N_{L})^{k}$. An even faster growth of large-basin
scaffold states can be obtained by increasing the size of the label layer
while holding the activity density ($d=k/N_{L}$) fixed (Fig. 3c). This results
in a capacity that grows exponentially as $\binom{N_{L}}{k}\sim\exp(dN_{L})$.
Attaining this exponential growth in capacity requires an increase in $k$,
which subsequently requires a corresponding linear increase in $N_{H}^{crit}$
(Fig. A.4c).

The number of large-basin stable states in this memory scaffold is far greater
than the number of nodes and the number of synapses in this bipartite network,
growing exponentially with the number of nodes. This does not violate CAM
synaptic information bounds (since the stable states are predetermined rather
than being arbitrary, and thus cannot transmit any information beyond the
pattern index). We next demonstrate that the hidden layer can be used as an
access point between arbitrary patterns and the memory scaffold, to hook
external patterns onto the scaffold states.

##  5 Heteroassociation of arbitrary patterns onto scaffold

Figure 4: (a) Detailed architecture of our proposed model MESH, with numbers
in red indicating the time step of information flow through the model. (b)
Number of label, hidden and feature layer vectors that are perfectly recovered
on cuing the MESH network with zero input noise (left) and 5% input noise
(right) in the Feature states, and allowing zero recovery error. MESH
constructed with $N_{L}=18$, $k=3$ and $N_{F}=\binom{N_{L}}{k}$. (c) Left:
Overlap between the stored and the recovered patterns. Right: Information per
synapse in MESH (number of stored patterns increases along the x-axis). (d)
Blue and red curves: Mutual information (per input bit). Gray curve: Mutual
information when $W_{HF}$ and $W_{FH}$ are trained using Hebbian learning. (e)
Left: Voronoi diagram showing basins of attraction (Voronoi cells) for the
stored patterns. Right: Even during partial reconstruction, the recovered
pattern continues to lie in the correct Voronoi cell.

The second component of MESH is bi-directional heteroassociative learning
between the memory scaffold and inputs in the feature layer. The feature layer
is the input and output of MESH: patterns to be stored are presented as random
dense patterns which are then “hooked” onto one of the large-basin fixed
points of the memory scaffold, Fig. 4a. The heteroassociative weights are set
by presenting an arbitrary input vector $f^{\mu}$111In analytical derivations,
we consider $f^{\mu}$ to be dense random binary $\\{-1,1\\}$ patterns,
although in practice this is not necessary (Sec. 6 shows examples of storage
of continuous valued features). while activating one of the predefined
scaffold states to generate a hidden layer state $h^{\mu}$. Weights are then
set by the pseudoinverse learning rule (Personnaz et al., 1985),

$\displaystyle W_{HF}$
$\displaystyle=HF^{+}\;\;\;\text{and}\;\;\;W_{FH}=FH^{+},$ (7)

where the columns of $H$ and $F$ are the the predefined hidden layer states
$h^{\mu}$ and input patterns $f^{\mu}$, respectively. Pseudoinverse learning
can also be approximated through a (biologically plausible) online incremental
learning mechanism (Tapson & van Schaik, 2013), allowing weights to be learned
as patterns are presented in an online or streaming setting. Note that the
essential component of MESH is heteroassociative learning, not specifically
the pseudoinverse rule. Heteroassociation through Hebbian learning, such that
$W_{HF}=HF^{T}$ and $W_{FH}=FH^{T}$ also produces a CAM continuum in MESH,
though as as seen in conventional Hopfield networks, pseudoinverse learning
results in higher total stored information (Kanter & Sompolinsky, 1987;
Refregier & Vignolle, 1989; Storkey, 1997), (Fig. 4d, gray curve).
Furthermore, given a memory scaffold that perfectly recovers all hidden
states, a single heteroassociatve step through Hebbian learning is also
sufficient for a continuum (see Appendix A.3 for details).

Presented with a noisy feature state $f(t)$ at time $t$, MESH dynamics are
summarized as follows:

$\displaystyle h(t)$ $\displaystyle=\operatorname*{sgn}[W_{HF}f(t)],$ (8)
$\displaystyle l(t)$ $\displaystyle=\operatorname*{topk}[W_{LH}h(t)],$ (9)
$\displaystyle h(t+1)$ $\displaystyle=\operatorname*{sgn}[W_{HL}l(t)],$ (10)
$\displaystyle f(t+1)$ $\displaystyle=\operatorname*{sgn}[W_{FH}h(t+1)].$ (11)

Heteroassociative weights project noisy input patterns onto the hidden layer
in the memory scaffold. The memory scaffold cleans up the received input by
flowing to the nearest fixed point. This fixed point is decoded by the return
projection to the feature layer, generating a non-noisy reconstruction of the
input. To see why the heteroassociation with the memory scaffold allows for
successful pattern storage and recovery, we examine the mapping from the
feature layer to the memory scaffold, and then the recovery of the feature
state from the scaffold. For the purpose of our arguments, we assume that the
patterns being stored in the feature layer are random binary $\\{-1,1\\}$
patterns, and hence the matrix $F$ will be full rank. This allows the
following results.

######  Theorem 5.1.

If the $N_{F}\times N_{patts}$ dimensional matrix $F$ is full rank, an input
of clean feature vectors perfectly reconstructs the hidden layer states
through heteroassociative pseudoinverse learning from the feature layer to the
hidden layer, provided $N_{patts}\leq N_{F}$

Theorem 5.1, which we prove in Appendix A.9, implies that cuing the network
with unperturbed features stored in the memory results in perfect
reconstruction of the predefined hidden layer states. Following the results in
Sec. 4, if $N_{H}>N_{H}^{crit}$, reconstruction of the correct hidden states
ensures that the correct predefined label states are also recovered as shown
in Fig. 4b, left. Note that the number of successfully recovered features is
equal to the number of hidden neurons $N_{H}$, consistent with our description
in Sec. 3, a result that we now formalize.

######  Theorem 5.2.

Assuming correctly reconstructed predefined hidden layer states,
heteroassociative pseudoinverse learning results in perfect reconstruction of
up to $N_{H}$ patterns in the feature layer.

This theorem (proof in Appendix A.10) also demonstrates the importance of the
expansion of the label layer to a hidden layer of size $N_{H}$ — setting up
the predefined fixed points of the memory scaffold in a space that is higher
dimensional than the label layer allows for perfect reconstruction of patterns
up to the hidden layer dimensionality. This allows for the ‘knee’ of the CAMC
to be tuned as required by choosing an appropriate value of $N_{H}$ (Fig.
A.5a).

We now show that a CAM continuum exists for $N_{patts}>N_{H}$. We first show a
result on the overlap between stored and recovered patterns before proving our
main result on the mutual information of recovery of the CAM continuum.

######  Theorem 5.3.

Assume that the memory scaffold has correctly reconstructed the predefined
hidden layer states. Heteroassociative pseudoinverse learning from the hidden
layer to the feature layer for $N_{patts}>N_{H}$ results in an partial
reconstruction of stored patterns such that the dot product between the stored
patterns and the reconstruction of the stored patterns without the sign
nonlinearity is $N_{H}/N_{patts}$ when averaged across all patterns.

Theorem 5.3 (proof in Appendix A.11) along with Theorem 5.2 demonstrate the
existence of the memory continuum — for $N_{patts}\leq N_{H}$ the stored
patterns are recovered perfectly, and for $N_{patts}>N_{H}$ the recovered
patterns vary from the originally stored patterns in a smoothly varying
fashion. However, Theorem 5.3 only accounts for the overlap before the
application of the sign nonlinearity; the sign nonlinearity in the feature
layer only serves to additionally error correct the reconstructed patterns.
This can be seen in Fig. 4c, left, where the gray curve presents the overlap
before the application of the sign nonlinearity and is in close agreement to
the theoretically expected result (dashed black curve). After this additional
error correction, the mutual information recovered is then observed to
asymptotically approach a $1/N_{patts}$ scaling as well, as seen in Fig. 2a.
This can alternately be viewed as the mutual information per synapse
approaching a constant as larger amounts of information are stored, Fig. 4c,
right. Following Theorem 5.3, we note that the overlap between the true
features and the recovered features is only a function of $N_{H}$ and
$N_{patts}$. Thus, varying $N_{L}$ does not affect the magnitude of mutual
information recovered and the corresponding curves for varying $N_{L}$ overlap
with each other, Fig. 4c,d.

Since a CAM continuum exists in MESH, storing larger than $N_{H}$ patterns
results in a slow drift of the recovered patterns from the true state. This is
shown schematically in Fig. 4e where the Voronoi cells around each stored
pattern are marked (i.e., the region closer to the stored pattern as compared
to any other pattern): when the number of stored patterns is less than $N_{H}$
(left) the recovered pattern corresponds exactly to the stored clean pattern;
storage of additional patterns up to the maximal $\binom{N_{L}}{k}$ results in
the recovered patterns drifting away from the clean pattern but remaining
within the same Voronoi cell as the correct Voronoi cell (right). In this
sense, the continuum in recovered mutual information implies that all
recovered features remain within the correct Voronoi cell corresponding to the
originally stored pattern, which we verify numerically as the black curve in
Fig. 4b, left.

Until now, our theoretical results have only considered presentation of
unperturbed versions of the stored patterns to the network. For up to $N_{H}$
patterns, presentation of corrupted versions of the stored features results in
an approximate reconstruction of the hidden layer states, which through the
memory scaffold dynamics then flows to the corresponding clean hidden and
label state, Fig. 4b, right. This is then mapped back to the perfectly
recovered stored pattern following Theorem 5.2. For more than $N_{H}$
corrupted patterns, a similar process results in perfect recovery of the
hidden layer and label layer states for a large number of patterns, although
the capacity remains slightly smaller than the maximal number of patterns,
$\binom{N_{L}}{k}$.

##  6 Continuous Patterns

Figure 5: (a) Top: Overlap (top) and Mutual information (bottom) when MESH is
trained on random continuous patterns. (b) Overlap when MESH (and the
overparameterized autoencoder) is trained on the Fashion MNIST dataset. (c)
Left: original images from the Fashion MNIST dataset. Right: images directly
decoded by the decoder from the compressed feature representations. (d) Images
decoded from the recovered feature representations stored in MESH trained on
300, 550, and 800 images respectively (left to right). MESH layer sizes:
$N_{L}=18$, $k=3$, $N_{H}=300$, $N_{F}=500$. (e) Images decoded from the
recovered feature representations stored in the overparameterized autoencoder
(shown in Fig. 1c) trained on 15, 300, and 550 images respectively (left to
right). Layer sizes: 500, 300, 18, 300 and 500.

Next, we show that MESH exhibits a CAMC even when trained on continuous valued
input patterns. To store such continous-valued patterns, the only change
necessary to the architecture is removal of the sign nonlinearity in Eq. (11)
Additionally, to compare the stored and recovered patterns, we normalize them
to unit $L_{2}$ norm before calculation of pattern overlap and recovered
mutual information.

Random Continuous Patterns: In this case we consider patterns $f^{\mu}$ such
that for each $\mu$ and $i$, $f^{\mu}_{i}$ is an independently sampled number
from a normal distribution with zero mean and unit variance. Since Lemma 5.3
did not rely on any assumptions of pattern discreteness, the result extends to
the case of continuous patterns. However, since we are normalizing the
patterns before calculating the overlap, Eq. 50 dictates the scaling of the
overlap as $\sqrt{N_{H}/N_{patts}}$, consistent with the numerical results in
Fig. 5a, top. Since the stored patterns were drawn from a normal distribution,
and assuming the recovered patterns are also distributed normally, the mutual
information can be computed from the overlap ($m$) using Eq. 12 (details in
Appendix A.2.3), which is again in close agreement with the numerical results
shown in Fig. 5a (bottom), demonstrating the CAMC. Note that perfect
reconstruction of continuous valued patterns (as in the case of $N_{patts}\leq
N_{H}$) results in an infinite mutual information.

$MI=-\log\left(1-m^{2}\right)/2=-\log\left(1-N_{H}/N_{patts}\right)/2$ (12)

Fashion MNIST dataset: To evaluate the performance of MESH on realistic
images, we considered the toy problem of image storage from the Fashion MNIST
dataset (Xiao et al., 2017). As the primary comparative model in this setting,
we will consider an equivalent overparameterized autoencoder (Fig. 1c) with
the same number of nodes and synapses in each layer. Since the images
themselves have large pattern-pattern correlations, we found it beneficial for
both MESH and the autoencoder to compress the dataset to extract lower-
dimensional feature representations of the images through a separate large
autoencoder (details in Sec. A.12). This large autoencoder was trained on all
classes in the dataset except the “shirts” class. The encoder was then used to
extract features of the “shirts” class which were used as the set of patterns
to be stored in the MESH network and the overparameterized autoencoder. Fig.
5b shows the mean-subtracted overlap between recovered and stored patterns —
MESH continues to show a continuum, whereas the overparameterized autoencoder
has a memory cliff at a very small number of patterns.

To visualize the memory storage, we pass the recovered patterns through the
larger trained decoder to reconstruct the stored images of the shirts (Fig.
5c-e). Fig. 5c shows a few samples of original images as well as images
reconstructed directly from the extracted feature representations using the
larger trained decoder. Fig. 5d shows the images reconstructed through the
decoder by using the feature representations recovered from MESH for varying
numbers of stored patterns. When trained on $N_{patts}=N_{H}=300$ feature
patterns, the image is reconstructed perfectly up to the quality of the larger
decoder. As the number of stored feature patterns is increased
($N_{patts}>N_{H}$), the quality of image reconstruction gradually degrades.
While the overparametrized autoencoder, Fig. 5e, also recovered the stored
images with high accuracy when training on only 15 patterns, training on a
larger number of patterns results in the retrieved images becoming rapidly
unrecognizable (corresponding to the memory cliff of Fig. 5b)

##  7 Discussion

In this work, we have proposed a CAM network, MESH, that exhibits a memory
continuum, and can be used as a high capacity pattern labeller for
recognition/familiarity detection, and locality sensitive hashing. While the
convergence time of the Hopfield network scales as
$\mathcal{O}(N_{F}^{\gamma});\gamma\ll 1$ (Kohring, 1990; Frolov & Húsek,
2000), MESH converges in a single step through a $\operatorname*{topk}$
nonlinearity, or within $\mathcal{O}(\log N_{L})$ time when a $k$-winners-
take-all attractor is used. Several neural networks use a key-value mechanism
to store and read memories (Graves et al., 2014, 2016; Sukhbaatar et al.,
2015; Vaswani et al., 2017; Le et al., 2019; Banino et al., 2020). MESH
provides a neurally plausible architecture for implementing them through a
factorized key-value structure provided by the Label and Feature layers.

MESH also maps naturally onto the entorhinal-hippocampal system in the brain
that factorizes sensory and spatial representations in lateral (LEC) and
medial (MEC) entorhinal cortices respectively (Manns & Eichenbaum, 2006;
Eichenbaum & Cohen, 2014; Mulders et al., 2021), with the feature, label and
hidden layers corresponding to LEC, MEC, and the hippocampus respectively.

Adding a heteroassociatively trained recurrent connection to the hidden layer
in MESH can enable reconstruction of sequences, from any given starting state
in both forward and backward directions, potentially related to planning in
the hippocampus through preplay and replay of hippocampal sequences (Dragoi &
Tonegawa, 2011; Pfeiffer & Foster, 2013).

## References

  * Abu-Mostafa (1989) Abu-Mostafa, Y. S.  Information theory, complexity and neural networks.  _IEEE Communications Magazine_ , 27(11):25–28, 1989.
  * Banino et al. (2020) Banino, A., Badia, A. P., Köster, R., Chadwick, M. J., Zambaldi, V., Hassabis, D., Barry, C., Botvinick, M., Kumaran, D., and Blundell, C.  Memo: A deep network for flexible combination of episodic memories.  _arXiv preprint arXiv:2001.10913_ , 2020.
  * Bollé et al. (2000) Bollé, D., Dominguez, D., and Amari, S.-i.  Mutual information of sparsely coded associative memory with self-control and ternary neurons.  _Neural Networks_ , 13(4-5):455–462, 2000.
  * Chaudhuri & Fiete (2019) Chaudhuri, R. and Fiete, I.  Bipartite expander hopfield networks as self-decoding high-capacity error correcting codes.  _Advances in neural information processing systems_ , 32, 2019.
  * Crisanti et al. (1986) Crisanti, A., Amit, D. J., and Gutfreund, H.  Saturation level of the hopfield model for neural network.  _EPL (Europhysics Letters)_ , 2(4):337, 1986.
  * Demircigil et al. (2017) Demircigil, M., Heusel, J., Löwe, M., Upgang, S., and Vermet, F.  On a model of associative memory with huge storage capacity.  _Journal of Statistical Physics_ , 168(2):288–299, 2017.
  * Dominguez et al. (2007) Dominguez, D., Koroutchev, K., Serrano, E., and Rodríguez, F. B.  Information and topology in attractor neural networks.  _Neural computation_ , 19(4):956–973, 2007.
  * Dragoi & Tonegawa (2011) Dragoi, G. and Tonegawa, S.  Preplay of future place cell sequences by hippocampal cellular assemblies.  _Nature_ , 469(7330):397–401, 2011.
  * Eichenbaum & Cohen (2014) Eichenbaum, H. and Cohen, N. J.  Can we reconcile the declarative memory and spatial navigation views on hippocampal function?  _Neuron_ , 83(4):764–770, 2014.
  * Frolov & Húsek (2000) Frolov, A. A. and Húsek, D.  Convergence time in hopfield network.  In _Proceedings of the IEEE-INNS-ENNS International Joint Conference on Neural Networks. IJCNN 2000. Neural Computing: New Challenges and Perspectives for the New Millennium_ , volume 5, pp. 622–626. IEEE, 2000\.
  * Fusi & Abbott (2007) Fusi, S. and Abbott, L.  Limits on the memory storage capacity of bounded synapses.  _Nature neuroscience_ , 10(4):485–493, 2007.
  * Gardner (1988) Gardner, E.  The space of interactions in neural network models.  _Journal of physics A: Mathematical and general_ , 21(1):257, 1988.
  * Graves et al. (2014) Graves, A., Wayne, G., and Danihelka, I.  Neural turing machines.  _arXiv preprint arXiv:1410.5401_ , 2014.
  * Graves et al. (2016) Graves, A., Wayne, G., Reynolds, M., Harley, T., Danihelka, I., Grabska-Barwińska, A., Colmenarejo, S. G., Grefenstette, E., Ramalho, T., Agapiou, J., et al.  Hybrid computing using a neural network with dynamic external memory.  _Nature_ , 538(7626):471–476, 2016.
  * Hertz et al. (2018) Hertz, J., Krogh, A., and Palmer, R. G.  _Introduction to the theory of neural computation_.  CRC Press, 2018.
  * Hopfield (1982) Hopfield, J. J.  Neural networks and physical systems with emergent collective computational abilities.  _Proceedings of the national academy of sciences_ , 79(8):2554–2558, 1982.
  * Hopfield (1984) Hopfield, J. J.  Neurons with graded response have collective computational properties like those of two-state neurons.  _Proceedings of the national academy of sciences_ , 81(10):3088–3092, 1984.
  * Kanter & Sompolinsky (1987) Kanter, I. and Sompolinsky, H.  Associative recall of memory without errors.  _Physical Review A_ , 35(1):380, 1987.
  * Kohring (1990) Kohring, G.  Convergence time and finite size effects in neural networks.  _Journal of Physics A: Mathematical and General_ , 23(11):2237, 1990.
  * Krotov & Hopfield (2020) Krotov, D. and Hopfield, J.  Large associative memory problem in neurobiology and machine learning.  _arXiv preprint arXiv:2008.06996_ , 2020.
  * Krotov & Hopfield (2016) Krotov, D. and Hopfield, J. J.  Dense associative memory for pattern recognition.  _Advances in neural information processing systems_ , 29:1172–1180, 2016.
  * Le et al. (2019) Le, H., Tran, T., and Venkatesh, S.  Neural stored-program memory.  _arXiv preprint arXiv:1906.08862_ , 2019.
  * Manns & Eichenbaum (2006) Manns, J. R. and Eichenbaum, H.  Evolution of declarative memory.  _Hippocampus_ , 16(9):795–808, 2006.
  * Mulders et al. (2021) Mulders, D., Yim, M. Y., Lee, J. S., Lee, A. K., Taillefumier, T., and Fiete, I. R.  A structured scaffold underlies activity in the hippocampus.  _bioRxiv_ , 2021.
  * Nadal et al. (1986) Nadal, J., Toulouse, G., Changeux, J., and Dehaene, S.  Networks of formal neurons and memory palimpsests.  _EPL (Europhysics Letters)_ , 1(10):535, 1986\.
  * Parisi (1986) Parisi, G.  A memory which forgets.  _Journal of Physics A: Mathematical and General_ , 19(10):L617, 1986.
  * Personnaz et al. (1985) Personnaz, L., Guyon, I., and Dreyfus, G.  Information storage and retrieval in spin-glass like neural networks.  _Journal de Physique Lettres_ , 46(8):359–365, 1985.
  * Personnaz et al. (1986) Personnaz, L., Guyon, I., and Dreyfus, G.  Collective computational properties of neural networks: New learning mechanisms.  _Physical Review A_ , 34(5):4217, 1986.
  * Pfeiffer & Foster (2013) Pfeiffer, B. E. and Foster, D. J.  Hippocampal place-cell sequences depict future paths to remembered goals.  _Nature_ , 497(7447):74–79, 2013.
  * Radhakrishnan et al. (2020) Radhakrishnan, A., Belkin, M., and Uhler, C.  Overparameterized neural networks implement associative memory.  _Proceedings of the National Academy of Sciences_ , 117(44):27162–27170, 2020.
  * Ramsauer et al. (2020) Ramsauer, H., Schäfl, B., Lehner, J., Seidl, P., Widrich, M., Adler, T., Gruber, L., Holzleitner, M., Pavlović, M., Sandve, G. K., et al.  Hopfield networks is all you need.  _arXiv preprint arXiv:2008.02217_ , 2020.
  * Refregier & Vignolle (1989) Refregier, P. and Vignolle, J.-M.  An improved version of the pseudo-inverse solution for classification and neural networks.  _EPL (Europhysics Letters)_ , 10(4):387, 1989\.
  * Rutishauser et al. (2011) Rutishauser, U., Douglas, R. J., and Slotine, J.-J.  Collective stability of networks of winner-take-all circuits.  _Neural computation_ , 23(3):735–773, 2011.
  * Storkey (1997) Storkey, A.  Increasing the capacity of a hopfield network without sacrificing functionality.  In _International Conference on Artificial Neural Networks_ , pp. 451–456. Springer, 1997.
  * Sukhbaatar et al. (2015) Sukhbaatar, S., Szlam, A., Weston, J., and Fergus, R.  End-to-end memory networks.  _arXiv preprint arXiv:1503.08895_ , 2015.
  * Tapson & van Schaik (2013) Tapson, J. and van Schaik, A.  Learning the pseudoinverse solution to network weights.  _Neural Networks_ , 45:94–100, 2013.
  * Tsodyks & Feigel’man (1988) Tsodyks, M. V. and Feigel’man, M. V.  The enhanced storage capacity in neural networks with low activity level.  _EPL (Europhysics Letters)_ , 6(2):101, 1988.
  * Van Rossum et al. (2012) Van Rossum, M. C., Shippi, M., and Barrett, A. B.  Soft-bound synaptic plasticity increases storage capacity.  _PLoS computational biology_ , 8(12):e1002836, 2012.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I.  Attention is all you need.  In _Advances in neural information processing systems_ , pp. 5998–6008, 2017.
  * Wang & Slotine (2003) Wang, W. and Slotine, J.-J. E.  K-winners-take-all computation with neural oscillators.  _arXiv preprint q-bio/0401001_ , 2003.
  * Xiao et al. (2017) Xiao, H., Rasul, K., and Vollgraf, R.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  _arXiv preprint arXiv:1708.07747_ , 2017.
  * Yang & Chen (1997) Yang, J.-F. and Chen, C.-M.  A dynamic k-winners-take-all neural network.  _IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics)_ , 27(3):523–526, 1997.

##  Appendix A Appendix

### Software and Data

The source code for the models presented in this paper is made available at
the following GitHub repository:
https://anonymous.4open.science/r/MESH

###  A.1 Performance of existing CAM models

To quantify and compare performance across models, in Fig. A.1, we construct
networks with $\approx 5\times 10^{5}$ synapses, and measure the mean mutual
information (MI) per-input-bit between the stored and the recovered patterns
as a metric for the ability of the network to distinguish a memorized pattern
from the recovered state (see Sec. A.2 for details). Unless otherwise
specified, we average the MI across all patterns and normalize by the number
of patterns and the number of bits per pattern (e.g., for storage of dense
binary patterns, if all stored patterns are perfectly recovered, the MI will
be unity, irrespective of the length of the patterns).

Figure A.1:  Mutual information (per input bit) between the stored and the
recovered pattern as a function of number of patterns stored in the existing
networks. (a) Hopfield network of size $N=708$, synapses = $N^{2}$.(b)
Pseudoinverse Hopfield network, tested with zero and non-zero input noise.
Size of the network $N=708$, synapses = $N^{2}$. (c) Hopfield network with
bounded synapses trained with Hebbian learning on sequentially seen patterns.
Size of the network $N=708$, synapses = $N^{2}$. (d) Hopfield network with
sparse inputs. Size of the network $N=708$, synapses = $N^{2}$, sparsity =
$100(1-p)$. (e) Sparse Hopfield network. Size of the network $N$, synapse
dilution $\gamma$, synapses = $\gamma\times N^{2}=10^{5}$ held constant for
all curves. (f) Overparameterized Autoencoder (shown in Fig. 1c). Network
layer sizes $N_{F}=816$, $N_{H}=300$, $N_{B}=18$.  Figure A.2: (a) Feature
recovery error forms a unimodal distribution, implying that each recovered
pattern has a graceful degradation with increase in the number of stored
patterns (every pattern still lies in the correct Voronoi cell). Here
$N_{L}=18$, $k=3$, $N_{H}=300$, $N_{F}=816$. (b) Mutual information (per input
bit) in existing networks relative to MESH as a function of total information
stored per synapse. (c) Mutual information (per input bit) in a Pseudoinverse
Hopfield network ($N=708$). Gray dashed line shows the theoretical upperbound
and black dashed line is the asymptotically proportional bound achieved by the
network. Figure A.3: Histograms of Label states before applying the Topk
nonlinearity in the dynamics of the MESH network. Here $N_{L}=18$, $k=3$,
$N_{F}=816$. (a) For a fixed number of hidden neurons ($N_{H}=300$) there’s a
clear threshold separating the Topk states that can be implemented by a winner
take all network. (b) Left: The choice of threshold can vary as $N_{H}$
varies, but a valid threshold always exists for any given $N_{H}$. Right:
Threshold varies slowly with $N_{H}$ for large $N_{H}$; same threshold can be
used for different $N_{H}$ since the Topk states are increasingly distant and
separable from the rest of the distribution. Figure A.4: (a) Capacity of the
memory scaffold (computed with 20% input noise injected in the hidden layer,
and allowing up to a 3% recovery error measured via the Hamming distance
between the stored and recovered patterns). Different curves show the capacity
corresponding to different sizes of the label layer for labels with a constant
number of active bits ($k=2$). (b) Variation of the critical number of hidden
neurons with respect to the number of label neurons. (c) Variation of the
critical number of hidden neurons with respect to the number of active bits
($k$).  Figure A.5: (a) Effect of varying $N_{H}$ on Mutual Information (per
input bit) in the MESH network. Here $N_{L}=18$, $k=3$, $N_{F}=816$. (b)
Effect of varying $N_{F}$ on Mutual Information (per input bit) in the MESH
network. Here $N_{L}=18$, $k=3$, $N_{H}=300$. (c) Number of recovered feature
states in the correct Voronoi cell as a function of the number of feature
neurons ($N_{F}$). Here $N_{L}=18$, $k=3$, $N_{H}=300$, $N_{patts}=816$.

###  A.2 Mutual Information

Shanon entropy or information entropy is defined as:

$H(X)=-\sum_{i=1}^{n}p(x_{i})\;\log\>p(x_{i})\ $ (13)

Where $p(x_{i})$ is the probability that the system is in the ith state.

The joint entropy of the stored patterns $\xi$ and the recovered patterns
$\sigma$ is given by:

$H(\sigma;\xi)=-\sum_{\sigma}\sum_{\xi}p(\sigma,\xi)\;\log\>p(\sigma,\xi)\ $
(14)

Thus the marginal entropy of $\sigma$ is given by:

$H(\sigma)=-\sum_{\sigma}p(\sigma)\;\log\>p(\sigma)=-\sum_{\sigma}\sum_{\xi}p(\sigma,\xi)\;\log\>p(\sigma)$
(15)

And the conditional entropy of $\sigma$ is given by:

$\displaystyle H(\sigma|\xi)$
$\displaystyle=\langle\;H(\sigma|\xi)\;\rangle_{\xi}$ (16)
$\displaystyle=\sum_{\xi}p(\xi)H(\sigma|\xi)$
$\displaystyle=-\sum_{\xi}p(\xi)\sum_{\sigma}p(\sigma|\xi)\;\log\>p(\sigma|\xi)$
$\displaystyle=-\sum_{\xi}\sum_{\sigma}p(\sigma,\xi)\;\log\>p(\sigma|\xi)$

We want to know how much information we acquire about $\xi$ by observing
$\sigma$. This is quantified by the Mutual Information between $\xi$ and
$\sigma$, which is defined as the average reduction in the entropy of $\xi$ on
observing $\sigma$:

$\displaystyle MI\;(\sigma;\xi)$ $\displaystyle=H\;(\sigma)-H\;(\sigma|\xi)$
(17)
$\displaystyle=\sum_{\sigma,\xi}p(\sigma,\xi)\;\log\>\left(\frac{p(\sigma)}{p(\sigma|\xi)}\right)$
$\displaystyle=\sum_{\sigma,\xi}p(\sigma,\xi)\;\log\>\left(\frac{p(\sigma)\;p(\xi)}{p(\sigma,\xi)}\right)$

####  A.2.1 Dense binary patterns

For binary (-1/1) patterns, $H(\sigma|\xi)$ depends on $p(\sigma,\xi)$ which
factorizes as follows:

$p(\sigma,\xi)=p(\sigma|\xi)p(\xi)\;\;\;\;\;\texttt{(Bayes rule)}$ (18)

where $p(\sigma|\xi)=(1+m\sigma\xi)/2$ is the conditional probability and
$p(\xi)$ is the input probability (Dominguez et al., 2007; Bollé et al.,
2000). Here $m$ is the overlap between the neural states and the pattern
$m=\frac{1}{N}\sum_{i}\sigma_{i}\xi_{i}$

The states of binary random patterns can be 1 or -1 with equal probability,
hence

$\displaystyle H\;(\sigma)$
$\displaystyle=-\frac{1}{2}\;\log\left(\frac{1}{2}\right)-\frac{1}{2}\;\log\left(\frac{1}{2}\right)=1\;\;\;\;\;\texttt{(Using
Eq.\ref{Eqn:marginal_entropy})}$ (19) $\displaystyle H\;(\sigma|\xi)$
$\displaystyle=-\frac{1}{2}\left(\frac{1+m}{2}\log\frac{1+m}{2}+\frac{1-m}{2}\log\frac{1-m}{2}\right)-\frac{1}{2}\left(\frac{1-m}{2}\log\frac{1-m}{2}+\frac{1+m}{2}\log\frac{1+m}{2}\right)$
$\displaystyle=-\frac{1+m}{2}\log\left(\frac{1+m}{2}\right)-\frac{1-m}{2}\log\left(\frac{1-m}{2}\right)\;\;\;\;\;\texttt{(Using
Eq.\ref{Eqn:conditional_entropy})}$

Thus using Equation 17, mutual information is given by:

$MI\;(\sigma;\xi)=1+\frac{1+m}{2}\log\left(\frac{1+m}{2}\right)+\frac{1-m}{2}\log\left(\frac{1-m}{2}\right)$
(20)

####  A.2.2 Sparse binary patterns

For sparse binary (0/1) patterns, let $p$ be the average activity of the
stored pattern, the average activity of the recovered pattern can be expressed
as $q=|\sigma|/N$.

Let $P_{1e}$ be the probability of error in a bit of $\sigma$ if the
corresponding bit of $\xi$ is 1, and $P_{0e}$ be the error probability in a
bit of sigma if the corresponding bit of $\xi$ is 0.

$\displaystyle H\;(\sigma)$ $\displaystyle=-[q\;\log\>(q)+(1-q)\;\log\>(1-q)]$
(21) $\displaystyle H\;(\sigma|\xi)$
$\displaystyle=-p[P_{1e}\log(P_{1e})+1-P_{1e}\log(1-P_{1e})]-(1-p)[P_{0e}\log(P_{0e})+1-P_{0e}\log(1-P_{0e})]$

Here, $P_{1e}$ and $P_{0e}$ can be computed using the overlap $m$ and the
average activity of the recovered pattern $q$ as follows:

$\displaystyle m$ $\displaystyle=\langle\sigma.\xi\rangle=p(1-P_{1e})\implies
P_{1e}=1-m/p$ (22) $\displaystyle q$
$\displaystyle=\frac{|\sigma|}{N}=p(1-P_{1e})+(1-p)P_{0e}=m+(1-p)P_{0e}\implies
P_{0e}=\frac{q-m}{1-p}$

####  A.2.3 Continuous random normal patterns

In this case, the patterns are sampled from a Random Normal distribution with
zero mean and standard deviation equal to one, and probability density as
expressed below:

$\displaystyle\phi(x)$
$\displaystyle=\frac{1}{\sqrt{2\pi}}e^{-\frac{x^{2}}{2}}$ (23)

Differential entropy extends the ideas of Shannon entropy to continuous
probability distributions, and can be defined as follows for the above
distribution:

$\displaystyle H(X)$
$\displaystyle=-\int_{-\infty}^{\infty}\phi(x)\;\log\>\phi(x)\,dx$ (24)
$\displaystyle=\mathbb{E}\;[-\log\;\phi(x)]$
$\displaystyle=\frac{1}{2}\;\log\;2\pi e$

The conditional entropy and mutual information is then given by:

$\displaystyle Var(X|Y)$
$\displaystyle=Var(X)-\frac{Cov^{2}(X,Y)}{Var(Y)}=(1-r^{2})$ (25)
$\displaystyle H(X|Y)$ $\displaystyle=\frac{1}{2}\;\log\;(2\pi e(1-r^{2}))$
$\displaystyle MI(X;Y)$
$\displaystyle=H(X)-H(X|Y)=\log\sqrt{\frac{1}{1-r^{2}}}$

Where $r$ is the correlation coefficient between $X$ and $Y$.

Thus in the case of random normal patterns the mutual information between the
stored pattern $\xi$ and the recovered pattern $\sigma$ can be computed
directly through the correlation between them using Equation 25 above. Since
X, Y are two random variables with zero mean (sampled from a Random Normal
distribution), $Cov[X,Y]$ is the dot product of X and Y. The standard
deviations of $X$ and $Y$ are their respective norms. Thus, the correlation
given by Equation 26 is the cosine of the angle ($\theta$) between $X$ and $Y$
vectors. An acute angle implies a positive correlation, an obtuse angle
implies a negative correlation and orthogonal implies $X$ and $Y$ are
uncorrelated.

$\displaystyle r=Corr[XY]$
$\displaystyle=\frac{Cov[XY]}{\sigma[X]\sigma[Y]}=Cos(\theta)$ (26)

###  A.3 One-step heteroassociation leads to the continuum given a perfect
memory scaffold

Figure A.6: Mutual Information (per input bit). Red and Blue curves: MESH
memory continuum. Gray and Brown curves: weights $W_{FH}$ in MESH are trained
using the Hebbian learning rule assuming perfect recovery of hidden states.
Here gray curve corresponds to the case when hidden states are dense random
binary.

The memory continuum in MESH is a result of the one-step heteroassociation
from the hidden to the feature layer, given a memory scaffold that perfectly
recovers the hidden states. This holds irrespective of the nature of
heteroassociation (pseudoinverse learning or hebbian learning).

To illustrate this, we consider a simpler scenario where $W_{FH}$ is trained
through Hebbian learning and the hidden layer states are assumed to be
correctly reconstructed (corresponding to pseudoinverse learning from $F$ to
$H$, Theorem 5.1), making an additional approximation of the hidden layer
states being dense random binary $\\{-1,1\\}$ patterns, we obtain an analytic
expression for the mutual information per input bit as a function of the
number of patterns (see Section A.3.1 for detailed proof) as follows

$\displaystyle MI_{perinbit}$ $\displaystyle=1+p\log p+(1-p)\log(1-p)$ (27)

for

$\displaystyle
p=\frac{1}{2}\left[1-\operatorname{erf}\left(\sqrt{\frac{N_{H}}{2N_{patts}}}\right)\right],$
(28)

where $\operatorname{erf}(x)$ is the Gauss error function. This result is in
close agreement with numerical simulations (Fig. A.6, gray curve), and is
asymptotically proportional to the MESH continuum. Furthermore, when the
hidden states are random projections of label states (as in the original MESH
network), rather than random dense states, the network still exhibits a
continuum (Fig. A.6, brown curve). This shows that one step heteroassociation
with Hebbian learning is itself sufficient for a memory continuum, given a
perfect memory scaffold.

####  A.3.1 MI for Hebbian learning

Given random binary dense hidden and feature states, if the weights from the
hidden to the feature layer are trained using Hebbian learning, we get:

$\displaystyle f_{i}(t_{0}+\Delta t)$
$\displaystyle=\operatorname*{sgn}\left[\frac{1}{N_{H}}\sum_{j=1}^{N_{H}}\sum_{\mu=1}^{N_{patts}}f_{i}^{\mu}h_{j}^{\mu}h_{j}^{\nu}\right]$
(29)
$\displaystyle=\operatorname*{sgn}\left[f_{i}^{\nu}\left(\frac{1}{N_{H}}\sum_{j=1}^{N_{H}}h_{j}^{\nu}h_{j}^{\nu}\right)+\frac{1}{N_{H}}\sum_{\mu\neq\nu}\sum_{j}f_{i}^{\mu}h_{j}^{\mu}h_{j}^{\nu}\right]$

Here we have separated the pattern $\nu$ from all the other patterns. Next, we
multiply the second term on the right-hand side by a factor
$f_{i}^{\nu}f_{i}^{\nu}=1$, and pull $f_{i}^{\nu}$ out of the argument of the
sign-function since $f_{i}^{\nu}=\pm{1}$ :

$\displaystyle f_{i}(t_{0}+\Delta t)$
$\displaystyle=f_{i}^{\nu}\operatorname*{sgn}\left[1+\frac{1}{N_{H}}\sum_{\mu\neq\nu}\sum_{j}f_{i}^{\mu}f_{i}^{\nu}h_{j}^{\mu}h_{j}^{\nu}\right]=f_{i}^{\nu}\operatorname*{sgn}[1-a_{i\nu}]$
(30) $\displaystyle where\;\;a_{i\nu}$
$\displaystyle=-\frac{1}{N_{H}}\sum_{\mu\neq\nu}\sum_{j}f_{i}^{\mu}f_{i}^{\nu}h_{j}^{\mu}h_{j}^{\nu}$

If $a_{i\nu}$ is negative, the crosstalk term has the same sign as
$f_{i}^{\nu}$ and does no harm. However, if it’s positive and larger than 1 it
changes the sign of $f_{i}^{\nu}$ and makes the bit $i$ of pattern $\nu$
unstable. Thus, the probability of error in recovering the true pattern
$f_{i}^{\nu}$ is equal to the probability of finding a value $a_{i\nu}>1$ for
one of the neurons $i$.

Since both the hidden and feature state patterns are generated from
independant binary random numbers $h_{i}^{\mu}=\pm{1}$ and
$f_{i}^{\mu}=\pm{1}$ with zero mean, the product
$f_{i}^{\mu}f_{i}^{\nu}h_{j}^{\mu}h_{j}^{\nu}=\pm{1}$ is also a binary random
number with zero mean. The term $a_{i\nu}$ can be thought of as a random walk
of $N_{H}(N_{patts}-1)$ steps and step size $1/N_{H}$ (Hertz et al., 2018).
For a large number of steps, we can approximate the walking distance using a
Gaussian distribution with zero mean and standard deviation given by
$\sigma=\sqrt{(N_{patts}-1)/N_{H}}\approx\sqrt{N_{patts}/N_{H}}$ for
$N_{patts}\gg 1$. The probability of error in the activity state of neuron $i$
is therefore given by:

$\displaystyle P_{error}$
$\displaystyle=\frac{1}{\sqrt{2\pi}\sigma}\int_{1}^{\infty}e^{\frac{-x^{2}}{2\sigma^{2}}}dx\approx\frac{1}{2}\left[1-erf\left(\sqrt{\frac{N_{H}}{2N_{patts}}}\right)\right]$
(31) $\displaystyle erf(x)$
$\displaystyle=\frac{2}{\sqrt{\pi}}\int_{0}^{x}e^{-y^{2}}dy$

Thus the probability of error increases with the ratio $N_{patts}/N_{H}$.

The mutual information between the stored and recovered feature states is thus
given by:

$\displaystyle MI_{perinbit}$ $\displaystyle=1-\left(-[p\log
p+(1-p)\log(1-p)]\right),\;\;\;\texttt{(Using Eq.\ref{eqn:MI}})$ (32)
$\displaystyle=1+p\log p+(1-p)\log(1-p),$

where $p=P_{error}$.

###  A.4 Metrics

####  A.4.1 Recovery error metrics

Recovery error is the error between the stored and the recovered pattern in a
network. It quantifies how close the pattern recovered from the network is to
the pattern originally stored in the network.

The recovery error metric in Figure 3b,c is the hamming distance between the
recovered pattern and the true pattern, relative to the hamming distance
between the initial noisy pattern and the true pattern, formally given by:

$Recovery\;error=\frac{\sum_{i=1}^{N_{H}}\;|\>h_{i}^{\mu}(t+1)-h_{i}^{\mu}\>|}{\sum_{i=1}^{N_{H}}\;|\>h^{\mu}_{i}(t)-h_{i}^{\mu}\>|}$
(33)

The recovery error metrics used in Figure 4b are hamming distances normalized
to lie between zero and one, formally given by:

$Feature\;recovery\;error=\frac{\sum_{i=1}^{N_{F}}\;|\>f_{i}^{\mu}(t+1)-f_{i}^{\mu}\>|}{2\times
N_{F}}$ (34)

$Label\;recovery\;error=\frac{\sum_{i=1}^{N_{L}}\;|\>l_{i}^{\mu}(t+1)-l_{i}^{\mu}\>|}{2\times
k}$ (35)

$Hidden\;recovery\;error=\frac{\sum_{i=1}^{N_{H}}\;|\>h_{i}^{\mu}(t+1)-h_{i}^{\mu}\>|}{2\times
N_{H}}$ (36)

####  A.4.2 Capacity metrics

Given the above definitions for the recovery error, the capacity in Figures
3b,c and Figure 4b is computed by finding the maximum number of patterns for
which the average recovery error over all the stored patterns is below a given
threshold. This threshold specifies the acceptable recovery error.

###  A.5 Heuristic justification of Theorem 4.1

We first provide broad qualitative justification for why the memory scaffold
may be capable of storage of such a large number of fixed points, before
presenting a mathematical proof in a simplified setting.

Unlike associative memory in the usual context of random patterns, note that
the hidden layer states are determined by a random projection of the
predefined label states. As a result the hidden layer states inherit similar
pattern-pattern correlations as the predefined label layer states. This allows
for Hebbian learning to act more efficiently in learning pairwise correlation
resulting in a high capacity. Indeed, while in Hopfield networks any given
fixed point is destabilized due to interference from other fixed points, the
shared pattern-pattern correlations in the memory scaffold result in the
interference terms being positively correlated with each fixed point (as can
be seen in Fig. A.3).

To show this result more quantitatively, recall that

$l(t+1)=\operatorname*{topk}[W_{LH}h(t)].$

Since we are only interested in showing that the state $h^{\mu}$ is a fixed
point, we set $h(t)=h^{\mu}$, and aim to recover $l(t+1)=l^{\mu}$. For ease of
notation, we denote the prespecified random projection $W_{LH}$ as $W$. Now,
from the definition of $W_{LH}$ and $h^{\mu}$,

$\displaystyle l(t+1)$
$\displaystyle=\operatorname*{topk}[LH^{T}\operatorname*{sgn}(Wl^{\mu})],$
(37)
$\displaystyle=\operatorname*{topk}[L\operatorname*{sgn}(L^{T}W^{T})\operatorname*{sgn}(Wl^{\mu})]$
(38)

For analytic simplicity, we make the assumption that the sign nonlinearities
in the above equation can be ignored. While this is a gross simplification,
the obtained result is broadly consistent with the numerical observations in
Sec. 4. This approximates the above equation to

$l(t+1)=\operatorname*{topk}[LL^{T}W^{T}Wl^{\mu}]=\operatorname*{topk}[Al^{\mu}],$

where $A=(LL^{T})(W^{T}W)$. Since each element of the $N_{H}\times N_{L}$
matrix $W$ was drawn independently from a normal distribution with unit
variance, $W^{T}W$ and hence $A$ can be treated as a matrix random variable.
Further, as we show more precisely, the symmetry of the bit permutations
across all patterns entails that each diagonal element of $A$ with i.i.d. and
similarly each off-diagonal element of $A$ will be i.i.d. Let the i.i.d.
variables on the diagonal be denoted as $\mathcal{X}_{d}^{i}$ for
$i\in\\{1\ldots N_{L}\\}$, and the off-diagonal i.i.d. variables be denoted as
$\mathcal{X}_{f}^{ij}$ for $i,j\in\\{1\ldots N_{L}\\}$, $i\neq j$.

$A=\begin{pmatrix}\mathcal{X}_{d}^{1}&\mathcal{X}_{f}^{12}&\ldots\\\
\mathcal{X}_{f}^{21}&\mathcal{X}_{d}^{2}&\ldots\\\
\vdots&&\ddots\end{pmatrix}$

Without loss of generality, let $l^{\mu}_{i}=1$ for $i\in\\{1,\ldots,k\\}$ and
$l^{\mu}_{i}=0$ otherwise. It will thus suffice to require that the matrix $A$
acting on the vector $L^{\mu}$ results in a vector with the value at the first
$k$ indices to be larger than all other values. We first examine the
constraints of the distributions $\mathcal{X}_{d}$ and $\mathcal{X}_{f}$ that
allow for this to hold. Left multiplying the matrix $A$ with the vector
$l^{\mu}$, we obtain a vector whose $i^{\text{th}}$ component is given by

$\mathcal{X}_{d}^{i}+\sum_{1\leq j\leq k;j\neq i}\mathcal{X}_{f}^{ij},$ (39)

for $1\leq i\leq k$, and

$\sum_{1\leq j\leq k}\mathcal{X}_{f}^{ij},$ (40)

for $i>k$. Since we require that this vector has it’s first $k$ elements
larger than the remaining $N_{L}-k$ elements, we are interested in the
probability

$P(\text{Eq. (\ref{eq:apx_firstk}) - Eq. (\ref{eq:apx_afterk})}>0)$ (41)

Here we make an additional approximation for ease of analytic calculation: we
will assume that the random variables $\mathcal{X}_{d}$ and $\mathcal{X}_{f}$
are normal variables (This approximation will be valid in the large $N_{H}$
limit due to Central Limit Theorem). Let the mean and standard deviation of
these variables be $\mu_{d},\sigma_{d}$ and $\mu_{f},\sigma_{f}$ respectively.
In terms of these, the condition Eq. (41) can be rewritten as

$P(\mathcal{N}(\mu_{d}-\mu_{f},\sigma_{d}^{2}+(2k-1)\sigma_{f}^{2})>0),$ (42)

with $\mathcal{N}(\mu,\sigma^{2})$ representing a normal variable with mean
$\mu$ and variance $\sigma^{2}$. This probability can be calculated as

$\frac{1}{2}\left[1+\operatorname{erf}\left(\frac{\mu_{A}}{\sigma_{A}\sqrt{2}}\right)\right]$
(43)

with $\mu_{A}=\mu_{d}-\mu_{f}$ and
$\sigma_{A}^{2}=\sigma_{d}^{2}+(2k-1)\sigma_{f}^{2}$. We will demonstrate that
this probability tends to $1$ in the large $N_{H}$ approximation that we have
assumed.

We now quantify more precisely the matrix random variable $A$. From the
definition of the set of patterns $l^{\mu}$, $LL^{T}$ can be shown to be a
matrix with $\lambda_{d}=\binom{N_{L}-1}{k-1}$ on the diagonal, and
$\lambda_{f}=\binom{N_{L}-2}{k-2}$ in each off-diagonal entry.

Next, note that since each element of the $N_{H}\times N_{L}$ matrix $W$ was
drawn independently from a normal distribution with unit variance, and thus
$W^{T}W$ will have each diagonal element being distributed as the sum of the
squares of $N_{H}$ standard normal variables, and each off-diagonal element
will be distributed as the sum of the products of $N_{H}$ pairs of
uncorrelated standard normal variables. Thus

$W^{T}W\sim\begin{pmatrix}\chi^{2}(N_{H})&\mathcal{NP}(N_{H})&\ldots\\\
\mathcal{NP}(N_{H})&\chi^{2}(N_{H})&\ldots\\\ \vdots&&\ddots\end{pmatrix},$
(44)

where $\chi^{2}(N)$ is the sum of $N$ i.i.d. $\chi^{2}$ distributions, and
$\mathcal{NP}(N)$ is the sum of $N$ i.i.d. normal product distributions (i.e.,
the distribution of the product of two i.i.d. standard normal variables). Note
that we have suppressed the indices on each matrix element, however it should
be noted that each element is an independent sample from the distribution and
are identical in distribution but not in value. This can now be used to
compute the distribution of the elements of $A$, in terms of the matrix
elements of $LL^{T}$ and $W^{T}W$ to obtain

$\displaystyle\mathcal{X}_{d}$
$\displaystyle=\lambda_{d}\chi^{2}(N_{H})+\sum_{N_{L}-1\text{
terms}}\mathcal{NP}(N_{H})$ (45) $\displaystyle\mathcal{X}_{f}$
$\displaystyle=\lambda_{f}\chi^{2}(N_{H})+\lambda_{d}\mathcal{NP}(N_{H})+\sum_{N_{L}-2\text{
terms}}\mathcal{NP}(N_{H}),$ (46)

where we again suppress indices over individual random variables but note that
each random variable is i.i.d., including each summand term in the above
expressions. In the large $N_{H}$ limit, each element of $W^{T}W$ is the sum
of a large number of random variables and can hence be approximated as a
normal distribution due to central limit theorem. Thus,
$\chi^{2}\sim\mathcal{N}(N_{H},2N_{H})$, and
$\mathcal{NP}(N_{H})\sim\mathcal{N}(0,N_{H})$. This allows for
$\mu_{d},\sigma_{d},\mu_{f}$ and $\sigma_{f}$ to be computed. We use these to
compute $\mu_{A}$ and $\sigma_{A}$ using $\mu_{A}=\mu_{d}-\mu_{f}$ and
$\sigma_{A}^{2}=\sigma_{d}^{2}+(2k-1)\sigma_{f}^{2}$. This results in

$\frac{\mu_{A}^{2}}{\sigma_{A}^{2}}=\binom{N_{L}-2}{k-1}\frac{N_{L}-k}{N_{L}(2k^{2}+1)-3k},$
(47)

which can then be used to compute the probability Eq. (42) via Eq. (43).

While the obtained expressions are particularly unwieldy, they can be used to
numerically compute probabilities. It should be noted that since
$\mathcal{X}_{d}$ and $\mathcal{X}_{f}$ are given by the sum of $N_{H}$
independent random terms (see Eqs. (45,46)), all of
$\mu_{d},\sigma_{d},\mu_{f}$ and $\sigma_{f}$ are proportional to $N_{H}$, and
thus the $N_{H}$ dependence cancels away in evaluating $\mu_{A}/\sigma_{A}$.
This primarily occurs due to the central limit theorem approximation made in
the large $N_{H}$ limit, and thus the obtained probabilities no longer depend
on $N_{H}$. Computing the probability that $A$ maintains a top-k vector
numerically, we see that for all cases considered in our results, i.e., $k\geq
3$ and $N_{L}\geq 15$, the probability evaluates to $0.9997$ or larger. Thus,
for sufficiently large $N_{H}$, all topk vectors, i.e., all predefined label
layer states (and hence all predefined hidden layer states) are fixed points.

Ideally, if we do not make a central limit approximation, the non-normality of
the distributions will allow for an $N_{H}$ dependent result which may be used
to compute $N_{H}^{crit}$, however this calculation lies beyond the scope of
the current work.

###  A.6 Memory scaffold dynamics converge within a single iteration

Here we provide the proof for the Corollary 4.2 that suggests single iteration
convergence of the memory scaffold dynamics given $N_{H}>N_{H}^{crit}$.

###### Proof.

This follows trivially from Eq. (5) and Theorem 4.1: since the
$\operatorname*{topk}$ nonlinearity ensures that $l(0)$ will be a $k$-hot
vector, and all $k$-hot vectors are predefined fixed points, thus
$l(0)=l^{\mu}$ for some $\mu$. Correspondingly, in the next time step,
$h(1)=\operatorname*{sgn}[W_{HL}l^{\mu}]=h^{\mu}$, and the hidden layer state
arrives at a fixed point within a single step starting from any vector. ∎

###  A.7 Memory scaffold has maximally sized basins of attraction

Theorem 4.3 suggests the existence of maximally sized basins of attraction
that are equal in volume. Here we provide the proof for the same.

###### Proof.

From Lemma 4.2, we see that the union of the basins about each of the
predefined fixed points cover the entire space $\\{-1,1\\}^{N_{H}}$. Note that
each $h^{\mu}$ are equivalent, i.e., there is no special $\mu$ since each
$l^{\mu}$ is equivalent up to a permutation of bits and $h^{\mu}$ are a random
projection of $l^{\mu}$. Thus, $\\{-1,1\\}^{N_{H}}$ must be partitioned into
basins with equal volume that are maximally large (and hence are of the same
volume as the Voronoi cell about the fixed points). ∎

###  A.8 Convexity of scaffold basins

Having shown the existence of maximally sized equi-volumed basins about each
predefined memory scaffold state (Theorem 4.3) is insufficient to guarantee
robustness to noise. This is because large basins do not preclude the case of
non-convex basins with basin boundaries arbitrarily close to the fixed points
(which is the basis for adversarial inputs). Here we demonstrate that the
obtained basins are convex, and thus the large basins must result in basin
boundaries that are well separated from the fixed points themselves.

Note that we are interested in the basins in the space $\\{-1,1\\}^{N_{H}}$,
since the hidden layer is used as the access to the memory scaffold and noise
robustness will hence be required there. The broad idea of the proof is as
follows: first we demonstrate that perturbations in the binary hidden-layer
space are equivalent to considering real-valued perturbations with small
magnitudes in the label-layer space. Then we show that the topk nonlinearity
on the labels results in convex basins in the label layer, which directly
translates to convex basins in the hidden layer space.

Consider a hidden layer state given by a small peturbation to a predefined
hidden-layer fixed point $h^{\mu}$, which we donote as $h=h^{\mu}+\epsilon$.
Since $h\in\\{-1,1\\}^{N_{H}}$, perturbations must take the form of bit-flips,
and the vector epsilon must have values of either of $-2$, $2$ or $0$ at each
component222More particularly, $\epsilon=-2h^{\mu}\odot\hat{\epsilon}$, where
$\odot$ represents pointwise multiplication, and $\hat{\epsilon}$ is a vector
with a $1$ at the location of the bit flips and 0 otherwise, but the
particular form of $\epsilon$ will not be essential to our argument. Let
$\delta$ denote the fraction of nonzero components of $\epsilon$. For small
perturbations, $\delta\ll 1$. This is mapped to the label layer through
$W_{LH}$ to obtain $\bar{l}$ before the application of the topk nonlinearity,
where

$\displaystyle\bar{l}$ $\displaystyle=W_{LH}h=W_{LH}[h^{\mu}+\epsilon]$ (48)
$\displaystyle=\bar{l}^{\mu}+W_{LH}\epsilon.$ (49)

Note that $W_{LH}\epsilon$ will have a magnitude of approximately $\delta$
times the magnitude of $\bar{l}^{\mu}$, and further, the nonzero elements of
$\epsilon$ are uncorrelated with $h^{\mu}$, and hence $W_{LH}\epsilon$ can be
treated as a small real-valued perturbation to $\bar{l}^{\mu}=W_{LH}h^{\mu}$.

If we can now show that the topk nonlinearity acting on a real-valued vector
has a convex basin, that would indicate that all points near $l^{\mu}$ map to
$l^{\mu}$, and since points near $h^{\mu}$ map to points near $l^{\mu}$, this
would imply convexity of basins in $h$-space.

Since all predefined label states are equivalent up to a permutation of
indices, it will suffice to show that the basin about any fixed point is
convex. Without loss of generality, we choose the fixed point $l^{\mu}$ whose
first $k$ components are 1, and remaining components are 0. Let $p$ and $q$ be
two real-valued vectors such that
$\operatorname*{topk}(p)=\operatorname*{topk}(q)=l^{\mu}$, i.e., both $p$ and
$q$ lie in the basin of attraction of $l^{\mu}$. Thus, $p_{i}>p_{j}$ and
$q_{i}>q_{j}$ for all $1\leq i\leq k$ and $j>k$. Adding the two inequalities
with coefficients $a$ and $(1-a)$, we obtain
$ap_{i}+(1-a)q_{i}>ap_{j}+(1-a)q_{j}$ for all $1\leq i\leq k$ and $j>k$. Thus,
$\operatorname*{topk}(ap+(1-a)q)=l^{\mu}$. Thus for any two vectors $p$ and
$q$ that lie in the basin of $l^{\mu}$, all vectors on the line from $p$ to
$q$ also belong in the basin. Hence, the basin is convex in the label layer
space, and as argued earlier this imposes convexity of basins in the hidden
layer space.

###  A.9 Perfect reconstruction of hidden layer states through
heteroassociative Psuedoinverse learning

Here we provide the proof for Theorem 5.1.

###### Proof.

The projection of the stored patterns onto the hidden state is given by
$W_{HF}F=HF^{+}F=HP_{F}$, where $P_{F}=F^{+}F$ is an orthogonal projection
operator onto the range of $F^{T}$. If $N_{F}\geq N_{patts}$, $F$ has linearly
independent columns, and $P_{F}=\mathbf{1}$. Thus $W_{HF}F=H$. ∎

###  A.10 Perfect reconstruction of $N_{H}$ feature states through
heteroassociative Psuedoinverse learning

To prove Theorem 5.2, we first require the following lemma,

######  Lemma A.1.

The matrix $H$, constructed with columns as the predefined hidden layer states
$h^{\mu}$ is full rank.

While we do not prove this lemma, we note that
$H=\operatorname*{sgn}[W_{HL}L]$, and while
$\operatorname{rank}(L)=N_{L}<N_{H}$, the sign nonlinearity results in
perturbations to the value of $H$ at each element, resulting in $H$ becoming
full rank. Theorem 5.2 can now be proved following a similar argument to
Theorem 5.1.

###### Proof.

The projection of the hidden layer states onto the feature layer is given by
$W_{FH}H=FH^{+}H=FP_{H}$, where $P_{H}=H^{+}H$ is an orthogonal projection
operator onto the range of $H^{T}$. For upto $N_{patts}\leq N_{H}$,
$P_{F}=\mathbf{1}$ and thus $W_{FH}H=F$. ∎

###  A.11 Overlap in MESH scales as $1/N_{patts}$

Lemma 5.3 states that the overlap between the stored and recovered patterns
(ignoring the sgn non linearity) in MESH scales as $1/N_{patts}$. Here we
present the proof for the same.

###### Proof.

Let $\bar{f}^{\mu}$ be the reconstruction of pattern $f^{\mu}$ in the feature
layer before the application of the sign nonlinearity, i.e.,
$\bar{f}^{\mu}=W_{FH}h^{\mu}$. Correspondingly, let $\bar{F}$ be the matrix
constructed with $\bar{f}^{\mu}$ as its columns, i.e.,
$\bar{F}_{i\mu}=\bar{f}^{\mu}_{i}$. In this notation, we wish to prove that
$f^{\mu}\cdot\bar{f}^{\mu}/|f^{\mu}|^{2}=N_{H}/N_{patts}$.

As earlier, $\bar{F}=FP_{H}$. Since $N_{patts}>N_{H}$,
$\operatorname{rank}(H)=N_{H}$, and the projection operator $P_{H}$ is thus no
longer an identity operator. Instead, $P_{H}$ projects on to the
$N_{H}$-dimensional hyperplane $\mathcal{S}_{H}$ spanned by the rows of $H$.
Notationally, let $\bar{f}_{i}$ be the vector corresponding to the
$i^{\text{th}}$ row of $\bar{F}$, and similarly, let $f_{i}$ be the vector
corresponding to the $i^{\text{th}}$ row of $F$. In this notation, the vectors
$\bar{f}_{i}$ (i.e., the rows of $\bar{F}$) are the vectors obtained by
projecting $f_{i}$ (i.e., the rows of $F$) onto $\mathcal{S}_{H}$.

By construction $f_{i}$ are $N_{patts}$-dimensional random vectors with no
privileged direction. Thus, $|f_{i}|^{2}$, the squared magnitude along each
dimension, will on average be equally divided across all dimensions. Hence, on
average, the component of $f_{i}$ projected onto $\mathcal{S}_{H}$ (i.e.,
$\bar{f}_{i}$) will have a squared magnitude of $N_{H}|f_{i}|^{2}/N_{patts}$
and thus $|\bar{f}_{i}|=|f_{i}|\sqrt{N_{H}/N_{patts}}$. However,
$|\bar{f}_{i}|$ is also the cosine of the angle between $f_{i}$ and the
hyperplane $\mathcal{S}_{H}$, and hence averaged over $i$,

$f_{i}\cdot\bar{f}_{i}=|f_{i}||\bar{f}_{i}|\sqrt{N_{H}/N_{patts}}=|f_{i}|^{2}N_{H}/N_{patts}.$
(50)

Note that
$\sum_{i}(f_{i}\cdot\bar{f}_{i})=\sum_{\mu}(f^{\mu}\cdot\bar{f}^{\mu})$, and
$\sum_{i}|f_{i}|^{2}=\sum_{\mu}|f^{\mu}|^{2}$. Thus the above equation can be
rewritten as

$f^{\mu}\cdot\bar{f}^{\mu}=|f^{\mu}|^{2}N_{H}/N_{patts}$ (51)

∎

###  A.12 Fashion MNIST: larger autoencoder

Layer sizes of the larger autoencoder used to compress the dataset to extract
lower dimensional features: 700, 600, 500, 600, 700. The autoencoder
compressed the $28\times 28$ images to 500 dimensional features.