统计关系学习综述（转载），贝叶斯逻辑程序相关内容，超高难度（part1）

本人：部分转载了吉林大学的论文【统计关系学习综述】，此篇未完成最后的部分存在大量复制错误等待我修正，看之前正常的即可了解里面含有的我之前提到的 贝叶斯逻辑程序，很高难度。因为比较多和混杂，决定分着发。

Warning：这个难度已经超过李航的书了，属于进阶的高难度啊，不懂不要硬看。千万不要转载。

• 1．引言 传统的机器学习和数据挖掘方法都集中于扁(flat)数据，假设数据由同类、相互独立、 等概率分布的实体组成。然而，现实世界中的数据本质却是关系的，数据是由不同种类的实 体组成，类属性不尽相同，且实体间通过多种连接相互关联，其分布不都是等概率的。

相关的研究和实际应用都表明，似然模型比确定性模型更有效。似然模型能评估模型在一些类和成本分布区域上的行为，给出错误分类所花费的代价和不确定的类的分布；能提供 信度值，更适合实际分析任务；能处理含有噪声和不完全的数据【3】o 

统计关系学习(StatisticalRelational 领域，它集关系(逻辑)表示、似然推理(不确定性处理)和机器学习(数据挖掘)于一体， 目的是获取关系数据(在本文，关系数据系指数据之间通常具有多种多样的关系，而非指关 系数据库中的数据)中的似然模型【4】。统计关系学习又称似然逻辑学>-j(Probabilistic Logic Data Learning，PLL)，(多)关系数据挖掘(Multi—Relational Ming，MRDM)，关系学习 (Relational Learning)。 

这里的所谓“统计(或概率)”是指应用统计学习和推理技术及基于概率论的概率表示 和推理机制，如贝叶斯网、(隐)马尔卡夫模型、随机文法、马尔卡夫网等，这些表示方法 已经成功应用于很多领域，并由此得到了许多不确定性推理模型；所谓“关系(或逻辑)” 系指关系和一阶逻辑表示，使用这些方法的好处是能够很好地表示包括多个对象及对象间关 系在内的复杂情况；所谓“学习”，在这里与数据挖掘等同，系指在数据基础上得到概率关系模型

近年来，统计关系学习已成为人工智能(AI)领域的一个重要研究热点。大量的统计 关系学习方法已被提出，新方法也正在不断涌现。统计关系学习在很多重要国际学术会议 团体组织了统计关系学习研讨班；一些大学开设了统计关系学习课程；一些统计关系学习研究项目已陆续被启动，如美国国防高级研究计划局的“证据抽取和链接发现”项目 英国的“面向推理和学习的有效一阶似然模型”项目(2002至2004年)、欧盟的“似然 APRIL-1(2001至2002年)和欧盟的“似然 APRIL．II”(2002至2006年)等。 

一些以聚合分类、连接预测、基于连接的聚类、社会网建模和对象识别等为代表的主要 应用研究任务得到了确定。统计关系学习已在生物信息学、系统生物学、Web导航、社 会网、似然模型获取与利用、地理信息系统和自然语言理解等领域，取得了成功的应用。

• 2。统计关系学习方法 统计关系学习方法由似然关系模型和学习算法组成。似然关系模型是关系的似然表示形 式，通过将不同的概率表示和推理机制，如贝叶斯网、(隐)马尔卡夫模型、随机文法、马 尔卡夫网等，与关系、一阶逻辑表示相结合得到。学习是指基于数据来调整似然关系模型的 过程，包括参数估计和结构学习(或模型选择)两个任务。参数估计是在假定模型的结构 已知或固定的前提下对参数进行估计；结构学习系指模型和参数皆未知的情况，二者均需要 通过学习来得到。根据统计关系学习方法所用的概率表示和推理机制不同，我们将SRL方 法分为四类进行介绍。

• 2.1基于贝叶斯网的SRL方法

贝叶斯网是最重要、最有效和最优雅的使用概率进行表示和推理的模型。然而，传统贝 叶斯网是命题逻辑的概率扩展，该方法针对扁数据，不能处理丰富的关系数据，且表达能力有限。将传统Bayesian网与一阶逻辑相结合(一阶贝叶斯逻辑)或将Bayesian网与实体关系模型相结合(似然关系模型)，就可以处理关系数据，并具有更强的表达能力。

• 一阶贝叶斯逻辑

1997年,Ngo和Haddawy将逻辑与Bayesian网相结合,在一阶逻辑或者关系解释上定义概率来扩展贝叶斯网，提出了似然逻辑程序模型(ProbabilisticLogic Programs，PLPs), 这些工作主要根据基于知识的模型建造(knowledge based model construction，KBMC）。在该思想中，知识库被用来描述概率模型集，一个查询将导致建立一个特定模型，该模型正好能用来回答该查询．PLPs模型能将Bayesian网直接提升为一阶逻辑。

在Ｎｇｏ和Ｈａｄｄａｗｙ等人工作的基础上，２００１年Ｋ．Ｋｅｒｓｔｉｎｇ等人提出了贝叶斯逻辑程序模型（Ｂａｙｅｓｉａｎ Ｌｏｇｉｃ Ｐｒｏｇｒａｍｓ，ＢＬＰｓ），表示对象及关系，ＢＬＰｓ模型通过建立基原子和随机变量间的一一映射，将Ｂａｙｅｓｉａｎ网和正定子句逻辑结合起来。该模型使用一个简化形式的组合规则，能处理连续随机变量，简化学习。

首先一阶贝叶斯逻辑和标准一阶逻辑区别在于：(1)原子r(t¨．．，岛)和谓词是贝叶斯的， 意味着它们领域D∽相关；(2)使用“l”代替“：一”，表达条件概率分布的思想。

接着利用BLPs模型对一阶贝叶斯逻辑进行形式化描述，分别给出了贝叶斯子句、联合 条件概率分布cpd(c)、组合规则、贝叶斯逻辑程序等重要概念。

---------------------------------------------------------------------------------------------------------------------------------

一个贝叶斯子句c形式表达如下：么IA，，．．．4。，此处刀≥0，A，A¨．．，么。是贝叶斯原子， 且所有的原子是(隐含地)全称量词限定的。 直观上，贝叶斯谓词一般表示随机变量的集合，每个贝叶斯基原子表示一个随机变量。 对于每个贝叶斯子句，都和一个条件概率分布cpd(c)市H关。 设c是贝叶斯子句r(，l'．．．，岛)IS1(fl，1，…，tl,n1)，…，％(‰，l，…，‰朋)，联合条件概率分 1】，其中cpd(c)(uI甜l，…，‰)=p(r(h…．，岛)=Ul Um)· 当将Bayesian网表示成命题子句集合时，恰有一个子旬来定义每个贝叶斯谓词。而在 贝叶斯逻辑程序中，可能会有两个子句c1、c：以及对应的替换岛得到的子旬C，，满足head(c，研) =head(c2晓)，这样会出现一个复杂化的问题，即可能存在多个基子句具有相同的首部。这种 情形下，获取概率分布的一般方法被称为组合规则。 一个组合规则是一个算法，该算法能将每个条件概率分布的有限集{P似M“，…4胁f)l {曰l，．．．，岛)=U：，{4∽．．，以，)且玎且玎<00．输出为空当且仅当输入为空。 一个贝叶斯逻辑程序B由贝叶斯子句集合构成。对于每个贝叶斯子句c，恰存在一个相 关的epd(c)，对于每个贝叶斯谓词，，恰存在一个相关的组合规则comb(r)． ．设B是一个贝叶斯逻辑程序，则口的贝叶斯子句集合所对应的逻辑正定子旬集合称为 对应的逻辑程序‖． 关于～阶贝叶斯逻辑的结构和参数学习方面，文献[161定义了一种表示上下文敏感概率 知识的语言，并为该语言提供了声明语义；文献【17】提出了概率逻辑子集和贝叶斯网动态生 成算法，逻辑子集足以表示具有离散值结点的贝叶斯网，贝叶斯网生成算法以查询Q和证 据集E形成推理问题，并通过生成贝叶斯网实现P(QlE)的计算；文献【18]弓1进了连续贝叶 斯逻辑程序，通过扩展BLPs使其能处理连续随机变量，该文还讨论了利用梯度方法解决最 大似然参数的问题：文献[201和【21】结合贝叶斯网和l乙P，从数据中学习BLPs的定性(即逻 辑)和定量(即概率)两部分。 似然关系模型 Relational 似然关系模型(Probabilistic model)作为基本的表示框架。 型使用表示实体间的关系的实体关系模型(entity-relationship 可以将PRM看成描述关系型数据库上概率分布的模板，模板的结构描述关系模式及属性间 的依赖，模板参数定义对象属性依赖关系的概率分布。 PRM模型由两个部分组成：依赖结构s和与之相关联的参数出．S由多个结点构成， 结点之间存在依赖关系。类X的属性爿作当前结点，表示为X．A，其父结点集是直接影响 X．A的属性集，用Pa(X．A)来表示．Pa(X．A)包含两种类型的结点，一种为同一个类中与之相 。 243 关的另一属性X．B，另～种为当前类的相关类中的某属性xpB．由于关系模式中存在关系链 石本质上类Ⅳ的某个实体x的属性值x．a还间接依赖予与之相关的所有实体的属性x．￡b． 可把数据库中聚合的概念引入到模型中，用丫Ⅸ￡B)表示X．A的父结点。有了模型结构S， 就可以计算父结点与子结点的条件概率分布P(X．AIPa(X-4))。条件概率分布中包含参数0s． 这样PRM模型就可以形式化表示为： P(I I仃，S，铅)=兀兀兀P(L．。lIr巾。)) XiAEAtX。’xe()0 tX。、 其中，，表示模型的一个实例，07倒表示所有实体的已知属性。PRM模型就是由实体的已 知属性求每个结点与父结点间依赖关系的概率分布，从而得到实例的未知属性。 在PRM模型的基础上，人们又开展了一些深入研究．2001年，Getoor等人【25≈71提出了统计关系模型SRM，SRM和PRM在语法方面相同，但SRM通过连接频率定义了依赖语义， 从而能回答与频率相关的查询．2003年，San曲ai等人【28】通过拓展动态Bayesian网，提出了 等人130J在实体关系图的基础上，基于BayesianNJ给出了有向无环似然实体关系模型，该模型 是一种表示抽象属性间条件独立性的语言，是PRM的泛化。 传统贝叶斯网的推理算法f3卜36】和学习算法【32,37--42]口-j-以直接或经过扩展后应用于PRM 的参数评价问题．Friedman等人【22J在研究直接从数据中对PRM模型进行结构学习的更复 杂方法