skip to main content
Explore Scholarly Publications and Datasets in the NSF-PAR

Title: Estimation in tensor Ising models
Abstract The $p$-tensor Ising model is a one-parameter discrete exponential family for modeling dependent binary data, where the sufficient statistic is a multi-linear form of degree $p \geqslant 2$. This is a natural generalization of the matrix Ising model that provides a convenient mathematical framework for capturing, not just pairwise, but higher-order dependencies in complex relational data. In this paper, we consider the problem of estimating the natural parameter of the $p$-tensor Ising model given a single sample from the distribution on $N$ nodes. Our estimate is based on the maximum pseudolikelihood (MPL) method, which provides a computationally efficient algorithm for estimating the parameter that avoids computing the intractable partition function. We derive general conditions under which the MPL estimate is $\sqrt N$-consistent, that is, it converges to the true parameter at rate $1/\sqrt N$. Our conditions are robust enough to handle a variety of commonly used tensor Ising models, including spin glass models with random interactions and models where the rate of estimation undergoes a phase transition. In particular, this includes results on $\sqrt N$-consistency of the MPL estimate in the well-known $p$-spin Sherrington–Kirkpatrick model, spin systems on general $p$-uniform hypergraphs and Ising models on the hypergraph stochastic block more » model (HSBM). In fact, for the HSBM we pin down the exact location of the phase transition threshold, which is determined by the positivity of a certain mean-field variational problem, such that above this threshold the MPL estimate is $\sqrt N$-consistent, whereas below the threshold no estimator is consistent. Finally, we derive the precise fluctuations of the MPL estimate in the special case of the $p$-tensor Curie–Weiss model, which is the Ising model on the complete $p$-uniform hypergraph. An interesting consequence of our results is that the MPL estimate in the Curie–Weiss model saturates the Cramer–Rao lower bound at all points above the estimation threshold, that is, the MPL estimate incurs no loss in asymptotic statistical efficiency in the estimability regime, even though it is obtained by minimizing only an approximation of the true likelihood function for computational tractability. « less
Authors:
; ;
Award ID(s):
2046393
Publication Date:
NSF-PAR ID:
10333719
Journal Name:
Information and Inference: A Journal of the IMA
ISSN:
2049-8772
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ( , Journal of Optical Communications and Networking)

    Estimating the quality of transmission (QoT) of a lightpath before its establishment is a critical procedure for efficient design and management of optical networks. Recently, supervised machine learning (ML) techniques for QoT estimation have been proposed as an effective alternative to well-established, yet approximated, analytic models that often require the introduction of conservative margins to compensate for model inaccuracies and uncertainties. Unfortunately, to ensure high estimation accuracy, the training set (i.e., the set of historical field data, or “samples,” required to train these supervised ML algorithms) must be very large, while in real network deployments, the number of monitored/monitorable lightpaths is limited by several practical considerations. This is especially true for lightpaths with an above-threshold bit error rate (BER) (i.e., malfunctioning or wrongly dimensioned lightpaths), which are infrequently observed during network operation. Samples with above-threshold BERs can be acquired by deploying probe lightpaths, but at the cost of increased operational expenditures and wastage of spectral resources. In this paper, we propose to useactive learningto reduce the number of probes needed for ML-based QoT estimation. We build an estimation model based on Gaussian processes, which allows iterative identification of those QoT instances that minimize estimation uncertainty. Numerical results using syntheticallymore »generated datasets show that, by using the proposed active learning approach, we can achieve the same performance of standard offline supervised ML methods, but with a remarkable reduction (at least 5% and up to 75%) in the number of training samples.

    « less
  2. ; ( , Leibniz international proceedings in informatics)
    We consider the problem of space-efficiently estimating the number of simplices in a hypergraph stream. This is the most natural hypergraph generalization of the highly-studied problem of estimating the number of triangles in a graph stream. Our input is a k-uniform hypergraph H with n vertices and m hyperedges, each hyperedge being a k-sized subset of vertices. A k-simplex in H is a subhypergraph on k+1 vertices X such that all k+1 possible hyperedges among X exist in H. The goal is to process the hyperedges of H, which arrive in an arbitrary order as a data stream, and compute a good estimate of T_k(H), the number of k-simplices in H. We design a suite of algorithms for this problem. As with triangle-counting in graphs (which is the special case k = 2), sublinear space is achievable but only under a promise of the form T_k(H) ≥ T. Under such a promise, our algorithms use at most four passes and together imply a space bound of O(ε^{-2} log δ^{-1} polylog n ⋅ min{(m^{1+1/k})/T, m/(T^{2/(k+1)})}) for each fixed k ≥ 3, in order to guarantee an estimate within (1±ε)T_k(H) with probability ≥ 1-δ. We also give a simpler 1-pass algorithm thatmore »achieves O(ε^{-2} log δ^{-1} log n⋅ (m/T) (Δ_E + Δ_V^{1-1/k})) space, where Δ_E (respectively, Δ_V) denotes the maximum number of k-simplices that share a hyperedge (respectively, a vertex), which generalizes a previous result for the k = 2 case. We complement these algorithmic results with space lower bounds of the form Ω(ε^{-2}), Ω(m^{1+1/k}/T), Ω(m/T^{1-1/k}) and Ω(mΔ_V^{1/k}/T) for multi-pass algorithms and Ω(mΔ_E/T) for 1-pass algorithms, which show that some of the dependencies on parameters in our upper bounds are nearly tight. Our techniques extend and generalize several different ideas previously developed for triangle counting in graphs, using appropriate innovations to handle the more complicated combinatorics of hypergraphs.« less
  3. ; ( , Scientific Reports)
    Abstract The Ising model provides a natural mapping for many computationally hard combinatorial optimization problems (COPs). Consequently, dynamical system-inspired computing models and hardware platforms that minimize the Ising Hamiltonian, have recently been proposed as a potential candidate for solving COPs, with the promise of significant performance benefit. However, prior work on designing dynamical systems as Ising machines has primarily considered quadratic interactions among the nodes. Dynamical systems and models considering higher order interactions among the Ising spins remain largely unexplored, particularly for applications in computing. Therefore, in this work, we propose Ising spin-based dynamical systems that consider higher order (> 2) interactions among the Ising spins, which subsequently, enables us to develop computational models to directly solve many COPs that entail such higher order interactions (i.e., COPs on hypergraphs). Specifically, we demonstrate our approach by developing dynamical systems to compute the solution for the Boolean NAE-K-SAT (K ≥ 4) problem as well as solve the Max-K-Cut of a hypergraph. Our work advances the potential of the physics-inspired ‘toolbox’ for solving COPs.
  4. ; ; ( , Acta Crystallographica Section B Structural Science, Crystal Engineering and Materials)
    The synthesis, crystal structure determination, magnetic properties and bonding interaction analysis of a novel 3 d transition-metal complex, [CrBr 2 (NCCH 3 ) 4 ](Br 3 ), are reported. Single-crystal X-ray diffraction results show that [CrBr 2 (NCCH 3 ) 4 ](Br 3 ) crystallizes in space group C 2/ m (No. 12) with a symmetric tribromide anion and the powder X-ray diffraction results show the high purity of the material specimen. X-ray photoelectron studies with a combination of magnetic measurements demonstrate that Cr adopts the 3+ oxidation state. Based on the Curie–Weiss analysis of magnetic susceptibility data, the Néel temperature is found to be around 2.2 K and the effective moment (μ eff ) of Cr 3+ in [CrBr 2 (NCCH 3 ) 4 ](Br 3 ) is ∼3.8 µ B , which agrees with the theoretical value for Cr 3+ . The direct current magnetic susceptibility of the molecule shows a broad maximum at ∼2.3 K, which is consistent with the theoretical Néel temperature. The maximum temperature, however, shows no clear frequency dependence. Combined with the observed upturn in heat capacity below 2.3 K and the corresponding field dependence, it is speculated that the low-temperature magnetic feature of a broad transition inmore »[CrBr 2 (NCCH 3 ) 4 ](Br 3 ) could originate from a crossover from high spin to low spin for the split d orbital level low-lying states rather than a short-range ordering solely; this is also supported by the molecular orbital diagram obtained from theoretical calculations.« less
  5. ; ; ; ( , Systematic Biology)
    Abstract

    A potential shortcoming of concatenation methods for species tree estimation is their failure to account for incomplete lineage sorting. Coalescent methods address this problem but make various assumptions that, if violated, can result in worse performance than concatenation. Given the challenges of analyzing DNA sequences with both concatenation and coalescent methods, retroelement insertions (RIs) have emerged as powerful phylogenomic markers for species tree estimation. Here, we show that two recently proposed quartet-based methods, SDPquartets and ASTRAL_BP, are statistically consistent estimators of the unrooted species tree topology under the coalescent when RIs follow a neutral infinite-sites model of mutation and the expected number of new RIs per generation is constant across the species tree. The accuracy of these (and other) methods for inferring species trees from RIs has yet to be assessed on simulated data sets, where the true species tree topology is known. Therefore, we evaluated eight methods given RIs simulated from four model species trees, all of which have short branches and at least three of which are in the anomaly zone. In our simulation study, ASTRAL_BP and SDPquartets always recovered the correct species tree topology when given a sufficiently large number of RIs, as predicted. A distance-basedmore »method (ASTRID_BP) and Dollo parsimony also performed well in recovering the species tree topology. In contrast, unordered, polymorphism, and Camin–Sokal parsimony (as well as an approach based on MDC) typically fail to recover the correct species tree topology in anomaly zone situations with more than four ingroup taxa. Of the methods studied, only ASTRAL_BP automatically estimates internal branch lengths (in coalescent units) and support values (i.e., local posterior probabilities). We examined the accuracy of branch length estimation, finding that estimated lengths were accurate for short branches but upwardly biased otherwise. This led us to derive the maximum likelihood (branch length) estimate for when RIs are given as input instead of binary gene trees; this corrected formula produced accurate estimates of branch lengths in our simulation study provided that a sufficiently large number of RIs were given as input. Lastly, we evaluated the impact of data quantity on species tree estimation by repeating the above experiments with input sizes varying from 100 to 100,000 parsimony-informative RIs. We found that, when given just 1000 parsimony-informative RIs as input, ASTRAL_BP successfully reconstructed major clades (i.e., clades separated by branches $>0.3$ coalescent units) with high support and identified rapid radiations (i.e., shorter connected branches), although not their precise branching order. The local posterior probability was effective for controlling false positive branches in these scenarios. [Coalescence; incomplete lineage sorting; Laurasiatheria; Palaeognathae; parsimony; polymorphism parsimony; retroelement insertions; species trees; transposon.]

    « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email