实体链接任务是将文本中的指称链接到知识库中一个无歧义实体的过程^[1].该任务是信息抽取以及许多其他应用的关键技术.然而，自然语言的多样性和歧义性使实体链接任务面临很大的挑战^[2].

通过分析研究前人的工作，发现目前大部分方法使用指称及其上下文信息来进行实体链接，对于流行度较高的指称，上下文信息较为丰富，实体链接性能较好，而对于流行度较低的实体，上下文信息比较匮乏，链接性能较差.笔者将指称和候选实体统一表示为概率分布形式，通过比较分布之间的差异来计算语义相似度.

1 相关工作

目前实体链接方法主要分为2种：单一实体链接和协同实体链接^[3].

单一实体链接仅考虑当前指称与实体的链接关系，而不考虑文本中其他指称的链接信息. Mihalcea等^[4]通过词袋模型计算指称与实体间的相似度.谭咏梅等^[5]通过ListNet排序模型对候选实体进行排序，取top1作为链接实体.单独对每个指称进行链接没有考虑到同一篇文本中指称的语义一致性，影响了实体链接的效果.

协同实体链接方法考虑了当前处理的文本中指称之间的语义一致性关系，从而对同一篇文本中的所有指称进行协同实体链接.怀宝兴等^[6]提出了一种基于概率主题模型的命名实体链接方法. Cucerzan^[7]使用维基百科中的分类条目来衡量指称间的全局一致性. Han等^[8]使用重启随机游走算法来获得候选实体的相关性向量，并将该向量的相应分量作为指称和候选实体之间的相关度.李茂林^[3]在Han的基础上加入了主题信息.

2 实体识别与链接

基于重启随机游走的实体识别与链接方法包括预处理、指称发现、指称扩充、候选实体生成、候选实体排序、指称聚类6部分，流程图如图 1所示.

2.1 预处理

预处理包括建立知识库索引、生成专有名词词表和建立Latent Dirichlet Allocation主题模型.

2.1.1 知识库索引

笔者使用Elasticsearch^①对知识库Freebase构建索引，提高了搜索候选实体的效率.

https://www.elastic.co/

2.1.2 生成专有名词词表

知识库中蕴含着丰富的实体信息，如实体的别名、简写、缩写、昵称等，提取以上信息形成专有名词词表.

2.1.3 建立LDA主题模型

主题相似的文本集中，指称之间的关联程度较高，有助于指称的消歧.笔者使用LDA主题模型将主题相似的文本划为一簇.

2.2 指称发现

指称类型包括人名、组织机构名、地名、地理政治名和设施名.笔者使用Stanford NER工具识别文本中的部分指称，使用预处理部分构造的专有名词词表来识别缩写、简写、别名、昵称等工具难以准确识别的指称.

2.3 指称扩充

对指称进行扩充可以减少指称的歧义性.笔者主要针对别名和简写形式的指称进行扩充.

2.4 候选实体生成

在生成候选实体时，为避免候选实体数量过多，影响实体链接的性能，根据指称类型和知识库中实体类型的对应关系进行筛选.

同时，在知识库中的多个域，如别名、昵称、缩写、简写等搜索指称，避免遗漏候选实体.此外，对于中文指称，利用汉语拼音查找候选实体来缓解由于书写错误、繁体字和简体字不统一以及外语音译词书写不一致等造成的指称难以识别的问题.

2.5 候选实体排序

当指称存在多个候选实体时，根据相似度算法对候选实体进行排序.

2.5.1 指称与实体图结构的构建

通过预处理构建LDA主题模型得到主题分布相似的文本集D，从D中发现指称集合M，则最初的实体链接图结构G=(V, E)的构造方式为：V包括指称集合和候选实体集合，E包括指称到候选实体的边以及候选实体之间的边.然后对图进行扩充，增加与候选实体相连的实体以及边，如图 2所示.

图 2中，最左边一列表示指称，中间表示候选实体，最右边一列表示额外添加的与候选实体相连的实体.为了避免引入噪声，只保留与2个或2个以上候选实体都直接相连的实体结点.

2.5.2 重启随机游走

随机游走是遍历图的一个随机过程，该过程收敛后会对应每个结点生成一个概率分布值，表示该结点被访问到的可能性^{[3, 9]}.用T表示转移矩阵，T中的元素T_ij表示从结点e_i到结点e_j的概率. T_ij的计算公式为

$ {T_{ij}} = \frac{{{w_{ij}}}}{{\sum\limits_{{e_{k \in N({e_i})}}} {{w_{ik}}} }} $

(1)

其中：N(e_i)为与e_i直接相连的结点集合，W_ij为结点e_i和e_j之间的权重(这2个结点在知识库中的共现次数).用r^t表示迭代t次时的概率分布，重启随机游走模型可表示为^[3]

$ {\mathit{\boldsymbol{r}}^{t + 1}} = \left( {1 - \lambda } \right){\mathit{\boldsymbol{r}}^t}\mathit{\boldsymbol{T}} + \lambda \mathit{\boldsymbol{s}} $

(2)

其中：s为初始向量，λ为重启概率.最终达到平稳分布^[3]：

$ \mathit{\boldsymbol{r}} = \lambda {\left( {\mathit{\boldsymbol{I}} - c\mathit{\boldsymbol{T}}} \right)^{ - 1}}\mathit{\boldsymbol{s}}, c = 1 - \lambda $

(3)

2.5.3 语义特征

1) 实体语义特征的计算

对任一实体e_i，重启随机游走初始向量s的设置为：初始向量s中第i个结点对应的分量为1，其余结点为0(s_i=1, s_j =0(j≠i))，这样保证从结点e_i开始随机游走并且每次重启也是从结点e_i开始.之后进行重启随机游走得到的平稳分布即为实体的语义特征.

2) 指称语义特征的计算

计算指称的语义特征时需要将指称的候选实体E_m设置为初始结点并计算候选实体e_i在初始向量s中的对应权重s_i=p(m→e_i). p(m→e_i)表示指称m指代实体e_i∈E_m的概率，计算方法为^[3]

$ P(m \to {e_i}) = \frac{{S(m, {e_i})}}{{\sum\limits_{{e_k} \in {E_m}} {S(m, {e_k})} }} $

(4)

其中S(m, e_i)表示m和e_i之间的语义相似度.利用tf-idf为词语赋予权重并根据词袋模型将指称和实体的上下文分别转换为向量m和e_i，则S(m, e_i)计算方式为^[3]

$ S(m, {e_i}) = \frac{{\mathit{\boldsymbol{m}}{\mathit{\boldsymbol{e}}_i}}}{{\left| \mathit{\boldsymbol{m}} \right||{\mathit{\boldsymbol{e}}_i}|}} $

(5)

然后执行随机游走，得到指称m的语义特征向量.

2.5.4 指称和候选实体之间的语义相似度计算

Guo等^[10]借助KL(Kullback-Leibler)散度来进行语义相似度的计算. KL散度是2个概率分布A和B之间差别的非对称性的度量，可以表示为

$ {D_{{\rm{KL}}}}\left( {\mathit{\boldsymbol{A}}\left\| \mathit{\boldsymbol{B}} \right.} \right) = \mathop \sum \limits_i {A_i}{\rm{lg}}\frac{{{A_i}}}{{{B_i}}} $

(6)

考虑到B_i可能为0的情况，Guo等^[10]使用KL散度公式为

$ {D_{{\rm{KL}}}}\left( {\mathit{\boldsymbol{A}}\left\| \mathit{\boldsymbol{B}} \right.} \right) = {\rm{ }}\mathop \sum \limits_i {A_i}\left\{ \begin{array}{l} {\rm{lg}}\frac{{{A_i}}}{{{B_i}}}\;\;\;{B_i} \ne 0{\rm{ }}\\ \gamma \;\;\;{\rm{ }}{B_i} = 0 \end{array} \right. $

(7)

其中γ为一个实数.

然而，由于KL散度是非对称的度量，参数γ依据经验值设定，不具备一般性.

针对以上不足，笔者使用Hellinger距离来度量2个概率分布的差异.概率分布A和B的Hellinger距离为

$ H\left( {\mathit{\boldsymbol{A}}, \mathit{\boldsymbol{B}}} \right) = \frac{1}{{\sqrt 2 }}\sqrt {\sum\limits_{i = 1}^K {{{(\sqrt {{A_i}} + \sqrt {{B_i}} )}^2}} } $

(8)

由式(8)可以看出，Hellinger距离具有非负性和对称性，可以很好地满足实验需求.指称和候选实体之间的语义相似度ψ(m, e_i)计算公式为

$ \psi (m, {e_i}) = \frac{1}{{H(C({e_i}), C\left( m \right))}} $

(9)

其中：C(e_i)表示候选实体e_i∈E_m的语义特征，C(m)表示指称的语义特征.将指称m的候选实体按语义相似度得分从大到小排序，取top1作为指称m在知识库中的目标实体.

笔者使用迭代方法进行实体链接，先对歧义性较小的指称进行链接.在每一轮迭代中，通过在图中执行重启随机游走，获得指称和实体的语义特征，然后计算指称m和候选实体e_i之间的语义相似度，找出相似度得分最大的实体作为指称的链接实体.在下一轮迭代过程中，会将m链接到e_i这一结果考虑进去，对图进行剪枝，去掉无关的候选实体并且重新计算概率转移矩阵.然后对剩余指称进行链接，直到所有的指称都链接完毕.如果指称没有候选实体或者指称与候选实体的相似度得分低于一定的阈值，则将该指称表示为NIL.

由于图结构是根据知识库中的实体来构建的，如果流行度较低的实体与其他实体有更多的关联，则该实体也会获得更高的权重，因此对流行度低的实体也有较高的链接准确率.此外，指称的语义特征是根据指称对应的知识库中的实体得到的，从而保证指称和实体相似度计算的一致性和有效性.

2.6 指称聚类

在实体链接系统中，如果存在多个指称在知识库中都无法找到与其对应的实体，则将指代同一实体的指称聚为一簇.

指称聚类模块使用了规则和谱聚类相结合的方法：先使用规则对指称进行粗划分，即如果2个指称m_i和m_j的命名实体类型相同且有相同的表面字符串时将其划为一簇.然后利用谱聚类算法对划分后的指称进行聚类.

3 实验 3.1 实验数据

笔者使用TAC Knowledge Base Population (KBP)2015年的Tri-Lingual Entity Discovery and Linking(TEDL)任务的实验数据.知识库为Freebase，版本为2015年1月份，包括上千万个实体.文本包括中文文本166篇、英文文本167篇和西班牙文文本167篇.总共发现的指称有32 533个，其中在知识库中可以找到其目标实体的有8 817个，在知识库中没有其对应的目标实体的有23 716个.在所有的指称中，15 014个来源于新闻文本，8 702个来源于论坛.

3.2 评价方法

对于实体链接部分要求指称在文本中的位置、指称类型以及指称对应的知识库中的实体id和官方所给的标准答案完全一致，则该指称的链接结果正确.笔者所用的准确率(P)、召回率(R)和F值的计算方法为^[11]

$ P = \frac{{|{N_{{\rm{gold}}}} \cap {N_{{\rm{sys}}}}|}}{{|{N_{{\rm{sys}}}}|}} $

(10)

$ R = \frac{{|{N_{{\rm{gold}}}} \cap {N_{{\rm{sys}}}}|}}{{|{N_{{\rm{gold}}}}|}} $

(11)

$ F = \frac{{2PR}}{{P + R}} $

(12)

其中：N_gold为正确结果，N_sys为实体链接系统得到的结果.

3.3 实验结果及分析

为了验证方法的有效性，笔者重现了文献[9]以及文献[3]中的实验方法，并将实验结果进行对比，如表 1所示.

由表 1可以得出，在KBP2015数据集上，笔者所用实体链接方法优于其他2种实验方法.

经过分析，Alhelbawy等^[9]和李茂林^[3]提出的算法在构建图结构的时候仅考虑了指称的候选实体，当这些候选实体之间没有直接边相连时，算法效果较差(在极端情况下，任意2个候选实体间都不存在直接边相连，算法的性能等同于单一实体链接).由于知识库中的实体有一部分是间接相连的，笔者使用的方法在图结构中引入与2个或2个以上候选实体都有直接边相连的实体，使图结构的构建更加合理，实验结果证明该扩充方法的有效性，与Guo等^[10]的结论一致.此外，笔者利用主题模型对主题相似的文本进行多文本协同实体链接，由于主题相似的候选实体联系更加密切，这样构造的图结构中边的信息便更加丰富，从而提高了算法的性能.

另一方面，笔者采用easy-first思想，即从歧义性较小的指称进行实体链接(歧义性较小的指称链接准确率相对较高)，之后利用已有的链接信息，从剩余的指称中找到歧义性较小的指称进行链接，直到所有指称链接完毕.与李茂林^[3]提出的方法相比，笔者的算法流程更加合理、清晰，因而效果更好.

KBP2015前3名参赛队伍的实验结果如表 2所示.

由表 2中的数据可以看出，笔者提出方法的实验结果排名第1，再次证明了此方法的有效性.

4 结束语

笔者提出了一种基于重启随机游走的实体识别与链接算法，包括预处理、指称发现、指称扩充、候选实体生成、候选实体排序、指称聚类6部分.在KBP2015的TEDL评测任务中实体链接的F值达到了0.665，指称聚类部分的F值达到了0.618，高于其他参赛队伍.同时与前人的工作进行对比，实验结果也证明了本方法的有效性.然而，该算法中仍存在以下不足：①在指称扩充部分，只利用了表面字符串进行扩充，没有考虑指称间的语义关联，虽然对指称类型和在文本中的位置做了限制，还是有可能出现指称扩充错误的情况；②论坛语料中，由于用语随意以及网络新词的使用，对指称的识别和链接造成干扰，需要对互联网信息加以搜集和利用，以便解决这部分问题.