Learning by random walks in the weight space of the Ising perceptron

Abstract

Several variants of a stochastic local search process for constructing the synaptic weights of an Ising perceptron are studied. In this process, binary patterns are sequentially presented to the Ising perceptron and are then learned as the synaptic weight configuration is modified through a chain of single- or double-weight flips within the compatible weight configuration space of the earlier learned patterns. This process is able to reach a storage capacity of $\alpha \approx 0.63$ for pattern length N = 101 and $\alpha \approx 0.41$ for N = 1001. If in addition a relearning process is exploited, the learning performance is further improved to a storage capacity of $\alpha \approx 0.80$ for N = 101 and $\alpha \approx 0.42$ for N=1001. We found that, for a given learning task, the solutions constructed by the random walk learning process are separated by a typical Hamming distance, which decreases with the constraint density $\alpha$ of the learning task; at a fixed value of $\alpha$, the width of the Hamming distance distributions decreases with $N$.

arXiv comment12 pages, 4 figures, An extensively revised version

References in corpus (18)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• A Landscape Analysis of Constraint Satisfaction Problems
• Learning by message-passing in networks of discrete synapses
• A variational description of the ground state structure in random satisfiability problems
• Efficient supervised learning in networks with binary synapses
• Focused Local Search for Random 3-Satisfiability
• Circumspect descent prevails in solving random constraint satisfaction problems
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Constraint satisfaction problems with isolated solutions are hard
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Generalization learning in a perceptron with binary synapses
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• Weight space structure and analysis using a finite replica number in the Ising perceptron
• An exact learning algorithm for autoassociative neural networks with binary couplings
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Clustering of solutions in hard satisfiability problems

Cited by in corpus (6)

• Origin of the computational hardness for learning with binary synapses
• Entropy landscape of solutions in the binary perceptron problem
• Combined local search strategy for learning in networks of binary synapses
• Counting solutions from finite samplings
• Equivalence between algorithmic instability and transition to replica symmetry breaking in perceptron learning systems
• Replication-based Inference Algorithms for Hard Computational Problems