## Preliminaries  
### Problem of BN Structure Learning  
A BN is a graphical tool to represent the \(n\)-dimensional probability distribution. It can be described by a directed acyclic graph (DAG) \(G\leq X\), \(A\), \(\Theta\)\(>\). In \(G\), each node \(X_{i}\)\(\in\)\(X\) represents a random variable of interest, while each arc \(a_{ij}\)\(\in\)\(A\) represents a direct dependence relationship between the variables \(X_{i}\) and \(X_{j}\). In addition, the parameter \(\theta_{i}=P(X_{i}\mid\pi_{i})\), where \(\Theta=\{\theta_{i}\}\), denotes the conditional probability distribution of \(X_{i}\) given its parent set \(\pi_{i}\). From the conditional distributions, the joint probability can be uniquely determined by  
\[P(X_{1},X_{2},\cdots,X_{n})=\prod_{i=1}^{n}P(X_{i}|\pi_{i}). \tag{1}\]Given a training database \(D=\{\textbf{x}^{1},\textbf{x}^{2},\ldots,\textbf{x}^{m}\}\) composed of \(m\) cases and each case contains \(n\) variables, where \(\textbf{x}^{i}\) is an instance of domain variable \(X\), the problem of the BN structure learning is to find the BN topology structure that best matches the dataset \(D\). As noted previously, algorithms for learning the BN structure from data mainly include the constraint-based methods and the score+search methods. Based on a dependency analysis, the existing approaches are close to the semantics of BNs and relatively simpler to implement [8]. However, it is hard to ensure the precision of the obtained structure. Furthermore, the computation for high-order tests is complex and unreliable. For this reason, most of the developed structure learning algorithms fall into the latter, namely the score+search methods [3; 5], which treat the problem of BN structure learning as a combinatorial optimization problem. The BN structure learning based on score+search methods firstly uses a scoring metric to evaluate how well the candidate BN structure matches the given dataset, and then finds the network structure with the maximum score. Popular scoring metrics include Akaike's information criterion (AIC), the Bayesian information criterion (BIC), the minimum description length (MDL) score, and the Bayesian Dirichlet equivalence (BDe) metric (usually called the K2 metric) [3]. Here, the BIC scoring metric, which comes from the penalized maximum likelihood, is used as the structure to identify the dataset matching degree as follows:  
\[P(\textit{B}_{S}|D)=\prod\limits_{i=1}^{n}\prod\limits_{j=1}^{q_{i}}\prod \limits_{k=1}^{r_{i}}\left(\frac{N_{ijk}}{N_{ijk}}\right)^{N_{ijk}}-f(m) \text{dim}(\textit{B}_{S}) \tag{2}\]  
where, \(\textit{B}_{S}\) is the candidate BN structure;  
\(r_{i}\) is the number of possible values for the variable \(\textit{X}_{i}\);  
\(q_{i}\) is the number of possible configurations instantiations for its parents \(\pi_{i}\);  
\(N_{ijk}\) is the number of cases in \(D\) in which variable \(\textit{X}_{i}\) has its \(k\)-th value, \(\pi_{i}\) is instantiated to its \(j\)-th value, and \(N_{ijk}=\sum\limits_{k=1}^{r_{i}}N_{ijk}\);  
\(\text{dim}(\textit{B}_{S})=\sum\limits_{i=1}^{m}q_{i}(r_{i}-1)\) is the dimension (the number of parameters needed to specify the model) of the BN; and \(f(m)\) is the non-negative penalization function that depends on the size of the dataset and can be computed as \(f(m)=0.5\)-\(\log\)\(m\). Using\(f(\textit{B}_{S},D)\) instead of \(P(\textit{B}_{S}\,|\,D)\), the BIC scoring metric [3] is defined as:  
\[ \begin{array}{rl}f_{BIC}(\textit{B}_{S},D)&=\log\left(\prod\limits_{i=1}^{n }\prod\limits_{j=1}^{q_{i}}\prod\limits_{k=1}^{r_{i}}\left(\frac{N_{ijk}}{N_ {ijk}}\right)^{N_{ijk}}\right)-f(m)\text{dim}(\textit{B}_{S})\\ &=\sum\limits_{i=1}^{n}f_{BIC}(x_{i},\pi_{i})\end{array}  \tag{3}\]  
where  
\[f_{BIC}(x_{i},\pi_{i})=\sum\limits_{j=1}^{q_{i}}\sum\limits_{k=1}^{r_{i}} \left(N_{ijk}\log\frac{N_{ijk}}{N_{ijk}}\right)-\frac{1}{2}\log m\cdot q_{i}(r _{i}-1). \tag{4}\]  
One desirable and important feature of scoring metrics is their decomposability in the presence of full data, and (3) shows that the BIC metric used here is decomposable.