Causal Discovery from Observational Data

Lecture Notes on Causal Inference

Motivation

在之前的内容中，我们都是基于 causal graph 去进行化简分析。那么如果我们没有 causal graph，只有观测到的数据应该怎么办呢？那么这就要用到 causal discovery 方法，根据数据去建立 causal graph

causal discovery 大致可分为两类，independence-based 完全基于数据去建图； Semi-Parametric 针对 parametric form 作假设建模

Independence-Based Causal Discovery

首先我们需要作出一些假设

• Faithfulness
  在之前的马尔科夫假设中，我们从因果图出发分析数据，假设如果 X 和 Y 在 G 图中的 Z 节点条件下独立，那么 X 和 Y 基于 Z 条件独立。
  这里的faithfulness假设则是从反方向假设，即如果 X 和 Y 在数据上对 Z 条件独立，那么在其对应的因果图中，同样有此条件独立关系
• Causal Sufficiency：对图中的任何变量而言，都不存在没有被观察到的潜在原因对其作用影响
• Acyclicity：假设是无环图

我们还需要引入马尔科夫等价类（Markov equivalence class）的概念。 马尔科夫等价意味着相同的条件独立分布，比如chain和fork类型属于同一种马尔科夫等价类，而immorality属于另一种马尔科夫等价类。

还有skeleton的概念，我们将因果图中的所有的有向边变为无向边，此时得到的图称为 skeleton

在介绍完假设及新概念后，我们在这里给出主要定理。两幅因果图是马尔科夫等价的 当且仅当 他们拥有相同的 skeleton 和 immoralities

进而由此我们得到 Essential graph（aka CPDAG completed partially） 的概念，Essential graph 是 skeleton 和 immorality 的组合，所有immorality子结构中的边是有向的，其余边仍为无向边。

现在来到了下一个问题，我们应该如何得到 Essential graph 呢？其中一种方法称为 PC Algorithm，该算法分为三步

1. Identify the skeleton
   我们首先从无向完全图开始，对于边 X-Y，如果存在一个 Condition set Z 使得 $X \perp !!! \perp Y \vert Z$ ，那么我们删除连接 X 和 Y 的这条边。condition set 从空集开始，逐渐增加集合内元素的个数进行判断
2. Identify immoralities
   经过第一步后，对图中所有的 X-Z-Y 路径进行判断，当同时满足以下两个条件时，我们可以判断 X-Z-Y 形成了immorality，并为其添加对应的方向
   • X 和 Y 之间没有边（在算法的第一步中被删去）
   • Z 不在使得 X 和 Y 条件独立的 condition set 中
3. Orient qualifying edges that are incident on colliders
   经过第二步后，所有的immorality都别识别出并添加了边的方向。在现在的图中，针对所有 $X \rightarrow Z - Y$ 的路径，当 X 和 Y 之间没有边连接时，我们可以对 Z 和 Y 之间的边添加方向，即 $Z \rightarrow Y$

我们从 PC Algorithm 得到的因果图只是 Essential graph 中的一种形式，并不能保证得到和真实因果图一模一样的graph。

除了 PC Algorithm 外，还有一些算法针对更加广泛的情况（即移除部分假设）进行应用，这里列举一些

• No assumed causal sufficiency: FCI algorithm
• No assumed acyclicity: CCD algorithm
• Neither causal sufficiency nor acyclicity: SAT-based causal discovery

Independence-Based Causal Discovery 也存在一些局限性。

• 最大的约束是这些算法都依赖准确的条件独立测试。这一点在拥有无限数据时是很容易进行的，但现实中我们得到的数据都是有限的，而且研究表明有时需要相当多的数据才能得到准确的测试结果。
• 需要 faithfulness 假设
• 只能 identify the Markov equivalence class

接下来一个很自然的疑问就是，我们可以做的更好吗？
在faithfulness的假设下，我们已经可以 identify the essential graph （Markov equivalence class）。现有研究表明，当数据是多正态分布，或者是线性高斯结构方程时，在最好的情况下我们也只能identify a essential graph （Markov equivalence class）

那如果是非高斯结构方程，或者是非线性结构方程呢？这就引出了第二类 causal discovery 的方法

Semi-Parametric Causal Discovery

首先考虑最简单的双变量情况，即 $X\rightarrow Y$ 和 $Y\rightarrow X$ 。如果从马尔科夫等价的角度来看，我们得到的essential graph是相同的，因此无法区分这两种情况。如果从结构方程的角度来看，前一种情况对应 $Y=f_Y(X,U_Y)$ ，X 与 $U_Y$ 相互独立。后一种情况对应 $X=f_X(Y,U_X)$ ，Y 与 $U_X$ 相互独立。此时同样无法进行区分

所以在这里我们需要对 parametric form 做一些假设。

• Linear Non-Gaussian Assumption：第一种假设噪声为线性非高斯分布的，即 $Y := f(X) + U$ ，X 与 U 相互独立，$U$为非高斯分布。此时根据现有研究，我们有如下定理
  linear non-Gaussian 假设下，如果真实的 SCM 为 $Y=f(X)+U $ ，X 与 U 相互独立，那么此时不存在能产生一致 P(x,y) 数据的相反方向的 SCM，即 $X=g(Y)+\tilde{U}$ ，Y 与 $\tilde{U}$ 相互独立，具体证明可见课程教材
• Nonlinear additive noise assumption：第二种假设噪声为加性的，方程时非线性的，即 $Y := f(X) + U$ ，X 与 U 相互独立， $f$ 是非线性方程。根据现有研究，此时结合Markov assumption, causal sufficiency, acyclicity assumption, 我们可以 identify the causal graph
  此外，我们也可以在外面继续嵌套非线性方程，将线性噪声转换为非线性噪声，即 $Y := g(f(X) + U)$ ，X 与 U 相互独立，则称为 Post-Nonlinear Assumption