Bayesian networks are arguably the most popular and important model for representing dependencies between variables of multivariate probability distributions [1]}. A Bayesian network consists of a directed acyclic graph (DAG) \(D\)  and a set of conditional probability tables, one for each vertex of \(D\) . The vertices of the network are the variables of the distribution and each conditional probability table specifies the probability distribution of the corresponding vertex given the values of its parents. Thus, the value of each variable depends directly on the values of its parents. The graph \(D\)  is called the structure of the network. Given a set of observed data over some variable set \(N\) , one needs to learn the structure \(D\)  from this data. This is usually done in two steps. First, for each variable \(v\)  and each possible set of parents a parent score \(f_v(P)\)  is computed. Roughly speaking, the score represents how useful it is to choose this particular set of parents in order to accurately represent the probability distribution that created the observed data. Second, using the computed parent scores, we aim to compute the DAG that maximizes the sum of the parent scores of its vertices. This problem, called Bayesian Network Structure Learning (BNSL), is NP-hard [2]}.
