# Learning a Tree-Structured Ising Model in Order to Make Predictions

arXiv: https://arxiv.org/abs/1604.06749 · HTML: https://mlsanity.com/paper/1604.06749/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Apr 2016.

## Built on by (most cited first, 15 of 15)

- [A Unified Approach to Learning Ising Models: Beyond Independence and Bounded Width](https://mlsanity.com/paper/2311.09197/) (2023)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Bypassing the Noisy Parity Barrier: Learning Higher-Order Markov Random Fields from Dynamics](https://mlsanity.com/paper/2409.05284/) (2024)
- [Learning and Testing Latent-Tree Ising Models Efficiently](https://mlsanity.com/paper/2211.13291/) (2022)
- [SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples](https://mlsanity.com/paper/2101.08917/) (2021)
- [Generative Modeling via Tree Tensor Network States](https://mlsanity.com/paper/2209.01341/) (2022)
- [Robust estimation of tree structured models](https://mlsanity.com/paper/2102.05472/) (2021)
- [Estimating Ising Models in Total Variation Distance](https://mlsanity.com/paper/2511.21008/) (2025)
- [Learning Linear Polytree Structural Equation Models](https://mlsanity.com/paper/2107.10955/) (2021)
- [Recoverability Landscape of Tree Structured Markov Random Fields under Symmetric Noise](https://mlsanity.com/paper/2102.08554/) (2021)
- [Decentralized Learning of Tree-Structured Gaussian Graphical Models from Noisy Data](https://mlsanity.com/paper/2109.10642/) (2021)
- [Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees](https://mlsanity.com/paper/2110.14341/) (2021)
- [Interaction Screening and Pseudolikelihood Approaches for Tensor Learning in Ising Models](https://mlsanity.com/paper/2310.13232/) (2023)
- [Efficient Sample-optimal Learning of Gaussian Tree Models via Sample-optimal Testing of Gaussian Mutual Information](https://mlsanity.com/paper/2411.11516/) (2024)
- [Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure](https://mlsanity.com/paper/2609.37841/) (2026)

## Abstract (arXiv)

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 S of a given size, of the total variation between the marginals of P and Q on S; 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.