Learning by Message Passing in Networks of Discrete Synapses

We show that a message-passing process allows us to store in binary “material” synapses a number of random patterns which almost saturate 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\simeq {10}^5–{10}^6$). The algorithm can be turned into an online—fault tolerant—learning protocol of potential interest in modeling aspects of synaptic plasticity and in building neuromorphic devices.

Figure 1

A nonoverlapping two-layer network with six synapses (empty circles) and three threshold units (filled dots), and its corresponding factor graph for four patterns (right). The factor graph is composed of variable nodes (circles; indices $i,j,o$ in the text) and function nodes (squares; indices $a,b$ in the text); messages “travel” over the edges of the factor graph in both directions. Note that while synaptic weights have a unique corresponding variable node on the factor graph, each of the two auxiliary variable computing a partial threshold (hidden units), being pattern-dependent, must be replicated for every pattern on the factor graph.

Figure 2

BP entropy vs $\alpha$ for single problem instances of size $n=3465$ for $K=1,3,5,7$. The analytic result for $K=1$ and $K\gg 1$ for $n\to \infty$ are also plotted for comparison. The upper inset shows $Q^t$ vs $t$ of the analytical DE prediction (dashed line) vs simulations over a system of size ${10}^5+1$ at $\alpha =0.6$ without reinforcement (data in perfect agreement to the prediction) and with reinforcement (${\gamma }_0=0$). The bottom inset shows the fraction of errors $E/n$ vs $t$ for both cases. In the latter case we can see that $Q^t\to 0$ as the solution is reached.

Figure 3

Learning of $\alpha n$ pseudorandom patterns curves for the binary perceptron for different values of ${\gamma }_0$ ($n={10}^4+1$, 20 samples). The running time scales with ${\gamma }_0$ roughly as $1/(1-{\gamma }_0)$. Inset: evolution of $Q^t$ and $E^t$ vs time $t$ for various kinds of two-layer network topologies, i.e., $n=3^7$, $\alpha =0.5$, and $K\in \{3^0,3^1,\dots ,3^6\}$. Note that the number of errors $E$ goes to 0 in all cases.