1. 引言
面对海量的网络信息，如何处理信息的复杂性和不确定性问题是人工智能、数据集成的难点之一。为解决这类问题近年来提出了统计关系学习[1] (statistical relational learning, SRL)和概率图模型[2] (probabilistic graphical model, PGM)。统计关系学习是通过逻辑表示、概率推理、机器学习和数据挖掘等方法获取关系数据中的似然模型。概率图模型将概率统计信息与数据的结构信息相结合，主要涵盖了贝叶斯网络(Bayesian networks, BNs) [3] 、隐马尔科夫模型(hidden Markov model, HMM) [4] 、神经网络(neural network, NN) [5] 等方法。人们迫切需要一种模型将逻辑表示方法和概率方法结合起来。
2004年美国华盛顿大学的Domingos和Richardson首次提出了马尔可夫逻辑网[6] (Markov logic networks, MLNs)，MLNs可以将统计关系学习和概率图进行较好的结合，比纯逻辑方法和纯概率方法能更好的解决问题。Markov逻辑网是一种统计关系学习框架，具有强大的描述能力、逻辑推理能力和处理不确定性的能力。从处理不确定性问题看，Markov逻辑网为一阶谓词附加权值，容忍知识库中存在不完整和互相矛盾的知识，具有较好的处理不确定性问题的能力；从概率统计方面看，Markov逻辑网为描述Markov网络提供了简洁有效的方法。Markov逻辑网已成为人工智能、数据集成、机器学习等领域的研究热点，具有广阔的应用前景。
本文介绍Markov逻辑网，在介绍模型定义的基础上简要介绍Markov逻辑网的推理、参数学习、与其他统计关系学习算法的比较，Markov逻辑网的主要应用和未来研究方向。
2. Markov逻辑网
2.1. Markov逻辑网的基本概念
Markov逻辑网是一种将Markov网络与一阶谓词逻辑相结合的统计关系学习模型[7] ，为Markov网络提供一种简洁的描述语言，为一阶逻辑增加了不确定性处理能力。
Markov网络也称为Markov随机场(Markov random field，简称MRF)，是一个变量集合
的联合分布模型。Markov网络由无向图G和定义于G上的一组势函数Фm组成，G中每个节点代表一个随机变量，G中每个团对应一个非负势函数Фi，代表团的一个状态。
一阶谓词逻辑是建立在一阶语言基础上的逻辑体系[8] 。一阶语言由常量、变量、函数和谓词四种类型符号组成，若干一阶谓词逻辑组成一阶谓词知识库[9] 。常量指定义域里一个简单的对象；变量指定义域里若干对象；函数表示一组对象到一个对象的映射；谓词指定义域中若干对象之间的关系，如FatherOf()，以及对象的属性，如Accurate()。一阶逻辑可以看做在可能世界的集合上建立的硬性规则，一系列硬性规则组成一阶逻辑知识库。如果一个世界违反了知识库中某一条规则，这个世界存在概率就为0。
Markov逻辑网的基本思想是放松一阶谓词逻辑的硬性规则，给每个规则附加权重。如果一个世界违反了其中一条规则，这个世界存在的可能性将降低，但仍有可能存在。一个世界违反的规则越少，这个世界存在的可能性就越大。一个规则的权重越大，越接近于一阶谓词逻辑。
Markov逻辑网的定义：Markov逻辑网L是一组二元项
，其中Fi表示一阶逻辑规则，wi是一个实数。
与有限常量集
一起定义了一个以闭谓词为节点，闭谓词关系为边的Markov网ML,C，其中：
1) L中任意闭谓词都对应ML,C中的一个二元节点．若此闭谓词为真，则对应的二元节点取值为1，否则为0。
2) L中任意闭公式都对应ML,C中的一个特征值，若闭公式为真，则对应的特征值为l，否则为0。特征值权重为二元项中该规则Fi对应的权重wi。
由定义可知，Markov逻辑网ML,C可以看作是一个构建Markov网络的模板，给定相同的Markov逻辑网ML,C和不同的有限量集合C，可以产生不同的Markov网络。这些Markov网络有一些相似点，比如有相同的团的数目，同一规则所有可能常量取值有相同权重。根据这种方式产生的Markov网络称为闭Markov网，一个闭Markov网中所蕴含的可能世界x的概率分布如下:
(1)
公式(1)中，Z为归一化常数，ni(x)为Fi在x中所有取值为真的基本规则数量，x{i}是Fi中为真的原子，
，wi为第i个公式Fi的权重。如果一个规则包含多个从句，这些从句将平分该规则的权重。
2.2. Markov逻辑网实例
从公式(1)中可以看出，对应同一公式的所有闭公式有相同权重。设知识库包含公式F1和F2，权重分别为1.2和2.0，一个简单的Markov逻辑网实例见表1。
表1中，x和y分别表示个体变项，Dr(x), Hy(x)和Fr(x, y)分别表示x酗酒与否，x患高血压与否，x与y是否是朋友的谓词；规则F1表示酗酒导致高血压，F2表示如果x与y是朋友，则他们可能都酗酒，可能都不酗酒。公式F2中两个从句平分权重为1.0。当给定个体常项集合
时，生成的闭Markov网络如图1所示。
从图1中看出，闭Markov网络中有6个团，团的权重如表2所示。
Table 1. A simple Markov logic network example
表1. 一个简单的Markov逻辑网实例
Table 2. A closed Markov network and its weight
表2. 闭Markov网及其权重
3. Markov逻辑网的推理
Markov逻辑网的推理主要在生成的闭Markov网上进行，可以进行边缘概率，条件概率和最大可能性推理。
3.1. 边缘概率和条件概率
边缘概率的推理问题可以表示为：给定Markov逻辑网和常量集，求某个规则取值为真的概率。条件概率是在边缘概率中给定了若干其他规则的取值情况，求某个规则取值为真的概率。
根据条件概率和Markov逻辑网定义可知，给定Markov逻辑网L、常量集C以及给定规则F1取真时，规则F2取真的概率为：
(2)
公式中
是所有使F1取值为真的世界存在的概率之和。公式中随着闭原子个数的增加，计算量将指数级上升。有效的方法是运用MCMC(Markov Chain Monte Carlo)算法[10] [11] 和的基于整数线性规划的CPI (Cutting Plane Inference)算法[12] 来近似推理。文献[13] 提出了切片抽样的MCMC算法MC-SAT，算法严格遵从MCMC所需要的遍历原则和细节平衡原则，在原有的MCMC算法中引入一个辅助参数，捕捉变量之间某些确定性关系，用模拟退火步骤对切片进行采样。文献[14] 证明，MC-SAT算法得到的概率非常准确。
3.2. 最大可能性
最大可能性问题是概率图模型推理的重要内容，其基本过程表述为：给定证据变量集x，求变量集y最可能处于的状态
。在Markov逻辑网中转化问题为求
，其中wi表示从句i的权重，
表示从句i的闭从句的真值数量[15] 。计算最大可能性问题可转换为最大化带权的可满足性问题，即寻找一组变量的赋值，使得所有被满足的从句权重之和最大。Richardson为解决这个问题提出了MaxWalkSAT算法[16] ，算法首先对所有变量随机赋值，然后在所有未满足的从句中随机选取一个从句，改变从句中一个变量x的值。变量x的选取可以根据概率随机选取，可以根据是否选取后所有已满足的从句权重之和达到最大进行选取。MaxWalkSAT算法有一个缺点是内存的需求量会随着从句数量增加呈指数级上升，文献[17] 提出的LazySAT算法弥补了这个缺陷。LazySAT算法是一种“需要时再激活”的“惰性”思想，利用一阶知识库的稀疏性，隐性决定了大多数闭从句的取值都为真。算法对内存的需求量只由搜索进行当中那些潜在的未满足的闭原子和闭从句决定。LazySAT算法提高了推理速度，但没有提高推理的精度，文献[18] 进一步提高推理速度。
4. Markov逻辑网的参数学习
Markov逻辑网的学习分为结构学习和参数学习。参数学习是指在Markov逻辑网结构确定的前提下，进一步学习和优化模型的参数。参数学习即学习公式(1)中的权重wi。参数学习可以采用最大似然方法，一个规则Fi的权重wi的对数似然函数梯度可表示为：
(3)
其中
为世界x中规则Fi的真值个数，
是在所有可能世界
中求和，
的计算建立在当前的规则权重向量集
上。直接计算规则Fi的真值个数的数学期望并不可行，目前主要方法是使用伪最大似然估计[6] 和区别式训练[19] 。
4.1. 伪最大似然估计
伪最大似然估计是对Markov逻辑网的伪似然概率分布，公式如下：
(4)
其中xl表示l个闭原子的真值，MBx(Xl)表示Xl的Markov边界，伪最大似然估计可以学习Markov逻辑网参数，但伪似然参数会导致非邻接变量之间的推理结果不理想。区别式训练参数方法可以解决该问题。
4.2. 区别式训练
区别式训练假设谓词分为两个集合: 证据谓词集合X(谓词已知真值)，查询谓词集合Y(谓词未知真值)，通过对条件概率求最大似然来学习权值wi，公式如下：
(5)
其中Fy是公式集合，该集合的每个公式至少包含1个闭查询谓词。
是知识库中第i个公式的真闭公式个数。
5. 统计关系学习算法比较
目前统计关系学习(SRL)方法主要有基于Bayesian网的SRL方法、基于隐Markov模型的SRL方法、基于随机文法的SRL方法和Markov逻辑网。MLNs与基于Bayesian 网的似然逻辑程序模型(Probabilistic Logic Program, PLPs) [20] 相比，具有能够在对象实体和关系不断变化中自动调整其网络结构，能够通过自动更新Markov网来调整规则的权重，能够对同一实体对象动态识别的优点。MLNs与隐Markov模型(HMM)相比，虽然HMM可以有效解决动态序列化问题，但处理数据时要遵循数据块之间是独立的前提[15] ，而MLNs没有这种限制。MLNs与基于随机文法的SRL方法相比，如与随机逻辑程序(stochastic logic program, SLP) [21] 和统计建模程序设计(programming in statistical modeling, PRISM) [22] 方法，MLNs推理和学习方法比较灵活，在处理质量较差的数据时MLNs受到的影响较小，而SLP和PRISM算法会受到较大影响。
6. Markov逻辑网的主要应用
Markov逻辑网(MLNs)作为统计关系学习的统一框架，受到国内外人工智能、数据挖掘、机器学习等领域[23] [24] 研究的广泛关注，Domingos研究团队不断完善Markov逻辑网的理论体系，并提供了一个学习和发展该理论体系的平台Alchemy[25] 。MLNs作为统计关系学习的统一框架，在实体识别[26] -[28] 、信息抽取[29] -[33] 、社会网络[34] 、语义网络[35] 、自然语言理解[36] -[39] 、数据挖掘[40] [41] 、生物信息[42] [43] 等方面都有大量应用。
国际上，文献[26] 将Markov 逻辑网与多个实体识别方法无缝结合，有效解决实体识别问题。文献[33] 利用Markov逻辑网采用StatSnowball方法进行Web实体关系的抽取。Gayathri等人[43] 使用MLNs进行层次行为识别。Cheng等人[44] 将Markov逻辑网运用于主题发现。Chahuara等人[45] 利用Markov逻辑网来处理不确定性推理问题。在国内，胡宜敏等人[28] 提出将Markov逻辑网和基于本体与Web搜索的属性抽取算法相结合的命名实体解析方法。刘永彬等人[32] 提出使用基于MLNs的联合推理模型处理开放式信息抽取。李燕[40] 构建Markov转移矩阵，针对过程挖掘算法的局限性设计多步过程挖掘算法。重庆大学张玉芳副教授的研究团队使用Markov逻辑网进行文本分类[46] [47] ，重复数据删除[48] ，取得较好效果。中国科学院的吴蕾等人将多个主题模型和MLNs相结合，提出了一种融合概率图模型[49] ，解决异构信息网络中存在多种数据目标类型和多种数据连接关系的问题；将隐马尔科夫网络与条件随机场相结合，提出基于深度学习框架的隐藏主题变量图模型[50] ，有效挖掘主题信息。张永新等人[51] 提出使用MLNs处理数据融合中的冲突问题，将冲突分为强冲突和弱冲突，制定不同规则使用MLNs推理真值，解决数据冲突。
7. 未来研究方向
统计关系学习模型Markov逻辑网的研究在起步阶段，模型需要完善，推理和学习算法仍需拓展。Markov逻辑网将来可以从以下几方面深入研究：1)增强算法学习能力，使其可以从不完备数据中学习；提高学习算法的效率，提高真闭公式个数计算速度。2)从一阶逻辑和 Markov 网两个方面完善 Markov逻辑网理论。3)扩展模型的应用范围，例如与主题模型等其他模型融合，与自然语言处理、信息抽取、数据融合、生物信息等领域充分结合，更好的解决实际问题。