Learning tree structures from noisy data

Konstantinos E. Nikolakakis, Dionysios S. Kalogerias, Anand D. Sarwate

Research output: Contribution to conferencePaperpeer-review

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 languageEnglish (US)
StatePublished - 2020
Event22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019 - Naha, Japan
Duration: Apr 16 2019Apr 18 2019

Conference

Conference22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019
Country/TerritoryJapan
CityNaha
Period4/16/194/18/19

All Science Journal Classification (ASJC) codes

  • Artificial Intelligence
  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Learning tree structures from noisy data'. Together they form a unique fingerprint.

Cite this