中国科技核心期刊      中国指挥与控制学会会刊     军事装备类重点期刊
Command Control and Simulation

Command Control and Simulation >

2020 , Vol. 42 >Issue 4: 8 - 12

DOI: https://doi.org/10.3969/j.issn.1673-3819.2020.04.002

Theory & Research

Survey of Knowledge Reasoning Based on Statistic

  • ZHAO Guo-qing ,
  • HE Jia-zhou ,
  • LI Yong-sheng ,
  • WANG Jing-shi
Expand
  • Jiangsu Automation Research Institute, Lianyungang 222061, China

Received date: 2019-10-16

  Revised date: 2019-12-03

  Online published: 2022-05-10

Fold

Abstract

As a key technology of Knowledge Graph(KG) construction, Knowledge Reasoning Technology aims to make up KG and correct wrong relationships in KG. Knowledge reasoning based on statistics has great advantages in the completion of the large knowledge graph, while can utilize the statistical laws followed by KG. This paper presents a systematic survey to knowledge reasoning technology based on statistics. It briefly introduces the concept of knowledge reasoning for KG. Then, it introduces existing knowledge reasoning technology from three aspects: relationship learning based on hidden features, relationship learning based on graph features and type reasoning based on entity distribution law. This paper also discusses the challenges and the future research direction of knowledge reasoning based on statistics.

Key words： knowledge graph; knowledge reasoning; statistical relationship learning; knowledge graph completion

Cite this article

ZHAO Guo-qing , HE Jia-zhou , LI Yong-sheng , WANG Jing-shi . Survey of Knowledge Reasoning Based on Statistic[J]. Command Control and Simulation, 2020 , 42(4) : 8 -12 . DOI: 10.3969/j.issn.1673-3819.2020.04.002

为了能充分利用异质多元、组织结构松散的互联网数据,从中获取有价值的知识,研究人员们做了大量的工作。Bernerslee等人[1]提出了语义网概念,用本体模型形式化表达Web数据信息中的隐含语义;W3C提出使用资源描述框架(RDF)和万维网本体语言(OWL)来规范化地描述网络资源[2]。2012年Google在此基础上提出了知识图谱概念[3],用以提升搜索引擎能力、增强用户体验。目前,知识图谱以其强大的语义处理能力和开放组织结构,已经成为人工智能领域的关键技术,也是当下研究的热点之一。
目前,已经出现了一大批可用的开放知识图谱,如YAGO[4-5]、Dbpedia[6]、NELL[7]、Freebase[8]等。这些知识图谱从大量数据资源中精炼出知识,并组织及管理知识库,为垂直搜索,问答系统等智能应用提供支持。然而不全面的数据来源使得这些知识图谱比较稀疏,大量实体间的关系未标注,甚至已标注关系中也存在错误,这就需要使用知识图谱补全技术补全知识图谱中缺失的知识,同时使用知识图谱去噪修正错误关系[9],主要采用的方法便是知识推理技术。

1 知识图谱中的知识推理

区别于传统意义上的推理,面向知识图谱的知识推理,是根据知识库中两个或两个以上的已有知识,通过各种方法推理出新知识的过程。由于知识图谱是以(头实体,关系,尾实体)事实三元组形式存储知识,故知识推理的任务主要是对实体预测或对实体间关系预测。
根据采用的方法不同,知识推理可分为基于逻辑的推理和基于统计的推理两大类。其中,基于逻辑的知识推理方法又可具体分为基于一阶谓词逻辑、基于描述逻辑和基于本体三种。一阶谓词逻辑以非结构化形式表达知识,将三元组化为一系列命题,其中头尾实体对应命题的个体,实体间关系对应命题的谓词,再根据设定好的逻辑规则与约束条件推理出新的命题(知识)。例如,由“A是B的父亲”和“B是C的父亲”,可推出“A是C的爷爷”。描述逻辑专门用来应对实体关系复杂的推理任务,通过知识库中的TBox与Abox将复杂问题简化为一致性检测问题[10]。基于本体的知识推理,则是利用SWRL等规则语言,在概念层次上进行推理。
基于逻辑的方法依靠专家先行给出确定的逻辑规则,再在此基础上进行推理,在小规模的知识图谱上取得了很高的精准度和解释性。然而为了适应信息技术的飞速发展,现在的开放知识图谱规模越来越大,包含的知识也横跨了越来越多的领域,单靠专家们一一设定逻辑规则效率太低。由此产生了基于统计的知识推理方法,利用知识图谱的统计规律,结合机器学习来进行推理。

2 基于统计的知识推理技术

知识图谱除了遵循一些确定性规则(如实体类型的传递性)外,还遵循一些统计规律:1)同质性,即具有相同特征的实体间更有可能有联系;2)可用块结构划分实体,同一个块的所有实体都与其他块的实体有相似关系[11];3)部分实体间依赖关系可能横跨多个不同三元组链与关系类型。基于统计的知识推理要充分利用知识图谱的这些统计规律,从现有知识库中学习新的知识。

2.1 基于隐特征的实体关系学习

2.1.1 建立数学模型

为学习实体及实体间关系,需要先建立起数学模型,将实体与关系转化为机器所能理解的形式。设知识图谱中所有实体的集合为 E = { e 1 , e 2 , … , e n },所有关系的集合为 R = { r 1 , r 2 , … , r m },则事实三元组可表示为 x i j k = e i , r k , e j,其中 i , j = 1,2 , … , n , k = 1,2 , … , m。
引入随机变量 y i j k ∈ 0,1表示三元组 x i j k的存在性, y i j k取1代表 x i j k存在,取0则表示 x i j k不存在。由 m * n 2 个 y i j k组成三阶张量 Y i j k ∈ 0,1 n × m × n,每个可能的 Y i j k都代表真实世界的一个可能实现。令 P ( Y i j k )为随机张量 Y i j k的联合分布函数,则基于统计的知识推理方法便是通过机器学习方法计算 P ( Y i j k )来达到预测事实三元组的目的。
例如,在假设随机变量 y i j k条件独立的情况下, P ( Y i j k )可定义为[12]
P ( Y i j k | D , C ) = ∏ i = 1 n ∏ j = 1 m ∏ k = 1 n B e r y i j k | σ f i j k ; C
其中D是E×R×E×{0,1}的一个子集,代表当前知识图谱,函数Ber(y|p)为伯努利分布函数。C为参数, σ x = 1 / ( 1 + e - x )为sigmoid函数, f i j k为事实三元组 x i j k的得分函数。
由此可见, P ( Y i j k )正相关于 f i j k,也即 f i j k可代表对三元组 x i j k存在的信心,得分越高, x i j k越有可能存在。事实上,不管 P ( Y i j k )表达式如何,总需要设计出一个与 P ( Y i j k )正相关的合适的得分函数 f i j k,这即是影响统计关系学习效率与准确度的关键。

2.1.2 RESCAL模型

针对知识图谱中关系域维度高、分布稀疏的特点,Nickel等人[13⇓-15]引入张量分解(Tensor Factorization)的方法,提出了RESCAL模型,通过模型的隐特征向量进行集体学习。他们认为实体的隐特征(Latent Feature)是影响实体间关系的关键,将各种不可被机器理解的实体用一个个隐特征向量表示后,可以方便地使用机器学习的方法来预测实体间的关系。
模型中设定 x i j k = e i , r k , e j的得分函数为
f i j k R E S C A L ∶ = l i T W k l j = ∑ a = 1 d ∑ b = 1 d w a b k l i a l j b
其中 l i = ( l i 1 , l i 2 , … , l i N ) T, l j = ( l j 1 , l j 2 , … , l j N ) T为实体 e i和 e j的隐特征向量,d为实体的隐特征个数, w a b k表示关系 r k中隐特征a和b的相互作用程度。它用乘法项描述了两实体间的相互作用,因 l i和 l j都是线性关系,故也称为双线性模型。训练过程中,同时学习实体的隐特征向量表示为影响矩阵 W k。
RESCAL模型的推理准确率高,但是计算慢,时间复杂度高,占用内存大,在大型知识图谱上并不适用。在此基础上,Chang等人[16]提出了TRESCAL模型,引入实体类型约束,提前排除与关系 r k不相关类型的实体,很大地提升了计算速度。

2.1.3 结构化嵌入模型(SE)

相比较于RESCAL模型直接利用实体的隐向量表示进行集体机器学习,隐距离模型(LDM)方法则是根据实体隐特征向量间的距离来预测两实体间的关系。Hoff等人在文献[17]中第一次提出此算法,并用于社交网络分析。他们定义得分函数 f i j为
f i j L D M ∶ = α + β ' δ i j - d l i , l j
其中 α与 β为常数,附加协变量 δ i j表示观测得到的潜在成对性, d l I , l j表示实体 e i和 e j的隐特征向量之间的距离(常用欧氏距离,也即 l i - l j ‖ 2 。 d l I , l j越大,则 f i j越小,实体 e i和 e j间就越可能有关系。
在此基础上,Bordes等人[18]提出了结构化嵌入(SE)模型,将隐距离模型方法推广到了多关系数据的知识推理中。定义所有实体的d维隐特征向量组成的空间为嵌入空间,取得分函数 f i j为
f i j k S E ∶ = - ‖ R k l h s l i - R k r h s l j ‖ p
其中矩阵对 R k = R k l h s , R k r h s表示关系 r k分别关于头实体和尾实体的线性变换,且 R k l h s和 R k r h s都是d维方阵, ‖ · ‖ p为向量的p-范数,为降低梯度学习的复杂度,常取p=1,即1-范数。同理,嵌入空间内的两实体隐特征向量,经特定关系线性变换后距离越近,则 f i j越大,两实体越有可能有关系。

2.1.4 翻译模型(TransE)

无论是基于隐特征的RESCAL模型,还是基于隐距离的SE模型,都是将关系视作一个变换矩阵,将实体映射到特定维的向量空间中进行集体学习。然而训练过程中需要先学习出关系变换矩阵等参数,对于大型知识图谱来说耗费时间较长,占用内存也较大,准确度不高。
为此,Bordes等人[19]受文献[20]中提出的“用嵌入空间中的向量差表示词汇间关系”思路启发,提出了TransE模型,定义得分函数 f i j为
f i j k T r a n s E : = - d l i + r k , l j
其中函数d(x1,x2)表示向量x1,x2间距离(常取欧氏距离), l i与 l j分别为头实体 e i和尾实体 e j在嵌入空间中的向量表示, r k为关系 r k在嵌入空间中的向量表示。该模型思路为:如果事实三元组 x i j k = e i , r k , e j存在,那么头实体向量 l i 与 关 系 向 量 r k之和与尾实体向量 l j相近,否则远离。训练过程中,若关系数量不足,可通过替换头尾实体增加负例,最终根据得分函数的高低确定推理结果。
TransE模型简单有效,可并行性好,计算效率和召回率都很高,在学术界大受欢迎,科研工作者们不断地投入了对Trans系列的研究。例如, Wang等人[21]为了提升TransE处理多属性关系的能力,提出了TransH模型,先将实体映射到关系所在的超平面上,再利用TransE算法建模;Lin等人[22]提出了TransR模型,先将实体和关系映射到不同向量空间,再通过空间映射矩阵将实体向量映射到每个关系对应的不同空间中,最后再计算得分函数。

2.2 基于图特征的实体关系学习

利用机器学习方法学习实体与关系,还可以借助知识图谱的图特征进行学习,从知识图谱中观察总结三元组中边(节点)的特征,进而预测出一条新的边(节点)。例如,从图中观察到 $M\xrightarrow{就学于}\times \times \text {学校} \times \times \text { 班 } \xleftarrow{就学于}N$,则说明三元组（M,同学,N）存在。
通过知识图谱中节点的领域与节点间路径的存在性观测度量出实体的相似性,相似性越高的实体间更可能存在关系(边)。根据度量方法不同可分为局部相似性指数、全局相似性指数和准局部相似性指数。局部相似性指数是通过实体的公共邻居数或绝对邻居数衡量实体间的相似性,计算效率高但无法预测远程或全局依赖关系,如文献[23]中提出的Adamic-Adar指数,文献[24]中提出的偏好连接(Preferential Attachment)算法;全局相似性指数是通过实体间所有的路径集合或图上的随机游走来计算实体相似性,预测效果更好但计算代价很高,对如Katz指数[25]、PageRank算法[26];准局部相似指数是对两者的折中,以兼顾计算效率和预测效果,如局部Katz指数[27]、局部随机游走算法[28]。
另一种方法是基于归纳逻辑编程(ILP)从知识图谱中挖掘提取出新的规则,并利用这些规则预测新的关系,如ALEPH系统[29]、AMIE系统[30-31],它们挖掘出的规则可解释性好,但是难于挖掘出有用的规则。此外,还有路径排序方法(Path Ranking)[32-33],受随机游走算法启发,先观测出两实体间的所有联通路径,然后随机跟踪一个传出链接,通过抽样过程递归地计算出每种不同长度路径的概率,并以此为特征预测新的边,即实体间关系。

2.3 实体类型推理(Type Inference)

大型知识图谱中实体数量众多,为了更方便地管理、调用知识库,需要实体按类型分组划分。而由于跨领域大型知识库中实体种类繁杂,靠人工标注耗费过大且效率低下,所以研究结合机器学习方法的自动类型推理方法很有必要。
基于RDF,知识图谱由一系列事实三元组组成,其中有一种特殊的关系叫“属性”,此时三元组可写作(实体,属性,属性值),例如(中国,首都,北京)三元组表示“中国的首都是北京”。在此基础上,Paulheim等人[34]提出了SDtype模型,利用三元组中头尾实体的在属性链接中的位置统计分布规律来推理实体的类型。例如,统计知识库中所有的关于属性“首都”的(x,首都,y)三元组的分类情况,可计算出x是“国家名”的概率P(x是国家名)与y是“城市名”的概率P(y是城市名),进而便可推理出其他未分类的形如(a,首都,b)三元组中实体的类型。
设类型集合为 T y p e = { t 1 , t 2 , … , t M },待分类实体的属性有 P r o p e r t y = { p 1 , p 2 , … , p N } ,Sdtype模型定义待分类实体类型为T的置信度为
c o n f T ∶ = 1 ∑ i = 1 N w p i ∑ i = 1 N w p i P T | c p i
其中事件 c p i表示头实体与尾实体是否含有公共属性 p i,含有则为真,不含则为假; c p i为真时, P T c p i是由统计得到的公共属性 p i存在时实体为类型T的概率;N为待分类实体属性总数,既包含传入属性(作为尾实体),也包含传出属性(作为头实体); w p i为权系数,代表预测实体类型时属性 p i的重要程度,定义为
w p i = ∑ j = 1 M [ P t j - P ( t j | c p ( i ) ) ] 2
其中 P t j表示类型 t j的三元组在全体三元组中所占比例。Sdtype模型可用于大型跨域数据集,分类准确率高,且能够处理噪声数据,在Dbpedia上取到了很好的效果,其不足之处是仅能预测较高级别的类型,难以预测更细粒度的类型。

3 结束语

知识图谱能够方便地将真实世界翻译成一张机器能够理解的数据网络,在人工智能领域占有重要地位,一直以来备受学术界与工业界的关注。知识推理技术能够在现有知识库基础上挖掘,预测新的知识,是知识图谱补全与知识图谱去噪的重要手段。
当前的基于统计的知识推理方法还存在一些问题,如难以处理开放世界多元关系问题,对实体属性的利用率不高。同时,近几年在图像,视频处理等领域的深度学习技术,也由于缺乏可解释性与因果推断能力,在知识推理领域受挫。而结合深度学习神经网络与分布式学习的混合推理方法,如ConvKB[35]、R-GCN[36]等模型,展现出较优的性能与较好的潜力,值得后续深入研究。
随着知识图谱规模越来越大、横跨的领域越来越多,传统的基于逻辑的知识推理方法计算速度缓慢、耗费代价高,不适用于大型知识图谱。而结合机器学习方法的知识推理技术能简单高效地完成推理任务,该方向的研究对完善知识图谱具有重要意义,值得后续深入探究。

References

Publishing order | Descend order by publishing year | Descend order by cited within
[1]
Berners-Lee T, Hendler J, Lassila O. The Semantic Web[J]. Scientific american, 2001, 284(5): 28-37.

[2]
KLYNE, Graham. Resource Description Framework (RDF): Concepts and Abstract Syntax[EB/OL]. [2004-02-10]. http://www.w3.org/TR/2004/REC-rdf-concepts-20040210.

[3]
AMIT S. Introducing the Knowledge Graph[R]. America:Official Blog of Google, 2012.

[4]
Suchanek F M, Kasneci G, Weikum G. Yago: A Core of Semantic Knowledge[C]. Proceedings of the 16th international conference on World Wide Web. ACM, 2007: 697-706.

[5]
Hoffart J, Suchanek F M, Berberich K, et al. YAGO2: A Spatially and Temporally Enhanced Knowledge Base From Wikipedia[J]. Artificial Intelligence, 2013(194): 28-61.

[6]
Auer S, Bizer C, Kobilarov G, et al. Dbpedia: A Nucleus For A Web of Open Data[M]. The Semantic Web. Springer, Berlin, Heidelberg, 2007: 722-735.

[7]
Carlson A, Betteridge J, Kisiel B, et al. Toward an Architecture for Never-ending Language Learning[C]. Twenty-Fourth AAAI Conference on Artificial Intelligence. 2010.

[8]
Bollacker K, Evans C, Paritosh P, et al. Freebase: A Collaboratively Created Graph Database for Structuring human Knowledge[C]. Proceedings of the 2008 ACM SIGMOD international conference on Management of data. ACM, 2008: 1247-1250.

[9]
Guan SP, Jin XL, Jia YT, et al. Knowledge Reasoning Over Knowledge Graph: A Survey[J]. Journal of Software, 2018, 29(10):2966-2994.

[10]
Lee T W, Lewicki M S, Girolami M, et al. Blind Source Separation of More Sources Than Mixtures Using Overcomplete Representations[J]. IEEE Signal Processing Letters, 1999, 6(4): 87-90.

DOI

[11]
Hoff P. Modeling Homophily and Stochastic Equivalence in Symmetric Relational Data[C]. Advances in Neural Information Processing Systems, 2008: 657-664.

[12]
Nickel M, Murphy K, Tresp V, et al. A review of Relational Machine Learning for Knowledge Graphs[J]. Proceedings of the IEEE, 2016, 104(1): 11-33.

DOI

[13]
Nickel M, Tresp V, Kriegel H P. A Three-Way Model for Collective Learning on Multi-Relational Data[C]. In: ICML. 2011. p. 809-816.

[14]
Nickel M, Tresp V, Kriegel H P. Factorizing yago: Scalable Machine Learning for Linked Data[C]. Proceedings of the 21st international conference on World Wide Web. ACM, 2012: 271-280.

[15]
Nickel M, Tresp V. Tensor Factorization for Multi-relational Learning[C]. Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, Berlin, Heidelberg, 2013: 617-621.

[16]
Chang K W, Yih W, Yang B, et al. Typed Tensor Decomposition of Knowledge Bases for Relation Extraction[C]. Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP). 2014: 1568-1579.

[17]
Hoff P D, Raftery A E, Handcock M S. Latent Space Approaches to Social Network Analysis[J]. Journal of the american Statistical association, 2002, 97(460): 1090-1098.

DOI

[18]
Bordes A, Weston J, Collobert R, et al. Learning Structured Embeddings of Knowledge Bases[C]. Twenty-Fifth AAAI Conference on Artificial Intelligence. 2011.

[19]
Bordes A, Usunier N, Garcia-Duran A, et al. Translating Embeddings for Modeling Multi-relational Data[C]. Advances in neural information processing systems. 2013: 2787-2795.

[20]
Mikolov T, Chen K, Corrado G, et al. Efficient Estimation of Word Representations in Vector Space[J]. arXiv preprint arXiv:1301. 3781, 2013.

[21]
Wang Z, Zhang J, Feng J, et al. Knowledge Graph Embedding by Translating on Hyperplanes[C]. Twenty-Eighth AAAI conference on artificial intelligence. 2014.

[22]
Lin Y, Liu Z, Sun M, et al. Learning Entity and Relation Embeddings for Knowledge Graph Completion[C]. Twenty-ninth AAAI Conference on Artificial Intelligence, 2015.

[23]
Adamic L A, Adar E. Friends and Neighbors on the Web[J]. Social Networks, 2003, 25(3): 211-230.

DOI

[24]
Barabási A L, Albert R. Emergence of Scaling in Random Networks[J]. Science, 1999, 286(5439): 509-512.

DOI

[25]
Katz L. A New Status Index Derived from Sociometric Analysis[J]. Psychometrika, 1953, 18(1): 39-43.

DOI

[26]
Brin S, Page L. The Anatomy of a Large-scale Hypertextual Web Search Engine[J]. Computer networks and ISDN Systems, 1998, 30(1/7): 107-117.

DOI

[27]
Liben-Nowell D, Kleinberg J. The Link-prediction Problem for Social Networks[J]. Journal of the American Society for Information Science Andtechnology, 2007, 58(7): 1019-1031.

[28]
Liu W, Lü L. Link Prediction Based on Local Random Walk[J]. EPL (Europhysics Letters), 2010, 89(5): 58007.

DOI

[29]
Muggleton S. Inverse Entailment and Progol[J]. New Generation Computing, 1995, 13(3/4): 245-286.

DOI

[30]
Galárraga L A, Teflioudi C, Hose K, et al. AMIE: Association Rule Mining Under Incomplete Evidence in Ontological Knowledge Bases[C]. Proceedings of the 22nd International Conference on World Wide Web. ACM, 2013: 413-422.

[31]
Galárraga L, Teflioudi C, Hose K, et al. Fast Rule Mining in Ontological Knowledge Bases with AMIE+[J]. The VLDB Journal-The International Journal on Very Large Data Bases, 2015, 24(6): 707-730.

[32]
Lao N, Cohen W W. Relational Retrieval Using a Combination of Path-constrained Random Walks[J]. Machine learning, 2010, 81(1): 53-67.

DOI

[33]
Lao N, Mitchell T, Cohen W W. Random Walk Inference and Learning in a Large Scale Knowledge Base[C]. Proceedings of the Conference on Empirical Methods in Natural Language Processing. Association for Computational Linguistics, 2011: 529-539.

[34]
Paulheim H, Bizer C. Type Inference on Noisy RDF Data[C]. International semantic web conference. Springer, Berlin, Heidelberg, 2013: 510-525.

[35]
Nguyen, Dai Quoc, et al. A Novel Embedding Model for Knowledge Base Completion Based on Convolutional Neural Network[J]. arXiv preprint arXiv:1712.02121, 2017.

[36]
Schlichtkrull, Michael, et al. Modeling Relational Data with Graph Convolutional Networks[C]. In: European Semantic Web Conference. Springer, Cham, 2018.

Options
Outlines

/

〈 〉