Efficient supervised learning in networks with binary synapses

I. INTRODUCTION

• Binary synapses are motivated as noisy switches that may preserve memories more robustly over time than noise-sensitive analog systems.The text notes that positive feedback in postsynaptic protein networks could in principle induce bistability.Source: §I · p. 1
• Prior unsupervised binary-synapse models perform poorly in information stored per synapse unless activity is sparse and transitions are stochastic and balanced on average.Hidden states were added in subsequent studies to provide multiple time scales for fast learning and slow forgetting.Source: §I · p. 1
• Efficient learning remains unclear for binary or finite-state synapses, despite binary perceptrons reaching about 0.83 bits per synapse in enumeration and the problem being NP-complete.The reported capacity is close to the theoretical upper bound of 1 bit per synapse, but enumeration takes exponentially long in network size.Source: §I · p. 2

A. The model neuron

• The model neuron sums binary presynaptic inputs weighted by binary synapses, and its output is active above a threshold and inactive otherwise.In the ±1 setup, the paper uses threshold zero and assumes odd N so total input cannot equal zero.Source: A. The model neuron · p. 2

B. The classification problem

• The task is to find weights that map every pattern in each labeled class to its corresponding output; such a weight vector is a perfect classifier.For ±1 inputs and synapses, the negative class can be removed by redefining inputs and requiring positive outputs, a simplification that does not hold in the next section.Source: B. The classification problem · p. 2

C. The perceptron learning algorithm

• The perceptron updates weights only when the current pattern is misclassified, using the current input and an error signal.It is guaranteed to converge in finite time if a solution exists, but that proof applies to unbounded or sign-constrained weights, not weights with only finitely many states.Source: C. The perceptron learning algorithm · pp. 2–3

D. Requirements for biologically plausible learning algorithms with binary weights

• Online updates use current total input, presynaptic activity, and an error signal, with hidden-variable changes based only on these synapse-available quantities.Patterns are drawn randomly from the set being learned.Source: D. Requirements for biologically… · p. 3

E. Quantifying performance of various algorithms

• The benchmark is the largest α for which an algorithm finds a solution within a set iteration limit, compared with the theoretical αmax ≃0.83 for random unbiased patterns.Complete enumeration is guaranteed to find a solution for α ≤ αmax but requires exponentially large time in N; the study typically limits iterations to 10^4 per pattern.Source: E. Quantifying performance of various… · p. 3

F. Belief propagation–inspired algorithms

• A simplified Belief Propagation-inspired algorithm is designed to operate online while meeting the paper’s stated biological-plausibility requirements.The antecedent BP algorithm performed well on the random binary perceptron problem but had biologically unrealistic features.Source: F. Belief propagation–inspired… · p. 3

BP-inspired (BPI) Algorithm

• When output is erroneous, hidden states move to a nearest neighbor; when safely correct, they stay unchanged, while barely correct BPI patterns trigger transitions toward less plastic states.The figure distinguishes metaplastic transitions, which change only the hidden state, from plastic transitions that change synaptic efficacy.Source: BP-inspired (BPI) Algorithm · pp. 3–4, Figure 1 · p. 4
• Unlike the perceptron, BPI adds rule R2 for synaptic input just above threshold while keeping the actual synaptic weight binary.A stochastic variant applies R2 with probability ps for each presented pattern.Source: BP-inspired (BPI) Algorithm · p. 4

• Setting ps = 1 recovers deterministic BPI, while ps = 0 removes R2 and gives the clipped perceptron algorithm.Source: Stochastic BP-inspired (SBPI) Algorithm · p. 4
• With ps = 0.3, SBPI can reach α = 0.6, but performs worse than BPI for α ≤ 0.3.Source: Figure 2 · p. 5
• Figure 2A–C plots convergence time against N, while panel D plots the probability of perfect learning against x for different N.Source: Figure 2 · p. 5

G. Performance with unbounded variables

• With unbounded hidden variables, SBPI at ps ≈ 0.3 reaches capacity of order 0.65 with sublinear convergence time, while deterministic BPI has capacity α ≈ 0.3.Source: G. Performance with unbounded variables · p. 5
• At α = 0.3, deterministic BPI’s convergence time grows approximately as (log N)^1.5; CP’s convergence time becomes exponential in N for every tested α.Source: G. Performance with unbounded variables · p. 5
• The optimal ps decreases as α rises, trading slower convergence for higher capacity; an adaptive ps is reported to combine faster convergence at low α with the high capacity of low ps.Source: G. Performance with unbounded variables · pp. 5–6

H. Performance with bounded hidden variables

• For fixed K, BPI has higher capacity than SP with K visible states when N is sufficiently large, although adding an R2-equivalent rule to SP lets it overcome BPI.Source: H. Performance with bounded hidden… · p. 6
• The capacity-optimizing number of internal states scales roughly as √N, and BPI’s capacity peaks at finite K while the other three algorithms improve monotonically with K.Source: H. Performance with bounded hidden… · p. 6
• Capacity αc reaches almost 0.7 bits per synapse, near the theoretical limit αmax ≃ 0.83, with convergence time scaling roughly linearly with N at high α.The convergence-time prefactor is ≈2 · 10^-3.Source: H. Performance with bounded hidden… · p. 6

A. The 0,1 model neuron

• The model uses binary 0,1 synapses and neurons, with each input active with probability f, the coding level.Source: A. The 0,1 model neuron · p. 6
• The threshold is chosen to be approximately 0.3Nf, and desired outputs are active with probability f.Source: A. The 0,1 model neuron · p. 7
• Learning requires finding a weight vector w that satisfies the p classification equations for the input patterns.Source: A. The 0,1 model neuron · p. 7

B. The optimized algorithm

• It evaluates stability Δ rather than total input I, and computes binary weights from the signs of hidden variables.Source: B. The optimized algorithm · p. 7
• The 0,1 algorithm reaches capacity about 0.25, compared with a theoretical limit of 0.59.Source: B. The optimized algorithm · p. 8
• SBPI01 applies rule R2 stochastically only for patterns whose desired output is σa = 0.Source: B. The optimized algorithm · p. 8

SBPI01 Algorithm

• If the stated condition is not met, the algorithm does nothing.Source: SBPI01 Algorithm · p. 8
• Rule R2 applies only to patterns with zero output, changing hidden variables only for involved silent synapses; this uses one secondary threshold, θ − θm.Applying R2 only when the output is zero also optimizes performance; applying it only when the output is one gives similar results.Source: SBPI01 Algorithm · p. 8
• Boundaries on hidden variables further improve performance, and the number of states K that maximizes capacity scales with system size.The passage does not specify the scaling expression.Source: SBPI01 Algorithm · p. 8
• In dense coding (f = 0.5), SBPI01 exceeds 0.5 bits per synapse and approaches the theoretical maximum of 0.59 bits per synapse at sufficiently high N.The reported optimal learning probability is ps = 0.4.Source: SBPI01 Algorithm · p. 8

C. Heterogeneous synapses and sparse coding

• The heterogeneous algorithm uses weights 0 or ai, with ai drawn from a Gaussian distribution of mean 1 and standard deviation 0.1, and randomly varies θm around 1; its performance is similar to SBPI01 at f = 0.5.The threshold is drawn at each pattern presentation from a Gaussian distribution with variance 0.1.Source: C. Heterogeneous synapses and sparse… · p. 8
• With sparse coding, K = 10 reaches about 70% of maximal capacity near N = 10,000, versus about 10% for K = 2; capacity then decreases if K is increased further.The optimal K increases with N, but more mildly than in dense coding.Source: C. Heterogeneous synapses and sparse… · p. 8
• For N = 64000, SBPI converges quickly across α, while the cascade model is significantly slower.Source: C. Heterogeneous synapses and sparse… · p. 8

IV. ROBUSTNESS AGAINST NOISE

• In all tested situations, binary synapses with K hidden states were more robust to noise than synapses with K visible states.The comparison used SBPI for binary synapses and SP for visible-state synapses, in both bounded and unbounded cases.Source: §IV · p. 9

V. DISCUSSION

• BPI learns random input-output associations near theoretical capacity with binary synapses and finite hidden states, using roughly an order of magnitude fewer presentations per pattern than other known protocols.For neurons with about 10^4–10^5 synapses and α in [0.3, 0.6], it finds solutions in a few tens of presentations per pattern, while CP fails within 10^4 presentations per pattern.Source: §V · p. 9
• The added rule triggers metaplastic changes only when a pattern is barely learned: a single synaptic flip would cause an error, so contributing synapses stabilize their current state.The rule derives from Belief Propagation.Source: §V · p. 9
• Earlier binary-synapse work either required a finite separation margin that limits random-pattern learning to a number not increasing with N, or performed significantly worse than BPI.The comparison concerns Senn and Fusi and Fusi et al, respectively.Source: §V · p. 9
• The authors predict that supervised biological systems may make metaplastic changes without an error signal when inputs are close to threshold, and note potential relevance to large-scale electronic implementations.They also note that retrieval is digital, with discrete hidden variables needed only during learning.Source: §V · p. 10