Convergence of stochastic learning in perceptrons with binary synapses

Walter Senn and Stefano Fusi

Phys. Rev. E 71, 061907 – Published 16 June 2005

Abstract

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.

Received 18 September 2004

DOI:https://doi.org/10.1103/PhysRevE.71.061907

Authors & Affiliations

Walter Senn and Stefano Fusi^*

Department of Physiology, University of Bern, CH-3012 Bern, Switzerland

^*Electronic address: {wsenn,fusi}@cns.unibe.ch; URL: http://www.cns.unibe.ch/∼{wsenn,fusi}

Article Text (Subscription Required)

Click to Expand

References (Subscription Required)

Click to Expand

Issue

Vol. 71, Iss. 6 — June 2005

Reuse & Permissions

Access Options

Author publication services for translation and copyediting assistance advertisement

Images

Figure 1
Convergence time as a function of different parameters. (a) Number of iterations per pattern as a function of the number of neurons $N$ for $p = 10$ , 20, and 40 uncorrelated random patterns $(q = 0.05, f = 1 ∕ 4, θ = 0.01)$ ; (b) Number of iterations per pattern as a function of the learning rate (synaptic transition probability) $q$ and the scaling factor $ϱ$ . Convergence is only guaranteed if $ϱ$ and $q$ are small. Note that for small $q$ the convergence time only increases because the “step size” decreases, and not because the combinatorial problem becomes difficult as is the case for large $ϱ$ and large $q$ .Reuse & Permissions
Figure 2
Classification of nonlinearly separable patterns: (a) Deformed LATEXcharacters used for the benchmark test. Left: prototype letters; right: random sample of deformed letters; bottom: sample of deformed letters of class “2” (reproduced from [12]). (b),(c) Distributions of the total postsynaptic currents $h_{i}$ evoked by the patterns belonging to the two different classes $C^{+}$ (solid line, pooling together all output units which should get activated) and $C^{-}$ (dashed line, pooling together all output units which should not get activated), averaged over the $26 \times 10$ output neurons representing the letters of the alphabet in groups of 10. While before learning both classes evoked subthreshold currents (b), the two classes are well separated after the training (c), with patterns $ξ ∊ C^{+}$ evoking suprathreshold currents (solid line) and patterns $ξ ∊ C^{-}$ evoking subthreshold currents (dashed line). Vertical lines represent the neuronal threshold $θ_{o}$ , flanked with the stop-learning thresholds $θ_{o} \pm δ_{o}$ .Reuse & Permissions
Figure 3
(a) Fraction of misclassified patterns (for which none of the $n \times 10$ output units is activated) and (b) fraction of nonclassified patterns (for which the majority rule applied to the $n$ groups of ten output units gives the wrong classification) as a function of the number $n$ of classes of preprocessed LATEXdeformed characters. Each class contains 32 different patterns [see example of class “2” in Fig. 2a]. Both fractions increase as a power law as the number of classes increases. Note that the number of misclassified patterns is an order of magnitude smaller than the number of nonclassified patterns. The misclassification is kept small by exploiting the fact that the neurons tend to shut down when exposed to nonlinearly separable patterns (see Discussion). Each point in the two panels represents the average performance across ten different choices of $n$ classes ( $n = 10, 20, \dots, 200$ as indicated on the abscissa; for $n = 100$ and 200 we only chose two class sets). The error bars indicate the standard deviation.Reuse & Permissions

Physical Review E

covering statistical, nonlinear, biological, and soft matter physics