【读论文】Exploiting Web Search to Generate Synonyms for Entities

最近在看Synonym Entity相关的内容。

这篇文章是2009年在WWW上发表的关于同义实体的文章,属于这个task非常早期的文章(没有找到更早的),所以精读了一下。

这篇博客文章记录了这篇paper的核心思想和我阅读时的感悟。


这篇文章主要研究的是在entity extraction的过程中,通过为reference entity table中的entities构建synonym entity的方式来判断candidate string是否表示一个特定的entity。

个人感觉这篇文章本质上还是在进行entity extraction(判断mention到底是什么entity)的工作,但其核心原理是依靠作者提出的另一种document-based similarity function来将原有的candidate string到entity的模糊查询转变为从candidate string到synonym entity的精确查询。

在这个任务转变的过程中,作者提出了一种构建synonym entity的方法,同时依靠构建出的synonym entity来补足entity extraction。

首先,整个文章的核心在于:如果在一个document中存在一个entity,则这个document中应该还包含了大量关于这个entity的同义描述。形式化表达一下:假设\(e\)表示了一个entity内所有的token(即\(e\)是一个set),而\(\tau_e\)是\(e\)的其中一个子集。如果\(\tau_e\)能够identifies \(e\)(即\(\tau_e\)能唯一地标识\(e\)),则有很大的概率\(\theta\)文档中提到的\(\tau_e\)的同时还会提到\(e-\tau_e\)。也就是说文档有很大的概率不但提到了identifying token set,还会提到entity token set去掉identifying token set剩下的哪些token。

很拗口是不是?举个例子来说明一下:例如说起“ThinkPad X61”(\(\tau_e\)),它是“Lenovo ThinkPad X61 Notebook”(\(e\))的一个子集。这个子集\(\tau_e\)能够准确无误地表示\(e\),我们称这个子集\(\tau_e\)为IDTokenSet。如果一个document中所说的entity就是这个\(e\)的话,若document中出现了“ThinkPad X61”,则此处很有可能还会出现“Lenovo”、“Notebook”等token。而这些token应该能够为“将‘ThinkPad X61’确定为‘Lenovo ThinkPad X61 Notebook’这个entity”这件事提供很多的信息。


先不谈这个核心idea,让我们回到entity extraction这个task上来。

entity extraction主要的任务是判断一个candidate string是否是reference entity table中的一个entity。

已经有一些传统方法可以做这件事。例如一个string-based的方法:计算candidate string和reference entity string的similarity(例如Jaccard similarity)。

但是,这种方法存在很多问题。比如相似度很高的两个string不一定就是同一个entity。而且同一个entity也可能有相似度完全不同的多个string表示。所以这种方法就被否定了。

这篇文章提出了一种document-based的similarity function。也就是说如果我们有包含了entity的document,就能算出一个candidate string对特定entity的相似程度:输入(1)candidate string token set、(2)entity token set和(3)document,输出一个similarity来度量candidate string就是指这个entity的可能性。(当然,document也可以有不止一个,可以在多个document上运行一遍这个流程,只要处理好归一化的问题就好)

这其实就是上面我们所提到的核心idea:输入(1)candidate text token set({ThinkPad, X61}),和(2)entity token set ({Lenovo, ThinkPad, X61, Notebook}),和(3)document(包含了各种Token,有可能还包括了ThinkPad, X61, Notebook,当然也可能不包括这些Token)。然后输出一个similarity来表示candidate text string和这个entity的similarity。

但是,这种方法还存在一个challenge:如何找到包含candidate string的document?这篇文章的方式是通过web search engine。

通过向web search engine去query candidate string。我们能得到少量与candidate string高度相关的document。再配合上reference entity table,我们就能去计算这个similarity了!

但是,想想复杂度吧。因为我们只有candidate string的时候,想要知道它到底是哪个entity的时候,我们就要从reference entity table中遍历每一个entity,然后再用上面的方式跑一遍。挑出similarity最大的哪个。但是这显然是太慢了。

所以我们想到先过滤掉一些不可能的entity,即我们可以模糊地先预判一下candidate string跟entity是不是很match。只去挑一些有可能正确的entity来跟candidate string和documents计算similarity。

但是,这就又回到了最开始的问题:两个文本的模糊匹配本身就非常不精确。尤其是candidate string是用户用各种各样的方式来填写的,跟规定好的reference entity之间的模糊匹配效果很不好。

这时,文章提出了一个方法:我们不需要模糊匹配了,我们精确匹配!然而匹配的对象不是entity token本身,而是synonym entity。文章为每一个entity都生成一组同义entity。这时候我们可以用一些很严格的精确匹配的规则,例如:candidate string token的子集必须是entity token set或者是其synonym的token set。如果不满足这条规则,就直接把这个entity排除掉——这个candidate string不可能描述这个entity。这样就降低了算法的复杂性。

所以,现在的任务就转而成为了以下几个: 1. 如何找到一个entity对应的synonym
2. 当有了这个synonym之后,如何来判断candidate string是否就是这个synonym对应的entity。(即本文提出的document-based similarity问题)


仔细展开,这篇文章为所关注的synonym加了一个限定:必须是IDTokenSet。即能够唯一标识entity的一个entity token的子集。(上面有介绍过)。所以上面说的问题的第一个就变成了如何找到一个entity对应的IDTokenSet。

但是只找到IDTokenSet还不够。因为一个entity token的非空子集非常多(\(2^n-1\)个),其中称得上IDTokenSet也有不少。对其中每一个都进行判断显然是没什么意义的。所以这篇文章还提出了一种方法来找到一个IDTokenSet的"border"。即这个IDTokenSet的所有超集(全集为entity token set)应该都是IDTokenSet,而它的子集都不是IDTokenSet。

形式化一下:如果一个集合\(\tau_e\subset e\)能identify一个实体\(e\),则一个集合\(\tau^{'}_e\)(\(\tau_e\subset\tau^{'}_e\subset e\))也能identify这个实体。换句话说,如果\(\tau_e\subset\tau^{'}_e\subset e\),则说明\(\tau^{'}_e\)比\(\tau_e\)更与\(e\)相关。而我们所要的边界就是哪个“介于相关和不相关”的边界。

举例来说,假如“Canon XTI”能唯一地identify “Canon EOS Digital Rebel XTI SLR Camera”。而“Canon EOS XTI”也能唯一地identify它。则“Canon EOS XTI”相当于提供了冗余信息。所以没有必要考虑后者。对于“Canon XTI”来说,它的子集肯定无法表示那个entity,所以最佳的边界IDTokenSet就是“Canon XTI”。


其实在明确了文章的意图之后,需要做的就是把文中脉络所述的两个坑填上。 第一是给定candidate token set和entity token set和documents之后,similarity function。 第二是产生一个恰到好处的IDTokenSet。

对于第一个问题,文章提出了两种similarity函数。都是以\(\tau_e\),\(e\),和\(d\)为输入。(此处\(d\)就是指一篇document,注意:此处的\(\tau_e\)是文档中的一个mention set,而不是前文中的\(e\)的一个子集,论文中符号相同,容易混淆):

\begin{align} g_1(\tau_e,e,d)=\left\{
\begin{aligned} 1 & ~ & \text{if }e\subseteq C(\tau_e,d,p)\\
0 & ~ & \text{otherwise}
\end{aligned} \right. \end{align}

\begin{align} g_2(\tau_e,e,d)=\frac{\sum_{t\in C(\tau_e,d,p)\cap e}w(t)}{\sum_{t\in e}w(t)}
\end{align}

其中\(C(\tau_e,d,p)\)是指在文档\(d\)中所有出现了\(\tau_e\)中任何一个token的地方前后长度为\(p\)所组成的上下文窗口:\(C(\text{\{F150\}, \{Sony, Vaio, F150, is, ...\}, 1})=\{(Vaio, F150, is)\}\)

然后就是定义\(\tau_e\)和\(e\)在所有文档\(W(\tau_e)\)(即用\(\tau_e\)为query在web search engine上检索到的所有文档)上的关系了:

\begin{align} \text{corr}(\tau_e,e,W(\tau_e))=\frac{\sum_{d\in W(\tau_e),\text{ d mentions }\tau_e}g(\tau_e,e,d)}{|\{d|d\in W(\tau_e),\text{ d mentions }\tau_e\}|} \end{align}

文章还引入了一个参数\(\theta\)作为判断\(\tau_e\)是否是\(e\)的IDTokenSet的阈值(若\(\text{corr}(\tau_e,e,W(\tau_e))>\theta\)则说明这个\(\tau_e\)可以作为\(e\)的IDTokenSet)。


使用上面的similarity function来衡量candidate string和reference entity table中的entity的距离需要耗费较大的代价。所以作者提出对reference entity table做一个预处理,并且能够扩展出IDTokenSet。这个方法通过离线生成准确的IDTokenSets,来讲原来的对reference entity table的approximate match问题转换成为对IDTokenSets的exact match问题。这能极大地提高效率和准确率。

这步预处理其实跟上面说到的similarity function的过程一模一样。唯一的区别是上面的\(\tau_e\)表示mention token set,而此时的\(\tau_e\)则表示entity \(e\)的众多子集中的一个。而上面的\(W(\tau_e)\)表示用这个mention去query搜索引擎得到的文档。此时的\(W(\tau_e)\)则表示用这个\(e\)的子集来去query得到的文档。

发出query得到documents之后,也用同样的公式和阈值来判断(\(\text{corr}(\tau_e,e,W(\tau_e))>\theta\))是否将\(\tau_e\)归类为IDTokenSet。

如此就能得到一个经过预处理的由大量synonym entity组成的新的集合。文章继续讲了一些过滤无用\(\tau_e\),来减少搜索引擎query的方法,此处就不详细阐述了。

Friskit

继续阅读此作者的更多文章