1

Noise Facilitation in Associative Memories of
Exponential Capacity
Amin Karbasi, Amir Hesam Salavati, Amin Shokrollahi, and Lav R. Varshney

arXiv:1403.3305v1 [] 13 Mar 2014

Abstract
Recent advances in associative memory design through structured pattern sets and graph-based inference algorithms have allowed reliable learning and recall of an exponential number of patterns. Although these designs
correct external errors in recall, they assume neurons that compute noiselessly, in contrast to the highly variable
neurons in brain regions thought to operate associatively such as hippocampus and olfactory cortex.
Here we consider associative memories with noisy internal computations and analytically characterize performance. As long as the internal noise level is below a specified threshold, the error probability in the recall phase
can be made exceedingly small. More surprisingly, we show that internal noise actually improves the performance
of the recall phase while the pattern retrieval capacity remains intact, i.e., the number of stored patterns does not
reduce with noise (up to a threshold). Computational experiments lend additional support to our theoretical analysis.
This work suggests a functional benefit to noisy neurons in biological neuronal networks.

I. I NTRODUCTION
RAIN regions such as hippocampus and olfactory cortex are thought to operate as associative memories [2]–[4],
having the ability to learn patterns from presented inputs, store a large number of patterns, and retrieve them
reliably in the face of noisy queries [5]–[7]. Mathematical models of associative memory are therefore designed to
memorize a set of given patterns so that corrupted versions of the memorized patterns may later be presented and
the correct memorized pattern retrieved.
Although such information storage and recall seemingly falls naturally into the information-theoretic framework
[8], where an exponential number of messages can be communicated reliably using a linear number of symbols [9],
classical associative memory models can only store a linear number of patterns with a linear number of symbols
[6]. A primary shortcoming of such classical models has been their requirement to memorize a randomly chosen
set of patterns. By enforcing structure and redundancy in the possible set of memorizable patterns—much like
natural stimuli [10], internal representations in neural systems [11], and codewords in error-control codes [12]—
new advances in associative memory design allow storage of an exponential number of patterns with a linear number
of symbols [13], [14], just like in communication systems.1
Information-theoretic and associative memory models of storage have been used to predict experimentally
measurable properties of synapses in the mammalian brain [16], [17]. But contrary to the fact that noise is present
in computational operations of the brain [18]–[22], associative memory models with exponential capacity have
assumed no internal noise in the computational nodes [14]; likewise with many classical models [5]. The purpose
of the present paper is to model internal noise in associative memories with exponential pattern retrieval capacity
and study whether they are still able to operate reliably. Surprisingly, we find internal noise actually enhances recall
performance without loss in capacity, thereby suggesting a functional role for variability in the brain.
In particular we consider a convolutional, graph code-based, associative memory model [14] and find that even
if all components are noisy, the final error probability in recall can be made exceedingly small. We characterize
a threshold phenomenon and show how to optimize algorithm parameters when knowing statistical properties of

B

This work is based in part on a paper presented at the 2013 Neural Information Processing Systems Conference, Lake Tahoe, December
2013 [1].
A. Karbasi is with Eidgenössische Technische Hochschule Zürich, Switzerland (e-mail: amin.karbasi@inf.ethz.ch).
A. H. Salavati and A. Shokrollahi are with École Polytechnique Fédérale de Lausanne, Switzerland (e-mail: {hesam.salavati,
amin.shokrollahi}@epfl.ch).
L. R. Varshney was with the IBM Thomas J. Watson Research Center, NY. He is now with the University of Illinois at Urbana-Champaign
(e-mail: varshney@illinois.edu).
1
The idea of restricted pattern sets leading to associative memories with increased storage capacity was first suggested in an unpublished
doctoral dissertation [15].

2

internal noise. Rather counterintuitively the performance of the memory model improves in the presence of internal
neural noise, as has been observed previously as stochastic resonance in the literature [21], [23]. Deeper analysis
shows mathematical connections to perturbed simplex algorithms for linear programing [24], where some internal
noise helps the algorithm get out of local minima.
A. Related Work
Designing neural networks to learn a set of patterns and recall them later in the presence of noise has been
an active topic of research for the past three decades. Inspired by Hebbian learning [25], Hopfield introduced an
auto-associative neural mechanism of size n with binary state neurons in which patterns are assumed to be binary
vectors of length n [5]. The capacity of a Hopfield network under vanishing block error probability was later
shown to be O(n/ log(n)) [6]. With the hope of increasing the capacity of the Hopfield network, extensions to
non-binary states were explored [7]. In particular, Jankowski et al. investigated a multi-state complex-valued neural
associative memory with estimated capacity less than 0.15n [26]; Muezzinoglu et al. showed the capacity with a
prohibitively complicated learning rule to increase to n [27]. Lee proposed the Modified Gradient Descent learning
Rule (MGDR) to overcome this drawback [28].
To further increase capacity and robustness, a recent line of work considers exploiting structure in patterns. This
is done either by making use of correlations among patterns or by only memorizing patterns with redundancy
(rather than any possible set of patterns). By utilizing neural cliques, [29] demonstrated that increasing the pattern
retrieval capacity of Hopfield networks to O(n2 ) is possible. Modification of neural architecture to improve pattern
retrieval capacity has also been previously considered by Venkatesh and Biswas [15], [30], where the capacity is
increased to Θ bn/b for semi-random patterns, where b = ω(ln n) is the size of clusters. This significant boost
to capacity is achieved by dividing the neural network into smaller fully interconnected disjoint blocks or nested
blocks (cf. [31]). This huge improvement comes at the price of limited worst-case noise tolerance capabilities.
Deploying higher order neural models beyond the pairwise correlation considered in Hopfield networks increases
the storage capacity to O(np−2 ), where p is the degree of correlation [32]. In such models, neuronal state depends
not only on the state of neighbors, but also on the correlations among them. A new model based on bipartite graphs
that captures higher-order correlations (when patterns belong to a subspace), but without prohibitive computational
complexity, improved capacity to O(an ), for some a > 1, that is to say exponential in network size [13].
The basic memory architecture, learning rule, and recall algorithm used herein is from [14], which also achieves
exponential capacity by capturing internal redundancy by dividing the patterns into smaller overlapping clusters,
with each subpattern satisfying a set of linear constraints. The problem of learning linear constraints with neural
networks was considered in [33], but without sparsity requirements. This has connections to compressed sensing
[34]; typical compressed sensing recall/decoding algorithms are too complicated to be implemented by neural
networks, but some have suggested the biological plausibility of message-passing algorithms [35].
Building on the idea of structured pattern sets [29], the basic associative memory model used herein [14] relies
on the fact all patterns to be learned lie in a low-dimensional subspace. Learning features of a low-dimensional
space is very similar to autoencoders [36]. The model also has similarities to Deep Belief Networks (DBNs)
and in particular Convolutional Neural Networks [37], albeit with different objectives. DBNs are made of several
consecutive stages, similar to overlapping clusters in our model, where each stage extracts some features and feeds
them to the following stage. The output of the last stage is then used for pattern classification. In contrast to DBNs,
our associative memory model is not classifying patterns but rather recalling patterns from noisy versions. Also,
overlapping clusters can operate in parallel to save time in information diffusion over a staged architecture.
In most deep or convolutional models, one not only has to find the proper dictionary for classification, but also
calculate the features for each input pattern. This increases the complexity of the whole system when the objective
is simply recall. Here the dictionary corresponds to the dual vectors from previously memorized patterns.
In this work, we reconsider the neural network model of [14], but introduce internal computation noise consistent
with biology. Note that the sparsity of the model architecture is also consistent with biology [38]. We find that
there is actually a functional benefit to internal noise.
The benefit of internal noise has been noted previously in associative memory models with stochastic update
rules, cf. [39], by analyzing attractor dynamics. In particular, it has been shown that noise may reduce recall
time in associative memory tasks by pushing the system from one attractor state to another [40]. However, our

3

framework differs from previous approaches in three key aspects. First, our memory model is different, which
makes extension of previous analysis nontrivial. Second, and perhaps most importantly, pattern retrieval capacity
in previous approaches decreases with internal noise, cf. [39, Figure 6.1], in that increasing internal noise helps
correct more external errors, but also reduces the number of memorizable patterns. In our framework, internal noise
does not affect pattern retrieval capacity (up to a threshold) but improves recall performance. Finally, our noise
model has bounded rather than Gaussian noise, and so a suitable network may achieve perfect recall despite internal
noise.
Reliably storing information in memory systems constructed completely from unreliable components is a classical
problem in fault-tolerant computing [41]–[43], where typical models have used random access architectures with
sequential correcting networks. Although direct comparison is difficult since notions of circuit complexity are
slightly different, our work also demonstrates that associative memory architectures can store information reliably
despite being constructed from unreliable components.
II. A SSOCIATIVE M EMORY M ODEL
In this section, we introduce our main notation, the model of associative memories and noise. We also explain
the recall algorithms.

A. Notation and basic structure
In our model, a neuron can assume an integer-valued state from the set Q = {0, . . . , Q − 1}, interpreted as the
n
short term firing rate of neurons. A neuron
Pnupdates its state based on the states of its neighbor {si }i=1 as follows.
It first computes a weighted sum h = i=1 wi si + ζ , where wi is the weight of the link from si and ζ is the
internal noise, and then applies nonlinear function f : R → Q to h.
An associative memory is represented by a weighted bipartite graph, G, with pattern neurons and constraint
neurons. Each pattern x = (x1 , x2 , . . . , xn ) is a vector of length n, where xi ∈ Q, i = 1, . . . , n. Following [14], the
focus is on recalling patterns with strong local correlation among entries. Hence, we divide entries of each pattern
x into L overlapping subpatterns of lengths n1 , n2 , . . . , nL . Due to overlaps, a pattern neuron can be a member of
(i) (i)
(i)
multiple subpatterns, as depicted in Figure 1a. The ith subpattern is denoted x(i) = (x1 , x2 , . . . , xni ), and local
correlations are assumed to be in the form of subspaces, i.e. the subpatterns x(i) form a subspace of dimension
ki < ni .
We capture the local correlations by learning a set of linear constraints over each subspace corresponding to
(i)
(i)
(i)
the dual vectors orthogonal to that subspace. More specifically, let {w1 , w2 , . . . , wmi } be a set of dual vectors
orthogonal to all subpatterns x(i) of cluster i. Then:
(i)

(i)

yj = (wj )T · x(i) = 0,

for all j ∈ {1, . . . , mi } and for all i ∈ {1, . . . , L}.
(i)

(i)

(1)

(i)

Eq. (1) can be rewritten as W (i) · x(i) = 0 where W (i) = [w1 |w2 | · · · |wmi ]T is the matrix of dual vectors. Now
we use a bipartite graph with connectivity matrix determined by W (i) to represent the subspace constraints learned
from subpattern x(i) ; this graph is called cluster i. We developed an efficient way of learning W (i) in [14], also
used here. Briefly, in each iteration of learning:
1) Pick a pattern x at random from the dataset;
(i)
(i)
2) Adjust weight vectors wj for j = {1, . . . , mi } and i = {1, . . . , L} such that the projection of x onto wj
is reduced. Apply a sparsity penalty to favor sparse solutions.
This process repeats until all weights are orthogonal to the patterns in the dataset or the maximum iteration limit
is reached. The learning rule allows us to assume the weight matrices W (i) are known and satisfy W (i) · x(i) = 0
for all patterns x in the dataset X , in this paper.
e whose connectivity matrix is
For the forthcoming asymptotic analysis, we need to define a contracted graph G
f
denoted W and has size L × n. This is a bipartite graph in which constraints in each cluster are represented by a
fij = 1; otherwise W
fij = 0, see Figure 1b.
single neuron. Thus, if pattern neuron xj is connected to cluster i, W

4
G(1)
y1

y2

G(2)
y3

y4

(2)

x1

(2)

x2

G(3)
y5

(2)

x3

y6

y7

y8

(2)

x4

(a) Bipartite graph G.

e
(b) Contraction graph G.

Fig. 1: The proposed neural associative memory with overlapping clusters.
e , using
We also define the degree distribution from an edge perspective over G
X
e
ej z j−1 , and
λ(z)
=
λ

(2)

j

ρe(z) =

X

ρej z j−1 ,

(3)

j

ej (resp., ρej ) equals the fraction of edges that connect to pattern (resp., cluster) nodes of degree j .
where λ
B. Noise model
There are two types of noise in our model: external errors and internal noise. As mentioned earlier, a neural
network should be able to retrieve memorized pattern x̂ from its corrupted version x due to external errors. We
assume the external error is an additive vector of size n, denoted by z satisfying x = x̂ + z , whose entries assume
values independently from {−1, 0, +1}2 with corresponding probabilities p−1 = p+1 = /2 and p0 = 1 − .
The realization of the external error on subpattern x(i) is denoted z (i) . Note that the subspace assumption implies
W · y = W · z and W (i) · y (i) = W (i) · z (i) for all i.
Neurons also suffer from internal noise. We consider a bounded noise model, i.e. a random number uniformly
distributed in the intervals [−υ, υ] and [−ν, ν] for the pattern and constraint neurons, respectively (υ, ν < 1).
The goal of recall is to filter the external error z to obtain the desired pattern x as the correct states of the pattern
neurons. When neurons compute noiselessly, this task may be achieved by exploiting the fact the set of patterns
x ∈ X satisfy the set of constraints W (i) · x(i) = 0. However, it is not clear how to accomplish this objective when
the neural computations are noisy. Rather surprisingly, we show that eliminating external errors is not only possible
in the presence of internal noise, but that neural networks with moderate internal noise demonstrate better external
error resilience.
C. Recall algorithms
To efficiently deal with external errors in associative memory, we use two simple iterative message passing
algorithms. The role of the first one, called the Intra-cluster algorithm and formally defined in Algorithm 1, is
to correct at least a single external error in each cluster. However, without overlaps between clusters, the error
2
Note that the proposed algorithms also work with larger noise values, i.e. from a set {−S, . . . , S} for some S ∈ N, see Sec. IV-A2; the
±1 noise model is presented here for simplicity.

5

resilience of this approach and the network in general is limited. The second algorithm, the Inter-cluster recall
algorithm, exploits the overlaps: it helps clusters with external errors recover their correct states by using the
reliable information from clusters that do not have external errors. The error resilience of the resulting combination
thereby drastically improves.
To go further into details, and with abuse of notations, let xi (t) and yj (t) denote the message transmitted at
iteration t by pattern and constraint neurons, respectively. In the first iteration, we initialize the pattern neurons
with a pattern randomly drawn from the dataset, x̂, corrupted with some external noise, z . Thus, x(0) = x̂ + z . As
a result, for cluster ` we have x(`) (0) = x̂(`) + z (`) , where z (`) is the realization of the external error on cluster `.
With these notations in mind, Algorithm 1 iteratively performs a series of forward and backward steps in order
to remove (at least) one external error from its input domain. Assuming that the algorithm is applied to cluster `,
in the forward step of iteration t the pattern neurons in cluster ` transmit their current states to their neighboring
constraint neurons. Each constraint neuron j then calculates the weighted sum of the messages it received over its
input links. Nevertheless, since neurons suffer from internal noise, additional noise terms appear in the weighted
P `
(`)
(`) (`)
sum, i.e., hj = ni=1
Wij xi + vi , where vi is the random internal noise affecting node i. As before, we consider
a bounded noise model for vi , i.e., it is uniformly distributed in the interval [−ν, ν] for some ν < 1.
A non-zero input sum, excluding the effect of vi , is an indication of the presence of external errors among the
pattern neurons. Thus, constraint neurons set to their states to the sign of the received weighted sum if its magnitude
is larger than a fixed threshold, ψ . More specifically, constraint neuron j updates its state based on the received
weighted sum according to the following rule

(`)

+1, if hj (t) ≥ ψ
(`)
(`)
(`)
yj (t) = f (hj (t), ψ) = 0,
(4)
if − ψ ≤ hj (t) ≤ ψ


−1, otherwise,
(`)

(`)

Here, x(`) (t) = [x1 (t), . . . , xn` (t)] is the vector of messages transmitted by the pattern neurons and vi is the
random internal noise affecting node i.3
In the backward step, the constraint neurons communicate their states to their neighboring pattern neurons. The
pattern neurons then compute a normalized weighted sum on the messages they receive over their input link and
update their current state if the amount of received (non-zero) feedback exceeds a threshold. Otherwise, they will
retain their current state for the next round. More specifically, pattern node i in cluster ` updates its state in round
t according to the equation below
( (`)
(`)
(`)
xi (t) − sign(gi (t)), if |gi (t)| ≥ ϕ
(`)
xi (t + 1) =
(5)
(`)
xi (t),
otherwise,
where ϕ is the update threshold and
(`)
gi (t)

=

(sign(W (`) )> · y (`) (t)
(`)
di


i

+ ui .

(`)

Note that xi (t + 1) is further mapped to the interval [0, Q − 1] by saturating the values below 0 and above Q − 1 to
(`)
0 and Q − 1 respectively; this saturation is not stated mathematically for brevity. Here, di is the degree of pattern
(`)
(`)
node i in cluster `, y (`) (t) = [y1 (t), . . . , ym` (t)] is the vector of messages transmitted by the constraint neurons
(`)
in cluster `, and ui is the random internal noise affecting pattern node i. Basically, the term gi (t) reflects the
(`)
(average) belief of constraint nodes connected to pattern neuron i about its correct value. If gi (t) is larger than
(`)
a specified threshold ϕ it means most of the connected constraints suggest the current state xi (t) is not correct,
hence, a change should be made. Note this average belief is diluted by the internal noise of neuron i. As mentioned
earlier, ui is uniformly distributed in the interval [−υ, υ], for some υ < 1.
The error correction ability of Algorithm 1 is fairly limited, as determined analytically and through simulations in
the sequel. In essence, Algorithm 1 can correct one external error with high probability, but degrades terribly against
3

(`)

Note that although the values of yi (t) can be shifted to 0, 1, 2, instead of −1, 0, 1 to match our assumption that neural states are
non-negative, we leave them as such to simplify later analysis.

6

Algorithm 1 Intra-Module Error Correction
Input: Training set X , thresholds ϕ, ψ , iteration tmax
(`) (`)
(`)
Output: x1 , x2 , . . . , xn`
1: for t = 1 → tmax do
Pn`
(`)
(`) (`)
(`)
(`)
2:
Forward iteration: Calculate the input hi =
and set yi =
j=1 Wij xj + vi , for each neuron yi
(`)

3:

f (hi , ψ).
(`)
Backward iteration: Each neuron xj computes

sign(Wij(`) )yi(`)
+ ui .
(`)
i=1 sign(|Wij |)
(`)
(`)
(`)
(`)
4:
Update the state of each pattern neuron j according to xj = xj − sign(gj ) only if |gj | > ϕ.
5: end for
(`)

gj =

Pm`

i=1

Pm`

Algorithm 2 Sequential Peeling Algorithm
e G(1) , G(2) , . . . , G(L) .
Input: G,
Output: x1 , x2 , . . . , xn
1: while there is an unsatisfied v (`) do
2:
for ` = 1 → L do
3:
If v (`) is unsatisfied, apply Algorithm 1 to cluster G(l) .
4:
If v (`) remained unsatisfied, revert the state of pattern neurons connected to v (`) to their initial state.
Otherwise, keep their current states.
5:
end for
6: end while
7: Declare x1 , x2 , . . . , xn if all v (`) ’s are satisfied. Otherwise, declare failure.

two or more external errors. Working independently, clusters cannot correct more than a few external errors, but
their combined performance is much better. As clusters overlap, they help each other in resolving external errors:
a cluster whose pattern neurons are in their correct states can always provide truthful information to neighboring
clusters. This property is exploited in Algorithm 2 by applying Algorithm 1 in a round-robin fashion to each
cluster. Clusters either eliminate their internal noise in which case they keep their new states and can now help
other clusters, or revert back to their original states. Note that by such a scheduling scheme, neurons can only
change their states towards correct values. This scheduling technique is similar in spirit to the peeling algorithm
[44].
III. PATTERN R ETRIEVAL C APACITY
Before proceeding to analyze recall performance, for completeness we review pattern retrieval capacity results
from [14] to show that the proposed model is capable of memorizing an exponentially large number of patterns.
First, note that since the patterns form a subspace, the number of patterns C does not have any effect on the
learning or recall algorithms (except for its obvious influence on the learning time). Thus, in order to show that
the pattern retrieval capacity is exponential in n, all we need to demonstrate is that there exists a training set X
with C patterns of length n for which C ∝ arn , for some a > 1 and 0 < r.

Theorem 1 ( [14]). Let X be a C × n matrix, formed by C vectors of length n with entries from the set Q.
Furthermore, let k = rn for some 0 < r < 1. Then, there exists a set of vectors for which C = arn , with a > 1,
and rank(X ) = k < n.
The proof is constructive: we create a dataset X such that it can be memorized by the proposed neural network

7

and satisfies the required properties, i.e. the subpatterns form a subspace and pattern entries are integer values from
the set Q = {0, . . . , Q − 1}. The complete proof can be found in [14].
IV. R ECALL P ERFORMANCE A NALYSIS
Now let us analyze recall error performance. The following lemma shows that if ϕ and ψ are chosen properly,
then in the absence of external errors the constraints remain satisfied and internal noise cannot result in violations.
This is a crucial property for Algorithm 2, as it allows one to determine whether a cluster has successfully eliminated
external errors (Step 4 of algorithm) by merely checking the satisfaction of all constraint nodes.
Lemma 1. In the absence of external errors, the probability that a constraintneuron 
(resp. pattern neuron) in cluster

(`)
(`)
` makes a wrong decision due to its internal noise is given by π0 = max 0, ν−ψ
(resp. P0 = max 0, υ−ϕ
).
ν
υ
Proof: To calculate the probability that a constraint node makes a mistake when there are no external errors,
consider constraint node i whose decision parameter will be


(`)
hi = W (`) · x(`) + vi = vi .
i

Therefore, the probability of making a mistake will be
(`)
π0



ν−ψ
= Pr{|vi | > ψ} = max 0,
ν



.

(6)

(`)

Thus, to make π0 = 0 we will select ψ > ν . Note that this might not be possible in all cases since, as we will
see, the minimum absolute value of network weights should be at least ψ ; if ψ is too large we might not be able
to find a proper set of weights. Nevertheless, and assuming that it is possible to choose a proper ψ , we will have
π (0) = 0.

(7)

Now knowing that the constraint will not send any non-zero messages in the absence of external noise, we
(`)
focus on the pattern neurons in the same circumstance. A given pattern node xj will receive a zero from all its
(`)

neighbors among the constraint nodes. Therefore, its decision parameter will be gj = uj . As a result, a mistake
could happen if |uj | ≥ ϕ. The probability of this event is given by


υ−ϕ
(`)
P0 = Pr{|ui | > ϕ} = max 0,
.
(8)
ϕ
(`)

Therefore, to make P0 go to zero, we must select ϕ ≥ υ .
(`)
(`)
In the sequel, we assume ϕ > υ and ψ > ν so that π0 = 0 and P0 = 0. However, an external error combined
with internal noise may still push neurons to an incorrect state.
Given the above lemma and our neural architecture, we can prove the following surprising result: in the asymptotic
regime of increasing number of iterations of Algorithm 2, a neural network with internal noise outperforms one
without, with the pattern retrieval capacity remaining intact. Let us define the fraction of errors corrected by the
noiseless and noisy neural network (parametrized by υ and ν ) after T iterations of Algorithm 2 by Λ(T ) and
Λυ,ν (T ), respectively. Note that both Λ(T ) ≤ 1 and Λυ,ν (T ) ≤ 1 are non-decreasing sequences of T . Hence, their
limiting values are well defined: limT →∞ Λ(T ) = Λ∗ and limT →∞ Λυ,ν (T ) = Λ∗υ,ν .
(`)

(`)

Theorem 2. Let us choose ϕ and ψ so that π0 = 0 and P0 = 0 for all ` ∈ {1, . . . , L}. For the same realization
of external errors, we have Λ∗υ,ν ≥ Λ∗ .

Proof: We first show that the noisy network can correct any external error pattern that the noiseless counterpart
can correct in the T → ∞ limit. If the noiseless decoder succeeds, then there is a non-zero probability P that the
noisy decoder succeeds in a given round as well (corresponding to the case that noise values are rather small).
Since we do not introduce new errors during the application of Algorithm 2, the number of errors in the new
rounds are smaller than or equal to the previous round, hence the probability of success is lower bounded by P .
If Algorithm 2 is applied T times, then the probability of correcting the external errors at the end of round T is
P + P (1 − P ) + · · · + P (1 − P )T −1 = 1 − (1 − P )T . Since P > 0, for T → ∞ this probability tends to 1.

8

Now, we turn attention to cases where the noiseless network fails in eliminating external errors and show that
there exist external error patterns, called stopping sets, for which the noisy network is capable of eliminating them
while the noiseless network has failed; see Appendix A for further explication. Assuming that each cluster can
eliminate i external errors in their domain and in the absence of internal noise,4 stopping sets correspond to noise
patterns in which each cluster has more than i errors. Then Algorithm 2 cannot proceed any further. However, in
the noisy network, there is a chance that in one of the rounds, the noise acts in favorably and the cluster could
correct more than i errors.5 In this case, if the probability of getting out of the stopping set is P in each round,
for some P > 0, then a similar argument to the previous case shows that P → 1 when T → ∞.
It should be noted that if the amount of internal noise or external errors is too high, the noisy architecture will
eventually get stuck just like the noiseless network. The high level idea why a noisy network outperforms a noiseless
one comes from understanding stopping sets, realizations of external errors where the iterative Algorithm 2 cannot
correct them all. We showed that the stopping set shrinks as we add internal noise and so the supposedly harmful
internal noise helps Algorithm 2 to avoid stopping sets. Appendix A illustrates this notion further.
Theorem 2 suggests the only possible downside to using a noisy network is its possible running time in eliminating
external errors: the noisy neural network may need more iterations to achieve the same error correction performance.
Interestingly, our empirical experiments show that in certain scenarios, even the running time improves when using
a noisy network.
Theorem 2 indicates that noisy neural networks (under our model) outperform noiseless ones, but does not specify
the level of errors that such networks can correct. Now we derive a theoretical upper bound on error correction
performance. To this end, let Pci be the average probability that a cluster can correct i external errors in its domain.
The following theorem gives a simple condition under which Algorithm 2 can correct a linear fraction of external
errors (in terms of n) with high probability. The condition involves λ̃ and ρ̃, the degree distributions of the contracted
graph G̃.
e grows large and it is chosen randomly with degree distributions
Theorem 3. Under the assumptions that graph G
e
given by λ and ρe, Algorithm 2 is successful if


i−1 di−1 ρ
X
e
(1
−
z)
z
e 1 −
 < z, f or z ∈ [0, ].
·
(9)
P ci
λ
i!
dz i−1
i≥1

Proof: The proof is based on the density evolution technique [12]. Without loss of generality, assume we have
Pc1 , Pc2 , and Pc3 (and Pci = 0 for i > 3.) but the proof can easily be extended if we have Pci for i > 3. Let Π(t)
be the average probability that a super constraint node sends a failure message, i.e., that it can not correct external
errors lying in its domain. Then, the probability that a noisy pattern neuron with degree di sends an erroneous
message to a particular neighbor among super constraint node is equal to the probability that none of its other
neighboring super constraint nodes could have corrected its error, i.e.,
Pi (t) = pe (Π(t))di −1 .

Averaging over di we find the average probability of error in iteration t:
e
z(t + 1) = pe λ(Π(t))
.

(10)

Now consider a cluster ` that contains d` pattern neurons. This cluster will not send a failure message over its
edge to a noisy pattern neuron in its domain with probability:
1) Pc1 , if it is not connected to any other noisy neuron;
2) Pc2 , if it is connected to exactly one other constraint neuron;
3) Pc3 , if it is connected to exactly two other constraint neurons; and
4) 0, if it is connected to more than two other constraint neuron.
Thus,




d` − 1
d` − 1
d` −1
d` −2
(`)
Π (t) = 1 − Pc1 (1 − z(t))
− Pc2
z(t) (1 − z(t))
− Pc3
z(t)2 (1 − z(t))d` −3 .
1
2
4
5

From the forthcoming Figure 2, we will see that i = 2 in this case.
This is reflected in the forthcoming Figure 2, where the value of Pci is larger when the network is noisy.

9

Probability of correcting external errors

1
Pc 1
Pc 2
Pc 3
Pc 4

0.8

0.6

0.4

0.2

0
0

0.1

0.2

0.3

0.4
υ

0.5

0.6

0.7

Fig. 2: The value of Pci as a function of pattern neurons noise υ for i = 1, . . . , 4. The noise at constraint neurons
is assumed to be zero (ν = 0).
Averaging over d` yields:


Π(t) = Ed` Π(`) (t) = 1 − Pc1 ρ(1 − z(t)) − Pc2 zρ0 (1 − z(t)) − 12 Pc2 z(t)2 ρ00 (1 − z(t)) ,

(11)

where ρ0 (x) and ρ00 (x) are derivatives of the function ρ(x) with respect to x.
Equations (10) and (11) yield the value of z(t + 1) as a function of z(t). We calculate the final error probability
as limt→∞ z(t); for limt→∞ z(t) → 0, it is sufficient to have z(t + 1) < z(t), which proves the theorem.
It must be mentioned that the above theorem holds when the decision subgraphs for the pattern neurons in graph
e
G are tree-like for a depth of τ L, where τ is the total number of number of iterations performed by Algorithm 2
[12].
Theorem 3 states that for any fraction of errors Λυ,ν ≤ Λ∗υ,ν that satisfies the above recursive formula, Algorithm 2
will be successful with probability close to one. Note that the first fixed point of the above recursive equation dictates
the maximum fraction of errors Λ∗υ,ν that our model can correct. For the special case of Pc1 = 1 and Pci = 0, for
e (1 − ρe(1 − z)) < z , the same condition given in [14]. Theorem 3 takes into account the
all i > 1, we obtain λ
contribution of all Pci terms and as we will see, their values change as we incorporate the effect of internal noise υ
and ν . Our results show that the maximum value of Pci does not occur when the internal noise is equal to zero, i.e.
υ = ν = 0, but instead when the neurons are contaminated with internal noise! As an example, Figure 2 illustrates
how Pci behaves as a function of υ in the network considered (note that maximum values are not at υ = 0). This
finding suggests that even individual clusters are able to correct more errors in the presence of internal noise.
To estimate the Pci values, we use numerical approaches.6 Given a set of clusters W (1) , . . . , W (L) , for each
cluster we randomly corrupt i pattern neurons with ±1 noise. Then, we apply Algorithm 1 over this cluster and
calculate the success rate once finished. We take the average of this rate over all clusters to end up with Pci . The
results of this approach are shown in Figure 2, where the value of Pci is shown for i = 1, . . . , 4 and various noise
amounts at the pattern neurons (specified by parameter υ ).
A. Simulations
Now we consider simulation results for a finite system. To learn the subspace constraints (1) for each cluster G(`)
we use the learning algorithm in [14]. Henceforth, we assume that the weight matrix W is known and given. In our
setup, we consider a network of size n = 400 with L = 50 clusters. We have 40 pattern nodes and 20 constraint
6

Appendix B derives an analytical upper bound to estimate Pc1 but this requires approximations that are loose.

10

Final SER

0.15

0.10

υ
υ
υ
υ
υ
υ
υ
υ

= 0, ν = 0-Sim
= 0, ν = 0-Thr
= 0.2, ν = 0-Sim
= 0.2, ν = 0-Thr
= 0.4, ν = 0-Sim
= 0.4, ν = 0-Thr
= 0.6, ν = 0-Sim
= 0.6, ν = 0-Thr

0.05

0.00
0.00

0.05

ǫ

0.10

Fig. 3: The final SER for a network with n = 400, L = 50. The red curves correspond to the noiseless neural
network.
nodes in each cluster, on average. External error is modeled by randomly generated vectors z with entries ±1 with
probability  and 0 otherwise. Vector z is added to the correct patterns, which satisfy (1). For recall, Algorithm 2
is used and results are reported in terms of Symbol Error Rate (SER) as the level of external error () or internal
noise (υ, ν ) is changed; this involves counting positions where the output of Algorithm 2 differs from the correct
pattern.
1) Symbol Error Rate as a function of Internal Noise: Figure 3 illustrates the final SER of our algorithm for
different values of υ and ν . Remember that υ and ν quantify the level of noise in pattern and constraint neurons,
respectively. Dashed lines in Figure 3 are simulation results whereas solid lines are theoretical upper bounds
provided in this paper. As evident, there is a threshold phenomenon such that SER is negligible for  ≤ ∗ and
grows beyond this threshold. As expected, simulation results are better than the theoretical bounds. In particular,
the gap is relatively large as υ moves towards one.
A more interesting trend in Figure 3 is the fact that internal noise helps in achieving better performance, as
predicted by theoretical analysis (Theorem 2). Notice how ∗ moves towards one as ν increases.
This phenomenon is inspected more closely in Figure 4 where  is fixed to 0.125 while υ and ν vary. Figs. 5a
and 5b display projected versions of the surface plot to investigate the effect of υ and ν separately. As we see
again, a moderate amount of internal noise at both pattern and constraint neurons improves performance. There is
an optimum point (υ ∗ , ν ∗ ) for which the SER reaches its minimum. Figure 5b indicates for instance that ν ∗ ≈ 0.25,
beyond which SER deteriorates. There is greater sensitivity to noise υ in the pattern neurons, reminiscent of results
for decoding circuits with internal noise [45].
2) Larger noise values: So far, we have investigated the performance of the recall algorithm when noise values
are limited to ±1. Although this choice facilitates the analysis of the algorithm and increases error correction speed,
our analysis is valid for larger noise values. Figure 6 illustrates the SER for the same scenario as before but with
noise values chosen from {−3, −2, . . . , 2, 3}. We see exactly the same behavior as we witnessed for ±1 noise
values.
B. Recall Time as a function of Internal Noise
Figure 7 illustrates the number of iterations performed by Algorithm 2 for correcting the external errors when 
is fixed to 0.075. We stop whenever the algorithm corrects all external errors or declare a recall error if all errors
were not corrected in 40 iterations. Thus, the corresponding areas in the figure where the number of iterations
reaches 40 indicates decoding failure. Figs. 8a and 8b are projected versions of Figure 7 and show the average
number of iterations as a function of υ and ν , respectively.

11

Final SER

0.10

0.05

0.00
0.4
0.2
ν

0.4

0 0.5

0.2

0.3

0.1

0

υ

Fig. 4: The final bit error probability when  = 0.125 as a function of internal noise parameters at the pattern and
constraint neurons, denoted by υ and ν , respectively.
ν
ν
ν
ν

Final SER

0.10

=0
= 0.1
= 0.3
= 0.5

0.05

0.00
0

0.1

0.2

υ

0.3

0.4

(a) Final SER as function of υ for  = 0.125.

Final SER

0.10

υ
υ
υ
υ

0.05

=0
= 0.1
= 0.2
= 0.5

0.00
0

0.1

0.2

ν

0.3

0.4

(b) The effect of ν on the final SER for  = 0.125

Fig. 5: The final bit error probability as a function of internal noise parameters at pattern and constraint neurons
for  = 0.125

12

0.20
υ
υ
υ
υ
υ
υ

Final SER

0.15

= 0, ν = 0-Sim
= 0, ν = 0-Thr
= 0.1, ν = 0-Sim
= 0.1, ν = 0-Thr
= 0.6, ν = 0-Sim
= 0.6, ν = 0-Thr

0.10

0.05

0.00
0.00

0.05

0.10

ǫ

Average number of iterations

Fig. 6: The final SER for a network with n = 400, L = 50 and noise values chosen from {−3, −2, . . . , 2, 3}. The
blue curves correspond to the noiseless neural network.

40.00
30.00
20.00
10.00
0.00
0.4
0.2
ν
0 0.5

0.4

0.3

0.2

0.1

0

υ

Fig. 7: The effect of internal noise on the number of iterations performed by Algorithm 2, for different values of
υ and ν with  = 0.075.

13

Average number of iterations

40
ν
ν
ν
ν

=0
= 0.2
= 0.3
= 0.5

10

0

0.1

0.2

υ

0.3

0.4

(a) Effect of internal noise at pattern neurons side.

Average number of iterations

40
υ
υ
υ
υ

=0
= 0.2
= 0.3
= 0.5

10

0

0.1

0.2

ν

0.3

0.4

(b) Effect of internal noise at constraint neurons side.

Fig. 8: The effect of internal noise on the number of iterations performed by Algorithm 2, for different values of
υ and ν with  = 0.075. The average iteration number of 40 indicate the failure of Algorithm 2.

The amount of internal noise drastically affects the speed of Algorithm 2. First, from Figure 7 and 8b observe that
running time is more sensitive to noise at constraint neurons than pattern neurons and that the algorithms become
slower as noise at constraint neurons is increased. In contrast, note that internal noise at the pattern neurons may
improve the running time, as seen in Figure 8a. Ordering of sensitivity to noise in pattern neurons and in constraint
neurons is opposite for running time as compared to error probability.
Note that the results presented so far are for the case where the noiseless decoder succeeds as well and its average
number of iterations is pretty close to the optimal value (see Figure 7). Figure 9 illustrates the number of iterations
performed by Algorithm 2 for correcting the external errors when  is fixed to 0.125. In this case, the noiseless
decoder encounters stopping sets while the noisy decoder is still capable of correcting external errors. Here we see
that the optimal running time occurs when the neurons have a fair amount of internal noise. Figs. 10b and 10a are
projected versions of Figure 9 and show the average number of iterations as a function of υ and ν , respectively.
C. Effect of internal noise on the performance in absence of external noise
Now we provide results of a study for a slightly modified setting where there is only internal noise and no
external errors and further ϕ < υ . Thus, the internal noise can now cause neurons to make wrong decisions, even
in the absence of external errors. With abuse of notation, we assume pattern neurons are corrupted with a ±1 noise
added to them with probability υ . The rest of the model setting is the same as before.
Figure 11 illustrates the effect of internal noise as a function of υ and ν , the noise parameters at the pattern and
constraint nodes, respectively. This behavior is shown in Figs. 12a and 12b for better inspection. Here, we witness
the more familiar phenomenon where increasing the amount of internal noise results in a worse performance. This

Average number of iterations

14

40.00
30.00
20.00
10.00
0.00
0.4
0.2
ν
0 0.5

0.4

0.3

0.2

0.1

0

υ

Fig. 9: The effect of internal noise on the number of iterations performed by Algorithm 2, for different values of
υ and ν with  = 0.125.
finding emphasizes the importance of choosing update threshold ϕ and ψ properly, according to Lemma 1. See
Appendix C for details on choosing thresholds.
V. D ISCUSSION
We have demonstrated that associative memories with exponential capacity still work reliably even when built
from unreliable hardware, addressing a major problem in fault-tolerant computing and further arguing for the
viability of associative memory models for the (noisy) mammalian brain. After all, brain regions modeled as
associative memories, such as the hippocampus and the olfactory cortex, certainly do display internal noise [18],
[21], [46].
The linear-nonlinear computations of Algorithm 1 are nearly identical to message-passing algorithms such as
belief propagation and are certainly biologically plausible [47]–[53]. The state reversion computation of Algorithm 2
requires keeping a state variable for a short amount of time which has been suggested as realistic for biological
neurons [54], but the general biological plausibility of Algorithm 2 remains an open question.
We found a threshold phenomenon for reliable operation, which manifests the tradeoff between the amount of
internal noise and the amount of external noise that the system can handle. In fact, we showed that internal noise
actually improves the performance of the network in dealing with external errors, up to some optimal value. This
is a manifestation of the stochastic facilitation [21] or noise enhancement [23] phenomenon that has been observed
in other neuronal and signal processing systems, providing a functional benefit to variability in the operation of
neural systems.
The associative memory design developed herein uses thresholding operations in the message-passing algorithm
for recall; as part of our investigation, we optimized these neural firing thresholds based on the statistics of the
internal noise. As noted by Sarpeshkar in describing the properties of analog and digital computing circuits, “In
a cascade of analog stages, noise starts to accumulate. Thus, complex systems with many stages are difficult to
build. [In digital systems] Round-off error does not accumulate significantly for many computations. Thus, complex
systems with many stages are easy to build” [55]. One key to our result is capturing this benefit of digital processing
(thresholding to prevent the build up of errors due to internal noise) as well as a modular architecture which allows
us to correct a linear number of external errors (in terms of the pattern length).

15

Average number of iterations

40
υ
υ
υ
υ

30
20

=0
= 0.1
= 0.2
= 0.3

10
0
0

0.1

0.2

ν

0.3

0.4

(a) Effect of internal noise at constraint neurons side.
Average number of iterations

40
ν
ν
ν
ν

30

=0
= 0.2
= 0.3
= 0.5

20
10
0
0

0.1

0.2

υ

0.3

0.4

(b) Effect of internal noise at pattern neurons side.

Fig. 10: The effect of internal noise on the number of iterations performed by Algorithm 2, for different values of
υ and ν with  = 0.125. The average iteration number of 40 indicate the failure of Algorithm 2.

This paper focused on recall, however learning is the other critical stage of associative memory operation. Indeed,
information storage in nervous systems is said to be subject to storage (or learning) noise, in situ noise, and retrieval
(or recall) noise [17, Figure 1]. It should be noted, however, there is no essential loss by combining learning noise
and in situ noise into what we have called external error herein, cf. [43, Fn. 1 and Prop. 1]. Thus our basic qualitative
result extends to the setting where the learning and stored phases are also performed with noisy hardware.
Going forward, it is of interest to investigate other neural information processing models that explicitly incorporate
internal noise and see whether they provide insight into observed empirical phenomena. As an example, we might
be able to explain the threshold phenomenon observed in the symbol error rate of human telegraph operators under
heat stress [56, Figure 2], by invoking a thermal internal noise explanation. Returning to engineering, internal noise
in decoders for limited-length error-correcting codes may improve performance as observed herein, since stopping
sets are a limiting phenomenon in that setting also.
ACKNOWLEDGMENT
We thank S. S. Venkatesh for telling us about [15].
A PPENDIX A
I LLUSTRATING P ROOF OF T HEOREM 2
e in our empirical studies. In the figure,
Figure 13a illustrates an example of a stopping set over the graph G
only the nodes corrupted with external noise are shown for clarity. Pattern neurons that are connected to at least
one cluster with a single error are colored blue and other pattern neurons are colored red. Figure 13b illustrates
the same network but after a number of decoding iterations that result in the algorithm getting stuck. We have a

16

Final PER

0.20

0.10

0.00
0

0.2
2 · 10−2
4 · 10−2
6 · 10−2
ν
8 · 10−2 0

0.15
0.1
5 · 10−2

υ

Fig. 11: The effect of the internal noise on final Pattern Error Rate (PER) as a function of υ and ν in absence of
external noise.

ν
ν
ν
ν

Final PER

0.20

=0
= 0.051
= 0.153
= 0.204

0.10

0.00
0.00

0.01

0.02

0.03

0.04
υ

0.05

0.06

0.07

0.08

(a) Effect of internal noise at pattern neurons side.

Final PER

0.20
υ=0
υ = 0.063
υ = 0.084

0.10

0.00
0

0.1
ν

0.2

(b) Effect of internal noise at constraint neurons side.

Fig. 12: The effect of the internal noise on final Pattern Error Rate (PER) as a function of υ and ν in absence of
external noise.

17

Constraint neurons

5

4.5

4.5

4

4

3.5

3.5

3

3

2.5

2.5

2

2

1.5

1.5

1

1

0.5

0.5

0

0

200

400

600

800

1000

1200

Constraint neurons

5

1400

1600

1800

2000

0

0

200

400

600

Pattern neurons

800

1000

1200

1400

1600

1800

2000

Pattern neurons

(a) t = 0

(b) t → ∞

Fig. 13: An external noise pattern that contains a stopping set in a noiseless neural circuit. Left figure shows
the original pattern and the right figure illustrates the result of the decoding algorithm after sufficient number of
iterations where the algorithm gets stuck. Blue pattern nodes are those that are connected to at least one cluster
with a single external error. Obviously, the stopping set on the right does not have any blue nodes.

stopping set in which no cluster has a single error and the algorithm cannot proceed further since Pci ' 0 for i > 1
in a noiseless architecture. Thus, the external error cannot get corrected.
As evident from Figure 13, the stopping set is the result of clusters not being able to correct more than one
external error; this is where internal noise might come to the rescue. Interestingly, an “unreliable” neural circuit in
which υ = 0.6 could easily get out of the stopping set shown in Figure 13b and correct all of the external errors.
Because we try several times to correct errors in a cluster (and overall in the network) while making sure that the
algorithm does not introduce new errors itself. Thus, the noise might act in our favor in one of these attempts and
the algorithm might be able to avoid stopping set as depicted in Figure 13.
A PPENDIX B
E STIMATING Pc1 T HEORETICALLY
To bound Pc1 , consider four event probabilities for a cluster:
•

•

(`)

(`)

π0 (resp. P0 ): The probability that a constraint neuron (resp. pattern neuron) in cluster ` makes a wrong
decision due to its internal noise when there is no external noise introduced to cluster `, i.e. kz (`) k0 = 0.
(`)
(`)
π1 (resp. P1 ): The probability that a constraint neuron (resp. pattern neuron) in cluster ` makes a wrong
decision due to its internal noise when one input error (external noise) is introduced, i.e. kz (`) k0 = kz (`) k1 = 1.
(`)

(`)

Notice Pc1 = 1 − P1 .
We derive an upper bound on the probability a constraint node makes a mistake in the presence of one external
error.

Lemma 2. In the presence of a single external error, the probability that a constraint neuron makes a wrong
decision due to its internal noise is given by


ν − (η − ψ)
(`)
,
π1 ≤ max 0,
2ν
where η = mini,j,Wij 6=0 (|Wij |) is the minimum absolute value of the non-zero weights in the neural graph and is
chosen such that η ≥ ψ .7
7
This condition can be enforced during simulations as long as ψ is not too large, which itself is determined by the level of constraint
neuron internal noise, ν, as we must have ψ ≥ ν.

18
(`)

Proof: Without loss of generality, assume it is the first pattern node, x1 , that is corrupted with noise +1.
Now calculate the probability that a constraint node makes a mistake in such circumstances. We only need analyze
(`)
constraint neurons connected to x1 since the situation for other constraint neurons is as when there is no external
(`)
error. For a constraint neuron j connected to x1 , the decision parameter is


(`)
hj = W (`) .(x(`) + z (`) ) + vj
j


(`) (`)
+ vj
= 0 + W .z
j

= wj1 + vj .

We consider two error events:
• A constraint node j makes a mistake and does not send a message at all. The probability of this event is
(1)
denoted by π1 .
• A constraint node j makes a mistake and sends a message with the opposite sign. The probability of this event
(1)
is denoted by π2 .
(1)
We first calculate the probability of π2 . Without loss of generality, assume the wj1 > 0 so that the probability
of an error of type two is as follows (the case for wj1 < 0 is exactly the same):
(1)

π2 = Pr{wji + vj < −ψ}


ν − (ψ + wj1 )
= max 0,
.
2ν

(12)

(1)

However, since ψ > ν and wj1 > 0, then ν − (ψ + wj1 ) < 0 and π2 = 0. Therefore, the constraint neurons
will never send a message that has an opposite sign to what it should have. All that remains is to calculate the
probability they remain silent by mistake.
To this end, we have
(1)

π1 = Pr{|wji + vj | < ψ}


ν + min(ψ − wj1 , ν)
= max 0,
.
2ν

(13)

This can be simplified if we assume that the absolute values of all weights in the network are bigger than a constant
η > ψ . Then, the above equation will simplify to


ν − (η − ψ)
(1)
π1 ≤ max 0,
.
(14)
2ν
Putting the above equations together, we obtain:
π

(1)



ν − (η − ψ)
≤ max 0,
2ν



.

(15)

In the case η − ψ > ν , we could even manage to make this probability equal to zero. However, we will leave it
(`)
as is and use (15) to calculate P1 .
(`)

A. Calculating P1

(`)

We start by calculating the probability that a non-corrupted pattern node xj makes a mistake, which is to change
(`)

(`)

(`)

its state in round 1. Let us denote this probability by q1 . Now to calculate q1 assume xj
(`)
x1 ,

has degree dj and it

has b common neighbors with
the corrupted pattern node.
Out of these b common neighbors, bc will send ±1 messages and the others will, mistakenly, send nothing. Thus,
(`)
the decision making parameter of pattern node j , gj , will be bounded by

sign(W (`) )> · y (`) j
bc
(`)
+ uj . ≤
+ uj .
gj =
dj
dj

19

We denote sign(W (`) )> · y (`)


j

by oj for brevity from this point on.
(`)

In this circumstance, a mistake happens when |gj | ≥ ϕ. Thus
(`)

(`)

q1 = Pr{|gj | ≥ ϕ|deg(aj ) = dj &|N (x1 ) ∩ N (aj )| = a}
oj
oj
= Pr{ + uj ≥ ϕ} + Pr{ + uj ≤ −ϕ},
dj
dj

(16)

where N (ai ) represents the neighborhood of pattern node ai among constraint nodes.
By simplifying (16) we get


+1,
if |oj | ≥ (υ + ϕ)dj



max(0, υ−ϕ ), if |o | ≤ |υ − ϕ|d
j
j
(`)
q1 (oj ) = υ−(ϕ−oj /dυj )

,
if |oj − ϕdj | ≤ υdj

2υ


 υ−(ϕ+oj /dj ) ,
if |oj + ϕdj | ≤ υdj .
2υ
We now average this equation over oj , bc , b and dj . To start, suppose that out of the bc non-zero messages
node aj receives, e of them have the same sign as the link they are being transmitted over. Thus, we will have
oj = e − (bc − e) = 2e − bc . Assuming the probability of having the same sign for each message is 1/2, the
 b
probability of having e equal signs out of bc elements will be bec 21 c . Thus, we will get
(`)
q̄1

=

bc    bc
X
bc
1

2

e

e=0

(`)

q1 (2e − bc ).

(17)

Now note that the probability of having a − bc mistakes from the constraint side is given by

(`)

π1 )bc . With some abuse of notations we get:
(`)
q̄1

=

b  
X
b
bc =0

bc

(`)
(π1 )b−bc (1

−

(`)
π1 )bc

bc    bc
X
bc
1
e=0

e

2

(`)

q1 (2e − bc ).

b
bc



(`)

(π1 )b−bc (1 −

(18)


Finally, the probability that aj and x1 have b common neighbors can be approximated by dbj (1−d¯(`) /m` )dj −b (d¯(`) /m` )b ,
where d¯(`) is the average degree of pattern nodes. Thus (again abusing some notation), we obtain:
(`)
q̄1

=

dj
X
b=0

pb

b
X
bc =0

pbc

bc    bc
X
bc
1
e=0

e

2

(`)

q1 (2e − bc ),

(19)

(`)

where
q1 (2e − bc ) is given by (16), pb is the probability of having b common neighbors and is estimated by
dj 
(1
−
d¯(`) /m` )dj −b (d¯(`) /m` )b , with d¯(`) being the average degree of pattern nodes in cluster `. Furthermore, pbc
b
 (`)
(`)
is the probability of having b − bc out of these b nodes making mistakes. Hence, pbc = bbc (π1 )b−bc (1 − π1 )bc .
We will not simplify the above equation any further and use it as it is in our numerical analysis in order to obtain
the best parameter ϕ.
Now we turn our attention to the probability that the corrupted node, x1 , makes a mistake, which is either not
to update at all or update itself in the wrong direction. Recalling that we have assume the external noise term in
x1 to be a +1 noise, the wrong direction would be for node x1 to increase its current value instead of decreasing
it. Furthermore, we assume that out of d1 neighbors of x1 , some j of them have made a mistake and will not send
(`)
any messages to x1 . Thus, the decision parameter of x1 , will be g1 = u + (d1 − j)/d1 . Denoting the probability
(`)
of making a mistake at x1 by q2 we get:
(`)

(`)

q2 = Pr{g1 ≤ ϕ|deg(x1 ) = d1 and j errors in constraints}


d1 − j
+u<ϕ ,
= Pr
d1

(20)

20

1.00
υ
υ
υ
υ

0.80

= 0.1
= 0.2
= 0.4
= 0.95

P1

(ℓ)

0.60

0.40

0.20

0.00
0.00

0.20

0.40

0.60

ϕ

0.80

1.00

Fig. 14: The behavior of Pc1 as a function of ϕ for different values of noise parameter, υ . Here, π(1) = 0.01.
which simplifies to



+1,
(`)
q2 (j) = max(0, υ−ϕ
υ ),

 υ+ϕ−(d1 −j)/d1

if |j| ≥ (1 + υ − ϕ)d1
if |j| ≤ (1 − υ − ϕ)d1
, if |ϕd1 − (d1 − j)| ≤ υd1 .
2υ
 (`)
(`)
Noting that the probability of making j mistakes on the constraint side is dj1 (π1 )j (1 − π1 )d1 −j , we get
(`)
q̄2

=

d1  
X
d1
j=0

j

(`)

(`)

(`)

(π1 )j (1 − π1 )d1 −j q2 (j),

(21)

(22)

(`)

where q2 (j) is given by (21).
Putting the above results together, the overall probability of making a mistake on the side of pattern neurons
when we have one bit of external noise is
1 (`) n(`) − 1 (`)
q̄ +
q̄ .
(23)
n(`) 2
n(`) 1
Finally, the probability that cluster ` could correct one error is that all neurons take the correct decision, i.e.
(`)

P1 =

(`)

(`)

Pc(`)
= (1 − P1 )n
1

and the average probability that clusters could correct one error is simply
Pc1 = E` (Pc(`)
).
1

(24)

We use this equation in order to find the best update threshold ϕ.
A PPENDIX C
C HOOSING PROPER ϕ
We now apply numerical methods to (23) to find the best ϕ for different values of noise parameter υ . The
following figures show the best choice for the parameter ϕ. The update threshold on the constraint side is chosen
(`)
such that ψ > ν . In each figure, we have illustrated the final probability of making a mistake, P1 , for comparison.
Figure 14 illustrates the behavior of the average probability of correcting a single error, Pc1 , as a function of ϕ
for different values of υ and for π1 = 0.01. The interesting trend here is that in all cases, ϕ∗ , the update threshold

21

ϕ∗

0.90

0.80

0.70
0.00

0.20

0.40

υ

0.60

0.80

1.00

Fig. 15: The behavior of ϕ∗ as a function of υ for π1 = 0.01.
1.00

P1

(ℓ)

π1 = 0
π1 = 0.01
π1 = 0.1
0.50

0.00
0.00

0.50
υ

1.00

Fig. 16: The optimum Pe1 as a function of υ for different values π1 .
that gives the best result, is chosen such that it is quite large. This actually is in line with our expectation because a
small ϕ will result in non-corrupted nodes to update their states more frequently. On the other hand, a very large ϕ
will prevent the corrupted nodes to correct their states, especially if there are some mistakes made on the constraint
(`)
side, i.e., π1 > 0. Therefore, since we have much more non-corrupted nodes than corrupted nodes, it is best to
(`)
choose a rather high ϕ but not too high. Please also note that when π1 is very high, there are no values of υ for
which error-free storage is possible.
Figure 15 illustrates the exact behavior of ϕ∗ against υ for the case where φ1 = 0. As can be seen from the
figure, ϕ should be quite large.
Figure 16 illustrates Pe1 = 1 − Pc1 for the best chosen threshold, ϕ∗ , as a function of υ for various choices of
π1 .
R EFERENCES
[1] A. Karbasi, A. H. Salavati, A. Shokrollahi, and L. R. Varshney, “Noise-enhanced associative memories,” in Advances in Neural
Information Processing Systems 26, C. J. C. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K. Q. Weinberger, Eds. Cambridge,
MA: MIT Press, 2013, pp. 1682–1690.
[2] A. Treves and E. T. Rolls, “Computational analysis of the role of the hippocampus in memory,” Hippocampus, vol. 4, no. 3, pp.
374–391, Jun. 1994.
[3] D. D. Stettler and R. Axel, “Representations of odor in the piriform cortex,” Neuron, vol. 63, no. 6, pp. 854–864, Sep. 2009.
[4] D. A. Wilson and R. M. Sullivan, “Cortical processing of odor objects,” Neuron, vol. 72, no. 4, pp. 506–519, Nov. 2011.
[5] J. J. Hopfield, “Neural networks and physical systems with emergent collective computational abilities,” Proc. Natl. Acad. Sci. U.S.A.,
vol. 79, no. 8, pp. 2554–2558, Apr. 1982.
[6] R. J. McEliece, E. C. Posner, E. R. Rodemich, and S. S. Venkatesh, “The capacity of the Hopfield associative memory,” IEEE Trans.
Inf. Theory, vol. IT-33, no. 4, pp. 461–482, 1987.
[7] D. J. Amit and S. Fusi, “Learning in neural networks with material synapses,” Neural Comput., vol. 6, no. 5, pp. 957–982, Sep. 1994.

22

[8]
[9]
[10]
[11]
[12]
[13]
[14]
[15]
[16]
[17]
[18]
[19]
[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]
[31]
[32]
[33]
[34]
[35]
[36]
[37]
[38]
[39]
[40]
[41]
[42]
[43]
[44]

G. Palm, “On associative memory,” Biol. Cybern., vol. 36, no. 1, pp. 19–31, Feb. 1980.
C. E. Shannon, “A mathematical theory of communication,” Bell Syst. Tech. J., vol. 27, pp. 379–423, 623–656, July/Oct. 1948.
B. A. Olshausen and D. J. Field, “Sparse coding of sensory inputs,” Curr. Opin. Neurobiol., vol. 14, no. 4, pp. 481–487, Aug. 2004.
A. A. Koulakov and D. Rinberg, “Sparse incomplete representations: A potential role of olfactory granule cells,” Neuron, vol. 72, no. 1,
pp. 124–136, Oct. 2011.
T. Richardson and R. Urbanke, Modern Coding Theory. Cambridge: Cambridge University Press, 2008.
A. H. Salavati and A. Karbasi, “Multi-level error-resilient neural networks,” in Proc. 2012 IEEE Int. Symp. Inf. Theory, Jul. 2012, pp.
1064–1068.
A. Karbasi, A. H. Salavati, and A. Shokrollahi, “Iterative learning and denoising in convolutional neural associative memories,” in
Proc. 30th Int. Conf. Mach. Learn. (ICML 2013), Jun. 2013, to appear.
S. Biswas, “A performance analysis of sparse neural associative memory,” Ph.D. dissertation, University of Pennsylvania, 1993.
N. Brunel, V. Hakim, P. Isope, J.-P. Nadal, and B. Barbour, “Optimal information storage and the distribution of synaptic weights:
Perceptron versus Purkinje cell,” Neuron, vol. 43, no. 5, pp. 745–757, 2004.
L. R. Varshney, P. J. Sjöström, and D. B. Chklovskii, “Optimal information storage in noisy synapses under resource constraints,”
Neuron, vol. 52, no. 3, pp. 409–423, Nov. 2006.
C. Koch, Biophysics of Computation: Information Processing in Single Neurons. New York: Oxford University Press, 1999.
A. A. Faisal, L. P. J. Selen, and D. M. Wolpert, “Noise in the nervous system,” Nat. Rev. Neurosci., vol. 9, no. 4, pp. 292–303, Apr.
2008.
E. T. Rolls and G. Deco, The Noisy Brain: Stochastic Dynamics as a Principle of Brain Function. Oxford University Press, 2010.
M. D. McDonnell and L. M. Ward, “The benefits of noise in neural systems: bridging theory and experiment,” Nat. Rev. Neurosci.,
vol. 12, no. 7, pp. 415–426, Jul. 2011.
A. Destexhe and M. Rudolph-Lilith, Neuronal Noise. New York: Springer, 2012.
H. Chen, P. K. Varshney, S. M. Kay, and J. H. Michels, “Theory of the stochastic resonance effect in signal detection: Part I–fixed
detectors,” IEEE Trans. Signal Process., vol. 55, no. 7, pp. 3172–3184, Jul. 2007.
D. A. Spielman and S.-H. Teng, “Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time,” J.
ACM, vol. 51, no. 3, pp. 385–463, May 2004.
D. O. Hebb, The Organization of Behavior: A Neuropsychological Theory. New York: Wiley, 1949.
S. Jankowski, A. Lozowski, and J. M. Zurada, “Complex-valued multistate neural associative memory,” IEEE Trans. Neural Netw.,
vol. 7, no. 6, pp. 1491–1496, Nov. 1996.
M. K. Müezzinoǧlu, C. Güzeliş, and J. M. Zurada, “A new design method for the complex-valued multistate Hopfield associative
memory,” IEEE Trans. Neural Netw., vol. 14, no. 4, pp. 891–899, Jul. 2003.
D.-L. Lee, “Improvements of complex-valued Hopfield associative memory by using generalized projection rules,” IEEE Trans. Neural
Netw., vol. 17, no. 5, pp. 1341–1347, Sep. 2006.
V. Gripon and C. Berrou, “Sparse neural networks with large learning diversity,” IEEE Trans. Neural Netw., vol. 22, no. 7, pp.
1087–1096, Jul. 2011.
S. S. Venkatesh, “Connectivity versus capacity in the Hebb rule,” in Theoretical Advances in Neural Computation and Learning,
V. Roychowdhury, K.-Y. Siu, and A. Orlitsky, Eds. Kluwer Academic Publishers, 1994, pp. 173–240.
Y. Baram, “Encoding unique global minima in nested neural networks,” IEEE Trans. Inf. Theory, vol. 37, no. 4, pp. 1158–1162, Jul.
1991.
P. Peretto and J. J. Niez, “Long term memory storage capacity of multiconnected neural networks,” Biol. Cybern., vol. 54, no. 1, pp.
53–63, May 1986.
L. Xu, A. Krzyzak, and E. Oja, “Neural nets for dual subspace pattern recognition method,” Int. J. Neur. Syst., vol. 2, no. 3, pp.
169–184, 1991.
E. J. Candés and T. Tao, “Near-optimal signal recovery from random projections: Universal encoding strategies?” IEEE Trans. Inf.
Theory, vol. 52, no. 12, pp. 5406–5425, Dec. 2006.
A. K. Fletcher, S. Rangan, L. R. Varshney, and A. Bhargava, “Neural reconstruction with approximate message passing (NeuRAMP),”
in Advances in Neural Information Processing Systems 24, J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Weinberger, Eds.
Cambridge, MA: MIT Press, 2011, pp. 2555–2563.
P. Vincent, H. Larochelle, Y. Bengio, and P.-A. Manzagol, “Extracting and composing robust features with denoising autoencoders,”
in Proc. 25th Int. Conf. Mach. Learn. (ICML 2008), Jul. 2008, pp. 1096–1103.
Q. V. Le, J. Ngiam, Z. Chen, D. Chia, P. W. Koh, and A. Y. Ng, “Tiled convolutional neural networks,” in Advances in Neural
Information Processing Systems 23, J. Lafferty, C. K. I. Williams, J. Shawe-Taylor, R. S. Zemel, and A. Culotta, Eds. Cambridge,
MA: MIT Press, 2010, pp. 1279–1287.
S. Song, P. J. Sjöström, M. Reigl, S. Nelson, and D. B. Chklovskii, “Highly nonrandom features of synaptic connectivity in local
cortical circuits,” PLoS Biol., vol. 3, no. 3, pp. 0507–0519, Mar. 2005.
D. J. Amit, Modeling Brain Function. Cambridge: Cambridge University Press, 1992.
H. Liljenström and X.-B. Wu, “Noise-enhanced performance in a cortical associative memory model,” Int. J. Neur. Syst., vol. 6, no. 1,
pp. 19–29, Mar. 1995.
M. G. Taylor, “Reliable information storage in memories designed from unreliable components,” Bell Syst. Tech. J., vol. 47, no. 10,
pp. 2299–2337, Dec. 1968.
A. V. Kuznetsov, “Information storage in a memory assembled from unreliable components,” Probl. Inf. Transm., vol. 9, no. 3, pp.
100–114, July-Sept. 1973.
L. R. Varshney, “Performance of LDPC codes under faulty iterative decoding,” IEEE Trans. Inf. Theory, vol. 57, no. 7, pp. 4427–4444,
Jul. 2011.
M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi, and D. A. Spielman, “Efficient erasure correcting codes,” IEEE Trans. Inf. Theory,
vol. 47, no. 2, pp. 569–584, Feb. 2001.

23

[45] S. M. S. Tabatabaei Yazdi, H. Cho, and L. Dolecek, “Gallager B decoder on noisy hardware,” IEEE Trans. Commun., vol. 61, no. 5,
pp. 1660–1673, May 2013.
[46] M. Yoshida, H. Hayashi, K. Tateno, and S. Ishizuka, “Stochastic resonance in the hippocampal CA3–CA1 model: a possible memory
recall mechanism,” Neural Netw., vol. 15, no. 10, pp. 1171–1183, Dec. 2002.
[47] J. M. Beck and A. Pouget, “Exact inferences in a neural implementation of a hidden Markov model,” Neural Comput., vol. 19, no. 5,
pp. 1344–1361, May 2007.
[48] P. Dayan, G. E. Hinton, R. M. Neal, and R. S. Zemel, “The Helmholtz machine,” Neural Comput., vol. 7, no. 5, pp. 889–904, Sep.
1995.
[49] S. Deneve, “Bayesian spiking neurons I: Inference,” Neural Comput., vol. 20, no. 1, pp. 91–117, Jan. 2008.
[50] K. Doya, S. Ishii, A. Pouget, and R. P. N. Rao, Bayesian Brain: Probabilistic Approaches to Neural Coding. Cambridge, MA: MIT
Press, 2007.
[51] G. E. Hinton and T. J. Sejnowski, “Learning and relearning in Boltzmann machines,” in Parallel Distributed Processing: Explorations
in the Microfoundations of Cognition, Volume 1: Foundations, D. E. Rumelhart and J. L. McLelland, Eds. Cambridge, MA: MIT
Press, 1986, pp. 282–317.
[52] W. J. Ma, J. M. Beck, P. E. Latham, and A. Pouget, “Bayesian inference with probabilistic population codes,” Nat. Neurosci., vol. 9,
no. 11, pp. 1432–1438, Nov. 2006.
[53] S. Litvak and S. Ullman, “Cortical circuitry implementing graphical models,” Neural Comput., vol. 21, no. 11, pp. 3010–3056, Nov.
2009.
[54] S. Druckmann and D. B. Chklovskii, “Neuronal circuits underlying persistent representations despite time varying activity,” Curr. Biol.,
vol. 22, no. 22, pp. 2095–2103, Oct. 2012.
[55] R. Sarpeshkar, “Analog versus digital: Extrapolating from electronics to neurobiology,” Neural Comput., vol. 10, no. 7, pp. 1601–1638,
Oct. 1998.
[56] N. H. Mackworth, “Effects of heat on wireless telegraphy operators hearing and recording Morse messages,” Br. J. Ind. Med., vol. 3,
no. 3, pp. 143–158, Jul. 1946.

