Convergence of stochastic learning in perceptrons with binary synapses

Senn, Walter; Fusi, Stefano (2005). Convergence of stochastic learning in perceptrons with binary synapses. Physical review. E - statistical, nonlinear, and soft matter physics, 71(6 Pt 1), 061907. American Physical Society 10.1103/PhysRevE.71.061907

Text PhysRevE.71.061907.pdf - Published Version Restricted to registered users only Available under License Publisher holds Copyright. Download (168kB) | Request a copy

The efficacy of a biological synapse is naturally bounded, and at some resolution, and is discrete at the latest level of single vesicles. The finite number of synaptic states dramatically reduce the storage capacity of a network when online learning is considered (i.e., the synapses are immediately modified by each pattern): the trace of old memories decays exponentially with the number of new memories (palimpsest property). Moreover, finding the discrete synaptic strengths which enable the classification of linearly separable patterns is a combinatorially hard problem known to be NP complete. In this paper we show that learning with discrete (binary) synapses is nevertheless possible with high probability if a randomly selected fraction of synapses is modified following each stimulus presentation (slow stochastic learning). As an additional constraint, the synapses are only changed if the output neuron does not give the desired response, as in the case of classical perceptron learning. We prove that for linearly separable classes of patterns the stochastic learning algorithm converges with arbitrary high probability in a finite number of presentations, provided that the number of neurons encoding the patterns is large enough. The stochastic learning algorithm is successfully applied to a standard classification problem of nonlinearly separable patterns by using multiple, stochastically independent output units, with an achieved performance which is comparable to the maximal ones reached for the task.

Interest & Impact

Downloads

3 since deposited on 18 Jan 2023
3 in the past 12 months

Citations

5 Citations in Web of Science ®
6 Citations in Scopus

Search

in Google Scholar™

Services

Actions (login required)

Edit item

Actions (login required)

Edit item