# Analyzing Markov Boundary Discovery Algorithms in Ideal Conditions Using the d-Separation Criterion
## 2 Related Work  
A number of Markov blanket discovery algorithms have been proposed and discussed since this class of algorithms was first established. In each case, the authors provided the results of empirical validations. A few of these algorithms are discussed in this section, along with the method used by the respective authors to validate the algorithm experimentally. [PERSON] and [PERSON]'s algorithm (KS) was the first algorithm to employ the concept of Markov boundaries for feature selection [3; 8] and it uses two heuristics called \(\beta\) and \(\gamma\), expressed as Kullback-Leibler divergences. These heuristics were later revealed to be conditional mutual information [12]. KS did not have a proof of correctness, but the foundations it laid had a great impact. The authors experimentally evaluated the KS algorithm by using it to select features from datasets, then feeding these features into a classifier and evaluating its final accuracy. A separate evaluation compares KS to a simple selection by thresholding mutual information [13]. Supplementary efficiency optimizations for the KS algorithm are possible [14], targeting both heuristics of the algorithm. The Incremental Association Markov Blanket (IAMB) [9] algorithm was the first to be regarded as scalable, even if it was not the first to be proven correct [3]; that distinction belongs to GS [15]. It also introduced a two-phase design, later inherited by other algorithms of this class. The CI test used by IAMB is a simple threshold applied on conditional mutual information. The algorithm also uses conditional mutual information as a heuristic to guide the selection of candidate nodes for the Markov boundary. The authors of IAMB performed a rigorous analysis of its accuracy and created ROC curves with respect to the thresholds applied on mutual information, reporting the areas under the ROC curves for both synthetic and real datasets. However, they provided very little information about its efficiency with respect to running time or number of CI tests performed. While scalable, the IAMB algorithm is regarded as sample-inefficient [3]. In the same year IAMB was published, two other related algorithms were published as well, namely Max-Min Markov and Blanket (MMMB) [6] and HITON [5]. These two algorithms try to address the inefficiencies of IAMB. Building on the principles of IAMB, they add novel methods of identifying the parents and children of a variable node within a Bayesian network. Unfortunately, MMMB and HITON were shown to be incorrect [7]. However, the ideas they introduced have been influential and were inherited by future algorithms of this class. The Parent-Child Markov Blanket (PCMB) [7] algorithm expanded on MMMB and HITON, aiming at achieving higher sample efficiency. The authors of PCMB provide a detailed analysis of accuracy and present results such as precision, recall and Euclidean distance from perfect precision and recall. These measures define a \"true positive\" when the algorithm correctly selects a node for the Markov boundary of the target node. This approach works for synthetic datasets when the Bayesian network is known in advance. The PCMB algorithm achieves its goal of sample efficiency, which is reflected in its increased accuracy [7]. As is the case of IAMB, the authors of PCMB provide almost no useful information about its efficiency, except for the total running time on a real dataset. The Iterative Parent-Child Based Search of Markov Blanket (IPC-MB) [11] algorithm improved the time and CI test efficiency of PCMB by first performing the CI tests with the smallest conditioning set. Apart from higher efficiency, the authors also reported increased accuracy compared to PCMB. They performed the same kind of accuracy analysis as PCMB did, and reported results such as precision, recall and the Euclidean distance from perfect precision and recall. Moreover, they provide the number of CI tests performed by the IPC-MB algorithm (and by PCMB, as part of the comparison).