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

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

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

(14)

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

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)