58
个编辑
更改
无编辑摘要
'''<font color="#ff8000">Do演算(Do-Calculus)</font>'''是由三条推演规则构成的推演系统，这三条规则可以将包含'''<font color="#ff8000">干预</font>'''变量和观测变量的概率分布表达式进行转化。
'''<font color="#ff8000">Do演算(Do-Calculus)</font>'''是由三条推演规则构成的推演系统，这三条规则可以将包含'''<font color="#ff8000">干预</font>'''变量和观测变量的概率分布表达式进行转化。
== 为何需要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|一个无法使用后门调整和前门调整的因果图]]
而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>指出的边后得到的子图。
=== 规则一 ===
'''增添或删除观察'''：
'''增添或删除观察'''：
:<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>
=== 规则二 ===
'''交换干预和观察'''：
'''交换干预和观察'''：
:<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>
=== 规则三 ===
'''增添或删除干预'''：
'''增添或删除干预'''：
其中符号<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) ==
=== 定理 ===
<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 ===
[[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算子的表达式。
* 第七步：（使用规则三）<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算法由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算法 ===
=== IDC算法 ===
== 代码实现 ==
软件/代码信息
软件/代码信息
== 参考文献 ==
<references />