# Analyzing Markov Boundary Discovery Algorithms in Ideal Conditions Using the d-Separation Criterion
## 3 Bayesian Networks and Markov Boundaries  
This section provides some theoretical background on Bayesian networks, Markov boundaries and the d-separation criterion, needed to discuss the algorithms and the experiment presented in this article. A Bayesian network is a directed acyclic graph that represents conditional dependencies between the variables of the dataset: each node in a Bayesian network is a variable of the dataset, while each directed edge represents the dependence of the destination node on the source node. Each node also contains the full conditional probability table of the variable it represents, given the variables it depends on (encoded as inbound edges in the graph). An essential property of the Bayesian is that any node is conditionally independent of all its ancestors, given its immediate parents. Expressed differently, a node is only dependent on its immediate parents:  
\[ \begin{split}\Pr(X_{1},X_{2},X_{3},\ldots,X_{n})=\prod_{i=1}^{n} \Pr(X_{i}\mid Parents(X_{i}))\\ \text{where }Parents(X_{i})\subset\{X_{1},X_{2},X_{3},\ldots,X_{n}\} \end{split}  \tag{1}\]  
Moreover, a Bayesian network is the minimal I-map for the joint probability distribution of the variables [2]. This means that the network encodes all the marginal and conditional independence relationships of the form \(I(X|\mathbf{Z}|Y)\) that present in the joint probability distribution, and removing any edge from the network would break at least one encoding of conditional independence. The notation \(I(X|\mathbf{Z}|Y)\) means that \(X\) and \(Y\) are conditionally independent given the set of variables \(\mathbf{Z}\). The fact that the edges of a Bayesian network are directed enables it to encode the marginal dependence of a cause and its effect distinctly from the conditional dependence between two causes that share the same effect, given the effect is known, and the causes are otherwise marginally independent. This is the case of the variables \(X_{1}\), \(X_{3}\), \(X_{5}\) and \(X_{6}\) from the simple Bayesian network in Figure 1.  
Here, the conditional probability table of variable \(X_{1}\) is only defined based on variables \(X_{3}\), \(X_{5}\) and \(X_{6}\). However, if \(X_{1}\) were not part of the dataset at all, then \(X_{6}\) would appear marginally independent of either \(X_{5}\) and \(X_{3}\). But the Bayesian network correctly expresses the fact that knowing \(X_{1}\) would render \(X_{6}\) dependent on both \(X_{3}\) and \(X_{5}\), because knowing one cause and its effect provides information about the other causes that share the effect. In the Bayesian network shown in Figure 1, the variables \(X_{6}\), \(X_{3}\) and \(X_{5}\) are the \"parents\" of \(X_{1}\), which is their \"child\". Because they share a child, \(X_{6}\), \(X_{3}\) and \(X_{5}\) are \"spouses\". To correctly determine the true relationship between these variables in the network, the d-separation criterion is applied, as discussed in Section 3.1. This criterion works by giving special meaning to nodes that have converging or diverging arrows. In other words, a path between two nodes cannot be unambiguously interpreted on its own as \"dependence\" or \"independence\" (d-connected or d-separated, respectively). The direction of the edges that compose it must be taken into account, along with the conditioning set. In a Bayesian network, the Markov boundary of a variable \(X_{i}\) is the smallest subset of variables which renders \(X_{i}\) conditionally independent of the entire Bayesian network, given the Markov boundary itself, not only of its ancestors. Therefore, if \(\mathbf{U}\) is the set of all the variables of the dataset and \(MB(X_{i})\) is the Markov boundary of \(X_{i}\), then  
\[I(X_{i}\mid MB(X_{i})\mid\mathbf{U}-MB(X_{i})-X_{i}). \tag{2}\]  
Figure 1: The Markov boundary of variable \(X_{3}\) emphasised with light gray in a simple Bayesian network. Note that the network may contain multiple sets for which this property holds. They are called Markov blankets, and the Markov boundary is the smallest blanket.