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 for causal inference. However, most of existing score-based structure learning methods focus on learning the directed acyclic graph (DAG) 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. In particular, we generalize the state-of-the-art IP model for DAG learning problems and derive new classes of valid inequalities to formalize the IP-based ADMG learning model. 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.
翻译:寻找祖传的环绕式定向混合图(ADMG)是一组变数之间的因果关系,是一个重要的因果推断研究领域。然而,现有基于分数的结构学习方法大多侧重于学习没有潜在变数的定向环绕式图(DAG),最近为ADMG的学习提出了一些基于分数的方法,但这些方法具有超自然性质,不能保证最佳解决办法。我们提出了一种新的精确的基于分数的方法,解决了一套整数编程(IP)的配方,并将一套连续变数的祖传ADMG的得分最大化。特别是,我们推广了用于DAG学习问题的最先进的IP模型,并产生了新的有效不平等类别,以正式确定基于IP的ADMG的学习模式。我们的模式对于中等规模的问题是可以有效解决的,而且比基于分数的先进方法以及基于基准的制约方法更准确。