论文部分内容阅读
图模型被广泛用来表示和分析随机变量之间的因果关系以及条件独立性.图模型中主要包括有向无环图、无向图和链图.有向无环图(通常被称为贝叶斯网络)中的边都是有向边,并且不能构成有向环,用来描述随机变量的因果关系.无向图(通常被称为马尔可夫网络)中的边是无向边,一般用来描述随机变量的相关关系.链图是一类更加广泛的图模型,它不仅包括无向图,还包括有向无环图.在对图模型的大量研究中,结构学习引起了大量讨论.目前主要有两类结构学习的方法:一类是限制型学习方法,一类是基于得分的方法.大多数结构学习的方法仅仅处理含有完全观测数据的数据库.随着计算机的发展和普及,各种数据库已经被建立,不同数据库中的变量集不一定完全相同,可能有部分变量相同.例如,在药物研究中,一个研究者搜集了一些变量的数据库,另一个研究者搜集了另外一些变量的数据库,在他们搜集的数据库中可能有相同的变量,这就是所谓的多数据库.本文主要提出两个算法,一个是基于多重数据库构建链图的算法,另一个是因果强分割搜索算法.第一个算法是从多重数据库中进行链图的结构学习,我们首先从每个单独的数据库中学习它的局部结构;其次把这些局部结构组合在一起构建一个在所有变量上的全局结构;再次,删除假边,构建全局骨架;最后,确定边的方向,构建等价类.这个算法不需要条件独立性假设,而条件独立性在大多数理论中是一个基本的假设.第二个算法是利用可观测样本集进行强分割搜索.在因果强分割搜索算法中,每个变量被分配到集合A、B、C中,并且A⊥⊥B|C.为了使结果最优化,我们在搜索过程中注意两个问题,一是使C中的变量尽可能少,二是使A与B的变量个数相差较小.这个算法是一个更加有效率的算法:首先,删减C中的变量在算法的中间进行,这就避免了C所包含的变量过多,提高了假设检验的效率;其次,本算法输出的是因果强分割,因果强分割具有很多好的性质,如在因果强分割下,有向无环图具有估计可压缩性、条件独立可压缩性、模型可压缩性,这就降低了统计分析的复杂性,并且提高了分析的有效性;最后,本算法的假设检验都是在数量相对较少的变量集进行的,可以提高小样本下大规模稀疏网络构建的有效性.我们在忠实性假定下对两个算法的正确性进行讨论,并给出例子演示算法的运行过程.