第13章++知识图谱与知识推理

第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知识图谱•知识图谱(knowledgegraph)：实体和关系所构成的异质、有向图，是表征实体间语义关联的语义网络TomLyonBobFRParis−节点代表实体−边代表不同类型的关系(异质)−两个节点之间有边相连表明它们之间存在相应关系−边是有向的表明关系是非对称的知识图谱•三元组(triple/triplet)：也称事实(fact)，是最基本的知识存储方式，表现为(主语,谓词,宾语)形式TomLyonBobFRParis(Tom,BornInCity,Paris)(Tom,LivedInCity,Lyon)(Tom,Nationality,France)(Tom,ClassMates,Bob)(Paris,CityLocatedInCountry,France)(Lyon,CityLocatedInCountry,France)(Bob,BornInCity,Paris)知识图谱•三元组(triple/triplet)：也称事实(fact)，是最基本的知识存储方式，表现为(主语,谓词,宾语)形式TomLyonBobFRParisBornInCity(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)知识图谱•知识图谱的作用–知识图谱能够提供海量、有组织的知识体系，使机器语言认知、概念认知成为可能，进而为自然语言处理和理解相关任务提供技术支撑–知识图谱为海量无结构数据提供了结构化的存储方式，方便计算机储存和管理信息–知识图谱还能借助其图结构和海量知识，帮助学习和发现事物之间的关联规律，理解事物全貌知识图谱•研究现状及应用前景国际国内学术界工业界ReadtheWebResearchProjectatCarnegieMellonUniversityHighPerformanceKnowledgeBases中国教育合作项目RepresentingandReasoningKnowledge目录•13.1概述•13.2知识图谱构建•13.3知识图谱中的知识推理–13.3.1表示学习技术–13.3.2张量分解技术–13.3.3路经排序算法•13.4本章小结知识图谱构建•几种主流构建方式基于信息抽取自动创建大众协作编辑创建专家人工创建NELL专家人工创建•典型代表：WordNet[Miller,1995]•方法优点–知识的准确性高–知识的完备性高，较少出现知识缺失问题•方法缺点–人力和时间成本极高–知识的覆盖面有限，知识图谱的规模有限–知识的实时更新较难，滞后性严重大众协作编辑创建•典型代表：Freebase[Bollackeretal.,2008],Wikidata•方法优点–知识的准确性较高–知识的覆盖面广，知识图谱的规模大•方法缺点–人力和时间成本较高–知识的完备性较差，知识缺失现象较为普遍–知识的实时更新较难，滞后性严重基于信息抽取自动创建•典型代表：NELL[Carlsonetal.,2010],YAGO[Suchaneketal.,2007]–指定关系类型，通过人工标注的种子知识，自动实现关系抽取•方法优点–人力和时间成本较低–知识的覆盖面广，知识图谱的规模大–知识的实时更新较为容易•方法缺点–依赖众多NLP任务，错误累积问题严重，知识准确性较低–知识的完备性较差，知识缺失现象较为普遍目录•13.1概述•13.2知识图谱构建•13.3知识图谱中的知识推理–13.3.1表示学习技术–13.3.2张量分解技术–13.3.3路经排序算法•13.4本章小结知识推理•知识推理(knowledgeinference)：根据知识图谱中已有的知识，推断出新的、未知的知识TomLyonBobFRParis(Tom,BornInCity,Paris)(Tom,LivedInCity,Lyon)(Tom,Nationality,France)(Tom,ClassMates,Bob)(Paris,CityLocatedInCountry,France)(Lyon,CityLocatedInCountry,France)(Bob,BornInCity,Paris)(Bob,Nationality,France)Nationality知识推理•知识推理(knowledgeinference)：根据知识图谱中已有的知识，推断出新的、未知的知识TomLyonBobFRParis(Tom,BornInCity,Paris)(Tom,LivedInCity,Lyon)(Tom,Nationality,France)(Tom,ClassMates,Bob)(Paris,CityLocatedInCountry,France)(Lyon,CityLocatedInCountry,France)(Bob,BornInCity,Paris)(Bob,Nationality,France)Nationality提高知识的完备性，扩大知识的覆盖面知识推理方法•表示学习技术–TransE[Bordesetal.,2013],TransH[Wangetal.,2014],TransR[Linetal.,2015]•张量分解技术–RESCAL[Nickeletal.,2011],TRESCAL[Changetal.,2014]•路径排序算法–PRA[LaoandCohen,2010],CPRA[Wangetal.,2016]目录•13.1概述•13.2知识图谱构建•13.3知识图谱中的知识推理–13.3.1表示学习技术–13.3.2张量分解技术–13.3.3路经排序算法•13.4本章小结表示学习技术•核心思想–将符号化的实体和关系在连续向量空间进行表示–简化操作与计算的同时最大程度保留原始的图结构•基本流程–将实体和关系在隐式向量空间进行表示（向量/矩阵/张量）–定义打分函数，衡量每个三元组成立的可能性–根据观测三元组构造优化问题，学习实体和关系的表示TransE模型•位移假设(translationassumption)：–China–Beijing=France–Paris=capital-of–Beijing+capital-of=China–Paris+capital-of=FranceTransE实体表示：向量𝐞𝑖关系表示：向量𝐫𝑘位移操作：𝐞𝑖+𝐫𝑘≈𝐞𝑗三元组打分：𝑓𝑒𝑖,𝑟𝑘,𝑒𝑗=𝐞𝑖+𝐫𝑘−𝐞𝑗1𝐞𝑖+𝐫𝑘≈𝐞𝑗TransE模型•实体和关系的向量空间表示–实体：向量𝐞∈ℝ𝑑–关系：向量𝐫∈ℝ𝑑•打分函数定义–距离模型：𝑓𝑒𝑖,𝑟𝑘,𝑒𝑗=𝐞𝑖+𝐫𝑘−𝐞𝑗1𝑓𝑒𝑖,𝑟𝑘,𝑒𝑗=+−𝑒𝑖,𝑟𝑘,𝑒𝑗TransE模型•优化问题构造–观测三元组（正例）得分𝑓𝑒𝑖,𝑟𝑘,𝑒𝑗–相应未观测三元组（负例）得分𝑓𝑒𝑖′,𝑟𝑘,𝑒𝑗′–排序损失：若正负例得分差距大于给定阈值𝛿，损失为零；否则损失大于零–排序损失最小化：正负例得分差距尽可能大min𝐞𝑖,𝐫𝑘��𝛿+𝑓𝑒𝑖,𝑟𝑘,𝑒𝑗−𝑓𝑒𝑖′,𝑟𝑘,𝑒𝑗′+𝑡−∈𝒩𝑡+𝑡+∈𝒪TransE模型TransE模型拓展•动机：弥补TransE在自反/多对一/一对多型关系上的不足–自反型关系：𝑒𝑖,𝑟𝑘,𝑒𝑗∈𝒪,𝑒𝑗,𝑟𝑘,𝑒𝑖∈𝒪–多对一型关系：∀𝑖∈1,⋯,𝑛,𝑒𝑖,𝑟𝑘,𝑒𝑗∈𝒪–一对多型关系：∀𝑗∈1,⋯,𝑚,𝑒𝑖,𝑟𝑘,𝑒𝑗∈𝒪𝐞𝑖+𝐫𝑘−𝐞𝑗=𝟎,𝐞𝑗+𝐫𝑘−𝐞𝑖=𝟎⇒𝐫𝑘=𝟎,𝐞𝑖=𝐞𝑗𝐞𝑖+𝐫𝑘−𝐞𝑗=𝟎,∀𝑖∈1,⋯,𝑛⇒𝐞1=𝐞2=⋯=𝐞𝑛𝐞𝑖+𝐫𝑘−𝐞𝑗=𝟎,∀𝑗∈1,⋯,𝑚⇒𝐞1=𝐞2=⋯=𝐞𝑚TransH和TransR模型•解决方案：同一实体在不同关系下有不同的表示–TransH：关系专属超平面(relation-specifichyperplanes)–TransR：关系专属投影矩阵(relation-specificprojectionmatrices)TransHTransRTransH模型•实体和关系的向量空间表示–实体：向量𝐞∈ℝ𝑑–关系：位移向量𝐫∈ℝ𝑑，超平面法向量𝐰∈ℝ𝑑•打分函数定义–头实体投影：𝐞⊥𝑖=𝐞𝑖−𝐰𝑘𝑇𝐞𝑖𝐰𝑘–尾实体投影：𝐞⊥𝑗=𝐞𝑗−𝐰𝑘𝑇𝐞𝑗𝐰𝑘–位移操作：𝐞⊥𝑖+𝐫𝑘≈𝐞⊥𝑗–距离模型：𝑓𝑒𝑖,𝑟𝑘,𝑒𝑗=𝐞𝑖−𝐰𝑘𝑇𝐞𝑖𝐰𝑘+𝐫𝑘−𝐞𝑗−𝐰𝑘𝑇𝐞𝑗𝐰𝑘1TransH模型•优化问题构造–观测三元组（正例）得分𝑓𝑒𝑖,𝑟𝑘,𝑒𝑗–相应未观测三元组（负例）得分𝑓𝑒𝑖′,𝑟𝑘,𝑒𝑗′–排序损失：若正负例得分差距大于给定阈值𝛿，损失为零；否则损失大于零–排序损失最小化：正负例得分差距尽可能大min𝐞𝑖,𝐫𝑘��𝛿+𝑓𝑒𝑖,𝑟𝑘,𝑒𝑗−𝑓𝑒𝑖′,𝑟𝑘,𝑒𝑗′+𝑡−∈𝒩𝑡+𝑡+∈𝒪TransR模型•实体和关系的向量空间表示–实体：向量𝐞∈ℝ𝑑–关系：位移向量𝐫∈ℝ𝑑，投影矩阵𝐌∈ℝ𝑑×𝑑•打分函数定义–头实体投影：𝐞⊥𝑖=𝐌𝑘𝐞𝑖–尾实体投影：𝐞⊥𝑗=𝐌𝑘𝐞𝑗–位移操作：𝐞⊥𝑖+𝐫𝑘≈𝐞⊥𝑗–距离模型：𝑓𝑒𝑖,𝑟𝑘,𝑒𝑗=𝐌𝑘𝐞𝑖+𝐫𝑘−𝐌𝑘𝐞𝑗1TransR模型•优化问题构造–观测三元组（正例）得分𝑓𝑒𝑖,𝑟𝑘,𝑒𝑗–相应未观测三元组（负例）得分𝑓𝑒𝑖′,𝑟𝑘,𝑒𝑗′–排序损失：若正负例得分差距大于给定阈值𝛿，损失为零；否则损失大于零–排序损失最小化：正负例得分差距尽可能大min𝐞𝑖,𝐫𝑘��𝛿+𝑓𝑒𝑖,𝑟𝑘,𝑒𝑗−𝑓𝑒𝑖′,𝑟�