Trading accuracy for faster named entity linking

Trading accuracy for faster entity linking Kristy Hughes Joel Nothman e -lab, School of Information Technologies University of Sydney NSW 2006, Australia {khug2372@uni.,joel.nothman@,james.r.curran@}sydney.edu.au James R. Curran Abstract Named entity linking (NEL) can be applied to documents such as financial reports, web pages and news articles, but state of the art disambiguation techniques are currently too slow for web-scale applica- tions because of a high complexity with re- spect to the number of candidates. In this paper, we accelerate NEL by taking two successful disambiguation features (popu- larity and context comparability) and use them to reduce the number of candidates before further disambiguation takes place. Popularity is measured by in-link score, and context similarity is measured by lo- cality sensitive hashing. We present a novel approach to locality sensitive hashing which embeds the pro- jection matrix into a smaller array and ex- tracts columns of the projection matrix us- ing feature hashing, resulting in a low- memory approximation. We run the linker on a test set in 63% of the baseline time with an accuracy loss of 0.72%. 1 Introduction Named entity linking (NEL) (Bunescu and Pasca, 2006; Varma et al., 2009; Cucerzan, 2007) is the task of mapping mentions of named entities to their canonical reference in a knowledge base (KB). Recently, this task has been motivated by the Text Analysis Conference (TAC) Knowledge Base Population (KBP) entity linking task. In this task, systems are given queries comprising of a mention string and document ID, and return the referring entity ID from the KB (in this case, Wikipedia) or a NIL ID if the entity is not in the KB. While large amounts of candidate data provides rich information that can be used for disambigua- tion, we show that data transfer and query costs comprise over 51% of running time in the unsu- pervised configuration of Radford (2014). Addi- tionally, whole document approaches for disam- biguation compare text using methods such as co- sine similarity, but are slow for high-dimensional data such as text (Indyk and Motwani, 1998). In this paper, we pre-filter candidates using a combination of candidate popularity and context similarity. These features are complimentary to each other, because a high in-link count suggests that the mention string refers to that entity fre- quently, but a high similarity measure is required for less popular candidates. Since context compar- ison is expensive to compute, we use LSH (Gio- nis et al., 1999) to produce a compact binary hash representation of each document, which can be compared using Hamming distance. This fast, in- formed pre-filtering reduces data communication costs and the number of similarity comparisons. While LSH has been shown to be a good approx- imation to cosine similarity on image data (Lu et al., 2008), we show that it this is also the case on text data. Using a hash size of 1024 bits, LSH simi- larity and cosine similarity have a Spearman corre- lation of 0.94, with correlation increasing as hash size increases. Using a hash size of …

Content truncated to 500 words