第13章知识图谱与知识推理王泉中国科学院大学网络空间安全学院2016年11月•13.1概述•13.2知识图谱构建•13.3 知识图谱中的知识推理–13.3.1 表示学习技术–13.3.2 张量分解技术–13.3.3 路经排序算法•13.4 本章小结•13.1概述•13.2知识图谱构建•13.3 知识图谱中的知识推理–13.3.1 表示学习技术–13.3.2 张量分解技术–13.3.3 路经排序算法•13.4 本章小结实体和关系•实体 (entity)：现实世界中可区分、可识别的事物或概念–客观对象：人物、地点、机构–抽象事件：电影、奖项、赛事•关系 (relation)：实体和实体之间的语义关联–BornInCity, IsParentOf, AthletePlaysForTeam•知识图谱 (knowledge graph)：实体和关系所构成的异质、有向图，是表征实体间语义关联的语义网络−节点代表实体−边代表不同类型的关系 (异质) −两个节点之间有边相连表明它们之间存在相应关系 −边是有向的表明关系是非对称的•三元组 (triple/triplet)：也称事实 (fact)，是最基本的知识存储方式，表现为(主语, 谓词, 宾语)形式(Tom, BornInCity, Paris)(Tom, LivedInCity, Lyon)(Tom, Nationality, France) (Tom, ClassMates, Bob)(Paris, CityLocatedInCountry, France) (Lyon, CityLocatedInCountry, France) (Bob, BornInCity, Paris)•三元组 (triple/triplet)：也称事实 (fact)，是最基本的知识存储方式，表现为(主语, 谓词, 宾语)形式BornInCity(Tom,Paris) LivedInCity(Tom,Lyon) Nationality(Tom,France) ClassMates(Tom,Bob) CityLocatedInCountry(Paris,France) CityLocatedInCountry(Lyon,France) BornInCity(Bob,Paris)谓词逻辑/一阶逻辑表达式•模式 (schema)：除三元组以外的高级知识形式–实体语义类别间的从属关系•(Athlete, SubclassOf, Person)•(City, SubclassOf, Location)•(Country, SubclassOf, Location)–关系的定义域(domain)和值域(range)•(AthletePlaysForTeam, Domain, Athlete)•(AthletePlaysForTeam, Range, SportTeam)•(CityLocatedInCountry, Domain, City)•(CityLocatedInCountry, Range, Country)•知识图谱的作用–知识图谱能够提供海量、有组织的知识体系，使机器语言认知、概念认知成为可能，进而为自然语言处理和理解相关任务提供技术支撑–知识图谱为海量无结构数据提供了结构化的存储方式，方便计算机储存和管理信息–知识图谱还能借助其图结构和海量知识，帮助学习和发现事物之间的关联规律，理解事物全貌•研究现状及应用前景国际Read the WebResearch Project at Carnegie Mellon University中国教育合作项目Representing and Reasoning Knowledge目录•13.1概述•13.2知识图谱构建•13.3 知识图谱中的知识推理–13.3.1 表示学习技术–13.3.2 张量分解技术–13.3.3 路经排序算法•13.4 本章小结知识图谱构建•几种主流构建方式NELL专家人工创建•典型代表：WordNet [Miller, 1995]•方法优点–知识的准确性高–知识的完备性高，较少出现知识缺失问题•方法缺点–人力和时间成本极高–知识的覆盖面有限，知识图谱的规模有限–知识的实时更新较难，滞后性严重大众协作编辑创建•典型代表：Freebase [Bollacker et al., 2008], Wikidata •方法优点–知识的准确性较高–知识的覆盖面广，知识图谱的规模大•方法缺点–人力和时间成本较高–知识的完备性较差，知识缺失现象较为普遍–知识的实时更新较难，滞后性严重基于信息抽取自动创建•典型代表：NELL [Carlson et al., 2010], YAGO [Suchanek et al., 2007] –指定关系类型，通过人工标注的种子知识，自动实现关系抽取•方法优点–人力和时间成本较低–知识的覆盖面广，知识图谱的规模大–知识的实时更新较为容易•方法缺点–依赖众多NLP任务，错误累积问题严重，知识准确性较低–知识的完备性较差，知识缺失现象较为普遍目录•13.1概述•13.2知识图谱构建•13.3 知识图谱中的知识推理–13.3.1 表示学习技术–13.3.2 张量分解技术–13.3.3 路经排序算法•13.4 本章小结•知识推理 (knowledge inference)：根据知识图谱中已有的知识，推断出新的、未知的知识(Tom, BornInCity, Paris)(Tom, LivedInCity, Lyon)(Tom, Nationality, France) (Tom, ClassMates, Bob)(Paris, CityLocatedInCountry, France) (Lyon, CityLocatedInCountry, France) (Bob, BornInCity, Paris)(Bob, Nationality, France)•知识推理 (knowledge inference)：根据知识图谱中已有的知识，推断出新的、未知的知识(Tom, BornInCity, Paris)(Tom, LivedInCity, Lyon)(Tom, Nationality, France)(Tom, ClassMates, Bob)(Paris, CityLocatedInCountry, France)(Lyon, CityLocatedInCountry, France)(Bob, BornInCity, Paris)(Bob, Nationality, France)提高知识的完备性，扩大知识的覆盖面知识推理方法•表示学习技术–TransE [Bordes et al., 2013], TransH [Wang et al., 2014], TransR [Lin et al., 2015]•张量分解技术–RESCAL [Nickel et al., 2011], TRESCAL [Chang et al., 2014] •路径排序算法–PRA [Lao and Cohen, 2010], CPRA [Wang et al., 2016]目录•13.1概述•13.2知识图谱构建•13.3 知识图谱中的知识推理–13.3.1 表示学习技术–13.3.2 张量分解技术–13.3.3 路经排序算法•13.4 本章小结表示学习技术•核心思想–将符号化的实体和关系在连续向量空间进行表示–简化操作与计算的同时最大程度保留原始的图结构•基本流程–将实体和关系在隐式向量空间进行表示（向量/矩阵/张量）–定义打分函数，衡量每个三元组成立的可能性–根据观测三元组构造优化问题，学习实体和关系的表示•位移假设 (translation assumption)： –China – Beijing = France – Paris = <capital-of> –Beijing + <capital-of> = China–Paris + <capital-of> = FranceTransE实体表示：向量 e i关系表示：向量 r k 位移操作：e i +r k ≈e j三元组打分：f e i ,r k ,e j =e i +r k −e j 1e i +r k ≈e j•实体和关系的向量空间表示–实体：向量e∈ℝd–关系：向量r∈ℝd•打分函数定义–距离模型：f e i,r k,e j=e i+r k−e j1f e i,r k,e j=+−•优化问题构造–观测三元组（正例）得分 f e i ,r k ,e j –相应未观测三元组（负例）得分 f e i ′,r k ,e j ′ –排序损失：若正负例得分差距大于给定阈值 δ，损失为零；否则损失大于零–排序损失最小化：正负例得分差距尽可能大min e i ,r k ��δ+f e i ,r k ,e j −f e i ′,r k ,e j ′+t −∈N t +t +∈OTransE 模型拓展•动机：弥补TransE 在自反/多对一/一对多型关系上的不足 –自反型关系：e i ,r k ,e j ∈O ,e j ,r k ,e i ∈O –多对一型关系：∀ i ∈1,⋯,n ,e i ,r k ,e j ∈O –一对多型关系： ∀ j ∈1,⋯,m ,e i ,r k ,e j ∈Oe i +r k −e j =0,e j +r k −e i =0 ⇒r k =0,e i =e j e i +r k −e j =0,∀ i ∈1,⋯,n ⇒e 1=e 2=⋯=e n e i +r k −e j =0,∀ j ∈1,⋯,m ⇒e 1=e 2=⋯=e mTransH和TransR模型•解决方案：同一实体在不同关系下有不同的表示–TransH：关系专属超平面(relation-specific hyperplanes)–TransR：关系专属投影矩阵(relation-specific projection matrices)TransH TransR•实体和关系的向量空间表示–实体：向量e∈ℝd–关系：位移向量r∈ℝd，超平面法向量w∈ℝd•打分函数定义–头实体投影：e⊥i=e i−w k T e i w k–尾实体投影：e⊥j=e j−w k T e j w k–位移操作：e⊥i+r k≈e⊥j–距离模型：f e i,r k,e j e i−w k T e i w k+r k−e j−w k T e j w k1•优化问题构造–观测三元组（正例）得分 f e i ,r k ,e j –相应未观测三元组（负例）得分 f e i ′,r k ,e j ′ –排序损失：若正负例得分差距大于给定阈值 δ，损失为零；否则损失大于零–排序损失最小化：正负例得分差距尽可能大min e i ,r k ��δ+f e i ,r k ,e j −f e i ′,r k ,e j ′+t −∈N t +t +∈O•实体和关系的向量空间表示–实体：向量e∈ℝd–关系：位移向量r∈ℝd，投影矩阵M∈ℝd×d •打分函数定义–头实体投影：e⊥i=M k e i–尾实体投影：e⊥j=M k e j–位移操作：e⊥i+r k≈e⊥j–距离模型：f e i,r k,e j M k e i+r k−M k e j1TransR 模型•优化问题构造–观测三元组（正例）得分 f e i ,r k ,e j –相应未观测三元组（负例）得分 f e i ′,r k ,e j ′ –排序损失：若正负例得分差距大于给定阈值 δ，损失为零；否则损失大于零–排序损失最小化：正负例得分差距尽可能大min e i ,r k ��δ+f e i ,r k ,e j −f e i ′,r k ,e j ′+t −∈N t +t +∈O统一框架•相同的优化方式•不同的实体/关系表示方式和打分函数 min e i ,r k ��δ+f e i ,r k ,e j −f e i ′,rk ,e j ′+t −∈N t +t +∈O目录•13.1概述•13.2知识图谱构建•13.3 知识图谱中的知识推理–13.3.1 表示学习技术–13.3.2 张量分解技术–13.3.3 路经排序算法•13.4 本章小结张量分解技术•核心思想–将知识图谱表示成张量 (tensor) 形式，通过张量分解 (tensor factorization/decomposition) 实现对未知事实的判定•典型应用–链接预测：判断两个实体之间是否存在某种特定关系–实体分类：判断实体所属语义类别–实体解析：识别并合并指代同一实体的不同名称•张量表示–知识图谱 = 三阶张量X∈ℝn×n×m–n为实体数目，m为关系数目–x ijk=1 表示e i和e j之间存在关系r k •张量分解•实体解析–根据实体的向量表示计算其相似度TRESCAL模型•动机：解决输入张量高度稀疏所带来的过拟合问题–<capital-of>：头实体仅能为城市实体，尾实体仅能为国家实体•解决方案：子张量分解(sub-tensor factorization)目录•13.1概述•13.2知识图谱构建•13.3 知识图谱中的知识推理–13.3.1 表示学习技术–13.3.2 张量分解技术–13.3.3 路经排序算法•13.4 本章小结路径排序算法•问题定义•核心思想–以两个实体间的路径作为特征，来判断它们之间可能存在的关系•基本流程–特征抽取：生成并选择路径特征集合–特征计算：计算每个训练样例的特征值–分类器训练：根据训练样例，为每个关系训练一个二分类分类器PRA模型•核心思想：以路径作为特征训练关系专属分类器–路径：连接两个实体的关系序列•特征抽取–随机游走，广度优先搜索，深度优先搜索•特征计算–随机游走概率，布尔值（出现/不出现），出现频次/频率•分类器训练–单任务学习：为每个关系单独训练一个二分类分类器–多任务学习：将不同关系进行联合学习，同时训练它们的分类器•规则自动挖掘–根据分类器权重自动挖掘并筛选可靠规则目录•13.1概述•13.2知识图谱构建•13.3 知识图谱中的知识推理–13.3.1 表示学习技术–13.3.2 张量分解技术–13.3.3 路经排序算法•13.4 本章小结知识图谱•知识图谱 (knowledge graph)：实体和关系所构成的异质、有向图，是表征实体间语义关联的语义网络−节点代表实体−边代表不同类型的关系 (异质)−两个节点之间有边相连表明它们之间存在相应关系−边是有向的表明关系是非对称的知识图谱构建•几种主流构建方式NELL知识推理•知识推理 (knowledge inference)：根据知识图谱中已有的知识，推断出新的、未知的知识(Tom, BornInCity, Paris)(Tom, LivedInCity, Lyon)(Tom, Nationality, France)(Tom, ClassMates, Bob)(Paris, CityLocatedInCountry, France)(Lyon, CityLocatedInCountry, France)(Bob, BornInCity, Paris)(Bob, Nationality, France)提高知识的完备性，扩大知识的覆盖面•核心思想–将符号化的实体和关系在连续向量空间进行表示–简化操作与计算的同时最大程度保留原始的图结构•基本流程–将实体和关系在隐式向量空间进行表示（向量/矩阵/张量）–定义打分函数，衡量每个三元组成立的可能性–根据观测三元组构造优化问题，学习实体和关系的表示•相同的优化方式•不同的实体/关系表示方式和打分函数 min e i ,r k ��δ+f e i ,r k ,e j −f e i ′,r k,e j ′+t −∈N t +t +∈O张量分解技术•核心思想–将知识图谱表示成张量 (tensor) 形式，通过张量分解 (tensor factorization/decomposition) 实现对未知事实的判定路径排序算法•核心思想–以两个实体间的路径作为特征，来判断它们之间可能存在的关系•基本流程–特征抽取：生成并选择路径特征集合•随机游走，广度优先搜索，深度优先搜索–特征计算：计算每个训练样例的特征值•随机游走概率，布尔值（出现/不出现），出现频次/频率–分类器训练：根据训练样例，为每个关系训练一个二分类分类器•单任务学习：为每个关系单独训练一个二分类分类器•多任务学习：将不同关系进行联合学习，同时训练它们的分类器。