We show that a message-passing process allows to store in binary "material" synapses a number of random patterns which almost saturates the information theoretic bounds. We apply the learning algorithm to networks characterized by a wide range of different connection topologies and of size comparable with that of biological systems (e.g. n ≃ 10 5 − 10 6 ). The algorithm can be turned into an on-line -fault tolerant-learning protocol of potential interest in modeling aspects of synaptic plasticity and in building neuromorphic devices. PACS numbers: 75.10.Nr,87.19.La,87.10+c, Learning and memory are implemented in neural systems mostly through distributed changes of synaptic efficacy [1] . The learning problem in neural networks (NN) asks whether one can find values for the synaptic efficacies such that a set of p patterns are stored simultaneously. Depending on the structure of the network -feed-forward or recurrent -the storage problem is either seen as a classification problem (input patterns are classified according to the output of the network) or as an attractor dynamics problem (patterns are the external stimuli which drive the dynamics of the network to the closest attractor) [2] . In any case, understanding the mechanisms underlying synaptic changes constitutes a crucial step for modeling real neural circuits (e.g. the Purkinje cells in the cerebellum [3] ). On the purely theoretical side many basic results have been derived, ranging from information theoretic bounds [4, 5] and statistical physics analysis of learning capabilities [6] in model NN to concrete algorithms, like artificial pattern recognition systems. Still there exist many open conceptual problems that are related to the need of satisfying realistic constraints [7] . Modeling material synapses is possibly one of the most basic ones, the discrete case (and specifically the switch-like binary one) being of particular experimental [8] and technological interest [9] : recent experiments -at the single synapse resolution level -have shown that some synapses undergo potentiation or depression between a restricted number of discrete stable states through switch-like unitary events [8] . It is has been known since many years that the discreteness of synaptic efficacies makes the learning problem extraordinarily difficult [10] : even the task of finding binary synaptic weights for a single layer network (the binary perceptron) which classifies in two classes a given set of patterns is both NP-complete and computationally hard on average (as observed in classical numerical experiments). In spite of the fact that binary networks can in principle classify correctly an extensive number p = αn of random patterns with n binary synapses [11] , practically there exists no known algorithm which is able to store exactly more than just a logarithmic number [12, 13] as soon as a sub-exponential cut is put on their running time. Here we present a distributed message-passing algorithm of statistical physics origin which is able to store efficiently an extensive number (p = αn with α > 0) of random patterns in binary NN characterized by a wide range of different topologies. We consider single and multi-layer networks with local connectivities of the neurons ranging from finite to extensive. The typical computational complexity of the algorithm will be shown to scale roughly as O n 2 log (n) , that is almost linearly on the size of the input for an extensive number of patterns. This fact together with the parallel nature of the algorithm allows to easily find optimal synaptic weights for systems as large as n = 10 6 with α relatively close the critical value α c above which perfect learning is no longer possible. From the algorithmic viewpoint, our solution to the binary learning problem should be seen as an example of solution of constraint satisfaction problems over dense factor graphs (a graphical representation of combinatorial constraints used in information theory [14, 15] ). As such, our result show how the recent progress in combinatorial optimization by statistical physics and message passing techniques which have allowed to solve efficiently famous combinatorial problems like random Ksatisfiability [16] or random graph Q-coloring [17], can be extended to other classes of problems in which constraints involve an extensive number of variables.
Constructing a factor-graph model for neural associative memory has been also addressed in REF where a message-passing algorithm is proposed to memorize any set of random patterns.
Learning by message-passing in networks of discrete synapses
Phys. Rev. Lett. 96, 030201 (2006)
Physics Computer Science Medicine Biology