知识图谱——关系抽取

本文介绍 Random Walk Algorithm 与 Path Ranking Algorithm 在知识图谱关系抽取中的应用.

1 Random Walk Algorithm

1.1 一点有趣的背景

Random Walk(随机游走)的概念很早就有了，不过在1973年于一本叫 A Random Walk Down Wall Street 的书中得到了广泛的应用. 该书认为股市的走向是随机的 (“Stocks take a random path”)，难以预测，其难度堪比预测一个酒鬼下一步会走向哪里. 书中认为股票的价格是独立同分布的，因此不能假设过去的股市走向可以用来预测未来.

1.2 进入正题

这里用一维的随机游走模型来举个例子：

设一条直线上有$n$个点，依次为$1,2,\dots,n$. 在当前时刻$t$，有一个质点$A$位于点$i$. 那么在$t+1$时刻，质点$A$的位置可能有：

1. 以$p$的概率走到点$i-1$.
2. 以$(1-p)$的概率走到点$i+1$.

理论看上去非常简单… 不过还有一些关于期望和概率分布的计算比较有趣，计算过程挺简单的，本文不再叙述，具体可以看看这里.

随机游走要解决的问题是，给定一个连接图及图中每个节点的转移概率，找到从某个点开始随机走动，最后停留在每个点的概率分布.

其求解的具体过程为：在任意一个顶点，以概率$1-p$走到这个顶点的邻居顶点，以概率$p$随机跳跃到图中的任何一个顶点，称$p$为跳转发生概率. 每次游走后得出一个概率分布，该概率分布刻画了图中每一个顶点被访问到的概率。用这个概率分布作为下一次游走的输入并反复迭代这一过程。当满足一定前提条件时，这个概率分布会趋于收敛，可以得到一个平稳的概率分布.

1.3 Random Walk with Restart

Random Walk with Restart (重启随机游走)考虑了回到起始点的概率概率分布，即下一跳有一定的概率回到起始点，称为重启概率.

设一个连接图有$n$个节点，则以$i$为起点，到达图中各个节点概率分布$\boldsymbol{r}\in\mathbb{R}^{n\times1}$可以由下式定义：

$$\boldsymbol{r}=(1-d)\boldsymbol{u}+d\boldsymbol{W}\boldsymbol{r}.$$

其中，$1-d$是重启概率，$W$是转移矩阵，$\boldsymbol{u}$是为one-hot的起点向量.

上式的解可以通过迭代地计算下式得到：

$$\boldsymbol{r}^t=(1-d)\boldsymbol{u}+d\boldsymbol{W}\boldsymbol{r}^{t-1}.$$

以图中每个节点各为起点做一次RWR得到$\boldsymbol{r}$，则可以表示点之间的相关性.

1.4 两个简单的应用

1. 图嵌入

   • DeepWalk

     将图信息转化为向量嵌入. 使用随机游走生成节点序列，将图数据转化为一段类似自然语言的序列，然后用Word2Vec的模型得到每个节点的向量.

   • Node2Vec

     DeepWalk完全随机，而Node2Vec用两个参数控制随机游走下一跳的概率分配.

2. 分类

   分别从A类型的节点与B类型的节点开始做RWR，如果RWR(A)数值比RWR(B)大，则将该节点归为A类，反之归为B类.

2 Path Ranking Algorithm

2.1 背景

Path Ranking Algorithm (PRA) 在 Relational Retrieval Using a Combination of Path-Constrained Random Walks (Lao and Cohen, 2010b) 一文中提出. 它想要解决的问题是，给定知识图谱与查询，得到图中与之相关的节点，即语义上相似(proximity)的节点.

“… ad hoc retrieval or named entity recognition (NER) to be formulated as typed proximity queries in the graph.”

不同于以往常用的有监督的重启随机游走(RWR)，给每个边一个权重，

“… associating each edge label with a parameter.”

PRA给出一组边序列，并给它们打分，然后再做加权，加权得到的结果用于衡量相似度.

“… a novel learnable proximity measure which instead uses one weight per edge label sequence: proximity is defined by a weighted combination of simple “path experts”, each corresponding to following a particular sequence of labeled edges.”

RWR的局限性是，忽略了边的上下文. 例如，给定年份$y$，要查询合适的参考文献. 那么有两种方式：(H1) $y$年发表的论文；(H2) $y$年发表的论文中被引用最多的. 直觉上，H2更好. 但RWR只能考虑到”发表于”(PublishedIn)，考虑不到”被引用”(“Cite“)

2.2 任务

该论文的任务背景是：用有标签的有向图来表示科学文献，其中不同类别的节点可以表示文档、术语、元数据，不同标签的边可以表示节点之间的关系，可以解决 typed oriximity queries. 给定查询节点(query nodes)和答案类型(answer type)作为输入，可以得到一组符合答案类型的节点作为输出，且按照与查询节点的相似度排序.

该论文考虑了4个任务：

1. 会议推荐 (venue recommendation)

   任务目标：查询一篇新的论文适合发表的会议

   查询节点：论文的标题与术语、一组与论文相关的实体 (基因或蛋白质)、当前年份

   答案类型：期刊 (“journal”)

2. 引用推荐 (reference recommendation)

   任务目标：查询一篇新论文相关的参考文献

   查询节点：同任务1

   答案类型：论文 (“paper”)

3. 专家寻找 (expert finding)

   任务目标：寻找某个特定的专家

   查询节点：术语、实体、当前年份

   答案类型：人 (“person”)

4. 基因推荐 (gene recommendation)

   任务目标：根据某个作者以往的发表，预测他之后发表文章将涉及的基因

   查询节点：作者、年份

   答案类型：基因 (“gene”)

2.3 方法

2.3.1 符号定义

符号	意义
$e$	实体(节点).
$R(e,e’)$	$e$与$e’$之间的关系$R$.
$R(e)$	满足$R(e,e’)$的$e’$,
$dom(R)$	$R$的定义域,
$range(R)$	$R$的值域.
$P$	由$R_1\dots R_l$构成的关系路径.

$P$满足$range(R_i)\equiv dom(R_{i+1})$，且$dom(R_1\dots R_l)\equiv dom(R_1)$，$range(R_1\dots R_l)\equiv range(R_l)$.

一条路径$P=R_1\dots R_l$可以表示为：

$$T_0\xrightarrow{R_1}\dots\xrightarrow{R_l}\dots T_l,$$

其中，$T_0=dom(R_1)=dom(P)$，$T_1=range(R1)=dom(R_2)$.

此外，用$^{-1}$表示关系的逆，并且关系与关系的逆是不同的.

2.3.2 具体算法

给定关系路径$P=R_1\dots R_l$，一组查询节点$E_q\subset dom(P)$，可以计算图中节点$e$的分数$h_{E_q,P(e)}$：

• 如果$P$为空

  $$h_{E_q,P(e)}= \begin{cases} & \frac{1}{|E_q|} &,\text{if }e\in E_q \newline & 0 &,\text{otherwise} \end{cases}.$$

• 如果$P$非空

  $$h_{E_q,P(e)}=\sum_{e'\in range(P')}h_{E_q,P'(e')}\cdot\frac{I(R_l(e',e))}{|R_l(e')|},$$

  其中，

  $$\begin{align} & P'=R_1\dots R_{l-1}, \newline & I(R_l(e',e))= \begin{cases} & 1 &,\text{if }e'\in dom(R_l) \newline & 0 &,\text{otherwise} \end{cases}. \end{align}$$

$\frac{1}{|E_q|}$和$\frac{I(R_l(e’,e))}{|R_l(e’)|}$可以大致理解为下一跳节点均匀分布的概率(稍微意会一下就好了).

总而言之，$h_{E_q,P(e)}$表示了给定一条关系路径和一组查询节点，图中某个节点的分数.

因此，考虑一组不同的关系路径$P_1,\dots,P_n$，并给出一组线性加权值$\theta_i$，我们可以对图中所有的$e$基于下式的结果排序：

$$\theta_1h_{E_q,P_1(e)}+\theta_2h_{E_q,P_2(e)}+\dots\theta_nh_{E_q,P_n(e)}.$$

给定查询节点$E_q$与答案类型$T_q$，对于固定的长度$l$，可以生成一组关系路径$\mathcal{P}(q,l)=\{P\}$，其中$\mathcal{P}$的值域包含于$T_q$.

因此，PRA就是用下列评分函数对所有符合答案类型的节点$e\in I(T_q)$进行排序：

$$s(e;\theta)=\sum_{P\in\mathcal{P}(q,l)}h_{E_q,P(e)}\theta_P.$$

上式可以写为矩阵形式$s=\boldsymbol{A}\theta$，其中$A$称为特征矩阵，$s$与$\theta$均为列向量，与不同的$P$对应.

2.3.3 参数估计

设训练集为$\mathcal{D}=\{(q^{(m)},r^{(m)})\},m=1,\dots,M$，其中，$r^{(m)}$为零一向量(binary vector). 如果节点$e$与查询$q^{(m)}$相关，那么$r_e^{(m)}=1$，反之为$0$.

优化目标为下式，运用了L2正则化：

$$O(\theta)=\sum_{m=1}^Mo^{(m)}(\theta)-\frac{\lambda}{2}|\theta|_2.$$

对于一个训练集$\mathcal{D}$中的第$m$条训练数据，设特征矩阵为$A^{(m)}$，与之相关的节点下标集合为$\mathcal{R}^{(m)}$，与之无关的节点下标集合为$\mathcal{N}^{(m)}$. 用二项分布的对数似然(binomial log-likelihood)来表示目标函数：

$$o^{(m)}(\theta)=\sum_{i\in\mathcal{R}^{(m)}}\frac{\ln p_i^{(m)}}{|\mathcal{R}^{(m)}|}+\sum_{i\in\mathcal{N}^{(m)}}\frac{\ln(1-p_i^{(m)})}{|\mathcal{N}^{(m)}|},$$

其中，$p_i^{(m)}=\sigma(\theta^TA_i^{(m)})$. 可以理解为将$s$分类为$r=1$与$r=0$，并且用sigmoid函数将其映射到$[0,1]$表示概率.

求导优化过程这里就不写了，具体的内容在论文的3.2节.

2.3.4 延伸

论文中还提到了基于上述PRA的延伸：

1. Query-Independent Experts
2. Popular Entity Experts