更改

添加3字节 、 2021年7月18日 (日) 20:45
无编辑摘要
第1行: 第1行:  
'''<font color="#ff8000">Do演算(Do-Calculus)</font>'''是由三条推演规则构成的推演系统,这三条规则可以将包含'''<font color="#ff8000">干预</font>'''变量和观测变量的概率分布表达式进行转化。
 
'''<font color="#ff8000">Do演算(Do-Calculus)</font>'''是由三条推演规则构成的推演系统,这三条规则可以将包含'''<font color="#ff8000">干预</font>'''变量和观测变量的概率分布表达式进行转化。
   −
=== 为何需要Do演算 ===
+
== 为何需要Do演算 ==
    
[[File:An Example That Front Door and Back Door Don't Work.png|thumb|300px|一个无法使用后门调整和前门调整的因果图]]
 
[[File:An Example That Front Door and Back Door Don't Work.png|thumb|300px|一个无法使用后门调整和前门调整的因果图]]
第9行: 第9行:  
而Do演算是一个具有完备性的推演系统,可以处理所有可识别的模型,当然也就包括了右侧图中这个例子。同时,利用Do演算还有一系列的计算机算法,可以自动、高速地去判断一个模型的可识别性,并在可识别的模型中将包含Do算子的概率分布表达式转换为仅包含观测变量的概率分布表达式。
 
而Do演算是一个具有完备性的推演系统,可以处理所有可识别的模型,当然也就包括了右侧图中这个例子。同时,利用Do演算还有一系列的计算机算法,可以自动、高速地去判断一个模型的可识别性,并在可识别的模型中将包含Do算子的概率分布表达式转换为仅包含观测变量的概率分布表达式。
   −
=== Do演算规则集 ===
+
== Do演算规则集 ==
    
在以下规则的表述中,使用符号<math>G_{\overline{X}}</math>表示删除有向图<math>G</math>中所有指向结点<math>X</math>的边后得到的子图,使用符号<math>G_{\overline{X}\underline{Z}}</math>表示删除有向图<math>G</math>中所有指向结点<math>X</math>的边和从结点<math>Z</math>指出的边后得到的子图。
 
在以下规则的表述中,使用符号<math>G_{\overline{X}}</math>表示删除有向图<math>G</math>中所有指向结点<math>X</math>的边后得到的子图,使用符号<math>G_{\overline{X}\underline{Z}}</math>表示删除有向图<math>G</math>中所有指向结点<math>X</math>的边和从结点<math>Z</math>指出的边后得到的子图。
   −
==== 规则一 ====
+
=== 规则一 ===
 
'''增添或删除观察''':
 
'''增添或删除观察''':
   第19行: 第19行:  
:<math> P(Y|do(X),Z,W)=P(Y|do(X),Z)</math>
 
:<math> P(Y|do(X),Z,W)=P(Y|do(X),Z)</math>
   −
==== 规则二 ====
+
=== 规则二 ===
 
'''交换干预和观察''':
 
'''交换干预和观察''':
   第25行: 第25行:  
:<math> P(Y|do(X),do(Z),W)=P(Y|do(X),Z,W)</math>
 
:<math> P(Y|do(X),do(Z),W)=P(Y|do(X),Z,W)</math>
   −
==== 规则三 ====
+
=== 规则三 ===
 
'''增添或删除干预''':
 
'''增添或删除干预''':
   第33行: 第33行:  
其中符号<math> Z(W) </math> 表示 <math> Z / An(W)_{ G_{ \overline{X} } }</math> ,而符号<math> An(W)_{ G_{ \overline{X} } }</math> 表示在子图<math>G_{ \overline{X}} </math>中由结点集<math>W</math>及其祖先节点构成的点集。
 
其中符号<math> Z(W) </math> 表示 <math> Z / An(W)_{ G_{ \overline{X} } }</math> ,而符号<math> An(W)_{ G_{ \overline{X} } }</math> 表示在子图<math>G_{ \overline{X}} </math>中由结点集<math>W</math>及其祖先节点构成的点集。
   −
=== Do演算的完备性(Completeness) ===
+
== Do演算的完备性(Completeness) ==
==== 定理 ====
+
=== 定理 ===
 
<math> Q = P(y \mid do(x),z) </math> 是可识别的,当且仅当它可以被Do演算的三条规则转化为一个不包含Do算子的表达式。
 
<math> Q = P(y \mid do(x),z) </math> 是可识别的,当且仅当它可以被Do演算的三条规则转化为一个不包含Do算子的表达式。
   −
==== 证明 ====
+
=== 证明 ===
 
要证明上述定理的正确性,需要分别证明Do演算的可靠性(Soundness)和充分性(Sufficiency)。其中可靠性的证明由Judea Pearl于1995年给出<ref name="pearl:95">{{citation | last = Pearl | first = Judea | doi = 10.1093/biomet/82.4.669 | issue = 4 | journal = Biometrika | pages = 669–710 | title = Causal diagrams for empirical research | volume = 82 | year = 1995| url = https://escholarship.org/uc/item/6gv9n38c }}.</ref>,充分性的证明由Yimin Huang和Marco Valtorta于2006年给出<ref name="huang:06">{{cite journal |last1=Huang |first1=Yimin |last2=Valtorta |first2=Marco |date=2006 |title=Pearl's Calculus of Intervention is Complete |url= |journal=Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence |pages=217–224}}</ref>。
 
要证明上述定理的正确性,需要分别证明Do演算的可靠性(Soundness)和充分性(Sufficiency)。其中可靠性的证明由Judea Pearl于1995年给出<ref name="pearl:95">{{citation | last = Pearl | first = Judea | doi = 10.1093/biomet/82.4.669 | issue = 4 | journal = Biometrika | pages = 669–710 | title = Causal diagrams for empirical research | volume = 82 | year = 1995| url = https://escholarship.org/uc/item/6gv9n38c }}.</ref>,充分性的证明由Yimin Huang和Marco Valtorta于2006年给出<ref name="huang:06">{{cite journal |last1=Huang |first1=Yimin |last2=Valtorta |first2=Marco |date=2006 |title=Pearl's Calculus of Intervention is Complete |url= |journal=Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence |pages=217–224}}</ref>。
   −
=== 应用案例 ===
+
== 应用案例 ==
   −
==== 应用案例1 ====
+
=== 应用案例1 ===
 
[[File:Do-Calculus Example.png|thumb|300px|Do演算的案例1]]
 
[[File:Do-Calculus Example.png|thumb|300px|Do演算的案例1]]
 
在右侧的因果图中,“吸烟基因”是未观测变量,其余变量都是可观测的。“吸烟”变量使用<math>s</math>来表示,“焦油沉积”变量使用<math>t</math>来表示,“癌症”变量使用<math>c</math>来表示。我们要估计干预“吸烟”变量后对“癌症”变量的因果效应,即计算<math>P(c \mid do(s))</math>。我们将使用Do演算将这个表达式转换为不包含Do算子的表达式。
 
在右侧的因果图中,“吸烟基因”是未观测变量,其余变量都是可观测的。“吸烟”变量使用<math>s</math>来表示,“焦油沉积”变量使用<math>t</math>来表示,“癌症”变量使用<math>c</math>来表示。我们要估计干预“吸烟”变量后对“癌症”变量的因果效应,即计算<math>P(c \mid do(s))</math>。我们将使用Do演算将这个表达式转换为不包含Do算子的表达式。
第54行: 第54行:  
* 第七步:(使用规则三)<math>\Sigma_{s'}\Sigma_t P(c \mid t,s')P(s' \mid do(t))P(t \mid s) = \Sigma_{s'}\Sigma_t P(c \mid t,s')P(s')P(t \mid s)</math>
 
* 第七步:(使用规则三)<math>\Sigma_{s'}\Sigma_t P(c \mid t,s')P(s' \mid do(t))P(t \mid s) = \Sigma_{s'}\Sigma_t P(c \mid t,s')P(s')P(t \mid s)</math>
   −
=== 相关算法 ===
+
== 相关算法 ==
   −
==== 处理多变量干预算法 ====
+
=== 处理多变量干预算法 ===
 
Jin Tian和Judea Pearl于2002年提出了第一个可以处理多变量被干预的算法<ref>{{cite journal |last1=Tian |first1=Jin |last2=Pearl |first2=Judea |date=2002 |title=A General Identification Condition for Causal Effects |url= |journal=Eighteenth National Conference on Artificial Intelligence |pages=567–573}}</ref>。
 
Jin Tian和Judea Pearl于2002年提出了第一个可以处理多变量被干预的算法<ref>{{cite journal |last1=Tian |first1=Jin |last2=Pearl |first2=Judea |date=2002 |title=A General Identification Condition for Causal Effects |url= |journal=Eighteenth National Conference on Artificial Intelligence |pages=567–573}}</ref>。
   −
==== Identify算法 ====
+
=== Identify算法 ===
 
Identify算法由Yimin Huang和Marco Valtorta于2006年提出<ref>{{cite journal |last1=Huang |first1=Yimin |last2=Valtorta |first2=Marco |date=2006 |title=Identifiability in Causal Bayesian Networks: A Sound and Complete Algorithm |journal=Proceedings of the 21st National Conference on Artificial Intelligence |volume=2 |pages=1149–1154}}</ref>。这个算法相较于上述Tian(2002)的算法消除了的对因果图的半马尔科夫性的限制,且也可以处理多变量干预的问题。
 
Identify算法由Yimin Huang和Marco Valtorta于2006年提出<ref>{{cite journal |last1=Huang |first1=Yimin |last2=Valtorta |first2=Marco |date=2006 |title=Identifiability in Causal Bayesian Networks: A Sound and Complete Algorithm |journal=Proceedings of the 21st National Conference on Artificial Intelligence |volume=2 |pages=1149–1154}}</ref>。这个算法相较于上述Tian(2002)的算法消除了的对因果图的半马尔科夫性的限制,且也可以处理多变量干预的问题。
   −
==== ID算法 ====
+
=== ID算法 ===
   −
==== IDC算法 ====
+
=== IDC算法 ===
   −
=== 代码实现 ===
+
== 代码实现 ==
    
软件/代码信息
 
软件/代码信息
 +
 +
== 参考文献 ==
 +
<references />
58

个编辑