Learning a tree-structured Ising model in order to make predictions

DOI10.1214/19-AOS1808MaRDI QIDQ2196190zbMATH OpenFDO

Authors Guy Bresler, Mina Karzand

Publication date 28 August 2020

Published in The Annals of Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.06749, https://projecteuclid.org/euclid.aos/1590480031

zbMATH Keywords

model selectionpredictionhigh-dimensional statisticsIsing modelMarkov random fieldstree modelChow-Liu treemaximum likelihood tree

Mathematics Subject Classification ID

Asymptotic properties of parametric estimators (62F12) Time series, auto-correlation, regression, etc. in statistics (GARCH) (62M10) Learning and adaptive systems in artificial intelligence (68T05) Estimation in multivariate analysis (62H12) Inference from stochastic processes and prediction (62M20) (L^p)-limit theorems (60F25)

Abstract: We study the problem of learning a tree Ising model from samples such that subsequent predictions made using the model are accurate. The prediction task considered in this paper is that of predicting the values of a subset of variables given values of some other subset of variables. Virtually all previous work on graphical model learning has focused on recovering the true underlying graph. We define a distance ("small set TV" or ssTV) between distributions $P$ and $Q$ by taking the maximum, over all subsets $mathcalS$ of a given size, of the total variation between the marginals of $P$ and $Q$ on $mathcalS$; this distance captures the accuracy of the prediction task of interest. We derive non-asymptotic bounds on the number of samples needed to get a distribution (from the same class) with small ssTV relative to the one generating the samples. One of the main messages of this paper is that far fewer samples are needed than for recovering the underlying tree, which means that accurate predictions are possible using the wrong tree.

Recommendations

• Efficiently learning Ising models on arbitrary graphs (extended abstract)
• The minimax learning rates of normal and Ising undirected graphical models
• Learning planar Ising models
• scientific article; zbMATH DE number 6253918
• Robust inference of trees

Cites work

• scientific article; zbMATH DE number 3174791 (Why is no real title available?)
• scientific article; zbMATH DE number 4037789 (Why is no real title available?)
• scientific article; zbMATH DE number 1134987 (Why is no real title available?)
• scientific article; zbMATH DE number 6253918 (Why is no real title available?)
• A Large-Deviation Analysis of the Maximum-Likelihood Learning of Markov Tree Structures
• A few logs suffice to build (almost) all trees. II
• Approximating discrete probability distributions with dependence trees
• Can local particle filters beat the curse of dimensionality?
• Efficiently learning Ising models on arbitrary graphs (extended abstract)
• Estimating the ``wrong graphical model: benefits in the computation-limited setting
• Forest density estimation
• Gibbs measures and phase transitions.
• Graphical models, exponential families, and variational inference
• High-dimensional Ising model selection using \(\ell _{1}\)-regularized logistic regression
• High-dimensional graphs and variable selection with the Lasso
• High-dimensional structure estimation in Ising models: local separation criterion
• Image denoising using scale mixtures of gaussians in the wavelet domain
• Information-Theoretic Limits of Selecting Binary Graphical Models in High Dimensions
• Introduction to algorithms.
• Introduction to nonparametric estimation
• Learning Markov networks: Maximum bounded tree-width graphs
• Learning factor graphs in polynomial time and sample complexity
• Learning loopy graphical models with latent variables: efficient methods and guarantees
• Learning loosely connected Markov random fields
• Learning low-level vision
• Learning with mixtures of trees.
• On the Approximability of Numerical Taxonomy (Fitting Distances by Tree Metrics)
• Phylogenies without branch bounds: contracting the short, pruning the deep
• Probabilistic graphical models.
• Probability Inequalities for Sums of Bounded Random Variables
• Random cascades on wavelet trees and their use in analyzing and modeling natural images
• Reconstruction of Markov Random Fields from Samples: Some Observations and Algorithms
• Structure estimation for discrete graphical models: generalized covariance matrices and their inverses

Cited in

(9)

• Stein's method for stationary distributions of Markov chains and application to Ising models
• Generative modeling via tree tensor network states
• Identifiability in robust estimation of tree structured models
• Learning polynomial transformations via generalized tensor decompositions
• The minimax learning rates of normal and Ising undirected graphical models
• Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu
• Tensor recovery in high-dimensional Ising models
• Bayesian model selection for high-dimensional Ising models, with applications to educational data
• scientific article; zbMATH DE number 7370576 (Why is no real title available?)

This page was built for publication: Learning a tree-structured Ising model in order to make predictions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2196190)