失眠网 > 知识图谱—知识推理综述(二)

知识图谱—知识推理综述(二)

时间：2022-09-05 07:30:07

相关推荐

知识图谱—知识推理综述(二)

本文接上一篇博客知识图谱—知识推理综述(一)

2 基于传统方法的推理

2.2 基于图结构的推理

2.2.1 引入

在知识图谱中，如果是自下而上的进行构建，那么最终图谱将以一个有向图的形式进行呈现。图中的节点表示的是实体或者实体的属性值，有向图的边表示的是不同实体之间的关系，或者实体和其属性值之间的属性关系。

有向图的结构可以很好的反应知识图谱的语义信息。当进行推理的时候，可以从图谱中的一个点进行出发，沿着有向边到达其他节点。从而形成一条推理路径。举一个例子来说：小明——>(妻子)——>小红——>(孩子)——>小李。这是一条从小明到小李的路径。所表示的信息是“小明的妻子是小红”，“小红的孩子是小李”。从语义关系的角度出发，可以推理出小明的孩子是小李。同理，这样的推理过程不仅仅包含这一条路径。在比如：老刘——>(妻子)——>小花——>(孩子)——>小刘。通过这条路径，我们也可以推理出老刘和小刘是父子关系。由个体到一般化，我们可以总结出在图谱中有A——>(妻子)——>B——>(孩子)——>C，其中ABC是三个实体变量。

上述的例子表明，在知识图谱中，路径是进行推理的一种重要的信息。除了路径之外，邻居节点也是一个进行推理的重要信息，比如在上述例子的推理中，我们要求的是AB是相邻节点，BC是相邻节点，这样我们才能对AC的关系进行推理。一般而言，距离当前实体越近，对于当前实体的描述的贡献越大。在一般的推理研究中，一般是一跳或者两调范围内的节点关系。

当我们把整个图谱视为一个有向图的时候，往往对于图谱中的事实三元组关注的更多，即对于实际存在的实体关注的比较多。而忽略了实体上层的本体和概念。而往往本体和上层概念中包含了更多的语义信息。

2.2.2 常见算法——PRA

最为经典的基于图结构的推理方法为PRA(Path Ranking Algorithm)，该算法利用了实体之间的路径当做特征从而进行链接预测推理。

PRA算法处理的推理问题是关系推理，在推理过程中包含两个任务，第一个任务是给定头实体h和关系r来预测尾实体t。第二个任务是利用尾实体t和关系r来预测头实体h。PRA算法针对的是自底向上构建的知识图谱，这种方法构建的知识图谱中存在着比较多的噪声。

在PRA算法中，将关系推理问题转换成了一个排序的问题，对每个关系的头实体预测和尾实体预测都单独训练处一个排序模型。PRA将知识图谱中的路径作为特征，并且通过图上的计算对每个路径赋予相应的特征值。然后利用这些特征学习一个逻辑回归模型。

在PRA算法中，我们第一个需要关注的就是如何生成路径？

在PRA中，利用随机游走的路径排序算法首先生成一些路径特征。一个路径P是由一系列的关系所生成：

P = T 0 − r 1 > T 1 − r 2 > T 2 − r 3 > T 3 − r 1 > . . . . . − r n > T n P=T_0-^{r1}>T_1-^{r2}>T_2-^{r3}>T_3-^{r1}>.....-^{rn}>T_n P=T0−r1>T1−r2>T2−r3>T3−r1>.....−rn>Tn

其中 T n T_n Tn为关系 r n r_n rn的作用域以及关系 r n − 1 r_{n-1} rn−1的值域。即：

T N = r a n g e ( r n ) = d o m a i n ( r n − 1 ) T_N=range(r_n)=domain(r_{n-1}) TN=range(rn)=domain(rn−1)

其中关系的值域和作用域通常指的是实体的类型。基于路径的随机游走定义了一个关系路径的分布，并且得到每条路径的特征值 s h , p ( t ) s_{h,p}(t) sh,p(t)，这个特征值可以理解为沿着路径P，从h开始能够到达t的概率。

初始时，我们可以对这个特征值进行初始化：

s h , p ( e ) = = { 1 e = h 0 e l e s s_{h,p}(e)==\left\{ \begin{aligned} 1 && e = h\\ 0 && eles \end{aligned} \right. sh,p(e)=={10e=heles

在随机游走的过程中， s h , p ( e ) s_{h,p}(e) sh,p(e)的更新规则为：

s h , p ( e ) = ∑ e ′ ∈ r a n g e ( p ′ ) s h , p ′ ( e ′ ) ∗ P ( e ∣ e ′ ; r l ) s_{h,p}(e)=∑_{e'∈range(p')}s_{h,p'}(e')*P(e|e';r_l) sh,p(e)=e′∈range(p′)∑sh,p′(e′)∗P(e∣e′;rl)

其中 P ( e ∣ e ′ ; r l ) P(e|e';r_l) P(e∣e′;rl)为：

P ( e ∣ e ′ ; r l ) = r l ( e ′ , e ) ∣ r l ( e ′ , ⋅ ) ∣ P(e|e';r_l)=\frac{r_l(e',e)}{|r_l(e',·)|} P(e∣e′;rl)=∣rl(e′,⋅)∣rl(e′,e)

其表示的是从节点 e ′ e' e′出发，沿着关系 r l r_l rl同过一步的游走就能够到达节点e的概率。理解了下面的公式，上面的公式就比较好理解了，其表示是对各个路径下的求和。对于关系r，在通过随机游走得到一系列的路径特征 P r = ( P 1 , P 2 , . . . . , P n ) P_r=(P_1,P_2,....,P_n) Pr=(P1,P2,....,Pn)之后，PRA利用这些特征为关系r训练一个线性的预测试题的排序模型。其中关系r下的每一个训练样本，即一个头实体和尾实体的组合的得分计算如下：

s c o r e ( h , t ) = ∑ p i ∈ p r θ i s h , p ( e ) = θ 1 s h , p 1 ( e ) + s h , p 2 ( e ) + , . . . , + s h , p n ( e ) score(h,t)=∑_{p_i∈p_r}θ_is_{h,p}(e)=θ_1s_{h,p_1}(e)+s_{h,p_2}(e)+,...,+s_{h,p_n}(e) score(h,t)=pi∈pr∑θish,p(e)=θ1sh,p1(e)+sh,p2(e)+,...,+sh,pn(e)

进一步，根据上面每一个样本的得分，我们可以通过一个逻辑回归函数老得到每一个样本的概率：

p ( r i = 1 ∣ s c o r e ( h i , t i ) ) = e x p ( s c o r e ( h i , t i ) ) 1 + e x p ( s c o r e ( h i , t i ) ) p(r_i=1|score(h_i,t_i))=\frac{exp(score(h_i,t_i))}{1+exp(score(h_i,t_i))} p(ri=1∣score(hi,ti))=1+exp(score(hi,ti))exp(score(hi,ti))

注意，这里的 r i r_i ri表示的是关系r的第i个样本，而不是第i个关系。

最后通过一个线性变换加上最大似然估计，损失函数如下表示：

l i ( θ ) = w i [ y i l n p i + ( 1 − y i ) l n ( 1 − p i ) ] l_i(θ)=w_i[y_ilnp_i+(1-y_i)ln(1-p_i)] li(θ)=wi[yilnpi+(1−yi)ln(1−pi)]

这里 y i y_i yi表示的是训练样本 ( h i , t i ) (h_i,t_i) (hi,ti)是否具有关系r的标记，如果 ( h i , r , t i ) (h_i,r,t_i) (hi,r,ti)存在，则 y i = 1 y_i=1 yi=1否则为0。

上述是PRA的路径搜索过程和评分和损失的计算过程。下面，我们来总结一下这个算法的其他特征：

PRA在路径的搜索过程中，引入了对于有效路径特征的约束，这一点可以从特征值得初始化以及特征值的更新过程中可以看出（无效路径的计算结果为0）。这样可以有效的减小搜索空间。在PRA算法中，路径在图谱中的支持度应该大于某设定的比例α，路径的长度小于或者等于事先设定的长度，每一个路径都至少存在一个正样本在训练集中。

结合以上两点，能够保证PRA算法可以快速(增加路径限制)，有效(合法路径中存在训练样本)的进行训练。

2.2.3 PRA的演化算法

在理解了PRA算法之后，我们可以来思考下面这样的一个问题：在PRA中，路径是连续的，并且是沿着有向边转移的，也就是说关系是同向的，即A->B->C =》 A->C。并且，在PRA中推理的过程是基于关系的作用域和值域，具体的取值应该是一个变量。但是，在实际的知识图谱中，很多推理路径都包含了常量，也就是一个确定的实体，举一个例子来说：

老王 − （就读于 ) > x − ( 是 ) > 学校老王-（就读于)>x-(是)>学校老王−（就读于)>x−(是)>学校

在上述的路径中小明，学校都是常量，这种带有常量，含有明显的语义信息，并且首尾不是闭合的路径是不能够被PRA捕捉到的。其原因就在于PRA中搜索的路径是由关系的值域和作用域构成的。为了解决这个问题，这里提出了co-PRA算法。该算法通过改变PRA的搜索策略，使其能够覆盖更多的语义信息(主要是包含常量的语义信息特征)。给定一个关系r下的训练样本(h,t)，其搜索过程如下：

生成初步的路径：通过路径搜索生成以h为起点的长度小于l 的路径集合 P h P_h Ph，通过路径搜索生成以t为起点的长度小于l的路径集合 P t P_t Pt。通过上述PRA的计算公式来计算路径特征的概率。对于属于 P h P_h Ph的某一条路径 π h π_h πh，计算沿着路径 π h π_h πh正向的由h到x的概率 p ( h − > x ; π h ) p(h->x;π_h) p(h−>x;πh)，以及沿着路径 π h π_h πh逆向的由x到达h的概率 p ( h < − x , π h − 1 ) p(h<-x,π_h^{-1}) p(h<−x,πh−1)，以及由路径 π t π_t πt，正向的从t到x的概率 p ( t − > x , π t ) p(t->x,π_t) p(t−>x,πt)和逆向的概率 p ( t < − x , π t − 1 ) p(t<-x,π_t^{-1}) p(t<−x,πt−1)，并且将所有的x放入到常量的候选集N中去。生成候选的常量的路径，对于每一个 x ∈ N ， π ∈ P t x∈N，π∈P_t x∈N，π∈Pt的组合，如果 p ( t − > x ∣ π t ) > 0 p(t->x|π_t)>0 p(t−>x∣πt)>0，那么生成路径特征 P ( c < − t ; π t − 1 ) P(c<-t;π_t^{-1}) P(c<−t;πt−1)，其中c=x，并且将路径特征对应的覆盖度值+1，同理，对于每一个 x ∈ N ， π ∈ P t x∈N，π∈P_t x∈N，π∈Pt的组合，如果 p ( t < − x ∣ π t − 1 ) > 0 p(t<-x|π_t^{-1})>0 p(t<−x∣πt−1)>0，则生成特征路径 P ( c − > t ; π t ) P(c->t;π_t) P(c−>t;πt)，其中c=x，覆盖度+1。生成更长的路径特征的候选集，对于每一个可能的特征组合(x∈N,π_h∈p_h,π_t∈p_t)，如果有 p ( s < − x ∣ π s ) > 0 且 p ( t < − x ∣ π t − 1 ) > 0 p(s<-x|π_s)>0且p(t<-x|π_t^{-1})>0 p(s<−x∣πs)>0且p(t<−x∣πt−1)>0，则生成新的路径 p ( h − > t , π s , π t − 1 ) p(h->t,π_s,π_t^{-1}) p(h−>t,πs,πt−1)，并且更新其覆盖度+1。同时更新其准确度：

准确度 ( h − > t , π s , π t − 1 ) = p ( s < − x ∣ π s ) p ( t < − x ∣ π t − 1 ) / n 准确度(h->t,π_s,π_t^{-1})=p(s<-x|π_s)p(t<-x|π_t^{-1})/n 准确度(h−>t,πs,πt−1)=p(s<−x∣πs)p(t<−x∣πt−1)/n

从整个的路径搜索中，可以发现相比于PRA，co-PRA增加了双向搜索，增加了带有常量的路径特征搜索两个方面。

2.2.3 小节

在上述我们所提提到的基于规则的推理和基于图结构的推理，他们在传统推理中都属于归纳推理的机制。其核心的思想都是利用现有的部分规则来推理出新的事实，也都存在着归纳推理中的问题，即推理出来的结果是一个预测值，不能说是一个真正的事实。在下一个小结，我们将介绍本体推理。

2.3 本体推理

本体推理是演绎推理的一种，其拥有着本体推理的特征，即利用现有的事实来论证出新的事实。与归纳推理不同，这种推理机制的结果是一个事实，而非是一个预测值。

2.3.1 如何描述本体？

在演绎推理中需要明确的定义先验信息，所以基于演绎的知识图谱推理围绕着本体展开。本体的一般性定义为概念化的显示规约。它给不同领域提供共享的词汇。因为共享词汇需要赋予一定的语义。所以一般来讲，基于演绎的推理一般都是基于具有逻辑描述基础的知识图谱上的进行。在进行演绎推理之前，我们需要先对逻辑描述定义一些规范。下面我们介绍的是最常见的描述规范为OWL。

OWL按照其描述能力可以分成OWL Lite，OWL DL和OWLFULL。在OWL中模型论语义，在逻辑丰富的知识图谱中，除了包含实体和二元关系，还包括很多抽象的信息。根据这些抽象信息，我们可以利用owl来对如下的问题进行推理：

概念包含：即推理出C是否为D的子概念。比如“母亲⊆女人，女人⊆人”=》“母亲⊆人”。概念互斥：判断两个概念C和D是否互斥。C∩D=φ是否为给定知识库的逻辑结论。概念可满足：判断概念C是否可满足，即需要在知识库中找到一个模型，是C成立。全局一致：判断知识库是否全局一致。TBox一致：判断给定知识库的TBox是否一致，需要判断TBox中的所有的原子概念是否满足。实例测试：判断个体a是否满足概念C的实例实例检索：找出概念C在给定知识库中的所有实例。