zbMATH — the first resource for mathematics

On the incompatibility of faithfulness and monotone DAG faithfulness. (English) Zbl 1131.68082
Summary: J. Cheng, R. Greiner, J. Kelly, D. Bell and W. Liu [Artif. Intell. 137, No. 1–2, 43–90 (2002; Zbl 0995.68114)] describe an algorithm for learning Bayesian networks that – in a domain consisting of $$n$$ variables – identifies the optimal solution using $$O(n^4)$$ calls to a mutual-information oracle. This result relies on (1) the standard assumption that the generative distribution is Markov and faithful to some directed acyclic graph (DAG), and (2) a new assumption about the generative distribution that the authors call monotone DAG faithfulness (MDF). The MDF assumption rests on an intuitive connection between active paths in a Bayesian-network structure and the mutual information among variables. The assumption states that the (conditional) mutual information between a pair of variables is a monotonic function of the set of active paths between those variables; the more active paths between the variables the higher the mutual information. In this paper, we demonstrate the unfortunate result that, for any realistic learning scenario, the monotone DAG faithfulness assumption is incompatible with the faithfulness assumption. Furthermore, for the class of Bayesian-network structures for which the two assumptions are compatible, we can learn the optimal solution using standard approaches that require only $$O(n^2)$$ calls to an independence oracle.

MSC:
 68T05 Learning and adaptive systems in artificial intelligence