Weight space structure and analysis using a finite replica number in the Ising perceptron

Abstract

The weight space of the Ising perceptron in which a set of random patterns is stored is examined using the generating function of the partition function $\varphi (n)=(1/N)\log [Z^n]$ as the dimension of the weight vector $N$ tends to infinity, where $Z$ is the partition function and $[...]$ represents the configurational average. We utilize $\varphi (n)$ for two purposes, depending on the value of the ratio $\alpha =M/N$, where $M$ is the number of random patterns. For $\alpha <{\alpha }_{\mathrm{s}}=\mathrm{0.833...}$, we employ $\varphi (n)$, in conjunction with Parisi's one-step replica symmetry breaking scheme in the limit of $n\to 0$, to evaluate the complexity that characterizes the number of disjoint clusters of weights that are compatible with a given set of random patterns, which indicates that, in typical cases, the weight space is equally dominated by a single large cluster of exponentially many weights and exponentially many small clusters of a single weight. For $\alpha >{\alpha }_{\mathrm{s}}$, on the other hand, $\varphi (n)$ is used to assess the rate function of a small probability that a given set of random patterns is atypically separable by the Ising perceptrons. We show that the analyticity of the rate function changes at $\alpha ={\alpha }_{\mathrm{GD}}=\mathrm{1.245...}$, which implies that the dominant configuration of the atypically separable patterns exhibits a phase transition at this critical ratio. Extensive numerical experiments are conducted to support the theoretical predictions.

21 pages, 11 figures, Added references, some comments, and corrections to minor errors

References in corpus (7)

• Phase Transitions in the Coloring of Random Graphs
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Large Deviations in the Free-Energy of Mean-Field Spin-Glasses
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Large Deviation Property of Free Energy in p-Body Sherrington-Kirkpatrick Model
• Complex Replica Zeros of $\pm J$ Ising Spin Glass at Zero Temperature
• Thermodynamic Construction of an One-Step Replica-Symmetry-Breaking Solution in Finite Connectivity Spin Glasses

Cited by in corpus (13)

• Subdominant Dense Clusters Allow for Simple Learning and High Computational Performance in Neural Networks with Discrete Synapses
• Origin of the computational hardness for learning with binary synapses
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Entropy landscape of solutions in the binary perceptron problem
• Statistical mechanical analysis of sparse linear regression as a variable selection problem
• Replica symmetry breaking, complexity and spin representation in the generalized random energy model
• Learning by random walks in the weight space of the Ising perceptron
• Combined local search strategy for learning in networks of binary synapses
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness
• Replication-based Inference Algorithms for Hard Computational Problems
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
• Active online learning in the binary perceptron problem
• Belief Propagation for Error Correcting Codes and Lossy Compression Using Multilayer Perceptrons