Efficiently learning Ising models on arbitrary graphs (extended abstract)
From MaRDI portal
Abstract: We consider the problem of reconstructing the graph underlying an Ising model from i.i.d. samples. Over the last fifteen years this problem has been of significant interest in the statistics, machine learning, and statistical physics communities, and much of the effort has been directed towards finding algorithms with low computational cost for various restricted classes of models. Nevertheless, for learning Ising models on general graphs with nodes of degree at most , it is not known whether or not it is possible to improve upon the computation needed to exhaustively search over all possible neighborhoods for each node. In this paper we show that a simple greedy procedure allows to learn the structure of an Ising model on an arbitrary bounded-degree graph in time on the order of . We make no assumptions on the parameters except what is necessary for identifiability of the model, and in particular the results hold at low-temperatures as well as for highly non-uniform models. The proof rests on a new structural property of Ising models: we show that for any node there exists at least one neighbor with which it has a high mutual information. This structural property may be of independent interest.
Recommendations
- The minimax learning rates of normal and Ising undirected graphical models
- Learning planar Ising models
- High-dimensional Ising model selection using \(\ell _{1}\)-regularized logistic regression
- Learning loosely connected Markov random fields
- High-dimensional structure estimation in Ising models: local separation criterion
Cites work
- Approximate distance oracles
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Fast C-K-R partitions of sparse graphs
- Near-Linear Time Construction of Sparse Neighborhood Covers
- On approximate distance labels and routing schemes with affine stretch
- On sparse spanners of weighted graphs
- Ramsey partitions and proximity data structures
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- Shortest-path queries in static networks
Cited in
(45)- Estimating the interaction graph of stochastic neural dynamics
- Fluctuations for block spin Ising models
- Fluctuation results for general block spin Ising models
- A global approach for learning sparse Ising models
- On testing for parameters in Ising models
- Multi-group binary choice with social interaction and a random communication structure -- a random graph approach
- Exact recovery in block spin Ising models at the critical line
- The minimax learning rates of normal and Ising undirected graphical models
- Learning a tree-structured Ising model in order to make predictions
- Joint estimation of parameters in Ising model
- Exact recovery in the Ising blockmodel
- Property testing in high-dimensional Ising models
- Identifying interacting pairs of sites in Ising models on a countable set
- Universality of the mean-field for the Potts model
- Learning planar Ising models
- Learning factor graphs in polynomial time and sample complexity
- Spectral bounds for the Ising ferromagnet on an arbitrary given graph
- Structure learning in inverse Ising problems using ℓ 2-regularized linear estimator
- The one-inclusion graph algorithm is near-optimal for the prediction model of learning
- Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models
- Structure learning of \(H\)-colorings
- Predictive learning on hidden tree-structured Ising models
- Efficient learning of discrete graphical models*
- Ising model selection using ℓ 1-regularized linear regression: a statistical mechanics analysis*
- An expectation maximization algorithm for high-dimensional model selection for the Ising model with misclassified states*
- High-temperature structure detection in ferromagnets
- Hardness of identity testing for restricted Boltzmann machines and Potts models
- Learning loosely connected Markov random fields
- Tractable minor-free generalization of planar zero-field Ising models
- Reconstruction of Markov random fields from samples: some observations and algorithms
- Region selection in Markov random fields: Gaussian case
- Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu
- Detecting structured signals in Ising models
- Learning polynomial transformations via generalized tensor decompositions
- Explicit, identical maximum likelihood estimates for some cyclic Gaussian and cyclic Ising models
- Tensor recovery in high-dimensional Ising models
- One-shot learning for k-SAT
- Limit theorems and phase transitions in the tensor Curie-Weiss Potts model
- On sampling from Ising models with spectral constraints
- High-dimensional structure estimation in Ising models: local separation criterion
- High dimensional logistic regression under network dependence
- Phase transitions of the maximum likelihood estimators in the p-spin Curie-Weiss model
- Inferring the dependence graph density of binary graphical models in high dimension
- Polynomial-time derivation of optimal k-tree topology from Markov networks
- One-shot learning for \(k\)-SAT
This page was built for publication: Efficiently learning Ising models on arbitrary graphs (extended abstract)
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941573)
