Relational retrieval using a combination of path-constrained random walks

---

Written by	title	date
zhengchu1994	Relational retrieval using a combination of path-constrained random walks	2018-5-22 07:12:55

(提出的算法)PRRW：核心思想是利用连接两个实体的路径去预测他们之间是否有潜在的关系。

定义

• An Entity-Relation graph G=(T,E,R)$G=(T,E,R)$, is
  
  • a set of entities types T={T}$\mathbf{T}=\{T\}$
  • a set of entities E={e}$\mathbf{E}=\{e\}$, Each entity is typed with T∈T$T\in \mathbf{T}$
  • a set of relations R={R}$\mathbf{R}=\{R\}$
• input：查询节点(query nodes)和指定返回的类型(answer type)。
• output：返回指定类型下，排好序(ordered by proximity to the query nodes)的节点。
• R$R$：是二元关系，R(e,e′)$R(e,e^{\prime })$ 表示实体e$e$ 和e′$e^{\prime }$ 之间存在关系R$R$。
• R(e)≡{e′:R(e,e′)}$R(e)\equiv \{e^{\prime }:R(e,e^{\prime })\}$，即和e$e$存在关系R$R$的所有实体集合。
• dom(R)$dom(R)$ ：关系R$R$ 的值域。
• range(R)$range(R)$：关系R$R$ 的排名。
• P$P$：查询下给出的关系路径，P={R1R2...Rl}$P=\{R_1{R}_2...R_l\}$，约束是
  ∀i:1<i<l−1，range(Ri)=dom(Ri+1)$\mathrm{\forall }i:1<i<\mathcal{l}-1，range(R_i)=dom(R_{i+1})$,定义dom(R1)=dom(P)$dom(R_1)=dom(P)$，range(Rl)=range(P)$range(R_l)=range(P)$。

则对于路径P={R1R2...Rl}$P=\{R_1{R}_2...R_l\}$：

有T0=dom(R1)=dom(P)$T_0=dom(R_1)=dom(P)$，T1=range(R1)=dom(R2)$T_1=range(R_1)=dom(R_2)$ 等。

• Path Constrained Random Walk

  • Given a query q=(Eq,Tq)$q=(E_q,T_q)$
  • Recursively define a distribution for each path：
    

• P$P$是empty path：
  

  hs,P(e)={1,0, if e=s otherwise(1)$$\begin{array}{}\text{(1)}& h_{s,P}(e)=\{\begin{array}{ll}1,& \text{ if e=s }\\ 0,& \text{otherwise}\end{array}\end{array}$$

• P$P$是nonempty：
  

  hs,P(e)=∑e′∈range(P′)hs,P′(e′)⋅P(e|e′;Rl)(2)$$\begin{array}{}\text{(2)}& h_{s,P(e)}=\sum _{e^{{}^{\prime }}\in range(P^{{}^{\prime }})}{h}_{s,P^{{}^{\prime }}(e^{{}^{\prime }})}\cdot P(e|e^{{}^{\prime }};R_{\mathcal{l}})\end{array}$$
  
  这里的P(e|e′;Rl)=Rl(e′,e)|Rl(e′,⋅)|$P(e|e^{{}^{\prime }};R_{\mathcal{l}})=\frac{R_{\mathcal{l}}(e^{{}^{\prime }},e)}{|R_{\mathcal{l}}(e^{{}^{\prime }},\cdot )|}$ 是给定Rl$R_{\mathcal{l}}$ 和e′$e^{{}^{\prime }}$ ，一步随机游走到e$e$的概率。
  1. 这里的s$s$是查询的节点，e$e$是返回的最终节点。

• 路径特征(path feature)：把查询到的s$s$ 与e$e$ 之间的各个路径P1,...,Pn$P_1,...,P_n$ ,即 hs,Pi(e)$h_{s,P_i}(e)$ 都作为特征,整个查询的得分是：
  

  score(e;s)=∑P∈Plhs,P(e)θP(3)$$\begin{array}{}\text{(3)}& \text{score}(e;s)=\sum _{P\in {\mathbf{P}}_{\mathcal{l}}}{h}_{s,P(e)}{\theta }_P\end{array}$$
  
  这里的 Pl${\mathbf{P}}_{\mathcal{l}}$ 是长度小于l$l$的关系路径集合。

  1. 给出关系集合 R$R$ 和节点对集合 {(si,ti)}$\{(s_i,t_i)\}$ ，构造训练集 D={(xi,ri)}$D=\{(x_i,r_i)\}$ ;
     其中 xi$x_i$ 是 (si,ti)$(s_i,t_i)$ (查询节点，返回终点)的全部路径和一起的向量，比如xi$x_i$的第j$j$ 个标量是 hsi,Pj(ti)$h_{s_i,P_j}(t_i)$ ,ri$r_i$ 表示关系 R(si,ti)$R(s_i,t_i)$ 是否为真。

  2. 目标函数：
     

     O(θ)=∑ioi(θ)−λ|θ|1−λ2|θ|2,(4)$$\begin{array}{}\text{(4)}& \mathcal{O}(\theta )=\sum _i{o}_i(\theta )-\lambda |\theta {|}_1-{\lambda }_2|\theta {|}_2,\end{array}$$

这里的pi$p_i$ 是预测相关性：

wi$w_i$ 衡量每个样本的重要性程度。

• 待补充：Low-Variance Sampling(LVS)，附加查询限制条件，只为保证只有小部分负样本被用在目标函数的优化中。原因是KB中的关系类型很多，即时限制路径长度，得到的关系路径还是巨大且无用。

实践

在已有知识库如NELL上做预测，48条关系，对每个关系做给定x$x$预测y$y$，正反预测共96个任务，训练集是
$$ each \ node \ x \ has \ relation\ R_i\ in \ KB \xrightarrow{R_i}any\ node \ y \$$
* $y$是正样本：如果$y$在KB中已经满足$R(x,y)$,
* $y$是负样本：不在上面都是负样本。

实验

结论

参考

http://www.cbdio.com/BigData/2016-08/30/content_5224578.htm
https://wenku.baidu.com/view/ddca21030166f5335a8102d276a20029bd64636e.html
《Relational retrieval using a combination of path-constrained random walks》
《Random Walk Inference and Learning in A Large Scale Knowledge Base》