Entropy landscape of solutions in the binary perceptron problem

Abstract

The statistical picture of the solution space for a binary perceptron is studied. The binary perceptron learns a random classification of input random patterns by a set of binary synaptic weights. The learning of this network is difficult especially when the pattern (constraint) density is close to the capacity, which is supposed to be intimately related to the structure of the solution space. The geometrical organization is elucidated by the entropy landscape from a reference configuration and of solution-pairs separated by a given Hamming distance in the solution space. We evaluate the entropy at the annealed level as well as replica symmetric level and the mean field result is confirmed by the numerical simulations on single instances using the proposed message passing algorithms. From the first landscape (a random configuration as a reference), we see clearly how the solution space shrinks as more constraints are added. From the second landscape of solution-pairs, we deduce the coexistence of clustering and freezing in the solution space.

21 pages, 6 figures, version accepted by Journal of Physics A: Mathematical and Theoretical

References in corpus (11)

• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Efficient supervised learning in networks with binary synapses
• Generalization of the cavity method for adiabatic evolution of Gibbs states
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Irreducible free energy expansion and overlaps locking in mean field spin glasses
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Learning by random walks in the weight space of the Ising perceptron
• Combined local search strategy for learning in networks of binary synapses

Cited by in corpus (19)

• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• Origin of the computational hardness for learning with binary synapses
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Mean-field inference methods for neural networks
• Advanced Mean Field Theory of Restricted Boltzmann Machine
• Mean field analysis of reverse annealing for code-division multiple-access multiuser detection
• Spin glass theory and its new challenge: structured disorder
• Quantum Annealing for Neural Network optimization problems: a new approach via Tensor Network simulations
• Teacher-student learning for a binary perceptron with quantum fluctuations
• Clustering of neural codewords revealed by a first-order phase transition
• On the Atypical Solutions of the Symmetric Binary Perceptron
• The Copycat Perceptron: Smashing Barriers Through Collective Learning
• Maximally flexible solutions of a random $K$-satisfiability formula
• How to escape atypical regions in the symmetric binary perceptron: a journey through connected-solutions states
• Data-driven effective model shows a liquid-like deep learning
• Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems
• Solvable Model for Inheriting the Regularization through Knowledge Distillation
• Frozen $1$-RSB structure of the symmetric Ising perceptron
• The maximum-average subtensor problem: equilibrium and out-of-equilibrium properties