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.
arXiv comment9 pages, 4 figures and 1 table, further discussions added
References in corpus (20)
- Weak pairwise correlations imply strongly correlated network states in a neural population
- Identification of direct residue contacts in protein-protein interaction by message passing
- The Bethe lattice spin glass revisited
- Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
- Maximum entropy models for antibody diversity
- Network information and connected correlations
- The Ising Model for Neural Data: Model Quality and Approximate Methods for Extracting Functional Connectivity
- The Entropy of the K-Satisfiability Problem
- Adaptive Cluster Expansion for Inferring Boltzmann Machines with Noisy Data
- Learning by message-passing in networks of discrete synapses
- Small-correlation expansions for the inverse Ising problem
- Intrinsic limitations of inverse inference in the pairwise Ising spin glass
- From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
- Communities of solutions in single solution clusters of a random K-Satisfiability formula
- Numerical Solution-Space Analysis of Satisfiability Problems
- Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
- 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
- Susceptibility Propagation for Constraint Satisfaction Problems
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