Learning Bayesian and Markov Networks with an Unreliable Oracle
This addresses a fundamental challenge in probabilistic graphical model learning for researchers and practitioners, but it is incremental as it builds on existing constraint-based methods.
The paper tackles the problem of learning Bayesian and Markov network structures with an unreliable oracle that makes bounded errors, showing that Markov networks are uniquely identifiable under certain conditions even with exponential errors, while Bayesian networks cannot tolerate any errors for guaranteed identification.
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.