Multi-Target Markov Boundary Discovery: Theory, Algorithm, and Application

Markov boundary (MB) has been widely studied in single-target scenarios. Relatively few works focus on the MB discovery for variable set due to the complex variable relationships, where an MB variable might contain predictive information about several targets. This paper investigates the multi-target MB discovery, aiming to distinguish the common MB variables (shared by multiple targets) and the target-specific MB variables (associated with single targets). Considering the multiplicity of MB, the relation between common MB variables and equivalent information is studied. We find that common MB variables are determined by equivalent information through different mechanisms, which is relevant to the existence of the target correlation. Based on the analysis of these mechanisms, we propose a multi-target MB discovery algorithm to identify these two types of variables, whose variant also achieves superiority and interpretability in feature selection tasks. Extensive experiments demonstrate the efficacy of these contributions.