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

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

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

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{-}^{r1}>T_1{-}^{r2}>T_2{-}^{r3}>T_3{-}^{r1}>.....{-}^{rn}>T_n$$
其中$T_n$为关系$r_n$的作用域以及关系$r_{n-1}$的值域。即：
$$T_N=range(r_n)=domain(r_{n-1})$$
其中关系的值域和作用域通常指的是实体的类型。基于路径的随机游走定义了一个关系路径的分布，并且得到每条路径的特征值$s_{h,p}(t)$，这个特征值可以理解为沿着路径P，从h开始能够到达t的概率。

初始时，我们可以对这个特征值进行初始化：
$$s_{h,p}(e)==\{\begin{array}{rlr}1& & e=h\\ 0& & eles\end{array}$$
在随机游走的过程中，$s_{h,p}(e)$的更新规则为：
$$s_{h,p}(e)=\sum _{e^{\prime }\in range(p^{\prime })}{s}_{h,p^{\prime }}(e^{\prime })\ast P(e|e^{\prime };r_l)$$
其中$P(e|e^{\prime };r_l)$为：
$$P(e|e^{\prime };r_l)=\frac{r_l(e^{\prime },e)}{|r_l(e^{\prime },\cdot )|}$$
其表示的是从节点$e^{\prime }$出发，沿着关系$r_l$同过一步的游走就能够到达节点e的概率。理解了下面的公式，上面的公式就比较好理解了，其表示是对各个路径下的求和。对于关系r，在通过随机游走得到一系列的路径特征$P_r=(P_1,P_2,....,P_n)$之后，PRA利用这些特征为关系r训练一个线性的预测试题的排序模型。其中关系r下的每一个训练样本，即一个头实体和尾实体的组合的得分计算如下：
$$score(h,t)=\sum _{p_i\in p_r}{\theta }_i{s}_{h,p}(e)={\theta }_1{s}_{h,p_1}(e)+s_{h,p_2}(e)+,...,+s_{h,p_n}(e)$$
进一步，根据上面每一个样本的得分，我们可以通过一个逻辑回归函数老得到每一个样本的概率：
$$p(r_i=1|score(h_i,t_i))=\frac{exp(score(h_i,t_i))}{1+exp(score(h_i,t_i))}$$
注意，这里的$r_i$表示的是关系r的第i个样本，而不是第i个关系。
最后通过一个线性变换加上最大似然估计，损失函数如下表示：
$$l_i(\theta )=w_i[y_{i}ln{p}_i+(1-y_i)ln(1-p_i)]$$
这里$y_i$表示的是训练样本$(h_i,t_i)$是否具有关系r的标记，如果$(h_i,r,t_i)$存在，则$y_i=1$否则为0。

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

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

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

2.2.3 PRA的演化算法

在理解了PRA算法之后，我们可以来思考下面这样的一个问题：在PRA中，路径是连续的，并且是沿着有向边转移的，也就是说关系是同向的，即A->B->C =》 A->C。并且，在PRA中推理的过程是基于关系的作用域和值域，具体的取值应该是一个变量。但是，在实际的知识图谱中，很多推理路径都包含了常量，也就是一个确定的实体，举一个例子来说：
$$老王-（就读于)>x-(是)>学校$$
在上述的路径中小明，学校都是常量，这种带有常量，含有明显的语义信息，并且首尾不是闭合的路径是不能够被PRA捕捉到的。其原因就在于PRA中搜索的路径是由关系的值域和作用域构成的。为了解决这个问题，这里提出了co-PRA算法。该算法通过改变PRA的搜索策略，使其能够覆盖更多的语义信息(主要是包含常量的语义信息特征)。给定一个关系r下的训练样本(h,t)，其搜索过程如下：

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

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

2.2.3 小节

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

2.3 本体推理

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

2.3.1 如何描述本体？

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

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

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

2.3.2 基于Tableaux的本体推理方法

基于表运算的本体推理方法是描述逻辑知识库一致性检查的最常用的方法。基于表运算的推理方法通过一系列的规则构建Abox（下面我们用L表示），其基本思路类似于一阶逻辑。举一个例子来说：假设知识库K是由一下三个声明组成：
$$C(a),C\subseteq D,﹁D(a)$$
将以a作为实例的所有概念集合记为L(a)，我们使用L<-C表示L(a)通过添加C来进行更新。比如，如果当前的L(a)=D，而且通过L(a)<-C来对L(a)进行更新，那么L(a)就变成了{C,D}。
根据我们上面对于知识库的声明，我们可以推导出L(a) = {C(a),﹁D}(L(a)为含有a的所有实例的集合)。同时，由于声明了C⊆D，则必有﹁D⊆﹁C，则L(a)可以更新为{C,﹁D,﹁C}，得到了矛盾，这表示知识库是不一致的。

在这种方法中，有以下几种更新迭代规则，L为原始的Abox：
${\prod }^{+}$规则：若C∩D(x)∈L，且C(x),D(x)∉L，则L:=L∪{C(x),D(x)}
${\prod }^{-}$规则：若C(x),D(x)∈L，且C∩D(x)∉L，则L:=L∪{C∩D(x)}
$\exists -$规则：∃R,C(x)∈L，且R(x,y),C(y)∉L，则L:=L∪{C∩D(x)}
$\forall -$规则：∀R,C(x)R(x,y)∈L，且C(y)∉L，则L:=L∪{C(y)}
$\subseteq -$规则：若C(x)∈L，C⊆D，且D(x)∉L，L:=L∪{D(x)}
$\perp -$规则：⊥(x)∈L，则拒绝L
其中y是新加入的个体。

2.4 总结

前一篇文章和上述中，主要介绍了知识推理的基本概念以及在知识图谱上的传统推理方法。由于是综述，这里对于各种方法只是介绍其基本的概念和方法的思想。没有给出具体的介绍，有兴趣的读者可以自行搜索其他对于方法介绍的文章。