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_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_29: thousands, are becoming common. Therefore, feature selection has been an active research area in pattern recognition, statistics and data mining communities. The main idea of feature reduction is to select a subset of input variables by eliminating features with little or no predictive ability, but without scarifying the performance of the model built on the chosen features. It is also known as variable selection, feature reduction, attribute selection or variable subset selection. By removing most of the irrelevant and redundant features from the data, feature reduction brings many potential benefits to us:  Alleviating the effect of the curse of dimensionality to improve prediction performance;  Facilitating data visualization and data
  @cite_4: 
summary: Many methods for discovering Markov blankets and causal networks rely on conditional independence tests @cite_15 @cite_4 ---which, by conditioning on the empty set, can also be used to measure association. For discrete data, the state of the art commonly relies on either the @math test or conditional mutual information (CMI) @cite_15 @cite_29 @cite_14 . Both measures, however, have drawbacks. The @math test is biased to independence when only limited data is available, whereas CMI has the opposite problem. In particular, it holds that @math for any @math , even if @math . For both @math and CMI it is necessary to define a significance threshold or cut-off, which can be arbitrary. Our proposed method based on algorithmic independence overcomes these limitations.