Zequn Sun et al. IJCAI 2018.

相关知识介绍

实体对齐(entity alignment)也被称为实体匹配(entity matching)，主要用于消除异构数据中实体冲突、指向不明等不一致性问题，可以从顶层创建一个大规模的统一知识库，从而帮助机器理解多源异质的数据，形成高质量的知识。

Bootstrap是一种统计学上的估计方法，由Stanford统计学的教授Bradley Efron提出。Bootstrap是一类非参数Monte Carlo方法，其实质是对观测信息进行再抽样，进而对总体的分布特性进行统计推断。

个人想法：Bootstrap只是通过多次重抽样对已有样本进行了最大程度的利用，并没有额外增加样本。因为样本有限，抽样次数在足够多的情况下，Bootstrap可以最大程度地估计出当前样本的统计特性。

论文背景

知识图谱(Knowledge Graph，KG)在AI的众多领域中广泛应用，如问答(question answering)、语义搜索(semantic searching)和知识推理(knowledge reasoning)等。知识图谱中知识一般以三元组(h,r,t)的形式表示，其中h表示头实体(head entity)，r表示关系(relation)，t表示尾实体(tail entity)。为更好地捕捉知识图谱中的隐藏语义，将知识图谱中的元素（如实体、关系等）用低维的向量(embedding)表示。

单一的知识图谱很难满足多元知识的需要，一种有效的方式是通过实体对齐(entity alignment)将多种知识图谱的异构知识集成起来。但有限的训练数据会使得embedding不准确，实体对齐的精确度不高。因此本文提出了一个基于Bootstrap的实体对齐技术。

问题定义

实体对齐的目标是找到集合$A = {(x,y)\in X\times Y|X\sim_RY}$A=(x,y)∈X×Y∣X∼R​Y，其中$X$X表示$KG_1$KG1​的实体集，$Y$Y表示$KG_2$KG2​的实体集， $\sim_R$∼R​是等价关系。$X^{'}$X′和$Y^{'}$Y′是已有的训练集。

本文将实体对齐转换成分类问题，即用$Y$Y的实体给$X$X的实体打标签，对应概率定义为$\pi(y|x;\theta) = \sigma(sim(\vec{v}(x), \vec{v}(y))),$π(y∣x;θ)=σ(sim(v(x),v(y))),其中，$\sigma(\cdot)$σ(⋅)是sigmoid函数，$sim(\cdot)$sim(⋅)是余弦相似度度量，$\theta$θ是$KG_1$KG1​和$KG_2$KG2​的embedding参数。最终，本文的最大似然优化目标为$\hat{\theta} = {\arg \max}_{\theta}\sum_{x\in X}\log \pi(L_x|x;\theta) = {\arg \max}_{\theta}\sum_{x\in X}\sum_{y\in Y} \mathbf{1}_{[y=L_x]}\log \pi(y|x;\theta),$θ^=argmaxθ​x∈X∑​logπ(Lx​∣x;θ)=argmaxθ​x∈X∑​y∈Y∑​1[y=Lx​]​logπ(y∣x;θ),其中$L_x$Lx​表示实体$x$x的真实标签，$\mathbf{1}_{[\cdot]}$1[⋅]​是示性函数。

主要方法

首先，考虑到正负样本的训练问题，使用了限制损失的embedding目标函数：$O_e = \sum_{\tau \in T^+}[f(\tau) - \gamma_1]_+ + \mu_1\sum_{\tau^{'} \in T^-}[\gamma_2 - f(\tau^{'})]_+.$Oe​=τ∈T+∑​[f(τ)−γ1​]+​+μ1​τ′∈T−∑​[γ2​−f(τ′)]+​.其中$f(\cdot)$f(⋅)是score function，度量三元组的合理性(plausibility)，$[\cdot]_{+} =max(\cdot,0)$[⋅]+​=max(⋅,0),$\gamma_1.\gamma_2>0$γ1​.γ2​>0和$\mu_1$μ1​是超参数，$T^+$T+是正样本，$T^{-}$T−是负样本。并且，使用$\epsilon$ϵ去除负样本生成，即从当前样本的最近$s=\lceil(1-\epsilon)N\rceil$s=⌈(1−ϵ)N⌉个样本中挑选负样本，使负样本更难从正样本中分别出。其中$\epsilon \in[0,1]$ϵ∈[0,1]是比例，$N$N是知识图谱中样本的总数目，$\lceil\cdot\rceil$⌈⋅⌉是向上取整函数(ceiling function)。

其次，考虑到样本不足的问题，并考虑到实体和标签间的一一对应，在第$t$t轮迭代标签对应使用如下的损失函数$\max \sum_{x\in X^{'}}\sum_{y \in {Y^{'}x}}\pi(y|x;\theta^{(t)}\cdot\psi^{(t)}(x,y)), \quad s.t. \sum_{x\in X^{'}}\psi^{(t)}(x^{'},y))\leq1,\sum_{y \in {Y^{'}x}}\psi^{(t)}(x,y^{'}))\leq1, \forall x,y.$maxx∈X′∑​y∈Y′x∑​π(y∣x;θ(t)⋅ψ(t)(x,y)),s.t.x∈X′∑​ψ(t)(x′,y))≤1,y∈Y′x∑​ψ(t)(x,y′))≤1,∀x,y.其中$Y^{'}x={y|y\in Y^{'} \text{ and } \pi(y|x;\theta^{(t)}) > \gamma_3}$Y′x=y∣y∈Y′ and π(y∣x;θ(t))>γ3​是$x$x的候选标签，$\psi^{(t)}(x,y)$ψ(t)(x,y)是需求解的预测函数。$\psi^{(t)}(x,y)=1$ψ(t)(x,y)=1当前仅当在$t$t轮时，$y$y是$x$x的标签，其它时候取0。并且，综合考虑标签样本和未标签样本，得到新的对齐目标函数为$O_a = -\sum_{x\in X}\sum_{y \in Y}\phi_x(y)\log\pi(y|x;\theta).$Oa​=−x∈X∑​y∈Y∑​ϕx​(y)logπ(y∣x;θ).其中当$x$x有标签时，$\phi(x)=\mathbf{1}_{[y=L_x]}$ϕ(x)=1[y=Lx​]​；当$x$x无标签时，$\phi(x) = \frac{1}{|Y^{'}|}$ϕ(x)=∣Y′∣1​。

最后，不仅需要捕获对齐似然，而且需要对知识图谱的语义建模，得到下面的综合目标函数：$O = O_e + \mu_2 \cdot O_a,$O=Oe​+μ2​⋅Oa​,其中$\mu_2$μ2​是一个平衡的超参数。