Counting solutions from finite samplings
arXiv:1111.4278 · doi:10.1103/PhysRevE.85.026118
Abstract
We formulate the solution counting problem within the framework of inverse Ising problem and use fast belief propagation equations to estimate the entropy whose value provides an estimate on the true one. We test this idea on both diluted models (random 2-SAT and 3-SAT problems) and fully-connected model (binary perceptron), and show that when the constraint density is small, this estimate can be very close to the true value. The information stored by the salamander retina under the natural movie stimuli can also be estimated and our result is consistent with that obtained by Monte Carlo method. Of particular significance is sizes of other metastable states for this real neuronal network are predicted.
9 pages, 4 figures and 1 table, further discussions added
References in corpus (9)
- Identification of direct residue contacts in protein-protein interaction by message passing
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- The Ising Model for Neural Data: Model Quality and Approximate Methods for Extracting Functional Connectivity
- Adaptive Cluster Expansion for Inferring Boltzmann Machines with Noisy Data
- Small-correlation expansions for the inverse Ising problem
- From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
- Learning by random walks in the weight space of the Ising perceptron
- Combined local search strategy for learning in networks of binary synapses
- Message passing algorithms for the Hopfield network reconstruction: threshold behavior and limitation
Cited by in corpus (5)
- Effects of hidden nodes on network structure inference
- Adaptive Thouless-Anderson-Palmer approach to inverse Ising problems with quenched random fields
- Clustering of neural codewords revealed by a first-order phase transition
- Data-driven effective model shows a liquid-like deep learning
- Theory of population coupling and applications to describe high order correlations in large populations of interacting neurons