Discovering Hidden Variables in Noisy-Or Networks using Quartet Tests

Abstract

We give a polynomial-time algorithm for provably learning the structure and parameters of bipartite noisy-or Bayesian networks of binary variables where the top layer is completely hidden. Unsupervised learning of these models is a form of discrete factor analysis, enabling the discovery of hidden variables and their causal relationships with observed data. We obtain an efficient learning algorithm for a family of Bayesian networks that we call quartet-learnable. For each latent variable, the existence of a singly-coupled quartet allows us to uniquely identify and learn all parameters involving that latent variable. We give a proof of the polynomial sample complexity of our learning algorithm, and experimentally compare it to variational EM.

Publication
Advances in Neural Information Processing Systems 26
Yacine Jernite
Yacine Jernite
PhD student

Research Scientist, Hugging Face

Yoni Halpern
Yoni Halpern
PhD student

Google Research

David Sontag
David Sontag
Professor of EECS

My research focuses on advancing machine learning and artificial intelligence, and using these to transform health care.

Related