PDF《马尔科夫逻辑网络》

马尔科夫逻辑网络 从贝叶斯信念网到马尔科夫逻辑网 高阳http://cs.

nju.edu.cn/gaoy, 2016.11.08 大纲 马尔科夫网 马尔科夫逻辑网 马尔科夫网络推理 近似推理 马尔科夫网 Markov链 考虑一个N(有限)状态{s1,s2,…,sn}的系统: 在离散的时间序列中{t1,t2,…},其在时间t的状态记为Xt, 系统在时间t处在状态sj(1≤j ≤ n)的概率取决与其在时间1,2,…,t-1 的状态: 一阶马尔科夫链 P ?? = ?? ?1, ?2, … , ???1 P ?? = ?? ?1, ?2, … , ???1 =P ?? = ?? ???1 俄罗斯数学家 Markov网 有向图 + 概率分布:Bayesian Network 无向图 + 概率分布:Markov Network(Markov Random Field, MRF), G=(V, E) 顶点:随机变量 V 边:变量间的依赖关系 E 团(Clique):各边所在的最大全联通子图 势函数:为非负函数,表示团的一个状态 联合分布函数 ? 吉布斯测度:已知一种分配方案x,求MLN刚好为该情况 的联合分布概率 ? 配分函数:所有分配方案的测度总和 对数线性模型 ? 对数线性模型:马尔可夫网络常表示为该模型,通过引入 特征函数 ? 配分函数: 将每个团的势函数表示为指数函数,指数项为对应团的加权特征量 Markov逻辑网的独立性 Pairwise Markov Property: 给定所有其他变量,任意两个不相邻变量条 件独立. Local Markov Property:一个变量如果给定所有邻居变量后与所有其他 变量条件独立. Global Markov Property:A、B两个子集间任何一条路径都经过子集S, 则给定S后,A、B两个子集相互条件独立. 一个无向图G=(V, E),是马尔可夫网络的充分必要条件是: 当且仅当其满足以上三条独立性质. 构建马尔可夫网络 ? 方法一:基于Pairwise Markov Property ? 如果满足下面条件,则在X和Y之间加边;

? 方法二:基于Local Markov Property ? 集合U是X的马尔可夫毯(Markov blanket,X的邻居节点集合),给定U,X独立于余下的变量;

一个班上有四名同学,A、B、C、D,他们每次做作业都会 与其他人讨论,但是由于某种不明的原因,A和C、B和D从 不一起讨论.当老师上课讲错知识点时,每个学生有一定几 率自己发现这个错误,当他发现错误时有可能将这个发现告 诉自己讨论的对象.这时我们有了四个随机变量{A,B,C,D}, 他们取值为1时表示发现了错误,为0时表示未发现,我们可 以获得如下独立性质: (A⊥C|{B,D})、(B⊥D|{A,C}) 给定B,D后,A,C独立;

给定A,C后,B,D独立. 构造贝叶斯网络 ? 第一次尝试(假设变量序存在 因果) ? 不满足(B⊥D|{A,C}) ? 第二次尝试(假设B,D是A, C的因) ? 不满足(B⊥D|{A,C}) A C D B A C D B 构造马尔科夫网络 ? 将可能的节点之间连上无向边 ? 满足(A⊥C|{B,D}) 、(B⊥D|{A,C}) A C D B 马尔科夫逻辑网 一阶谓词演算:语义 表达式的真值依赖于常元、变元、谓词、函词到论域中的映 射;

在论域中关系的真假决定了相应表达式的真假. 闭谓词(ground predicate)为不包含变元的谓词. friends(X, Y) 例如: friends(george, susie) friends(george, kate) 一阶谓词演算:语义 一个可能世界(A Possible World):为每个可能的闭谓词指定真值. 可满足:一个一阶公式是可满足的,当且仅当该公式至少在一个 世界中为真. 一阶逻辑的推理:判断一个知识库中是否包含公式F,即F是否在 所有满足知识库的世界中为真. friends(X, Y) 例如: friends(george, susie) friends(george, kate) 在一阶逻辑知识库中:每个可能世界 必须满足知识库中的所有公式, 否则该世界不可能存在(发生概率为0) MLN起源 概率逻辑学习(Probabilistic Logic Learning, PLL): 关系逻辑表示、概率推理机制(不确定性处理)、机器学习和 数据挖掘,以获得关系数据中的似然模型 Markov逻辑网(Markov Logic Networks, MLNs): Markov网+一阶逻辑,其本质是 公式附加权值的一阶逻辑知识库 2004年,Richardson. Domingos, Kok, Singla Markov逻辑网 基本思想:将一阶逻辑的限制放松,即一个可能世界违反公式越多,其 发生的概率越小,但未必为0. 公式权重:表示公式限制强度的大小.权值越大,满足该公式世界的发 生概率与不满足该公式世界的发生概率之间的差越大. P(world)∝exp(∑可满足公式的权重) Markov逻辑网的定义 马尔科夫逻辑网L:是(Fi , wi)对的集合,其中 Fi代表一阶逻辑规则, wi是用一个实数表示权重;