序
大家好，好久没有更新因果技术的文章了，从今天开始，我会开启一个新的专栏，和大家聊聊因果推断，一方面是给自己做一个技术沉淀，另一方面也是希望可以制造一个场，让对因果有兴趣的朋友们一起来讨论技术。
前一篇因果入门的文章中已经为大家简单的介绍了一下因果推断了。大家反响很热烈，收到一致好评。忘记的同学可以回顾一下：
入门：因果推断 简介
https://blog.csdn.net/jiey0407/article/details/126599496?spm=1001.2014.3001.5502
文章看完记得小手点个赞，纯原创纯手打，大家一键三连支持一下！
这个系列出现的所有paper里的算法我都希望能向大家用大白话的方式讲出来，使得一个就算不太了解技术的人也能理解他。
“因果推断”作为目前统计以及机器学习届最炙手可热的一个名词，19年图灵奖得主Yoshua Bengio认为：“深度学习已经走到了瓶颈期，将因果关系整合到AI当中已经成为目前的头等大事“。而11年的图灵奖得主的Judea Pearl则提到：“目前有太多深度学习项目都单纯关注缺少因果关系的粗糙关联性，这常常导致深度学习系统在真实条件下（明显不同于训练场景的条件下）进行测试时，往往拿不出良好的实际表现。”并在他的新书《The Book of Why: The New Science of Cause and Effect》当中提到，“如果没有对因果关系的推理能力，AI的发展将从根本上受到限制。”
接下来的系列，我会通过对重要的paper和方法总结，逐步的为大家介绍因果推断这个方法，同时也不断开发自己的开源代码库Causal ToolBox。
在接下来的这篇文章中，为求表达精确，我主要会使用英文对论文进行总结和讲解，与此同时，对于一些核心的理解，也会用中文表达。
需要注明的是，传统因果很多方法都是通过做实验，即controlled experiment来得到结果，但是这种实验成本往往巨大，即便在体量相当大的公司，做一些商业上的ABtest也意味巨大的成本，在这个情况下，我们希望从以及观察到的数据，即observational data中得到因果推断的结果。接下来的所有内容，都围绕着如何在observational data里做因果推断这个问题。
什么是causality（因果）
Formal Definition: Causality is a generic relationship between an effect and the cause that gives rise to it.
这个大家直译就好，就是和大家平常理解的因果关系一个意思
causality和statistical association的区别（因果性和相关性区别）
举个例子：如果我们发现，夏天的时候，一个冰淇淋店的电费上涨的同时冰淇淋卖的也很好，我们可以说他们互相之间有因果的关系吗？不见得，他们之间可能只是统计上的相关性，而真正给他们带来的因果性的因子叫做气温，是因为气温的上升，导致电费的增加，也是因为气温的上升，导致了冰淇淋销量的上升。这个例子很好的向我们阐述了因果性和统计相关性的区别。
Two main questions
- Causal discovery(因果关系挖掘): 比如研究：温度升高是否是电费增加的原因？或者在商品价格，商品转化率，商品上市时间，商品成本等几个变量之间探究一个因果图，即变量两两之间是否有因果关系？如果有，谁是因谁是果？
- Causal effect(因果效应推理): 比如我们已经知道温度升高是电费增加的原因，我们想知道温度从20度升至30度，会对电费带来多少增加？
Two main frameworks
Structural Causal Models(SCM) – Judea Pearl: A causal model by SCMs consists of two components: the causal graph (causal diagram) and the structural equations.
即我们需要先得到一张因果图，然后对于因果图，我们去使用Structural Equations来描述它。
比如对于这一张因果图，箭头由因指向果，X和E都是变量。然后右边的一系列方程就是Structural Equations来描述这个图，每一个方程f都表示着由因到果的一个映射或者说一个表达式，这个方程可以是linear也可以是nonlinear的，取决于他们的因果关系是否线性。
Potential Outcome Framework– Donald Rubin: It is mainly applied to learning causal effect as it corresponds to a given treatment-outcome pair (D,Y).
简单来说，计算因果效应最直接的手段就是控制住所有的变量不变，只变化cause，比如把温度从20变到30度，然后直接看outcome变化，也就是直接用30度时的电费减去20度时的电费，既可以得到causal effect。HOWEVER，easier said than done！！！如果这个世界有两个平行时空，那么我们可以做这个实验，但是如果没有呢？我们知道温度不可能在同一个地方，同一个时间，即20度又30度，那么必然20度的时候，30度时的电费就叫potential outcome。而这个framework，就是相方设法从能观察到的数据中得到这个potential的结果，然后二者相减，就是我们想要的答案啦！
Causal Discovery
这篇文章首先我们来看第一个问题，causal discovery。因为如果你没有因果关系，又谈何因果推断呢？
Started from Bayesian Network
首先我们从贝叶斯网络聊起，贝叶斯网络是一个DAG(directed acyclic graph)，即有向无环网络。然后我们可以把它当作一个概率图，也就是可以概率表达它。举个例子：对于下图，我们可以表达为P(A,B) = P(B|A)*P(A)，why?，因为A指向B，而无箭头指向A，我们就可以得到A和B的联合分布有他们两部分组成，非常简单对吧！
P(A,B) = P(B|A)*P(A)
加一点难度，对于下图，可以表达为P(A,B,C) = P(C|A,B)*P(B|A)*P(A)。因为C有AB两个变量指向他，而B同样只有A指向它。
P(A,B,C) = P(C|A,B)*P(B|A)*P(A)
这就是所谓的贝叶斯网络，那么下面我们来做一个题目，理解这个题目对于causal discovery是essential的，所以非常重要。从下面的图中可以得到a和b的什么关系？
head-to-head
p(a,b,c)=p(a)∗p(b)∗p(c|a,b)∑cp(a,b,c)=∑cp(a)∗p(b)∗p(c|a,b)p(a,b)=p(a)∗p(b)a⊥b
基于上述公式我们可以推导出a与b独立
tail-to-tail
p(a,b,c)=p(c)∗p(a|c)∗p(b|c)p(a,b,c)p(c)=p(a|c)∗p(b|c)p(a,b|c)=p(a|c)∗p(b|c)a⊥b|c
基于上述公式我们可以推导出a与b条件独立（given c）
head-to-tail
p(a,b,c)=p(a)∗p(c|a)∗p(b|c)p(a,b,c)p(c)=p(a)∗p(c|a)∗p(b|c)p(c)p(a,b|c)=p(a,c)∗p(b|c)p(c)p(a,b|c)=p(a,c)p(c)∗p(b|c)p(a,b|c)=p(a|c)∗p(b|c)a⊥b|c
基于上述公式我们可以推导出a与b条件独立（given c）
总结一下，对于head-to-head，我们有a与b独立，对于tail-to-tail，我们有given c，a与b条件独立，对于head-to-tail，我们有given c，a与b条件独立。换一个直观的例子：
我们可以看到，因为c这个“搅屎棍”的存在，我们很可能在数据误以为a与b有因果关系，实际上他们只是有相关性，也可以说c d-separate/blocked a and b。但是对于a与b的关系，NONE of them are causality。而我们要做的就是找到这些关系，才能判断出真正的因果。我们定义一下，head-to-head叫做v-structure或者collider，tail-to-tail叫做confounder或者fork，head-to-tail叫做chain。以便于理解后面以及其他paper。
接下来我们进入正题，来介绍causal discovery的算法
Constraint-based Algorithms
方法介绍
这一类算法learn a set of causal graphs which satisfy the conditional independence embedded in the data。
也就是通过找到上面三种结构来构建因果图，寻找方式就是通过条件独立的检验，一般的方式都是从一个无向的全链接图出发开始寻找，通过一系列规则最终生成一个图。
他有两类重要假设：1. Faithfulness Assumption and Markov Assumption，说人话就是Conditional independence imply d-separate, vice versa。2. Sufficiency Assumption ，说人话就是No unobserved confounder (common cause)。
他的缺点是：
1. 不能有unobserved confounder，这个条件即便在如今大数据的时代下，也很难满足。当然有类似IC*和FCI这种算法可以loose这个unobserved confounder的假设。所以这个缺点还好。
2. 对于上面的chain和fork，由于他们都imply a和b基于c条件独立，故称为马尔可夫等价类，而这类算法无法从马尔可夫等价类中区分出不同的DAG，即对于这类算法，他认为chain和fork是一个东西，这也意味着对于上图，a有可能是c的因，也可能是果，这显然不make sense。
3. 假设极其严格，需要非常多且高质量的数据，因为faithfulness假设使得我们只能通过conditional independence来测试，如果数据很少，有可能这些测试互相都会相斥，做起图非常困难
论文分享
IC algorithm: 一个经典的constraint-based algorithm, 它是利用conditional independence 来确定v-structure, chain, confounder，然后由此来identify DAG。
方法见书：《Causality: models, reasoning, and inference》[Judea_Pearl], p60
IC* algorithm: IC算法的改良版，可以用在latent(unobserved) confounder存在的情况下。前两步与IC算法相同，第三步的判断规则基于存在latent confounder的假设下做了调整
方法见书：《Causality: models, reasoning, and inference》[Judea_Pearl], p62
PC algorithm: 也是一个经典的constraint-based algorithm, 和IC算法的思路很相近
方法见文章：http://www.cs.cmu.edu/afs/cs.cmu.edu/project/learn-43/lib/photoz/.g/web/.g/scottd/fullbook.pdf p136
Score-based Algorithms
方法介绍
这一类算法是通过最优化一个给每个图打分的score function来找到最优的图。要想成为打分函数，其要有两个基本部分。1. structural equation from candidate G’, 2:other constraints of G’。比如学过统计的朋友们都知道BIC就是一个打分函数： S(X,G′)=logP(X|θ^,G′)−J2log(n)
他由两部分最成，Maximize likelihood（第一项）的同时regularize graph size（第二项），正好对应了上面的两个基本部分。
这类方法的优点是由于使用goodness of fit替代了conditional independent，于是relax了上面的第一类假设，但是缺点是仍然无法区分马尔可夫等价类。另一个大的缺点是这类算法因为要找到最优的分数，就要搜索全部的图，这是一个NP-hard和NP-complete的问题，复杂度极高且容易陷入局部最优。
论文分享
GES algorithm: 一个经典的scored-based algorithm, 使用下面BDeu这个打分函数来给每个图打分。但是这个方法只要求找到一个局部最优解即可。方法使用2阶段的贪婪搜索，第一阶段只insert edges，每轮insert operator只操作可以让这个打分函数最高分的三元组，直到达到local optimum。然后第二阶段只delete edges，同理delete operator只操作可以让这个打分函数最高分的三元组，直到达到local optimum。
SBDeuG′,X=log∏j=1J0.001(rh−1)qj∏k=1qjΓ(10/qj)Γ(10/qj+Njk)∏l=1rjΓ(10/(riqi)+Njkl)Γ(10/(rjqj))
方法见论文：http://www.jmlr.org/papers/volume3/chickering02b/chickering02b.pdf
fGES algorithm: fast GES, 是快速版，复杂度低版的GES，有两处改变：parallelize and reorganize caching in the GES
方法见论文：https://errorstatistics.files.wordpress.com/2016/11/a-million-variables-and-more-2016-proofs.pdf
FCMs-based Algorithms
方法介绍
这类算法的名字是我自己起的。什么是FCM (functional causal model)呢？不严谨的来说就是上面我提到的Structural Causal Models的图里右边那一堆function，假设我们能先得到这些function，我们就可以还原左边的图。大概就是这个思路。举个例子，对于s，d，y三个变量，如果我们通过某个算法得到了如下的等式关系，也就是一个下三角阵：
那我们可以通过它得到一个causal order，也就是一个序，比如对于s，d，y来说就是1，2，3。通过这个序，我们知道s一定在d和y前面，d一定在y前面，于是我们有下图的因果DAG
这类方法最大的优点就在于能够从马尔可夫等价类中区分出不同的DAG，从而保证有序的因果关系。
论文分享
LiNGAM: 一个最经典的FCM-based algorithm, 用于continuous data。方法最常用的是用ICA（independent component analysis）作为求解的武器，核心逻辑就是估计一个类似上图的那种strictly lower triangle matrix (下三角阵)，然后这个下三角阵就得到了一个unique的causal order。但是有严格的假设，分别是如下三个假设(a) the data generating process is linear, (b) there are no unobserved confounders, and (c) disturbance variables have non-Gaussian distributions of non-zero variances. 这个方法还有几个优化的变体，DirectLiNGAM，LvLiNGAM，SLIM，LiNGAM-GC-UK等
方法见文章：https://www.cs.helsinki.fi/u/ahyvarin/papers/JMLR06.pdf
BMLiNGAM: 和LiNGAM很像, 但是使用于两变量之间的，换句话说就是一个在确定两者有因果关系的变量之间找出谁是因谁是果。 他还有一个极其重要的优势就是可以用于unobserved confounders存在的情况下。类似的还有pairwise LiNGAM
方法见文章：http://www.jmlr.org/papers/volume15/shimizu14a/shimizu14a.pdf
ANM: additive noise model: 也是一个处理两变量的方法。模型对LiNGAM第一个linear的假设做了放松（即variables和noise不需要再有linear relationship的假设了），然后对于noise，只要是additive的即可。还有一个ANM的优势是缩小了图的搜索空间。类似的可以处理多变量的模型还有一个叫CAM (causal additive model)的模型
方法见文章：https://papers.nips.cc/paper/3548-nonlinear-causal-discovery-with-additive-noise-models.pdf
DL/RL algorithm
方法介绍
这类方法有别于上述方法，更多使用深度学习或者强化学习等思路来挖掘因果图，里面的方法其实基本是也是上面的三类，只不过他们的实现路径不太好直接去归类到其中某一类，故我们就单列一类
论文分享
CGNN: AWESOME! 一个极其强大的算法。可以在如下情况下使用，can be used for multi-variable, can be used in asymmetric distribution, can be used in unobserved confounder, non-linear cases.
回忆我们刚刚提到的FCM方程，里面有一个f，这些f我们刚刚说可以是linear也可以是nonlinear的，这里是使用神经网络作为FCM 里的f，然后用他来生成拟合的一个FCM作为拟合出来的joint distribution来approximate the real joint distribution of data，用拟合的distribution和真正的distribution之间的差距作为损失函数，网络的目标即为最小化这个损失函数。损失函数表达如下： S(G^,D)=−MMD^k(D,D^)−λ|G^| ，其中 |G^| 是 G^ 的edge的个数。另外：
MMD^k=1n2∑i,j=1nk(xi,xj)+1n2∑i,j=1nk(x^i,x^j)−2n2∑i,j=1nk(xi,x^j)
这里k就是某种核函数，衡量距离用的，MMD就是用来衡量两个分布的接近程度的，当两个分布完全一样时，MMD=0。所以大家其实可以看出来，这是一个score-based method，因为他的score function由两部分组成，一部分评估SCM的效果，一部分是对图的构造做了限制。不过这个方法理论上我理解是可以区分马尔可夫等价类的，所以也不算一般的score-based method
具体怎么实现呢？
首先我们需要输入一个skeleton，就是一个先验的无向的因果图，这个图一般由专家知识得到。如果是score-based method，就会有一个搜索的策略，CGNN也是如此，他一共有3步搜索策略。
1. 对于两两相邻的变量，通过这两个变量做一个pairwise CGNN，然后两个方向分别去训练一波，得到最优的损失，选比较小的损失作为选定的方向。于是我们就得到了两两的方向，即
2. 顺着目前得到图的任意一个节点，找找有没有环，有环则把他reverse，这步就是保证不存在任意一个环，即
3. 对于目前的图，不断的尝试reverse其中某个边，然后再去训练，看最后损失能不能减少，如果可以就reverse。这步一般使用hill-climbing算法。即
这样就得到了最后的图，所以NN其实是在每次需要计算score的时候都训练一遍，且参数并不保留，都是重新训练。还有就是，这个方法可以处理hidden confounder，方法就是把noise作为variables也放进图里。
详细可以看原论文：https://arxiv.org/pdf/1711.08936.pdf
SAM: recovering full causal models from continuous observational data along a multivariate non-parametric setting。也是可以处理有hidden confounder的情况。这篇文章比较骚的地方在于他提到自己不是上述任意一类的方法，他说他是一个集大成者，即用到了conditional independence如constraint-based，又做了regularization如score-based，同时又可以和CGNN，CAM等方法一样解决distributional asymmetries的问题。可见现在学术圈有多卷！
详细可以看原论文：https://arxiv.org/pdf/1803.04929.pdf
CAUSAL DISCOVERY WITH REINFORCEMENT LEARNING: 这篇文章来自华为的诺亚实验室，他利用Reinforcement Learning (RL)来寻找得分最高的DAG. Its encoder-decoder model takes observable data as input and generates graph adjacency matrices that are used to compute rewards. It uses RL as a search strategy and its final output would be the graph, among all graphs generated during training, that achieves the best reward, is the best DAG. 使用RL作为因果挖掘的思想非常straightforward，因为在RL里的每个action可以看作是一个treatment的改变，而reward就可以是图的分数，这个思想非常好
详细可以看原论文：https://arxiv.org/pdf/1906.04477.pdf
当然，这里还有许多文章我没有提到，不代表不重要，大家可以根据上述文章的文献综述去找一波！
因果分析系统只推荐一个，有兴趣可以去了解一下：
关河因果分析系统https://yinguo.grandhoo.com/home
文章看完记得小手点个赞，纯原创纯手打，大家一键三连支持一下！
Reference
[1] Ruocheng Guo, Lu Cheng, Jundong Li, P. Richard Hahn, and Huan Liu. 2020. A Survey of Learning Causality with Data: Problems and Methods. ACM Comput. Surv. 1, 1, Article 1 (January 2020), 36 pages.