text: We consider the problem of inferring the directed, causal graph from observational data, assuming no hidden confounders. We take an information theoretic approach, and make three main contributions. First, we show how through algorithmic information theory we can obtain SCI, a highly robust, effective and computationally efficient test for conditional independence---and show it outperforms the state of the art when applied in constraint-based inference methods such as stable PC. Second, building upon on SCI, we show how to tell apart the parents and children of a given node based on the algorithmic Markov condition. We give the Climb algorithm to efficiently discover the directed, causal Markov blanket---and show it is at least as accurate as inferring the global network, while being much more efficient. Last, but not least, we detail how we can use the Climb score to direct those edges that state of the art causal discovery algorithms based on PC or GES leave undirected---and show this improves their precision, recall and F1 scores by up to 20 .
  @cite_14: Finding an efficient way to discover Markov blanket is one of the core issue s in data mining. This paper first discusses the problems existed in IAMB algorithm which is a typical algorithm for discovering the Markov b lanket of a target variable from the training dat a, and then proposes an improved algorithm λ -IAMB based on the improving approach which contains two aspects: code optimization and the improving strategy for conditional independence testing. E xperimental results show that λ -IAMB algorithm performs better than IAMB by finding Markov blanket of variables in typical Bayesian network and by testing the performance of them as feature selection method on some well-known real world datasets .
  @cite_24: 
  @cite_15: We present an algorithmic framework for learning local causal structure around target variables of interest in the form of direct causes effects and Markov blankets applicable to very large data sets with relatively small samples. The selected feature sets can be used for causal discovery and classification. The framework (Generalized Local Learning, or GLL) can be instantiated in numerous ways, giving rise to both existing state-of-the-art as well as novel algorithms. The resulting algorithms are sound under well-defined sufficient conditions. In a first set of experiments we evaluate several algorithms derived from this framework in terms of predictivity and feature set parsimony and compare to other local causal discovery methods and to state-of-the-art non-causal feature selection methods using real data. A second set of experimental evaluations compares the algorithms in terms of ability to induce local causal neighborhoods using simulated and resimulated data and examines the relation of predictivity with causal induction performance. Our experiments demonstrate, consistently with causal feature selection theory, that local causal feature selection methods (under broad assumptions encompassing appropriate family of distributions, types of classifiers, and loss functions) exhibit strong feature set parsimony, high predictivity and local causal interpretability. Although non-causal feature selection methods are often used in practice to shed light on causal relationships, we find that they cannot be interpreted causally even when they achieve excellent predictivity. Therefore we conclude that only local causal techniques should be used when insight into causal structure is sought. In a companion paper we examine in depth the behavior of GLL algorithms, provide extensions, and show how local techniques can be used for scalable and accurate global causal graph learning.
  @cite_13: 
  @cite_25: The problem of learning the Markov network structure from data has become increasingly important in machine learning, and in many other application fields. Markov networks are probabilistic graphical models, a widely used formalism for handling probability distributions in intelligent systems. This document focuses on a technology called independence-based learning, which allows for the learning of the independence structure of Markov networks from data in an efficient and sound manner, whenever the dataset is sufficiently large, and data is a representative sample of the target distribution. In the analysis of such technology, this work surveys the current state-of-the-art algorithms, discussing its limitations, and posing a series of open problems where future work may produce some advances in the area, in terms of quality and efficiency.
  @cite_17: We propose algorithms for learning Markov boundaries from data without having to learn a Bayesian network flrst. We study their correctness, scalability and data e‐ciency. The last two properties are important because we aim to apply the algorithms to identify the minimal set of features that is needed for probabilistic classiflcation in databases with thousands of features but few instances, e.g. gene expression databases. We evaluate the algorithms on synthetic and real databases, including one with 139351 features.
summary: To the best of our knowledge, there exists no algorithm that directly discovers the directed, causal Markov blanket, i.e. that can tell apart parents, children and spouses given only the Markov blanket of a target. In , we first discover the Markov blanket, and then orient the edges. To discover the blanket, we build upon and extend the state of the art @cite_17 and @cite_24 algorithms. Both follow the general structure of the GS algorithm, with employing fast symmetry correction to exclude children of children. Zhu and Yang @cite_13 proposed to speed up by pre-filtering based on mutual information, whereas @cite_14 discover Markov blankets based on conditional mutual information. Unlike our approach, these approaches require the user to set a cut-off value and a scaling parameter @math . For an in depth overview of related algorithms, we refer to the following articles @cite_15 @cite_25 .