On the Number of Samples Needed to Learn the Correct Structure of a
  Bayesian Network
  Bayesian Networks (BNs) are useful tools giving a natural and compact
representation of joint probability distributions. In many applications one
needs to learn a Bayesian Network (BN) from data. In this context, it is
important to understand the number of samples needed in order to guarantee a
successful learning. Previous work have studied BNs sample complexity, yet it
mainly focused on the requirement that the learned distribution will be close
to the original distribution which generated the data. In this work, we study a
different aspect of the learning, namely the number of samples needed in order
to learn the correct structure of the network. We give both asymptotic results,
valid in the large sample limit, and experimental results, demonstrating the
learning behavior for feasible sample sizes. We show that structure learning is
a more difficult task, compared to approximating the correct distribution, in
the sense that it requires a much larger number of samples, regardless of the
computational power available for the learner.
