Constraint-based causal discovery

In this section, we’ll introduce the first of the four families of causal discovery methods – constraint-based methods. We will learn the core principles behind constraint-based causal discovery and implement the PC algorithm (Sprites et al., 2000).

By the end of this chapter, you will have a solid understanding of how constraint-based methods work and you’ll know how to implement the PC algorithm in practice using gCastle.

Constraints and independence

Constraint-based methods (also known as independence-based methods) aim at decoding causal structure from the data by leveraging the independence structure between three basic graphical structures: chains, forks, and colliders.

Let’s start with a brief refresher on chains, forks, and colliders. Figure 13.4 presents the three structures:

Figure 13.4 – The three basic graphical structures

In Chapter 5, we demonstrated that the...

Score-based causal discovery

In this section, we’ll introduce score-based methods for causal discovery. We’ll discuss the mechanics of the GES algorithm and implement it using gCastle.

Tabula rasa – starting fresh

The very first step of the PC algorithm was to build a fully-connected graph. GES starts on the other end of the spectrum, but first things first.

GES is a two-stage procedure. First, it generates the edges, then it prunes the graph.

The algorithm starts with a blank slate – an entirely disconnected graph – and iteratively adds new edges. At each step, it computes a score that expresses how well a new graph models the observed distribution, and at each step, the edge that leads to the highest score is added to the graph.

When no more improvement can be achieved, the pruning phase begins. In this phase, the algorithm removes edges iteratively and checks for score improvement. The phase continues until no further improvement...

Functional causal discovery

Functional causal discovery (also called function-based causal discovery) is all about leveraging the information about the functional forms and properties of distributions governing the relationships between variables in order to uniquely identify causal directions in a dataset. In this section, we’ll introduce the logic behind function-based methods, using the Additive Noise Model (ANM) (Hoyer et al., 2008) and LiNGAM (Shimizu et al., 2006) as examples. We’ll implement ANM and LiNGAM and discuss the differences between the two. By the end of this section, you will have a good understanding of the general principles of function-based causal discovery and you’ll be able to apply the ANM and LiNGAM models to your own problems using Python and gCastle.

The blessings of asymmetry

Tyger Tyger, burning bright,

In the forests of the night;

What immortal hand or eye,

Could frame thy fearful symmetry?

William Blake –...

Gradient-based causal discovery

In this section, we’ll introduce gradient-based causal discovery methods. We’ll discuss the main contributions of this family of methods and their main disadvantages. Finally, we’ll implement selected methods using gCastle and compare their performance with other families.

What exactly is so gradient about you?

2018 was an exciting year for the causal discovery community. Xun Zheng from CMU and his colleagues presented an interesting paper during the 2018 NeurIPS conference.

The work was titled DAGs with NO TEARS: Continuous Optimization for Structure Learning and introduced a novel approach to causal structure learning (though we need to say that the authors did not explicitly state that their method is causal).

The proposed method (called NOTEARS) was not based on a set of independence tests or local heuristics but rather treated the task of structure learning as a joint, continuously-optimized task.

One of the main...

Encoding expert knowledge

Combining expert knowledge with automated methods can be incredibly beneficial. It can help algorithms learn while inspiring human stakeholders to deepen their own insights and understanding of their environments and processes.

In this section, we’ll demonstrate how to incorporate expert knowledge into the workflow of our causal discovery algorithms.

By the end of this section, you’ll be able to translate expert knowledge into the language of graphs and pass it to causal discovery algorithms.

What is expert knowledge?

In this section, we think about expert knowledge as an umbrella term for any type of knowledge or insight that we’re willing to accept as valid.

From the algorithmic point of view, we can think of expert knowledge as a strong (but usually local) prior. We encode expert knowledge by freezing one or more edges in the graph. The model treats these edges as existing and adapts their behavior accordingly.

Expert...

Wrapping it up

We started this chapter with a refresher on important causal discovery assumptions. We then introduced gCastle. We discussed the library’s main modules and trained our first causal discovery algorithm. Next, we discussed the four main families of causal discovery models – constraint-based, score-based, functional, and gradient-based – and implemented at least one model per family using gCastle. Finally, we ran a comparative experiment and learned how to pass expert knowledge to causal models.

In the next chapter, we’ll discuss more advanced ideas in causal discovery and take a broader perspective on the applicability of causal discovery methods in real-life use cases.

Ready for one more dive?

References

Barabási, A. L. (2009). Scale-free networks: a decade and beyond. Science, 325(5939), 412-413.

Barabási, A. L., and Albert, R. (1999). Emergence of Scaling in Random Networks. Science, 286(5439), 509–512.

Blake, W. (2009) The Tyger. Songs of Experience. In William Blake: The Complete Illuminated Books.

Cai, R., Wu, S., Qiao, J., Hao, Z., Zhang, K., and Zhang, X. (2021). THP: Topological Hawkes Processes for Learning Granger Causality on Event Sequences. ArXiv.

Chickering, D. M. (2003). Optimal structure identification with greedy search. J. Mach. Learn. Res., 3, 507–554.

Chickering, M. (2020). Statistically Efficient Greedy Equivalence Search. Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI). In Proceedings of Machine Learning Research, 124, 241-249.

Colombo, D., and Maathuis, M.H. (2012). Order-independent constraint-based causal structure learning. J. Mach. Learn. Res., 15, 3741-3782.

Cressie...

Gradient-based causal discovery

In this section, we’ll introduce gradient-based causal discovery methods. We’ll discuss the main contributions of this family of methods and their main disadvantages. Finally, we’ll implement selected methods using gCastle and compare their performance with other families.

What exactly is so gradient about you?

2018 was an exciting year for the causal discovery community. Xun Zheng from CMU and his colleagues presented an interesting paper during the 2018 NeurIPS conference.

The work was titled DAGs with NO TEARS: Continuous Optimization for Structure Learning and introduced a novel approach to causal structure learning (though we need to say that the authors did not explicitly state that their method is causal).

The proposed method (called NOTEARS) was not based on a set of independence tests or local heuristics but rather treated the task of structure learning as a joint, continuously-optimized task.

One of the main...

Encoding expert knowledge

Combining expert knowledge with automated methods can be incredibly beneficial. It can help algorithms learn while inspiring human stakeholders to deepen their own insights and understanding of their environments and processes.

In this section, we’ll demonstrate how to incorporate expert knowledge into the workflow of our causal discovery algorithms.

By the end of this section, you’ll be able to translate expert knowledge into the language of graphs and pass it to causal discovery algorithms.

What is expert knowledge?

In this section, we think about expert knowledge as an umbrella term for any type of knowledge or insight that we’re willing to accept as valid.

From the algorithmic point of view, we can think of expert knowledge as a strong (but usually local) prior. We encode expert knowledge by freezing one or more edges in the graph. The model treats these edges as existing and adapts their behavior accordingly.

Expert...

Wrapping it up

We started this chapter with a refresher on important causal discovery assumptions. We then introduced gCastle. We discussed the library’s main modules and trained our first causal discovery algorithm. Next, we discussed the four main families of causal discovery models – constraint-based, score-based, functional, and gradient-based – and implemented at least one model per family using gCastle. Finally, we ran a comparative experiment and learned how to pass expert knowledge to causal models.

In the next chapter, we’ll discuss more advanced ideas in causal discovery and take a broader perspective on the applicability of causal discovery methods in real-life use cases.

Ready for one more dive?

References

Barabási, A. L. (2009). Scale-free networks: a decade and beyond. Science, 325(5939), 412-413.

Barabási, A. L., and Albert, R. (1999). Emergence of Scaling in Random Networks. Science, 286(5439), 509–512.

Blake, W. (2009) The Tyger. Songs of Experience. In William Blake: The Complete Illuminated Books.

Cai, R., Wu, S., Qiao, J., Hao, Z., Zhang, K., and Zhang, X. (2021). THP: Topological Hawkes Processes for Learning Granger Causality on Event Sequences. ArXiv.

Chickering, D. M. (2003). Optimal structure identification with greedy search. J. Mach. Learn. Res., 3, 507–554.

Chickering, M. (2020). Statistically Efficient Greedy Equivalence Search. Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI). In Proceedings of Machine Learning Research, 124, 241-249.

Colombo, D., and Maathuis, M.H. (2012). Order-independent constraint-based causal structure learning. J. Mach. Learn. Res., 15, 3741-3782.

Cressie...