# Analyzing Markov Boundary Discovery Algorithms in Ideal Conditions Using the d-Separation Criterion
## 5 Experiment and Results
### The Algorithm Runs in the DS Group  
The \(DS\) group consists of runs that use the statistical G-test on synthetic datasets to discover the Markov boundaries of variables, but each test is also verified using the d-separation criterion for the tested variables on the source Bayesian network. The d-separation result is recorded for later analysis. A random sampler was employed to generate datasets of 800, 4000, 8000 and 20,000 samples for each of the three Bayesian networks in the experiment. Of interest are the following measures:  
* The total number of CI tests performed by the algorithms on each dataset, considered a measure of the overall efficiency of the algorithms;
* The percentage of statistical tests performed by the algorithms that were accurately evaluated, i.e., the statistical tests in agreement with the simultaneously computed d-separation criterion;
* The average size of the conditioning set used in the CI tests, considered a measure for the overall sample efficiency of the algorithms;
* The precision-recall Euclidean distance from perfect precision and recall, as calculated by the authors of PCMB [7] and of IPC-MB [11]. Tables 2-5 capture the behavior of IAMB and IPC-MB with G-tests on the three Bayesian networks, recording the measures of interest mentioned above. There are a few interesting facts to observe in the results. Values representing the highest efficiency and accuracy in their respective columns are shown bolded. \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 & **207** & 23.44 & 67.63\% & 0.137 & 27.523 \\ IAMB & ALARM & 267 & 9.01 & 95.51\% & 0.144 & 4.248 \\ IAMB & MILDEW & 1131 & 24.17 & 30.15\% & 0.668 & 193.901 \\ IPC-MB & CHILD & 25,343 & 6.64 & **97.89\%** & **0.039** & 357.632 \\ IPC-MB & ALARM & 33,183 & 2.94 & 94.84\% & 0.115 & 310.035 \\ IPC-MB & MILDEW & 18,536 & **1.64** & 69.50\% & 0.880 & 229.154 \\ \hline \hline \end{tabular}
\end{table} 
Table 4: G-test results across all datasets of 8000 samples for IAMB and IPC-MB. \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 & **144** & 10.78 & 86.11\% & **0.216** & 1.070 \\ IAMB & ALARM & 223 & 6.18 & 89.24\% & 0.235 & 0.484 \\ IAMB & MILDEW & 713 & 9.63 & 20.48\% & 0.827 & 5.179 \\ IPC-MB & CHILD & 10,581 & 3.94 & **92.74\%** & 0.366 & 22.225 \\ IPC-MB & ALARM & 19,042 & 2.34 & 92.70\% & 0.270 & 30.213 \\ IPC-MB & MILDEW & 4176 & **1.34** & 42.94\% & 1.306 & 8.240 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: G-test results across all datasets of 800 samples for IAMB and IPC-MB. \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 & **177** & 18.42 & 77.97\% & 0.097 & 9.783 \\ IAMB & ALARM & 255 & 8.25 & 93.73\% & 0.165 & 2.098 \\ IAMB & MILDEW & 1019 & 22.55 & 28.95\% & 0.711 & 83.683 \\ IPC-MB & CHILD & 26,588 & 6.67 & **97.65\%** & **0.022** & 237.000 \\ IPC-MB & ALARM & 26,430 & 2.72 & 94.62\% & 0.116 & 131.340 \\ IPC-MB & MILDEW & 10,104 & **1.46** & 59.12\% & 1.122 & 70.179 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: G-test results across all datasets of 4000 samples for IAMB and IPC-MB. Firstly, IPC-MB has issues with the MILDEW datasets of 800, 4000 and 8000 samples, resulting in high PR distances, while IAMB performs much better. This happens in spite of IPC-MB performing tests with very small conditioning sets. This is also not an effect of inaccurate tests, because the d-separation results agree with the G-tests performed by IPC-MB almost twice as often as for IAMB.