Entropy landscape of solutions in the binary perceptron problem

DOI10.1088/1751-8113/46/37/375002MaRDI QIDQ2854130zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1304.2850, http://repository.ust.hk/ir/bitstream/1783.1-62092/1/605010-Article-11-fulltext.pdf

Mathematics Subject Classification ID

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

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.

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

Cited in

(16)

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

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)