查看原文
其他

什么是Do演算 | 集智百科

集智百科 集智俱乐部 2022-04-08


“集智百科精选”是一个长期专栏,持续为大家推送复杂性科学相关的基本概念和资源信息。作为集智俱乐部的开源科学项目,集智百科希望打造复杂性科学领域最全面的百科全书,欢迎对复杂性科学感兴趣、热爱知识整理和分享的朋友加入!

本文是对集智百科中“Do演算”词条的摘录,参考资料及相关词条请参阅百科词条原文。

本词条由集智俱乐部众包生产,难免存在纰漏和问题,欢迎大家留言反馈或者前往对应的百科词条页面进行修改,一经修改,可以获得对应的积分奖励噢!


目录


一、为何需要Do演算二、Do演算规则集
三、Do演算的完备性
四、应用案例五、相关算法六、代码实现七、编者推荐八、百科项目志愿者招募

Do演算(Do-Calculus)于1995年由Judea Pearl提出,是由三条推演规则构成的推演系统,这三条规则可以将包含干预变量和观测变量的概率分布表达式进行转化。Do演算属于因果科学中结构因果模型的基础分析工具,可用于非参数模型中因果效应的识别,并能够在中介分析(Mediation Analysis)、知识迁移(Transportability)、元综合(Metasynthesis)等方向上发挥重要作用。





为何需要Do演算




一个无法使用后门调整和前门调整的因果图


在处理一部分因果图时,可以使用后门调整后门调整和前门调整等技术进行统计调整,这样可以根据不涉及Do算子的数据来估算干预的效果。然而我们无法根据前门准则和后门准则事先确定一个给定的因果模型是否适用于这样的统计调整方式。后门调整和前门调整方法也无法处理所有可识别的模型,例如上侧的因果图是可识别的,但既无法使用后门调整也无法使用前门调整。


而Do演算是一个具有完备性的推演系统,可以处理所有可识别的模型,当然也就包括了右侧图中这个例子。同时,利用Do演算还有一系列的计算机算法,可以自动、高速地去判断一个模型的可识别性,并在可识别的模型中将包含Do算子的概率分布表达式转换为仅包含观测变量的概率分布表达式。





Do演算规则集




在以下规则的表述中,使用符号GX表示删除有向图G中所有指向结点X的边后得到的子图,使用符号GXZ表示删除有向图G中所有指向结点X的边和从结点Z指出的边后得到的子图。


规则一

增添或删除观察:

对于有向图G若满足

(即在子图GX中,给定结点集X和W时,结点集Y和Z满足d-分离条件),则P(Y|do(X),Z,W)=P(Y|do(X),Z)


规则二

交换干预和观察:

对于有向图G,若满足

(即在子图Gzx中,给定结点集X和W时,结点集Y和Z满足d-分离条件),则P(Y|do(X),do(Z),W)=P(Y|do(X),Z,W)


规则三

增添或删除干预:

对于有向图G若满足

(即在子图Gxz(w)中,给定结点集X和W时,结点集Y和Z满足d-分离条件),则

P(Y|do(X),do(Z),W)=P(Y|do(X),W)


其中符号Z(W)表示Z/An(W)Gx,而符号An(W)Gx表示在子图Gx中由结点集W及其祖先节点构成的点集。





Do演算的完备性(Completeness)




定理

Q=P(y|do(x),z)是可识别的,当且仅当它可以被Do演算的三条规则转化为一个不包含Do算子的表达式。


证明

要证明上述定理的正确性,需要分别证明Do演算的可靠性(Soundness)和充分性(Sufficiency)。其中可靠性的证明由Judea Pearl于1995年给出,充分性的证明由Yimin Huang和Marco Valtorta于2006年给出。





应用案例




应用案例1

Do演算的案例1


在右侧的因果图中,“吸烟基因”是未观测变量,其余变量都是可观测的。“吸烟”变量使用s来表示,“焦油沉积”变量使用t来表示,“癌症”变量使用c来表示。我们要估计干预“吸烟”变量后对“癌症”变量的因果效应,即计算P(c|do(s))。我们将使用Do演算将这个表达式转换为不包含Do算子的表达式。



应用案例2

Do演算的案例2 - 间接混杂


此案例由Nanny Wermuth和D. R. Cox给出,对应的实际例子可参见论文内容。其中治疗方案1(X)是随机施于患者的,而治疗方案2(Z)是根据治疗方案1所导致的中期结果(W)而制定的,在这里要计算的是干预两种治疗方案后对最终结果的因果效应,即P(y|do(x),do(z))。可以再次使用Do演算将这个表达式转换为不包含Do算子的表达式。






相关算法




处理多变量干预算法

Jin Tian和Judea Pearl于2002年提出了第一个可以处理多变量被干预的算法。


Identify算法

Identify算法由Yimin Huang和Marco Valtorta于2006年提出。这个算法相较于上述Tian(2002)的算法消除了的对因果图的半马尔科夫性的限制,且也可以处理多变量干预的问题。


ID算法

ID算法由Ilya Shpitser和Judea Pearl与2006年提出,该算法的能力与上述Tian(2002)的算法等价,但更易于编程实现。


IDC算法

IDC算法由Ilya Shpitser和Judea Pearl与2006年提出,该算法是基于ID算法拓展的,可以处理联合干预条件分布的因果效应求解问题。





代码实现




Ananke

Ananke框架基于Python语言实现,集成了ID算法,详细内容可见Ananke开源地址https://gitlab.com/causal/ananke


causaleffect

causaleffect框架基于R语言实现,集成了ID算法和IDC算法,详细内容可见causaleffect包信息地址

https://cran.r-project.org/web/packages/causaleffect/index.html


CEE

CEE框架基于Golang语言实现,集成了ID算法、IDC算法、Identify算法等,详细内容可见CEE开源地址

https://github.com/L-F-Z/CEE





编者推荐




暑期学校「来临」
第二季因果读书会聚集了全球最前沿的青年学者探讨因果的奥秘,获得了很好的反响,形成了因果社区的种子用户群体,为后续因果社区的发展注入活力和灵魂。为此,8月份,集智俱乐部联合中国计算机学会(CCF)和重庆大学大数据与软件学院举办一期暑期学校,因果社区线上举办,感兴趣的同学可以详细了解:集智俱乐部×重庆大学因果科学暑期学校8月14-17日线上举办,基础+前沿+实践一站习得

泛太平洋因果推断国际大会及因果科学竞赛

PCIC (the Pacific Causal Inference Conference,泛太平洋因果推断大会) 2021将于2021年9月11日至12日在北京以线上+线下相结合的方式举行。本大会聚集了海内外一大批因果科学相关领域的学术大拿汇聚一堂,共同探讨因果科学的新进展,探索新的科研方向,吸引了非常多优秀的科研工作者投身于该领域,推动了因果科学的研究进程。

会议期间会议组委会,北京大学和华为诺亚方舟实验室共同组织了此次因果竞赛。竞赛的数据集为经过抽取脱敏的实际数据或者根据实际场景抽象出来的模拟数据。获奖团队获得现金奖励和证书,并邀请在大会上做技术报告。

对会议和竞赛感兴趣的同学可以详细了解:PCIC 2021华为因果推理挑战赛开放组队报名

“基于社会系统的因果发现”讲习班

BDSC2021前沿讲习班以“社会系统中的因果发现”为主题,将于11月12日举办。讲习班将介绍因果发现相关的相关基础知识,从因果图构建的模型与假设出发,对基于约束的方法、基于因果函数模型的方法和混合型方法这三大类因果关系发现方法进行介绍;并针对因果图在社会调查、社交网络、人口变动分析等领域的应用进行探讨。同时,通过介绍如何使用python语言对典型的因果发现方法进行编程实现,以及使用Tetrad软件实现从数据中自动进行因果图构建的方法。

感兴趣的同学可以详细了解:BDSC2021前沿讲习班 | 社会系统中的因果发现





百科项目志愿者招募




作为集智百科项目团队的成员,本词条由中科院计算所博士生李奉治贡献。


以上内容都是我们做这项目的起点,作为来自不同学科和领域的志愿者,我们建立起一个有效的百科团队,分配有审校、翻译、编辑、宣传等工作。我们秉持:知识从我而来,问题到我为止的信念,认真负责编撰每一个词条。




在这里从复杂性知识出发与伙伴同行,同时我们希望有更多志愿者加入这个团队,使百科词条内容得到扩充,并为每位志愿者提供相应奖励与资源,建立个人主页与贡献记录,使其能够继续探索复杂世界。


如果你有意参与更加系统精细的分工,扫描二维码填写报名表,我们期待你的加入!



集智百科报名表


来源:集智百科

编辑:王建萍



推荐阅读


点击“阅读原文”,阅读词条Do演算原文与参考文献

您可能也对以下帖子感兴趣

文章有问题?点此查看未经处理的缓存