Published on Fri Feb 05 2021

Integer Programming for Causal Structure Learning in the Presence of Latent Variables

Rui Chen, Sanjeeb Dash, Tian Gao

The problem of finding an ancestral acyclic directed mixed graph (ADMG) that represents the causal relationships between a set of variables is an important area of research on causal inference. A number of score-based methods have recently been proposed for the ADMG learning, yet they are

0
0
0
Abstract

The problem of finding an ancestral acyclic directed mixed graph (ADMG) that represents the causal relationships between a set of variables is an important area of research on causal inference. Most existing score-based structure learning methods focus on learning directed acyclic graph (DAG) models without latent variables. A number of score-based methods have recently been proposed for the ADMG learning, yet they are heuristic in nature and do not guarantee an optimal solution. We propose a novel exact score-based method that solves an integer programming (IP) formulation and returns a score-maximizing ancestral ADMG for a set of continuous variables that follow a multivariate Gaussian distribution. We generalize the state-of-the-art IP model for DAG learning problems and derive new classes of valid inequalities to formulate an IP model for ADMG learning. Empirically, our model can be solved efficiently for medium-sized problems and achieves better accuracy than state-of-the-art score-based methods as well as benchmark constraint-based methods.

Thu May 20 2021
Machine Learning
Definite Non-Ancestral Relations and Structure Learning
Ancestral relations between variables play an important role in causal modeling. These relations are usually deduced from learned structures and used for orienting edges. We propose a framework that can learn non-ancestral relations without first learning the skeleton.
0
0
0
Fri May 29 2020
Artificial Intelligence
Bayesian network structure learning with causal effects in the presence of latent variables
In Bayesian Networks (BNs), this challenge is known as learning under causal insufficiency. This paper describes a hybrid structure learning algorithm called CCHM. It combines the constraint-based. part of cFCI with hill-climbing score-based learning.
0
0
0
Thu Dec 01 2016
Machine Learning
PAG2ADMG: An Algorithm for the Complete Causal Enumeration of a Markov Equivalence Class
Causal graphs, such as directed acyclic graphs (DAGs) and partial ancestral graphs (PAGs), represent causal relationships among variables in a model. PAG2ADMG is the first algorithm for enumerating all causal graphs consistent with .
0
0
0
Wed Jun 10 2020
Machine Learning
Low Rank Directed Acyclic Graphs and Causal Structure Learning
Learning causal structures represented by directed acyclic graphs (DAGs) remains a challenging task in high dimensional settings when the graphs to be learned are not sparse. We propose a novel approach to mitigate this problem by exploiting a low rank assumption regarding the (weighted)
0
0
0
Tue Apr 23 2019
Machine Learning
Integer Programming for Learning Directed Acyclic Graphs from Continuous Data
Learning directed acyclic graphs (DAGs) from data is a challenging task both in theory and in practice. We propose a new mixed-integerquadratic optimization (MIQO) model, referred to as a layered network (LN)formulation. Computational
0
0
0
Fri Apr 29 2011
Machine Learning
Learning high-dimensional directed acyclic graphs with latent and selection variables
We consider the problem of learning causal information between random variables in directed acyclic graphs (DAGs) The FCI (Fast Causal Inference) algorithm has been explicitly designed to infer conditional independence and causal information in such settings. We therefore propose the new RFCI algorithm,
0
0
0