T. Kocka, R. R. Bouckaert, M. Studeny:
On characterizing inclusion of Bayesian networks.
In Uncertainty in Artificial Intelligence.
Proceedings of the 17th Conference
(J. Breese, D. Koller eds.), Morgan Kaufmann, San Francisco 2001, pp. 261-268.
- 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
- Bayesian network
- dependence complex
- equivalence of DAGs
- inclusion problem
- Meek's conjecture
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,
- T. Kocka, R. R. Bouckaert, M. Studeny:
On the inclusion problem
research report n. 2010, Institute of Information Theory
and Automation, Prague, February 2001.