Entropy landscape of solutions in the binary perceptron problem

DOI10.1088/1751-8113/46/37/375002zbMATH Open1273.82052arXiv1304.2850OpenAlexW2062247903MaRDI QIDQ2854130FDOQ2854130

Authors: Hai-Ping Huang, K. Y. Michael Wong, Yoshiyuki Kabashima 

Publication date: 17 October 2013

Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1304.2850

Recommendations

• Clustering of solutions in the symmetric binary perceptron
• Learning and generalization errors for the 2D binary perceptron.
• Storage capacity in symmetric binary perceptrons
• Finite-size effects and bounds for perceptron models
• Threshold-induced phase transitions in perceptrons

Mathematics Subject Classification ID

Measures of information, entropy (94A17) Neural nets applied to problems in time-dependent statistical mechanics (82C32)

Cited In (14)

• Algorithmic obstructions in the random number partitioning problem
• Storage capacity in symmetric binary perceptrons
• On the atypical solutions of the symmetric binary perceptron
• Clustering of solutions in the symmetric binary perceptron
• Binary perceptron: efficient algorithms can find solutions in a rare well-connected cluster
• Local entropy as a measure for sampling solutions in constraint satisfaction problems
• Mean-field inference methods for neural networks
• Quantum annealing for neural network optimization problems: a new approach via tensor network simulations
• Gaussian-spherical restricted Boltzmann machines
• Dreaming neural networks: rigorous results
• Active online learning in the binary perceptron problem
• Minimal model of permutation symmetry in unsupervised learning
• Frozen 1-RSB structure of the symmetric Ising perceptron
• Entropy Bifurcation of Neural Networks on Cayley Trees

This page was built for publication: Entropy landscape of solutions in the binary perceptron problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2854130)