文摘

我们提出一个有向无环图的结构学习方法从多个数据库。我们首先学习局部结构分别从每个数据库,然后我们把这些局部结构共同构建一个全局图对所有变量。在我们的方法,我们不需要有条件的独立,这是一个基本的假设在大多数方法。

1。介绍

图形模型包括独立图表,有向无环图(无进取心的人),和贝叶斯网络已经广泛应用于许多领域,如数据挖掘、模式识别、人工智能、复杂的系统,和因果关系的发现1- - - - - -4]。图形模型可以用来应对不确定性与许多大型系统变量。图形模型的数据结构学习是一个重要而困难的问题,已经被许多作者讨论(1- - - - - -5]。有两种主要的结构学习方法。一是理论学习,另一个是参考学习。大部分的结构学习方法,只有一个数据库处理完全观测数据。随着计算机的发展和普及,各种数据库已经建立,它可能包含不同的变量和互相重叠。例如,在医学研究,研究人员收集这些变量的数据,另一位研究人员可能收集数据的其他变量,和他们有一些共同的变量。

在本文中,我们讨论如何学习熟练的技艺从多个数据库具有不同的结构和重叠的变量。在我们的方法,我们首先了解当地结构分别从每个数据库,然后我们将这些结构结合在一起,构建一个全球所有变量的图。一些理论结果显示我们的算法的有效性。我们的方法可以有效发现熟练的技艺从多个数据库。在我们的方法中,我们只需要一个条件低于条件独立,这是一个基本的假设在大多数方法(1- - - - - -5]。这种方法还可以利用先验知识的条件独立性降低变量在每个条件设置的数量。

部分2给出了符号和定义。节3,我们展示了如何构建与多个数据库的DAG。我们举个例子4为了说明我们的方法恢复DAG。最后讨论了在部分5。

2。符号和定义

让表示一个DAG是一组顶点和是一组定向边缘。一个有向边从一个顶点到另一个顶点用和我们说是父母的和是一个孩子。我们表示所有父母的顶点的集合通过。一个路径之间的两个截然不同的顶点和是一个独特的顶点序列开始吗,以,连续两个顶点相连的边缘;也就是说,,在那里或包含在,因为(),,尽管。我们说的是一个祖先和的后裔如果有一个路径来在和这条路径上所有边缘点的方向。表示的祖先的集合作为。一个路径据说是由一组顶点吗当且仅当存在至少一个,这样。和据说是分开的当且仅当(1) 包含一个“链”或“叉”这样中间顶点是在,或(2) 包含一个“倒叉”这样的碰撞点不在没有后代的是在。

两套和顶点是分开的(由一组分离)如果分离(从任何顶点在分离)每条路径任何顶点在,我们说是一个分隔符(分隔符)和。如果,和在DAG,那么三被称为不道德和和被称为不道德的两个父母。

请注意,这两个顶点和不相邻的DAG当且仅当分开的一个子集。尽管这是显而易见的了是或对于熟练的技艺,有某些类型的图表,nonadjacency分离性是不够的,例如,祖先图(6]。

例2.1。考虑一个DAG在图1,在那里和。在这十克,我们这,,,,是不道德的。的路径之间的和是分开的或,而路径之间的和是分离的空集,顶点的是一个祖先和的后裔。的集和是分离的设置。

让顶点在DAG表示变量。如果一个变量的联合分布或密度满足 在哪里的条件概率和密度吗鉴于,然后DAG和分布据说是兼容的(3),遵循全球导演马尔可夫性质(2]。我们使用的符号7)来表示的独立性。让表示的独立性和和的条件独立和鉴于对于任何一个变量或一组变量,,。因为在我们的讨论,我们总是认为联合分布对应于一个潜在的DAG,我们不区分字母的用法,,,,,表示变量或顶点;但是,我们将一个明显的参考如果上下文是不清楚。

所指出的(3),如果集和是分开的,然后是独立于有条件地在在每一个兼容的分布。在本文中,我们假设所有的发行版都兼容。我们还假设所有变量的概率分布的独立性可以通过检查分离的,称为诚实的假设在4]。信实的假设意味着所有变量之间的独立性和条件独立性可以表示为。遵守诚实的分布假设,我们可以通过检查了解底层DAG成对条件独立,在那里和两个随机变量和吗是变量的一个子集。

一个超图是顶点集的集合(8,9]。多个数据库被描绘成超图,hyperedge吗是一个观测变量在数据库和设置(5,10]。一个数据库和一个观测变量集被当作一个样本变量集的边缘分布。让的交集和其他设置。给定一组数据库,没有更高的信息在不同的数据库的交互。

例2.2。让是一个超图,如图2。我们可以得到,,,。

3所示。结构学习熟练的技艺

在本节中,我们提出一个熟练的技艺的结构学习方法。在我们的方法,我们首先学习每个数据库的局部结构,然后我们把这些局部结构结合在一起,构建一个全球所有变量的图。

注意,对于一个分布服从诚实的假设对某个DAG可能不存在有DAG可以完全代表所有条件独立性的边际分布;参见[6更多的讨论这个问题。虽然这一事实意味着,我们可能不希望学习DAG为每个数据库,它将表明,在一定条件下的边际结构可以学到这部分反映了原始真实的结构。

我们考虑一组变量的联合分布这满足信实的假设和表示DAG可以完全代表本联合分布的条件独立性。我们考虑问题从多个数据库结构的恢复。为了便于讨论,我们首先给出局部结构的定义。

定义3.1。对于一个DAG和一个子集,我们定义局部结构是一个无向图的边缘设置对所有。

从定义,众所周知,判断和局部结构中相邻吗,我们只需要寻找分隔符从所有可能的变量子集这样两个变量和是独立的有条件地在。与信实的假设,这相当于测试是否和是独立的有条件地在这可以通过使用数据观察只有。注意边缘的局部结构可能是虚假的,它不相邻的两个顶点原始的DAG;我们称这些边缘伪边缘。然而,在下面的小节中,我们展示了这种学习局部结构可以用来识别原始DAG的真实结构的一部分在一个附加条件。我们给出一个引理证明的定理。

引理3.2。如果不是一个祖先的,然后和是分开的一个子集当且仅当分开的。

证明。参见[2]。

下面的两个定理展示当地的关系结构和原始DAG的真实结构。

定理3.3。让,,的分区。如果和由,然后两个顶点是分开的一个子集当且仅当分开的一个子集。

证明。的必要性是显而易见的。充足,让和是两个顶点这是分开的 。因此没有边缘连接和在。自和被包含在和和由,和被包含在。不失一般性,假设不是一个祖先的。从引理3.2我们有 分离和。

从定理3.3,我们可以看到,两个顶点在DAG相邻吗当且仅当它们在当地相邻结构。这意味着诚实的假设,边落入的存在从边际分布可以确定有效吗。

定理3.4。假设,,是一个分区和和由。让和。如果和是分开的一个子集,然后他们分开的一个子集。

证明。结果是显而易见的。

根据定理3.4,我们可以看到这一点 和 不相邻的DAG如果不相邻的局部结构。这意味着我们可能会假边缘局部结构。

根据上面的两个定理,我们可以得到一条边的两个顶点都包含只有一个数据库可以使用的边际分布决定了吗没有其他数据库的需求。这些边缘交叉和或下降到可能是假的。他们的存在必须确定根据多个数据库。

现在我们有向无环的结构学习算法的图形模型。

算法3.5。构建一个从多个数据库DAG(1)输入:多个数据库。(2)构造一个局部结构从数据库分别为每个:(一)初始化作为一个完整的无向图;(b)删除边从如果存在一个子集的这样和是条件独立的给。(3)构建全球无向图:(一)初始化边缘设置的作为工会的边集为;(b)对于一个边缘,会变成一些,删除它如果是在其他缺席。(4)删除虚假边缘构造全球框架:(一)对于一个边缘与在一些和在,删除它如果存在一个子集的这样和是条件独立的给;(b)对于一个边缘,下降一些,删除它如果存在一个子集的或这样和是条件独立的给。(5)构造等价类:(一)东方当地的骨架作为如果和不相邻的和;(b)东方其他边缘相反如果每个人创建定向循环或新的不道德。(6)输出:熟练的技艺的等价类。

请注意,在步骤4表示的所有顶点与顶点相邻。根据定理3.3和3.4,上面的等价类构造的算法是有效的。

4所示。结构学习的例子

在本节中,我们使用报警网络图说明我们的算法3常被用来评估结构学习算法(4,11,12]。报警网络图3描述了37个变量之间的因果关系在医疗诊断病人监护系统。使用网络,一些研究人员生成连续的正态分布的数据和其他从多项式生成离散数据分布(4,12]。我们的方法适用于两个连续和离散数据。因为可以保证算法的有效性定理3.3和3.4说明了算法,使用条件独立性从底层有向无环图在图3而不是从模拟数据测试条件独立。

假设我们有三个数据库超图描述的图3。数据库包含变量、数据库包含变量和数据库包含变量。因此,,。请注意,和没有条件独立吗。在第2步,当地结构分开了三个数据库,如图4(一),4 (b),4 (c)分别为例,无向边因为是独立于有条件的。

在步骤3中,我们把三个局部结构结合在一起,构建全球无向图,如图5。在步骤4,我们删除虚假边缘的全球框架,这是无向图的版本6。例如,伪边缘可以删除,因为变量和是条件独立的给。

在步骤5中,我们确定不道德和东方边缘尽可能多。例如,无向边的方向确定是通过这样就不会创建一个新的结构和无向边的方向确定是通过和这样就不会创建一个循环。我们终于获得等价类图6正确,所有直接面向边缘的,除了四个无向边,,,面向不能因为任何的取向导致马尔可夫DAG。

5。讨论

在本文中,我们提出了一个有向无环图的结构学习方法从多个数据库。在我们的方法中,我们要求和由,这是一个比条件较弱的条件和是分开的。这种情况可以与专家的判断变量之间的关联的先验知识,如马尔可夫链、链图形模型,和时间序列。

有几个明显的优点我们的方法进行结构学习。首先,我们不需要有条件的独立,这是一个基本的假设在大多数方法。第二我们搜索分隔符在或,这是远小于。最后,本文提出的理论结果可以应用到多个数据库的方案设计。没有损失的信息结构学习熟练的技艺,联合数据集可以被一群不完整数据集根据先验知识。

确认

我想感谢裁判的宝贵的意见和建议。这项研究得到了国家自然科学基金委(11001155),山东省博士基金(BS2010SW030),和一个项目山东省高等教育科技计划(J11LA08)。