Entity linking

01 · CONTEXT

The problem: linking mentions to entities

Entity linking takes a text and the list of entity mentions it contains, and returns a list of mention-entity pairs, where each entity is an entry in a knowledge base, such as Wikipedia.

Questions of this kind appear in Chip Huyen's list of ML systems design exercises: train a model to predict whether a word in a sentence refers to the animal or the car, and map nicknames such as Pete, Andy, Nick, and Rob to real names.

What decides the entity is the sentence's context, not the spelling of the mention: the same word points to different entries in the base depending on the surrounding text.

The page itself warns that many questions are ambiguous on purpose and that it is up to the interviewee to ask for clarification and bound the scope of the problem. Educative's Grokking the Machine Learning Interview course lists an Entity Linking System project built on named entity linking (NEL), with recognition, disambiguation, metrics, architecture, and modeling; only that public description was used here.

02 · FORMULATION

What the reference paper assumes

As a reference design, the case uses the paper Scalable Zero-shot Entity Linking with Dense Entity Retrieval, from Facebook AI Research. It studies linking with mentions already provided (gold mentions) and assumes that entity titles and descriptions are available.

The central challenge is scale: for each mention there are millions of possible entities to consider. Earlier methods relied on mention tables and Wikipedia link popularity; in the paper's zero-shot setting, there is no external knowledge and each entity is defined only by a short textual description.

03 · ARCHITECTURE

Dense retrieval followed by reranking

The paper splits the task into two stages: candidate generation and ranking. Earlier work generated candidates using frequency information, alias tables, and TF-IDF-based methods.

The proposal is a two-stage zero-shot algorithm. In the first, retrieval happens in a dense space defined by a bi-encoder that independently embeds the mention context and the entity descriptions. In the second, each candidate is reranked by a cross-encoder that concatenates the mention text and the entity text.

1. Off the request path, a batch job reads the title and description of each entity in the knowledge base, computes their embeddings, and publishes them to the vector index. Entity representations can be precomputed and cached.

2. The client sends the linking service the text and the mention to resolve.

3. The service asks the mention encoder for the mention's vector with its context; the bi-encoder embeds the mention and the entities independently.

4. The index returns the entities with the highest dot product with the mention vector.

5. The reranker reads the candidates' descriptions from the knowledge base and scores each mention-entity pair; the cross-encoder has deep cross-attention between the context and the descriptions.

6. The service returns the chosen entity for the mention to the client.

04 · MODELS AND TRAINING

Bi-encoder, cross-encoder, and how to train

No bi-encoder, two independent BERT transformers encode the context with the mention and the entity into dense vectors, and each candidate is scored by the dot product of those vectors. The entity goes in with title and description; for Wikipedia entities, the description uses the first sentences of the page.

In the cross-encoder, context/mention and entity are encoded together in a single transformer, with an additional linear layer. Because of its larger memory and compute footprint, it is used to rerank a small set of candidates from the bi-encoder, up to 100, and the paper considers it unsuitable for retrieval or tasks that require fast inference.

The bi-encoder is trained to maximize the score of the correct entity against entities randomly sampled from the same batch. Besides in-batch negatives, the paper uses hard negatives, obtained from the 10 top-predicted entities for each training example and added to the random negatives.

In the zero-shot experiment, the cross-encoder was trained on the top 64 bi-encoder candidates for each sample, with a softmax loss to maximize the score of the correct entity.

1. The annotated mention-entity pairs feed the bi-encoder's training, which maximizes the score of the correct entity against the entities in the same batch.

2. Mining picks, for each training example, the top-predicted entities as hard negatives and feeds them back into training, along with the batch's random negatives.

3. The trained bi-encoder supplies the candidates for training the cross-encoder: in the zero-shot experiment, the top 64 for each sample.

4. The cross-encoder is trained with a softmax loss to maximize the score of the correct entity among the candidates.

5. In distillation, the cross-encoder plays the role of teacher to a bi-encoder: part of the accuracy gain of the costlier cross-encoder is transferred to the bi-encoder.

6. The resulting models are written to the model repository.

05 · EVALUATION AND COST

Recall, latency, and the price of each stage

In the zero-shot evaluation, the bi-encoder reaches much higher recall than BM25, and the paper passes the top 64 retrieved candidates to the ranker.

On speed, the paper states that bi-encoder linking is very fast with approximate nearest neighbor search, for example over 5.9 million candidates in 2 milliseconds. Computing the embeddings for the 5.9M-entity set is a resource-intensive but parallelizable step, and took about 2.8 hours.

The paper also shows that a good part of the accuracy gain of the costlier cross-encoder can be transferred to the bi-encoder through knowledge distillation.

06 · LIMITS AND INTERVIEW

What the design does not cover

The paper focuses on local resolution, in which each mention is modeled independently. Out-of-KB (nil) prediction and end-to-end linking are left for future work: the paper says its techniques should apply to that setting, but leaves the exploration for later.

For the interview, after closing the scope (mentions given or detected, size of the base, what to do when there is no correct entity), present cheap retrieval followed by expensive reranking, justify precomputing the entity embeddings, discuss hard negatives in training, and finish with the limits: coherence between mentions in the same document, new entities, and mentions with no entity in the base.