Entropy landscape of solutions in the binary perceptron problem

Abstract

The statistical picture of the solution space for a binary perceptron is\nstudied. The binary perceptron learns a random classification of input random\npatterns by a set of binary synaptic weights. The learning of this network is\ndifficult especially when the pattern (constraint) density is close to the\ncapacity, which is supposed to be intimately related to the structure of the\nsolution space. The geometrical organization is elucidated by the entropy\nlandscape from a reference configuration and of solution-pairs separated by a\ngiven Hamming distance in the solution space. We evaluate the entropy at the\nannealed level as well as replica symmetric level and the mean field result is\nconfirmed by the numerical simulations on single instances using the proposed\nmessage passing algorithms. From the first landscape (a random configuration as\na reference), we see clearly how the solution space shrinks as more constraints\nare added. From the second landscape of solution-pairs, we deduce the\ncoexistence of clustering and freezing in the solution space.\n