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.

68T05 Learning and adaptive systems in artificial intelligence
Full Text: DOI
[1] Cheng, J.; Greiner, R.; Kelly, J.; Bell, D.; Liu, W., Learning Bayesian networks from data: an information-theory based approach, Artificial intelligence, 137, 43-90, (2002) · Zbl 0995.68114
[2] Chickering, D.M.; Meek, C.; Heckerman, D., Large-sample learning of Bayesian networks is NP-hard, Journal of machine learning research, 5, 1287-1330, (2004) · Zbl 1222.68169
[3] Cover, T.M.; Thomas, J.A., Elements of information theory, (1991), John Wiley and Sons Inc., New York · Zbl 0762.94001
[4] Meek, C., Strong-completeness and faithfulness in belief networks, (), 411-418
[5] Pearl, J., Probabilistic reasoning in intelligent systems: networks of plausible inference, (1988), Morgan Kaufmann San Mateo, CA
[6] Spirtes, P.; Glymour, C.; Scheines, R., Causation, prediction, and search, (2000), MIT Press Cambridge, MA · Zbl 0806.62001
[7] T. Verma, J. Pearl, Equivalence and synthesis of causal models, in: M. Henrion, R. Shachter, L. Kanal, J. Lemmer (Eds.), Proceedings of the Sixth Conference on Uncertainty in Artificial Intelligence, 1991, pp. 220-227
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.