Efficient supervised learning in networks with binary synapses

Abstract

Recent experimental studies indicate that synaptic changes induced by neuronal activity are discrete jumps between a small number of stable states. Learning in systems with discrete synapses is known to be a computationally hard problem. Here, we study a neurobiologically plausible on-line learning algorithm that derives from Belief Propagation algorithms. We show that it performs remarkably well in a model neuron with binary synapses, and a finite number of `hidden' states per synapse, that has to learn a random classification task. Such system is able to learn a number of associations close to the theoretical limit, in time which is sublinear in system size. This is to our knowledge the first on-line algorithm that is able to achieve efficiently a finite number of patterns learned per binary synapse. Furthermore, we show that performance is optimal for a finite number of hidden states which becomes very small for sparse coding. The algorithm is similar to the standard `perceptron' learning algorithm, with an additional rule for synaptic transitions which occur only if a currently presented pattern is `barely correct'. In this case, the synaptic changes are meta-plastic only (change in hidden states and not in actual synaptic state), stabilizing the synapse in its current state. Finally, we show that a system with two visible states and K hidden states is much more robust to noise than a system with K visible states. We suggest this rule is sufficiently simple to be easily implemented by neurobiological systems or in hardware.

10 pages, 4 figures

References in corpus (4)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Survey propagation: an algorithm for satisfiability
• Learning by message-passing in networks of discrete synapses
• Polynomial iterative algorithms for coloring and analyzing random graphs

Cited by in corpus (42)

• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Entropy and mutual information in models of deep neural networks
• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• Mean-field message-passing equations in the Hopfield model and its generalizations
• Shaping the learning landscape in neural networks around wide flat minima
• BS4NN: Binarized Spiking Neural Networks with Temporal Coding and Learning
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Efficiency of quantum versus classical annealing in non-convex learning problems
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• An atomic Boltzmann machine capable of on-chip learning
• Unveiling the structure of wide flat minima in neural networks
• Entropy landscape of solutions in the binary perceptron problem
• Learning through atypical "phase transitions" in overparameterized neural networks
• The committee machine: Computational to statistical gaps in learning a two-layers neural network
• Dreaming neural networks: rigorous results
• Generalization learning in a perceptron with binary synapses
• Learning may need only a few bits of synaptic precision
• On the role of synaptic stochasticity in training low-precision neural networks
• Inference and learning in sparse systems with multiple states
• Binarized Neural Networks on the ImageNet Classification Task
• A Max-Sum algorithm for training discrete neural networks
• Clustering of solutions in the symmetric binary perceptron
• Deep learning via message passing algorithms based on belief propagation
• Fast inference of ill-posed problems within a convex space
• On the Atypical Solutions of the Symmetric Binary Perceptron
• Power-law forgetting in synapses with metaplasticity
• Learning by random walks in the weight space of the Ising perceptron
• Learning with a network of competing synapses
• Combined local search strategy for learning in networks of binary synapses
• Theory and learning protocols for the material tempotron model
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness
• Competing synapses with two timescales: a basis for learning and forgetting
• Mean Field Bayes Backpropagation: scalable training of multilayer neural networks with binary weights
• Recognition Capabilities of a Hopfield Model with Auxiliary Hidden Neurons
• Quantum walk in a reinforced free-energy landscape: Quantum annealing with reinforcement
• Storing and retrieving long-term memories: cooperation and competition in synaptic dynamics
• Markov chain Hebbian learning algorithm with ternary synaptic units
• Frozen $1$-RSB structure of the symmetric Ising perceptron
• Noise tolerance via reinforcement: Learning a reinforced quantum dynamics
• Identifying all irreducible conserved metabolite pools in genome-scale metabolic networks: a general method and the case of Escherichia coli
• Training Multi-Layer Binary Neural Networks With Local Binary Error Signals