因果系列文章（10）—— 因果关系发现

如何从纷繁复杂的数据中发现其中隐含因果关系，就是因果关系发现（casual discovery）要做的工作。本节简要总结这方面的工作，主要材料来源于《Elements of Causal Inference Foundations and Learning Algorithms》[1]这本书第4章、第7章和一些综述文章[2][3]。

在学习因果关系发现之前，首先补充一些相关的概念定义。

这些定义都是参考知乎作者：木土老师《因果关系》https://zhuanlan.zhihu.com/p/555170435

马尔可夫性、忠实性

马尔可夫性（Markov property）是构成图模型基础的一个常用假设。当一个分布关于一个图是“马尔可夫”（Markovian）的，则表明这个图能够建模分布中的某些特定的独立性，那么我们就可以利用这些独立性来进行有效的计算或进行数据存储。有向图和无向图都存在马尔可夫性，但在因果推理中，主要还是研究有向图的马尔可夫性。

【定义】 马尔可夫性：给定一个有向无环图 G 以及所有节点的联合概率分布 P ，那么如果 Xi 和 Xj被 S d分离⇒Xi⊥⊥Xj|S ，则称这个分布 P 满足关于G 的全局马尔可夫性。

与之相对偶的性质是忠实性（Faithfulness）。

【定义】 忠实性：考虑一个分布 P 和一个有向无环图 G ，那么如果 Xi⊥⊥Xj|S⇒ Xi 和 Xj被 S d分离 ，那么 P 关于 G 就是忠实的。

考虑如下的一个例子。假设概率分布 P 对有向无环图 G 是马尔可夫且忠实的，那么根据以下条件确定模型 G 的结构。

1. X⊥⊥Z （变量包括 X 、 Y 、 Z ）
2. X⊥⊥Y|Z （变量包括 X 、 Y 、 Z ）
3. X⊥⊥Y 、 X⊥⊥W|Z 、 X⊥⊥W|Z,Y 、 Y⊥⊥W|Z 、 Y⊥⊥W|Z,X （变量包括 W 、X 、 Y 、 Z ）

图1

三种条件下的答案如图1所示。第1个条件的情形是唯一的对撞结合，也就是V结构。根据之前学习的知识，对撞结合让 X 和 Z 独立，当以 Y 为条件时， X 和 Z 变为相关。第2个条件符合的结合不止一种。这三种结构被称为马尔可夫等价类（Markov Equivalence class）。

【定义】马尔可夫等价类：如果有向无环图 G 和 H 具有相同的d分离特性，那么 G 和 H 就是马尔可夫等价的，并且同属于一个马尔可夫等价类。如果 G 和 H 是马尔可夫等价的，那么它们具有相同的骨架（Skeleton）和V结构（也即对撞结构），反之亦然。

骨架的意思可以理解为不考虑箭头方向的连接结构。图1(i)和(ii)的四个图都共有相同的骨架。图1(ii)的三个图不仅具有相同的骨架，还具有相同的V结构（因为它们都没有V结构），所以它们属于同一个马尔可夫等价类，但是它们同图1(i)的图就不是同一个马尔可夫等价类，因为(i)中有一个V结构。

如果分布 P 对于可能的有向无环图 G 是马尔可夫且忠实的，那么图 G 中的d分离语句与分布中相应的条件独立性语句就可以建立一一对应的关系。因此，在图 G 的马尔可夫等价类之外的所有图都可以被排除。但同属于一个马尔可夫等价类的图是无法区分的。

基于独立性的方法

所以第一类因果关系发现方法就是基于独立性的方法（independence-based methods）。一共分两步，第一步是从数据分布中找出所有的独立性或条件独立性，第二步是从这些独立性中选择可能的有向无环图结构。

图2：基于独立性的方法

大多数基于独立性的方法首先估计可能的骨架，即无向边，然后尽可能地确定边的方向。在确定骨架时，可考虑使用以下两条引理：

【引理1】在有向无环图 DAG(X;ε) 中，两个节点 X 和 Y 是相邻的，当且仅当它们不能被任何子集 S⊆V∖{X,Y} d分离。
【引理2】如果有向无环图 DAG(X;ε) 中两个节点 X 和 Y 是不相邻的，那么它们就可以被 PAx 或 PAy 所d分离。其中PAx 和 PAy分别表示 X 和 Y 的父节点（集）。

引理1告诉我们，如果两个变量总是相关的，那么无论以何其它变量为条件，这两个变量总是相邻的。IC算法（inductive causation）和SGS算法利用了这条引理。对于每一组节点 (X,Y) ，通过搜索既不包含 X 也不包含 Y 的可能的子节点集 A⊆X∖{X,Y} ，然后检查 X 和 Y 是否是被 A d分离的。当且仅当无法找到任何一组 A 能够将 X 和 Y d分离时，可以判断 X 和 Y 是相邻的。

然后就要确定边的方向。如果在上一步得到的骨架结构中，两个结点没有直接相连，那么便有一个结点集将这两个结点d分离。假如我们已经得到了这样的骨架结构 X−Z−Y ，然后假设结点集 A 能够将 X 和 Y d分离，那么 X−Z−Y 就可以确定为V结构，那么当且仅当 Z∉A 时可以初步确定V结构为： X→Z←Y 。然后再根据其他条件最终确定整体结构。

但是这类方法有两个问题，一是穷尽所有结点之间的独立性测试是非常巨大的搜索问题，当结点数较多的时候计算量是不可接受的。为此，也有一些改进的算法通过逐渐增加结点个数的方式来进行测试（如PC算法）。

下图给出了PC算法的大致流程。图3A是真实的因果结构关系。通过d分离原则不难得知， X 与 Y 是独立的，即 X⊥⊥Y 。当以 Z 为条件时， X 和 Y 分别与 W 独立，也即 {X,Y}⊥⊥W|Z 。PC算法基于马尔可夫性和忠实性的假设。其主要流程如下：

图3

1. 建立一个包含所有结点的无向图（如图3B）。
2. 去掉非条件独立的变量之间的边，这里是 X−Y 之间的边（如图3C）。
3. 如果变量 (A,B) 之间有边，并且如果任意一个变量 C 连接了 A 和 B 中的任何一个，那么如果 A⊥⊥B|C 则去掉 A 和 B 之间的边。如图3D中，假如 X⊥⊥W|Z 且 Y⊥⊥W|Z ，于是去掉了 X 和 W 、 Y 和 W 之间的边。
4. 如果变量 (A,B) 之间有边，并且变量 (C,D) 都连接到 A 或者都连接到 B ，那么如果 A⊥⊥B|{C,D} ，则去掉 A 和 B 之间的边。以此类推，增大作为条件的结点集的结点个数，直到结点集的每一个结点都与 A 相连或者都与 B 相连，然后做同样的判断。
5. 对于任意一组结点 (A,B,C) ，其中 A 和 B 相连， B 和 C 相连， A 和 C 不相连的话，如果以某个结点集为条件A 和 C 是独立的并且 B 不在这个结点集中，那么可确定三个结点的结构为 A→B←C。在图3E中，消除 X 和 Y 之间边的时候没有以 Z 为条件，所以可以得到 X→Z←Y 。
6. 对于任意形如 A→B−C 这样的结构， A 和 C 不相邻，则可。将 B−C 转换为 B→C ，这一步被称为“方向传播”（orientation propagation）。在图3F中， Y→Z−W 转变为 Y→Z→W 。

第二个问题是，如前所述，同属于一个马尔可夫等价类的图是无法区分的，这对于两个结点的情况尤其突出，比如 X→Y 和 X←Y 两种结构，它们骨架相同，都没有V结构，所以它们是属于同一个马尔可夫等价类。这种情况下借助加性噪声模型（additive noise models，ANMs）来考虑。

还有一种类似的算法叫FCI算法（Fast Causal Inference）在此不做深入介绍。有兴趣的读者可以自行查阅相关文献。

加性噪声模型

加性噪声模型的一般定义如下：

【定义】加性噪声模型：如果 X 和 Y 的关系可以用如下的一个函数加一个噪声的SCM形式来表示的话，那么我们称联合概率分布PX,Y 满足 X 到 Y 的加性噪声模型：

Y=fY(X)+NY,NY⊥⊥X

基于加性噪声模型的可辨识性定义，判断 X 和 Y 之间因果关系的方法如下：

1. 在 X 上回归 Y ，即，用某种回归算法将 Y 表示为一个关于 X 的函数 fY ，加上某个噪声。
2. 测试 Y−f^Y(X) 是否与 X 独立。
3. 重复以上步骤但反过来在 Y 上回归 X 。
4. 如果这两种情形的测试结果，某一个独立，另一个不独立，那么独立的那个就是因果关系的方向。

更进一步地可以总结为如下的定理：

【定理1】考虑一个如下的结构因果模型 X→Y ：
Y=αX+NY,NY⊥⊥X那么，存在 β∈R 使得
X=βY+NX,NX⊥⊥Y成立，当且仅当 (X,NY) 的分布是高斯的。

也就是说，只有当且仅当 (X,NY) 的分布是高斯时才有反向模型（如果有反向模型那么说明因果关系的方向无法确定）。所以如果不是高斯的就可以辨识出因果的方向（书中4.1.3节给出了证明过程）。看下面的这个例子。

已知一个如下的SCM：

Y=2X+NYX∼U[−1,1]NY∼U[−0.4,0.4]

U 表示均匀分布，也即 X 和 NY 都是服从均匀分布而不是高斯分布。图4给出了满足以上SCM的500个点（蓝色空心圆），以及在 X 上对 Y 做回归后的结果（红色实线）。

图4

如果在 X 轴的任意位置做一条垂直于 X 轴的线，可以发现在 Y 方向上的残差（residual）都是处处均匀的，也即 Y−f^Y(X) 与 X 是独立的。图5给出了残差和 X 的关系图。

图5

反过来，如果在 Y 上对 X 进行回归，也就是说把 X 写成一个有关 Y 的线性函数加一个残差 NX ，然后同样可以画出来如图6所示。绿色是这条回归线。要注意的是我们还是横坐标 X ，纵坐标 Y ，所以在画这条回归线时要反转一次，即画出的是 (f^X(Y),Y) 。

图6

再来看残差，此时应看的是在 X 方向上的残差了，所以应该垂直于 Y 方向，任意位置做一条垂直于 Y 方向的线，然后通过与绿色线的相交出看绿线左右两边的残差。不难发现，这个残差并不是处处一致的。把两张图叠加在一起看就更加明显地看出区别来。

图7

也可以单独把 X 方向上的残差 X−f^X(Y) 和 Y 的关系画出来，如图8所示。很明显，残差和 Y 并不是独立的，因为 Y 不同的地方残差也不同。

图8

定理1说的是情形是线性模型，如果是非线性模型，即使残差是服从高斯分布的，也没有反向模型。定理2描述了这一规则：

【定理2】考虑一个如下的结构因果模型 X→Y ：
Y=f(X)+NY,NY⊥⊥XNY,X∼N
那么只有当 f 是线性函数时才会有反向模型存在：
X=g(Y)+NX,NX⊥⊥YNX,Y∼N

考虑如下的一个SCM：

Y=X3+NYX∼N(1,0.52)NY∼N(0,0.42)

图9给出了满足以上SCM的500个点（蓝色空心圆）以及拟合的结果（红色曲线）。

图9

同样地，也可以画出残差 Y−f^Y(X) 和 X 的关系图，可以看出 Y 方向上的残差与 X 是基本独立的（中间数据点多两边数据点少是因为数据产生时服从了高斯分布）。

图10

然后再反过来进行拟合，结果如图11所示。

图11

残差 X−f^X(Y) 和 Y 的关系如图12所示。很显然， X 方向上的残差和 Y 是不独立的。

图11

对于三个变量组成的SCM来说，只需要以其中一个为条件（conditioning on）然后考察另两个的因果关系方向，就转换成两个变量的情况了。总的来说，将SCM写成加性噪声模型的形式，并且在满足某些条件的情况下，可以辨识出变量之间的因果关系方向。

扩展阅读

本节介绍的内容只涵盖了因果关系发现中最基本的两类方法：

基于独立性测试的方法，以及通过加性噪声模型的形式分析残差与预测者独立性关系的方法。除以上介绍的基本方法以外，近年来不乏一些通过深度学习[4]、强化学习[5]的方法来挖掘因果关系的方法。

因果关系发现的重要性也越来越引起人们的重视，所涉及的方法也在各领域得到了应用[6]。近几年来大部分科研机构开始不仅在发现数据间相关性同时还注重相关中蕴含的因果联系，挖掘这样的关系对现实场景中业务的开展是大有帮助的，专做这一方向研发的系统有深算院自研的关河因果分析系统。新型数据分析产品_因果分析_关河因果【官网】 (grandhoo.com)

有兴趣的读者可下载相关论文继续研读。

参考

1. ^Jonas Peters, Dominik Janzing, Bernhard Schölkopf, Elements of Causal Inference Foundations and Learning Algorithms, The MIT Press
2. ^Clark Glymour, Kun Zhang and Peter Spirtes, "Review of Causal Discovery Methods Based on Graphical Models,"Frontiers in Genetics,vol.10, article 524, 2019
3. ^Daniel Malinsky, David Danks, "Causal discovery algorithms: A practical guide,"Philosophy Compass, vol.13, no.1, 2018
4. ^Yuhao Wang, Vlado Menkovski, Hao Wang, Xin Du, Mykola Pechenizkiy, "Causal Discovery from Incomplete Data: A Deep Learning Approach,"arXiv:2001.05343. https://arxiv.org/abs/2001.05343
5. ^Shengyu Zhu, Ignavier Ng, Zhitang Chen, "Causal discovery with reinforcement learning," ICLR 2020
6. ^Xinpeng Shen, Sisi Ma, Prashanthi Vemuri, Gyorgy Simon & the Alzheimer’s Disease Neuroimaging Initiative, "Challenges and Opportunities with Causal Discovery Algorithms Application to Alzheimer’s Pathophysiology,"Scientific Reports vol. 10, 2020.