论文部分内容阅读
有向无环图(DAG)是表示因果关系的很直观的工具，图中节点表示研究的变量，有向边表示因果关系，如X→Y表示变量X是变量Y的原因。用有向图表示因果在经济学，社会学和心理学中有很多应用，包括结构方程模型和路径分析方法。近十几年来，人们将图的结构通过Markov条件和变量的概率分布联系在一起，一个有向无环图G和一个满足Markov条件的分布P就构成了一个贝叶斯网络(Bayesian Networks)，又称为概率网络(Probabilistic networks)或置信网络(Belief networks)。
如何通过观测数据学习潜在有向无环图是一个重要的问题。一方面，它可以从观测数据中挖掘变量之间的因果关系，增加我们的知识，另一方面，它可以用于干预下变量的预测问题。现有的学习算法可以分为基于条件独立性约束的和基于搜索得分的两类。基于独立性检验约束的方法逻辑清晰，可以应用于有隐变量的数据，可以方便的学习贝叶斯网络的局部结构，但是需要忠实性假定，基于独立性检验的学习在样本量趋于无穷时仍然不能消除因第一类错误造成的少边。后者不需要忠实性，可以自然的融合先验信息，能渐近的得到与分布相容的参数最少的模型，但是因为搜索空间太大所以收敛速度不快，且需要对分布做出参数化的假定，在样本量不够大时效果不好且不易推广到隐变量等情况。近来Guyon等人指出，贝叶斯网络结构学习的发展趋势是讲这两种算法结合起来[1]，如MMHC算法等。
基于奥莱姆剪刀原理，对于一个分布P，本文定义相容于P的参数最少的有向无环图为”真”模型。对于忠实的分布P，这个”真”模型即与P忠实的有向无环图。对于基于独立性约束的算法，文中指某算法收敛至”真”模型，都是指，结果收敛到代表”真”模型观测等价类的部分有向图(PDAG)。对于贝叶斯方法，指得分最大模型属于”真”模型的观测等价类的概率趋于1。
本文研究了以下三个问题，并提出了自己的方法。
第一，对于学习MB的问题，提出了基于BIC得分的后退算法BIC-MB，并证明了算法和得分的相合性。现有的学习MB的算法都是基于独立性约束方法，只有在忠实性假定和条件独立检验正确的条件下才能保证算法的相合性。而学习MB(T)相当于预测T模型的变量选择问题，对指数分布族中，论文[3]中Haughton证明了BIC得分最大模型的相合性。本文在无约束的离散取值变量中推导了BIC得分，并证明了得分最大模型的相合性，同时提出了基于BIC得分的后退搜索算法，使得我们能仅需计算n(n+1)/2+1个模型的BIC得到的最大得分模型仍依概率收敛于真模型。而且这种相合性不需要忠实性条件。注意，本文中MB(T)定义为使得T()other|MB(T)成立的最小集合。在忠实性下，它是真模型G中T的父节点，子节点以及子节点的父节点的并。
第二，对于寻找目标变量T的父节点集pa(T)以及子节点集ch(T)的局部定向问题，提出了PCDbyPCD算法和MBbyMB算法，证明了在忠实性假定和假设检验正确的条件下，两个算法的结果和潜在模型等价类的结构一样。局部定向问题的研究源于WCCI2008因果挑战问题和NIPS2008的因果挑战问题。前者要求根据观测分布，对干预后的目标变量做出尽可能精确的预测，后者关心贝叶斯网络中目标变量周围的边的方向。他们共同的特点是变量数目很大，几百甚至几千，现有的全局贝叶斯学习算法计算速度都很难达到，且只关心目标变量周围的边及方向，而不关心整个网络的结构。对此，本文提出了PCDbyPCD算法。事实证明，这个算法相比全局算法速度大幅提高，而且模拟结果表明，在模型精度上与全局算法中精度最好的MMHC算法不相上下甚至更高。最终，本文的算法在这两次比赛中均战胜了其他团队提出的学习算法，获得了Best Overall Contribution奖，具体细节见[4][5]。MBbyMB算法借鉴了文[6]中局部学习的想法，在一定的独立性条件下，本文可以保证在部分变量上运行全局学习算法和在所有变量上计算的结果在某些局部一样，从而能够通过对部分变量数据进行学习得到局部定向。
第三，对于部分变量观测数据的贝叶斯网络学习问题，本文给出了一系列充分条件，并给出了这些条件下的学习算法，使得我们可以根据这些服从边缘分布的部分变量观测数据，在样本量充分大的时候，得到和数据完全观测一样好的结果。现实中，随着信息技术的发展，有越来越多的大型公共以及商业数据库建立起来，很多时候，我们并不一定能找到包含所有相关变量的观测数据。并且，有些时候即使我们有完全观测数据，我们也希望能够利用部分变量观测数据的信息提高学习效果。比如当一个数据集有大量数据有个别变量随机缺失时，希望利用那些有缺失的数据。关于在部分变量观测数据下如何学习贝叶斯网络的问题，现有的研究不多，Danks等在文献[7][8][9]中基于首先在每个数据中检验条件独立性，然后再根据这些独立性推断图模型的想法，最后提出了ION算法，整个讨论都是基于条件独立性约束方法。而且没有讨论什么时候我们能根据这个算法得到潜在图模型等价类的问题。本文考虑了如何根据部分观测数据得到和完全观测数据一样好的结果得问题，并给出了一系列条件和算法如下。如果根据ION[7]等算法或者专家经验，对每个变量X，已知集合pa+(X)包含X的所有父节点，且有同时含X和pa+(X)的数据Dx，那么可以通过搜索BIC*得分最大的有向无环图渐近得到真模型。其中BIC*是本文根据BIC的原则提出的定义在部分变量观测数据上的得分。进一步，如果对每个变量X，已知集合pc+(X)的包含X的所有父子节点，且有同时含X和pc+(X)的数据。那么本文提出了与MMHC类似的MMHC*算法，并证明了，在忠实性假定，假设检验正确，样本量充分大的条件下，此算法可得到真模型。同时，本文考虑了部分观测数据下贝叶斯网络的部分定向问题，得到如下结果。如果对每个变量X，已知集合pc+(X)包含X的所有父子节点，且有同时含X和pc+(X)的数据，本文结合独立性约束方法和搜索得分方法，提出了pcdpcd-bayes算法，并证明了在忠实性假设和假设检验正确的条件下，学得的局部定向依概率收敛于潜在图模型等价类的局部定向。最后，如果对每个变量X，已知集合mb+(X)包含X的MB，且有同时含X和mb+(X)的数据，本文提出了与MBbyMB类似的MBbyMB*算法，可以得到和完全数据一样的结果。
本文用LUCAS数据对BIC-MB算法进行了模拟研究。用ALARM网络对PCDbyPCD算法和MBbyMB算法进行了模拟，并介绍了在WCCI2008挑战比赛数据中我们的结果。最后，本文对pcdpcd_bayes算法进行了模拟。本文对所有由笔者得到的定理都给出了证明。