论文部分内容阅读
摘要：有向无环图（DAG）作为一种表示多个变量间关系的方法，因其简单直观，在社会各个领域有着广泛应用。为了表示复杂数据所蕴含的因果关系，常常需要在DAG中引入一些不可观测的潜变量和选择变量。如何基于观测数据得到蕴含不可观测潜变量和选择变量的DAG，Spirtes， Meek和 Richardson提出了FCI算法。FCI算法是在PC算法上的一种改进算法，改进的目的是为了避免由于潜变量以及选择变量的存在而出现的因果推断的偏差和错误。本文简要的介绍了FCI算法，并结合FCI算法对大学生数学类课程的数据进行了分析，并给出了相应的结论。
关键词：有向无环图；潜变量；FCI算法；因果关系
中图分类号：G642 文献识别码：A 文章编号：1001-828X（2016）018-000-02
一、引言
随着大数据时代的来临，人们生产、生活各个领域都存在着大量的复杂数据，这些数据通常包含许多变量，而且变量间的影响机制复杂，如何描述变量间的关系是一个重要的问题。有向无环图是一种基于概率推理的图形化网络，为处理变量间的因果关系提供了新的途径[9]。有向无环图因其强大的不确定性信息处理能力，逐渐成为处理不确定信息的主流，进而成功地应用在智能化系统、学习预测、医疗诊断等多个领域中[8]。基于有向无环图的重要性和广泛的应用性，如何根据实际数据学习有向无环图是科学研究中的一个重要问题。Spirtes， Glymour和Scheines [7]在1991年提出了一种学习贝叶斯网的算法--PC算法，PC算法是用来探索贝叶斯网中多个变量之间的条件独立关系和因果关系的一种方法，结果简单易懂，便于交流，但是它的假设比较强，它假设研究的问题中所有变量都是可观测的。但在社会学、教育学、管理学等研究领域，可能存在一些不可观测的潜变量和选择变量，潜变量和选择变量的出现会使实际上两个无关的变量表现出相关性[6]。为了学习含有潜变量和选择变量的贝叶斯网，Spirtes， Meek和 Richardson[6]在1999年提出了PC算法的改进算法--FCI算法，FCI算法通过验证初始骨架中邻接的两个顶点在给定Possible-D-SEP集[2]下的条件独立信息来解决潜变量和选择变量带来的影响，因此FCI算法比PC算法更具有一般性。
本文首先介绍了图的相关概念以及FCI算法的基本步骤，然后利用FCI算法对大学生数学类课程进行了因果关系的分析，探究各课程之间的影响，为大学数学类课程的设置以及课程教学提供一些建议和参考。
二、图的概念及介绍
由于在FCI算法中涉及到了一些图的知识，所以简单介绍一下图中的相关知识。
在图论中，图是由顶点集和边集构成的。若是有序的，它称为有向边，否则为无向边。一个图中如果只包含有向边，则称为有向图，如果只包含无向边，则称为无向图。把图中的有向边全变为无向边得到的无向图为其骨架。
如果两顶点之间有边，则称这两顶点是邻接的，如果图中所有顶点都是邻接的，那么就称这个图为完全图。用来表示图中与点邻接的点集，如果有，则成是的父顶点，是的子顶点。如果有，则称是的配偶顶点。我们称一系列两两有边的点为一条路，若路中边的方向一致，则称这条路为有向路。当一条路首尾相连，这样的路就形成环。若环中的边方向一致，则形成有向环。如果一个从到的有向环中包含，则称为几乎有向环。若从到之间存在有向路，则称是的祖先顶点，是的后代顶点。我们用an（G，Xi）和de（G，Xi）来表示点的祖先顶点集和后代顶点集。
在有向图中，如果不含有有向环，则称这个图为有向无环图（DAG）。如果一个混合图满足（i）不包含有向环（ii）不包含几乎有向环（iii）对于图中的任意无向边，和没有父顶点和配偶顶点，则称这个图为祖先图。DAG就是一个祖先图。若一个祖先图满足图中任意两个不邻接的顶点之间没有诱导路径，则称为极大祖先图（MAG）。极大祖先图的马尔科夫等价类称为部分祖先图（PAG）。
如果三个顶点中，与是邻接的，与是邻接的，但是和不是邻接的，那么这样的三个顶点被称为开放三元组。在一条路中的一个非端点，如果它的前后两条边的箭头均指向它，则称它为一个汇连顶点。如果在一个开放三元组中，是一个汇连顶点，那么称这个开放三元组为--结构。
d-分离准则：若G是一个DAG，i，j为不在Z中两个顶点，考虑i，j两个顶点之间的路p如果满足下列条件之一，则称路p被顶点集Zd-分离。
（i）p中含有顺连结构（），或含有分连结构（）
（ii）p中含有匯连结构满足点m以及其后代都不在Z中。
若对于集合I，J，Z，若连接I中任一点和J中任一点的路都被Zd-分离，则称I，J被Zd-分离。
三、FCI算法
如果我们想考虑以下的问题：假设顶点集的分布忠实于一个未知的DAG（表示可观测变量之集，表示潜变量之集，表示选择变量之集）。已知中所有变量和在给定（）下的条件独立关系，我们想推断真实DAG中变量间的因果关系，FCI算法正是推断含有潜变量和选择变量情况下可观测变量间因果关系的方法。
FCI算法是在PC算法的基础上对存在边的两个顶点进行了条件独立检验。因为FCI算法的输出图为PAG，判断PAG中两个节点是否邻接的依据在于：如果不是的祖先，并且在给定（）的条件下，和是条件独立的，那么在给定的条件下（是或的子集），和是条件独立的。于是，要判断两个节点之间是否有边，只需验证对于是否成立。由于根据观测到的条件独立信息不能找到，所以转而寻找它的超集（）。这样就解决了潜变量带来的问题。
下面具体介绍一下FCI算法的步骤。
第一步，构造一个非定向边构成的完全图，对于顶点和，在给定的邻接子集条件下，对两个顶点做条件独立检验，如果条件独立关系成立，则移除和之间的边，并且把相应的邻接子集保存到分离集和中。第一步得出的骨架是最终骨架的超集。 第二步，对于开放三元组，若不在和中，则把此三元组定向成--结构。
第三步，对于中所有顶点，找出它的。然后对于所有的邻接顶点，检验是否存在，。若存在则移除两顶点之间的边，并把相应的邻接子集保存到分离集和中。这样就破坏了图的骨架，需要重新定向--结构。所以最后把所有的边重新改为非定向边。
第四步，重复第二步，重新定向--结构。
第五步，利用ZHANG，J.（2008）中的定向准则，尽可能多的给边定向。
下面给出FCI算法的缩略图。
表3.1
FCI算法
已知：所有变量X在给定S条件下的条件独立信息
1：利用[5]中算法4.1找到初始骨架C，分离集（sepset）和开放三元组（M）；
2：利用[5]中算法4.2确定v--结构（更新C）；
3：利用[5]中算法4.3找到最终骨架（更新C和sepset）；
4：利用[5]中算法4.2确定v--结构（更新C）；
5：利用[4]中的规则（R1）--（R10）尽可能的给更多的边定向（更新C）；
6：返回C，sepset。
四、实例分析
本文数据来自于某大学00级学生在校期间所学的15门数学类课程的成绩。旨在寻找数学类课程间的因果关系。选取的课程以及代码如表4.1所示，
利用R软件的pcalg包执行FCI算法得到的结果如图4.1所示，
由图4.1可以看出，课程1（空间解析几何）和课程2（数学分析1）之间的关系并不确定，可能是存在不可观测的潜变量影响，使它们表现出一定的相关性，就这两门课程的知识体系来说，并没有直接的因果关系。课程2（数学分析1）有可能影响了课程4（数学分析2），因为数学分析1中收敛和导数相关知识是数学分析2的基础，扎实的基础功底是后续学习所必需的。课程4（数学分析2）影响了课程3（高等代数），由知识结构可以看出，数学分析2中的知识是高等代数的基础和工具，多元函数的微分积分以及级数都可以帮助学习高等代数。课程4（数学分析2）和课程11（离散数学）之间的双向边表示它们之间有不可观测的潜变量影响，没有什么直接的因果关系，同理，课程11（离散数学）和课程14（最优化方法）之间关系，也是有潜变量影响。课程13（数值分析1）有可能影响课程14（最优化方法），数值分析1中的理论方法是最优化方法中的工具。所以可能会对学习最优化方法有帮助。
参考文献：
[1]Colombo， D.， Maathuis， M. H.， Kalisch， M. and Richardson， T. S.Learning high-dimensional directed acyclic graphs with latent and selection variables[J].The Annals of Statistics，2012，（01）：298-299.
[2]SPIRTES， P.， GLYMOUR， C. and SCHEINES， R. Causation， Prediction， and Search，2nd ed[M].New York：Springer Publishers，2000：188.
[3]KALISCH， M.， MCHLER， M.， COLOMBO， D.， MAATHUIS， M. H. and BHLMANN， P.Causal inference using graphical models with the R package pcalg[J].Journal of Statistical Software，2012，（02）：13-14.
[4]ZHANG， J. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias[J]. Artificial Intelligence，2008，（16-17）：1879-1881.
[5]COLOMBO， D.， MAATHUIS， M. H.， KALISCH， M. and RICHARDSON， T. S. Supplement to “Learning high-dimensional directed acyclic graphs with latent and selectionvariables.”[J].The Annals of Statistics，2012，（01）：16-17.
[6]Spirtes，P.，Glymour，C.，Scheines，R.Causation， Prediction， and Search[M].New York：Springer Publishers，1993：181.
[7]Spirtes， P.， Glymour， C.， and Scheines， R. An algorithm for fast recovery of sparse causal graphs[J]. Social Science Computer Review，1991，（01）：68.
[8]Pearl J.Probabilistic Reasoning in Intelligent Systems：Networks of Plausible Inference[M].San Mateo，CA：Morgan Kaufman Publishers，1988：116.
[9]王理冬，汪光陽，程泽凯，朱孝宇，贝叶斯网络的发展与展望[J].安徽工业大学学报，2006（02）：195-196.
[10]詹原瑞，谢秋平，李雪.贝叶斯网络在因果图中的应用[J].管理工程学报， 2003（02）：118.
作者简介：王福友（1992-），男，汉族，河北石家庄人，长春工业大学基础科学学院2015级统计学专业在读硕士研究生，研究方向：图模型。
张冬阳（1992-），男，汉族，吉林长春人，长春工业大学基础科学学院2015级统计学专业在读硕士研究生，研究方向：因果推断。
赵 波（1992-），男，汉族，甘肃天水人，长春工业大学基础科学学院2015级统计学专业在读硕士研究生，研究方向：生存分析。
关键词：有向无环图；潜变量；FCI算法；因果关系
中图分类号：G642 文献识别码：A 文章编号：1001-828X（2016）018-000-02
一、引言
随着大数据时代的来临，人们生产、生活各个领域都存在着大量的复杂数据，这些数据通常包含许多变量，而且变量间的影响机制复杂，如何描述变量间的关系是一个重要的问题。有向无环图是一种基于概率推理的图形化网络，为处理变量间的因果关系提供了新的途径[9]。有向无环图因其强大的不确定性信息处理能力，逐渐成为处理不确定信息的主流，进而成功地应用在智能化系统、学习预测、医疗诊断等多个领域中[8]。基于有向无环图的重要性和广泛的应用性，如何根据实际数据学习有向无环图是科学研究中的一个重要问题。Spirtes， Glymour和Scheines [7]在1991年提出了一种学习贝叶斯网的算法--PC算法，PC算法是用来探索贝叶斯网中多个变量之间的条件独立关系和因果关系的一种方法，结果简单易懂，便于交流，但是它的假设比较强，它假设研究的问题中所有变量都是可观测的。但在社会学、教育学、管理学等研究领域，可能存在一些不可观测的潜变量和选择变量，潜变量和选择变量的出现会使实际上两个无关的变量表现出相关性[6]。为了学习含有潜变量和选择变量的贝叶斯网，Spirtes， Meek和 Richardson[6]在1999年提出了PC算法的改进算法--FCI算法，FCI算法通过验证初始骨架中邻接的两个顶点在给定Possible-D-SEP集[2]下的条件独立信息来解决潜变量和选择变量带来的影响，因此FCI算法比PC算法更具有一般性。
本文首先介绍了图的相关概念以及FCI算法的基本步骤，然后利用FCI算法对大学生数学类课程进行了因果关系的分析，探究各课程之间的影响，为大学数学类课程的设置以及课程教学提供一些建议和参考。
二、图的概念及介绍
由于在FCI算法中涉及到了一些图的知识，所以简单介绍一下图中的相关知识。
在图论中，图是由顶点集和边集构成的。若是有序的，它称为有向边，否则为无向边。一个图中如果只包含有向边，则称为有向图，如果只包含无向边，则称为无向图。把图中的有向边全变为无向边得到的无向图为其骨架。
如果两顶点之间有边，则称这两顶点是邻接的，如果图中所有顶点都是邻接的，那么就称这个图为完全图。用来表示图中与点邻接的点集，如果有，则成是的父顶点，是的子顶点。如果有，则称是的配偶顶点。我们称一系列两两有边的点为一条路，若路中边的方向一致，则称这条路为有向路。当一条路首尾相连，这样的路就形成环。若环中的边方向一致，则形成有向环。如果一个从到的有向环中包含，则称为几乎有向环。若从到之间存在有向路，则称是的祖先顶点，是的后代顶点。我们用an（G，Xi）和de（G，Xi）来表示点的祖先顶点集和后代顶点集。
在有向图中，如果不含有有向环，则称这个图为有向无环图（DAG）。如果一个混合图满足（i）不包含有向环（ii）不包含几乎有向环（iii）对于图中的任意无向边，和没有父顶点和配偶顶点，则称这个图为祖先图。DAG就是一个祖先图。若一个祖先图满足图中任意两个不邻接的顶点之间没有诱导路径，则称为极大祖先图（MAG）。极大祖先图的马尔科夫等价类称为部分祖先图（PAG）。
如果三个顶点中，与是邻接的，与是邻接的，但是和不是邻接的，那么这样的三个顶点被称为开放三元组。在一条路中的一个非端点，如果它的前后两条边的箭头均指向它，则称它为一个汇连顶点。如果在一个开放三元组中，是一个汇连顶点，那么称这个开放三元组为--结构。
d-分离准则：若G是一个DAG，i，j为不在Z中两个顶点，考虑i，j两个顶点之间的路p如果满足下列条件之一，则称路p被顶点集Zd-分离。
（i）p中含有顺连结构（），或含有分连结构（）
（ii）p中含有匯连结构满足点m以及其后代都不在Z中。
若对于集合I，J，Z，若连接I中任一点和J中任一点的路都被Zd-分离，则称I，J被Zd-分离。
三、FCI算法
如果我们想考虑以下的问题：假设顶点集的分布忠实于一个未知的DAG（表示可观测变量之集，表示潜变量之集，表示选择变量之集）。已知中所有变量和在给定（）下的条件独立关系，我们想推断真实DAG中变量间的因果关系，FCI算法正是推断含有潜变量和选择变量情况下可观测变量间因果关系的方法。
FCI算法是在PC算法的基础上对存在边的两个顶点进行了条件独立检验。因为FCI算法的输出图为PAG，判断PAG中两个节点是否邻接的依据在于：如果不是的祖先，并且在给定（）的条件下，和是条件独立的，那么在给定的条件下（是或的子集），和是条件独立的。于是，要判断两个节点之间是否有边，只需验证对于是否成立。由于根据观测到的条件独立信息不能找到，所以转而寻找它的超集（）。这样就解决了潜变量带来的问题。
下面具体介绍一下FCI算法的步骤。
第一步，构造一个非定向边构成的完全图，对于顶点和，在给定的邻接子集条件下，对两个顶点做条件独立检验，如果条件独立关系成立，则移除和之间的边，并且把相应的邻接子集保存到分离集和中。第一步得出的骨架是最终骨架的超集。 第二步，对于开放三元组，若不在和中，则把此三元组定向成--结构。
第三步，对于中所有顶点，找出它的。然后对于所有的邻接顶点，检验是否存在，。若存在则移除两顶点之间的边，并把相应的邻接子集保存到分离集和中。这样就破坏了图的骨架，需要重新定向--结构。所以最后把所有的边重新改为非定向边。
第四步，重复第二步，重新定向--结构。
第五步，利用ZHANG，J.（2008）中的定向准则，尽可能多的给边定向。
下面给出FCI算法的缩略图。
表3.1
FCI算法
已知：所有变量X在给定S条件下的条件独立信息
1：利用[5]中算法4.1找到初始骨架C，分离集（sepset）和开放三元组（M）；
2：利用[5]中算法4.2确定v--结构（更新C）；
3：利用[5]中算法4.3找到最终骨架（更新C和sepset）；
4：利用[5]中算法4.2确定v--结构（更新C）；
5：利用[4]中的规则（R1）--（R10）尽可能的给更多的边定向（更新C）；
6：返回C，sepset。
四、实例分析
本文数据来自于某大学00级学生在校期间所学的15门数学类课程的成绩。旨在寻找数学类课程间的因果关系。选取的课程以及代码如表4.1所示，
利用R软件的pcalg包执行FCI算法得到的结果如图4.1所示，
由图4.1可以看出，课程1（空间解析几何）和课程2（数学分析1）之间的关系并不确定，可能是存在不可观测的潜变量影响，使它们表现出一定的相关性，就这两门课程的知识体系来说，并没有直接的因果关系。课程2（数学分析1）有可能影响了课程4（数学分析2），因为数学分析1中收敛和导数相关知识是数学分析2的基础，扎实的基础功底是后续学习所必需的。课程4（数学分析2）影响了课程3（高等代数），由知识结构可以看出，数学分析2中的知识是高等代数的基础和工具，多元函数的微分积分以及级数都可以帮助学习高等代数。课程4（数学分析2）和课程11（离散数学）之间的双向边表示它们之间有不可观测的潜变量影响，没有什么直接的因果关系，同理，课程11（离散数学）和课程14（最优化方法）之间关系，也是有潜变量影响。课程13（数值分析1）有可能影响课程14（最优化方法），数值分析1中的理论方法是最优化方法中的工具。所以可能会对学习最优化方法有帮助。
参考文献：
[1]Colombo， D.， Maathuis， M. H.， Kalisch， M. and Richardson， T. S.Learning high-dimensional directed acyclic graphs with latent and selection variables[J].The Annals of Statistics，2012，（01）：298-299.
[2]SPIRTES， P.， GLYMOUR， C. and SCHEINES， R. Causation， Prediction， and Search，2nd ed[M].New York：Springer Publishers，2000：188.
[3]KALISCH， M.， MCHLER， M.， COLOMBO， D.， MAATHUIS， M. H. and BHLMANN， P.Causal inference using graphical models with the R package pcalg[J].Journal of Statistical Software，2012，（02）：13-14.
[4]ZHANG， J. On the completeness of orientation rules for causal discovery in the presence of latent confounders and selection bias[J]. Artificial Intelligence，2008，（16-17）：1879-1881.
[5]COLOMBO， D.， MAATHUIS， M. H.， KALISCH， M. and RICHARDSON， T. S. Supplement to “Learning high-dimensional directed acyclic graphs with latent and selectionvariables.”[J].The Annals of Statistics，2012，（01）：16-17.
[6]Spirtes，P.，Glymour，C.，Scheines，R.Causation， Prediction， and Search[M].New York：Springer Publishers，1993：181.
[7]Spirtes， P.， Glymour， C.， and Scheines， R. An algorithm for fast recovery of sparse causal graphs[J]. Social Science Computer Review，1991，（01）：68.
[8]Pearl J.Probabilistic Reasoning in Intelligent Systems：Networks of Plausible Inference[M].San Mateo，CA：Morgan Kaufman Publishers，1988：116.
[9]王理冬，汪光陽，程泽凯，朱孝宇，贝叶斯网络的发展与展望[J].安徽工业大学学报，2006（02）：195-196.
[10]詹原瑞，谢秋平，李雪.贝叶斯网络在因果图中的应用[J].管理工程学报， 2003（02）：118.
作者简介：王福友（1992-），男，汉族，河北石家庄人，长春工业大学基础科学学院2015级统计学专业在读硕士研究生，研究方向：图模型。
张冬阳（1992-），男，汉族，吉林长春人，长春工业大学基础科学学院2015级统计学专业在读硕士研究生，研究方向：因果推断。
赵 波（1992-），男，汉族，甘肃天水人，长春工业大学基础科学学院2015级统计学专业在读硕士研究生，研究方向：生存分析。