A PC-Style Markov Blanket for High Dimensional Datasets

For classification in high-dimensional datasets, it is often helpful to know not just the Markov blanket MB(t) of the target variable t but also the Markov blanket DAG MBD(t) of t. The Markov Blanket Fan Search (MBFS) is a local adaption of the PC algorithm (Spirtes et al., 2000) that searches directly for possible MBD(t) from conditional independence information over a set of casually sufficient acyclically related variables in a dataset D containing t. MBFS is scalable, just-in-time and allows adjacency search to be performed in flexible order. The algorithm requires one parameter, maximum depth of search, though conditional independence tests used by the algorithm may require other parameters, such as significance level. Simulation results for datasets of up to 10,000 variables are given.