论文部分内容阅读
因果网络模型已被广泛应用于很多领域。利用数据进行因果网络的结构学习是因果推断研究领域中的重要问题之一。当前已有一些算法可以从观测数据学习变量集的全局因果网络或局部因果关系。全局网络结构学习算法的复杂度为NP,随着变量数目的增多,复杂度迅速上升。目前一些局部因果关系学习算法,即使得到大样本数据甚至真分布,也不能保证能够学习得到正确的局部网络。针对现有的全局网络结构学习算法和局部结构学习算法的上述弱点,本文探讨新的结构学习算法,提出全局网络结构学习的得分分解算法和逐步扩展的局部网络学习算法。主要研究内容包括: ⑴利用条件独立性信息,提出了将全局网络的BIC得分学图问题分解成两个较小网络上BIC得分学图问题的BIC分解学图算法。由于有向无环图(Directed Acyclic Graph,DAG)的数目随着变量数目的增多以超指数的速度增长,所以将一个大网络的BIC得分学习问题分解成两个或更多小网络的得分学习问题,可大大降低算法的复杂度。 ⑵在条件独立性检验的框架下,提出了局部扩张学习算法:PCD-by-PCD算法和MB-by-MB算法。两个算法从学习目标节点开始,每步学习一个节点的父子后代(parents-children-or some descendants,PCD)集合或Markov边界(Markov Boundary,MB)上的局部图,并根据条件独立性检验更新学习的局部网络,当可判断当前学出的局部网络与真图的Markov等价类一致时算法停止。PCD-by-PCD算法和MB-by-MB算法可得到与全局网络算法相同的局部网络结构,同时有更高的时间效率。相比于PCD-by-PCD算法,MB-by-MB算法对样本量的要求较大,但在大的稀疏网络上有较快的速度。 ⑶在一些实际研究中,我们只关注某个响应变量附近的局部网络,但是不能同时观测所有变量,而是每次只能观测到某个变量和与它相关的一些变量。现有的算法都是基于整个变量集的完全观测数据进行学习。本文基于独立性检验和BIC得分搜索,提出了在这种不完全观测情况下逐步观测和逐步学习相结合的全局网络结构和局部网络结构的学习算法。 ⑷对所提出的全局结构学习的分解得分算法、逐步扩展的局部结构学习算法和不完全数据的结构学习算法从理论上论证了它们的正确性,并利用模拟方法对这些算法进行了评价和与其他算法进行了比较,模拟结果体现了所提出算法的有效性和正确性。