Search papers, labs, and topics across Lattice.
This paper analyzes the identifiability of Markov and Bayesian networks using constraint-based structure learning with an unreliable conditional independence oracle. It shows that Markov network structure is uniquely identifiable with a moderately exponential number of oracle errors when the maximum number of vertex-wise disjoint paths is low. However, for Bayesian networks, the paper proves that even a single oracle error prevents the unique identification of the structure, even with bounded graph parameters like treewidth.
Even a single error from a conditional independence oracle can prevent the unique identification of a Bayesian network structure, regardless of bounded graph parameters like treewidth.
We study constraint-based structure learning of Markov networks and Bayesian networks in the presence of an unreliable conditional independence oracle that makes at most a bounded number of errors. For Markov networks, we observe that a low maximum number of vertex-wise disjoint paths implies that the structure is uniquely identifiable even if the number of errors is (moderately) exponential in the number of vertices. For Bayesian networks, however, we prove that one cannot tolerate any errors to always identify the structure even when many commonly used graph parameters like treewidth are bounded. Finally, we give algorithms for structure learning when the structure is uniquely identifiable.
