# Analyzing Markov Boundary Discovery Algorithms in Ideal Conditions Using the d-Separation Criterion
## 5 Experiment and Results
### The Algorithm Runs in the DS Group
Still, IAMB produces much more accurate Markov boundaries (lower PR distances) in spite of performing G-tests that end up being accurate in less than 30% of cases, for any dataset size. A simple and satisfactory explanation for this observation could not be found as part of this experiment, although it was indeed surprising. At this moment, an implementation mistake cannot be ruled out, although this is highly unlikely because IAMB and IPC-MB have been developed under the same suite of unit tests and they also produce the same Markov boundaries when configured with the d-separation CI test. It is also worth mentioning that MILDEW causes the lowest CI test accuracies of all the Bayesian networks for both algorithms at all sample sizes. On top of that, IAMB appears to be more accurate than IPC-MB for all datasets of 800 samples. Apart from the anomaly described above, IPC-MB consistently outperforms IAMB with respect to accuracy, producing lower PR distances. On the CHILD dataset at 20,000 samples, IPC-MB achieves 0.000 PR distance, the best value in the experiment. Secondly, the average conditioning set size in the G-tests performed by the algorithms grows as the number of samples in the dataset grows. The most noteworthy increase is observed for IAMB on the MILDEW dataset: at 800 samples, IAMB performs tests with an average conditioning set size of 9.63, but at 20,000 samples, this average becomes 28.49. Note that the entire MILDEW network consists of 35 nodes in total and 28.49 represents 81.4% of the whole network. In contrast, IPC-MB appears much more stable: the greatest difference in the average conditioning set size is seen on the CHILD datasets, but it starts at 3.94 at 800 samples and reaches 6.88 at 20,000 samples, a much smaller increase than that which is observed for IAMB. Thirdly, the d-separation validations recorded for the G-tests reveal another interesting fact: the CI tests performed by IAMB do not have a clear trend in accuracy with respect to sample size, but those performed by IPC-MB become more and more accurate as sample size increases. The lack of a trend in IAMB is somewhat surprising, because a higher sample count should provide more accurate tests, but this potential increase in accuracy is cancelled by the growing average conditioning set seen for IAMB as the sample count increases, described above. The values in the \"Duration\" column in Tables 2-5 reinforce the fact that CI tests consume the overwhelming majority of the computing resources used by an MBD algorithm. It also highlights another drawback of CI tests when used during algorithm development, namely the delay they introduce in the design loop. However, the G-test was computed here with the \(dcMI\) optimization, which can reduce the computation time of the G statistic by a factor of 20 [10]. Without optimization, the durations observed in this experiment would have been much greater. However, configuring an MBD algorithm to use a statistical CI test alongside d-separation during the design phase may be a necessary condition, depending on the algorithm, as hypothesized in the Introduction (Section 1). \begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Algorithm** & **Network** & **Tests** & **Average Cond. Set Size** & **Accurate Tests** & **PR Distance** & **Duration (s)** \\ \hline IAMB & CHILD & **178** & 22.79 & 75.28\% & 0.079 & 57.649 \\ IAMB & ALARM & 277 & 9.24 & 96.75\% & 0.109 & 10.230 \\ IAMB & MILDEW & 1220 & 28.49 & 28.11\% & 0.702 & 611.964 \\ IPC-MB & CHILD & 37,240 & 6.88 & **98.85\%** & **0.000** & 1177.597 \\ IPC-MB & ALARM & 36,139 & 2.95 & 95.34\% & 0.121 & 792.971 \\ IPC-MB & MILDEW & 33,480 & **2.45** & 85.62\% & 0.467 & 978.469 \\ \hline \hline \end{tabular}
\end{table} 
Table 5: G-test results across all datasets of 20,000 samples for IAMB and IPC-MB.