To advance the Web of Linked Data, mapping ambiguous names in structured and unstructured contents onto knowledge bases would be a vital asset. State-of-the-art methods for Named Entity Disambiguation (NED) face major tradeo s regarding e ciency/scalability vs. accuracy. Fast methods use relatively simple context features and avoid computationally expensive algorithms for joint inference. While doing very well on prominent entities in clear input texts, these methods achieve only moderate accuracy when fed with di cult inputs. On the other hand, methods that rely on rich context features and joint inference for mapping names onto entities pay the price of being much slower. This paper presents AIDA-light which achieves high accuracy on di cult inputs while also being fast and scalable. AIDA-light uses a novel kind of two-stage mapping algorithm. It rst identi es a set of \easy" mentions with low ambiguity and links them to entities in a very e cient manner. This stage also determines the thematic domain of the input text as an important and novel kind of feature. The second stage harnesses the high-con dence linkage for the \easy" mentions to establish more reliable contexts for the disambiguation of the remaining mentions. Our experiments with four di erent datasets demonstrates that the accuracy of AIDA-light is competitive to the very best NED systems, while its run-time is comparable to or better than the performance of the fastest systems.
H.3.1 [Information Storage and Retrieval]: Content Analysis and Indexing
The Web of Linked Data [
In computational linguistics, the problem of mapping
ambiguous entity mentions (or just mentions for short)
occurring in natural-language texts onto a set of known
target entities is referred to as Named Entity Disambiguation
(NED). State-of-the-art NED methods [
Based on our prior experience with AIDA, this paper reconsiders the design space of possible context features and mapping functions, in order to develop an NED system that achieves both high throughput and high output accuracy. We present the AIDA-light system that performs very well even on di cult input texts, while also being as e cient as the fastest methods. AIDA-light employs simpler features than AIDA, thus reducing computational cost, and also adds a new kind of feature: thematic domains like pop music, football, skiing, etc. A major novelty of AIDA-light is its two-stage mapping algorithm: First, our method identi es a set of \easy" mentions which exhibit low ambiguity and can be mapped onto entities with high con dence. The second stage harnesses this intermediate result by inferring the primary domain of the input text and uses this as an additional feature to establish more reliable contexts for the remaining, more di cult, mentions.
Running Example. Consider the following natural-language input sentence as a running example: \Under Fergie, United won the Premier League title 13 times." It is obvious that the above mentions of \Fergie" and \United ", with hundreds of candidate entities, are more ambiguous than the mention of \Premier League", which exhibits just a few candidate entities when using a DBpedia/Wikipediabased set of target entities. So the risk of disambiguating the mention \Premier League" incorrectly is fairly low. Moreover, once we x this mention to the entity Premier_League, the English professional football league, we can infer that the above text snippet likely (and primarily) relates to the general domain of \Football". Within the context of this domain, it thus becomes easier to map \United " to the entity Manchester_United_F.C. (rather than to United_Airlines) and \Fergie" to the entity Alex_Ferguson (rather than to Fergie_(singer) or Sarah,_Duchess_of_York). 1.2
Bunescu and Pasca [
Collective-learning models perform a joint mapping of all
mentions [
In addition, some of these high-accuracy NED methods
also face high computational cost due to their rich contextual
features, most notably, key phrases of entities, entity-entity
relatedness measures, and corresponing statistics [
Fast NED methods, on the other hand, use simpler
features, for example, only characteristic words and
precomputed statistics. By the more compact feature space, they
also avoid interacting with databases and instead use
customized in-memory data structures. The probably fastest
publicly available NED systems are TagMe [
We summarize the novel aspects of this work as follows. AIDA-light makes a judicious choice of contextual features to compute pairwise mention-entity and entity-entity similarities. These feature functions allow us to store the underlying context statistics with low memory footprint, which contributes to faster processing.
AIDA-light is the rst approach that harnesses a thematic domain hierarchy to capture measures for domain-entity and entity-entity coherence.
AIDA-light employs a novel two-stage algorithm in which we determine the \easy and low-cost" mappings rst. By doing so, we reduce both the complexity and di culty of the second-stage disambiguations.
AIDA-light is a complete system for NED, which is orders of magnitude faster than AIDA while achieving comparable output quality. Our experimental comparisons against AIDA, Spotlight, and Illinois Wiki er show that AIDA-light is consistently close to the best competitor (or is even the best) in terms of both run-time and accuracy.
As shown in Figure 1, AIDA-light focuses on the
disambiguation of named-entity mentions in natural-language
input texts such as news articles, Web pages and Wikipedia
articles. We assume that the mentions in the input text have
been recognized and annotated by an NER tool, such as the
Stanford tagger [
In its rst processing stage, AIDA-light divides the
sequence of mentions as they have been marked in the input
text into two parts using its mention partitioner component.
This form of partitioning is based on the number of
possible candidate entities each of the mentions can be mapped
to in the background KB. At this stage, we thus focus on
detecting easy mentions, i.e., those mentions with very few
candidate entities, which exhibit a low level of ambiguity
and thus can be mapped to the correct target entity with
high con dence. Once these easy mentions are xed to their
respective sets of target entities, the more general domain
of the input text is discovered via the entity-domain
dictionary. For example, if there are multiple occurrences of
football clubs in the text snippet, then the text likely
relates to the domain \Football". The chosen target entities
(a) The system architecture.
(b) The collective mapping algorithm [
Figure 2 illustrates how AIDA-light processes our earlier example sentence \Under Fergie, United won the Premier League title 13 times." After the preprocessing steps (including tokenization and NER) are performed, a sliding window is contiguously moved over the resulting token and mention sequences, thus keeping the current mention that is about to be disambiguated at the center of the window. Hence, for each further mention that we disambiguate, this window is moved forward. Both surrounding tokens and mentions within this window are taken into the context of this central mention. We remark that in this example, some intermediate results are hidden. For example, the tokenizer (e.g. Stanford tokenizer) splits \Premier League" into two tokens \Premier" and \League"; however, these two tokens create a mention based on the results of NER, and thus AIDA-light only considers this phrase as a single unit. As shown in the gure, the ambiguities of the three mentions in our example sentence vary substantially. The mention \Premier League" is mapped to only very few candidate entities (even just to one in this example). Thus, we obtain a high-con dence disambiguation of this mention to the entity Premier_League. Thanks to this entity and the domain hierarchy, which maps an entity to its respective domains (such as football, politics, etc.), AIDA-light is able to predict that the text relates to the domain \Football". As a result, it is now much easier to choose also the correct entities for the other mentions, for example, to map the mention of \United " to the entity Manchester_United_F.C. rather than to United_Airlines.
As mentioned before, AIDA-light employs a combination
of various feature functions to perform NED via a two-stage
mapping algorithm. Speci cally, we investigate the usage of
seven di erent feature functions that indicate either
1) the likelihood of a mention M within its given textual
context to represent a named entity E out of a set of
known entities E in our background KB, or
2) the coherence (i.e., the semantic similarity) of a pair of
entity candidates E1,E2 2 E with respect to this KB.
These feature functions, which are de ned in detail in the
following subsections, partly consist of simpli ed context
features used in AIDA (e.g., using sets of plain key tokens
instead of sets of key phrases as in [
Token Sequences. We start by tokenizing a given input
text into a token sequence T = hT1; : : : ; Tti of white-space
and punctuation separated terms. All tokens used as
input for our context features are stemmed using the Porter
stemmer. This token sequence serves as input to the various
context features employed by the disambiguation algorithm.
Mention Sequences. We assume that a subset T0 T
of these tokens has been annotated as a sequence of
mentions M = hM1; : : : ; Mmi by an auxiliary NER tool (using,
e.g., the Stanford [
Mention Dictionary. In addition to the NER
function, we also assume the availability of a dictionary function
Dict : M ! 2E that identi es the set of candidate entities
Ej E for a given mention Ej := Dict (Mj ) to be provided as
input to our NED algorithm. Just like AIDA [
Dictionary Augmentation via LSH. In order to
improve recall over a variety of input texts, including Web
1YAGO2.4.0 - http://www.mpi-inf.mpg.de/yago-naga/yago/
pages where many out-of-dictionary mentions occur, we
apply Locality Sensitive Hashing (LSH) in combination with
a min-wise permutation scheme [
We remark that, according to the above de nitions, two or more mentions, which are represented by identical tokens occurring at di erent locations in the input sequence may be mapped to di erent entities. That is, the same annotated name may very well be disambiguated to di erent meanings if this name occurs at di erent positions of the input text.
We next explain how we maintain the contexts of both mentions and candidate entities which form the basis for the actual disambiguation step. 3.1.1
The mention context is extracted from the annotated text snippet T that contains a mention Mj which we aim to disambiguate. For both e ciency and robustness reasons, this mention context is limited to a sliding window M0 = hMj k; : : : ; Mj; : : : ; Mj+ki with 2 k + 1 mentions that surround Mj. Similarly, we consider also a sliding window T0 = hTi l; : : : ; Ti; : : : ; Ti+li of 2 l + 1 tokens surrounding Mj, such that Mj = NER(Ti).
Domains. Within such a mention context, each candidate entity E 2 E may be assigned to (i.e., be mapped to) zero or more domains via a domain function Dom : E ! 2D. This set of domains D consists of the collection of 46 manually selected classes 2 (such as \Football") of the subclassOf hierarchy of YAGO2 shown in Figure 3. As inherited from the original subclassOf relation, these 46 domains form a DAG structure.
In the rst stage of the NED algorithm, both neighboring tokens and mentions that fall within their respective sliding windows are taken into account by our disambiguation algorithm. Later, as the algorithm proceeds from its rst to its second stage, the context of a mention might hold extra information such as the domains that the neighboring mentions under this context are associated with. At the rst stage, however, these domains are unknown, and the iterative mapping described in Section 4.2, updates the mention contexts after the rst round by the set of chosen entities and their respective domains. 3.1.2
In analogy to the mention context, the entity context is
used to describe each entity E out of the set of known entities
E with respect to a given background KB such as YAGO2.
We focus on two main components for this purpose. The
rst is a set of key tokens extracted from all the key phrases
provided by AIDA for the respective entity. The second
component consists of a set of Wikipedia categories which
is again obtained from YAGO2 as the background KB.
Key Tokens. Each entity E 2 E is assigned to zero or more
key tokens of type string via a token function Tok : E !
2string . These tokens are obtained by simplifying the key
phrases provided by AIDA [
Both of these components together form the basis for de ning the pairwise coherence of two entities, or the pairwise similarity between a mention and an entity if the domains are known, respectively. 3.2
For the following steps, we consider only sets of candidate entities Ei = Dict (Mi). That is, we consider only 2The 46 domains: badminton, baseball, basketball, cricket, football, golf, table tennis, rugby, soccer, tennis, volleyball, cycling, skating, skiing, hockey, mountaineering, rowing, swimming, sub, diving, racing, athletics, wrestling, boxing, fencing, archery, shing, hunting, bowling, agriculture, alimentation, architecture, computer science, engineering, medicine, veterinary, astronomy, biology, chemistry, earth, mathematics, physics, economy, fashion, industry, politics. for those mentions Mi that occur in the mention context M0 = hMj k; : : : ; Mj; : : : ; Mj+ki of a mention Mj that is about to be disambiguated. Moreover, these mentions need to match an entry in our mention dictionary as described earlier. Both these points help us to signi cantly reduce the amount of candidate entities for a given mention. 3.2.1
The function prior re ects the likelihood that a mention Mi refers to an entity Ei;j with respect to the link structure of Wikipedia. It is thus de ned as the relative frequency with which a link with anchor Mi points to a Wikipedia article representing entity Ei;j . 8Mi 2 M0; 8Ei;j 2 Ei := Dict (Mi ) : f1(Mi; Ei;j ) := prior (Mi; Ei;j) := count(Mi ! Ei;j) count(Mi) (1) The respective counts are obtained from a recent WikiMedia dump of English Wikipedia articles3. Each such count is normalized by the number of times Mi occurs as an anchor among all links in Wikipedia. It thus produces a real value in the range [0; 1]. 3.2.2
The similarity between a mention (e.g., \Obama") and an entity name (e.g., Barack_Obama) is measured by the Jaccard similarity over 3-gram character sequences extracted from the respective mention and entity strings. 8Mi 2 M0; 8Ei;j 2 Ei := Dict (Mi ) : f2(Mi; Ei;j ) := Jaccard (Mi; Ei;j ) := j3 -grams(Mi) \ 3 -grams(Ei;j)j (2) j3 -grams(Mi) [ 3 -grams(Ei;j)j White-spaces and truncators (such as \ ") are removed from the input strings before the 3-grams are generated. Hence, Jaccard also produces a real value between 0 and 1. 3.2.3
The function context similarity de nes how similar the token context T0 = hTi l; : : : ; Ti; : : : ; Ti+li surrounding a mention Mi and the key tokens Tok (Ei;j ) of an entity candidate Ei;j are. 8Mi 2 M0; 8Ei;j 2 Ei := Dict (Mi ) : f3(Mi; Ei;j) := Overlap(T0; Tok (Ei;j)) :=
jT0 \ Tok (Ei;j)j min(jT0j; jTok (Ei;j )j) (3) It is thus estimated as the overlap coe cient of tokens extracted from the mention context T0 and the key tokens Tok (Ei;j ) (thus using word stems as tokens and excluding stopwords). It produces a real value between 0 and 1. 3.2.4
This feature function measures the semantic coherence among mentions Mt within the context of a mention Mi which we aim to disambiguate. Thus, given the mention context M0 = hMi k; : : : ; Mi; : : : ; Mi+ki that is surrounding a mention Mi, this feature function computes the pairwise coherence between Mi and the remaining mentions Mt 2 M, t 6= i, based on their co-occurrence counts in Wikipedia. 3http://dumps.wikimedia.org/enwiki/20130103/ For example, if there is a pair of mentions \Victoria" and \David Beckham", then \Victoria" tends to be mapped to Victoria_Beckham and \David Beckham" to David_Beckham, respectively.
:=
This features thus resembles the conditional probability P (Ei;j jMt) that an entity Ei;j occurs when we are given a surrounding mention Mt. In YAGO2, this probability is again estimated over an English Wikipedia dump by counting how many times entity Ei;j and mention Mt occur together in an article. This count is normalized by the absolute number of times mention Mt occurs (i.e., using count (Mt)) in all articles. In order to avoid counts of zero, we apply a simple smoothing technique for our implementation by assigning 1 to unseen mention-entity pairs. This already produces a real value from 0 to 1. However, it is quite small in most cases. And thus, we apply a linear normalization to all values among the candidate set Ei of a mention. 3.2.5
The entity-entity context coherence function nally reects the pairwise relatedness between the two entities via their key tokens sets Tok (Ei;j ) and Tok (Et;v). 8Mi; Mt 2 M0; 8Ei;j 2 Ei := Dict (Mi ); 8Et;v 2 Et := Dict (Mt ) : f6(Ei;j ; Et;v) := :=
Overlap(Tok (Ei;j ); Tok (Et;v))
jTok (Ei;j ) \ Tok (Et;v)j min(jTok (Ei;j )j; jTok (Et;v)j) (5) It is once more computed as the overlap coe cient of two key tokens sets. It produces a real value from 0 to 1. 3.3
3.3.1
Despite the obvious usefulness of Wikipedia categories for
estimating the coherence of two entities or the coherence of
an entity and a domain, there|so far|has not been much
work investing this particular issue. We thus propose to
build hierarchies between Wikipedia categories (instances
of the type relation) and domains (leafs in the subclassOf
relation system). Both kinds of semantic relations are
available in YAGO2 [
Once these hierarchies (as shown in Figure 3) are built, the coherence between two such domains, or between a category and a domain, can be computed as the inverse of the length of the shortest path between them in this hierarchy. In addition, this feature may help to predict the domain of the input text when some of the mentions with low ambiguity are already xed to entities, which results in a better local similarity estimation for the remaining, more ambiguous mentions. For example, if a number of \easy mentions" have been mapped to soccer players, clubs or leagues, we can predict that the text likely relates to the domain \Football". 3.3.2
The domain-entity coherence function re ects the (binary) relevance of assigning an entity to one of the prede ned domains (e.g., \Football").
f5(Mi; Ei;j ) := 8Mi 2 M0; 8Ei;j 2 Ei := Dict (Mi ); Domains D : 8 < 1
9D 2 D ^ Ei;j 2 D : 0
otherwise
In case a chosen entity candidate Ei;j belongs to one of our prede ned domains D, we are thus able to take the coherence between this entity candidate and the domain hierarchy into account. This feature function only produces a binary value of 0 or 1, which re ects whether there is a domain D 2 D holding Ei;j , or not. 3.3.3
When using both YAGO2 or DBpedia 3.8 as background KB, Wikipedia categories (such as wiki-category:English_ footballers or wiki-category:FIFA_World_Cup) may provide good hints on the coherence among pairs of entities, especially for long-tail entities with otherwise poor context information. The entity-entity category coherence function thus estimates the relatedness between the two entities via their assigned Wikipedia categories Cat (Ei;j ) and Cat (Et;v). 8Mi; Mt 2 M0; 8Ei;j 2 Ei := Dict (Mi ); 8Et;v 2 Et := Dict (Mt ) : f7(Ei;j ; Et;v) := Coherence(Cat (Ei;j ); Cat (Et;v)) 1 :=
max Ci;j;x 2Cat(Ei;j) Distance(Ci;j;x ; Ct;v;y )
Ct;v;y 2Cat(Et;v) Here, the function Distance of two categories is computed as the shortest path between them in a domain hierarchy D.
It is computed as the maximum coherence over all pairs of Wikipedia categories the two candidate entities belong to. The coherence of a category pair can be computed by using the domain-hierarchy described above. It produces a real value from 0 to 1. 3.4
To aim for a robust disambiguation algorithm, we combine the seven individual feature functions described above into a single objective function (all functions except prior are computed at runtime). In doing so, we disambiguate the entire sequence of mentions occurring in an input document jointly. Thus let MD = hM1; : : : ; Mki denote this sequence of mentions occurring in the input document, and let ED = hE1; : : : ; Eki, Ei 2 Dict (Mi ), denote its corresponding set of disambiguated entities. We select exactly one entity candidate Ei for each mention Mi 2 MD, i = 1::k subject to the following optimization objective NED : 2M ! 2E.
NED(hM1; : : : ; Mki) := hE1; : : : ; Eki := argmaxE12Dict(M1 ) X pj fj (Mi; Ei) + j=1::5 i=1::k
Ed2Dict(Mk ) X pj fj (Et; Ev) j=6::7 t=1::k v=1::k t6=v (8) such that P pj = 1 and p6 + p7 = 1.
j=1::5 The rst ve feature functions f1; :::; f5 thus re ect the likelihood of choosing an entity based on the respective mention and entity contexts, while functions f6 and f7 compute the pairwise coherences among the chosen entities.
We remark that, as described before for the feature functions, the mention context for each mention Mi 2 MD still is based on a sliding window of mentions M0 and tokens T0 surrounding that mention (see Section 3.1.1).
We construct a weighted, undirected dependency graph
whose nodes are formed by all mentions and their candidate
entities, and whose weighted edges are created by the
feature functions described in the previous section [
The mention-entity dependency graph (see Figure 1 for an example) is typically dense on the entity side, often having hundreds or thousands of nodes because there might be many candidate entities for common mentions (e.g., common rst names, last names, etc.). Therefore, in order to stay e cient, we rst propose to keep at most k of the best entity candidates for each mention in the graph. Thanks to the multi-phase computation (see the next subsection), which iteratively updates the context and thus gives a better initial mention-entity similarity estimation, this cut-o at the top k (even with fairly small values of k, e.g., k = 5) does not a ect accuracy too much. Second, an entity node which is not the last remaining candidate entity of a mention
Require: Weighted dependency graph of mentions and entities.
Ensure: Best sub-graph with one edge per mention. 1: //build the graph 2: for each mention M do 3: for each candidate entity Ei of mention M do 4: sim(M; Ei) := P ptft(M; Ei); //local similarity t=1::5 5: end for 6: Keep the k best candidates, drop the others; 7: end for 8: for each candidate entity Ei of mention M do 9: Wi := sim(M; Ei); //init weight 10: for each entity Ej not generated from mention M do 11: //compute coherence 12: coh(Ei; Ej ) := p6f6(Ei; Ej ) + p7f7(Ei; Ej ); 13: Wi += coh(Ei; Ej ); //update weight 14: end for 15: end for 16: /*an entity is non-taboo if it is not the last candidate of 17: a mention*/ 18: while graph has non-taboo entity do 19: Determine non-taboo entity node with lowest weight, remove it and all its incident edges; 20: Recompute the weights; 21: end while (and hence a \non-taboo" node), and which holds the currently smallest weighted degree, is iteratively removed from the mention-entity graph as shown in Algorithm 1. 4.2
Current NED approaches either map each mention separately in a \context-free" manner, which cannot capture the intricate coherences among entities, or they map all mentions together in an expensive joint-mapping step. However, in practice the level of ambiguity of various mentions occurring in a text snippet often varies substantially. Often, there are mentions which are not very di cult to disambiguate because of the very few candidates (e.g., less than 4 candidates based on our experiments) that come into question for them. We thus propose to organize the mapping algorithm into 2-stage computation as shown in Algorithm 2.
For each stage of the disambiguation algorithm, we apply the collective mapping algorithm described in the previous subsection by using the 7 features functions from Section 4.1. The unknown context-related domains D0 in the rst stage does not a ect the algorithm because the corresponding feature function f6 only returns 0. The multi-phase computation not only helps to reduce the complexity of collective mapping algorithm but it also contributes to a better local similarity estimation for \highly ambiguous" mentions (in the second stage) by updating the mention contexts such as context-related domains or already chosen entities (from the rst stage). 5.1
Test corpora. We conducted experiments for four different test corpora, with di erent characteristics:
Require: Sequence of mentions M0; 1: Initialize context-related domains D0 := ;; 2: Find sets Ei = Dict (Mi), Mi 2 M0, of \easy mentions" such that jEij 4; 3: Jointly disambiguate sets of candidate entities for these easy mentions using Algorithm 1 and let M00 M0 denote the set of mentions disambiguated after the rst stage; 4: for each domain D 2 D do 5: if at least half of the entities chosen in the rst stage relate to D then 6: add D to D0; 7: end if 8: end for 9: Recompute the mention-entity similarities; 10: Disambiguate M0 M00 using Algorithm 1;
CoNLL-YAGO: The CoNLL-YAGO testb corpus was
originally used in [
WP: The WP corpus [
Wiki-links: We randomly extracted a subset of the Wikilinks dataset 5, consisting of 10665 annotated articles (21643 mentions) with an average article length of 5344 words. They are web-pages in a number of websites including blogspot 6, livejournal 7, etc. Note that in this dataset, the annotated mentions are limited to href anchor texts that point to a Wikipedia page. This way, each article has only a marked-up mentions (often only one or two), although many additional entities are mentioned in the text. Moreover, most annotated mentions refer to prominent entities.
Wikipedia articles: We randomly extract 153 Wikipedia featured articles 8, with a total of 19264 mentions and an average article length of 9487 words. This corpus covers a variety of topics such as football (Arsenal_F.C page), entertainment (Batman page), people (John_Calvin page), etc. For each of these four NED tasks, ground truth is given, either by manual annotation or by the href links in Wikipedia (which, of course, are not given to the NED methods). In all cases, we consider only mentions that refer to individual entities like people, organizations, places, events, etc. We disregard text phrases that refer to general concepts such as \peace", \harmony", \logic", \statistics", etc. In so-called Wiki cation tasks, such as TAC KBP Entity Linking, all Wikipedia articles are considered as targets, including general concepts. For the Web of Linked Data and this paper's emphasis on NED, this does not make sense; hence our focus on individual entities. We implement this restriction by considering only mentions with ground-truth entities that are in both Wikipedia and YAGO (as YAGO does not include general concepts of the above kind).
Parameters. The parameters p1 : : : p7 to combine AIDAlight 's feature functions were manually tuned with the goal of maximizing the precision of AIDA-light on CoNLL-YAGO testa training corpus. Plus, based on our experiments, we chose a sliding window of 11 sentences (5 sentences before, 5 sentences after and the sentence holding the mention) to extract the context of a mention.
Performance measures. Our measure for output quality is the per-mention precision: the fraction of mentions that are correctly mapped to the proper entities. When a system has a choice of abstaining on a di cult mention by reporting \null" although the proper entity is in the knowledge base, we count this as a false mapping. Alternatively, we could count precision only on the non-null entities, and additionally consider the correctly mapped fraction of all entities as recall. However, our notion of precision captures both of these aspects in a single metric.
Our measure for e ciency is the run-time, measured in single-threaded mode with cold caches on a server with 8 (+8 in hyper-threading mode) Intel Xeon CPUs at 2.4GHz and 48GB of memory.
Systems under comparison. We compared AIDA-light against the following state-of-the-art methods:
AIDA [
We did not include TagMe [
In the following, we rst report on experiments with different AIDA-light con gurations, then on our comparison against state-of-the-art baselines regarding output quality, and nally on run-time measurements. 5.2
In order to study the in uence of the di erent assets of AIDA-light, we con gured our system in di erent ways and ran it on the CoNLL data, which presumably is the most di cult one of our four test sets.
One possible concern about our architecture is that the multi-stage algorithm could su er from early mistakes that propagate in the processing pipeline. Our experiments showed a precision of 96% for the \easy" mentions identi ed in stage 1. So this potential concern was not an issue.
A second concern was that using only the top K candidate entities for each mention is risky in potentially missing the proper entity. We compared two di erent settings in this regard:
Top 5: Iteratively updating the context in our multiphase computation is deactivated. The local similarity is computed with the lack of context-related domains. Top 5 with domain coherence: The local similarity is updated by the chosen entities for \easy mentions". That is, the entity-domain coherence is taken into account. Table 1 shows the top-5 precision results for these two settings. When the correct entity of a mention was among the top-5 candidates, we count this stage as being successful, otherwise it is counted as false. The results demonstrate that the context-related domains have substantial bene t: 3% better precision. In general, the precision of 95.2% at this rst stage is very high, especially considering that the CoNLL corpus has very di cult texts (with short contexts, long-tail entity names, metonyms, etc.).
Finally, we report the results of AIDA-light with all mentions on CoNLL, in the following three con gurations: KW: AIDA-light uses the baseline features including a bag of key tokens and surrounding mentions. The collective algorithm is applied in a single round to the entire mention set (deactivating the two-stage approach). KW and easy mentions: the multi-phase computation is activated. However, AIDA-light does not update the context (e.g. domain feature) after the rst round. KW, easy mentions, and domains: All components in AIDA-light including multi-phase computation and domain features are turned on.
The results are shown in Table 2. Obviously, each additional asset helps AIDA-light in gaining output quality. Most notably, enabling \easy mention" disambiguation stage improves precision by almost 4%. Note that this is not at the expense of increased run-time. 5.3
In our experiments, Illinois Wiki er performed poorly with
precision results around 70% or worse, probably because of
code changes (and perhaps resulting bugs) compared to the
version used in [
Table 3 shows the precision results for the three systems. AIDA-light outperforms the other two systems on CoNLL and Wiki-links. Especially, a paired t-test shows that AIDAlight is signi cantly better than Spotlight on both corpora (p-value < 0.01). Particularly on CoNLL, AIDA-light can handle many di cult entities such as football teams mentioned in the form of city names, national sport teams in the form of country names, etc. On Wiki-links, the point that brings 4% higher precision than others is AIDA-light 's strong ability to handle mentions that di er from the o cial names of entities (e.g. \Northwest Fur Company " for the entity North_West_Company). AIDA-light is slightly worse than AIDA on WP, but still much better than Spotlight (20% higher precision). On Wikipedia articles, the best system is AIDA (90.0%), followed by Spotlight (89.6%) and AIDA-light (88.3%). However, there is no signi cant di erence among the three systems.
Overall, AIDA-light consistently exhibits high output quality, whereas Spotlight is inferior on very di cult input texts. AIDA is usually close in performance to AIDA-light, but clearly loses on Wiki-links because of the small number of mentions per document for this test case.
The original AIDA system uses a SQL database as a backend. Therefore, it is an order of magnitude slower that the systems that use customized in-memory data structures. To avoid reporting apples vs. oranges, we exclude AIDA from the following run-time comparisons, leaving us with two competitors: AIDA-light and Spotlight.
Table 4 shows the average run-times per document for the four test corpora. Both systems are very fast. AIDA-light is faster on CoNLL, WP, and Wiki-links, and slightly slower on Wikipedia articles. The reason is that AIDA-light computes coherence including context coherence and type coherence over all entity pairs, and thus, it becomes slower to process large documents with hundreds of mentions.
Table 5 shows the run-times on the Wiki-links corpus in more detail. The reason for choosing Wiki-links is that it is the largest one among our corpora with 10665 documents. The table gives 90% con dence intervals for the per-document average run-time, and also the standard deviation. AIDA-light is much faster than Spotlight on average. However, they are almost the same on the 90% quantile, that is, the 10% longest or most di cult documents. The reason is the increasing complexity of AIDA-light when the number of mentions increases. Overall, however, AIDA-light clearly outperformed its competitor on this dataset.
AIDA-light is a new NED system that reconciles high output quality with fast run-time. Our experiments have shown that AIDA-light consistently performs as well as or better
Avg Running
Time
KW+Easy Mentions
KW+Easy Mentions+Domain
Avg Running
Time
Accuracy
Avg Running
Time 0.47s
Standard Deviation 2250 2810
Mean 1225 1234 352 443 than state-of-the-art competitors, over a variety of corpora including news (CoNLL), di cult and short contexts (WP), Web pages (Wiki-links), and Wikipedia articles.
By its two-stage algorithm, its simple but expressive features including thematic domains, and its low footprint, AIDA-light is geared for high-throughput usage at Web scale. Our measurements showed that AIDA-light can process a typical Web page (from the Wiki-links corpus) within 0.2 seconds on mid-range hardware. Its architecture easily allows it to scale out the processing of a large corpus across the nodes of a cluster or distributed platform. By its small memory consumption, AIDA-light runs well even on low-end nodes of such platforms. Thus, with a single-thread throughput of 5 pages/second, we can process, for example, the complete ClueWeb'12 collection (lemurproject.org/clueweb12/) with ca. 700 Million pages, in about one week (including NER) on a mid-range 32-node, 16 cores-per-node cluster.
Our future work includes further improvements of the multi-stage algorithm, and especially a deeper integration of the mention recognition (NER, currently implemented by the CRF-based Stanford Tagger) with the NED method.