IR Lecture 6: Entity Retrieval and Linking

Background Reading is EOS Ch.3 and Ch.5, but the slides seem to follow the reading quite closely. Due to time constraint, I just add some notes about the reading here in the lecture notes.

Query: "Turing Award Winners".

For this query, search machines do not just return documents, but they directly show the names of the Turing award winners. I.e. it "understands" and answers a question.

Cf. Google's "Knowledge Graph"

We have various knowledge repositories such as imdb; but knowledge graphs are knowledge bases that have structured sets of assertions about entities.

Freebase is one of the best examples and it was open source. But Google bought Freebase and shut it down, saying that Freebase data would be moved to Wikidata. The content is not freely accessible to the (research) community anymore.

DBpedia is another example.

Linked Open Data (LOD) cloud: See https://lod-cloud.net/ for a cloud of knowledge graphs; they seem to be all connectd to DBPedia.

So DBPedia can be seen at the center of the LOD graph. (One assignment was about working with DBPedia).

What does DBpedia do? Read Wikipedia entries and try to represent the information in a graph.

Q: What's a knowledge graph?

A: A structured repository containing facts/assertions/knowledge about entities.

Entity Retrieval

An entity is an object or concept that can be uniquely identified.

Query: "Dutch Comedians"

Knowledge graphs and entity-oriented search are the core-enabling data component of semantic search.

For above query we want semantic search: the search machine should "understand" that we are looking for a particular type of entity, namely persons that are both Dutch and comedians.

In this case, entity retrieval is necessary.

For entity retrieval, we take two steps:

  1. Construct entity representations
  2. Apply a retrieval model on these representations

Note that the process of going from a query with mentions to the entities in some index or knowledge graph requires entity linking (see below).

Q: How does entity retrieval relate to semantic search?

Constructing Entity Representations from different sources

Three scenarios for different sources: unstructured; semi-structured; structured data.

In general, we are interested in estimating $c(t,e;d)$ i.e. the amount of co-occurrences of term t with entity e in document d.

From unstructured data

We start with unstructured documents.

  • We annotate these documents with entities
  • Take into account terms within a window around the entity mention.
    • The idea is that entities are well described by the words they frequently co-occur with
    • c(t,e;d) is just the number of times t and e co-occur in a window w around that entity mention in document d.
    • See EOS. p.64: window sizes range from 20 to 250.

You can also compute document-entity weights, repeating the same process on document-level rather than mention windows.

  • Have a bag-of-words representation.
  • Determine frequency of mentions of each entity in document d, i.e. $c(e;d)$ relative to total entity mentions in the document.
  • Entity Frequency is just in how many documents an entity occurs, cf. DF
  • Then compute similar to TF-IDF, TF*log(M / DF )

We want to quantify the association between a document and an entity. We can apply the same reasoning as TF-IDF.

From semi-structured documents

Sometimes a "catch-all" field is introduced that amassing all fields or all contents of the document. This may help compensating troubles introduces by sparse fields.

Why semi-structured? Consider a movie review. Has several fields, such as 'title' or 'genre', but also a large amount of free text.

Each entity has its own format. E.g. when we are considering movies, not each movie will have the same fields. So this is not as organized as data in a database.

Q: When doing entity retrieval on movies, do you think this is an example of unstructured, semi-structured or structured input data?

From structured data

In knowledge graphs, entity information is stored in RDF format: < subject, predicate, object > also called SPO triples.

RDF: Resource Description Framework.

So to get entity representations, we can also parse knowledge graphs. The idea is still the same: ultimately we need a textual entity description so that we can apply regular retrieval methods.

See p.73-74 on parsing SPO triples.

To apply a retrieval model, we need an index. There is an important difference between RDFs and what we had before, namely a document with some fields. Per document we only had a few fields, but in a knowledge base any given entity may have hundreds of predicates. So if we consider each predicate as a field, we get way too many fields.

So if we want to make a fielded index we need to first solve by applying predicate folding: grouping predicates together into a small set of predefined categories.

(I guess this also standardizes things a bit, because now we use predefined categories, whereas normally one entity may have fields A, B, C and another fields C, D, E. This aids in building a useful index).

Predicate folding

Typical categories:

  • Name
  • Name aliases
  • Attributes
  • Types
  • Outgoing relations
  • Incoming relations
  • Top-predicates
  • Catch-all

Apply retrieval model

What I'm missing in the slides are more comments about the actual retrieval, so I'm appending some stuff from EOS Ch. 3 here.

Input: Free form query. Output: A ranking of entities most relevant to query q.

The idea proposed in the book (and I guess also why it's barely mentioned in the slides) is that we 1) build appropriate textual entity representations so that 2) we can use well-known ranking functions such as BM25.

In concrete (and what we've seen above) this means constructing term-based representations or entity descriptions.

We then need a way to link the terms in a query to entities and score the entities on relevance. W.r.t. the default setup, we mostly just need to change d (for document) with e for the entity description.

We can then define:

  • Term Frequency ( TF ): term count in entity description
  • Entity Frequency (EF): number of entities in which a term occurs
    • Analogue to DF!
  • Inverse entity frequency (IEF): log( |E| / EF(t)) with |E| being total number of entities.

For unstructured representations

  • Language model with JM-smoothing or such
  • BM25

For (semi-)structured

  • Mixed Language Models
  • BM25F

Structured

What is a useful retrieval model for structured data?

  • BM25F: takes different fields into account.
  • Mixture of Language Models (MLM) (one LM per field)

Q: How would an inverted index for entity retrieval look like?

Assuming entity term-based representations, we could imagine indexes for entity retrieval something like this, if we just replace document d with entity d.

Index: entity -> [terms of entity description].

Inversed: term -> [entityIDs].

Extended inversed: term -> Entity Frequency -> [ {EntityID, TF in entity }]

(Recall EF is the amount of entity descriptions in which the term occurs). We then have all the information available that we need to for example apply BM25. This assumes a lot of other work is already done, e.g. that mentions in the docs with DocID are resolved to that entity.

I had another idea which involved DocIds, but this is not what we are after here since we are ranking entities and not documents. Just kept it in here for completeness.

Index, DocID -> [mentioned entity]. Inversed index: entityID -> [DocIDs].

Could extend this to use TF and EF (entity frequency) to look something like this: entityID -> Entity Frequency -> [ {DocID, TF}, {DocID, TF}, ...]

Q: What is the RDF format?

Q: Which retrieval models are suitable to be used for entity retrieval?

Q: What is predicate folding?

Q: Let's say we use BM25F, why do we then need predicate folding?

Entity Linking

If we go to a Wikipedia page, we also see a lot of hyperlinks between entities. The task of linking these mentions in free text to the appropriate entry on an entity automatically is called Entity Linking.

Q: What's Entity Linking?

In Wikipedia, this process is done manually, but we are interested in letting a machine do this.

  • Document and entity retrieval
  • Query understanding
  • Automatic document enrichment; go-read-here
  • Knowledge graph population
  • Topic based recommendation

Entity linking is based on a knowledge base.

The BERT model, for example also leas to entity understanding, but this is not what we usually consider under the term "entity linking".

Q: How does entity linking relate to entity retrieval?

Q: What are applications of entity linking?

General Framework for Entity Linking

Input free text.

  1. Mention detection: identify all linkable phrases
  2. Entity selection (for each mention): generate set of candidate entities for each mention
    • This step, somewhat counter-intuitively, thus does not already "select" a single entity.
    • Instead it produces a ranking over the best matches entities according to some criterion
  3. Disambiguation: select a single entity (or NIL) for each mention.

Output: Annotated text.

Neural approaches do not make these steps that explicit.

Mention detection

This is a recall oriented task.

We will disambiguate later. But if we do not find all mentions, they can never be processed into the pipeline and will be an error by default.

Challenge: find entity name variants.

This is a very dominant problem in queries. E.g. "JLO" for "Jennifer Lopez".

One basic approach is to build a name dictionary. Wikipedia is very handy here:

  • The most common name of the entity; probably the page title
  • Redirect pages: these indicate alternative names
  • Wikipedia also has disambiguation pages; with entities sharing the same name.
  • Anchor texts
    • This is generally applicable, as many other types of sources have annotations.
  • Other sources: e.g. YAGO; annotated corpora.

Q: Is precision or recall more important during mention detection? Why?

Q: Which aspects of Wikipedia can be used during mention detection?

Q: What's a name dictionary in mention detection?

Entity Selection

Narrow down the space of disambiguation possibilities by ranking the entities for each mention.

Two main types used:

  • Textual similarity
    • Compare surrounding context of a mention with an entity representation
    • Cosine similarity: basically angle between two n-dimensional vectors
  • Popularity bases features
    • E.g. commonness measure

Commonness measure: what's the probability that a word refers to the entity (in terms of known use):

$$P(e|m)= \frac{n(m,e)}{\sum_{e'}n(m,e')}$$

$n(m,e)$ is number of time entity $e$ is in the link target of mention $m$.

Remember, we have a mention and are trying to find which entity corresponds to that mention. So in this case we check how often a particular entity is in the link target of the given mention, normalized by the total occurrences of mention $m$.

Q: Name two methods for ranking mentions during entity selection

Q: Explain the commonness measure used during entity selection

Disambiguation

Goal: select single entity, or none.

For each mention we now have a ranked list of entities. If we did a very good part in entity selection, then the best match should be in the top 10 ranking.

That makes disambiguation more feasible, because this step is usually very expensive. That's also why local models should be considered.

In general, the idea is that an entity is described well by the local context in which it is used.

Local models:

  • Rely only on local context of mentions
  • Completely ignore interdependencies between the linking decision in the document

Global model:

  • Besides using local context, also take into account entity coherency
  • True global optimization is NP-hard
  • Simple approximation approach: consider sum over all pairwise entity scores

Entity Linking Evaluation

This was missing from the slides. See EOS 5.8.

  • Compare system-generated annotations with a golden standard (manual labeling)
  • Precision, recall and F1 are common.
  • When computing scores over a whole collection of documents, we need to average these measures.
    • But notice the distinction between micro-averaging and macro-averaging.
    • Micro-average: across mentions
    • Macro-average: across documents
  • You need to define when an annotation "matches"
    • Exact matches vs. overlap.

REL

Was supposed to be a guest lecture part, but guest lecturer didn't make it.