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

Chow-Liu treehigh-dimensional statisticsIsing modelMarkov random fieldsmaximum likelihood treemodel selectionpredictiontree model

Mathematics Subject Classification ID

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

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.

Review text

The objective of this paper is to show that learning a model that makes accurate predictions is possible even when structure learning is not. For realizing of this objective, the authors introduced a loss function to evaluate learning algorithms based on the accuracy of low-order marginals. The small-set total variation between true distribution \(P\) and learned distribution \(Q\) is used. The main result gives lower and upper bounds on the number of samples needed to learn a tree Ising model to ensure small \(L^{(2)}\) loss, which in this setting is equivalent to accurate pairwise marginals. In fact, the main result concerns the maximum likelihood tree (also called Chow-Liu tree, see [\textit{C. K. Chow} and \textit{C. N. Liu}, IEEE Trans. Inf. Theory 14, 462--467 (1968; Zbl 0165.22305)]. At the end of the paper, some interesting numerical simulations to demonstrate the performance of the Chow-Liu algorithm in terms of both the probability of incorrect recovery of underlying structure (zero-one loss) and the \(L^{(2)}\) loss are presented.

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

• A few logs suffice to build (almost) all trees. II
• A Large-Deviation Analysis of the Maximum-Likelihood Learning of Markov Tree Structures
• 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 graphs and variable selection with the Lasso
• High-dimensional Ising model selection using \(\ell _{1}\)-regularized logistic regression
• High-dimensional structure estimation in Ising models: local separation criterion
• 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?)
• 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 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 Markov networks: Maximum bounded tree-width graphs
• 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

(11)

• The minimax learning rates of normal and Ising undirected graphical models
• Bayesian model selection for high-dimensional Ising models, with applications to educational data
• Stein's method for stationary distributions of Markov chains and application to Ising models
• Predictive learning on hidden tree-structured Ising models
• Generative modeling via tree tensor network states
• Identifiability in robust estimation of tree structured models
• Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu
• Learning polynomial transformations via generalized tensor decompositions
• Tensor recovery in high-dimensional Ising models
• High dimensional logistic regression under network dependence
• On a risk model with tree-structured Poisson Markov random field frequency, with application to rainfall events

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)