Introduction - Causal Structure Learning - Philosophy, MDL & Assumptions

This
research
investigates how causal structure learning algorithms can
aid the
performance analysis of (parallel) programs.

More information & publications: Jan Lemeire (jan.lemeire@vub.ac.be) & Stijn Meganck

Our causal learning module

Experimental Setup

Research results, explained with examples

Information analysis module

Kernel density estimation (KDE) module

Interactive tutorial on causality, information and KDE

Although causality is still a highly debated issue among statisticians, we believe it provides a natural and intuitive representation about the relations among variables. We propose the use of causal models for modeling how variables influence the overall performance of (parallel) applications.

The following figure represents a simplified performance model of a sort algorithm:

It contains application parameters (at the left), system parameters (at the bottom), the overall performance (at the right) and intermediate variables that can be measured inside the application of the system.

The following figure shows the basic causal model of the performance of a parallel application:

This model is reflected in the analysis of EPPA.

Causal Structure Learning

Besides the formalization of causality by Judea Pearl, another important scientific advance was the invention of algorithms that can learn causal models from observational data. The research of Spirtes, Glymour and Scheines (SGS) has resulted in the TETRAD tool. Our work is based on TETRAD's algorithms, which we extended to capture the full complexity of performance models:

- A mixture of continuous and discrete data.
- A form-free measure of dependency.
- The handling of deterministic relations.
- Context-specific variables and independencies.

The handling of deterministic relations is attained by considering the case that two variables have equivalent information about a third variable. The only objective criterion for deciding upon which variables are directly related is then the complexity of the relations. This work is done by Jan Lemeire. The last extension is currently being studied by Joris Borms, he will use context-specific graphs.

Our causal learning module

Research results, explained with examples

Philosophy of Learning, Minimum Description Length & Assumptions

One of the hardest criticisms of causality and the learning algorithms are the assumptions that are made.

We want to answer by considering learning in general, in a philosophical way: what can we learn from observations? It is clear that no method can guarantee that the 'real' model will be learnt.

An interesting side question is if the real, physical world can be known. After all, everything we know about the world comes from observation (and partly from a book). See the opinions from Jorma Rissanen and Peter Grünwald about this.

By linking the work of causal structure learning with the ideas developed by the field of Algorithmic Information Theory (see Paul Vitanyi) around regularities (= compression!) and typicalness (randomness = incompressibility), I believe that we an conclude that we have to search for regularities in data and construct models that capture these regularities. Moreover, causal models suggest that we have to look for models that capture all regularities!

Draft paper Causal Models as Minimal Descriptions of Multivariate Systems.