Research ArticleCOMPUTER SCIENCE

Optimal structure and parameter learning of Ising models

See allHide authors and affiliations

Science Advances  16 Mar 2018:
Vol. 4, no. 3, e1700791
DOI: 10.1126/sciadv.1700791
  • Fig. 1 ISO for different probe values of model parameters in the large M limit.

    The ISO is an empirical average of the inverse of the factors in the Gibbs measure, and its screening property becomes apparent in the limit of large number of samples. Changing the value of the probing parameters (Ji,Hi) in the ISO alters the effective interaction strength of σi with its neighbors. This mechanism is schematically represented in the figure, where the value of ISO for different values of probing parameters is depicted. When the probing parameters are equal to the true ones (J*i,H*i), the ISO completely screens this interaction making σi effectively independent of its neighbors. With some analysis, this can be shown to be equivalent to the ISO attaining its minimum at the true parameters of the model.

  • Fig. 2 Reconstruction of the graph topology and the values of parameters with the logRISE.

    Reconstruction procedure for an Erdös-Rényi graph with N = 25 and average degree 〈d〉 = 4 given M = 5000 configurations. The couplings and magnetic fields are generated uniformly at random in the range [−1.0, −0.4] ∪ [0.4, 0.1] and [−0.3, 0.3], respectively. (A) The symmetrized estimate of coupling Ĵij associated with the edge (i, j) is obtained as an average of local estimates (Ĵij+Ĵji)/2. When the regularizing parameter λ is appropriately chosen and the number of samples is sufficient, gaps emerge in the estimated couplings Ĵij around δ+ > 0 and δ < 0, separating the estimated couplings that are close to zero and those with higher intensities in absolute value. The values below the threshold are then set to zero to obtain an estimate of the graph structure. (B) Once the graph structure is learned, the parameters are reestimated by optimizing the unregularized objective only over the edges in the reconstructed graph. The reduction in the number of free optimization variables from N to dmax + 1 greatly improves the estimates. The resulting values are shown in the scatter plot. (C) Empirical probability of successful structure recovery Pemp over L = 45 independent runs as a function of the number of samples M. For the logRISE, the smallest number of samples for which Pemp = 1 is given by M* = 5000.

  • Fig. 3 Verification of the logarithmic scaling with the size of the system.

    Scaling of M* with the number of spins N for (A) the logRISE and (B) the RPLE obtained using samples produced in the cases of the ferromagnetic Ising model over a double periodic two-dimensional lattice with β = 0.7 and ferromagnetic random regular graphs with degree d = 3 for β = 1.0. In all cases, we observe a logarithmic growth of M* with respect to N, which is in agreement with the information-theoretic bounds and our theoretical analysis for the estimators.

  • Fig. 4 Scaling of M* with the couplings strength.

    Comparison of the performance of the logRISE and the RPLE is presented for five different ensembles of Ising models. Because of a weak dependence M* ∝ ln N, we consider graphs of size N = 16, which allowed us to produce independent samples through an exhaustive enumeration of spin configurations. The first four cases correspond to (A) a ferromagnet on a square lattice with double-periodic boundary conditions, (B) a ferromagnet on a random 3-regular graph, (C) a spin glass on a periodic lattice, and (D) a spin glass on a random 3-regular graph. The most difficult reconstruction test case for both algorithms, a ferromagnetic lattice with a weak antiferromagnetic impurity, is presented in (E). The phase transition points in the corresponding infinite systems are indicated as βc. An exact pictorial representation of the corresponding Ising model is portrayed on the left-hand side of each plot. Ferromagnetic couplings equal to β and α = 0.4 are colored in orange and red, respectively. Antiferromagnetic couplings equal to −β and −α, respectively, are colored in turquoise and blue.

  • Fig. 5 Reconstruction of the structure of a portion of the D-Wave annealer chip using 5 × 105 samples.

    This part contains 62 qubits with heterogeneous connectivity, couplings, and magnetic fields. Reconstructed couplings are presented for (A) the logRISE, (B) the RPLE, and (C) the mean-field regime (MFR) of the RPLE and the logRISE. On each histogram in the main plots, bars corresponding to the edges actually present on the chip are colored in blue, whereas nonexistent connections are colored in red. The reconstructed magnetic fields are shown in green in a separate histogram on the right-hand side. A topology of the reconstructed structure is depicted on the left-hand side, with correctly reconstructed edges, missing edges, and incorrectly reconstructed edges colored in gray, blue, and red, respectively. Although the MFR exhibits a poor behavior, as expected at such low temperatures, both the logRISE and the RPLE are achieving similarly good performance. Notice that whereas there exists a thresholding procedure that produces a perfect network recovery with the logRISE, it is not the case for the RPLE as one existing coupling has been set to zero.

  • Fig. 6 Theoretical and empirical worst-case scaling of M* with respect to γ.

    This figure summarizes the main theoretical and empirical results of this paper for the inverse Ising problem. The red region represents the undersampled regime where the number of samples is insufficient for perfect graph reconstruction from the information theory perspective. The existence of an exact algorithm, albeit with an exponential computational complexity, has been proven for Me, and thus represents an upper bound on the optimal number of samples Mopt that must lie in the white region, named the optimal regime. The quantities e, e, and e10γ denote our theoretical upper bounds on the scaling for the RISE, the RPLE, and the logRISE, respectively. However, these bounds are not tight, and the worst-case empirical scalings observed in our numerical experiments were much lower; these values are indicated in the chart as “RISE,” “RPLE,” and “logRISE” and correspond to e4.5γ, e5.2γ, and e3.8γ, respectively (see the Supplementary Text for additional details on the scaling of the RISE). The empirical scaling for the logRISE lies within the optimal regime.

Supplementary Materials

  • Supplementary material for this article is available at http://advances.sciencemag.org/cgi/content/full/4/3/e1700791/DC1

    Supplementary Text

    section S1. Analysis of the estimators RPLE, RISE, and logRISE

    section S2. On optimization techniques for minimizing the estimators

    section S3. On the procedure for M* selection

    section S4. On the theoretical predictions for λ selection

    section S5. Empirical selection of the regularization parameter λ

    section S6. Hyperparameter λ selection through cross-validation

    section S7. Scalings of the RISE with respect to γ

    section S8. High-temperature expansion of the RISE and the RPLE

    fig. S1. Schematic representation of the proof strategy for bounding the reconstruction error.

    fig. S2. Dependence of the number of samples M* required for a correct structure recovery on the regularization coefficient.

    fig. S3. Selection of the hyperparameter λ through the K-fold cross-validation method on a 4 × 4 spin glass system on a square lattice.

    fig. S4. Values of M* and γ exponents for the RISE across different test cases.

    References (4245)

  • Supplementary Materials

    This PDF file includes:

    • Supplementary Text
    • section S1. Analysis of the estimators RPLE, RISE, and logRISE
    • section S2. On optimization techniques for minimizing the estimators
    • section S3. On the procedure for M* selection
    • section S4. On the theoretical predictions for λ selection
    • section S5. Empirical selection of the regularization parameter λ
    • section S6. Hyperparameter λ selection through cross-validation
    • section S7. Scalings of the RISE with respect to γ
    • section S8. High-temperature expansion of the RISE and the RPLE
    • fig. S1. Schematic representation of the proof strategy for bounding the reconstruction error.
    • fig. S2. Dependence of the number of samples M* required for a correct structure recovery on the regularization coefficient.
    • fig. S3. Selection of the hyperparameter λ through the K-fold cross-validation method on a 4 × 4 spin glass system on a square lattice.
    • fig. S4. Values of M* and γ exponents for the RISE across different test cases.
    • References (42–45)

    Download PDF

    Files in this Data Supplement:

Stay Connected to Science Advances

Navigate This Article