Stable Memory Allocation in the Hippocampus:
Fundamental Limits and Neural Realization
Wenlong Mou∗

Zhi Wang†

Liwei Wang‡

arXiv:1612.04659v1 [cs.NE] 14 Dec 2016

December 15, 2016

Abstract
It is believed that hippocampus functions as a memory allocator in brain, the mechanism of
which remains unrevealed. In Valiant’s neuroidal model [19], the hippocampus was described as
a randomly connected graph, the computation on which maps input to a set of activated neuroids
with stable size. Valiant proposed three requirements for the hippocampal circuit to become
a stable memory allocator (SMA): stability, continuity and orthogonality. The functionality of
SMA in hippocampus is essential in further computation within cortex, according to Valiant’s
model.
In this paper, we put these requirements for memorization functions into rigorous mathematical formulation and introduce the concept of capacity, based on the probability of erroneous
allocation. We prove fundamental limits for the capacity and error probability of SMA, in
both data-independent and data-dependent settings. We also establish an example of stable
memory allocator that can be implemented via neuroidal circuits. Both theoretical bounds and
simulation results show that the neural SMA functions well.

1

Introduction

It is well known that the computational speed of human brain is several orders of magnitude slower
than that of current computer, while almost everything human can do easily are still beyond the
capability of the most powerful computers. Thus, the investigation into computational mechanisms
of human brains leads a promising direction for theoretical aspect of computation, machine learning
and neuroscience. In particular, the formation of memory, during which the neural circuit creates
a representation for an object, was not fully understood, though it has been observed that the
hippocampus plays a significant role in this process.
A research line developed by Valiant [15, 16, 18, 20] focused on the connectivity structure
of neuroids, i.e., the computational abstraction of neurons, on which local computation can be
performed. This formal and conservative model assumes the brain to be a randomly connected
graph of neuroids. Each of them can be either active or inactive, depending on the states of
neighbors that have a directed edge to it. Biological constraints are also taken into consideration,
such as weak synaptic connections and sparsity of graphs. With biological evidences, this model
captures the capability of realistic neurons. Specific supervised and unsupervised learning tasks
such as inductive learning, rational expressions, and reasoning are viable in this model, using the
vicinal algorithms [17, 18, 7]. In Valiant’s model, those complicated processes are based on basic
∗

Key Laboratory of Machine Perception, School of EECS, Peking University. Email: mouwenlong@pku.edu.cn
Key Laboratory of Machine Perception, School of Mathematics, Peking University. Email: zhiwpku@gmail.com
‡
Key Laboratory of Machine Perception, School of EECS, Peking University. Email: wanglw@cis.pku.edu.cn

†

1

operations of JOIN and LIN K. Recently, a new operation called P JOIN , namely, predictive
JOIN , was proposed for unsupervised learning of patterns [14, 13]. All those operations, as well as
experimental evidences from neuroscience, requires the representation for an item to be allocated
with a stable amount of neurons, which is done by hippocampus, before the computation in cortex.
Valiant [19] first discussed the role and computational mechanisms of hippocampus in this
model. The paper stated that the function of hippocampus is to ”identify the set of neurons in
cortex at which a new compound concept or chunk will be represented, and to enable that set of
neurons to take on that role”. The stability of the amount of neurons allocated plays a key role in
Valiant’s neuroidal models in order to control each new chunk within a limited range so as to avoid
the overall system becoming unstable. To guarantee this, three requirements for stable memory
allocators (SMA) was proposed in their paper, namely, stability, continuity and orthogonality.
Valiant pointed out the direction by discussing biological constraints and proposing an example in
his paper, yet rigorous mathematical treatment is still in need. Our systematic analysis of stable
memory allocators is therefore important in the neuroidal model.
Memorization process creates neural representation for arbitrary set of input item, either randomly or through learning from samples. Performance and characteristics of such mapping functions
have been vastly studied in machine learning, theoretical computer science and computational neuroscience. For example, in [1], a sign-consistent sparse JL transform is constructed to explain the
formation of memory, under a different model of neurons. [3] proposed a neuron-friendly random
projection for robust concept learning via dimension reduction. Hopfield networks [8] dynamically
adjust network weights to create memory for new items. Locality sensitive hashing [9] and binary
embeddings [21] randomly maps input vector into a discrete space while preserving locality. Our
work relates to them in terms of compression of information and preservation of locality.
In this paper, we first manage to put Valiant’s idea into a rigorous mathematical formulation. We give basic theoretical results and a simple construction in Section 2. By introducing
concepts of error probability and capacity into our formulation, we are able to better characterize
the fundamental possibilities and impossibilities of memory allocation. Their theoretical bounds
are discussed under both data-dependent and data-independent settings; see Section 3. While the
network designed by Valiant works in special cases [19], it could not be generalized to the scale of
real hippocampus. That’s why we propose, in Section 4, a feed-forward neural network model to realize stable memory allocation in hippocampus, and at the same time consistent with the biological
constraints. In contrast to subtractive models [19], the inhibition patterns of neurons are divisive
in our design. We show that this stable memory allocator can better achieves the requirements
with reasonable capacity.

2

Formulation of SMA

In this section, we will first refine the requirements for the stable memory allocation task [19], and
put it into mathematical formulations.

2.1

Basic requirements and motivation

As proposed in [19], a valid stable memory allocator (SMA) for the cortex should subject to three
basic requirements: stability, continuity and orthogonality. In the following we present high-level
ideas in the formulation of SMA, and discuss basic requirements for a stable memory allocator to
function well in Valiant’s model.
• Stability: The mapping is stable in that for inputs within a wide range of activity levels,
2

the output will have activity level differing little. This condition is fundamental in vicinal
algorithms in the cortex, and also reasonable in neural representation of abstract concepts.
• Continuity: A noise in the input pattern should not cause huge variations in the output.
Continuity can provide neural systems with robustness (error-correcting) and help to realize
pattern recognition functions (nearest-neighbor search).
• Orthogonality: With this property, distinct items will not be confused. Pairs of inputs that
differ by much will be mapped to outputs that also differ sufficiently, so that they can be
treated by cortex as distinct. We weaken the orthogonality requirement in [19] and broaden
the class of stable memory allocators, yet the biological functionality can still be guaranteed.
The randomness of mapping function plays an essential role in a stable memory allocator, since
any data-independent deterministic allocation function will fail upon adversarial inputs: Suppose
we have a fixed SMA which maps vectors in {0, 1}n to a stable number of activated neurons. By
pigeon-hole principle there must be 2Ω(n) vectors mapped to the same set of neurons. Among those
colliding inputs, there must be a pair of vectors with Hamming distance Ω(n), which leads to the
failure of orthogonality. On the contrary, a randomized SMA, like random projections, can fulfill
these requirements for arbitrary input set of bounded size, with high probability. This observation
is important and triggers the concept of error probability in our framework. We can thereby define
the concept of capacity as the maximal number of objects that a stable memory allocator can
handle with low error probability. In other words, the capacity of stable memory allocator stands
for the number of items one can memorize without being confused.

2.2

Mathematical formulation

In our framework, SMA is formulated as a series of distributions with respect to size n over function
space. Although the growth of synapses is quite random, there are some underlying rules that govern
the formation of random graph so that almost everyone can allocate memory for new incoming
items without any difficulty, no matter the difference of inner connections for each individual.
We therefore demand the three properties here to hold uniformly with high probability, which
guarantees more robustness than the model based on expected value [19]. It is also worth noticing
that we do not make any assumptions on the structure or distribution of input vectors.
Definition 1. A series of distributions {Hn } over function space {0, 1}n → {0, 1}n is called a
stable memory allocator (SMA) with parameter hδ, µ, κ, An , Bn , rn i and capacity Kn , if ∀ε > 0,
∃N ∈ N s.t. ∀n > N ∀Sn ⊂ {0, 1}n \ {x||x| ≤ κn} , |Sn | ≤ Kn , the following three properties hold
P r {∀x ∈ Sn , |h(x)| ∈ ((1 − δ)rn , (1 + δ)rn )} > 1 − ε

h∼Hn

P r {∀x ∈ Sn , y ∈ {0, 1}n , dH (h(x), h(y)) ≤ µdH (x, y)} > 1 − ε

h∼Hn

(1)

P r {∀x, y ∈ Sn , dH (x, y) > An , dH (h(x), h(y)) > Bn } > 1 − ε

h∼Hn

It is natural to assume ∀x, y ∈ Sn , dH (x, y) > An according to our interpretation of orthogonality. There are some requirements for parameters of SMA: as the output vector is stably sparse,
the number of activated neurons in the output rn should satisfy rn /n  1. Also, An and Bn
should increase with respect to size n and one typical assumption is that they grow linearly:
An = an, Bn = brn . Notice that a is also a small number compared to 1, otherwise only few items
are considered ”truly different” and orthogonality would fail.
3

Not all SMAs have good performance. When judging a SMA, we should first consider those
parameters that define it: smaller Lipschitz factor µ in the continuity requirement means better
preservation of input information and stronger error-correcting functions. SMA with larger Bn
and smaller An can distinguish items better. The parameter κ represents the lowest input density
required. The following discussion, without pointing out explicitly, regards elements in Sn as not too
sparse (with density larger than κ) for all the Sn mentioned. A small δ stands for good performance
in stability. The extreme case is that δ = 0, which is a strong version that realize stability precisely:
Strong stability
Pr

h∼Hn
(rn )

where Tn

n
o
∀x ∈ Sn , h(x) ∈ Tn(rn ) > 1 − ε


, x ∈ {0, 1}n |x| = rn

(2)

and we call a specific allocator function h(x) strong
(rn )

stable with respect to input set Sn if ∀x ∈ Sn , h(x) ∈ Tn

.

An SMA that satisfies the strong stability defined above is called a strong SMA.

2.3

Relating error probability to capacity

The key issue involved within capacity is error probability. The more items are there to be allocated,
the more conflicts are likely to be happen in the outputs. Thus, one target of designing SMA is to
maximize its capacity, i.e. to avoid the possible conflicts.
Theorem 1 reveals the relationship between pairwise error probability and capacity, in order to
fulfill the requirements uniformly with high probability. In the design and analysis of SMA, this
theorem serves as a useful tool to guarantee capacity.
Theorem 1. If a series of distributions {Hn } over function space {0, 1}n → {0, 1}n satisfies the
following properties:
• For ∀x ∈ {0, 1}n fixed ,with probability at least 1 − εn :
|h(x)| ∈ ((1 − δ)rn , (1 + δ)rn )

(3)

• For ∀x ∈ {0, 1}n fixed, with probability at least 1 − εn :
∀y ∈ {0, 1}n , dH (h(x), h(y)) ≤ µdH (x, y)

(4)

• For ∀x, y ∈ {0, 1}n fixed, dH (x, y) > An , we have:
P r {dH (h(x), h(y)) > Bn } > 1 − εn

h∼Hn

(5)

where lim εn = 0. Then {Hn } is a strong SMA with parameters hµ, An , Bn , rn i and capacity at
least

n→0
o(1)
√ , as
εn

n goes to infinity.

The proof of this theorem estimates the overall error probability for a given set of items via
union bound, the technical detail of which is deferred to the Appendix.

4

2.4

A simple example for SMA

The following simple construction serves as a proof for the existence of SMA. The basic idea is that
we first randomly select 2rn bits from the input item, then flip each of these bits with probability
1
2.
Suppose that {i1 , i2 , · · · , i2rn } is uniformly distributed on all the 2rn -sized subsets of {1, 2, · · · , n},

i.i.d.
and that b1 , b2 , · · · , b2rn ∼ B 1, 21 . We define h(x) along with its distribution Hn as follows, with
operation ⊕ denoting the modulo 2 addition.

bj ⊕ xk
k = ij
h(x)k =
(6)
0
otherwise
We argue that ∀a, p, δ ∈ (0, 1), the construction above is an SMA with parameter hδ, 0, 1, An =
2 2
a · n, (1 − δ)pAn , rn = p · ni and capacity at least o(1)e2pa δ n , according to Theorem 1.
Apparently, the flips would not change Hamming
 distance and naturally meet the requirement
of continuity. As ∀x ∈ {0, 1}n ,|h(x)| ∼ B 2rn , 21 , we know stability by using Chernoff bound.
For orthogonality, let d = dH (x, y). According to Chvátal’s estimation on tail probability of

d 2 2
hypergeometric distribution [4], we have P rh∼Hn dH (h(x), h(y)) ≤ (1 − δ) 2rnn d ≤ e−4rn ( n ) δ
However, this example is still far from actual memorization mechanisms, since it could not be
fit into a biologically plausible neural realization.

3

Theoretical analysis

In this section, we will consider the theoretical bounds for capacity and error probability of SMA,
which are two important characteristics to judge its performance other than those parameters that
define it. Lower bound of error probability and upper bound of capacity are first proposed. We also
consider a different scheme where the memory allocator can be learned from input, and establish
upper and lower bounds for the capacity.

3.1

Lower bound of pairwise error probability

Lower bounds for pairwise error probability is important, since it indicates what capacity bound
we can get via Theorem 1. In this subsection, we consider a slightly modified scheme, where the
orthogonality condition is strengthened in Lipschitz form, and combined with continuity condition
to constitute a bi-Lipschitz condition on the input set, as in Valiant’s paper [19].
Theorem 2. If {Hn } is a series of distribution over functions that satisfies the following requirements
• ∀h ∈ supp(Hn ),

|h(x)|
rn

∈ (1 − δ, 1 + δ)

• ∀x, y ∈ {0, 1}n fixed, with probability at least 1 − εn :
λdH (x, y) ≤ dH (h(x), h(y)) ≤ µdH (x, y)
then we have the lower bound for error


−( µ−λ )2 1 !
µ+λ
logn
n
εn = Ω 2rn δ
rn (1 + δ)

(7)

(8)

Basically, the theorem states information-theoretic limitations on a random mapping which can
compress {0, 1}n to a much smaller one while preserving distance. The proof is based on reduction
to one-way public-coin randomized communication complexity, which is deferred to Appendix.
5

3.2

Upper bound of capacity

The following theorem gives an upper bound for the capacity when strong stability holds. This
results mainly captures the limitations against achieving orthogonality posed by stability requirement.

Theorem 3. For an SMA with parameters h0, 0, µ, An , Bn , rn i, if max |Sn | ∀x, y ∈ Sn , dH (x, y) >
An ≥ Kn , then the capacity is upper bounded with:




αβ
log Kn ≤ H(α) − αH(β) − (1 − α)H
+ o(1) n
(9)
1−α
where α =

rn
n,

β=

Bn
4rn

and H(·) indicates entropy.

This theorem also discussed information-theoretic limitations on stable memory allocator, from
a different perspective: the output space can only contain a limited number of ”truly different”
objects. The proof uses ”sphere packing” arguments, which is deferred to the Appendix.

3.3

Theretical results for data-dependent allocators

Till now, our discussions are data-independent without exploring whether the memory allocator can
adjust according to data. We focus in this part on the theoretical possibilities for a data-dependent
memory allocator which can learn from items. Though it is impossible for hippocampus to be aware
of all the items to encounter beforehand, our theoretical analysis in data-dependent setting reveals
the possibilities and limits for online learning in memory allocation, where the memory allocator
can adjust its mapping function after seeing each instance. In the following we propose both upper
and lower bounds for the capacity in the data-dependent setting.
The definition of SMA indicates that, for each fixed input set with limited size, there is at
least one allocator h that satisfies the three conditions regardless of the distribution Hn on the
function space. Therefore, ∀Sn , ∃ h dependent on Sn such that ∀x, y ∈ Sn , dH (x, y) > An ⇒
dH (h(x), h(y) ≥ Bn . An equivalent description of Theorem 3 from a data-dependent perspective
is as follows:
If an allocator function is strong stable, then the number of ”truly different” items it can
discriminate would be upper bounded with:



 
αβ
exp
H(α) − αH(β) − (1 − α)H
+ o(1) n
(10)
1−α
Conversely, we consider that for a given set of ”truly different” items Sn , whether an SMA that
guarantees strong stability, orthogonality and uniform Lipschitz continuity exists. The following
theorem guarantees the existence of data-dependent memory allocator with high capacity. We defer
the technical proof to Appendix.
Theorem
4. Given input set Sn ⊂
{0, 1}n that satisfies ∀x, y ∈ Sn , dH (x, y) > An . If log |Sn | ≤

αβ
1
n, then there exists a function hn : {0, 1}n → {0, 1}n such
2 H(α) − αH(β) − (1 − α)H 1−α
that
∀x ∈ Sn , h(x) ∈ Tn(rn ) ; ∀x, y ∈ Sn , dH (hn (x), hn (y)) > Bn ;
8rn
∀x ∈ Sn , ∀y ∈ {0, 1}n , dH (hn (x), hn (y)) ≤
dH (x, y)
An
where rn = |Sn |, α =

rn
n,

β=

Bn
2rn

and H(·) is the entropy.
6

(11)

Notice that the number of input items in Theorem 4 is approximately the square root of the
upper bound indicated by Theorem 3. The lower bound is strong in this sense.

4

A feedforward neural network for SMA

In this section, we propose a feedforward neural network model that realizes SMA functionality.
Compared with Valiant’s previous neural circuits [19], not only does our construction achieve better
performance of SMA, with capacity guarantees, but also it is biologically more reasonable, in terms
of number of synapse connected to a neuron and their strengths.

4.1

Biologically reasonable assumptions

We adopt the randomly-connected feed-forward network architecture and unmodifiable synapse in
Valiant’s paper [19]. Actually, as Valiant has suggested in his paper [19], there are also experimental
evidences supporting this architecture. The information flow within hippocampus appears to be unidirectional, with much less reciprocal connections [2]; it has also been reported that both modifiable
and unmodifiable synapse exists in the hippocampus [5]. As in Valiant’s paper, our theory focuses
on explaining the mechanism of memory allocation component, with conservative assumptions on
neurons, though the overall infrastructure of hippocampus can be much more complicated.
A major difference we made in the design of neural circuit is that, the inhibition patterns of
neurons are divisive, instead of subtractive. Whether the way of inhibition is subtractive or divisive
is an important open question in neuroscience [6, 12]. In divisive inhibition
model, each neuron is
P
activated if and only if the ratio of its total positive
inputs + Wi to the sum of all the
P synapticP
W
)
+
(
synaptic weights that
come
from
input
neurons
(
i
− Wi ) is larger than the threshold
+
P
Wi

value C, i.e. P Wi++P Wi > C. For the purpose of memory allocation, subtractive models [19]
+
−
have to narrow down the range of density in each layer and use contraction mapping theorem for
stability. Divisive inhibition, on the contrary, enables us to control the expected level of activity in
second layer directly, for a wide range of input density.

4.2

Description of the network

Our neural realization is based on a unidirectional three-layer network architecture. For simplicity
we assume each layer has n neurons. Firing neurons in the first layer represents the input vector
x ∈ {0, 1}n , and the output h(x) is taken from the third layer. For k ∈ {1, 2}, the edges from k-th
layer to (k +1)-th layer is randomly and independently connected: each edge exists with probability
2p, and the chances for it to become positive and inhibitive are both p. The threshold value in
divisive inhibition is denoted as C1 and C2 , for second and third layer neurons respectively.

4.3

Proof of SMA functionality

In this subsection, we give proofs on the validity of our construction as a stable memory allocator,
with reasonable parameters and capacity.
We first give the following technical lemmas needed in our analysis. Lemma 1, 2, 3 and 4
described the consequences of passing through one layer in our network model. We defer the proofs
for the lemmas and theorem to Appendix.

7

Lemma 1. For ∀x ∈ {0, 1}n fixed, let β ∈ Rn with all entries i.i.d., P r{βi = 1} = P r{βi = −1} =
p, P r{βi = 0} = 1 − 2p. Then we have:
0≤

1
1
1
+ e−2(2 ln 2−1)p|x|
− P r{β T x > 0} ≤ p
2
2 πp|x| 2

(12)

The following lemma estimates how one-bit difference in the input influence the output.
Lemma 2. For ∀x, y ∈ {0, 1}n fixed, with dH (x, y) = 1, let β ∈ Rn with all entries i.i.d., P r{βi =
1} = P r{βi = −1} = p, P r{βi = 0} = 1 − 2p. For ∀v ∈ {0, 1}n , let g(v) = I[β T v] > 0. Then we
have:
r
p
P r {g(x) 6= g(y)} ≤ 2
+ 2pe−2(2 ln 2−1)p|x|
(13)
π|x|
For a more general case, we cannot write the probability of changed bits in closed form, while
its asymptotic behavior can be estimated using central limit theorem, as stated in the following
two lemmas.
Lemma 3. For ∀x, y ∈ {0, 1}n fixed, with dH (x, y) = L, let β ∈ Rn with all entries i.i.d.,
P r{βi = 1} = P r{βi = −1} = p, P r{βi = 0} = 1 − 2p. For ∀v ∈ {0, 1}n , let g(v) = I[β T v] > 0.
Then we have:
1
|x ∩ y|
P r {g(x) 6= g(y)} ≈ cos−1 p
(14)
π
|x| · |y|
Lemma 4. For n independent and identically distributed pairs {(xi , yi )}ni=1 with P r{xi = 1} =
P r{yi = 1} ≈ 12 and P r{xi 6= yi } = η, we concatenate them and get two random vectors x, y ∈
{0, 1}n . Let β ∈ Rn with all entries i.i.d., P r{βi = 1−c} = P r{βi = −c} = p, P r{βi = 0} = 1−2p.
For ∀v ∈ {0, 1}n , let g(v) = I[β T v] > 0. We have P r{g(x) 6= g(y)} is approximately equal to:
√
Z
2
t
−1 √
(2c − 1)p n
q
ϕ( q
)Φ( √
)dt
(15)
2t − p
η
v(c, p)
1 − 1η R
1 − 1η
2

2

(ϕ(·) and Φ(·) denotes the density and cumulative density function for N (0, 1), respectively)
(v(c, p) = (2c2 − 2c + 1)p − (1 − 2c)2 p2 is variance of βi )
By combining them together, we conclude the functionality of neural stable memory allocator:
Theorem 5. Given rn , An = a·n, s0 , ∀γ ∈ (0, 1), we construct the
neural network with parameters:
q 2
r
1
1
1
s
−1
n
p = nγ , and C1 = 2 , C2 = 2 − 2√2−s2 , where s = Φ
n
np . Let H denote the mapping
function defined by this neural network. There exists a constant b depending solely on a, and
−1

1+γ

µn = Z0 rn s0 4 n− 4 (log n)2 with some absolute constant Z0 , such that ∀x, y, z ∈ {0, 1}n with
|x|, |y|, |z| ≥ s0 n, and dH (x, z) > An ), the following hold if n is large enough:
(



 )
|h(x) − rn |
log(n/rn ) 2
Pr
>  ≤ exp −2n  − √
h∼H
n
s0 n1−γ
(
)
n
o
p
dH (h(x), h(y))
(16)
p
Pr
≥ tµn ≤ exp −(t ln t − (t − 1))µn dH (x, y) . ∀t ≥ 1
h∼H
dH (x, y)
P r {dH (h(x), h(z)) ≤ (b − )rn } ≤ e−2n

h∼H

8

2

Assume rn grows linearly with n → +∞, while , b remains absolutely constant, and t = Θ(nδ )
with small absolute constant δ, the error probabilities in Theorem 5 diminish quasi-exponentially
as n increases. Combined with Theorem 1, we conclude that the neural stable memory allocator
achieves a capacity which is exponential in poly(n). The continuity requirement in this neural
SMA deviates from standard definition: on the one hand, though the Lipschitz factor tµn grows
unboundedly as n → +∞, it is much smaller than rn so that error-correcting functions can still be
performed; on the other hand, the theorem provides morepguarantees than Lipschitz constant, since
the number of different output bits grows linearly with dH (x, y) instead of dH (x, y), making it
more robust for input errors of more than constant bits.

4.4

Simulation results

In this subsection, we verify the theoretical guarantees via simulating the neural network. Numerical
results show that, the neural stable memory allocator is consistent with theoretical predictions, and
thus functions well as an SMA.
We construct three-layer network as described in this section. Guided by Theorem 5, parameters
are set as follows:
n = 105 , p = 2.5 × 10−3 , C1 = 0.5, C2 = 0.57

0.485

Expansion Rate

Layer 2

0.025

0.475
0.020

Layer 3 (output)

0.480

0.015

0.470

1
3
10
30
100

0

0.010

5

0.465

dH(x, y)

10 15 20 25 30 35 40 45 50

Layer 2
Layer 3

0.030

0.035

To illustrate the stability of allocated neurons, we observe the proportion of activated neurons in
second and third layer for input density ranging from 0.05 to 0.5, as plotted in Figure 1.a. The
density of firing neurons is restricted in (0.46, 0.49) in the second layer, and further narrowed down
in range (0.014, 0.017) in the third layer. By adjusting C2 we can also control the density in output
layer arbitrarily.

0.1

0.2

0.3

0.4

0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5

0.5

Input Density

Layer 1 (input)

(a) Stability

(b) Expansion rates

Figure 1: Stability and expansion rate of the neural SMA
Figure 1.b shows the relationship between expansion rate dH (h(x),h(y))
and the proportion of
dH (x,y)
activated input neurons, which demonstrates continuity and orthogonality properties of our memory allocator. The values shown in the figure is by taking average from 10 randomly chosen inputs.
Different curves stand for the behaviors of expansion rate for dH (x, y) = 1, 3, 10, 30, 100, respectively. As the figure shows, difference in inputs for a few bits will not cause the large Hamming
9

distance between outputs, which verifies continuity. On the other hand, the expansion rate is lower
bounded with some positive constant, which illustrates orthogonality. It is also worth noticing
that expansion rate decreases as dH (x, y) increases, which is consistence with continuity result in
Theorem 5. Therefore, our experimental results verify the validity of Theorem 5, and demonstrate
the performance of our construction as a stable memory allocator.

5

Conclusion and open questions

In this paper we give definitions, fundamental limits and a neural realization for stable memory
allocation in the hippocampus, under Valiant’s neuroidal framework. We first push ahead rigorous
formulations from the three properties of SMA that Valiant has proposed in his paper [19]. Some
important characteristics of SMAs in our definition such as capacity and error probability are
discussed with their upper and lower bounds presented. We also explore the theoretical possibilities
of memory allocators which can learn from input items.
We explicitly construct a stable memory allocator based on a randomly-connected feed-forward
neural network with biologically sound parameters. We use divisive inhibition of neurons in our
model, which allows us to obtain arbitrary level of stability and preserves continuity better. Rigorous proofs are given for the performance of this SMA. We also verify our theory through computer
simulations.
There are a lot of promising future works we can do. By making full use of the three conditions in
definition, we can possibly give tighter bounds for theoretical limits of SMAs. On the other hand,
though we have constructed a neural network model that realizes SMA, it is far from optimal.
The question whether we can construct a neural stable memory allocator with constant Lipschitz
factor for continuity remains open. Besides, it is worthwhile to investigate more complicated
computational functions of the hippocampus, such as the interaction between hippocampus and
cortex, and the retrieval of allocated memory.

Appendix
Proof of Theorem 1
Proof. We bound the overall error probability using pairwise error probabilities via union bound.
For orthogonality, we have:
P r {∀x, y ∈ Sn , dH (x, y) > An , dH (h(x), h(y)) > Bn }

h∼Hn

=1 − P r {∃x, y ∈ Sn , dH (x, y) > An , dH (h(x), h(y)) < Bn }
h∼Hn




[
=1 − P r
{dH (h(x), h(y)) < Bn }

h∼Hn 
x,y∈Sn ,dH (x,y)>An
X
≥1 −
P r {dH (h(x), h(y)) < Bn }
x,y∈Sn ,dH (x,y)>An

h∼Hn

≥1 − |Sn |2 εn
Similarly, for continuity and stability we have:
P r {∀x ∈ Sn , y ∈ {0, 1}n , dH (x, y) ≤ µdH (x, y)} ≥ 1 − |Sn |εn

h∼Hn

10

(17)

P r {∀x ∈ Sn , |h(x)| ∈ (rn (1 − δ), rn (1 + δ))} ≥ 1 − |Sn |εn

(18)

h∼Hn

For any sequence ξn → 0, let |Sn | = Kn = ξn √1εn . The probability of violating any of the requirements is O(ξn ), which goes to zero. Therefore, the capacity of this SMA is at least

o(1)
√ .
n

Proof of Theorem 2
Proof. The proof is based on the lower bound of one-way randomized approximate communication
complexity of Hamming distance by [10]. They showed that: If Alice has vector x of length n, and
Bob has vector y of length n, to estimate dH (x,y) within a factor of 1 ± δ with probability at least
1 − ε, Alice has to send at least Ω δ12 log 1ε logn bits to Bob.
We can use SMA to construct an one-way communication protocol: For a given SMA described
in the theorem, a common hashing function h ∼ Hn for Alice and Bob is sampled first. Upon
receiving the vector x, Alice computes h(x) and sends it to Bob. Bob has vector y and gets h(x),


Prn (1+δ)
n
n
so he can compute dH (h(x), h(y)). Because there are
j=rn (1−δ) j ≤ 2rn δ rn (1+δ) different
possible values for h(x), the number of bits needed to encode these values is at least:



n
K = log 2rn δ
(19)
rn (1 + δ)
We can write the Lipschitz condition in normalized form:


2
µ−λ
µ−λ
)dH (x, y) ≤
dH (h(x), h(y)) ≤ (1 +
)dH (x, y) > 1 − εn
P r (1 −
h∼Hn
µ+λ
µ+λ
µ+λ
By plugging into the result of [10], we have


µ+λ 2
1
) log logn
K=Ω (
µ−λ
εn
By combining equation (19)(21), we have





−( µ−λ )2 1
n
µ+λ
logn
εn = Ω 2rn δ
rn (1 + δ)

(20)

(21)

(22)

Proof of Theorem 3

Proof. For a strong SMA with An not too large, max |Sn | ∀x, y ∈ Sn , dH (x, y) > An ≥ Kn , we
can select set of input items Sn ⊆ {0, 1}n that satisfies |Sn | = Kn and ∀x, y ∈ Sn , dH (x, y) > An .
According to the definition of strong SMA, there exists a hashing function h such that ∀x ∈
(r )
Sn , h(x) ∈ Tn n and ∀x,
n y ∈ Sn , dH (x, y) > Bn . o
(r )
Let U (x, r) denote x0 ∈ Tn n |dH (x, x0 ) ≤ r , we have

∀x, y ∈ Sn , U

B
h(x),
2





B
∩ U h(y),
=∅
2

(23)

Thus, we have
X
x∈Sn



 
Bn
n
(rn )
U h(x),
≤ |Tn | =
2
rn
11

(24)


(r )
To estimate the number of elements in set U h(x), B2n , notice that to guarantee h(x) ∈ Tn n ,
we can change k ≤ Bn /4 bits at most from 0 to 1 and from 1 to 0 at the same time. Therefore,

U

Bn
h(x),
2



Bn

 
4 
X
n − rn
rn
·
=
k
k

(25)

k=1

Also,
Bn ≤ dH (h(x), h(y)) ≤ 2rn =⇒ k ≤

Bn
rn
≤
4
2

The sparsity of output suggests that rn  n, hence
 n−rn 
rn
1
1
rn
rn
k+1 · k+1
 n−rn  =
(r − k)(n − rn − k) ≥ rn
· (n − rn − )  1
rn
2 n
2
(k
+
1)
(
+
1)
2
2
·
2
k
k
and

 



n − rn
Bn
·
≤ U h(x),
Bn
Bn
2
4
4

is a good estimation for U h(x), B2n ,and we have

n


rn

|Sn | ≤

Bn
4



·

(27)

(28)

rn
rn

(26)

(29)

n−rn 
Bn
4

As n, rn and Bn are large, we can use Stirling’s formula log n! = n log n−n+O(log n) to approximate
n
rn :
 
n
rn
rn
rn
rn
log
= (− log − (1 − )log(1 − ) + o(1))n = (H(α) + o(1))n
(30)
rn
n
n
n
n
n−r 
r 
Similar results can be derived for Bnn and Bn n . By using inequality (29), we get
4

4


log Kn ≤
where α =

rn
n,

β=

Bn
4rn


H(α) − αH(β) − (1 − α)H

αβ
1−α




+ o(1) n

(31)

and H(p) = −p log p − (1 − p) log (1 − p).

Proof of Theorem 4
(r )

Proof. Let U denotes the uniform distribution on all the function that maps from Sn to Tn n .
h̃n ∼ U indicates that given x, y, h̃n (x) and h̃n (y) are independently and uniformly distributed on

12

(rn )

Tn

. We have
n
o
∃x 6= y ∈ Sn , dH (h̃n (x), h̃n (y)) ≤ Bn
h̃n ∼U


 [

= Pr
{dH (h̃n (x), h̃n (y)) ≤ Bn }

h̃n ∼U 
x6=y∈S
n
o
X
P r dH (h̃n (x), h̃n (y)) ≤ Bn
≤
Pr

<

x6=y∈Sn
|Sn |2

2

|Sn |2
<
2

h̃n ∼U

Pr

n
o
dH (h̃n (x), h̃n (y)) ≤ Bn

h̃n ∼U

P B2n

k=0

rn
n−rn
k ·
k
n
rn





From equation (27) in the proof of Theorem 3, we know that
Bn
rn 
n−r 
 n−rn 
rn
2
· Bn n
Bn
X
·
k
k
≤ 2 2 n 2
n
rn

k=0

(32)

rn

By using the condition in the statement




αβ
1
H(α) − αH(β) − (1 − α)H
+ o(1) n,
log |Sn | ≤
2
1−α

(33)

we derive
n
o
∃x 6= y ∈ Sn , dH (h̃n (x), h̃n (y)) ≤ Bn < 1

Pr
h̃n ∼U

⇒∃ĥn : Sn →

(34)
Tn(rn ) , ∀x, y

∈ Sn , dH (ĥn (x), ĥn (y)) > Bn

n
n
Notice that ĥn has Lipschitz constant 2r
An on Sn . To extend ĥn to hn defined on {0, 1} , we use
Kirszbraun theorem [11].
P
Consider the Euclidean space Rn and its subspace W n−1 = {x ∈ Rn−1 | ni=1pxi = 0}. The relationship between Euclidean distance and Hamming distance is that d(x, y) = dH (x, y), ∀x, y ∈
Sn . Let ω denote the translation ω(x) = x − rnn 1n , then we have ω ◦ ĥn : Sn → Wn−1 is a Lipschitzn
continuous
qmap from the subset Sn of Hilbert space (R , d) to Hilbert space (Wn−1 , d) with Lipschitz

constant

2rn
An .

According to Kirszbraun theorem, there exists a Lipschitz-continuous map h0 that

extends ω ◦ ĥn and has the same Lipschitz constant: h0 : Rn → W n−1
r
2rn
n
∀x, y ∈ R , d(h0 (x), h0 (y)) ≤
d(x, y)
An

(35)

We define hn on {0, 1}n as follows:
∀x ∈ {0, 1}n , hn (x)i =



0 |h0 (x)i +
1 |h0 (x)i +

rn
n|
rn
n|

≤ |h0 (x)i −
> |h0 (x)i −

n−rn
n |
n−rn
n |

1≤i≤n

(36)

Given an arbitrary y ∈ Sn , we have ∀x ∈ {0, 1}n ,
|h0 (x)i − h0 (y)i | <

1
⇒ hn (x)i = hn (y)i
2
13

(37)

Let k denote the number of bits such that |h0 (x)i − h0 (y)i | ≥ 21 , we have
r

k
≤ d(h0 (x), h0 (y)) ≤
4

Therefore
dH (hn (x), hn (y)) =

n
X

r

8rn
2rn
d(x, y) ⇒ k ≤
dH (x, y)
An
An

|hn (x)i − hn (y)i | ≤ k ≤

i=1

8rn
dH (x, y)
An

(38)

(39)

Proof of Theorem 5
Theorem 5 guarantees stable memory allocation properties of a three-layer neural circuit with
divisive inhibition. Key issue in the proof is to estimate high probability upper and lower bounds
for output-layer proportion of activation, as well as expansion rates. From a high level point of
view, the second layer of this network makes it possible for a wide range of input density to have
approximately the same output density, while in the third layer, the parameter for divisive inhibition
enables us to control the output density at an arbitrary level. The continuity and orthogonality
condition is satisfied since random projection preserves locality.
Lemma 1 describes the probability of activation in the second layer:
Proof of Lemma 1. By symmetry, the probability of β T x > 0 and β T x < 0 is equal. So we have
P r{β T x > 0} = 12 1 − P r{β T x > 0} . We can then write this probability as:
P r{β T x = 0} =

b|x|/2c 

X
i=1

 
|x| 2i 2i
p (1 − 2p)|x|−2i
2i
i

(40)

By applying Chernoff bound in relative entropy form, we have:
b|x|/2c

X
i=2p|x|+1

 
|x| 2i 2i
2 p (1 − 2p)|x|−2i ≤ e−2(2 ln 2−1)p|x|
2i

(41)


1
√1
For the first 2p|x| terms, we use Stirling approximation 2−k 2k
k = πk + O( k ) for each term. Since
first p|x| terms are smaller than terms with k ∈ [p|x| + 1, 2p|x|], we have
2p|x| 

X
i=1

 

2p|x| 
X
|x| 2i 2i
2
|x|
1
|x|−2i
(2p)2i (1 − 2p)|x|−2i ≤ p
p (1 − 2p)
≤p
2i
i
πp|x| i=p|x|+1 2i
πp|x|

(42)

which concludes the proof of this lemma.
Proof of Lemma 2. Let q be the index where xq 6= yq , we assume xq = 0, yq = 1 without loss of
generality. On such circumstance, the only chance to make g(x) 6= g(y) is hβq = 1, β T x = 0i or
hβq = −1, β T x = 1i. Using the estimate in Lemma 1 we can obtain the probability of such events,
which leads directly to the result.
Proof of Lemma 3 and Lemma 4. In the proof we use Gaussian approximation for binomial variables, the error term can be estimated via Berry-Esseen bound.
Let the common bits of x and y be vector w = x ∩ y, we have x = w + x̃, y = w + ỹ. We obtain
14

independent random variables β T w, β T x̃, β T ỹ. By applying bivariate central limit theorem to them,
we have
 T 

 


β x
|x|
|x| |w|
∼ N p(1 − 2c)
, v(c, p)
(43)
βT y
|y|
|w| |y|
Then the probability can be written as quadrant integral of bivariate Gaussian distribution, as
appears in the lemmas.

 


Z Z
|x|
|x| |w|
N p(1 − 2c)
, v(c, p)
dudv
(44)
P r {g(x) 6= g(y)} ≈
|y|
|w| |y|
u·v<0
The integral in Lemma 3 centers at origin and admits a closed-form solution. While in Lemma 4
we write it as univariate integral with CDF and PDF of Gaussian. Later we will estimate its value
given specific parameters.
According to Berry-Esseen inequality, the error introduced in cumulative density functions by
E[|βi |3 ]
√ ) = O( √1 ).
Gaussian approximator is bounded with O( var(β
pn
)1.5 n
i

Now we proceed to prove Theorem 5.
Proof of Theorem 5. We give proofs for three requirements one by one:
Stability: Let s1 denote the probability for middle-layer neurons to fire. According to Lemma 1,
s1 is restricted in a narrow range: 0 ≤ 12 − s1 ≤ √ 1
+ 21 e−2(2 ln 2−1)p|x| .
2

πp|x|

Now that each unit in third layer depends upon the sum of several i.i.d. random variables. By
applying central limit theorem to the sum, we can estimate the probability for a output-layer
neuron to fire is approximately
!
√ (1 − 2c)ps1
P r{h(x)i = 1} ≈ Φ
np
(45)
v(c, ps1 )
By plugging in the parameter C2 =
≤

1
2

−

√s
2 2−s2

and s = Φ−1

rn
n

q

2
np ,

we can show that

log(n/rn )
rn
− P r{h(x)i = 1} ≤ √
n
s0 n1−γ

(46)

Since all output units are i.i.d. with respect to randomness of last layer, we can therefore apply
Chernoff’s bound to conclude the stability argument.
Continuity: The technique used in our proof is based on bounding the output difference
between two vector who has exact one different bit. Fix dH (x, y) = L, we construct a sequence
x = v0 , v1 , v2 , · · · , vL = y with dH (vi−1 , vi ) = 1.
For vi−1 and vi , consider the probability for each second-layer neuron to be different. According to
Lemma 2, we can estimate P r{g(vi ) 6= g(vi−1 )} ≈ π1 cos−1 √|vi−1 ∩vi | . By union bound we have the
|vi |·|vi−1 |

following probabilistic triangle inequality:
P r{g(x) 6= g(y)} ≤ P r{

L
[

g(vi ) 6= g(vi−1 )} ≤

i=1

L
X

P r{g(vi ) 6= g(vi − 1)}

(47)

i=1

Lemma 1 tells us that both x and y activate approximately

n
2

neurons in the middle layer, which
q
satisfies the requirement of Lemma 4. By applying Lemma 4 with η = O(L s0pn ), we derive the
15

following (approximate) upper bound for probability of changed bits in third layer:
!
1
Z
(s0 n1+γ ) 4
−1 rn
√
ϕ(t)Φ −
O(1) ·
|t − Φ ( )| dt
n
L
R

(48)

We estimate the integral by √
dividing it into three parts:
2 log n L
rn
−1
Let t1 , t2 = Φ ( n ) ±
1 respectively. We have
(s0 n1+γ ) 4

!
1
Z
(s0 n1+γ ) 4
r
1
n
−1
√
ϕ(t)Φ −
|t − Φ ( )| dt ≤
φ(t)dt ≤ √ (t2 − t1 )
n
2π
L
(t1 ,t2 )
(t1 ,t2 )

Z

For the integral value outside this interval, we bound it with Gaussian tail:
!
 
1
Z
Z
(s0 n1+γ ) 4
1
r
n
−1
√
ϕ(t)Φ (−2 log n) dt = O
|t − Φ ( )| dt ≤
ϕ(t)Φ −
n
n2
L
t>t2
t>t2
(For t < t1 , we have very similar bounds)
Summarizing the calculation above, we can get an approximate upper bound
!
√
log n L
r
−1 n
P r{h(x)i 6= h(y)i } = O
( ))
1 ϕ(Φ
1+γ
n
4
(s0 n )

(49)

(50)

(51)
√

So the probability for each output neuron to differ is upper bounded with µnn L . We then apply
the Chernoff bound in relative entropy form and conclude the probabilistic upper bound.
Orthogonality: For x, y ∈ {0, 1}n such that dH (x, y) ≥ an, we have
s
|x ∩ y|
|x ∩ y| √
p
≤ 1−a
≤
(52)
|x ∪ y|
|x| · |y|
According to Lemma 3, the probability of making differences at second layer is at least
√
1
P r{g(x) 6= g(y)} ≥ b1 , cos−1 1 − a
π
Then we apply Lemma 4 with η = b1 :
Z
t
|t − Φ−1 (rn /n)|
√
P r{h(x)i 6= h(y)i } ≥
ϕ( q
)Φ(
)dt
1
b
1
R
1 − 2 b1
Assuming b1 constant, we can obtain the following lower bound for this integral:
Z
|t − Φ−1 (rn /n)|
t
√
)dt
P r{h(x)i 6= h(y)i } ≥ ϕ( q
)Φ(
b1
R
1 − 12 b1
Z
t
|t − Φ−1 (rn /n)|
q
√
≥
ϕ(
)Φ(
)dt
√
b1
|t−Φ−1 ( rnn )|≤ b1
1 − 12 b1
Z
t
≥
ϕ( q
)Φ(−1)dt
√
|t−Φ−1 ( rnn )|≤ b1
1 − 12 b1




√
√
−1
−1
Φ (rn /n) + b1 
Φ (rn /n) − b1 
q
q
≥Φ(−1)Φ 
− Φ(−1)Φ 
1
1 − 2 b1
1 − 12 b1
≥

brn
n
16

(53)

(54)

(55)

The value of b depends upon neither rn nor n, but only b1 , which is assumed to be a constant. So
we have proved a lower bound for the probability of third-layer nodes to be different. Since those
nodes are i.i.d. with respect to the randomness in the last layer. By applying Chernoff bound we
can get this result.

References
[1] Zeyuan Allen-Zhu, Rati Gelashvili, Silvio Micali, and Nir Shavit. Sparse sign-consistent
johnson–lindenstrauss matrices: Compression with neuroscience-based constraints. Proceedings of the National Academy of Sciences, 111(47):16872–16876, 2014.
[2] Per Andersen, Richard Morris, David Amaral, Tim Bliss, and John O’Keefe. The hippocampus
book. Oxford University Press, USA, 2006.
[3] Rosa I. Arriaga and Santosh Vempala. An algorithmic theory of learning: Robust concepts
and random projection. In Proc. of FOCS, pages 616–623, 1999.
[4] Vašek Chvátal. The tail of the hypergeometric distribution. Discrete Mathematics, 25(3):285–
287, 1979.
[5] Dominique Debanne, Beat H Gähwiler, and Scott M Thompson. Heterogeneity of synaptic
plasticity at unitary ca3–ca1 and ca3–ca3 connections in rat hippocampal slice cultures. The
Journal of Neuroscience, 19(24):10664–10671, 1999.
[6] Brent Doiron, André Longtin, Neil Berman, and Leonard Maler. Subtractive and divisive
inhibition: effect of voltage-dependent inhibitory conductances and noise. Neural Computation,
13(1):227–248, 2001.
[7] Vitaly Feldman and Leslie G. Valiant. Experience-induced neural circuits that achieve high
capacity. Neural Computation, 21(10):2715–2754, 2009.
[8] John J Hopfield. Neural networks and physical systems with emergent collective computational
abilities. Proceedings of the national academy of sciences, 79(8):2554–2558, 1982.
[9] Piotr Indyk and Rajeev Motwani. Approximate nearest neighbors: towards removing the curse
of dimensionality. In Proc. of STOC, pages 604–613. ACM, 1998.
[10] T. S. Jayram and David P. Woodruff. Optimal bounds for johnson-lindenstrauss transforms
and streaming problems with subconstant error. ACM Transactions on Algorithms, 9(3):26,
2013.
[11] M Kirszbraun. Über die zusammenziehende und lipschitzsche transformationen. Fundamenta
Mathematicae, 1(22):77–108, 1934.
[12] Jorge F Mejias, Alexandre Payeur, Erik Selin, Leonard Maler, and André Longtin. Subtractive,
divisive and non-monotonic gain control in feedforward nets linearized by noise and delays.
Frontiers in computational neuroscience, 8, 2014.
[13] Christos H. Papadimitriou and Santosh S. Vempala. Cortical computation. In Proceedings of
the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San
Sebastián, Spain, July 21 - 23, 2015, pages 1–2, 2015.

17

[14] Christos H Papadimitriou and Santosh S Vempala. Cortical learning via prediction. In Proc.
of COLT, 2015.
[15] Leslie G. Valiant. Circuits of the mind. Oxford University Press, 1995.
[16] Leslie G Valiant. A neuroidal architecture for cognitive computation. Journal of the ACM
(JACM), 47(5):854–882, 2000.
[17] Leslie G. Valiant. Memorization and association on a realistic neural model. Electronic Colloquium on Computational Complexity (ECCC), (004), 2005.
[18] Leslie G Valiant. A quantitative theory of neural computation.
95(3):205–211, 2006.

Biological cybernetics,

[19] Leslie G. Valiant. The hippocampus as a stable memory allocator for cortex. Neural Computation, 24(11):2873–2899, 2012.
[20] Leslie G Valiant. What must a global theory of cortex explain? Current opinion in neurobiology, 25:15–19, 2014.
[21] Xinyang Yi, Constantine Caramanis, and Eric Price. Binary embedding: Fundamental limits
and fast algorithm. In Proc. of ICML, pages 2162–2170, 2015.

18

