Replica symmetry breaking in bipartite spin glasses and neural networks

Some interesting recent advances in the theoretical understanding of neural networks have been informed by results from the physics of disordered many-body systems. Motivated by these findings, this work uses the replica technique to study the mathematically tractable bipartite Sherrington-Kirkpatrick (SK) spin-glass model, which is formally similar to a restricted Boltzmann machine (RBM) neural network. The bipartite SK model has been previously studied assuming replica symmetry; here this assumption is relaxed and a replica symmetry breaking analysis is performed. The bipartite SK model is found to have many features in common with Parisi's solution of the original, unipartite SK model, including the existence of a multitude of pure states which are related in a hierarchical, ultrametric fashion. As an application of this analysis, the optimal cost for a graph partitioning problem is shown to be simply related to the ground state energy of the bipartite SK model. As a second application, empirical investigations reveal that the Gibbs sampled outputs of an RBM trained on the MNIST data set are more ultrametrically distributed than the input data themselves.

Figure 1

(a) The phase diagram for the bipartite SK model (restricted to zero biases), as predicted by the replica-symmetric analysis. Only the SG/F phase boundary depends on the relative fractions of visible and hidden spins, and in this plot we have set ${\alpha }_v={\alpha }_h=1/2$ so that this phase diagram is exactly the same as in the SK model. (b) To display the effect of a disparity between the numbers of the two types of spins, we have zoomed into the SG/F transition for various values of ${\alpha }_h$. The solid line corresponds to ${\alpha }_v={\alpha }_h=1/2$, and starting in the lower right-hand corner, the curves descend as ${\alpha }_h$ decreases.

Figure 2

The block-diagonal Parisi ansatz for the overlap matrices $Q_{ab}$ (bottom) along with a dendrogram (top) illustrating the hierarchical relationship contained within the ansatz. Here, $k=3$, with $m_i=(64,16,8,4,1)$ for $i=0,...,k+1$. The branching ratio of the tree at level $i$ equals $m_i/m_{i+1}$. This plot uses a gray scale with white corresponding to 0 and black corresponding to 1. The shading thus reflects the fact that the $q_i$ form an increasing sequence (for readability, only $q_0$ and $q_1$ have been labeled).

Figure 3

Schematic depiction of the hierarchical tree of spin-glass states, with ancestor states at higher temperatures related to descendant states at lower temperatures by a branching process. The various curves represent the free energy at different temperatures, plotted against a one-dimensional line through the state space. Although the state space is discrete, it is schematically shown here as a continuum.

Figure 4

(a) The near-critical overlap $q^{\left(v\right)}$ for the visible spins. The overlap for the hidden spins may be obtained by interchanging ${\alpha }_v\leftrightarrow {\alpha }_h$. (b) The probability distribution of visible overlaps. The vertical line represents a delta function spike.

Figure 5

A depiction of the bipartite graph partitioning problem. The vertices have been separated into two clusters, $A,B$, with each cluster containing $N_v/2$ vertices of one species, and $N_h/2$ of the other. The clusters were chosen to minimize the number of interpartition edges.

Figure 6

The optimal cost of the graph partitioning problem with the leading term in the large-$N$ limit subtracted, plotted against $N^{3/2}$. The points correspond to simulation results and the dashed lines are linear fits. Equation (3.7) gives that each line slope is proportional to the ground state energy density of the bipartite SK model with the same value of ${\alpha }_h$. When ${\alpha }_h=1/2$ the ground state energy of the bipartite SK model agrees with that of the unipartite SK model, which is known to high accuracy: $E_{gs}^{\text{SK}}/N=-0.7633$ [31]. The solid line corresponds to the ${\alpha }_h=1/2$ analytic prediction, calculated using this value for the ground state energy. The best-fit slope for the simulation data agrees with the analytic prediction to within 2.9%. In Sec. 4 below we will compare this method's estimates for $E_{gs}^{\text{SK}}$ for ${\alpha }_h\ne 1/2$ against other numerical methods' estimates.

Figure 7

The disorder-averaged energy density (a) and entropy density (b), obtained from 3 distinct calculations and for several values of ${\alpha }_h$. The bottom set of 3 (blue) curves in both figures corresponds to ${\alpha }_h=1/2$, the middle set of (orange) curves to ${\alpha }_h=1/4$, and the top set of (green) curves to ${\alpha }_h=1/8$. Within each set of 3 curves, the solid lines correspond to the RSB-1 ansatz, the dashed to the RS ansatz, and the dotted lines to MC simulations. Above $T>1$, the RS ansatz is exact and gives Eq. (2.31), and the RSB-1 result is omitted. In both plots $N=400$. In (b) the horizontal line corresponds to zero entropy density.

Figure 8

The ground state energy density of the bipartite SK model as a function of the ratio ${\alpha }_h=N_h/N$. The dashed and solid black curves are the RS and RSB-1 approximations, respectively. The blue crosses correspond to the $T=0$ extrapolation of the Monte Carlo curves shown in Fig. 7. The orange stars correspond to the estimate yielded by the graph partitioning problem considered in Sec. 3 for $N=400$. The isolated black point at ${\alpha }_h=1/2$ corresponds to the exact RSB-$\infty$ result for the ground state energy of the SK model, $E_{gs}^{\text{SK}}/N=-0.7633$ [31]. For ${\alpha }_h=1/2$, the exact ground state energy lies between the RSB-1 and MC estimates, and as explained in the main text, we believe this holds true for general values of ${\alpha }_h$.

Figure 9

Overlap distribution, $P\left(q\right)$, for the visible spins (blue, solid) and the hidden spins (orange, dashed), for (a) a temperature in the spin-glass phase, and (b) a temperature in the paramagnetic phase. The distributions are estimated from $N=400$, ${\alpha }_h=0.25$ MC samples using Parzen windows with a standard deviation of 0.05. In an infinite RSB analysis, one would expect delta function peaks at the maximal values of $q$, though these divergences are difficult to capture with finite-$N$ simulations.

Figure 10

Visual depictions of the ultrametric structure, or lack thereof, in the state space of the bipartite SK model for different temperatures and $w=1$, $w_0=0$. The first temperature (a) corresponds to the paramagnetic (disordered) phase, and the others (b), (c) correspond to the spin-glass (ordered) phase. Black pixels correspond to matrix entries with $d_{ab}=0$, and the color then changes from dark purple to yellow as the distances increase. These plots were made for $N_v=N_h=500$.

Figure 11

The probability density of triangle side lengths, for visible spins only, in the $(d_{\text{mid}}-d_{\text{min}},d_{\text{max}}-d_{\text{mid}})$ plane for (a) the paramagnetic phase at $T=4.0$, and (b) the spin-glass phase at $T=0.217$. Points which lie on the horizontal axis correspond to isosceles triangles, and the origin corresponds to equilateral triangles. In the spin-glass phase, approximately 25% of the points lie in the equilateral cluster near the origin, in agreement with the theoretical prediction Eq. (2.39). These plots were generated for $N_v=400$, $N_h=200$.

Figure 12

(a) A random selection of 100 MNIST images, with 10 examples of each digit. (b) Images generated from the RBM through Gibbs sampling, using the MNIST data shown in the left panel as initial seeds.

Figure 13

(a) The dissimilarity matrix and associated dendrogram for 150 images of the MNIST data, after converting to binary by rounding all nonzero pixel intensities to 1. (b) The same plot, made for the Gibbs samples drawn from the trained RBM, using the MNIST images as initial seeds. The distances are calculated according to the formula used in Fig. 10, namely $d_{ab}=(1-N_v^{-1}{\sum }_i{v}_i^a{v}_i^b)/2$.

Figure 14

Distribution of triangle side lengths for the visible spins. (a) MNIST data, converted to binary by rounding all nonzero pixel intensities to 1. (b) Samples generated through Gibbs sampling a fully trained RBM. The insets show zoomed-in depictions of the distribution.