The page Building Fields from Irreducible Polynomials says, in the middle of a proof, that evaluation at a root respects products, and the word evaluation there is a link to Polynomial Rings. On this site the same word is a link in 29 places, this one included. Twenty of them point to Retrieval Evaluation, five to Polynomial Rings, three to Ring Homomorphisms and Isomorphisms and one to Training, Validation and Test Sets. A reader of the algebra proof knows at once which one is meant. How can a program decide which entry a phrase refers to, and how well do the standard methods do when this site's own links are the answer key?
Entity linking is the task of mapping each mention, a span of text that refers to some entity, to that entity's entry in a knowledge base, or to the special label NIL when the knowledge base has no entry for it (Shen, Wang and Han, 2015, §1.2). Here an entity is a thing with an identity, such as a person, a place or a theorem, and the knowledge base is a catalog of entities with names and descriptions, such as Wikipedia or this site's set of pages. The task is also called named entity disambiguation, and when the targets are Wikipedia articles of any kind, concepts as well as named things, it is called wikification (Balog, 2018, §5.1).
Here is the route. First we set out the three steps of a linking system and the alias dictionary on which most systems rest, with commonness, the prior probability of an entity given a mention. Then we derive the relatedness measure of Milne and Witten from the Normalized Google Distance and prove what its sign means. Next we sketch collective disambiguation and describe dense entity retrieval as BLINK does it. Then we define the evaluation measures. Finally we run the methods on this site, where every [[slug|text]] link is a mention annotated with its entity by the page's author. The unit's topic page, Knowledge Stores and Memory for Language Models, places this article; Knowledge Graphs describes the knowledge bases that linking targets. The numbers on the site are computed by tools/experiments/knowledge-stores/entity-linking.py.
The task in three steps
Shen et al. (2015, §1.2) divide a typical entity linking system into three modules, and Balog (2018, §5.3) uses the same division with mention detection added in front when the mentions are not given.
- Mention detection finds the spans that might refer to entities. In many evaluations the mentions are given, and the task starts at the next step.
- Candidate selection narrows the whole knowledge base to a short set $C(m)$ of entities that mention $m$ might refer to.
- Disambiguation picks one entity $e \in C(m)$, or NIL. Shen et al. treat the decision to return NIL as a third module of its own, unlinkable mention prediction, which checks whether the top-ranked candidate is really the referent.
Two facts about language make the task hard, and both appear in the running example. A name can denote several entities: evaluation names four pages here. And an entity can have several names: the page Polynomial Rings is reached on this site by links whose text is polynomial rings, evaluation, degree proposition, integral domain and others. Shen et al. (2015, §1.1) call these name variation and entity ambiguity.
The alias dictionary
Most systems generate candidates from an alias dictionary (a "name dictionary" in Shen et al.'s terms, a "surface form dictionary" in Balog's), a map from each name to the entities it can denote. Shen et al. (2015, §2.1) list the parts of Wikipedia used to build one:
- the title of each entity's page, usually its most common name;
- redirect pages, which exist for alternative names (the page Microsoft Corporation redirects to Microsoft);
- disambiguation pages, which list the entities that share a name;
- bold phrases in the first paragraph of an article;
- the anchor text of links, which records the names that writers actually use (Bill Hewlett as a link to William Reddington Hewlett).
The simplest candidate generation is exact lookup of the mention in the dictionary; partial matching rules extend it (Shen et al., 2015, §2.1). Anchor texts are what make the dictionary large and useful, because every link written by a person is a vote that this phrase names that entity.
Commonness: the prior probability of an entity given a mention
The same anchors also say how often a name is used for each entity. For a name $m$ and an entity $e$, let $n(m, e)$ be the number of links with anchor text $m$ that point to $e$. The commonness of $e$ for $m$ is the share of those links that go to $e$,
$$P(e \mid m) = \frac{n(m, e)}{\sum_{e' \in \mathcal{E}} n(m, e')} ,$$
where $\mathcal{E}$ is the set of entities in the knowledge base (Balog, 2018, eq. 5.3). It is the maximum-likelihood estimate of the probability that a link with this text goes to $e$, before anything about the surrounding text is known. Balog credits the idea to Medelyan, Witten and Milne (2008), whose example is the anchor Jaguar: it appears 927 times as a link in their copy of Wikipedia, 466 of them to the car maker, so that mapping has a commonness of about 0.5, and 203 to the animal, a commonness of 0.22.
Example (commonness of evaluation). Build the dictionary from every page of this site except the algebra page of the opening. The anchor evaluation then occurs 28 times, one fewer than on the whole site, because the algebra page's own link is left out: 20 links to Retrieval Evaluation, 4 to Polynomial Rings, 3 to Ring Homomorphisms and 1 to Training, Validation and Test Sets. The commonness values are $20/28 = 5/7$, $4/28 = 1/7$, $3/28$ and $1/28$. Choosing the entity of highest commonness, the most common sense, links the algebra page's evaluation to Retrieval Evaluation. It is wrong here, and it is the right choice for most uses of the word on this site.
Choosing the most common sense is a strong baseline. Balog (2018, §5.6) calls it "a very reliable indicator of the correct disambiguation", quoting Ratinov et al. (2011). Shen et al. (2015, §3.1.1.2) report that a ranking by Web popularity alone reached 71% accuracy on the TAC-KBP 2010 entity linking task, better than 24 of the systems submitted to it. Ratinov et al. (2011, Table 4) give the accuracy of commonness alone, measured on mentions whose correct entity is among the candidates: 94.05% on ACE, 81.91% on MSNBC, 93.19% on AQUAINT and 85.88% on their Wikipedia sample.
Which phrases are mentions at all: link probability
When the mentions are not given, a system must also decide which phrases deserve a link. The word evaluation occurs on many pages of this site without a link. Mihalcea and Csomai (2007) proposed keyphraseness, the share of the pages containing a phrase in which it appears as a link:
$$P(\text{keyphrase} \mid m) = \frac{\lvert D_{\text{link}}(m) \rvert}{\lvert D(m) \rvert} ,$$
where $D_{\text{link}}(m)$ is the set of pages in which $m$ is the anchor of a link and $D(m)$ the set of pages that contain $m$ at all (Mihalcea and Csomai, 2007, eq. 1; Balog, 2018, eq. 5.1). A closely related link probability counts occurrences in place of pages. Mention detection then keeps the phrases whose keyphraseness passes a threshold. For evaluation, 20 of the other pages of this site use it as the anchor of a link and 387 contain the word, so its keyphraseness is $20/387 = 0.052$. Most occurrences of the word are not links, and a threshold of the kind tuned in the experiment below, between 0.2 and 0.3, would never select it.
Relatedness: how the other entities of a page vote
Commonness ignores the page the mention is on. The algebra page also links, without ambiguity, to Integral Domains and Fields, Irreducible Polynomials and other algebra pages, and those entities are evidence about what evaluation means there. Milne and Witten turned that evidence into a number with a measure of how related two entities are, computed from nothing but links.
The Normalized Google Distance
The measure is modeled on the Normalized Google Distance of Cilibrasi and Vitányi (2007). Its idea is that two words are related in meaning when the pages that contain one also tend to contain the other. Let $f(x)$ be the number of pages containing the term $x$, $f(x, y)$ the number containing both terms, and $N$ the total number of pages. Their equation (III.3) defines
$$\mathrm{NGD}(x, y) = \frac{\max\{\log f(x), \log f(y)\} - \log f(x, y)}{\log N - \min\{\log f(x), \log f(y)\}} .$$
They derive it from an information distance between objects, with page counts standing in for code lengths, and list its properties (their §III.D): it is 0 when the two terms occur on exactly the same pages, it is symmetric, it grows without bound as the overlap shrinks to nothing, and it is not a metric, since it can be 0 for distinct terms and it violates the triangle inequality.
The Wikipedia link-based measure
Milne and Witten (2008a) replaced the pages containing a term by the articles linking to an entity. For two entities $a$ and $b$ with in-link sets $L_a$ and $L_b$, the sets of pages that link to each, the relatedness is one minus the Normalized Google Distance of those sets:
$$\mathrm{WLM}(a, b) = 1 - \frac{\log \max(\lvert L_a \rvert, \lvert L_b \rvert) - \log \lvert L_a \cap L_b \rvert}{\log N - \log \min(\lvert L_a \rvert, \lvert L_b \rvert)} ,$$
with $N$ the number of entities, and the score is set to zero when either entity has no in-links or the two share none (Balog, 2018, eq. 5.4; Shen et al., 2015, §3.1.2.2, give the same formula). On their sample of word pairs this Google-Distance-inspired measure correlated better with human judgments than a TF-IDF-like comparison of out-links, 0.72 against 0.66 (Milne and Witten, 2008a, Table 2). The intuition is the one Milne and Witten state for out-links: two articles both linking to science says little, and both linking to atmospheric thermodynamics says a great deal. The measure rewards a shared in-link more when the two sets are small relative to the whole collection.
What does the sign of WLM mean? Here is the claim in one sentence: WLM is positive exactly when two entities share more in-links than they would if pages chose to link to each of them independently.
The formal version. Assume $\lvert L_a \cap L_b \rvert \ge 1$ and $\min(\lvert L_a \rvert, \lvert L_b \rvert) < N$, so that every logarithm is defined and the denominator is positive. Write $p = \lvert L_a \rvert$, $q = \lvert L_b \rvert$ and $k = \lvert L_a \cap L_b \rvert$. Then
$$\mathrm{WLM}(a, b) > 0 \iff \log \max(p, q) - \log k < \log N - \log \min(p, q) \iff \max(p, q) \cdot \min(p, q) < N k \iff k > \frac{pq}{N} .$$
The first step multiplies the inequality $\text{fraction} < 1$ by the positive denominator. The second adds $\log k + \log \min(p, q)$ to both sides and uses that the logarithm is increasing. The third uses $\max(p, q) \cdot \min(p, q) = pq$. If each of the $N$ pages linked to $a$ with probability $p/N$ and to $b$ with probability $q/N$, independently, the expected number linking to both would be $N \cdot (p/N)(q/N) = pq/N$. So WLM is positive exactly when the observed overlap exceeds that expectation. The same inequality is the condition for $\frac{N k}{p q}$ to exceed 1, that is, for its logarithm, the pointwise mutual information, to be positive. Ratinov et al. (2011, §4.3) use this ratio itself, without the logarithm, as their PMI relatedness. So WLM and their measure agree about which pairs are related more than chance would predict. $\blacksquare$
They do not agree on how related. Equal signs do not make one measure a rescaling of the other, nor even an increasing function of it. Take $N = 1000$. The pair with $p = q = 500$ and $k = 300$ has $\mathrm{WLM} = 1 - \ln(5/3)/\ln 2 = 0.263$ and ratio $1000 \times 300 / 250{,}000 = 1.2$. The pair with $p = 2$, $q = 500$ and $k = 2$ has $\mathrm{WLM} = 1 - \ln 250 / \ln 500 = 0.112$ and ratio $1000 \times 2 / 1000 = 2.0$. WLM ranks the first pair higher, and the ratio ranks the second higher.
Three more properties follow from the formula. The base of the logarithm cancels, since it multiplies numerator and denominator by the same constant. The numerator is never negative, because $k \le \min(p, q) \le \max(p, q)$, so $\mathrm{WLM} \le 1$, with equality exactly when $k = \max(p, q)$, that is, when $L_a = L_b$. And WLM can be negative, when the overlap is below the independence expectation. Balog's statement of the formula does not say what to do then; the experiment below sets negative values to zero, so that an unrelated entity counts as unrelated and no more.
Example (two algebra pages). Counting links from every page of the site except the algebra page of the opening, Polynomial Rings has 12 in-links, Integral Domains and Fields has 18, they share 10, and the site has $N = 850$ pages. Independence would predict $12 \times 18 / 850 = 0.254$ shared in-links, and 10 is far more, so the relatedness is positive:
$$\mathrm{WLM} = 1 - \frac{\ln 18 - \ln 10}{\ln 850 - \ln 12} = 1 - \frac{0.5878}{4.2603} = 0.862 .$$
Retrieval Evaluation, with 27 in-links, shares none with Integral Domains and Fields, so their relatedness is 0.
Disambiguating with relatedness
To use relatedness, a system needs the entities of the rest of the page, the disambiguation context, before it has disambiguated them. Milne and Witten's answer was to take the mentions that are not ambiguous at all: a mention whose dictionary entry has a single entity supplies that entity as context (Balog, 2018, §5.6.2.2). Each candidate of an ambiguous mention is then scored by its commonness and its average relatedness to the context entities. Milne and Witten (2008b, §3.1) went further and weighted each context entity by the average of its link probability and its mean relatedness to the other context entities, so that phrases almost always used as links, and entities on the document's central thread, count more. Balog (2018, §5.6.2.2) points out the approach's weakness: it assumes that unambiguous mentions exist, which in practice means that documents must be long enough to contain some.
In the earlier paper, on pairs of words, Milne and Witten (2008a, Table 3) had compared simple ways of choosing the senses of two terms before measuring their relatedness. Choosing the most common sense of each gave a correlation of 0.68 with human judgments, choosing the most closely related pair of senses 0.69, and weighting commonness and relatedness evenly, "highest (commonness + relatedness)", 0.74. The experiment below uses that even weighting:
$$\mathrm{score}(e; m) = P(e \mid m) + \frac{1}{\lvert X \rvert} \sum_{c \in X} \mathrm{WLM}(e, c) ,$$
where $X$ is the set of context entities other than $e$ itself.
Example (the running mention, scored). The algebra page has 36 link mentions, and 12 distinct entities come from its unambiguous ones. Their average relatedness is 0.691 to Polynomial Rings, which is related to all 12, 0.742 to Ring Homomorphisms, and 0 to Retrieval Evaluation and to Training, Validation and Test Sets. Ring Homomorphisms is itself one of the 12, through another link on the page whose anchor names only it, so its average is taken over the other 11. The scores are
| Candidate | Commonness | Mean relatedness | Score |
|---|---|---|---|
| Ring Homomorphisms and Isomorphisms | 0.107 | 0.742 | 0.849 |
| Polynomial Rings | 0.143 | 0.691 | 0.833 |
| Retrieval Evaluation | 0.714 | 0 | 0.714 |
| Training, Validation and Test Sets | 0.036 | 0 | 0.036 |
Relatedness moves the decision from information retrieval to algebra, as a reader would. It then picks Ring Homomorphisms, not the page the author linked. Both pages are defensible: Polynomial Rings proves the theorem that evaluation respects sums and products, and Ring Homomorphisms presents evaluation as its leading example of a homomorphism and links back to that theorem. The site's own links send the algebraic evaluation to both pages, four times to one and three times to the other. A gold standard written by authors records one acceptable answer, not the only one.
Collective disambiguation, in outline
The method just traced disambiguates each mention separately, with the context fixed in advance. Collective (or global) methods choose all the entities of a document together, so that the assignment as a whole is coherent. Ratinov et al. (2011, eq. 2) write the goal as choosing the tuple of entities $\Gamma = (e_1, \dots, e_n)$ for the mentions $m_1, \dots, m_n$ of a document that maximizes
$$\sum_{i=1}^{n} \phi(m_i, e_i) + \psi(\Gamma) ,$$
where $\phi$ scores how well an entity fits its mention locally (commonness, textual similarity of the mention's context to the entity's page) and $\psi$ scores the coherence of the whole assignment. They note that this problem is NP-hard and that approximations are required. Four approaches show the range.
- A fixed context. Ratinov et al. (2011, eq. 3) replace $\psi(\Gamma)$ by the relatedness of each $e_i$ to an approximate solution $\Gamma'$ computed first, which turns the problem back into separate decisions. Their system GLOW takes $\Gamma'$ to be the predictions of a local disambiguator, so that every mention contributes context, not only the unambiguous ones. The experiment below runs this variant too, with commonness as the local disambiguator.
- Integer programming. Kulkarni et al. (2009) were the first to optimize the coherence directly, as a binary integer linear program relaxed to a linear program, and they found that the relaxation often gives integral solutions; a greedy hill-climbing search was comparable in speed and accuracy (Balog, 2018, §5.6.2.3). Shen et al. (2015, §3.2.3) report 69% F1 on their IITB data set.
- Graphs. Han, Sun and Zhao (2011) build a graph of mentions and candidate entities and run a random walk over it, similar to topic-sensitive PageRank; Shen et al. report an F1 of 73% on the same IITB data. Hoffart et al. (2011) search the mention-entity graph for a dense subgraph with exactly one entity per mention, a problem that is NP-hard because it generalizes the Steiner tree problem, and solve it greedily. On the CoNLL data set those authors built from Reuters news, their best variant linked every mention with a micro-averaged precision, that is an accuracy, of 81.82% (their Table 2), which Shen et al. report as 81.8% accuracy.
- Voting. TAGME (Ferragina and Scaiella, 2010) lets every other mention vote for a candidate with the commonness-weighted average of its candidates' relatedness to it, keeps the candidates whose votes are within the top $\epsilon$ of the scores, and among those takes the one of highest commonness (Balog, 2018, eqs. 5.8 and 5.9). Balog reports $\epsilon = 30\%$ and a computation linear in the number of mentions, citing the system's authors.
How much does coherence add? Ratinov et al. (2011, Table 4) measured it on mentions whose correct entity is a candidate. Adding global features to commonness raised accuracy from 94.05% to 96.75% on ACE, from 81.91% to 88.51% on MSNBC, from 93.19% to 95.91% on AQUAINT, and from 85.88% to 89.79% on Wikipedia, using their predicted context; local features alone did better than global ones on Wikipedia (93.59%), and combining both helped only marginally. Their summary is that "the global approaches marginally outperform the local approaches on ranker accuracy". In the end-to-end evaluation of their Table 6, GLOW's bag-of-titles F1 was above Milne and Witten's system on all four data sets, for instance 90.54 against 80.32 on Wikipedia, and its full version was close to its local version.
Dense entity retrieval: BLINK
The dictionary has a hard limit: an entity can only be a candidate for a name that someone has already used for it. A mention with a name the dictionary has never seen gets no candidates at all. Dense retrieval removes the limit by comparing meanings instead of strings, as Dense Passage Retrieval does for passages. BLINK (Wu et al., 2020) applies it to entity linking in two stages.
The bi-encoder. One transformer encodes the mention in its context, and a second encodes each entity from its title and description (for Wikipedia, the first ten sentences). The mention's input marks the mention with special tokens, [CLS] left context [Ms] mention [Me] right context [SEP], and the entity's input is [CLS] title [ENT] description [SEP]; each is reduced to the vector at the [CLS] token (their §4.1). The score of entity $e$ for mention $m$ is the dot product of the two vectors, $s(m, e) = \vec{y}_m \cdot \vec{y}_e$ (their eq. 3), so that all entity vectors can be computed in advance and the search is the maximum inner product search of the dense retrieval unit. Training maximizes the score of the correct entity against the other entities of the batch (their eq. 4), the in-batch negatives of Contrastive Training for Retrieval, with hard negatives added from the model's own top 10 predictions, as in Hard Negatives and Distillation. The paper's experiments find a mention context of as little as 32 word pieces works well.
The cross-encoder. The top candidates, 64 or 100, are then re-scored by a third transformer that reads the mention's context and the entity's description together, as one input, so that every word of each can attend to every word of the other; a linear layer turns the [CLS] vector into a score (their eqs. 5 and 6). This is the cross-encoder re-ranking of the neural ranking unit, applied to entities. The paper also distills the cross-encoder into the bi-encoder (their §4.3).
What it reported. On the zero-shot entity linking data of Logeswaran et al. (2019), whose test entities come from domains never seen in training, the bi-encoder's recall at 64 on the test set was 82.06% against 69.13% for BM25 (their Table 1), and the full system's accuracy was 63.03% with BERT-large, against 55.08% for the model of Logeswaran et al. (56.58% with that model's domain-adaptive pre-training) (their Table 2). On TAC-KBP 2010 its accuracy was 94.5%, with 92.9% for the bi-encoder alone and 91.5% when linking against all 5.9 million Wikipedia entities without fine-tuning on the task (their Table 4). With full Wikipedia as the knowledge base, the bi-encoder's recall at 100 was 98.3%, against 89.5% for an alias table ordered by commonness (their Table 5, a baseline implemented by Gillick et al., 2019). With approximate nearest-neighbor search, retrieving candidates from 5.9 million entities took about 2 milliseconds per query (1.4 to 2.6 milliseconds for the two approximate indexes of their Table 7, against 9.2 for exact search). One limit is stated in the paper's task definition: it assumes that every mention has its entity in the knowledge base, which "is usually referred as in-KB evaluation", and leaves NIL prediction to future work. A third design generates the entity's name token by token, constrained to real titles, as GENRE does; Generative Retrieval describes it.
Evaluating entity linking
A linker's output is compared with gold annotations, and the measures are those of precision, recall and F applied to links (Shen et al., 2015, §5.1):
$$\text{precision} = \frac{\lvert \text{correctly linked mentions} \rvert}{\lvert \text{mentions linked by the system} \rvert} , \qquad \text{recall} = \frac{\lvert \text{correctly linked mentions} \rvert}{\lvert \text{mentions that should be linked} \rvert} ,$$
with $F_1 = 2PR/(P + R)$. Four choices change what these numbers mean.
- Given or detected mentions. When the gold mentions are given and the system links every one, the number linked equals the number to be linked, and precision, recall and F1 all equal the accuracy, the share of mentions linked correctly (Shen et al., 2015, §5.1). Accuracy is the official measure of the TAC-KBP track.
- In-KB and NIL. A NIL mention should not be linked. Linking it is an error that lowers precision; leaving an in-KB mention unlinked lowers recall. In-KB evaluation, as in BLINK, uses only mentions whose entity is in the knowledge base, which removes the NIL decision from the test.
- Micro or macro. Precision and recall can be pooled over all mentions of a collection (micro-averaged) or computed per document and averaged (macro-averaged) (Balog, 2018, §5.8.1).
- Strict or lenient spans. With detected mentions, a system's span may overlap the gold span without matching it exactly. Balog (2018, §5.8.1) defines a perfect match, which requires the same entity and the same span, and a relaxed match, which requires the same entity and overlapping spans.
A fifth convention compares entities without spans. In the bag-of-titles evaluation used by Milne and Witten (2008b, §4.3) and, following them, by Ratinov et al. (2011), each document's set of linked entities, without duplicates, is compared with the gold set. It suits Wikipedia-style gold data, in which an entity is usually linked once however often it is mentioned. Worked problem 5 computes Ratinov et al.'s example.
Early work used Wikipedia both as the knowledge base and as the gold standard, recovering links that Wikipedia's contributors had made (Balog, 2018, §5.8.2). Later test collections annotated news and web text by hand: for instance, Cucerzan's 20 MSNBC articles with 755 mentions (113 of them NIL), the 107 web pages of the IITB set with 17,200 mentions (40% NIL), and the 1,393 Reuters articles of CoNLL-YAGO with 34,956 mentions (Balog, 2018, Table 5.6).
An experiment: this site's links as gold annotations
This site is a small Wikipedia in the sense that matters here: its pages are the entities, and its authors have written 14,942 links from a phrase to a page. Each link is a mention with its entity attached. The experiment asks the early work's question on that data: given a page whose links have been hidden, how many can the methods above recover?
Setup
The pages are read from the commit pinned by the unit's site-graph module (sitegraph.py), so pages written later, this one included, change nothing. There are 850 pages. Each page is cut into words, with fenced code and display mathematics removed and inline mathematics reduced to its letters and digits. Each link becomes a mention: its anchor text, its position in the word stream and its target page. Links are found as the site-graph module finds them, with code and mathematics masked first, so that a link label containing bracketed mathematics, such as $F[x]$, is read whole. A name is compared in lower case, word by word.
Some statistics of the gold annotations come first, because they set what the methods can gain. The 14,942 mentions use 2,282 distinct anchor texts, and 2,197 of those texts always point to the same page. Only 85 of those texts point to more than one page, and they account for 655 mentions, 4.4% of the total. In 10,217 mentions, 68.4%, the anchor text is the target page's title. Most links on this site name their page in full, which makes them easier to link than the mentions of a news article, where a person may be named by surname alone.
Each of 30 splits (seeds 0 to 29) shuffles the pages and divides them three ways:
- Test pages, 170 (20%), whose mentions are linked and scored.
- Unknown entities, 85 pages (10%), removed from the knowledge base altogether. Their titles are not in the dictionary and their links are not used. A test mention that points to one of them is a gold NIL mention.
- Training pages, the other 595, whose links build the alias dictionary and whose links supply the in-link sets for relatedness. The dictionary also holds the title of every known page, counted once, as a title page would be. In WLM, $N$ is the number of known pages, 765, as in Balog's definition; since the in-links come only from the 595 training pages, the independence threshold $pq/N$ of the proof above is somewhat lower than it would be with $N$ set to the number of pages that can link. No mention on the site points to its own page.
A median split has 2,593.5 in-KB test mentions (the median of an even number of splits) and 301 NIL mentions. Five linkers are compared on the gold mentions, the setting in which mentions are given.
| Linker | Candidates | Decision |
|---|---|---|
| Commonness | the dictionary | the candidate of highest $P(e \mid m)$; NIL when there is no candidate |
| Milne and Witten context | the dictionary | commonness plus mean WLM to the page's unambiguous entities |
| GLOW-style context | the dictionary | commonness plus mean WLM to the commonness predictions of the page's other mentions |
| Bi-encoder | every known page except the mention's own | highest cosine; always links |
| Dictionary, then bi-encoder | the dictionary, or every known page when it has none | commonness; with no candidate, the bi-encoder's top page if its cosine reaches a threshold, else NIL |
The bi-encoder is the unit's pinned model, sentence-transformers/all-MiniLM-L6-v2 at revision 1110a243fdf4706b3f48f1d95db1a4f5529b4d41, through the dense retrieval unit's encoding module. It encodes each mention as its anchor with 32 words of context on each side, and each page as its title followed by its summary. It is not BLINK: it is one network shared by mentions and entities, trained for sentence similarity, never trained to link entities, and it has no mention markers. The threshold of the last linker is tuned on each split's training pages: a quarter of them are linked with a dictionary built from the other three quarters, and the cosine threshold with the best F1 there is kept.
Results with the mentions given
Precision, recall and F1 are micro-averaged over each split's test mentions, as defined in the previous section, and the table gives the median over the 30 splits with the interquartile range in brackets.
| Linker | Precision | Recall | F1 |
|---|---|---|---|
| Commonness | 0.978 [0.974, 0.981] | 0.899 [0.830, 0.917] | 0.935 [0.900, 0.946] |
| Milne and Witten context | 0.979 [0.975, 0.982] | 0.901 [0.831, 0.918] | 0.937 [0.900, 0.947] |
| GLOW-style context | 0.979 [0.975, 0.982] | 0.901 [0.831, 0.918] | 0.937 [0.900, 0.947] |
| Bi-encoder | 0.328 [0.312, 0.340] | 0.366 [0.343, 0.379] | 0.347 [0.327, 0.357] |
| Dictionary, then bi-encoder | 0.977 [0.974, 0.981] | 0.899 [0.831, 0.917] | 0.935 [0.899, 0.946] |
Four observations follow.
Commonness alone is close to the ceiling the dictionary sets. Its precision is 0.978: when it links, it is almost always right. Its recall is lower, and the reason is coverage, not choice. Of the in-KB test mentions of a median split, 8.1% have no candidate at all, because their anchor text was never used on a training page and is not a known page's title. A further 1.1% have candidates that do not include the right page. Only 0.3% have the right page among the candidates and lose it to a more common one. The dictionary contains the right entity for 0.903 of in-KB mentions (median), and that bounds the recall of every dictionary linker.
Relatedness helps a little, and only where it can. The Milne and Witten context raises the median F1 from 0.935 to 0.937; split by split, the median gain is 0.0008, with an interquartile range from 0.0000 to 0.0014. It was better than commonness on 20 of the 30 splits, equal on 6 and worse on 4. Over all 30 splits together it corrected 89 mentions that commonness got wrong and spoiled 24 that commonness got right. The GLOW-style context corrected 88 and spoiled 22. The gain is small because the opportunity is small: in a median split only 2.3% of in-KB mentions have more than one candidate with the right one among them, and only in those can any disambiguation method change the outcome. The running example's evaluation is one of them.
The bi-encoder retrieves well and chooses badly. As a linker it is far behind, with an F1 of 0.347. Its candidates exclude the page the mention is on, as a real linker's would: that page's title and summary resemble the mention's context, and without the exclusion the bi-encoder can return the page itself. The right page is the bi-encoder's first choice for 0.366 of in-KB mentions (median), within its top 5 for 0.696, its top 10 for 0.802 and its top 64 for 0.966. With 64 candidates it covers more mentions than the dictionary, whose candidate sets mostly hold a single page (0.966 against 0.903); with one candidate each, it covers 0.366. For mentions with no dictionary candidate, the cases the dictionary cannot reach, the right page is in its top 10 for 0.741 and its top 64 for 0.941. That is BLINK's division of labor seen from below: a bi-encoder generates candidates with high recall, and a second stage that reads mention and entity together is needed to pick the right one. Our run has no such second stage trained for the task.
The fallback does not pay here. The tuned threshold was 0.85 on 23 splits, 0.9 on 3, 0.8 on 2 and 0.75 on 2, so high that the bi-encoder is almost never trusted: over all 30 splits the fallback changed 38 decisions. On the tuning pages, linking unseen names by the bi-encoder's top choice cost more precision, on NIL mentions and on wrong pages, than it gained in recall.
NIL is easy in this simulation, and that is an artifact. Commonness left 0.962 of the NIL mentions unlinked (median), because the anchors that pointed to a removed page were mostly used for no other page. The simulation produces few NIL mentions whose name is also the name of a known entity, which is the case that makes NIL prediction hard: a linker must then decide that a familiar name refers to something outside the knowledge base.
Results with the mentions detected
The second run starts from the test pages' plain words, with no link markup. Mentions are detected by scanning left to right for the longest word sequence, up to eight words, that is a dictionary name with keyphraseness at or above a threshold $\theta$, where keyphraseness is counted over the training pages. A detected mention is linked by commonness, or by commonness with the Milne and Witten context, and a page never links to itself. The threshold is tuned on the training quarter as before; it came out at 0.25 or 0.3 on 26 splits and 0.2 on 4. Scored as bags of titles, micro-averaged over the test pages:
| Linker | Precision | Recall | F1 |
|---|---|---|---|
| Commonness | 0.853 [0.845, 0.865] | 0.862 [0.840, 0.876] | 0.859 [0.849, 0.864] |
| Milne and Witten context | 0.855 [0.847, 0.866] | 0.863 [0.842, 0.876] | 0.859 [0.849, 0.865] |
The end-to-end F1 of 0.859 is below the 0.935 of the given mentions, and the loss is in detection. A page links a phrase when its author chose to, and the detector proposes links wherever a linkable name appears, so some of its "errors" are links an author could reasonably have made. Others are real misses: a page's gold links include names that no training page used.
What the experiment can and cannot show
The setting is far easier than linking news text to Wikipedia, and for several reasons.
- The knowledge base is small. It has 850 entities, against millions in Wikipedia, so there are few names to collide.
- The anchors are mostly titles. As counted above, 68.4% of the mentions use the target's title, and most anchors name one page only.
- The annotations were written by language models. The site's pages, and so their links, were written by models under the owner's direction. Their habits shape the data: the full-title anchors, and phrases such as the previous article, whose 18 uses on the site point to 15 different pages and which no dictionary can resolve.
- The gold annotations record one acceptable answer. As the running example showed, the site's authors link the algebraic evaluation to two pages, so a disagreement with the gold need not be an error.
- NIL is simulated. As noted above, removed pages make NIL mentions easier than real unlinkable names.
- The bi-encoder was not trained for the task. BLINK's numbers come from encoders trained on millions of Wikipedia links; ours come from a sentence-similarity model used as it is.
What the experiment does show, within those limits, is the shape of the problem that the literature describes: on gold mentions, the prior from the links already decides almost everything; relatedness can only help on the few ambiguous mentions and helps a little; recall is limited by names the dictionary has never seen; and dense retrieval covers those names as candidates but needs a trained second stage to choose among them.
What is proved here, what is cited, and what the experiment shows
Derived on the page. That WLM is positive exactly when two entities share more in-links than independent linking would produce, and so agrees with the PMI ratio of Ratinov et al. about which pairs are related (ratio above 1), though not about how strongly; that it is independent of the logarithm's base, at most 1, and equal to 1 exactly when the in-link sets coincide. The arithmetic of the running example and of the worked problems.
Cited. The task's definition and modules (Shen et al., 2015; Balog, 2018). Commonness and its origin (Medelyan et al., 2008; Balog, 2018), keyphraseness (Mihalcea and Csomai, 2007). The Normalized Google Distance and its properties (Cilibrasi and Vitányi, 2007). The relatedness measure and its results on word pairs (Milne and Witten, 2008a). Milne and Witten's linking system (2008b): its context, its weighting and its evaluation. The collective methods and their reported results (Ratinov et al., 2011, and Hoffart et al., 2011, read in full; Kulkarni et al., 2009, Han et al., 2011, and TAGME, as the two surveys report them). BLINK's design and results (Wu et al., 2020). The evaluation measures and test collections (Shen et al., 2015; Balog, 2018).
Shown by the experiment. On this site's 850 pages and 14,942 author-written links, over 30 seeded splits: commonness links given mentions with a median F1 of 0.935, limited by the dictionary's coverage of 0.903; relatedness from the site's link graph adds a median of 0.0008 per split; a pretrained sentence encoder used as an entity retriever ranks the right page first for 0.366 of in-KB mentions and within its top 64 for 0.966; and detecting the mentions as well lowers the bag-of-titles F1 to 0.859. These are observations on one small, model-written collection, not general findings about entity linking.
Worked problems
These problems are posed on this site's links and on the examples of the cited papers; the unit has no course assignments. The script recomputes every number.
Problem 1 (commonness and keyphraseness). On every page of this site except the algebra page of the opening, the anchor evaluation links 20 times to Retrieval Evaluation, 4 times to Polynomial Rings, 3 times to Ring Homomorphisms and once to Training, Validation and Test Sets. The anchor occurs in 20 of those pages, and the word occurs in 387. Give the commonness of each entity and the keyphraseness of evaluation, and say what a linker that uses only these two numbers does with the algebra page's mention.
Solution. The anchor is used $20 + 4 + 3 + 1 = 28$ times, so the commonness values are $20/28 = 0.714$, $4/28 = 0.143$, $3/28 = 0.107$ and $1/28 = 0.036$. They sum to 1, as the shares of one set of links must. The keyphraseness is $20/387 = 0.052$. A linker that must detect mentions with a threshold above 0.052 does not link the word at all. A linker given the mention, using commonness alone, links it to Retrieval Evaluation, which is wrong for this page. Neither number looks at the page.
Problem 2 (relatedness of two pages). Polynomial Rings has 12 in-links, Integral Domains and Fields 18, and they share 10, among $N = 850$ pages. Compute their relatedness, check its sign against the independence condition, and compute the relatedness of Retrieval Evaluation (27 in-links, none shared with Integral Domains and Fields) to Integral Domains and Fields.
Solution. With natural logarithms, $\ln 18 = 2.8904$, $\ln 10 = 2.3026$, $\ln 850 = 6.7452$ and $\ln 12 = 2.4849$. The numerator is $2.8904 - 2.3026 = 0.5878$ and the denominator $6.7452 - 2.4849 = 4.2603$, so
$$\mathrm{WLM} = 1 - \frac{0.5878}{4.2603} = 1 - 0.1380 = 0.862 .$$
The independence expectation is $12 \times 18 / 850 = 0.254$ shared in-links. The observed 10 is larger, so by the result proved above the relatedness must be positive, and it is. For Retrieval Evaluation the intersection is empty, so its relatedness is 0 by definition. The logarithm of zero is not defined, which is why the definition sets the score to zero in that case.
Problem 3 (one disambiguation in full). The algebra page's unambiguous mentions give 12 context entities. The mean relatedness of each candidate to them is 0.691 for Polynomial Rings, 0.742 for Ring Homomorphisms and 0 for the other two candidates. With the commonness values of Problem 1, which candidate does the Milne and Witten score choose, and by what margin?
Solution. The scores are commonness plus mean relatedness: $0.143 + 0.691 = 0.833$ for Polynomial Rings, $0.107 + 0.742 = 0.849$ for Ring Homomorphisms, $0.714 + 0 = 0.714$ for Retrieval Evaluation and $0.036$ for Training, Validation and Test Sets. The highest is Ring Homomorphisms, 0.016 ahead of Polynomial Rings. Retrieval Evaluation, the most common sense, falls to third, 0.135 behind the winner: relatedness worth more than the commonness gap of $0.714 - 0.107 = 0.607$ is what overturns the prior. The author's link went to Polynomial Rings, so the score is counted wrong, though, as the article explains, the chosen page is a defensible reading.
Problem 4 (precision and recall with NIL mentions). A page has ten gold mentions, eight of entities in the knowledge base and two NIL. A linker links seven mentions: six of them correctly, and one of the NIL mentions to some entity. It returns NIL for the other three, which are the other NIL mention and two in-KB mentions. Compute precision, recall and F1, and the accuracy if a correct NIL is counted as a correct decision.
Solution. Precision is correct links over links made, $6/7 = 0.857$. Recall is correct links over mentions that should be linked, $6/8 = 0.750$. Then $F_1 = 2 \cdot \frac{6}{7} \cdot \frac{3}{4} / (\frac{6}{7} + \frac{3}{4}) = \frac{9/7}{45/28} = \frac{4}{5} = 0.800$. The correct decisions are the six correct links and the one correct NIL, so the accuracy is $7/10 = 0.700$. The NIL mention that was linked costs precision, and the two in-KB mentions left unlinked cost recall.
Problem 5 (a bag-of-titles evaluation). Ratinov et al. (2011) give this example in the description of their evaluation. The gold annotation of a document is {(China, People's Republic of China), (Taiwan, Taiwan), (Jiangsu, Jiangsu)}. The system outputs {(China, People's Republic of China), (China, History of China), (Taiwan, NIL), (Jiangsu, Jiangsu), (republic, Government)}. Compute bag-of-titles precision and recall.
Solution. The gold bag is {People's Republic of China, Taiwan, Jiangsu}. The predicted bag holds the titles the system linked from mentions that appear in the gold annotation: People's Republic of China, History of China and Jiangsu. Taiwan was linked to NIL, so it contributes nothing, and Government is excluded because its mention republic is not a gold mention. Two titles are shared, so precision is $2/3$ and recall $2/3$, both 0.667. The paper prints 0.66, which is $2/3$ truncated to two places.
What we have learned
Entity linking rests on a dictionary of names built from links people have written, and the prior that dictionary carries, commonness, is already a strong linker. Context enters through relatedness, and Milne and Witten's measure, a Normalized Google Distance over in-links, is positive exactly when two entities share more linking pages than chance predicts. Collective methods enforce coherence over a whole document, at the cost of a hard optimization, and the comparisons in the literature show them gaining a few points over the prior. Dense retrieval breaks the dictionary's limit to known names, and BLINK pairs a bi-encoder for candidates with a cross-encoder for the choice. On this site's own links the same pattern appeared on a small scale: the prior decided almost everything, relatedness corrected a few dozen ambiguous mentions, recall was bounded by unseen names, and a pretrained bi-encoder found those names among its candidates without being able to choose them.
Linking turns text into references to entities, and the entities live in a knowledge base. The next article, Knowledge Graphs, describes such knowledge bases and their data model. After it, Entity-Oriented Search reverses the direction of this article: given a query, which entities are the answer?
References
- Balog, K. (2018). Entity-Oriented Search. The Information Retrieval Series 39. Springer, Cham. Open access. doi:10.1007/978-3-319-93935-3. record · 2 pages
- Cilibrasi, R. L., and Vitányi, P. M. B. (2007). The Google similarity distance. IEEE Transactions on Knowledge and Data Engineering, 19(3), 370–383. arXiv:cs/0412098. record
- Ferragina, P., and Scaiella, U. (2010). TAGME: On-the-fly annotation of short text fragments (by Wikipedia entities). In Proceedings of CIKM 2010, 1625–1628. doi:10.1145/1871437.1871689. record
- Gillick, D., Kulkarni, S., Lansing, L., Presta, A., Baldridge, J., Ie, E., and Garcia-Olano, D. (2019). Learning dense representations for entity retrieval. In Proceedings of CoNLL 2019, 528–537. record
- Han, X., Sun, L., and Zhao, J. (2011). Collective entity linking in web text: A graph-based method. In Proceedings of SIGIR 2011, 765–774. doi:10.1145/2009916.2010019. record
- Hoffart, J., Yosef, M. A., Bordino, I., Fürstenau, H., Pinkal, M., Spaniol, M., Taneva, B., Thater, S., and Weikum, G. (2011). Robust disambiguation of named entities in text. In Proceedings of EMNLP 2011, 782–792. record
- Kulkarni, S., Singh, A., Ramakrishnan, G., and Chakrabarti, S. (2009). Collective annotation of Wikipedia entities in web text. In Proceedings of KDD 2009, 457–466. doi:10.1145/1557019.1557073. record
- Logeswaran, L., Chang, M.-W., Lee, K., Toutanova, K., Devlin, J., and Lee, H. (2019). Zero-shot entity linking by reading entity descriptions. In Proceedings of ACL 2019, 3449–3460. record
- Medelyan, O., Witten, I. H., and Milne, D. (2008). Topic indexing with Wikipedia. In Proceedings of the AAAI Workshop on Wikipedia and Artificial Intelligence: An Evolving Synergy, 19–24. record
- Mihalcea, R., and Csomai, A. (2007). Wikify! Linking documents to encyclopedic knowledge. In Proceedings of CIKM 2007, 233–242. doi:10.1145/1321440.1321475. record
- Milne, D., and Witten, I. H. (2008a). An effective, low-cost measure of semantic relatedness obtained from Wikipedia links. In Proceedings of the AAAI Workshop on Wikipedia and Artificial Intelligence: An Evolving Synergy, 25–30. record
- Milne, D., and Witten, I. H. (2008b). Learning to link with Wikipedia. In Proceedings of CIKM 2008, 509–518. doi:10.1145/1458082.1458150. record
- Ratinov, L., Roth, D., Downey, D., and Anderson, M. (2011). Local and global algorithms for disambiguation to Wikipedia. In Proceedings of ACL 2011, 1375–1384. record
- sentence-transformers (n.d.). sentence-transformers/all-MiniLM-L6-v2. Model card at revision
1110a243fdf4706b3f48f1d95db1a4f5529b4d41. https://huggingface.co/sentence-transformers/all-MiniLM-L6-v2 (accessed 22 November 2026). record · 6 pages - Shen, W., Wang, J., and Han, J. (2015). Entity linking with a knowledge base: Issues, techniques, and solutions. IEEE Transactions on Knowledge and Data Engineering, 27(2), 443–460. doi:10.1109/TKDE.2014.2327028. record
- Wu, L., Petroni, F., Josifoski, M., Riedel, S., and Zettlemoyer, L. (2020). Scalable zero-shot entity linking with dense entity retrieval. In Proceedings of EMNLP 2020, 6397–6407. arXiv:1911.03814. record