https://wiki.swarma.org/api.php?action=feedcontributions&user=Kuang&feedformat=atom
集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织 - 用户贡献 [zh-cn]
2024-03-29T13:07:01Z
用户贡献
MediaWiki 1.35.0
https://wiki.swarma.org/index.php?title=%E5%89%8D%E9%97%A8%E8%B0%83%E6%95%B4&diff=24635
前门调整
2021-07-23T15:31:02Z
<p>Kuang:/* 例子:吸烟与肺癌 */</p>
<hr />
<div><br />
==调整目的: 因果效应估计== <br />
<br />
我们期望在给定如下因果图的情况下,判断治疗变量 T 对结果变量 Y 的因果效应 <math> P(y|do(t))</math>,其中 W 是一个未观测的混淆变量,M 是中介变量。(注意:我们现在观测不到W,无法进行后门调整.。)<br />
[[文件:Front door.png|缩略图|229x229像素|前门调整]]<br />
<br />
<br />
<br />
主要步骤如下<ref>https://www.bradyneal.com/Introduction_to_Causal_Inference-Dec17_2020-Neal.pdf</ref>:<br />
<br />
#'''估计T对M的因果效应'''<math> P(m|do(t))</math> ,由于T-W-Y-M 这条路径被 [[阻断]] (见 [[D-分离]]) <math> P(m|do(t))=P(m|t)</math>.<br />
#'''估计M对Y的因果效应'''<math> P(y|do(m))</math>, 由于 T 阻断了[[后门路径]] M<-T<-W ->Y, 根据[[后门调整]] 我们可以轻松得到<math> P(y|do(m))= \sum_t P(y|m,t) P(t)</math>.<br />
#'''结合以上两种因果效应'''<math> P(y|do(t))= \sum_m P(y|do(m)) P(m| do(t))</math>.<br />
<br />
==前门准则<ref>Pearl, Judea. "Models, reasoning and inference." ''Cambridge, UK: CambridgeUniversityPress'' 19 (2000).</ref>==<br />
定义:我们说变量集 M 关于 T 和 Y 满足前门准则,若:<br />
<br />
# M 完全中介了 T 和 Y,即所有从T到Y的因果路径都经过M。<br />
# 从 T 到 M 没有未被阻断的[[后门路径]]。<br />
# 所有从M到Y的[[后门路径]]被 T阻断。<br />
<br />
==前门调整==<br />
若变量集M关于(T,Y)满足前门准则,并且我们有<math> P(t,m)>0</math>, T对Y的因果效应是可识别的,<br />
<br />
<math> P(y|do(t))= \sum_m P(m| t) \sum_{t'} P(y|m,t') P(t') </math>.<br />
<br />
==例子:吸烟与肺癌==<br />
[[文件:吸烟与肺癌.png|缩略图|吸烟与肺癌。S=smoking=吸烟(对应表中X),T=Tar=焦油(对应表中Z),C=cancer=肺癌(对应表中Y),G=gene=基因。我们需要估计吸烟对肺癌的因果效应。]]<br />
[[文件:吸烟肺癌数据.png|缩略图|吸烟、焦油、肺癌数据。]]<br />
{| class="wikitable"<br />
|+吸烟、焦油、肺癌数据<br />
!<br />
!组别<br />
!P(x,z) (每个组别所占百分比)<br />
!<nowiki>P(Y=1|x,z) (每组内罹患癌症的百分比)</nowiki><br />
|-<br />
!X=0,Z=0<br />
!非吸烟者,肺内无焦油<br />
!47.5<br />
!10<br />
|-<br />
!X=1,Z=0<br />
!吸烟者,肺内无焦油<br />
!2.5<br />
!90<br />
|-<br />
!X=0,Z=1<br />
!非吸烟者,肺内有焦油<br />
!2.5<br />
!5<br />
|-<br />
!X=1,Z=1<br />
!吸烟者,肺内有焦油<br />
!47.5<br />
!85<br />
|}<br />
从数据中来看,似乎吸烟对肺癌有显著影响,但是烟草公司会从不同的角度争辩,从而给出不同的答案。若我们只看非吸烟者,体内有焦油可以的患癌率从10%降到了5%;若们只看吸烟者,体内有焦油可以的患癌率从90%降到了85%,可见焦油有防护作用。<br />
<br />
<br />
<br />
数学上,前门调整可以被运用,<br />
<br />
<math> P(Y=1|do(X=0))= 0.4975,P(Y=1|do(X=1))= 0.4525, </math>。<br />
<br />
<br />
<br />
<br />
<references /></div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%89%8D%E9%97%A8%E8%B0%83%E6%95%B4&diff=24634
前门调整
2021-07-23T15:29:34Z
<p>Kuang:/* 例子:吸烟与肺癌 */</p>
<hr />
<div><br />
==调整目的: 因果效应估计== <br />
<br />
我们期望在给定如下因果图的情况下,判断治疗变量 T 对结果变量 Y 的因果效应 <math> P(y|do(t))</math>,其中 W 是一个未观测的混淆变量,M 是中介变量。(注意:我们现在观测不到W,无法进行后门调整.。)<br />
[[文件:Front door.png|缩略图|229x229像素|前门调整]]<br />
<br />
<br />
<br />
主要步骤如下<ref>https://www.bradyneal.com/Introduction_to_Causal_Inference-Dec17_2020-Neal.pdf</ref>:<br />
<br />
#'''估计T对M的因果效应'''<math> P(m|do(t))</math> ,由于T-W-Y-M 这条路径被 [[阻断]] (见 [[D-分离]]) <math> P(m|do(t))=P(m|t)</math>.<br />
#'''估计M对Y的因果效应'''<math> P(y|do(m))</math>, 由于 T 阻断了[[后门路径]] M<-T<-W ->Y, 根据[[后门调整]] 我们可以轻松得到<math> P(y|do(m))= \sum_t P(y|m,t) P(t)</math>.<br />
#'''结合以上两种因果效应'''<math> P(y|do(t))= \sum_m P(y|do(m)) P(m| do(t))</math>.<br />
<br />
==前门准则<ref>Pearl, Judea. "Models, reasoning and inference." ''Cambridge, UK: CambridgeUniversityPress'' 19 (2000).</ref>==<br />
定义:我们说变量集 M 关于 T 和 Y 满足前门准则,若:<br />
<br />
# M 完全中介了 T 和 Y,即所有从T到Y的因果路径都经过M。<br />
# 从 T 到 M 没有未被阻断的[[后门路径]]。<br />
# 所有从M到Y的[[后门路径]]被 T阻断。<br />
<br />
==前门调整==<br />
若变量集M关于(T,Y)满足前门准则,并且我们有<math> P(t,m)>0</math>, T对Y的因果效应是可识别的,<br />
<br />
<math> P(y|do(t))= \sum_m P(m| t) \sum_{t'} P(y|m,t') P(t') </math>.<br />
<br />
==例子:吸烟与肺癌==<br />
[[文件:吸烟与肺癌.png|缩略图|吸烟与肺癌。S=smoking=吸烟(对应表中X),T=Tar=焦油(对应表中Z),C=cancer=肺癌(对应表中Y),G=gene=基因。我们需要估计吸烟对肺癌的因果效应。]]<br />
[[文件:吸烟肺癌数据.png|缩略图|吸烟、焦油、肺癌数据。]]<br />
{| class="wikitable"<br />
|+吸烟、焦油、肺癌数据<br />
!<br />
!组别<br />
!P(x,z) (每个组别所占百分比)<br />
!<nowiki>P(Y=1|x,z) (每组内罹患癌症的百分比)</nowiki><br />
|-<br />
!X=0,Z=0<br />
!非吸烟者,肺内无焦油<br />
!47.5<br />
!10<br />
|-<br />
!X=1,Z=0<br />
!吸烟者,肺内无焦油<br />
!2.5<br />
!90<br />
|-<br />
!X=0,Z=1<br />
!非吸烟者,肺内有焦油<br />
!2.5<br />
!5<br />
|-<br />
!X=1,Z=1<br />
!吸烟者,肺内有焦油<br />
!47.5<br />
!85<br />
|}<br />
从数据中来看,似乎吸烟对肺癌有显著影响,但是烟草公司会从不同的角度争辩,从而给出不同的答案。若我们只看非吸烟者,体内有焦油可以的患癌率从10%降到了5%;若们只看吸烟者,体内有焦油可以的患癌率从90%降到了85%,可见焦油有防护作用。<br />
<br />
<br />
数学上,前门调整可以被运用。<br />
<br />
<br />
<br />
<br />
<br />
<br />
<references /></div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%89%8D%E9%97%A8%E8%B0%83%E6%95%B4&diff=24633
前门调整
2021-07-23T15:20:28Z
<p>Kuang:/* 例子:吸烟与肺癌 */</p>
<hr />
<div><br />
==调整目的: 因果效应估计== <br />
<br />
我们期望在给定如下因果图的情况下,判断治疗变量 T 对结果变量 Y 的因果效应 <math> P(y|do(t))</math>,其中 W 是一个未观测的混淆变量,M 是中介变量。(注意:我们现在观测不到W,无法进行后门调整.。)<br />
[[文件:Front door.png|缩略图|229x229像素|前门调整]]<br />
<br />
<br />
<br />
主要步骤如下<ref>https://www.bradyneal.com/Introduction_to_Causal_Inference-Dec17_2020-Neal.pdf</ref>:<br />
<br />
#'''估计T对M的因果效应'''<math> P(m|do(t))</math> ,由于T-W-Y-M 这条路径被 [[阻断]] (见 [[D-分离]]) <math> P(m|do(t))=P(m|t)</math>.<br />
#'''估计M对Y的因果效应'''<math> P(y|do(m))</math>, 由于 T 阻断了[[后门路径]] M<-T<-W ->Y, 根据[[后门调整]] 我们可以轻松得到<math> P(y|do(m))= \sum_t P(y|m,t) P(t)</math>.<br />
#'''结合以上两种因果效应'''<math> P(y|do(t))= \sum_m P(y|do(m)) P(m| do(t))</math>.<br />
<br />
==前门准则<ref>Pearl, Judea. "Models, reasoning and inference." ''Cambridge, UK: CambridgeUniversityPress'' 19 (2000).</ref>==<br />
定义:我们说变量集 M 关于 T 和 Y 满足前门准则,若:<br />
<br />
# M 完全中介了 T 和 Y,即所有从T到Y的因果路径都经过M。<br />
# 从 T 到 M 没有未被阻断的[[后门路径]]。<br />
# 所有从M到Y的[[后门路径]]被 T阻断。<br />
<br />
==前门调整==<br />
若变量集M关于(T,Y)满足前门准则,并且我们有<math> P(t,m)>0</math>, T对Y的因果效应是可识别的,<br />
<br />
<math> P(y|do(t))= \sum_m P(m| t) \sum_{t'} P(y|m,t') P(t') </math>.<br />
<br />
==例子:吸烟与肺癌==<br />
[[文件:吸烟与肺癌.png|缩略图|吸烟与肺癌。S=smoking=吸烟,T=Tar=焦油,C=cancer=肺癌,G=gene=基因。我们需要估计吸烟对肺癌的因果效应。]]<br />
[[文件:吸烟肺癌数据.png|缩略图|吸烟、焦油、肺癌数据。]]<br />
{| class="wikitable"<br />
|+吸烟、焦油、肺癌数据<br />
!<br />
!组别<br />
!P(x,z) (每个组别所占百分比)<br />
!<nowiki>P(Y=1|x,z) (每组内罹患癌症的百分比)</nowiki><br />
|-<br />
!X=0,Z=0<br />
!非吸烟者,肺内无焦油<br />
!47.5<br />
!10<br />
|-<br />
!X=1,Z=0<br />
!吸烟者,肺内无焦油<br />
!2.5<br />
!90<br />
|-<br />
!X=0,Z=1<br />
!非吸烟者,肺内有焦油<br />
!2.5<br />
!5<br />
|-<br />
!X=1,Z=1<br />
!吸烟者,肺内有焦油<br />
!47.5<br />
!85<br />
|}<br />
从数据中来看,似乎吸烟对肺癌有显著影响,但是烟草公司会从不同的角度争辩,从而给出不同的答案。<br />
<br />
<references /></div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%89%8D%E9%97%A8%E8%B0%83%E6%95%B4&diff=24632
前门调整
2021-07-23T15:08:55Z
<p>Kuang:/* 例子 */</p>
<hr />
<div><br />
==调整目的: 因果效应估计== <br />
<br />
我们期望在给定如下因果图的情况下,判断治疗变量 T 对结果变量 Y 的因果效应 <math> P(y|do(t))</math>,其中 W 是一个未观测的混淆变量,M 是中介变量。(注意:我们现在观测不到W,无法进行后门调整.。)<br />
[[文件:Front door.png|缩略图|229x229像素|前门调整]]<br />
<br />
<br />
<br />
主要步骤如下<ref>https://www.bradyneal.com/Introduction_to_Causal_Inference-Dec17_2020-Neal.pdf</ref>:<br />
<br />
#'''估计T对M的因果效应'''<math> P(m|do(t))</math> ,由于T-W-Y-M 这条路径被 [[阻断]] (见 [[D-分离]]) <math> P(m|do(t))=P(m|t)</math>.<br />
#'''估计M对Y的因果效应'''<math> P(y|do(m))</math>, 由于 T 阻断了[[后门路径]] M<-T<-W ->Y, 根据[[后门调整]] 我们可以轻松得到<math> P(y|do(m))= \sum_t P(y|m,t) P(t)</math>.<br />
#'''结合以上两种因果效应'''<math> P(y|do(t))= \sum_m P(y|do(m)) P(m| do(t))</math>.<br />
<br />
==前门准则<ref>Pearl, Judea. "Models, reasoning and inference." ''Cambridge, UK: CambridgeUniversityPress'' 19 (2000).</ref>==<br />
定义:我们说变量集 M 关于 T 和 Y 满足前门准则,若:<br />
<br />
# M 完全中介了 T 和 Y,即所有从T到Y的因果路径都经过M。<br />
# 从 T 到 M 没有未被阻断的[[后门路径]]。<br />
# 所有从M到Y的[[后门路径]]被 T阻断。<br />
<br />
==前门调整==<br />
若变量集M关于(T,Y)满足前门准则,并且我们有<math> P(t,m)>0</math>, T对Y的因果效应是可识别的,<br />
<br />
<math> P(y|do(t))= \sum_m P(m| t) \sum_{t'} P(y|m,t') P(t') </math>.<br />
<br />
==例子:吸烟与肺癌==<br />
[[文件:吸烟与肺癌.png|缩略图|吸烟与肺癌。S=smoking=吸烟,T=Tar=焦油,C=cancer=肺癌,G=gene=基因。我们需要估计吸烟对肺癌的因果效应。]]<br />
[[文件:吸烟肺癌数据.png|缩略图|吸烟、焦油、肺癌数据。]]<br />
<references /></div>
Kuang
https://wiki.swarma.org/index.php?title=%E6%96%87%E4%BB%B6:%E5%90%B8%E7%83%9F%E8%82%BA%E7%99%8C%E6%95%B0%E6%8D%AE.png&diff=24631
文件:吸烟肺癌数据.png
2021-07-23T15:07:37Z
<p>Kuang:</p>
<hr />
<div>吸烟肺癌数据</div>
Kuang
https://wiki.swarma.org/index.php?title=%E6%96%87%E4%BB%B6:%E5%90%B8%E7%83%9F%E4%B8%8E%E8%82%BA%E7%99%8C.png&diff=24630
文件:吸烟与肺癌.png
2021-07-23T14:58:36Z
<p>Kuang:</p>
<hr />
<div>S=smoking=吸烟,T=Tar=焦油,C=cancer=肺癌,G=gene=基因。我们需要估计吸烟对肺癌的因果效应。</div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%89%8D%E9%97%A8%E8%B0%83%E6%95%B4&diff=24629
前门调整
2021-07-23T14:50:50Z
<p>Kuang:/* 前门调整 */</p>
<hr />
<div><br />
==调整目的: 因果效应估计== <br />
<br />
我们期望在给定如下因果图的情况下,判断治疗变量 T 对结果变量 Y 的因果效应 <math> P(y|do(t))</math>,其中 W 是一个未观测的混淆变量,M 是中介变量。(注意:我们现在观测不到W,无法进行后门调整.。)<br />
[[文件:Front door.png|缩略图|229x229像素|前门调整]]<br />
<br />
<br />
<br />
主要步骤如下<ref>https://www.bradyneal.com/Introduction_to_Causal_Inference-Dec17_2020-Neal.pdf</ref>:<br />
<br />
#'''估计T对M的因果效应'''<math> P(m|do(t))</math> ,由于T-W-Y-M 这条路径被 [[阻断]] (见 [[D-分离]]) <math> P(m|do(t))=P(m|t)</math>.<br />
#'''估计M对Y的因果效应'''<math> P(y|do(m))</math>, 由于 T 阻断了[[后门路径]] M<-T<-W ->Y, 根据[[后门调整]] 我们可以轻松得到<math> P(y|do(m))= \sum_t P(y|m,t) P(t)</math>.<br />
#'''结合以上两种因果效应'''<math> P(y|do(t))= \sum_m P(y|do(m)) P(m| do(t))</math>.<br />
<br />
==前门准则==<br />
定义:我们说变量集 M 关于 T 和 Y 满足前门准则,若:<br />
<br />
# M 完全中介了 T 和 Y,即所有从T到Y的因果路径都经过M。<br />
# 从 T 到 M 没有未被阻断的[[后门路径]]。<br />
# 所有从M到Y的后门路径被 T阻断。<br />
<br />
==前门调整==<br />
若变量集M关于(T,Y)满足前门准则,并且我们有<math> P(t,m)>0</math>, T对Y的因果效应是可识别的,<br />
<br />
<math> P(y|do(t))= \sum_m P(m| t) \sum_{t'} P(y|m,t') P(t') </math>.<br />
<br />
==例子==<br />
<br />
<references /></div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%89%8D%E9%97%A8%E8%B0%83%E6%95%B4&diff=24628
前门调整
2021-07-23T14:49:38Z
<p>Kuang:/* 有后门路径的定义,链接到后门调整 */</p>
<hr />
<div><br />
==调整目的: 因果效应估计== <br />
<br />
我们期望在给定如下因果图的情况下,判断治疗变量 T 对结果变量 Y 的因果效应 <math> P(y|do(t))</math>,其中 W 是一个未观测的混淆变量,M 是中介变量。(注意:我们现在观测不到W,无法进行后门调整)<br />
[[文件:Front door.png|缩略图|229x229像素|前门调整]]<br />
<br />
<br />
<br />
主要步骤如下<ref>https://www.bradyneal.com/Introduction_to_Causal_Inference-Dec17_2020-Neal.pdf</ref>:<br />
<br />
#'''估计T对M的因果效应'''<math> P(m|do(t))</math> ,由于T-W-Y-M 这条路径被 [[阻断]] (见 [[D-分离]]) <math> P(m|do(t))=P(m|t)</math><br />
#'''估计M对Y的因果效应'''<math> P(y|do(m))</math>, 由于 T 阻断了[[后门路径]] M<-T<-W ->Y, 根据[[后门调整]] 我们可以轻松得到<math> P(y|do(m))= \sum_t P(y|m,t) P(t)</math><br />
#'''结合以上两种因果效应'''<math> P(y|do(t))= \sum_m P(y|do(m)) P(m| do(t))</math><br />
<br />
==前门准则==<br />
定义:我们说变量集 M 关于 T 和 Y 满足前门准则,若:<br />
<br />
# M 完全中介了 T 和 Y,即所有从T到Y的因果路径都经过M。<br />
# 从 T 到 M 没有未被阻断的[[后门路径]]。<br />
# 所有从M到Y的后门路径被 T阻断。<br />
<br />
==前门调整==<br />
若变量集M关于(T,Y)满足前门准则,并且我们有<math> P(t,m)>0</math>, T对Y的因果效应是可识别的,<br />
<br />
<math> P(y|do(t))= \sum_m P(m| t) \sum_t' P(y|m,t') P(t') </math><br />
<br />
==例子==<br />
<br />
<references /></div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%89%8D%E9%97%A8%E8%B0%83%E6%95%B4&diff=24609
前门调整
2021-07-22T08:46:44Z
<p>Kuang:/* 调整目的: 因果效应估计 */</p>
<hr />
<div><br />
==调整目的: 因果效应估计== <br />
<br />
我们期望在给定如下因果图的情况下,判断治疗变量 T 对结果变量 Y 的因果效应 <math> P(y|do(t))</math>,其中 W 是一个未观测的混淆变量,M 是中介变量。(注意:我们现在观测不到W,无法进行后门调整)<br />
[[文件:Front door.png|缩略图|229x229像素|前门调整]]<br />
<br />
<br />
<br />
主要步骤如下<ref>https://www.bradyneal.com/Introduction_to_Causal_Inference-Dec17_2020-Neal.pdf</ref>:<br />
<br />
#'''估计T对M的因果效应'''<math> P(m|do(t))</math> ,由于T-W-Y-M 这条路径被 [[阻断]] (见 [[D-分离]]) <math> P(m|do(t))=P(m|t)</math><br />
#'''估计M对Y的因果效应'''<math> P(y|do(m))</math>, 由于 T 阻断了[[后门路径]] M<-T<-W ->Y, 根据[[后门调整]] 我们可以轻松得到<math> P(y|do(m))= \sum_t P(y|m,t) P(t)</math><br />
#'''结合以上两种因果效应'''<math> P(y|do(t))= \sum_m P(y|do(m)) P(m| do(t))</math><br />
<br />
==前门准则==<br />
<br />
===有后门路径的定义,链接到后门调整===<br />
<nowiki>https://cse.sc.edu/~javidian/Notes_Presentations/BackFrontDoor.pdf</nowiki><br />
<br />
==前门调整(内容包含调整公式)==<br />
<br />
==例子==<br />
<br />
<references /></div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%89%8D%E9%97%A8%E8%B0%83%E6%95%B4&diff=24608
前门调整
2021-07-22T08:44:22Z
<p>Kuang:/* 调整目的: 因果效应估计 */</p>
<hr />
<div><br />
==调整目的: 因果效应估计== <br />
<br />
我们期望在给定如下因果图的情况下,判断治疗变量 T 对结果变量 Y 的因果效应 <math> P(y|do(t))</math>,其中 W 是一个未观测的混淆变量,M 是中介变量。(注意:我们现在观测不到W,无法进行后门调整)<br />
[[文件:Front door.png|缩略图|229x229像素|前门调整]]<br />
<br />
<br />
<br />
主要步骤如下<ref>https://www.bradyneal.com/Introduction_to_Causal_Inference-Dec17_2020-Neal.pdf</ref>:<br />
<br />
#'''估计T对M的因果效应'''<math> P(m|do(t))</math> ,由于T-W-Y-M 这条路径被 [[阻断]] (见 [[D-分离]]) <math> P(m|do(t))=P(m|t)</math><br />
#'''估计M对Y的因果效应'''<math> P(y|do(m))</math>, 由于 T 阻断了[[后门路径]] M<-T<-W ->Y, 根据[[后门调整]] 我们可以轻松得到<math> P(y|do(m))= \sum_t P(y|m,t) P(t)</math><br />
#结合以上两种因果效应<math> P(y|do(t))= \sum_m P(y|do(m)) P(m| do(t))</math><br />
<br />
==前门准则==<br />
<br />
===有后门路径的定义,链接到后门调整===<br />
<nowiki>https://cse.sc.edu/~javidian/Notes_Presentations/BackFrontDoor.pdf</nowiki><br />
<br />
==前门调整(内容包含调整公式)==<br />
<br />
==例子==<br />
<br />
<references /></div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%89%8D%E9%97%A8%E8%B0%83%E6%95%B4&diff=24607
前门调整
2021-07-22T08:27:36Z
<p>Kuang:/* 调整目的: 因果效应估计 */</p>
<hr />
<div><br />
==调整目的: 因果效应估计== <br />
<br />
我们期望在给定如下因果图的情况下,判断治疗变量 T 对结果变量 Y 的因果效应 <math> P(y|do(t))</math>,其中 W 是一个未观测的混淆变量,M 是中介变量。(注意:我们现在观测不到W,无法进行后门调整)<br />
[[文件:Front door.png|缩略图|229x229像素|前门调整]]<br />
<br />
<br />
<br />
主要步骤如下<ref>https://www.bradyneal.com/Introduction_to_Causal_Inference-Dec17_2020-Neal.pdf</ref>:<br />
<br />
#'''估计T对M的因果效应'''<math> P(m|do(t))</math> ,由于T-W-Y-M 这条路径被 [[阻断]] (见 [[D-分离]]) <math> P(m|do(t))=P(m|t)</math><br />
#'''估计M对Y的因果效应'''<math> P(y|do(m))</math>, 由于 T 阻断了[[后门路径]] M<-T<-W ->Y, 根据[[后门调整]] 我们可以轻松得到<math> P(y|do(m))= \sum_t P(y|m,t) P(t)</math><br />
#结合以上两种因果效应<br />
<br />
==前门准则==<br />
<br />
===有后门路径的定义,链接到后门调整===<br />
<nowiki>https://cse.sc.edu/~javidian/Notes_Presentations/BackFrontDoor.pdf</nowiki><br />
<br />
==前门调整(内容包含调整公式)==<br />
<br />
==例子==<br />
<br />
<references /></div>
Kuang
https://wiki.swarma.org/index.php?title=Do%E6%BC%94%E7%AE%97&diff=24606
Do演算
2021-07-22T08:11:14Z
<p>Kuang:/* 为何需要Do演算 */</p>
<hr />
<div>'''<font color="#ff8000">Do演算(Do-Calculus)</font>'''是由三条推演规则构成的推演系统,这三条规则可以将包含'''<font color="#ff8000">干预</font>'''变量和观测变量的概率分布表达式进行转化。<br />
<br />
== 为何需要Do演算 ==<br />
<br />
[[File:An Example That Front Door and Back Door Don't Work.png|thumb|300px|一个无法使用后门调整和前门调整的因果图]]<br />
<br />
在处理一部分因果图时,可以使用[[后门调整]]'''<font color="#ff8000">后门调整</font>'''和[[前门调整]]等技术进行统计调整,这样可以根据不涉及[[Do算子]]的数据来估算干预的效果。然而我们无法根据前门准则和后门准则事先确定一个给定的因果模型是否适用于这样的统计调整方式。后门调整和前门调整方法也无法处理所有'''<font color="#ff8000">可识别</font>'''的模型,例如右侧的因果图是可识别的,但既无法使用后门调整也无法使用前门调整。<br />
<br />
而Do演算是一个具有完备性的推演系统,可以处理所有可识别的模型,当然也就包括了右侧图中这个例子。同时,利用Do演算还有一系列的计算机算法,可以自动、高速地去判断一个模型的可识别性,并在可识别的模型中将包含Do算子的概率分布表达式转换为仅包含观测变量的概率分布表达式。<br />
<br />
== Do演算规则集 ==<br />
<br />
在以下规则的表述中,使用符号<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>指出的边后得到的子图。<br />
<br />
=== 规则一 ===<br />
'''增添或删除观察''':<br />
<br />
对于有向图<math>G</math>,若满足<math>(Y \perp\!\!\!\perp Z \mid X, W)_{G_{\overline{X}}}</math>(即在子图<math>G_{\overline{X}}</math>中,给定结点集<math>X</math>和<math>W</math>时,结点集<math>Y</math>和<math>Z</math>满足d-分离条件),则<br />
:<math> P(Y|do(X),Z,W)=P(Y|do(X),Z)</math><br />
<br />
=== 规则二 ===<br />
'''交换干预和观察''':<br />
<br />
对于有向图<math>G</math>,若满足<math>(Y \perp\!\!\!\perp Z \mid X, W)_{G_{\overline{X}\underline{Z}}}</math>(即在子图<math>G_{\overline{X}\underline{Z}}</math>中,给定结点集<math>X</math>和<math>W</math>时,结点集<math>Y</math>和<math>Z</math>满足d-分离条件),则<br />
:<math> P(Y|do(X),do(Z),W)=P(Y|do(X),Z,W)</math><br />
<br />
=== 规则三 ===<br />
'''增添或删除干预''':<br />
<br />
对于有向图<math>G</math>,若满足<math>(Y \perp\!\!\!\perp Z \mid X, W)_{G_{\overline{X}\underline{Z(W)}}}</math>(即在子图<math>G_{\overline{X}\underline{Z(W)}}</math>中,给定结点集<math>X</math>和<math>W</math>时,结点集<math>Y</math>和<math>Z</math>满足d-分离条件),则<br />
:<math> P(Y|do(X),do(Z),W)=P(Y|do(X),W)</math><br />
<br />
其中符号<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>及其祖先节点构成的点集。<br />
<br />
== Do演算的完备性(Completeness) ==<br />
=== 定理 ===<br />
<math> Q = P(y \mid do(x),z) </math> 是可识别的,当且仅当它可以被Do演算的三条规则转化为一个不包含Do算子的表达式。<br />
<br />
=== 证明 ===<br />
要证明上述定理的正确性,需要分别证明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>。<br />
<br />
== 应用案例 ==<br />
<br />
=== 应用案例1 ===<br />
[[File:Do-Calculus Example.png|thumb|300px|Do演算的案例1]]<br />
在右侧的因果图中,“吸烟基因”是未观测变量,其余变量都是可观测的。“吸烟”变量使用<math>s</math>来表示,“焦油沉积”变量使用<math>t</math>来表示,“癌症”变量使用<math>c</math>来表示。我们要估计干预“吸烟”变量后对“癌症”变量的因果效应,即计算<math>P(c \mid do(s))</math>。我们将使用Do演算将这个表达式转换为不包含Do算子的表达式。<br />
<br />
* 第一步:(使用概率公理)<math>P(c \mid do(s)) = \Sigma_t P(c \mid do(s), t)P(t \mid do(s))</math><br />
* 第二步:(使用规则二)<math>\Sigma_t P(c \mid do(s), t)P(t \mid do(s)) = \Sigma_t P(c \mid do(s), do(t))P(t \mid do(s))</math><br />
* 第三步:(使用规则二)<math>\Sigma_t P(c \mid do(s), do(t))P(t \mid do(s)) = \Sigma_t P(c \mid do(s), do(t))P(t \mid s)</math><br />
* 第四步:(使用规则三)<math>\Sigma_t P(c \mid do(s), do(t))P(t \mid s) = \Sigma_t P(c \mid do(t))P(t \mid s)</math><br />
* 第五步:(使用概率公理)<math>\Sigma_t P(c \mid do(t))P(t \mid s) = \Sigma_{s'}\Sigma_t P(c \mid do(t),s')P(s' \mid do(t))P(t \mid s)</math><br />
* 第六步:(使用规则二)<math>\Sigma_{s'}\Sigma_t P(c \mid do(t),s')P(s' \mid do(t))P(t \mid s) = \Sigma_{s'}\Sigma_t P(c \mid t,s')P(s' \mid do(t))P(t \mid s)</math><br />
* 第七步:(使用规则三)<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><br />
<br />
== 相关算法 ==<br />
<br />
=== 处理多变量干预算法 ===<br />
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>。<br />
<br />
=== Identify算法 ===<br />
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)的算法消除了的对因果图的半马尔科夫性的限制,且也可以处理多变量干预的问题。<br />
<br />
=== ID算法 ===<br />
ID算法由Ilya Shpitser和Judea Pearl与2006年提出<ref>{{cite journal |last1=Shpitser |first1=Ilya |last2=Pearl |first2=Judea |date=2006 |title=Identification of Joint Interventional Distributions in Recursive Semi-Markovian Causal Models |journal=Proceedings of the 21st National Conference on Artificial Intelligence |volume=2 |pages=1219–1226}}</ref>,该算法的能力与上述Tian(2002)的算法等价,但更易于编程实现。<br />
<br />
=== IDC算法 ===<br />
IDC算法由Ilya Shpitser和Judea Pearl与2006年提出<ref>{{cite journal |last1=Shpitser |first1=Ilya |last2=Pearl |first2=Judea |date=2006 |title=Identification of Conditional Interventional Distributions |journal=Proceedings of the Twenty-Second Conference on Uncertainty in Artificial Intelligence |pages=437–444}}</ref>,该算法是基于ID算法拓展的,可以处理联合干预条件分布的因果效应求解问题。<br />
<br />
== 代码实现 ==<br />
<br />
=== Ananke ===<br />
Ananke框架基于Python语言实现,集成了ID算法,详细内容可见[https://gitlab.com/causal/ananke Ananke开源地址]<br />
<br />
=== causaleffect ===<br />
causaleffect框架基于R语言实现,集成了ID算法和IDC算法,详细内容可见[https://cran.r-project.org/web/packages/causaleffect/index.html causaleffect包信息地址]<br />
<br />
=== CEE ===<br />
CEE框架基于Golang语言实现,集成了ID算法、IDC算法、Identify算法等,详细内容可见[https://github.com/L-F-Z/CEE CEE开源地址]<br />
<br />
== 参考文献 ==<br />
<references /></div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%89%8D%E9%97%A8%E8%B0%83%E6%95%B4&diff=24605
前门调整
2021-07-22T08:09:23Z
<p>Kuang:</p>
<hr />
<div><br />
==调整目的: 因果效应估计== <br />
<br />
我们期望在给定如下因果图的情况下,判断治疗变量 T 对结果变量 Y 的因果效应 $P(Y| do(t))$,其中 W 是一个未观测的混淆变量,M 是中介变量。(注意:我们现在观测不到W,无法进行后门调整)<br />
[[文件:Front door.png|缩略图|229x229像素|前门调整]]<br />
<br />
<br />
<br />
主要步骤如下<ref>https://www.bradyneal.com/Introduction_to_Causal_Inference-Dec17_2020-Neal.pdf</ref>:<br />
<br />
# 估计T对M的因果效应<br />
# 估计M对Y的因果效应<br />
# 结合以上两种因果效应<br />
<br />
==前门准则==<br />
<br />
===有后门路径的定义,链接到后门调整===<br />
<nowiki>https://cse.sc.edu/~javidian/Notes_Presentations/BackFrontDoor.pdf</nowiki><br />
<br />
==前门调整(内容包含调整公式)==<br />
<br />
==例子==</div>
Kuang
https://wiki.swarma.org/index.php?title=%E6%96%87%E4%BB%B6:Front_door.png&diff=24603
文件:Front door.png
2021-07-22T08:02:24Z
<p>Kuang:</p>
<hr />
<div>front_door_from_brady</div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%89%8D%E9%97%A8%E8%B0%83%E6%95%B4&diff=24599
前门调整
2021-07-21T14:25:42Z
<p>Kuang:</p>
<hr />
<div><br />
==调整目的: 因果效应估计== <br />
<br />
我们期望在给定如下因果图的情况下,判断治疗变量 T 对结果变量 Y 的因果效应 $P(Y| do(t))$,其中 W 是一个未观测的混淆变量,M 是中介变量。(注意:我们现在观测不到W,无法进行后门调整)<br />
<br />
主要步骤如下<ref>https://www.bradyneal.com/Introduction_to_Causal_Inference-Dec17_2020-Neal.pdf</ref>:<br />
<br />
# 估计T对M的因果效应<br />
# 估计M对Y的因果效应<br />
# 结合以上两种因果效应<br />
<br />
<br />
<nowiki>https://www.youtube.com/watch?v=-kWocwaXqlk&ab_channel=BradyNeal-CausalInference</nowiki><br />
<br />
==前门准则==<br />
<br />
===有后门路径的定义,链接到后门调整===<br />
<nowiki>https://cse.sc.edu/~javidian/Notes_Presentations/BackFrontDoor.pdf</nowiki><br />
<br />
==前门调整(内容包含调整公式)==<br />
<br />
==例子==</div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%89%8D%E9%97%A8%E8%B0%83%E6%95%B4&diff=24598
前门调整
2021-07-21T14:10:19Z
<p>Kuang:</p>
<hr />
<div><br />
== 调整目的: 因果效应估计 == <br />
<br />
<br />
<nowiki>https://www.youtube.com/watch?v=-kWocwaXqlk&ab_channel=BradyNeal-CausalInference</nowiki><br />
<br />
== 前门准则 ==<br />
<br />
===有后门路径的定义,链接到后门调整===<br />
<nowiki>https://cse.sc.edu/~javidian/Notes_Presentations/BackFrontDoor.pdf</nowiki><br />
<br />
== 前门调整(内容包含调整公式)==<br />
<br />
== 例子 ==</div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%89%8D%E9%97%A8%E8%B0%83%E6%95%B4&diff=24597
前门调整
2021-07-21T14:09:23Z
<p>Kuang:建立内容为“ # 调整目的: 因果效应估计 <nowiki>https://www.youtube.com/watch?v=-kWocwaXqlk&ab_channel=BradyNeal-CausalInference</nowiki> #前门准则(3条…”的新页面</p>
<hr />
<div><br />
# 调整目的: 因果效应估计 <br />
<br />
<br />
<nowiki>https://www.youtube.com/watch?v=-kWocwaXqlk&ab_channel=BradyNeal-CausalInference</nowiki><br />
<br />
#前门准则(3条)<br />
<br />
===有后门路径的定义,链接到后门调整===<br />
<nowiki>https://cse.sc.edu/~javidian/Notes_Presentations/BackFrontDoor.pdf</nowiki><br />
<br />
#前门调整(内容包含调整公式)<br />
<br />
#例子</div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%BF%A0%E5%AE%9E%E6%80%A7%E5%81%87%E8%AE%BE&diff=23875
忠实性假设
2021-06-18T09:08:05Z
<p>Kuang:/* 因果忠实性 */</p>
<hr />
<div>==因果忠实性==<br />
在因果发现或贝叶斯网络结构学习中,我们会建立一些假设来保证结构的可识别性,忠实性假设就是其中之一。<br />
<br />
===定义===<br />
<br />
假设某个总体是忠实的,那就是假设其中发生的任何独立性都不是来自不可思议的巧合,而是来自结构。<ref name="introduction">Scheines R. (1997) [https://pattern.swarma.org/paper?id=72ab907c-c3b0-11eb-a051-0242ac170007 An introduction to causal inference].</ref><br />
(总体:统计学概念,指包含所研究的全部个体(数据)的集合)<br />
<br />
考虑一个多变量联合概率分布<math>P_{X}</math>和一个有向无环图DAG <math>\mathcal{G}</math>.<br />
<br />
定义:联合概率分布 <math>P_{X}</math> 对于给定的 DAG <math>\mathcal{G}</math> 满足因果忠实性,如果<ref name="Elements">Peters Jonas,Janzing Dominik,Schlkopf Bernhard (2017) [https://pattern.swarma.org/paper?id=5c93b918-c3ba-11eb-8fd5-0242ac170007 Elements of Causal Inference: Foundations and Learning Algorithms].</ref>:<br />
<br />
<math>A \perp\!\!\!\perp B \mid C \Rightarrow A \perp\!\!\!\perp_{\mathcal{G}} B \mid C</math><br />
<br />
对于所有不相交的顶点(变量)集 A,B,C 均成立。<br />
<br />
这个定义暗示了一个与全局马尔可夫条件相反的结论:<br />
<br />
<math>A \perp\!\!\!\perp_{\mathcal{G}} B \mid C \Rightarrow A \perp\!\!\!\perp B \mid C</math><br />
<br />
粗略一看,忠实性并不是很直观。 我们现在给出一个马尔可夫分布的例子,但对于给定的 DAG <math>\mathcal{G_{1}}</math> 不忠实。 这是通过使两条路径相互抵消并创建图结构未暗示的独立性来实现的。<br />
<br />
====违背忠实性的例子<ref name="Elements"/>====<br />
<br />
考虑下图:<br />
<br />
<gallery><br />
Faithful-3.png<br />
</gallery><br />
<br />
我们首先看一个线性高斯 <math>SCM</math> 对应于左图<math>\mathcal{G_{1}}</math>。<br />
<br />
<gallery><br />
Faithful-4.png<br />
</gallery><br />
<br />
正态分布的噪声变量<math>N_{X} ∼ \mathcal{N} (0,\sigma^2_X )</math>、<math>N_{Y} ∼ \mathcal{N} (0,\sigma^2_Y )</math> 和 <math>N_{Z} ∼ \mathcal{N} (0,\sigma^2_Z )</math> 共同独立。 这是带有图<math>\mathcal{G_{1}}</math> 的线性高斯 <math>SCM</math> 的示例。 现在,如果<br />
<br />
<math>a \cdot b + c = 0</math> (1)<br />
<br />
由于我们获得 <math>X \perp\!\!\!\perp Z</math>,因此分布不忠实于<math>\mathcal{G_{1}}</math>,这不是图结构所暗示的。读者可以轻松验证存在带有DAG <math>\mathcal{G_{2}}</math>的SCM引出相同分布。<br />
<br />
为了在前面的例子中获得额外的独立性,我们必须“调整”系数,使得两条路径在(1)中相互抵消。 Spirtes等人[2000, Theorem 3.2]对于线性模型表明,如果我们假设系数是从正密度中随机抽取的,那么这种情况发生的概率为零。<br />
<br />
上例中的分布对于<math>\mathcal{G_{2}}</math>是忠实的,但对于<math>\mathcal{G_{1}}</math>则不是。尽管如此,对于这两个模型,如果没有任何参数归零,则满足因果最小性。换句话说,该分布对于<math>\mathcal{G_{1}}</math> 或<math>\mathcal{G_{2}}</math>的任何真子图都不是马尔可夫的,因为删除任何边将对应于在分布中不成立的新(条件)独立性; 注意<math>\mathcal{G_{2}}</math>不是<math>\mathcal{G_{1}}</math>的真子图。 然而,它是<math>\mathcal{H}</math>的真子图,因此,该分布不满足关于<math>\mathcal{H}</math>的因果最小性。通常,因果最小性弱于忠实性。<br />
<br />
通过假定因果图满足因果马尔可夫性,我们假设此因果图产生的所有总体都具有通过对其应用d分离而获得的独立性关系。 但是,并不能因此而得出结论,这些总体恰好具有这些独立性关系并且没有其他独立性关系。<ref name="introduction"/><br />
<br />
===示例<ref name="introduction"/>===<br />
<br />
<gallery><br />
因果忠实性假设图例1.png|运动,吸烟和健康之间的关系<br />
</gallery><br />
<br />
图1中描述了运动,吸烟和健康之间的关系,其中+和-分别表示正向和抑制性关系。<br />
<br />
在这种结构可能产生的某些分布中,可能存在巧合,如果吸烟对健康有直接的负面影响,但是吸烟对运动有积极的影响(可能看起来很奇怪),而锻炼对健康有积极的影响,那么吸烟可以直接抑制健康并间接改善健康。<br />
<br />
如果这两种效应恰好完全平衡并因此抵消,那么吸烟与健康之间可能根本就没有关联。<br />
<br />
在这种情况下,我们说总体分布不忠实于产生它的因果图。<br />
<noinclude><br />
<br />
==参考文献==<br />
</noinclude></div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%BF%A0%E5%AE%9E%E6%80%A7%E5%81%87%E8%AE%BE&diff=23249
忠实性假设
2021-06-06T07:34:13Z
<p>Kuang:/* 定义 */</p>
<hr />
<div>==因果忠实性==<br />
<br />
===定义===<br />
<br />
假设某个总体是忠实的,那就是假设其中发生的任何独立性都不是来自不可思议的巧合,而是来自结构。<ref name="introduction">Scheines R. (1997) [https://pattern.swarma.org/paper?id=72ab907c-c3b0-11eb-a051-0242ac170007 An introduction to causal inference].</ref><br />
(总体:统计学概念,指包含所研究的全部个体(数据)的集合)<br />
<br />
考虑一个多变量联合概率分布<math>P_{X}</math>和一个有向无环图DAG <math>\mathcal{G}</math>.<br />
<br />
定义:联合概率分布 <math>P_{X}</math> 对于给定的 DAG <math>\mathcal{G}</math> 满足因果忠实性,如果<ref name="Elements">Peters Jonas,Janzing Dominik,Schlkopf Bernhard (2017) [https://pattern.swarma.org/paper?id=5c93b918-c3ba-11eb-8fd5-0242ac170007 Elements of Causal Inference: Foundations and Learning Algorithms].</ref>:<br />
<br />
<math>A \perp\!\!\!\perp B \mid C \Rightarrow A \perp\!\!\!\perp_{\mathcal{G}} B \mid C</math><br />
<br />
对于所有不相交的顶点(变量)集 A,B,C 均成立。<br />
<br />
这个定义暗示了一个与全局马尔可夫条件相反的结论:<br />
<br />
<math>A \perp\!\!\!\perp_{\mathcal{G}} B \mid C \Rightarrow A \perp\!\!\!\perp B \mid C</math><br />
<br />
粗略一看,忠实性并不是很直观。 我们现在给出一个马尔可夫分布的例子,但对于给定的 DAG <math>\mathcal{G_{1}}</math> 不忠实。 这是通过使两条路径相互抵消并创建图结构未暗示的独立性来实现的。<br />
<br />
====违背忠实性的例子<ref name="Elements"/>====<br />
<br />
考虑下图:<br />
<br />
<gallery><br />
Faithful-3.png<br />
</gallery><br />
<br />
我们首先看一个线性高斯 <math>SCM</math> 对应于左图<math>\mathcal{G_{1}}</math>。<br />
<br />
<gallery><br />
Faithful-4.png<br />
</gallery><br />
<br />
正态分布的噪声变量<math>N_{X} ∼ \mathcal{N} (0,\sigma^2_X )</math>、<math>N_{Y} ∼ \mathcal{N} (0,\sigma^2_Y )</math> 和 <math>N_{Z} ∼ \mathcal{N} (0,\sigma^2_Z )</math> 共同独立。 这是带有图<math>\mathcal{G_{1}}</math> 的线性高斯 <math>SCM</math> 的示例。 现在,如果<br />
<br />
<math>a \cdot b + c = 0</math> (1)<br />
<br />
由于我们获得 <math>X \perp\!\!\!\perp Z</math>,因此分布不忠实于<math>\mathcal{G_{1}}</math>,这不是图结构所暗示的。读者可以轻松验证存在带有DAG <math>\mathcal{G_{2}}</math>的SCM引出相同分布。<br />
<br />
为了在前面的例子中获得额外的独立性,我们必须“调整”系数,使得两条路径在(1)中相互抵消。 Spirtes等人[2000, Theorem 3.2]对于线性模型表明,如果我们假设系数是从正密度中随机抽取的,那么这种情况发生的概率为零。<br />
<br />
上例中的分布对于<math>\mathcal{G_{2}}</math>是忠实的,但对于<math>\mathcal{G_{1}}</math>则不是。尽管如此,对于这两个模型,如果没有任何参数归零,则满足因果最小性。换句话说,该分布对于<math>\mathcal{G_{1}}</math> 或<math>\mathcal{G_{2}}</math>的任何真子图都不是马尔可夫的,因为删除任何边将对应于在分布中不成立的新(条件)独立性; 注意<math>\mathcal{G_{2}}</math>不是<math>\mathcal{G_{1}}</math>的真子图。 然而,它是<math>\mathcal{H}</math>的真子图,因此,该分布不满足关于<math>\mathcal{H}</math>的因果最小性。通常,因果最小性弱于忠实性。<br />
<br />
通过假定因果图满足因果马尔可夫性,我们假设此因果图产生的所有总体都具有通过对其应用d分离而获得的独立性关系。 但是,并不能因此而得出结论,这些总体恰好具有这些独立性关系并且没有其他独立性关系。<ref name="introduction"/><br />
<br />
===示例<ref name="introduction"/>===<br />
<br />
<gallery><br />
因果忠实性假设图例1.png|运动,吸烟和健康之间的关系<br />
</gallery><br />
<br />
图1中描述了运动,吸烟和健康之间的关系,其中+和-分别表示正向和抑制性关系。<br />
<br />
在这种结构可能产生的某些分布中,可能存在巧合,如果吸烟对健康有直接的负面影响,但是吸烟对运动有积极的影响(可能看起来很奇怪),而锻炼对健康有积极的影响,那么吸烟可以直接抑制健康并间接改善健康。<br />
<br />
如果这两种效应恰好完全平衡并因此抵消,那么吸烟与健康之间可能根本就没有关联。<br />
<br />
在这种情况下,我们说总体分布不忠实于产生它的因果图。<br />
<noinclude><br />
==参考文献==<br />
</noinclude></div>
Kuang
https://wiki.swarma.org/index.php?title=%E6%9C%89%E5%90%91%E6%97%A0%E7%8E%AF%E5%9B%BE_Directed_acyclic_graph&diff=23248
有向无环图 Directed acyclic graph
2021-06-06T07:28:47Z
<p>Kuang:</p>
<hr />
<div>本词条由孙钦贵初步翻译<br />
<br />
[[文件:Example_of_a_directed_acyclic_graph.png|thumb|right|250px|图1:一个有向无环图的例子 Example of a directed acyclic graph]]<br />
<br />
在图论和计算机科学中,<font color="#ff8000">'''有向无环图 Directed acyclic graph'''</font>(DAG 或 dag)是一个没有定向循环的有向图。也就是说,它由<font color="#ff8000"> '''顶点 Vertex''' </font>和<font color="#ff8000"> '''边 Edge''' </font>(也称为弧)组成,每条边都从一个顶点指向另一个顶点,沿着这些顶点的方向 不会形成一个闭合的<font color="#ff8000"> '''环 Loop''' </font>。有向图是一个有向无环图当且仅当它可以通过将顶点按照与所有边方向一致的线性顺序排列构成<font color="#ff8000"> '''拓扑排序 Topologically ordered''' </font>。有向无环图有许多科学的和计算的应用,从生物学(进化论,家谱,流行病学)到社会学(引文网络)到计算(调度)。<br />
<br />
<br />
<br />
==定义==<br />
图是由顶点和连接顶点对的边组成的,顶点可以是任何一种由边成对连接的对象。在有向图中,每条边都有一个方向,从一个顶点到另一个顶点。有向图中的<font color="#ff8000"> '''路径 Path''' </font>是一个边序列,序列中每条边的结束顶点是序列中下一条边的起始顶点; 如果一条路的第一条边的起始顶点与它的最后一条边的结束顶点相同,那么它就形成了一个环。有向无环图即为没有环出现的有向图。<ref name="thul">{{citation|title=Graphs: Theory and Algorithms|first1=K.|last1=Thulasiraman|first2=M. N. S.|last2=Swamy|publisher=John Wiley and Son|year=1992|isbn=978-0-471-51356-8|contribution=5.7 Acyclic Directed Graphs|page=118}}.</ref><ref name="bang">{{citation|title=Digraphs: Theory, Algorithms and Applications|first1=Jørgen|last1=Bang-Jensen|series=Springer Monographs in Mathematics|edition=2nd|publisher=Springer-Verlag|year=2008|isbn=978-1-84800-997-4|contribution=2.1 Acyclic Digraphs|pages=32–34}}.</ref><ref>{{citation|title=Graph theory: an algorithmic approach|first=Nicos|last=Christofides|author-link=Nicos Christofides||publisher=Academic Press|year=1975|pages=170–174}}.</ref><br />
<br><br />
<br />
当存在一条从顶点{{mvar|u}}到顶点{{mvar|v}}的路径时,顶点v被称作是从顶点{{mvar|u}}<font color="#ff8000"> '''可达的 Reachability''' </font>。每个顶点都是从自身可达的(通过一条没有边的路径)。如果一个顶点可以从一条<font color="#32cd32"> 非平凡</font>路径(一条由一个或更多边组成的路径)到达自身,那么这条路径就是一个环。因此,有向无环图也可以被定义为没有顶点可以通过非平凡路径到达自身的图。<ref>{{citation|title=Simulation Techniques for Discrete Event Systems|volume=14|series=Cambridge Computer Science Texts|first=I.|last=Mitrani|year=1982|publisher=Cambridge University Press|isbn=9780521282826|page=27|url=https://books.google.com/books?id=CF04AAAAIAAJ&pg=PA27}}.</ref><br />
<br />
== 数学性质 ==<br />
<br />
=== 可达性,传递闭包和传递归约 ===<br />
[[file:Example_of_a_directed_acyclic_graph.png|thumb|right|175px|图2:有向无环图G A DAG]] [[file:Example_of_a_directed_acyclic_graph.png|thumb|right|124px|图3:G的传递规约 Transitive reduction of G]]<br />
<br />
有向无环图的<font color="#ff8000"> '''可达性 Reachability''' </font>可以用其顶点的<font color="#ff8000"> '''偏序关系 Partial order''' </font>{{math|≤}}来表示。在偏序关系中,如果存在一条路径从顶点{{mvar|u}}指向顶点{{mvar|v}},它们的偏序关系可被写作{{math|''u'' ≤ ''v''}}。这也被称作{{mvar|v}}是从{{mvar|u}}可达的。<ref>{{citation|title=The Design and Analysis of Algorithms|series=Monographs in Computer Science|first=Dexter|last=Kozen|authorlink=Dexter Kozen|publisher=Springer|year=1992|isbn=978-0-387-97687-7|page=9|url=https://books.google.com/books?id=L_AMnf9UF9QC&pg=PA9}}.</ref>不同的有向无环图可以有着相同的可达关系和偏序关系。<ref>{{citation|title=Loop Transformations for Restructuring Compilers: The Foundations|first=Utpal|last=Banerjee|publisher=Springer|year=1993|isbn=978-0-7923-9318-4|page=19|contribution=Exercise 2(c)|url=https://books.google.com/books?id=Cog7zSSlqFwC&pg=PA19}}.</ref>例如,有两条边{{math|''a'' → ''b''}},{{math|''b'' → ''c''}}的有向无环图,和有三条边的{{math|''a'' → ''b''}}, {{math|''b'' → ''c''}},{{math|''a'' → ''c''}}的有向无环图有着相同的偏序关系{{math|''a'' ≤ ''b'' ≤ ''c''}}。<br />
<br />
[[file:Example_of_a_directed_acyclic_graph.png|thumb|right|175px|图4:将{ x, y, z }的幂集按包含偏序排序得到的哈斯图]] <br />
对于一个有向无环图{{mvar|G}},它的<font color="#ff8000"> '''传递闭包 Transitive closure''' </font>等同于一个在保持与其相同可达性的情况下,边数最多的图。在这个图中,当{{mvar|u}}可达{{mvar|v}}的时候,边{{math|''u'' → ''v''}}必定存在。换句话说,每个{{mvar|G}}中的非相同元素<!-- distinct elements -->偏序关系对{{math|''u''&nbsp;≤&nbsp;''v''}}都在这个图中有一条边。这可以被视作用图来可视化图{{mvar|G}}的可达性关系。<br />
<br />
有向无环图{{mvar|G}}的<font color="#ff8000"> '''传递规约 Transitive reduction''' </font>为和其有着相同可达性,边数最少的图。它是{{mvar|G}}的一个子图。构造方法为当{{mvar|G}}有着一条更长的路径连接顶点{{mvar|u}}和{{mvar|v}}的时候,消去边{{math|''u'' → ''v''}}。<br />
传递约简和传递闭包都是有向无环图的特有概念<!-- is uniquely defined 唯一的? -->。相反的,对于有向有环图,可以存在多个与原图有着相同可达性的最简子图。<ref>{{citation|title=Digraphs: Theory, Algorithms and Applications|series=Springer Monographs in Mathematics|first1=Jørgen|last1=Bang-Jensen|first2=Gregory Z.|last2=Gutin|publisher=Springer|year=2008|isbn=978-1-84800-998-1|url=https://books.google.com/books?id=4UY-ucucWucC&pg=PA36|contribution=2.3 Transitive Digraphs, Transitive Closures and Reductions|pages=36–39}}.</ref><br />
<br />
对于有向无环图G和表达其可达性的偏序关系≤,它的传递规约也可以看作包含G的<font color="#ff8000"> '''覆盖关系 Covering relation''' </font>中每一条边的G的子图。传递规约在图示有向无环图的偏序关系时十分有用,因为它们比其他具有相同偏序关系的图的边数要少,这简化了绘图。偏序关系的<font color="#ff8000"> '''哈斯图 Hasse diagram''' </font>由将传递规约中的每条边的起点绘制在其终点的下方而得到。<ref>{{citation|title=Graphs, Networks and Algorithms|volume=5|series=Algorithms and Computation in Mathematics|first=Dieter|last=Jungnickel|publisher=Springer|year=2012|isbn=978-3-642-32278-5|pages=92–93|url=https://books.google.com/books?id=PrXxFHmchwcC&pg=PA92}}.</ref><br />
<br />
=== 拓扑排序===<br />
[[file:Example_of_a_directed_acyclic_graph.png|thumb|right|175px|图5:一个有向无环图的拓扑排序:每一条边都从排序的前一条(左上)到排序的后一条(右下)。有向图是无环的当且仅当它具有拓扑序]] [[file:Example_of_a_directed_acyclic_graph.png|thumb|right|124px|图6:将红色边添加到蓝色有向无环图中会产生另一个DAG,即蓝色图的传递闭包。对于每个红边或蓝边uv,v可以从u到达:存在一条从u开始到v结束的蓝色路径。]]<br />
有向无环图的<font color="#ff8000"> '''拓扑排序 Topological ordering''' </font>为所有边的起点都出现在其终点之前的排序。能构成拓扑排序的图一定没有环,因为环中的一条边必定从排序较后的顶点指向比其排序更前的顶点。<ref name="bang"/>基于此,拓扑排序可以被用来定义有向无环图:当且仅当一个有向图有拓扑排序,它是有向无环图。一般情况下,拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下,有唯一的拓扑排序方式,这时,拓扑排序与它们在这条路径中出现的顺序相同。<ref>{{citation|title=Algorithms|first1=Robert|last1=Sedgewick|author1-link=Robert Sedgewick (computer scientist)|first2=Kevin|last2=Wayne|edition=4th|publisher=Addison-Wesley|year=2011|isbn=978-0-13-276256-4|url=https://books.google.com/books?id=idUdqdDXqnAC&pg=PA598|pages=598–599|contribution=4,2,25 Unique topological ordering}}.</ref><br />
<br />
有向无环图的拓扑排序族等同于其可达性的<font color="#ff8000"> '''线性拓展 Linear extension''' </font>族。 <ref>{{citation|title=A Short Course in Discrete Mathematics|series=Dover Books on Computer Science|first1=Edward A.|last1=Bender|first2=S. Gill|last2=Williamson|publisher=Courier Dover Publications|year=2005|isbn=978-0-486-43946-4|page=142|url=https://books.google.com/books?id=iuEoAwAAQBAJ&pg=PA142|contribution=Example 26 (Linear extensions – topological sorts)}}.</ref>因此,偏序关系相同的任意两个图会有相同的拓扑排序集。<br />
<br />
=== 组合计数 ===<br />
罗宾逊 Robinson (1973) 研究了有向无环图的<font color="#ff8000"> '''图计数 Graph enumeration''' </font>问题。<ref name="enum">{{citation|first=R. W.|last=Robinson|contribution=Counting labeled acyclic digraphs|pages=239–273|editor-first=F.|editor-last=Harary|editor-link=Frank Harary|title=New Directions in the Theory of Graphs|publisher=Academic Press|year=1973}}. See also {{citation<br />
|last1 = Harary | first1 = Frank | author1-link = Frank Harary | first2 = Edgar M. | last2 = Palmer | year = 1973| title = Graphical Enumeration | publisher = [[Academic Press]] | isbn = 978-0-12-324245-7 | page=19}}.</ref><br />
如标号顶点在拓扑排序中出现的顺序不受限制,有{{mvar|n}}个顶点的标号有向无环图的数量为<br />
:1, 1, 3, 25, 543, 29281, 3781503, … (OEIS中的数列A003024)。<br />
其中{{math|1=''n''&nbsp;=&nbsp;0, 1, 2, 3,……}}。这个数列的<font color="#ff8000"> '''递推关系式 Recurrence relation''' </font>是<br />
:<math>a_n = \sum_{k=1}^n (-1)^{k-1} {n\choose k}2^{k(n-k)} a_{n-k}.</math><ref name="enum" /><br />
埃里克·韦斯坦因 Eric W. Weisstein <ref>{{MathWorld | urlname=WeissteinsConjecture | title=Weisstein's Conjecture}}</ref>,{{mvar|n}}个顶点的标号有向无环图的数量与其中所有<font color="#ff8000"> '''特征值 Eigenvalues''' </font>都为正实数的{{math|n*n}}<font color="#ff8000"> '''逻辑矩阵''' </font>的数量相同。这一点随后被 McKay 证实,证明采用了<font color="#ff8000"> '''双射法 Bijective'''</font>:一个矩阵{{mvar|A}}是有向无环图的一个<font color="#ff8000"> '''邻接矩阵 Adjacency matrix''' </font>,当且仅当{{math|''A''&nbsp;+&nbsp;''I''}}是一个所有特征值都为正数的逻辑矩阵,其中{{mvar|I}}为<font color="#ff8000"> '''单位矩阵 Identity matrix''' </font>。因为一个有向无环图不允许<font color="#ff8000"> '''自环 Self-loops''' </font>,它的邻接矩阵的对角线必定全为0。因此,加上{{mvar|I}}保持了所有矩阵因子都是0或1的特性。<ref>{{citation|last1=McKay|first1=B. D.|author1-link=Brendan McKay|last2=Royle|first2=G. F.|author2-link=Gordon Royle|last3=Wanless|first3=I. M.|last4=Oggier|first4=F. E.|author4-link= Frédérique Oggier |last5=Sloane|first5=N. J. A.|author5-link= Neil Sloane|last6=Wilf|first6=H.|author6-link=Herbert Wilf|title=Acyclic digraphs and eigenvalues of (0,1)-matrices|journal=[[Journal of Integer Sequences]]|volume=7|year=2004|url=http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Sloane/sloane15.html}}, Article 04.3.3.</ref><br />
<br />
=== 相关概念 ===<br />
[[file:Example_of_a_directed_acyclic_graph.png|thumb|right|175px|图7:多重树,一种由无向树的边定向而成的有向无环图]]<br />
[[file:Example_of_a_directed_acyclic_graph.png|thumb|right|124px|图8:多重树,是一种DAG,其中每个从一个顶点(红色)可到达的子图都是一棵树]]<font color="#ff8000"> '''多重树 Polytree''' </font>由将自由树的边<font color="#ff8000"> '''定向 Orienting''' </font>而得到。<ref>{{citation<br />
| last1 = Rebane<br />
| first1 = George<br />
| last2 = Pearl<br />
| first2 = Judea<br />
| author2-link = Judea Pearl<br />
| contribution = The recovery of causal poly-trees from statistical data<br />
| pages = 222–228<br />
| title = in Proc. 3rd Annual Conference on Uncertainty in Artificial Intelligence (UAI 1987), Seattle, WA, USA, July 1987<br />
| url = ftp://ftp.cs.ucla.edu/tech-report/198_-reports/870031.pdf<br />
| year = 1987<br />
}}{{Dead link|date=July 2019 |bot=InternetArchiveBot |fix-attempted=yes }}.</ref> 多重树必定是有向无环图。对于有根树,将其所有边赋予指离根的方向也可以得到有向无环图,即<font color="#ff8000"> '''树状图''' </font>。<br />
<!--- rough translation & ref needed ---><br />
<br />
<font color="#32cd32">强明确树 Multitree </font>是每两个顶点最多被一条路径所连接的有向无环图。等价的说,它是满足以下性质的一个有向无环图:对于图中每个顶点{{mvar|v}},从{{mvar|v}}可达的顶点组成一颗树。<ref>{{citation<br />
| last1 = Furnas | first1 = George W. | author1-link = George Furnas<br />
| last2 = Zacks | first2 = Jeff<br />
| contribution = Multitrees: enriching and reusing hierarchical structure<br />
| doi = 10.1145/191666.191778<br />
| pages = 330–336<br />
| title = Proc. SIGCHI conference on Human Factors in Computing Systems (CHI '94)<br />
| year = 1994| isbn = 978-0897916509 }}.</ref><br />
<br />
== 相关计算问题 ==<br />
=== 基于邻接矩阵的有向无环图的判别方法 ===<br />
<br />
=== 拓扑排序和识别 ===<br />
{{Main|拓扑排序}}<br />
可以用<font color="#ff8000"> '''线性时间复杂度''' </font>的卡恩算法来找到一个有向无环图的拓扑排序。<ref name="clrs">{{Introduction to Algorithms|edition=2}} Section 22.4, Topological sort, pp. 549–552.</ref>简单来说,开设一个存放结果的列表{{mvar|L}},先将入度为零的节点放到{{mvar|L}}中,因为这些节点没有任何的父节点。将与这些节点相连的边从图中去掉,再寻找图中入度为零的节点。对于新找到的节点来说,他们的父节点已经都在{{mvar|L}}中了,所以也可以从末端插入{{mvar|L}}。重复上述操作,直到找不到入度为零的节点。<ref name="j50" /> 另外一种构造拓扑排序的算法是将<font color="#ff8000"> '''深度优先搜索''' </font>的<font color="#ff8000"> '''后序遍历''' </font>结果翻转。<ref name="clrs" /><br />
<br />
检查一个有向图是否为有向无环图亦可在线性时间内完成。一种方法是先找到一个拓扑排序,然后测试这个排序是否能符合图中每条边所连顶点在排序中应该出现的顺序。<ref>For [[深度优先搜索|depth-first search]] based topological sorting algorithm, this validity check can be interleaved with the topological sorting algorithm itself; see e.g. {{citation|title=The Algorithm Design Manual|first=Steven S.|last=Skiena|publisher=Springer|year=2009|isbn=978-1-84800-070-4|pages=179–181|url=https://books.google.com/books?id=7XUSn0IKQEgC&pg=PA179}}.</ref> 对于卡恩算法在内的部分拓扑排序算法,通过在算法终止时判断是否满足一定条件即可知道图是否有环。<ref name="j50">{{harvtxt|Jungnickel|2012}}, pp. 50–51.</ref>如果有环,卡恩算法最终获得的{{mvar|L}}中节点个数会与图的节点总数不同。<br />
<br />
=== 从其他图构建===<br />
任意无向图都可以被转化为有向无环图。构造方法是选定一个顶点的<font color="#ff8000"> '''全序关系 Total order''' </font>,并将无向图中所有边从全序关系中较前的顶点指向较后的顶点。这种方法是定向方法中的<font color="#ff8000"> '''无环定向 Acyclic orientation''' </font>。不同的全序关系可能推出相同的无环定向,因此一个包含{{mvar|n}}个顶点的图的无环定向数量小于{{math|''n''!}}<!---全序关系数量?--->。如果定义{{mvar|χ}}为给定图的<font color="#ff8000"> '''色多项式 Chromatic polynomial''' </font>,无环定向数量等于{{math|{{!}}''χ''(−1){{!}}}}。<ref>{{citation|first=Richard P.|last=Stanley|authorlink=Richard P. Stanley|title=Acyclic orientations of graphs|journal=Discrete Mathematics|volume=5|issue=2 |pages=171–178|year= 1973|doi=10.1016/0012-365X(73)90108-8|url=http://math.mit.edu/~rstan/pubs/pubfiles/18.pdf}}.</ref><br />
<br />
[[file:Example_of_a_directed_acyclic_graph.png|thumb|right|175px|图9:黄色有向无环图是蓝色有向图的缩合。它是通过将蓝色图的每个强连通部分收缩为一个黄色顶点而形成的]]<br />
任意有环有向图都可以被转化为有向无环图。只要从图中移除<font color="#ff8000"> '''反馈节点集 Feedback vertex set''' </font>或<font color="#ff8000"> '''反馈边集 Feedback arc set''' </font>,即对于图中每个环,至少包括环中一个顶点或边的集合。不过,找到反馈节点或边的最小集合是<font color="#ff8000"> '''NP困难 NP-hard''' </font>问题。<ref>{{citation | last1=Garey | first1=Michael R. | authorlink1=Michael Garey | last2=Johnson | first2=David S. | authorlink2=David S. Johnson | year=1979| title=[[Computers and Intractability|Computers and Intractability: A Guide to the Theory of NP-Completeness]]| publisher=[[W. H. Freeman and Company|W.&nbsp;H.&nbsp;Freeman]]| isbn=0-7167-1045-5| chapter = Problems GT7 and GT8| pages = 191–192}}</ref> 另外一种方法将有环有向图去环的方法是将每个强连通分量[[边收缩|收缩]]为一个顶点。<ref>{{citation|title=Structural Models: An Introduction to the Theory of Directed Graphs|last1=Harary|first1=Frank|author1-link=Frank Harary|last2=Norman|first2=Robert Z.|last3=Cartwright|first3=Dorwin|publisher=John Wiley & Sons|year=1965|page=63}}.</ref> 对于无环图,它的最小反馈顶点或边集为<font color="#ff8000"> '''空集''' </font>,它的强连通分量则为自身。<br />
<br />
=== 传递闭包和传递约简 ===<br />
有向无环图的传递闭包可以通过<font color="#ff8000"> '''广度优先搜索''' </font>或<font color="#ff8000"> '''深度优先搜索''' </font>对每个节点测试可达性来构建。算法对于一个有着{{mvar|n}}个顶点和{{mvar|m}}条边的有向无环图的复杂度为{{math|''O''(''mn'')}}。<ref>{{harvtxt|Skiena|2009}}, p. 495.</ref>也可以使用<font color="#ff8000"> '''矩阵乘法算法 Matrix multiplication algorithm''' </font>中最快的<font color="#ff8000"> '''Coppersmith–Winograd算法'''</font>,其复杂度为{{math|''O''(''n''<sup>''2.3728639''</sup>)}}。这个算法理论上在<font color="#ff8000"> '''稠密图 Dense graph'''</font>中快过{{math|''O''(''mn'')}}。<ref>{{harvtxt|Skiena|2009}}, p. 496.</ref><br />
<br />
不论在哪种传递闭包算法中,那些被一条长度至少为2的路径所连接的顶点对,都可以和只有一条长度为1的路径所连接的顶点对区分开。由于传递约简包含后者,传递约简可以在和传递闭包相同的<font color="#ff8000"> '''渐进时间复杂度 Asymptotic computational complexity''' </font>中被构建。<ref>{{harvtxt|Bang-Jensen|Gutin|2008}}, p. 38.</ref><br />
<br />
=== 闭包问题 ===<br />
闭包是一个图中没有出边的顶点子集,即不存在从子集中顶点指向子集外顶点的边。<font color="#ff8000"> '''闭包问题 Closure problem''' </font>是则是找到带权图中使得权之和最大或最小的子集。闭包问题可以看作<font color="#ff8000"> '''最大流问题''' </font>的简化版,在<font color="#ff8000"> '''多项式时间''' </font>内被解决。实际上,是否有环对于找到闭包没有影响。<ref>{{citation<br />
| last = Picard | first = Jean-Claude<br />
| doi = 10.1287/mnsc.22.11.1268<br />
| issue = 11<br />
| journal = {{tsl|en|Management Science (journal)||Management Science}}<br />
| mr = 0403596<br />
| pages = 1268–1272<br />
| title = Maximal closure of a graph and applications to combinatorial problems<br />
| volume = 22<br />
| year = 1976}}.</ref><br />
<br />
=== 最短或最长路径问题 ===<br />
基于拓扑排序的性质,有向无环图的[[最短路问题 Shortest paths]]和[[最长路径问题 Longest paths]]可以在线性时间内解决。将顶点拓扑排序后,从前到后遍历每一个顶点,对于遍历到的顶点,更新其所有出边所到达顶点的长度值。如果求最短路,则在本边是更短路径的一部分时更新。求最长路则反之。<ref>Cormen et al. 2001, Section 24.2, Single-source shortest paths in directed acyclic graphs, pp. 592–595.</ref>对于非有向无环图,最短路需要用复杂度为<math>O(|E|+|V|\log|V|)</math>的<font color="#ff8000"> '''戴克斯特拉算法 Dijkstra's algorithm''' </font>或<math>O (|V| |E|)</math>的<font color="#ff8000"> '''贝尔曼-福特算法 Bellman–Ford algorithm''' </font>等。<ref>Cormen et al. 2001, Sections 24.1, The Bellman–Ford algorithm, pp. 588–592, and 24.3, Dijkstra's algorithm, pp. 595–601.</ref>最长路径则是一个[[NP困难|NP困难问题]]。<ref>Cormen et al. 2001, p. 966.</ref><br />
<br />
==应用==<br />
=== 调度 ===<br />
有向无环图的偏序关系可以在[[時間表|调度]]有着先后顺序限制的系统任务中发挥作用。<ref>{{harvtxt|Skiena|2009}}, p. 469.</ref>调度问题的一个重要种类是串联需要更新的对象,如[[電子試算表]]中某个单元格的计算公式依赖于其他单元格,或在程序的[[源代码]]被修改后重新编译[[目标代码|目标文件]]。<font color="#ff8000"> '''依赖图 Dependency graph''' </font>则记录了这种更新依赖关系。其每个顶点对应一个需要被更新的对象,边则表示更新的关系。依赖图中的环被称为<font color="#ff8000"> '''环状依赖 Circular dependency''' </font>。环状依赖通常是不被允许出现的,因为不能保证圈内任务排定顺序的一致性。无环的依赖图即为有向无环图。<ref>{{citation | last1=Al-Mutawa | first1=H. A. | last2=Dietrich | first2=J. | last3=Marsland | first3=S. | last4=McCartin | first4=C. | contribution=On the shape of circular dependencies in Java programs | doi=10.1109/ASWEC.2014.15 | pages=48–57 | publisher=IEEE | title=23rd Australian Software Engineering Conference | year=2014| isbn=978-1-4799-3149-1 }}.</ref><br />
<br />
举例来说,当电子表格中一个单元格的数值发生改变,其他直接或间接依赖于该单元格的所有单元格的值都需要被重新计算。被调度的任务为重新计算某个特定单元格的值。当一个单元格的值取决于另外一个单元格时,两个单元格之间则有依赖关系。每个被依赖单元格的值的计算过程都必须先于使用它的表达式执行。使用依赖图的拓扑排序来调度任务使得在每个单元格的值都仅被重新计算一次的情况下,整个工作表都能被更新。<ref name="hgt1181">{{citation |title=Handbook of Graph Theory |first1=Jonathan L. |last1=Gross |first2=Jay |last2=Yellen |first3=Ping |last3=Zhang | author3-link = Ping Zhang (graph theorist)|edition=2nd |publisher=CRC Press |year=2013 |isbn=978-1-4398-8018-0 |page=1181 |url=https://books.google.com/books?id=cntcAgAAQBAJ&pg=PA1181}}.</ref>相似的任务调度场景出现在程序源代码编译的<font color="#ff8000"> '''Makefile''' </font>,<ref name="hgt1181" />和优化计算机程序底层执行的[[指令调度]]中。<ref>{{citation |title=The Compiler Design Handbook: Optimizations and Machine Code Generation |first1=Y. N. |last1=Srikant |first2=Priti |last2=Shankar |edition=2nd |publisher=CRC Press|year=2007 |isbn=978-1-4200-4383-9 |pages=19–39 |url=https://books.google.com/books?id=1kqAv-uDEPEC&pg=SA19-PA39}}.</ref><br />
<br />
[[File:Pert chart colored.svg|thumb|一个有着五个里程碑(注有10–50)和六个任务(注有A–F)的计划评审图。ADF和BC是[[关键路径]]]]<br />
[[计划评审技术]]是一种基于有向无环图的计划排定技术,通常用于组织大型的人工项目。在计划评审技术中,每个顶点表示项目的一个 里程碑 (项目管理) Milestone (project management),每条有向边表示任务或者活动,连接着表示任务开始或结束的两个节点。每条边则被标注上预估需时。图中的[[最长路径问题|最长路径]]即为项目的[[关键路径]]。关键路径决定了项目所需的总时间,里程碑的完成时间取决于结束于本顶点的最长路径。<ref>{{citation |title=What Every Engineer Should Know About Decision Making Under Uncertainty |first=John X. |last=Wang |publisher=CRC Press |year=2002 |isbn=978-0-8247-4373-4 |page=160 |url=https://books.google.com/books?id=C3yKML0dUVIC&pg=PA160}}.</ref><br />
<br />
=== 数据处理网络 ===<br />
有向无环图可以用于表示处理数据的元素网络。在网络中,数据从一个元素顶点的入边进入,处理后从出边离开。<br />
<br />
在电子电路设计中,静态[[组合逻辑电路]]块可以被表示为由[[逻辑门]]组成的有向无环系统。每个逻辑门对输入做一次函数处理,输入和输出均为一个[[位元]]组。通常,这些电路块的输出不能够再作为输入,除非它们被存储在寄存器或者状态单元中,以保证图不出现环。<ref>{{citation|title=Timing|first=Sachin|last=Sapatnekar|publisher=Springer|year=2004|isbn=978-1-4020-7671-8|page=133|url=https://books.google.com/books?id=fL9k-VkZVr0C&pg=PA133}}.</ref><br />
<br />
<font color="#ff8000">'''数据式编程 Dataflow programming''' </font>语言描述针对<font color="#ff8000"> '''数据流 Data stream''' </font>的操作,以及操作的输出和其他操作的输入之间的关系。这类型的语言使得描绘高重复率数据处理任务的变得更加简单,因为同样的数据操作可以应用于许多数据项。数据操作可以用有向无环图来表示。这些数据操作可以被[[平行演算法|并发]]执行,从而高效利用多核心[[中央处理器|处理器]]。<ref>{{citation|title=Programming Symposium|series=Lecture Notes in Computer Science|volume=19|year=1974|pages=362–376|contribution=First version of a data flow procedure language|first=Jack B.|last=Dennis|doi=10.1007/3-540-06859-7_145|isbn=978-3-540-06859-4}}.</ref><br />
<br />
在[[编译器]]中,直线码(不含条件分支和循环的代码段)可以使用有向无环图表示。图标示出每个算术运算的输入和输出。这种表示法让编译器能执行<font color="#ff8000"> '''通用子表达式删除 Common subexpression elimination''' </font>,使得代码更高效。<ref>{{citation|title=Advanced Backend Optimization|first1=Sid|last1=Touati|first2=Benoit|last2=de Dinechin|publisher=John Wiley & Sons|year=2014|isbn=978-1-118-64894-0|page=123|url=https://books.google.com/books?id=nO2-AwAAQBAJ&pg=PA123}}.</ref><br />
<br />
=== 因果结构 ===<br />
{{main|贝叶斯网络}}<br />
<br />
用顶点表示事件,边表示[[因果关系]]的图通常是无环的。<ref>{{citation|title=Causal Learning|first1=Alison|last1=Gopnik|first2=Laura|last2=Schulz|publisher=Oxford University Press|year=2007|isbn=978-0-19-803928-0|page=4|url=http://books.google.com/books?id=35MKXlKoXIUC&pg=PA4}}.</ref>事件由时间上的先后顺序来排列,所有箭头遵循从先发生事件指向后发生事件的原则,因此也不存在环。<br />
<br />
举例来说,<font color="#ff8000">'''贝叶斯网络 Bayesian network''' </font>表示多个概率事件的关联网络。顶点表示事件,后续事件的发生可能性则可以通过其在有向无环图的前驱节点的发生概率计算出来。<ref>{{citation|title=Probabilistic Boolean Networks: The Modeling and Control of Gene Regulatory Networks|publisher=Society for Industrial and Applied Mathematics|first1=Ilya|last1=Shmulevich|first2=Edward R.|last2=Dougherty|year=2010|isbn=978-0-89871-692-4|page=58|url=http://books.google.com/books?id=RfshqEgO7KgC&pg=PA58}}.</ref>在此基础上,一个有向无环图的<font color="#ff8000"> '''端正图 Moral graph''' </font>通过以下方法而得到:将单个顶点的所有父节点之间添加一条无向边,再将所有的有向边换成无向边。<ref>{{citation |last1= Cowell |first1= Robert G. |author2-link=Philip Dawid|last2=Dawid|first2=A. Philip|author3-link=Steffen Lauritzen|last3=Lauritzen|first3=Steffen L.|author4-link=David Spiegelhalter|last4=Spiegelhalter|first4=David J.|title= Probabilistic Networks and Expert Systems |publisher= Springer |year= 1999 |isbn= 0-387-98767-3 |chapter= 3.2.1 Moralization|pages= 31–33 }}.</ref><br />
<br />
另外一种具有相似因果结构的图是<font color="#ff8000"> '''影响图 Influence diagram''' </font>。其顶点表示决策或不确定的事件,边表示两个顶点之间的因果关系。<ref>{{citation|title=The Technology Management Handbook|first=Richard C.|last=Dorf|publisher=CRC Press|year=1998|isbn=978-0-8493-8577-3|page=9-7<!-- Do not conver this hyphen into a dash! It is a section-page number, not a range of page numbers. -->|url=http://books.google.com/books?id=C2u8I0DFo4IC&pg=SA9-PA7}}.</ref>在流行病学中,这些表示因果关系的图表常常用来评估不同干预手段的效果。<ref>{{citation|title=Encyclopedia of Epidemiology, Volume 1|first=Sarah|last=Boslaugh|publisher=SAGE|year=2008|isbn=978-1-4129-2816-8|page=255|url=http://books.google.com/books?id=wObgnN3x14kC&pg=PA255}}.</ref><ref name=pearl:95>{{cite journal|last1=Pearl|first1=Judea|authorlink= Judea Pearl|title=Causal diagrams for empirical research|journal=Biometrika|date=1995|volume=82|issue=4|pages=669–709|doi=10.1093/biomet/82.4.669}}</ref><br />
<br />
=== 系谱学和版本历史 ===<br />
[[File:EgyptianPtolemies2.jpg|thumb|upright=1.5|[[托勒密王朝]]的谱系图。]]<br />
<br />
[[谱系图]]可以看作是有向无环图,顶点代表家族成员,边代表亲子关系。<ref>{{citation|journal=Algorithms for Molecular Biology|date=April 2011|volume=6|issue=10|pages=10|title=Haplotypes versus genotypes on pedigrees|first=Bonnie B.|last=Kirkpatrick|doi=10.1186/1748-7188-6-10|pmc=3102622|pmid=21504603}}.</ref>虽然谱系图也被称作为家族“树”, 但近亲结婚导致的 [[血统崩溃 Pedigree collapse]] 会违反树的性质。即一个孩子的祖先既可以从父亲向上追溯,也可以从母亲一侧。<ref>{{citation<br />
| last1 = McGuffin | first1 = M. J.<br />
| last2 = Balakrishnan | first2 = R.<br />
| contribution = Interactive visualization of genealogical graphs<br />
| contribution-url = http://profs.etsmtl.ca/mMcGuffin/research/genealogyVis/genealogyVis.pdf<br />
| doi = 10.1109/INFVIS.2005.1532124<br />
| pages = 16–23<br />
| title = IEEE Symposium on Information Visualization (INFOVIS 2005)<br />
| year = 2005| isbn = 978-0-7803-9464-3<br />
}}.</ref>图中的[[母系制度|母系血统]]和[[父系制度|父系血统]]则可以看作为树。因为没有人可以是自己的祖先,谱系图是无环的。<ref>{{citation<br />
| last1 = Bender | first1 = Michael A.<br />
| last2 = Pemmasani | first2 = Giridhar<br />
| last3 = Skiena | first3 = Steven<br />
| last4 = Sumazin | first4 = Pavel<br />
| contribution = Finding least common ancestors in directed acyclic graphs<br />
| contribution-url = http://dl.acm.org/citation.cfm?id=365411.365795<br />
| isbn = 978-0-89871-490-6<br />
| location = Philadelphia, PA, USA<br />
| pages = 845–854<br />
| publisher = Society for Industrial and Applied Mathematics<br />
| title = Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '01)<br />
| year = 2001}}.</ref><br />
<br />
基于相同的原因, 一个[[分散式版本控制]]系统的版本历史的结构也是有向无环图。在系统中,每个版本对应一个节点。边连接起有直接衍生关系的两个版本。由于分支合并的存在,这个结构并不能用树来表示。<ref>{{citation|title=Architecture and Methods for Flexible Content Management in Peer-to-Peer Systems|first=Udo|last=Bartlang|publisher=Springer|year=2010|isbn=978-3-8348-9645-2|page=59|url=https://books.google.com/books?id=vXdEAAAAQBAJ&pg=PA59}}.</ref><br />
<br />
在[[计算几何]]领域,许多随机化算法都会维护一个“历史有向无环图”,用以记录结构变动中的旧几何结构。例如,在<font color="#ff8000"> '''德劳内三角化 Delaunay triangulation''' </font>的随机增量算法中,在添加每个点时,通过用三个较小的三角形替换一个三角形,以及通过“翻转”操作将三角形对替换为另一对三角形,来改变三角剖分。在该算法的历史有向无环图中,每个在算法中构建出的三角形对应一个顶点,边则将每个三角形和替代它的两个或三个三角形连接起来。这种图结构可以高效地处理<font color="#ff8000"> '''点定位 Point location''' </font>问题,即对于一个查询点{{mvar|q}},找到它在德勞內三角剖分中的位置。在历史有向无环图中,从起点开始,不断移动到包含{{mvar|q}}的替代三角形组,最后到达的终点必定代表包含q的德劳内三角形。<ref>{{citation|title=Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures|volume=152|series=Mathematical surveys and monographs|first1=János|last1=Pach|author1-link=János Pach|first2=Micha|last2=Sharir|author2-link=Micha Sharir|publisher=American Mathematical Society|isbn=978-0-8218-7533-9|pages=93–94|url=https://books.google.com/books?id=-fguzNaYoqcC&pg=PA93}}.</ref><br />
<br />
=== 引用图 ===<br />
在<font color="#ff8000"> '''引用图 Citation graph''' </font>中, 每个顶点代表单篇著作,边代表著作之间的[[參考文獻|引用]]关系。1965年[[德瑞克·约翰·德索拉·普莱斯|普莱斯]]的文章“科学文献的网络”是使用引用图的一个经典例子。<ref>{{citation | last = Price | first = Derek J. de Solla | date = July 30, 1965 | doi = 10.1126/science.149.3683.510 | issue = 3683 | journal = [[科学 (期刊)|Science]] | pages = 510–515 | pmid = 14325149 | title = Networks of Scientific Papers | url = http://garfield.library.upenn.edu/papers/pricenetworks1965.pdf | volume = 149| bibcode = 1965Sci...149..510D }}.</ref>在引用图中,每篇论文的<font color="#ff8000"> '''引用影响(引用次数) Citation impact''' </font>为对应顶点的入度。这是[[引文分析]]中的一种重要的展示方式。另一个例子是[[裁判 (法律)|法律裁判]]中,法官通过引用过往案例中的判决来支持他们的结论。引用图亦可以用来描绘[[专利]],因为专利必须要提及[[现有技术]],即已经公开的并且和本专利有关的先前专利。<br />
<br />
相较于[[网络科学]]中对一般图的研究,有向无环图的独特性质可以被用来作深层次分析。例如,传递规约可以呈现引用在不同应用领域的分布情况,这突出了不同领域中不同的引用网构造机制。<ref>{{citation | last1 = Clough | first1 = James R. | last2 = Gollings | first2 = Jamie | last3 = Loach | first3 = Tamar V. | last4 = Evans | first4 = Tim S. | doi = 10.1093/comnet/cnu039 | issue = 2 | journal = Journal of Complex Networks | pages = 189–203 | title = Transitive reduction of citation networks | volume = 3| arxiv = 1310.8224 | year = 2015 }}.</ref>引用图的衍生概念还有<font color="#ff8000"> '''主干道路分析 Main path analysis''' </font>,即对引用图中最显著的一条路径的分析。<br />
<br />
=== 数据压缩 ===<br />
[[Image:Trie-vs-minimal-acyclic-fa.svg|thumb|right|250px|分别用trie(左)和有向无环词图(右)存放英文单词“tap”,“taps”,“top”和“tops”。<tt>EOW</tt>表示单词结束。]]<br />
有向无环图也可以用于对一系列序列的[[数据压缩|压缩]]中。在这里,有向无环图中的路径代表这些序列。当多个序列有共同的子序列时,子序列可以被表示为这些序列对应路径的公共边。比起直接列出所有序列,这种方法占用更少空间。例如,<font color="#ff8000"> '''无环确定有限状态自动机 Deterministic acyclic finite state automaton''' </font>为仅含单个源(入度为0的顶点)的有向无环图,其每条边附有一个或多个字符。每条其源到汇(出度为0的节点)的路径均代表一个[[字符串]],字符串可以是英文单词。<ref>{{citation | first1=Maxime | last1=Crochemore | first2=Renaud | last2=Vérin | contribution=Direct construction of compact directed acyclic word graphs | series=Lecture Notes in Computer Science | publisher=Springer | title=Combinatorial Pattern Matching | volume=1264 | year=1997 | pages=116–129 | doi=10.1007/3-540-63220-4_55 | isbn=978-3-540-63220-7 | citeseerx=10.1.1.53.6273 }}.</ref>与其结构不同但功能相似的树称为[[trie]]。相比于trie,有向无环词图允许多条边指向同一个顶点,使得具有相同后缀的一些词的词头可以被相同的顶点所表示,因而更省空间。<ref>{{citation|title=Applied Combinatorics on Words|volume=105|series=Encyclopedia of Mathematics and its Applications|first=M.|last=Lothaire|authorlink=M. Lothaire|publisher=Cambridge University Press|year=2005|isbn=9780521848022|page=18|url=https://books.google.com/books?id=fpLUNkj1T1EC&pg=PA18}}.</ref><br />
<br />
[[二元决策图]]是基于有向无环图的一种数据结构,用于表示[[布尔函数]]<ref>{{citation|first=C. Y.|last=Lee|title=Representation of switching circuits by binary-decision programs|journal=Bell System Technical Journal|volume=38|issue=4|pages=985–999|year=1959|doi=10.1002/j.1538-7305.1959.tb01585.x}}.</ref><ref>{{citation|first=Sheldon B.|last=Akers|doi=10.1109/TC.1978.1675141|title=Binary decision diagrams|journal=IEEE Transactions on Computers|volume=C-27|issue=6|pages=509–516|year=1978}}.</ref>。在二元决策图中,每个非汇节点对应一个布尔变量,每个汇和边则表示0或1。要找到一个[[解释 (逻辑)|解释]]的真值,只要从唯一的源顶点出发,沿着该顶点代表的布尔变量的实际真值所对应的出边一直前进,到达的汇则为其真值。如同有向无环词图可以被看作是trie的一种压缩形式一样,二元决策图可以被看作是<font color="#ff8000"> '''决策树''' </font>的压缩形式。它通过将导向相同结果的边重新汇合到一个顶点来节省空间。<ref>{{citation<br />
| last1 = Friedman | first1 = S. J.<br />
| last2 = Supowit | first2 = K. J.<br />
| contribution = Finding the optimal variable ordering for binary decision diagrams<br />
| doi = 10.1145/37888.37941<br />
| isbn = 978-0-8186-0781-3<br />
| location = New York, NY, USA<br />
| pages = 348–356<br />
| publisher = ACM<br />
| title = Proc. 24th ACM/IEEE Design Automation Conference (DAC '87)<br />
| year = 1987}}.</ref><br />
<br />
==参考文献==<br />
{{Reflist|30em}}<br />
{{圖論}}</div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%BF%A0%E5%AE%9E%E6%80%A7%E5%81%87%E8%AE%BE&diff=22925
忠实性假设
2021-06-03T13:23:23Z
<p>Kuang:/* 违反忠实性 */</p>
<hr />
<div>==因果忠实性==<br />
<br />
===定义===<br />
<br />
假设某个总体是忠实的,那就是假设其中发生的任何独立性都不是来自不可思议的巧合,而是来自结构。<ref name="introduction">Scheines R. (1997) [https://pattern.swarma.org/paper?id=72ab907c-c3b0-11eb-a051-0242ac170007 An introduction to causal inference].</ref><br />
(总体:统计学概念,指包含所研究的全部个体(数据)的集合)<br />
<br />
考虑一个多变量联合概率分布<math>P_{X}</math>和一个有向无环图DAG <math>\mathcal{G}</math>.<br />
<br />
定义:联合概率分布 <math>P_{X}</math> 对于给定的 DAG <math>\mathcal{G}</math> 满足因果忠实性,如果<ref name="Elements">Peters Jonas,Janzing Dominik,Schlkopf Bernhard (2017) [https://pattern.swarma.org/paper?id=5c93b918-c3ba-11eb-8fd5-0242ac170007 Elements of Causal Inference: Foundations and Learning Algorithms].</ref>:<br />
<br />
<math>A \perp\!\!\!\perp B \mid C \Rightarrow A \perp\!\!\!\perp_{\mathcal{G}} B \mid C</math><br />
<br />
对于所有不相交的顶点(变量)集 A,B,C 均成立。<br />
<br />
这个定义暗示了一个与全局马尔可夫条件相反的结论:<br />
<br />
<math>A \perp\!\!\!\perp_{\mathcal{G}} B \mid C \Rightarrow A \perp\!\!\!\perp B \mid C</math><br />
<br />
乍一看,忠实性并不是很直观。 我们现在给出一个马尔可夫分布的例子,但对于给定的 DAG <math>\mathcal{G_{1}}</math> 不忠实。 这是通过使两条路径相互抵消并创建图结构未暗示的独立性来实现的。<br />
<br />
====违背忠实性的例子<ref name="Elements"/>====<br />
<br />
考虑下图:<br />
<br />
<gallery><br />
Faithful-3.png<br />
</gallery><br />
<br />
我们首先看一个线性高斯 <math>SCM</math> 对应于左图<math>\mathcal{G_{1}}</math>。<br />
<br />
<gallery><br />
Faithful-4.png<br />
</gallery><br />
<br />
正态分布的噪声变量<math>N_{X} ∼ \mathcal{N} (0,\sigma^2_X )</math>、<math>N_{Y} ∼ \mathcal{N} (0,\sigma^2_Y )</math> 和 <math>N_{Z} ∼ \mathcal{N} (0,\sigma^2_Z )</math> 共同独立。 这是带有图<math>\mathcal{G_{1}}</math> 的线性高斯 <math>SCM</math> 的示例。 现在,如果<br />
<br />
<math>a \cdot b + c = 0</math> (1)<br />
<br />
由于我们获得 <math>X \perp\!\!\!\perp Z</math>,因此分布不忠实于<math>\mathcal{G_{1}}</math>,这不是图结构所暗示的。读者可以轻松验证存在带有DAG <math>\mathcal{G_{2}}</math>的SCM引出相同分布。<br />
<br />
为了在前面的例子中获得额外的独立性,我们必须“调整”系数,使得两条路径在(1)中相互抵消。 Spirtes等人[2000, Theorem 3.2]对于线性模型表明,如果我们假设系数是从正密度中随机抽取的,那么这种情况发生的概率为零。<br />
<br />
上例中的分布对于<math>\mathcal{G_{2}}</math>是忠实的,但对于<math>\mathcal{G_{1}}</math>则不是。尽管如此,对于这两个模型,如果没有任何参数归零,则满足因果最小性。换句话说,该分布对于<math>\mathcal{G_{1}}</math> 或<math>\mathcal{G_{2}}</math>的任何真子图都不是马尔可夫的,因为删除任何边将对应于在分布中不成立的新(条件)独立性; 注意<math>\mathcal{G_{2}}</math>不是<math>\mathcal{G_{1}}</math>的真子图。 然而,它是<math>\mathcal{H}</math>的真子图,因此,该分布不满足关于<math>\mathcal{H}</math>的因果最小性。通常,因果最小性弱于忠实性。<br />
<br />
通过假定因果图满足因果马尔可夫性,我们假设此因果图产生的所有总体都具有通过对其应用d分离而获得的独立性关系。 但是,并不能因此而得出结论,这些总体恰好具有这些独立性关系并且没有其他独立性关系。<ref name="introduction"/><br />
<br />
===示例<ref name="introduction"/>===<br />
<br />
<gallery><br />
因果忠实性假设图例1.png|运动,吸烟和健康之间的关系<br />
</gallery><br />
<br />
图1中描述了运动,吸烟和健康之间的关系,其中+和-分别表示正向和抑制性关系。<br />
<br />
在这种结构可能产生的某些分布中,可能存在巧合,如果吸烟对健康有直接的负面影响,但是吸烟对运动有积极的影响(可能看起来很奇怪),而锻炼对健康有积极的影响,那么吸烟可以直接抑制健康并间接改善健康。<br />
<br />
如果这两种效应恰好完全平衡并因此抵消,那么吸烟与健康之间可能根本就没有关联。<br />
<br />
在这种情况下,我们说总体分布不忠实于产生它的因果图。<br />
<noinclude><br />
==参考文献==<br />
</noinclude></div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%BF%A0%E5%AE%9E%E6%80%A7%E5%81%87%E8%AE%BE&diff=22921
忠实性假设
2021-06-03T13:20:03Z
<p>Kuang:/* 定义 */</p>
<hr />
<div>==因果忠实性==<br />
<br />
===定义===<br />
<br />
假设某个总体是忠实的,那就是假设其中发生的任何独立性都不是来自不可思议的巧合,而是来自结构。<ref name="introduction">Scheines R. (1997) [https://pattern.swarma.org/paper?id=72ab907c-c3b0-11eb-a051-0242ac170007 An introduction to causal inference].</ref><br />
(总体:统计学概念,指包含所研究的全部个体(数据)的集合)<br />
<br />
考虑一个多变量联合概率分布<math>P_{X}</math>和一个有向无环图DAG <math>\mathcal{G}</math>.<br />
<br />
定义:联合概率分布 <math>P_{X}</math> 对于给定的 DAG <math>\mathcal{G}</math> 满足因果忠实性,如果<ref name="Elements">Peters Jonas,Janzing Dominik,Schlkopf Bernhard (2017) [https://pattern.swarma.org/paper?id=5c93b918-c3ba-11eb-8fd5-0242ac170007 Elements of Causal Inference: Foundations and Learning Algorithms].</ref>:<br />
<br />
<math>A \perp\!\!\!\perp B \mid C \Rightarrow A \perp\!\!\!\perp_{\mathcal{G}} B \mid C</math><br />
<br />
对于所有不相交的顶点(变量)集 A,B,C 均成立。<br />
<br />
这个定义暗示了一个与全局马尔可夫条件相反的结论:<br />
<br />
<math>A \perp\!\!\!\perp_{\mathcal{G}} B \mid C \Rightarrow A \perp\!\!\!\perp B \mid C</math><br />
<br />
乍一看,忠实性并不是很直观。 我们现在给出一个马尔可夫分布的例子,但对于给定的 DAG <math>\mathcal{G_{1}}</math> 不忠实。 这是通过使两条路径相互抵消并创建图结构未暗示的独立性来实现的。<br />
<br />
====违反忠实性<ref name="Elements"/>====<br />
<br />
考虑下图:<br />
<br />
<gallery><br />
Faithful-3.png<br />
</gallery><br />
<br />
我们首先看一个线性高斯 <math>SCM</math> 对应于左图<math>\mathcal{G_{1}}</math>。<br />
<br />
<gallery><br />
Faithful-4.png<br />
</gallery><br />
<br />
正态分布的噪声变量<math>N_{X} ∼ \mathcal{N} (0,\sigma^2_X )</math>、<math>N_{Y} ∼ \mathcal{N} (0,\sigma^2_Y )</math> 和 <math>N_{Z} ∼ \mathcal{N} (0,\sigma^2_Z )</math> 共同独立。 这是带有图<math>\mathcal{G_{1}}</math> 的线性高斯 <math>SCM</math> 的示例。 现在,如果<br />
<br />
<math>a \cdot b + c = 0</math> (1)<br />
<br />
由于我们获得 <math>X \perp\!\!\!\perp Z</math>,因此分布不忠实于<math>\mathcal{G_{1}}</math>,这不是图结构所暗示的。读者可以轻松验证存在带有DAG <math>\mathcal{G_{2}}</math>的SCM引出相同分布。<br />
<br />
为了在前面的例子中获得额外的独立性,我们必须“调整”系数,使得两条路径在(1)中相互抵消。 Spirtes等人[2000, Theorem 3.2]对于线性模型表明,如果我们假设系数是从正密度中随机抽取的,那么这种情况发生的概率为零。<br />
<br />
上例中的分布对于<math>\mathcal{G_{2}}</math>是忠实的,但对于<math>\mathcal{G_{1}}</math>则不是。尽管如此,对于这两个模型,如果没有任何参数归零,则满足因果最小性。换句话说,该分布对于<math>\mathcal{G_{1}}</math> 或<math>\mathcal{G_{2}}</math>的任何真子图都不是马尔可夫的,因为删除任何边将对应于在分布中不成立的新(条件)独立性; 注意<math>\mathcal{G_{2}}</math>不是<math>\mathcal{G_{1}}</math>的真子图。 然而,它是<math>\mathcal{H}</math>的真子图,因此,该分布不满足关于<math>\mathcal{H}</math>的因果最小性。通常,因果最小性弱于忠实性。<br />
<br />
通过假定因果图满足因果马尔可夫性,我们假设此因果图产生的所有总体都具有通过对其应用d分离而获得的独立性关系。 但是,并不能因此而得出结论,这些总体恰好具有这些独立性关系并且没有其他独立性关系。<ref name="introduction"/><br />
<br />
===示例<ref name="introduction"/>===<br />
<br />
<gallery><br />
因果忠实性假设图例1.png|运动,吸烟和健康之间的关系<br />
</gallery><br />
<br />
图1中描述了运动,吸烟和健康之间的关系,其中+和-分别表示正向和抑制性关系。<br />
<br />
在这种结构可能产生的某些分布中,可能存在巧合,如果吸烟对健康有直接的负面影响,但是吸烟对运动有积极的影响(可能看起来很奇怪),而锻炼对健康有积极的影响,那么吸烟可以直接抑制健康并间接改善健康。<br />
<br />
如果这两种效应恰好完全平衡并因此抵消,那么吸烟与健康之间可能根本就没有关联。<br />
<br />
在这种情况下,我们说总体分布不忠实于产生它的因果图。<br />
<noinclude><br />
==参考文献==<br />
</noinclude></div>
Kuang
https://wiki.swarma.org/index.php?title=%E5%BF%A0%E5%AE%9E%E6%80%A7%E5%81%87%E8%AE%BE&diff=22914
忠实性假设
2021-06-03T13:08:55Z
<p>Kuang:/* 定义 */</p>
<hr />
<div>==因果忠实性==<br />
<br />
===定义===<br />
<br />
假设某个总体是忠实的,那就是假设其中发生的任何独立性都不是来自不可思议的巧合,而是来自结构。<ref name="introduction">Scheines R. (1997) [https://pattern.swarma.org/paper?id=72ab907c-c3b0-11eb-a051-0242ac170007 An introduction to causal inference].</ref><br />
(总体:统计学概念,指包含所研究的全部个体(数据)的集合)<br />
<br />
考虑一个多变量联合概率分布<math>P_{X}</math>和一个有向无环图DAG <math>\mathcal{G}</math>.<br />
<br />
定义:联合概率分布<math>P_{X}</math>对于DAG <math>\mathcal{G}</math>满足因果忠实性,如果<ref name="Elements">Peters Jonas,Janzing Dominik,Schlkopf Bernhard (2017) [https://pattern.swarma.org/paper?id=5c93b918-c3ba-11eb-8fd5-0242ac170007 Elements of Causal Inference: Foundations and Learning Algorithms].</ref>:<br />
<br />
<math>A \perp\!\!\!\perp B \mid C \Rightarrow A \perp\!\!\!\perp_{\mathcal{G}} B \mid C</math><br />
<br />
对于所有不相交的顶点(变量)集 A,B,C 均成立。<br />
<br />
这个定义暗示了一个与全局马尔可夫条件相反的结论:<br />
<br />
<math>A \perp\!\!\!\perp_{\mathcal{G}} B \mid C \Rightarrow A \perp\!\!\!\perp B \mid C</math><br />
<br />
乍一看,忠实性并不是很直观。 我们现在给出一个马尔可夫分布的例子,但对于给定的 DAG <math>\mathcal{G_{1}}</math> 不忠实。 这是通过使两条路径相互抵消并创建图结构未暗示的独立性来实现的。<br />
<br />
====违反忠实性<ref name="Elements"/>====<br />
<br />
考虑下图:<br />
<br />
<gallery><br />
Faithful-3.png<br />
</gallery><br />
<br />
我们首先看一个线性高斯 <math>SCM</math> 对应于左图<math>\mathcal{G_{1}}</math>。<br />
<br />
<gallery><br />
Faithful-4.png<br />
</gallery><br />
<br />
正态分布的噪声变量<math>N_{X} ∼ \mathcal{N} (0,\sigma^2_X )</math>、<math>N_{Y} ∼ \mathcal{N} (0,\sigma^2_Y )</math> 和 <math>N_{Z} ∼ \mathcal{N} (0,\sigma^2_Z )</math> 共同独立。 这是带有图<math>\mathcal{G_{1}}</math> 的线性高斯 <math>SCM</math> 的示例。 现在,如果<br />
<br />
<math>a \cdot b + c = 0</math> (1)<br />
<br />
由于我们获得 <math>X \perp\!\!\!\perp Z</math>,因此分布不忠实于<math>\mathcal{G_{1}}</math>,这不是图结构所暗示的。读者可以轻松验证存在带有DAG <math>\mathcal{G_{2}}</math>的SCM引出相同分布。<br />
<br />
为了在前面的例子中获得额外的独立性,我们必须“调整”系数,使得两条路径在(1)中相互抵消。 Spirtes等人[2000, Theorem 3.2]对于线性模型表明,如果我们假设系数是从正密度中随机抽取的,那么这种情况发生的概率为零。<br />
<br />
上例中的分布对于<math>\mathcal{G_{2}}</math>是忠实的,但对于<math>\mathcal{G_{1}}</math>则不是。尽管如此,对于这两个模型,如果没有任何参数归零,则满足因果最小性。换句话说,该分布对于<math>\mathcal{G_{1}}</math> 或<math>\mathcal{G_{2}}</math>的任何真子图都不是马尔可夫的,因为删除任何边将对应于在分布中不成立的新(条件)独立性; 注意<math>\mathcal{G_{2}}</math>不是<math>\mathcal{G_{1}}</math>的真子图。 然而,它是<math>\mathcal{H}</math>的真子图,因此,该分布不满足关于<math>\mathcal{H}</math>的因果最小性。通常,因果最小性弱于忠实性。<br />
<br />
通过假定因果图满足因果马尔可夫性,我们假设此因果图产生的所有总体都具有通过对其应用d分离而获得的独立性关系。 但是,并不能因此而得出结论,这些总体恰好具有这些独立性关系并且没有其他独立性关系。<ref name="introduction"/><br />
<br />
===示例<ref name="introduction"/>===<br />
<br />
<gallery><br />
因果忠实性假设图例1.png|运动,吸烟和健康之间的关系<br />
</gallery><br />
<br />
图1中描述了运动,吸烟和健康之间的关系,其中+和-分别表示正向和抑制性关系。<br />
<br />
在这种结构可能产生的某些分布中,可能存在巧合,如果吸烟对健康有直接的负面影响,但是吸烟对运动有积极的影响(可能看起来很奇怪),而锻炼对健康有积极的影响,那么吸烟可以直接抑制健康并间接改善健康。<br />
<br />
如果这两种效应恰好完全平衡并因此抵消,那么吸烟与健康之间可能根本就没有关联。<br />
<br />
在这种情况下,我们说总体分布不忠实于产生它的因果图。<br />
<noinclude><br />
==参考文献==<br />
</noinclude></div>
Kuang
https://wiki.swarma.org/index.php?title=%E7%94%A8%E6%88%B7%E8%AE%A8%E8%AE%BA:Dario_Zhang&diff=22789
用户讨论:Dario Zhang
2021-06-01T01:54:38Z
<p>Kuang:这里没有给出数学定义,可以按照elements of causal inference一书中的定义给出, 其中一些名词如d-sep 可链接到其他词条</p>
<hr />
<div>这里没有给出数学定义,可以按照elements of causal inference一书中的定义给出, 其中一些名词如d-sep 可链接到其他词条</div>
Kuang