候选实体生成策略

候选实体生成

想要进行实体链接的重要一步就是从千万级的实体中找到少量相关的候选实体，使得真实的目标实体尽可能的在这个列表中。其实整个实体链接可以看做信息检索的简化版，即查询通常为较短的文本，候选实体是包含实体名称和多种属性的文档。因此除了传统的通过字符比对的方法确定候选实体列表外，还可以采用 tf-idf、向量、BM25 等模型。

基于字符匹配

基于名称字典的方法

基于名称字典的技术是候选实体生成的主要方法，并被许多实体链接系统所利用。 维基百科的结构提供了一组用于生成候选实体的有用功能，例如实体页面，重定向页面，消歧页面，来自第一段的粗体短语，以及维基百科文章中的超链接。 这些实体链接系统利用这些特征的不同组合来在各种名称及其可能的映射实体之间构建离线名称字典D，并利用该构造的名称字典D来生成候选实体。 此名称字典D包含有关命名实体的各种名称的大量信息，如名称变体，缩写，可混淆的名称，拼写变体，昵称等。
具体地，名称字典D是⟨键，值⟩映射，其中键列是名称列表。 假设k是键列中的名称，并且其值列中的映射值 k：value是一组命名实体，可以称为名称k。 字典D是通过利用维基百科的功能构建的，如下所示：

• 实体页面。 维基百科中的每个实体页面都描述了一个实体，并包含关注该实体的信息。 通常，每个页面的标题是本页描述的实体的最常见名称，例如，总部位于雷德蒙德的大型软件公司的页面标题“Microsoft”。 因此，实体页面的标题被添加到D中的键列作为名称k，并且该页面中描述的实体被添加为k.value。
• 重定向页面。 每个备用名称都有一个重定向页面，可用于引用维基百科中的现有实体。 例如，标题为“Microsoft Corporation”的文章是Microsoft的全名，其中包含指向Microsoft实体文章的指针。 重定向页面通常表示同义词术语，缩写或指向实体的其他变体。 因此，重定向页面的标题被添加到D中的键列作为名称k，并且指向的实体被添加为k.value。
• 消歧页面。 当维基百科中的多个实体可以被赋予相同的名称时，创建消歧页面以将它们分开并包含对这些实体的引用列表。 例如，名为“迈克尔乔丹”的消歧页面列出了具有相同名称“迈克尔乔丹”的13个相关实体，包括着名的NBA球员和伯克利教授。 这些消歧页面在提取缩写或其他实体别名时非常有用。 对于每个消除歧义的页面，此页面的标题将作为名称k添加到D中的键列，并且此页面中列出的实体将添加为k.value。
• 第一段中的黑体短语。 一般而言，维基百科文章的第一段是整篇文章的摘要。 它有时包含一些用粗体写的短语。 Varma等。观察到这些粗体短语总是昵称，别名或本文所述实体的全名。 例如，在Hewlett-Packard实体页面的第一段中，有两个用粗体写的短语（即“Hewlett-Packard Company”和“HP”），它们分别是实体Hewlett-Packard的全名和缩写。因此，对于每个维基百科页面的第一段中的每个粗体短语，将其作为名称k添加到D中的键列，并且将该页面中描述的实体添加为k:value。
• 维基百科文章中的超链接。 维基百科中的文章通常包含链接到本文中提到的实体页面的超链接。 指向实体页面的链接的锚文本提供了非常有用的同义词源和指向实体的其他名称变体，并且可以被视为该链接实体的名称。 例如，在Hewlett-Packard的实体页面中，有一个指向实体William Reddington Hewlett的超链接，其锚文本是“Bill Hewlett”，它是实体William Reddington Hewlett的别名。 因此，超链接的锚文本被添加到D中的键列作为名称k，并且指向的实体被添加为k:value。

使用上述维基百科的这些功能，实体链接系统可以构建字典D.字典D的一部分如表1所示。除了利用维基百科的功能外，还有一些研究利用查询点击日志和Web文档以查找实体同义词，这对名称字典构造也很有帮助。
基于以这种方式构造的字典，为实体mention $m\in M$ 生成候选实体集合Em的最简单方法是key中的名称k与实体mention m之间的精确匹配。 如果某个k等于m，则将实体集合k：value添加到候选实体集合Em中。
除了精确匹配之外，一些方法利用字典D中的实体名称k和实体mention m之间的部分匹配。 这些方法使用的通用规则包括：

• 实体名称完全包含在实体mention中或包含实体mention。
• 实体名称与实体mention中所有单词的首字母完全匹配。
• 实体名称与实体mention共享几个常用词。
• 实体名称与实体mention 具有强烈的字符串相似性。 已经使用了许多字符串相似性度量，例如字符Dice得分，skip bigram Dice得分，汉明距离等。

对于每个实体mention $m\in M$ ，如果key列中的某个实体名称k满足上述规则之一，则将实体集合k：value添加到候选实体集合Em中。 与精确匹配相比，部分匹配导致更高的召回率，但候选实体集中的噪声更多。

字符串匹配技术

最小编辑距离(Levenshtein distance)

目的是用最少的编辑操作（增删替换）将一个字符转换为另一个，比如：

• ‘Lvensshtain’ –>(插入e) ‘Levensstain’
• ‘Levensshtain’ –>(删除s) ‘Levenshtain’
• ‘Levenshtain’ –>(替换a 为 e) ‘Levenshtein’

上面得例子里从 ‘Lvensshtain’ 转为 ‘Levenshtein’ 共操作3次，编辑距离也就是 3。代码为

import difflib

def edit_distance(strA, strB):
    """ Cal Levenshtein distance """
    leven_cost = 0
    s = difflib.SequenceMatcher(None, strA, strB)
    for tag, i1, i2, j1, j2 in s.get_opcodes():
        if tag == 'replace':
            leven_cost += max(i2-i1, j2-j1)
        elif tag == 'insert':
            leven_cost += (j2-j1)
        elif tag == 'delete':
            leven_cost += (i2-i1)
    return leven_cost

Wagner and Fisher distance

它是 Levenshtein 的一个扩展，它将这个模型中编辑操作的代价赋予了不同的权重。

Edit distance with affine gaps

在上面两种算法的基础上，引入了 gap 的概念，将上述的插入、删除和替换操作用 gap opening 和 gap extension 代替，编辑操作的代价用公式表示为
其中 s 是 open gap 的代价， e 是 extend gap 的代价， l 是 gap 的长度。如计算 Lvensshtain 与 Levenshtein间的距离，首先将两个单词首尾对齐，将对应缺少的部分视为gap，如下图中上面和下面单词相比少了第一个e和倒数第三个的e，这是两个gap。下面的单词与上面的比则少了一个s和a，这又是两个gap。加一起一共4个gap，每个长度为1.因此编辑距离为:

Dice 系数

Dice系数用于度量两个集合的相似性，因为可以把字符串理解为一种集合，因此Dice距离也会用于度量字符串的相似性，Dice系数定义如下：
以Lvensshtain 和 Levenshtein为例，两者的相似度为 2 * 9 / (11+11) = 0.82。代码为

def dice(strA, strB):
    """ Cal Dice coefficient """
    if len(strA) + len(strB) == 0:
        return 1
    overlap = intersection(strA, strB)
    return 2.0*overlap/(len(strA) + len(strB))

def intersection(strA, strB):
    """  Calculate the number of same strings between two strings  """
    if not strA or not strB:
        return 0
    strA_list = list(strA)
    strB_list = list(strB)
    overlap = 0
    for sa in strA_list:
        if sa in strB_list:
            overlap += 1
            strB_list.pop(strB_list.index(sa))
    return overlap

Jaccard系数

Jaccard 系数适合处理短文本的相似度，定义如下：
可以看出与Dice系数的定义比较相似。

def Jaccard(strA, strB):
    """ Cal Jaccard coefficient """
    if len(strA) + len(strB) == 0:
        return 1
    overlap = intersection(strA, strB)
    return overlap/(len(strA) + len(strB) - overlap)

def intersection(strA, strB):
    """  Calculate the number of same strings between two strings  """
    if not strA or not strB:
        return 0
    strA_list = list(strA)
    strB_list = list(strB)
    overlap = 0
    for sa in strA_list:
        if sa in strB_list:
            overlap += 1
            strB_list.pop(strB_list.index(sa))
    return overlap

TF-IDF

TF-IDF 主要用来评估某个字或者用某个词对一个文档的重要程度。其中：
举个例子，比如某个语料库中有5万篇文章,含有“健康”的有2万篇,现有一篇文章,共1000个词,‘健康’出现30次,则sim TF-IDF = 30/1000 * log(50000/(20000+1)) = 0.012。

从本地文档扩展表面形式

由于某些实体mention的是首字母缩略词或其全名的一部分，因此一类实体链接系统使用表面形式扩展技术来识别实体mention 出现的相关文档中的其他可能的扩展变体（例如全名）。 然后，他们可以利用这些扩展形式来使用其他方法生成候选实体集，例如上面介绍的基于名称字典的技术。

基于启发的方法

对于以首字母缩略词形式mention 的实体，一些方法通过启发式模式匹配搜索实体mention的文本上下文来扩展它。他们利用的最常见模式是与扩展相邻的括号中的缩写（例如，Hewlett-Packard（HP））以及与首字母缩略词相邻的括号中的扩展（例如，UIUC（University of Illinois at Urbana-Champaign） ））。此外，一些研究人员从整个文件中确定了扩展形式，其中实体mention是通过基于N-Gram的方法定位的。他们在删除与首字母缩略词字符具有相同首字母的停用词后，检查整个文件中是否存在“N”个连续词。如果存在，他们会将这些’N’连续词视为首字母缩略词的扩展形式。此外，Varma等人和Gottipati和Jiang 使用现成的命名实体识别器（NER）来识别文档中的命名实体，如果一些识别出的命名实体包含实体mention为子字符串，他们将此命名实体视为实体mention的扩展形式。例如，如果NER将“Michael I. Jordan”标识为实体mention“Jordan”的文档中的人名，则“Michael I. Jordan”被视为mention“Jordan”的实体的扩展形式。 Cucerzan 采用首字母缩略词检测器，利用Web数据识别首字母缩略词的扩展。

监督学习的方法

前面基于启发式的表面形式扩展方法无法识别某些复杂缩写词的扩展形式，例如交换或遗漏的首字母缩写词（例如，“CCP”代表“Communist Party of China””和“DOD”代表“United States Department of Defense“）。张等人。 提出了一种监督学习算法，用于找到复杂缩写词的扩展形式，与最先进的首字母缩略词扩展方法相比，可以提高15.1％的准确度（实体连接的评估指标将在5.1节中介绍）。具体来说，他们通过一些预定义的策略（包括文本标记（例如“Hewlett-Packard（HP）”和“HP（Hewlett-Packard）”）和首字母匹配（即所有单词序列）确定了文档中可能的候选扩展。以与首字母缩略词相同的第一个字母开头并且不包含标点符号或超过两个停用词的文档被提取作为候选扩展。例如，从“Communist Party of China leaders have granted the …”这句话来看，就“CCP”这个缩写而言，他们提取了“Communist Party of China leaders have”，其中包含两个停用词及其所有子词，从第一个匹配单词作为候选扩展。然后将每对首字母缩略词和其候选扩展之一表示为特征向量，包括词性特征和首字母缩略词与扩展之间的对齐信息。将SVM（支持向量机）分类器应用于每个候选首字母缩略词 – 扩展对以输出置信度得分。对于每个首字母缩略词，选择具有最高分数的候选扩展。该分类器的训练数据包括170个首字母缩略词，以及它们从首字母缩略词所在的文档中扩展。

基于检索的方法

通过 ElasticSearch 等搜索引擎， 在完全基于字符匹配的基础上，对不同的字符赋予不同的权重，从而剔除查询实体中不重要的部分。除此之外还特别的快，适合在海量数据时使用。