Finding optimal bayesian networks

In this paper, we derive optimality results for greedy Bayesian-network search algo-rithms that perform single-edge modica-tions at each step and use asymptotically consistent scoring criteria. Our results ex-tend those of Meek (1997) and Chickering (2002), who demonstrate that in the limit of large datasets, if the generative distribution is perfect with respect to a DAG dened over the observable variables, such search algo-rithms will identify this optimal (i.e. gener-atve) DAGmodel. We relax their assumption about the generative distribtion, and assume only that this distribution satises the com-position property over the observable vari-ables, which is a more realistic assumption for real domains. Under this assumption, we guarantee that the search algorithms identify an inclusion-optimal model; that is, a model that (1) contains the generative distribution and (2) has no sub-model that contains this distribution. In addition, we show that the composition property is guaranteed to hold whenever the dependence relationships in the generative distribution can be characterized by paths between singleton elements in some generative graphical model (e.g. a DAG, a chain graph, or a Markov network) even when we allow the generative model to include un-observed variables, and the observed data to be subject to selection bias.