Optimizing Causal Objective Functions - Algorithms and Complexity

Explore the intricacies of causal objective functions in this comprehensive keynote lecture delivered by Adnan Darwiche of UCLA at the 2023 workshop on causal discovery in Cholula, Mexico. Delve into the syntax and semantics of causal objective functions, also known as causal loss functions, and learn about an exact algorithm for optimizing a broad class of these functions. Examine the relationship between optimizing causal objective functions and the "unit selection" problem introduced by Li & Pearl, while focusing on the algorithmic approach that assumes a fully specified causal model. Cover key topics such as structural causal models, the causal hierarchy, and the identifiability/learning dimension. Gain insights into variable elimination for computing associational queries, the optimization of causal objective functions using Reverse-MAP, and the complexity of these algorithms. Conclude with discussions on elimination orders, treewidth of parallel worlds, and causal treewidth, providing a thorough understanding of this advanced topic in causal inference.

Causal objective functions: What and why?
The causal hierarchy
Structural causal models SCM
The identifiability/learning dimension
Unit selection: The work of Li & Pearl
The algorithmic dimension of unit selection optimization
Examples of causal objective functions
Syntax and semantics of causal objective functions
Sub-models
Worlds
Events associational, interventional, counterfactual
Satisfaction of an event by a world
Example of satisfaction
Probability of events associational, interventional, counterfactual
Generalized events: conjunctive, disjunctive and negated
Variable elimination for computing associational queries
MAR marginals
MAP maximum a posteriori hypothesis
Treewidth & elimination orders
Optimizing causal objective functions
Triplet models: evaluating counterfactual queries
Objective models: optimizing the causal objective function using Reverse-MAP
Reverse-MAP: Relation to MAP, complexity class of Reverse-MAP and unit selection
Reverse-MAP: Algorithm, complexity bound, experiments
Elimination orders and treewidth of parallel worlds twin, triplet, .., models
Causal treewidth
Main messages