知识图谱-第9章-知识推理

第九章：知识推理《知识图谱》配套讲义1提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结2提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结3作为知识载体的知识图谱物理世界人类世界机器世界能理解言外之意；能创造新说法和新语法；语言系统语言理解与语言生成知识图谱能不能举一反三，自动发现新知识？知识表示与知识推理4作为认知智能重要基础的知识图谱知其然的AI

vs

知其所以然的AI人的大脑依赖所学的知识进行思考、逻辑推理、理解语言知识图谱感知识别判断思考推理生成深度学习学习有智慧的AI有知识的AI推理5基于知识的Agent人类认识世界，这种认识能帮助我们做事。也称认识论、知识论，相对应的是行为论。---认知论人类一直强调人的智能是如何获得的：不是靠反射机制而是对知识的内部表示进行操作的推理过程。---基于知识的Agent领域无关的算法特定领域的内容推理引擎知识库6知识推理示例：渡河背景：一个人带着一匹狼、一只羊和一捆卷心菜来到了河边。他需要过河，但是河边只有一条船，而且他只能带一样东西上船。他不能把狼和羊一起留在河边，也不能让羊和卷心菜一起留在河边，因为在这两种情况下，前者都会吃掉后者。提问：如何用最少的渡河次数把所有东西都带到河对岸？

背景：狮子、老虎、熊三对动物过河，每种动物有妈妈和孩子两个（就是狮子妈妈、小狮子；老虎妈妈、小老虎；熊妈妈、小熊）。而小动物的妈妈不在的话，自己就会被吃掉（例如老虎妈妈不在，小老虎会被狮子妈妈或熊妈妈吃掉）。所有的妈妈都会划船，孩子里面只有小狮子会划船。一艘船上只能同时最多坐两个动物（可以是两个妈妈。提问：请问他们要如何过河才能保全所有的动物？7知识推理示例：Wumpus世界（1）来自书籍《ArtificialIntelligence:AModernApproach(4thEdition)》Wumpus世界是一个由多个房间组成并连接起来的山洞。在洞穴的某处隐藏着一只怪兽(Wumpus)，它会吃掉进入它房间的任何人。探险者(Agent)可以射杀怪兽，但是探险者只有一支箭。某些房间是无底洞，任何人漫游到这些房间都会被无底洞吞噬。生活在该环境下的唯一希望是存在发现一堆金子的可能性。性能度量：带着金子爬出洞口+1000，掉入洞被Wumpus吃-1000，采用一个行动-1，用掉箭-10。Agent死亡或出洞，则游戏结束。环境：4*4房间网格，始发[1,1]且向右。1个Wumpus，1/5房间为无底洞，分布均匀。执行器：Agent向前、左转、右转、射箭。8知识推理示例：Wumpus世界（2）传感器：在与无底洞相邻的方格内，Agent能感知到微风（Breeze）；在与Wumpus相邻的方格内，Agent能感受到臭气（Stench）；在金子所处方格，Agent能感受到闪闪金光（Glitter）；当Agent碰到墙时，它感知到碰撞（Bump）；当Wumpus被杀死后，它发出的嚎叫声（Scream）。9知识推理示例：Wumpus世界（3）第1步感知：NONE[1,2]和[2,1]安全第2步感知：微风[2,2]或[3,1]洞

回到[1,1]然后去[1,2]10知识推理示例：Wumpus世界（4）第3步感知：臭气[1,3]怪兽和[2,2]安全

射杀怪兽,去往[2,2]第5步感知：臭气，闪光，微风[2,3]金子，[2,4]或[3,3]洞

拿金子,往回走11什么是推理（1）推理是逻辑学、哲学、心理学、人工智能等学科中的重要概念。早在古希腊时期，著名哲学家亚里斯多德就提出三段论作为现代演绎推理的基础。在计算机科学及人工智能领域，推理是一个按照某种策略从已知事实出发去推出结论的过程。推理就是通过已知知识推断出未知知识的过程。12什么是推理（2）推理，逻辑学中指思维的基本形式之一，是由一个或几个已知的判断（前提）推出新判断（结论）的过程，有直接推理、间接推理等。------《现代汉语词典第6版》事件必定有其原因，事件背后必定有其真相。通过推理可以预测未来，甚至确定未来发展的详细过程。任何一个推理都包含已知判断、新的判断和一定的推理形式。作为推理的已知判断叫前提，根据前提推出新的判断叫结论。前提与结论的关系是理由与推断，原因与结果的关系。13什么是推理（3）牛顿的出生地属于哪个国家已知知识：事实公理常识…未知知识：新事实新公理新常识…演绎、归纳、朔因预测、推断、类比14提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结15知识推理的分类归纳推理与演绎推理归纳推理(induction)：归纳是从特殊到一般的过程。所谓归纳推理，就是从一类事物的大量特殊事例出发，去推出该类事物的一般性结论。我们熟知的数学归纳法就是归纳推理的一个典型例子。前提：蓝鲸可以喷射水柱。抹香鲸可以喷射水柱。座头鲸可以喷射水柱。结论：鲸鱼都可以喷射水柱。前提：树木有年轮。乌龟有年轮（龟甲上的环数）。牛马有年轮（年轮在牙齿上）。结论：所有生物都有记录自己寿命长短的年轮。日本科学家发现，人的年轮在脑中。16知识推理的分类归纳推理与演绎推理演绎推理(deduction)：演绎是从一般到特殊的过程。所谓演绎推理，就是从一般性的前提出发，通过演绎（即推导），得出具体陈述或个别结论的过程。最经典的演绎推理就是三段论(syllogism)，它包括一个一般性原则（大前提）、一个附属于大前提的特殊化陈述（小前提），以及由此引申出的特殊化陈述符合一般性原则的结论。大前提：人工智能学院的学生都会PyTorch。小前提：小李是人工智能学院的学生。结论：小李会PyTorch。17知识推理的分类归纳推理与演绎推理演绎推理(deduction)：演绎推理不仅仅局限于三段论，也不只是从一般到特殊的过程。它有着强烈的演绎特性，重在通过利用每一个证据，逐步地推导到目标或以外的结论，多被用于数学物理证明、思维推导等各类应用。例：莎士比亚在《威尼斯商人》中，描写富家少女鲍西亚品貌双全，贵族子弟、公子王孙纷纷向她求婚。鲍西亚按照其父遗嘱，由求婚者猜盒订婚。鲍西亚有金、银、铅三个盒子，分别刻有三句话，其中只有一个盒子放有鲍西亚的肖像。求婚者中谁通过这三句话，最先猜中肖像放在哪个盒子里，谁就可以娶到鲍西亚。

金盒子上说：“肖像不在此盒中。”

银盒子上说：“肖像在铅盒中。”

铅盒子上说：“肖像不在此盒中。”鲍西亚告诉求婚者，上述三句话中，最多只有一句话是真的。如果你是一位求婚者，如何尽快猜中鲍西亚的肖像究竟放在哪一个盒子里？18知识推理的分类归纳推理与演绎推理的区别演绎推理是在已知领域内的一般性知识的前提下，求解一个具体问题或者证明一个结论的正确性。演绎推理得出的结论实际上早已蕴含在一般性知识的前提中，演绎推理只不过是将已有事实揭示出来，因此它不能增殖新知识。相反，归纳推理所推出的结论是没有包含在前提内容中的。这种由个别事物或现象推出一般性知识的过程，是增殖新知识的过程。19知识推理的分类必然性推理与或然性推理：必然性推理前提与结论有必然性联系，即前提蕴含结论。在必然性推理中，前提真而结论假是不可能的，即把对前提的肯定与对结论的否定结合起来就会产生矛盾。传统逻辑中通过直言命题变形的直接推理（换质法、换位法推理等）、通过命题间对应关系所进行的直接推理、三段论推理、各种假言推理、选言推理以及完全归纳推理等等，都属于必然性推理。20知识推理的分类必然性推理与或然性推理：或然性推理前提与结论无蕴含关系。或然性推理中，前提真而结论假并非完全不可能，将对前提的肯定与对结论的否定结合起来并不产生矛盾。简单枚举归纳推理、类比推理、回溯推理等等都属于或然性推理。例如，前提P只是结论C的“疑似”必要条件。P：房间里有物品

C：房子会着火21知识推理的分类单调推理与非单调推理：单调推理单调推理是指在推理过程中随着推理的向前推进以及新知识的加入，推出的结论呈单调增加的趋势并越来越接近最终目标，且在推理过程中不会出现反复的情况，即不会因新知识的加入而否定前面推出的结论，从而使推理又退回到前面的某一步。一般情况下考虑单调推理，大部分书籍和我们的课程都只考虑单调推理。22知识推理的分类单调推理与非单调推理：非单调推理非单调推理是指在推理过程中，由于新知识的加入，不仅没有加强已经推出的结论，反而要否定它，使其需要退回到之前步骤。通常是在知识不完备的情况下发生，该种情况下需要先做某些假设，并在此假设下进行推理；随着新知识的加入可能会发现原假设不正确。人们日常生活中很多推理都是非单调推理，例如，鸵鸟在原野上飞驰（默认以为所有鸟都会飞），只有看到它是奔跑，才能推断它不是在飞。23知识推理的分类缺省推理也称默认推理，它是在知识不完全的情况下作出的推理，通常的形式：如果没有足够的证据证明结论不成立，则认为结论是正确的。溯因推理也称反绎推理、反向推理，是推理到最佳解释的过程。它是开始于事实的集合，并推导出其最佳解释的推理过程。溯因（abduction）意味生成假设来解释观察或结论。24知识推理的分类确定性推理与不确定性推理：确定性推理确定性推理大多指确定性逻辑推理，它具有完备的推理过程和充分的表达能力，可以严格地按照专家预先定义好的规则准确地推导出最终结论。但是确定性推理很难应对真实世界中，尤其是存在于网络大规模知识图谱中的不确定甚至不正确的事实和知识。不确定的知识：“一个人和其父亲拥有同样的国籍”这条规则在现实生活中大部分情况下都是正确的，但也不排除移民、母方国籍等因素使得少量事实不满足它。不正确的事实：“美国的首都是纽约”这个事实是错误的，大规模知识图谱YAGO抽样统计中有5%左右的错误事实。25知识推理的分类确定性推理与不确定性推理：不确定性推理不确定性推理也被称为概率推理，是统计机器学习中一个重要的议题。它并不是严格地按照规则进行推理，而是根据以往的经验和分析，结合专家先验知识构建概率模型，并利用统计计数、最大化后验概率等统计学习的手段对推理假设进行验证或推测。不确定性推理可以有效建模真实世界中的不确定性。权重推理规则0.9∀𝑥,𝑦:(𝑥,child_of,𝑦)⇒(𝑦,parent_of,𝑥)0.8∀𝑥,𝑦,𝑧:

(𝑥,born_in,𝑦)⋀(𝑦,city_of,𝑧)⇒(𝑥,nationality,𝑧)0.5∀𝑥,𝑦,𝑧:

(𝑥,child_of,𝑧)⋀(𝑦,child_of,𝑧)⇒(𝑥,sister_of,𝑧)……26知识推理的分类逻辑推理和非推理推理逻辑推理：过程包含了严格的约束和推理过程（研究较多）。非逻辑推理：自然语言推理，推理过程相对模糊。符号推理与数值推理符号推理：符号推理的特点就是在知识图谱中的实体和关系符号上直接进行推理。确定性和不确定性逻辑推理都属于符号推理。数值推理：与符号推理相对的就是数值推理。数值推理就是使用数值计算，尤其是向量矩阵计算的方法，捕捉知识图谱上隐式的关联，模拟推理的进行。本课程介绍的数值推理方法一般指基于分布式知识表示的推理（神经网络方法）。27概括：推理方式及其分类参考书籍《知识表示与处理》推理方式按前提与结论的联系性质划分按新知识推出途径划分按知识确定性划分按推理过程单调性划分按实现技术划分演绎推理归纳推理朔因推理缺省推理必然性推理或然性推理确定性推理不确定性推理单调推理非单调推理基于符号演算的推理基于数值计算的推理28提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结29知识图谱补全不完备的知识图谱：实体缺失、事实缺失等对于世界中存在的2百多万部电影，DBpedia和Freebase中只分别记录了78万和26万部；在DBpedia和Freebase中，分别有40.7%和72.2%的人物没有记录“出生地”信息，有90.8%和75.5%的人物没有记录“国籍”信息。据统计，知识图谱DBpedia在2016年到2017年间，1年时间新增了近37万实体和146万事实。知识图谱补全：也称知识图谱上的链接预测，其本质是根据知识库中已有的知识推断出新的、未知的知识。知识库补全可以用来建立更全面的知识库，是知识库构建的重要手段之一。30知识问答基于知识推理的深度问答问答系统是自然语言处理领域一个重要的发展方向，通过自然语言的方式来获取知识。在很多真实应用场景下，问答系统能够带来极大的知识获取的便利性。但除了简单地检索实体，更多的问题要求问答系统具有知识推理的能力。基于知识推理的问答系统：如将TransE向量空间与搜索技术结合。或将知识推理等技术直接应用于问答系统：如用R-GCN来建模多轮对话问答系统的对话结构和背景知识。31搜索与推荐基于知识图谱的搜索搜索直达目标是搜索系统的核心需求。在知识图谱的支撑下，搜索系统越来越智能化，集中体现在对搜索意图的准确理解以及对搜索结果的精准匹配上。实体搜索主要分为搜索意图理解，目标查找，结果呈现和实体探索。例如，系统可以借助知识图谱，理解用户想搜索的是网球明星李娜，而不是歌星李娜，从而实现准确的意图理解。此外，还可以拓展搜索结果，呈现“李娜”的相关实体。在Google上还会显示“李娜”知识卡片。基于准确搜索意图理解的精确匹配扩展的搜索结果来自Google知识图谱的“李娜”知识卡片32提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结33演绎推理：推理具体事实34演绎推理：推理具体事实35提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结36逻辑推理/逻辑学（Logics）

37蕴含（Entailment）

38回到Wumpus世界[1,1]感知NONE[2,1]感知微风系统（Agent）想知道未探索的邻近房间[1,2][2,2][3,1]是否包含洞39Wumpus世界

40逻辑推理算法

41命题逻辑：语法命题逻辑是一种简单逻辑命题符号P、Q、R、P22等是语句IfSisasentence,

Sisasentence(negation/非)IfS1andS2aresentences,S1

S2isasentence(conjunction/合取)IfS1andS2aresentences,S1

S2isasentence(disjunction/析取)IfS1andS2aresentences,S1

S2isasentence(implication/蕴含)IfS1andS2aresentences,S1

S2isasentence(biconditional)42命题逻辑：语义

43逻辑等价（Logicalequivalence）如果在相同模型中真值相同，则两个语句是逻辑等价的：α≡βiffα╞βandβ╞α44有效性和可满足性

45推导与证明：基本推理规则假言推理规则（ModusPonens）:消去合取词（And-Elimination）:其他规则:46Wumpus世界的语句

47Wumpus世界的推理

48归结（Resolution）证明

P1,3

P2,2,

P2,2P1,349转换为合取范式（CNF）合取范式(ConjunctiveNormalForm,CNF)子句为合取式表达，每个子句为文字的析取式(A

B)

(B

C

D)如何转换为合取范式：以B1,1

(P1,2

P2,1)为例消去等价词

,

替换α

β为(α

β)

(β

α).(B1,1

(P1,2

P2,1))

((P1,2

P2,1)

B1,1)2.消去蕴含词

,替换α

β为

α

β.(

B1,1

P1,2

P2,1)

(

(P1,2

P2,1)

B1,1)3.将否定词

内移：使用deMorgan'srules和

double-negation.(

B1,1

P1,2

P2,1)

((

P1,2

P2,1)

B1,1)4.使用分配律，在可能的位置上将

对

进行分配.(

B1,1

P1,2

P2,1)

(

P1,2

B1,1)

(

P2,1

B1,1)50归结算法，归结推理/证明

第一行为合取范式，第二行为对第一行的归结结果51归结演绎推理示例请写出下面推理的证明过程事实：如果今天是下雨天，则要带雨伞或带雨衣。如果走路上班，则不带雨衣。问题：今天下雨，走路上班，所以带伞。进行如下定义：P:今天下雨；Q:带雨伞；R:带雨衣；S:走路上班。证明：将已知事实及问题用命题公式表示出来R1:如果今天是下雨天，则要带雨伞或带雨衣。命题公式：P(Q

R)合取范式：

P

QRR2:如果走路上班，则不带雨衣。命题公式：S

R合取范式：

S

RR3：今天下雨，走路上班，所以带伞。命题公式：P∧S

Q合取范式：

P

SQ结论取反：P

SQ参考书籍《知识表示与处理》归结过程：(1)

P

QR(2)

S

R(3)P(4)S(5)Q(6)

R---(2)与(4)(7)

P---(1)(5)与(6)(8)None---(3)与(7)52推理算法：前向链接和反向链接算法Horn形式（受限形式的一种）KB=Horn子句的合取Horn子句：至多只有一个正文字的析取式例如，¬L1,1

¬Breeze

B1,1,L1,1

Breeze

B1,1α1

…

αn

β

中

前的为前提（premise）,后的为结论（conclusion）对于Horn形式的假言推理：使用Horn子句的推理可以使用前向链接（forwardchaining）和反向链接（backwardchaining）算法这两种算法都很自然，易于理解，且是线性运行时间α1,…,αn, α1

…

αn

ββ53前向链接（Forwardchaining）基本思想：找到前件（premise）能够被KB满足的规则把推理结论添加到KB中，直到查询被发现Horn子句集合对应的AND–OR图54前向链接（Forwardchaining）主要步骤统计子句中未知前件的个数（计数）如果前件已知，则减去未知个数数量当数量为0时，结论作为已知事实添加到KB中为了避免冗余推理，还可记录推理结论55前向链接的完备性

56反向链接（Backwardchaining）基本思路：从查询Q反向工作检查Q是否已知，如果已知，则返回否则，检测能推导出Q的规则（rules），反复应用反向链接证明它们的前件（premises）需要避免循环：检查新的子目标1）是否已经被证明为真2）是否已经证明失败57前向链接vs.反向链接时间复杂度都是与KB的规模线性相关前向链接是数据驱动（data-driven）反向链接是任务驱动（goal-driven）前向链接算法可能生成很多与目标无关的结论一般来说，反向链接算法更适合用来解决具体问题反向链接算法的时间复杂度一般比KG的线性规模要小得多58提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结59基于产生式规则的推理产生式系统一种前向推理系统，可以按照一定机制执行规则从而达到某些目标典型应用：专家系统（如诊断感染性疾病的专家系统MYCIN）产生式系统的组成事实集合（WorkingMemory）产生式/规则集合推理引擎本节内容大部分参考书籍《知识图谱导论》控制策略规则集合推理引擎事实集合60基于产生式规则的推理事实集合/运行内存（WorkingMemory,WM）事实的集合用于存储当前系统中的所有事实事实描述对象，如(studentname:Aliceage:24)描述关系，如(olderThanJohnAlice)产生式集合(ProductionMemory,PM)产生式（推理规则）的集合产生式IFconditionsTHENactionsconditions是由条件组成的集合，又称为LHS（LeftHandSide）actions是由动作组成的序列，又称为RHS（RightHandSide)61产生式规则：LeftHandSideLHS条件（condition）的集合，各条件之间是且的关系当LHS中的所有条件均被满足，则该规则触发每个条件形如(typeattr1:spec1…

attrn:specn)speci表示对attri的约束，形式可取下面种类原子，如：Alice(personname:Alice)用于判断取值是否为Alice变量，如：x(personname:x)用于判断取值是否为x(如果未绑定常量，则视为自由变量）表达式，如[n+4]（personage:[n+4])用于判断取值是否等于（需事先赋值）布尔测试，如{>10}(personage:{>10})用于判断取值是否满足条件约束的与、或、非操作62产生式规则：RightHandSideRHS动作(action)的序列，执行时依次执行动作的种类如下：ADDpattern向事实集合WM中加入形如pattern的事实REMOVEi从事实集合WM中移除当前规则第i个条件匹配的事实MODIFYi(attrspec)对于当前规则第i个条件匹配的事实，将其对应于attr属性的值改为spec63产生式规则产生式规则IFconditionsTHENactions示例1：IF（Student姓名:XYZ）ThenADD(Person姓:X)如果有个学生名为XYZ，那么向事实集合中加入一个事实，表示有一个姓X的人。示例2（来自MYCIN专家系统，RULE047）：IF($AND(NotDefiniteCntxtIdent)#病原体的鉴别名不确定，且 (SAMECntxtSiteBlood)#病原体来自血液，且 (SAMECntxtStainGramneg)#病原体的染色是革兰氏阴性，且 (SAMECntxtMorphRod)#病原体的形态是杆状的，且 (SAMECntxtBurnt)#病原体呈褐色，且Then(CntxtIdentPseudomonasTally.4)#病原体的鉴别名是假单胞细菌，可信度为0.464推理引擎该步骤是产生式系统的核心，用于控制系统的执行模式匹配用规则的条件部分匹配事实集中的事实，整个LHS都被满足的规则被触发，并被加入议程(agenda)冲突消解按一定的策略从被触发的多条规则中选择一条规则执行执行被选择出来的规则的RHS，从而对WM进行一定的操作产生式系统=事实集合+产生式集合+推理引擎65产生式系统执行流程模式匹配产生式规则库WM(事实集合)冲突规则集推理控制冲突消解规则触发规则执行产生式系统的工作周期控制系统进行的一次推理过程从产生式规则库中取一条规则，将其前提同当前WM中的事实/数据进行模式匹配是否匹配成功把该规则的结论放入当前WM，或者执行规则所规定的动作是否66模式匹配：Rete算法Rete算法是产生式规则系统中常用的推理算法核心思想：将产生式规则中的LHS部分组织成判别网络，然后用分类的匹配项构造匹配网络，同时缓存中间结果。以空间换时间的做法Rete算法基本过程

网络用来检验和保存规则集合中每条规则所对应的条件集合。

网络用来保存Join计算的中间结果。WorkingMemory中的所有事实首先与

网络中的元素进行匹配，然后按照网络的结构形式完成Join操作，将Join的中间结果保存于

网络中，最终结果加入agenda中。67冲突消解解决冲突：匹配成功的规则可能不止一条从被触发的多条规则中选择一条注：在具体场景中，被触发的多条规则可全被执行常见策略随机选择：从被触发的规则中随机选择一条执行具体性（specificity）：选最具体的规则(studentname:x)…(studentname:xage:20)…新近程度(recency)：选择最近没有被触发的规则68提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结69基于元知识（规则）进行推理核心挑战：如何利用不确定性的元知识进行联合推理

5.0

儿子(X,Y)∧国籍(Y,Z)⇒国籍(X,Z)5.0

工作地(X,Y)∧国家(Y,Z)⇒国籍(X,Z)10.0

出生地(X,Y)∧国家(Y,Z)⇒国籍(X,Z)10.0

出生地(X,Y)∧语言(Y,Z)⇒母语(X,Z)70马尔可夫逻辑网马尔可夫逻辑网(MarkovLogicNetwork)[RichardsonandDomingos,2006]

是将概率图模型与一阶谓词逻辑相结合的一种统计关系学习模型，其核心思想是通过为规则绑定权重的方式将一阶谓词逻辑规则中的硬性约束（hardconstraints）进行软化。1）一阶谓词逻辑知识库可看作是在一个可能世界的集合上建立一系列硬性规则，即如果一个世界违反了其中的某一条规则，那么这个世界的存在概率即为零。2）马尔可夫逻辑网的基本思想是让那些硬性规则有所松弛，即当一个世界违反了其中的一条规则，那么这个世界存在的可能性将降低，但并非不可能。一个世界违反的规则越少，那么这个世界存在的可能性就越大。71马尔可夫逻辑网马尔可夫逻辑网(MarkovLogicNetwork)[RichardsonandDomingos,2006]

是将概率图模型与一阶谓词逻辑相结合的一种统计关系学习模型，其核心思想是通过为规则绑定权重的方式将一阶谓词逻辑规则中的硬性约束（hardconstraints）进行软化。3）为此，马尔可夫逻辑网给每条规则都加上一个特定的权重来反映其约束强度。规则的权重越大，其约束能力越强，即对于满足和不满足该规则的两个世界而言，它们之间的差异将越大。当规则的权重设置为无穷大时，其退化为硬性规则。72马尔可夫逻辑网绑定权重的规则示例这些规则在现实世界中通常是真的，但不总是真的，并且它们有着不同的成立概率。73马尔可夫逻辑网马尔可夫逻辑网形式化定义

74马尔可夫逻辑网

75马尔可夫逻辑网从马尔可夫逻辑网的定义出发，很容易得到一个图结构：每个原子事实对应于图中的一个节点。当两个节点所表示的原子事实出现在同一个实例化规则之中时，这两个节点之间存在一条边。所有出现在同一个实例化规则之中的原子事实组成了一个团。76马尔可夫逻辑网从马尔可夫逻辑网的定义出发，很容易得到一个图结构：每个原子事实对应于图中的一个节点。当两个节点所表示的原子事实出现在同一个实例化规则之中时，这两个节点之间存在一条边。所有出现在同一个实例化规则之中的原子事实组成了一个团。

77马尔可夫逻辑网从马尔可夫逻辑网的定义出发，很容易得到一个图结构：每个原子事实对应于图中的一个节点。当两个节点所表示的原子事实出现在同一个实例化规则之中时，这两个节点之间存在一条边。所有出现在同一个实例化规则之中的原子事实组成了一个团。

事实集合（世界空间）Sm(A)Sm(B)Ca(A)Ca(B)Fr(A,A)Fr(A,B)Fr(B,A)Fr(B,B)78马尔可夫逻辑网从马尔可夫逻辑网的定义出发，很容易得到一个图结构：每个原子事实对应于图中的一个节点。当两个节点所表示的原子事实出现在同一个实例化规则之中时，这两个节点之间存在一条边。所有出现在同一个实例化规则之中的原子事实组成了一个团。

事实集合（世界空间）Sm(A)Sm(B)Ca(A)Ca(B)Fr(A,A)Fr(A,B)Fr(B,A)Fr(B,B)79马尔可夫逻辑网从马尔可夫逻辑网的定义出发，很容易得到一个图结构：每个原子事实对应于图中的一个节点。当两个节点所表示的原子事实出现在同一个实例化规则之中时，这两个节点之间存在一条边。所有出现在同一个实例化规则之中的原子事实组成了一个团。

事实集合（世界空间）Sm(A)Sm(B)Ca(A)Ca(B)Fr(A,A)Fr(A,B)Fr(B,A)Fr(B,B)80马尔可夫逻辑网从马尔可夫逻辑网的定义出发，很容易得到一个图结构：每个原子事实对应于图中的一个节点。当两个节点所表示的原子事实出现在同一个实例化规则之中时，这两个节点之间存在一条边。所有出现在同一个实例化规则之中的原子事实组成了一个团。

命题集合（一个世界）81马尔可夫逻辑网

Sm(A)Sm(B)Ca(A)Ca(B)Fr(A,A)Fr(B,B)Fr(A,B)Fr(B,A)L1L2logit0000110000011100

00101100001111000100111101011111……………………………10101111221.5*2+1.1*211111111241.5*2+1.1*4

82马尔可夫逻辑网研究任务利用马尔可夫逻辑网对知识图谱进行建模后，我们可以：当规则及其权重已知时：推断知识图谱中任意未知事实成立的概率（马尔可夫随机场的推断问题）证据变量为知识图谱中的已知事实，问题变量为未知事实当规则已知但其权重未知时：自动学习每条规则的权重（马尔可夫随机场的参数学习）当规则及其权重均未知时：自动学习规则及其权重（马尔可夫随机场的结构学习），这实际上属于我们讨论过的归纳推理的范畴83扩展阅读84概率软逻辑

85概率软逻辑一阶谓词逻辑真值表松弛版本的逻辑联结词操作及不确定性规则建模1101111100100001110100010011成立当且仅当86概率软逻辑概率软逻辑建模示例不确定性规则不确定性事实规则实例建模87概率软逻辑

88概率软逻辑研究任务利用概率软逻辑对知识图谱进行建模后，我们可以：当规则及其权重已知时：推断知识图谱中任意未知事实成立的概率（马尔可夫随机场的推断问题）证据变量为知识图谱中的已知事实，问题变量为未知事实当规则已知但其权重未知时：自动学习每条规则的权重（马尔可夫随机场的参数学习）当规则及其权重均未知时：自动学习规则及其权重（马尔可夫随机场的结构学习），这实际上属于我们讨论过的归纳推理的范畴89提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结90演绎推理：应用推理规则91归纳推理：学习推理规则92推理规则

93推理规则概述

94提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结95归纳逻辑程序设计归纳逻辑程序设计（InductiveLogicProgramming,ILP）使用一阶谓词逻辑来进行知识表示，通过修改和扩充逻辑表达式来完成对数据的归纳。

背景知识样例

96FOIL算法

97FOIL算法

从一般到特殊：逐步向规则体添加约束，直至其不覆盖任何反例

98FOIL算法

99FOIL算法示例

背景知识样例2.00-0.420.58-0.42NANANANANANA100FOIL算法示例

背景知识样例2.00-0.420.58-0.42NANANANANANA

101FOIL算法示例

背景知识样例-0.420.58-0.42NANANANANANA

102FOIL算法示例

背景知识样例-0.420.58-0.42NANANANANANA

103传统ILP问题VS知识图谱传统ILP问题：谓词可以是多元的计算冗余且复杂度较高需要目标谓词的正例与反例封闭世界假设（ClosedWordAssumption）所有未声明是正例的样本全都是反例知识图谱：谓词几乎都是二元的谓词规模大、样例数量多知识图谱一般不显式表示谓词的反例开放世界假设（OpenWordAssumption）未声明是正例的样本既可以是反例，也可以是未知类别的样本104扩展阅读：NeuralLogicMachinesNeuralLogicMachine(NLM),aneural-symbolicarchitectureforbothinductivelearningandlogicreasoning.

105提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结106知识图谱中规则与关系路径知识图谱中包含的仅仅是实体间的二元关系，因此规则与知识图谱中的关系路径存在对应关系。

107路径排序算法PRA(PathRankingAlgorithm)[Laoetal.,2011]

以实体间的路径作为特征，来学习目标关系的分类器。

RandomWalkInferenceandLearningina

largescaleKnowledgeBase,EMNLP2011.108路径排序算法PRA工作流程特征抽取：生成并选择路径特征集合特征计算：计算每个训练样例的特征值分类器训练：根据训练样例，为每个目标关系训练一个分类器TomLyonBobFRParisLivedInCityNationalityCityLocatedInCountryBornInCityClassMatesCityLocatedInCountryBornInCity109路径排序算法PRA工作流程特征抽取：随机游走，广度优先搜索，深度优先搜索特征计算：随机游走概率，布尔值（出现/不出现），出现频次/频率分类器训练：单任务学习：为每个关系单独训练一个二分类分类器多任务学习：将不同关系进行联合学习，同时训练它们的分类器110路径排序算法PRA规则学习：根据分类器权重自动挖掘并筛选可靠规则PRA在Freebase上挖掘出的规则111PRA挖掘路径和规则112PRA进行关系推理实验效果113提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结114规则学习评估方法

115AMIE：不完备知识库中的关联规则挖掘AMIE

(AssociationRuleMiningunderIncompleteEvidence)[Galárragaetal.,2013]

支持从不完备的知识库中，挖掘闭式（closed）规则。两个谓词共享一个变量或实体，则称其为连通的。规则中任意两个谓词可通过连通关系的传递性相连，则称该规则为连通的。规则是连通的并且其中的变量都至少出现两次，则称其为闭式（closed）逻辑规则。116AMIE：不完备知识库中的关联规则挖掘AMIE依次学习预测每种关系的规则。对于每种关系，从规则体为空的规则开始，通过三种操作扩展规则体部分，保留支持度大于阈值的候选（闭式）规则。添加悬挂边(AddDanglingAtom)：悬挂边是指边的一端是一个未出现过的变量，而另一端（变量或常量）是在规则中出现过的。添加实例边(AddInstantiatedAtom)：实例边与悬挂边类似，边的一端也是在规则中出现过的变量或常量，但另一端是未出现过的常量，也就是知识库中的实体。添加闭合边(AddClosingAtom)：闭合边则是连接两个已经存在于规则中的元素（变量或常量）的边。117AMIE：不完备知识库中的关联规则挖掘AMIE工作流程示意

118AMIE：不完备知识库中的关联规则挖掘AMIE规则评估支持度(support)：同时符合规则体和规则头的实例数目置信度(confidence)：支持度除以仅符合规则体的实例数目119AMIE：不完备知识库中的关联规则挖掘AMIE规则评估支持度(support)：同时符合规则体和规则头的实例数目置信度(confidence)：支持度除以仅符合规则体的实例数目封闭世界假设(ClosedWorldAssumption)：知识库中不存在的事实都是错误的120AMIE：不完备知识库中的关联规则挖掘

/~weblt/pikm2014/slides/Luis-Galarraga-applications-rule-mining.pdf121AMIE：不完备知识库中的关联规则挖掘

应该算反例不应该算反例122AMIE：不完备知识库中的关联规则挖掘AMIE规则评估支持度(support)：同时符合规则体和规则头的实例数目置信度(confidence)：支持度除以仅符合规则体的实例数目PCA置信度(PCAconfidence)：123AMIE：不完备知识库中的关联规则挖掘只要存在一个不是y的才可算数124AMIE：不完备知识库中的关联规则挖掘AMIE在YAGO上挖掘出的规则http://resources.mpi-inf.mpg.de/yago-naga/amie/data/yago2/amie_yago2_2.html125相关工作：基于表示学习获取推理规则

Embeddingentitiesandrelationsforlearningandinferenceinknowledgebases,ICLR2015.126提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结127知识图谱的数值表示（向量化表示）把知识库中的实体和关系表示为低维空间的对象（向量）及其它们的操作（空间转换）；该表示能够蕴涵其在知识库中的性质，即具有类似上下文的对象，在低维空间中更接近。第j

个实体第i

个实体第k

个关系事实集合

学习实体和关系的低维表示

事实推理表示学习技术：从原始数据中学习概念的潜在表示128分布式知识表示分布式知识表示（KnowledgeGraphEmbedding）的核心思想是将符号化的实体和关系在低维连续向量空间进行表示，在简化计算的同时最大程度保留原始的图结构。基本步骤：实体关系表示：定义实体和关系在向量空间中的表示形式（向量/矩阵/张量）。打分函数定义：定义打分函数，衡量每个三元组成立的可能性。表示学习：构造优化问题，学习实体和关系的低维连续向量表示。129位移距离模型代表性方法：TransE及其变种目标：头尾实体表示之差与关系表示一致headentity+relation=tailentityChina–Beijing=France–Paris=capital-ofBeijing+capital-of=ChinaParis+capital-of=France130语义匹配模型代表性方法：RESCAL及其变种直接根据三元组头尾实体和关系的表示定义计算函数matching(relation,composition(head,tail))头尾实体和关系都为向量逐位相乘并累加得到事实打分头尾实体和关系都为向量间隔位置相乘并累加得到事实打分头尾实体为向量，关系为矩阵头实体与矩阵相乘然后与尾实体计算内积得到事实打分131融合多元化信息的分布式知识表示上述分布式知识表示方法仅用到了知识图谱中的三元组信息，还有多种其他类型的信息也被证实能够提升分布式知识表示的效果。实体类别关系路径实体描述文本逻辑规则…/xinguoxia/KGE132提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结133DeepPath：基于强化学习的推理PRA算法的升级版，利用强化学习（RL）学习路径（paths）将知识图谱推理简化为一个“事实判断”（FactPrediction）事实判断即确定一个三元组（h,r,t）是否成立寻找一条能链接已知头实体h和尾实体的路径，并将此问题建模为序列决策问题。训练基于策略梯度的强化学习方法搜索路径。需要事先编码KG，使用TransE等传统方法预训练KGDeepPath:AReinforcementLearningMethodforKnowledgeGraphReasoning,EMNLP2017.134DeepPath模型示意图

135DeepPath效果：关系预测对于每个三元组，使用PRA得到TopK结果，来得到训练和测试样本的负样本（即替换掉真实三元组中的t为t’）。判断真实的(h,r,t)是否得分最高136DeepPath学习得到的路径样例137基于强化学习的查询问答把知识推理定义为查询问题任务<ColinKaepernick,PlaysInLeague,?>无法“预知”答案对应的尾实体（更符合真实场景）需要尽可能避免遍历大规模知识图谱（影响算法效率）GoforaWalkandArriveattheAnswer:ReasoningOverPathsinKnowledgeBasesusingReinforcementLearning,ICLR2018.138MINERVA模型

139MINERVA模型

140MINERVA模型的实验结果事实预测效果（与DeepPath的比较）链接预测（无性能优势）141提纲知识推理概述什么是推理推理方式及分类知识推理典型应用演绎推理：推理具体事实经典逻辑推理基于产生式规则的推理基于概率逻辑学习的推理归纳推理：学习推理规则归纳推理概述归纳逻辑程序设计路径排序算法（PRA算法）关联规则挖掘算法（AMIE算法）知识图谱推理新进展基于表示学习的知识图谱推理基于强化学习的知识图谱推理符号规则与表示学习相融合的知识图谱推理总结142推理模式人类进行推理时，往往呈现出以下两个特点：考虑尽可能多的因素，全局推理。实际中，考虑的影响因素越全面，就越有可能得到正确的推理结论。人的智能表现在可以利用潜在的推理模式，而这些推理模式难以穷举。有些事物之间虽然没有呈现出显式的联系，但有可能存在尚未探知的隐式规律。143符号推理VS.数值推理之前介绍的几种归纳和演绎推理方法都属于符号推理的范畴，即在知识图谱中的实体和关系符号上直接进行推理。与符号推理相对的就是数值推理，即使用数值计算，尤其是向量矩阵计算的方法，捕捉知识图谱上隐式的关联，模拟推理的进行。基于分布式知识表示的推理就是典型的数值推理方法。捕捉实体和关系之间的隐式关联分布式空间映射对特征间的复杂关系进行了解耦，减少了维数灾难问题（curseofdimensionality）使符号数据可以直接参与运算且计算速度非常快144符号推理与分布式表示推理的比较符号表示分布式表示表示方法离散符号连续的数值推理范围局部全局推理的精确性高较低效率小规模高，大规模低高是否易被人理解容易困难与其他系统结合的难易程度难易跨领域难（需专家设计种子规则）易知识推理：融合之道融合符号表示和分布式表示的知识推理145SystemIvs.SystemIIReasoningSystemI感知能力，如识别图像中的对象等高效推理（Fast）例如，KnowledgeGraphEmbedding（得到分布式向量表示）SystemII认知能力，涉及逻辑推理和规划严谨推理（Slow）例如，MarkovLogicNetwork（根据周围事实的标签进行逻辑推理）146IterE模型知识图谱

挖掘规则

推理事实

补充知识图谱知识图谱

表示学习

规则约束

推理知识AxiomInduction（计算规则权重）IterativelyLearningEmbeddingsandRulesforKnowledgeGraphReasoning,WWW2019.147IterE模型148SoLE模型规则实例化将规则中变量替换成知识实例后的结果对（实例化的）规则进行数值约束EnhancedKnowledgeGraphEmbeddingbyJointlyLearningSoftRulesandFacts,Algorithms2019.149SoLE模型简单事实建模：输入事实得到概率得分（0-1）组合知识建模：与、或、非、蕴含基于规则的约束EnhancedKnowledgeGraphEmbeddingbyJointlyLearningSoftRulesandFacts,Algorithms2019.规则的fp置信度150推理规则与表示学习相融合IterE模型优点：可以迭代地学习规则置信度和推理缺点：需要人工定义公理模板，直接加入的事实包含大量的噪声SoLE模型优点：利用AMIE挖掘的高质量规则缺点：缺乏持续学习的能力，同样规则推理会引入部分噪声，规则实例数量组合爆炸151神经符号逻辑推理马尔可夫逻辑网结合一阶逻辑和概率图模型

152马尔可夫逻辑网

表示学习的优缺点优点：可以通过随机梯度下降高效训练链接预测高召回率缺点：难以利用领域知识（逻辑规则）153pLogicNet模型将马尔可夫逻辑网络和表示学习结合起来用马尔可夫逻辑网络定义事实的联合分布使用变分EM