New papers reveal the advantages of novel local causal pathway methods for the analysis of high dimensional data.

November 02, 2009

The work also provides the largest benchmarking in the literature to date comparing biomarker discovery algorithms. To appear in the highest impact factor in statistical machine learning journal: Journal of Machine Learning Research.

Local Causal and Markov Blanket Induction for Causal
Discovery and Feature Selection for Classification.
Part I: Algorithms and Empirical Evaluation

by Constantin F. Aliferis, Alexander Statnikov, Ioannis Tsamardinos, Subramani Mani, and Xenofon D. Koutsoukos

Abstract
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 datasets 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.

Local Causal and Markov Blanket Induction for Causal
Discovery and Feature Selection for Classification.
Part II: Analysis and Extensions

by Constantin F. Aliferis, Alexander Statnikov, Ioannis Tsamardinos, Subramani Mani, and Xenofon D. Koutsoukos

Abstract
In part I of this work we introduced and evaluated the Generalized Local Learning (GLL)
framework for producing local causal and Markov blanket induction algorithms. In the
present second part we analyze the behavior of GLL algorithms and provide extensions
to the core methods. Specifically, we investigate the empirical convergence of GLL to the
true local neighborhood as a function of sample size. Moreover, we study how predictivity
improves with increasing sample size. Then we investigate how sensitive are the algorithms
to multiple statistical testing, especially in the presence of many irrelevant features. Next
we discuss the role of the algorithm parameters and also show that Markov blanket and
causal graph concepts can be used to understand deviations from optimality of state-of-the-
art non-causal algorithms. The present paper also introduces the following extensions
to the core GLL framework: parallel and distributed versions of GLL algorithms, versions
with false discovery rate control, strategies for constructing novel heuristics for specific
domains, and divide-and-conquer local-to-global learning (LGL) strategies. We test the
generality of the LGL approach by deriving a novel LGL-based algorithm that compares
favorably to the state-of-the-art global learning algorithms. In addition, we investigate the
use of non-causal feature selection methods to facilitate global learning. Open problems and future research paths related to local and local-to-global causal learning are discussed.