## Abstract

We provide high-probability sample complexity guarantees for exact structure recovery of tree-structured graphical models, when only noisy observations of the respective vertex emissions are available. We assume that the hidden variables follow either an Ising model or a Gaussian graphical model, and the observables are noise-corrupted versions of the hidden variables: We consider multiplicative ±1 binary noise for Ising models, and additive Gaussian noise for Gaussian models. Such hidden models arise naturally in a variety of applications such as physics, biology, computer science, and finance. We study the impact of measurement noise on the task of learning the underlying tree structure via the well-known Chow-Liu algorithm, and provide formal sample complexity guarantees for exact recovery. In particular, for a tree with p vertices and probability of failure δ > 0, we show that the number of necessary samples for exact structure recovery is of the order of O(log(p/δ)) for Ising models (which remains the same as in the noiseless case), and O(polylog(p/δ)) for Gaussian models.

Original language | English (US) |
---|---|

State | Published - 2020 |

Event | 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019 - Naha, Japan Duration: Apr 16 2019 → Apr 18 2019 |

### Conference

Conference | 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019 |
---|---|

Country/Territory | Japan |

City | Naha |

Period | 4/16/19 → 4/18/19 |

## All Science Journal Classification (ASJC) codes

- Artificial Intelligence
- Statistics and Probability