Discovering Hidden Variables in Noisy-Or Networks using Quartet Tests
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.
The paper discusses parameter estimation and two 
      versions of quartet-based structure learning algorithms for bipartite 
      noisy-or networks of binary variables. The presented ideas are based on a 
      recent paper [Halpern & Sontag, 2013], extending to a more general 
      class of networks. The performance of the proposed algorithm is 
      illustrated on synthetic examples. The exposition of paper is generally 
      logical but the writing needs a lot of improvement. The paper 
      contains potentially interesting algorithms but it is at times hard to 
      tell which ideas are new and which ones are borrowed. A summary of the 
      main contributions and their significance would be useful. What are the 
      real applications of the algorithm, for which existing algorithms would 
      not be applicable? * Main concerns: -- Experiments: The 
      authors list a number of practical applications but the performed 
      experiments are rather limited. -- Exposition: There are too many 
      missing definitions, missing essential information (e.g., the algorithm by 
      Halpern & Sontag ), inconsistent notation, and wrong pointers to other 
      parts of the text. If this paper is accepted, I hope the authors take the 
      task of improving the text seriously. * Additional remarks: -- 
      Rank test: How practical is the epsilon-rank-testability assumption? In 
      what applications would it be satisfied (with large epsilon)? Can epsilon 
      be estimated from the data? -- Definition 2: Please explain what you 
      mean by "the third eigenvalue of ... is at least epsilon" if the 
      eigenvalues are not necessary nonnegative real numbers. -- Coherence 
      test: For each quartet, 4 sets of parameters have to be estimated. State 
      the computational cost of this estimation. "If the parameters learned do 
      not agree" should be further explained. -- The recent tensor 
      decomposition method [Halpern & Sontag] seems to be an important part 
      of the proposed algorithms and should at least briefly be explained. 
      -- The definition of noisy-or networks could be more thorough. -- 
      Some notation updates are required, e.g., on p.2, U stands for a set of 
      latent variables but on p.3 U is used to describe a set of observed 
      variables. -- Figure 3 has wrong caption. Generally, Section 3 looks 
      like it suffered last minute restructuring. -- Figure 2 should come 
      later, around the place it is referred to. The algorithms should probably 
      not be called figures. -- Thorough proofreading is necessary. There 
      are multiple typos and missing references to figures and sections (in the 
      main file and in the supplementary material).