# Active-LATHE: An Active Learning Algorithm for Boosting the Error Exponent for Learning Homogeneous Ising Trees

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 32 references that are in the map.
- First posted on arXiv 27 Oct 2021.

## Builds on (most cited first, 14 of 14)

- [Active Structure Learning of Causal DAGs via Directed Clique Tree](https://mlsanity.com/paper/2011.00641/) (2020)
- [Testing Ising Models](https://mlsanity.com/paper/1612.03147/) (2016)
- [Near-Optimal Learning of Tree-Structured Distributions by Chow-Liu](https://mlsanity.com/paper/2011.04144/) (2020)
- [Learning a Tree-Structured Ising Model in Order to Make Predictions](https://mlsanity.com/paper/1604.06749/) (2016)
- [Chow-Liu++: Optimal Prediction-Centric Learning of Tree Ising Models](https://mlsanity.com/paper/2106.03969/) (2021)
- [Active Learning Algorithms for Graphical Model Selection](https://mlsanity.com/paper/1602.00354/) (2016)
- [Predictive Learning on Hidden Tree-Structured Ising Models](https://mlsanity.com/paper/1812.04700/) (2018)
- [SGA: A Robust Algorithm for Partial Recovery of Tree-Structured Graphical Models with Noisy Samples](https://mlsanity.com/paper/2101.08917/) (2021)
- [Exact Asymptotics for Learning Tree-Structured Graphical Models with Side Information: Noiseless and Noisy Samples](https://mlsanity.com/paper/2005.04354/) (2020)
- [Active Structure Learning of Bayesian Networks in an Observational Setting](https://mlsanity.com/paper/2103.13796/) (2021)
- [Property Testing in High Dimensional Ising models](https://mlsanity.com/paper/1709.06688/) (2017)
- [Active Learning for Undirected Graphical Model Selection](https://mlsanity.com/paper/1404.3418/) (2014)
- [Lower Bounds on Active Learning for Graphical Model Selection](https://mlsanity.com/paper/1607.02413/) (2016)
- [Robustifying Algorithms of Learning Latent Trees with Vector Variables](https://mlsanity.com/paper/2106.00885/) (2021)

## Abstract (arXiv)

The Chow-Liu algorithm (IEEE Trans.~Inform.~Theory, 1968) has been a mainstay for the learning of tree-structured graphical models from i.i.d. sampled data vectors. Its theoretical properties have been well-studied and are well-understood. In this paper, we focus on the class of trees that are arguably even more fundamental, namely em homogeneous trees in which each pair of nodes that forms an edge has the same correlation ρ. We ask whether we are able to further reduce the error probability of learning the structure of the homogeneous tree model when em active learning or em active sampling of nodes or variables is allowed. Our figure of merit is the em error exponent, which quantifies the exponential rate of decay of the error probability with an increasing number of data samples. At first sight, an improvement in the error exponent seems impossible, as all the edges are statistically identical. We design and analyze an algorithm Active Learning Algorithm for Trees with Homogeneous Edge (Active-LATHE), which surprisingly boosts the error exponent by at least 40% when ρ is at least 0.8. For all other values of ρ, we also observe commensurate, but more modest, improvements in the error exponent. Our analysis hinges on judiciously exploiting the minute but detectable statistical variation of the samples to allocate more data to parts of the graph in which we are less confident of being correct.