Abstract

The inclusion problem deals with how to characterize (in graphical terms) whether all independence statements in the model induced by a DAG K are in the model induced by the second DAG L. Meek (1997) had a conjecture that this inclusion holds iff there exists a sequence of DAGs from L to K such that only certain 'legal' arrow reversal and 'legal' arrow addition operations are performed to get the next graph in the sequence. In this paper, we give several characterizations of inclusion of DAG models and verify Meek's conjecture in the case that the DAGs K and L differ in at most one adjacency. As a warming up a rigourous proof of graphical characterizations of equivalence of DAGs is given.

AMS classification 68T30

Keywords

Bayesian network

dependence complex

equivalence of DAGs

inclusion problem

Meek's conjecture

A scanned pdf copy (1012kB) is available.

The paper builds on the following works:

• C. Meek: Graphical models, selecting causal and statistical models, PhD thesis, Carnegie Melon Univeristy 1997.
• D. M. Chickering: A transformational characterization of equivalent Bayesian networks In Uncertainty in Artificial Intelligence. Proceedings of the 11th Conference (P. Besnard, S. Hanks eds.), Morgan Kaufmann, pp. 87-98.
• T. Kocka, R. R. Bouckaert, M. Studeny: On the inclusion problem research report n. 2010, Institute of Information Theory and Automation, Prague, February 2001.