Mutual Disambiguation for Entity Linking

The use of Wikipedia for explicit disambiguation dates back to [2] who built a system that compared the context of a mention to the Wikipedia categories of an entity candidate. Lately, [6, 15, 17] extended this framework by using richer features for similarity comparison. Some authors like Milne and Witten (2008) utilized machine learning methods rather than a similarity function to map mentions to entities. They also introduced the notion of semantic relatedness. Alternative propositions were suggested in other works like [10] that considered the relatedness of common noun phrases in a mention context with Wikipedia article names. While all these approaches focus on semantic relation between entities, their potential is limited by the separate mapping of candidate links for each mention.

More recently, several systems have been launched as web services dedicated to EL tasks. Most of them are compliant with new emergent semantic web standards like LinkedData network. DBPedia Spotlight [14] is a system that finds mentions of DBpedia [1] resources in a textual document. Wikimeta [3] is another system relying on DBpedia. It uses bags of words to disambiguate semantic entities according to a cosine similarity algorithm. Those systems have been compared with commercial ones like AlchemyAPI, Zemanta, or Open Calais in [9]. The study showed that they perform differently on various essential aspects of EL tasks (mention detection, linking, disambiguation). This suggests a wide range of potential improvements on many aspects of the EL task. Only some of these systems introduce the semantic relatedness in their methods like the AIDA [12] system. It proposes a disambiguation method that combines popularity-based priors, similarity measures, and coherence. It relies on the Wikipedia-derived YAGO2 [11] knowledge base.

Documents are processed by an annotator capable of producing POS tags for each word, as well as spans, NE surface forms, NE labels and ranked candidate Wikipedia URIs for each candidate NE. For each document $𝒟$, this knowledge is gathered in an array called annotation object, which has initially one row per document lexical unit. Since the system focuses on NEs, rows with lexical units that do not belong to a NE SF are dropped from the annotation object, and NE SF are refined as described in [5]. When NE SF are spanned over several rows, these rows are merged into a single one. Thus, we consider an annotation object ${𝒜}_{𝒟}$, which is an array with a row for each NE, and columns storing related knowledge.

If $n$ NEs were annotated in $𝒟$, then ${𝒜}_{𝒟}$ has $n$ rows. If $l$ candidate URIs are provided for each NE, then ${𝒜}_{𝒟}$ has $\left(l+4\right)$ columns $c_{u,u\in \left\{1,l+4\right\}}$. Columns $c_1$ to $c_l$ store Wikipedia URIs associated with NEs, ordered by decreasing values of likelihood. Column $c_{l+1}$ stores the offset of the NEs, $c_{l+2}$ stores their surface forms, $c_{l+3}$ stores the NE labels (PER, ORG, …), and $c_{l+4}$ stores the (vectors of) POS tags associated with the NE surface forms. ${𝒜}_{𝒟}$ contains all the available knowledge about the NEs found in $𝒟$. Before being processed by the disambiguation module, ${𝒜}_{𝒟}$ is dynamically updated by correction processes.

To support the correction process based on co-reference chains, the system tries to correct NE labels for all the NEs listed in the annotation object. The NE label correction process assigns the same NE label to all the NEs associated with the same first rank URI. For all the rows in ${𝒜}_{𝒟}$, sets of rows with identical first rank URIs are considered. Then, for each set, NE labels are counted per type, and all the rows in a same set are updated with the most frequent NE label found in the set, i.e. all the NEs in this set are tagged with this label.

First rank candidate URIs are corrected by a process that relies on co-reference chains found in the document. The co-reference detection is conducted using the information recorded in the annotation object. Among the NEs present in the document, the ones that co-refer are identified and clustered by logical rules applied to the content of the annotation object. When a co-reference chain of NEs is detected, the system assigns the same URI to all the members of the chain. This URI is selected through a decision process that gives more weight to longer surface forms and frequent URIs. The following example illustrates an application of this correction process:
Three sentences are extracted from a document about Paris, the French capital. NEs are indicated in brackets, first rank URIs and surface forms are added below the content of each sentence.
- [Paris] is famous around the world.
URI${}_1$: http://en.wikipedia.org/wiki/Paris_Hilton
NE surface form: Paris
- The [city of Paris] attracts millions of tourists.
URI${}_1$: http://en.wikipedia.org/wiki/Paris
NE surface form: city of Paris
- The [capital of France] is easy to reach by train.
URI${}_1$: http://en.wikipedia.org/wiki/Paris
NE surface form: capital of France

The three NEs found in these sentences compose a co-reference chain. The second NE has a longer surface form than the first one, and its associated first rank URI is the most frequent. Hence, the co-reference correction process will assign the right URI to the first NE (URI${}_1$: http://en.wikipedia.org/wiki/Paris), which was wrongly linked to the actress Paris Hilton.

The extraction of an accurate link is a process occurring after the URI annotation of NEs in the whole document. The system makes use of all the semantic content stored in ${𝒜}_{𝒟}$ to locally improve the precision of each URI annotation in the document. The Mutual Disambiguation Process (MDP) relies on the graph of all the relations (internal links, categories) between Wikipedia content related to the document annotations.

A basic example of semantic relatedness that should be captured is explained hereafter. Let us consider the mention IBM in a given document. Candidate NE annotations for this mention can be International Business Machine or International Brotherhood of Magicians. But if the IBM mention co-occurs with a Thomas Watson, Jr mention in the document, there will probably be more links between the International Business Machine and Thomas Watson, Jr related Wikipedia pages than between the International Brotherhood of Magicians and Thomas Watson, Jr related Wikipedia pages. The purpose of the MDP is to capture this semantic relatedness information contained in the graph of links extracted from Wikipedia pages related to each candidate annotation.

In MDP, for each Wikipedia URI candidate annotation, all the internal links and categories contained in the source Wikipedia document related to this URI are collected. This information will be used to calculate a weight for each of the $l$ candidate URI annotations of each mention. For a given NE, this weight is expected to measure the mutual relations of a candidate annotation with all the other candidate annotations of NEs in the document. The input of the MDP is an annotation object ${𝒜}_{𝒟}$ with $n$ rows, obtained as explained in Section 3.1. For all $i\in \left[\left[1,n\right]\right]$, $k\in \left[\left[1,l\right]\right]$, we build the set $S_i^k$, composed of the Wikipedia URIs and categories contained in the source Wikipedia document related to the URI stored in ${𝒜}_{𝒟}$$\left[i\right]\left[k\right]$ that we will refer to as URI${}_i{}^k$ to ease the reading.
Scoring:
For all $i,\hspace{0.25em}j\in \left[\left[1,n\right]\right]$, $k\in \left[\left[1,l\right]\right]$, we want to calculate the weight of mutual relations between the candidate URI${}_i{}^k$ and all the first rank candidates URI${}_j{}^1$ for $j\ne i$. The calculation combines two scores that we called direct semantic relation score (dsr_score) and common semantic relation score (csr_score):

- the dsr_score for URI${}_i{}^k$ sums up the number of occurrences of URI${}_i{}^k$ in $S_j^1$ for all $j\in \left[\left[1,n\right]\right]-\left\{i\right\}$.

- the csr_score for URI${}_i{}^k$ sums up the number of common URIs and categories between $S_i^k$ and $S_j^1$ for all $j\in \left[\left[1,n\right]\right]-\left\{i\right\}$.

We assumed the dsr_score was much more semantically significant than the csr_score, and translated this assumption in the weight calculation by introducing two correction parameters $\alpha$ and $\beta$ used in the final scoring calculation.

Re-ranking:
For all $i\in \left[\left[1,n\right]\right]$, for each set of URIs $\left\{{\text{URI}}_i^k,\hspace{0.25em}k\in \left[\left[1,l\right]\right]\right\}$, the re-ranking process is conducted according to the following steps:
For all $i\in I$,

1. 1.

   $\forall k\in \left[\left[1,l\right]\right]$, calculate dsr_score(URI${}_i{}^k$)

2. 2.

   $\forall k\in \left[\left[1,l\right]\right]$, calculate csr_score(URI${}_i{}^k$)

3. 3.

   $\forall k\in \left[\left[1,l\right]\right]$, calculate
   mutual_relation_score(URI${}_i{}^k$) =
   $\alpha .$dsr_score(URI${}_i{}^k$)+$\beta .$csr_score(URI${}_i{}^k$)

4. 4.

   re-order $\left\{{\text{URI}}_i^k,\hspace{0.25em}k\in \left[\left[1,l\right]\right]\right\}$, by
   decreasing order of mutual relation score.

In the following, we detail the MDP in the context of a toy example to illustrate how it works. The document contains two sentences, NE mentions are in bold:

IBM has 12 research laboratories worldwide. Thomas J. Watson, Jr. became president of the company.

For the first NE mention [IBM], ${𝒜}_{𝒟}$ contains two candidate URIs identifying two different resources:

For the second NE mention [Thomas J. Watson, Jr.], ${𝒜}_{𝒟}$ contains the following candidate URI, which is ranked first:

[Thomas J. Watson, Jr.] URI${}_2{}^1\equiv \mathtt{\text{Thomas Watson, Jr.}}$

$S_1^1$ gathers URIs and categories contained in the International Brotherhood of Magicians Wikipedia page. $S_1^2$ is associated to the International Business Machines Corporation, and $S_2^1$ to the Thomas Watson, Jr. page. dsr_score(URI${}_1{}^1$) sums up the number of occurrences of URI${}_1{}^1$ in $S_j^1$ for all $j\in \left[\left[1,n\right]\right]-\left\{1\right\}$. Hence, in the current example, dsr_score(URI${}_1{}^1$) is the number of occurrences of URI${}_1{}^1$ in $S_2^1$, namely the number of times the International Brotherhood of Magicians are cited in the Thomas Watson, Jr. page. Similarly, dsr_score(URI${}_1{}^2$) is equal to the number of times the International Business Machines Corporation is cited in the Thomas Watson, Jr. page.
csr_score(URI${}_1{}^1$) sums up the number of common URIs and categories between $S_1^1$ and $S_2^1$, i.e. the number of URIs and categories appearing in both International Brotherhood of Magicians and Thomas Watson, Jr. pages. csr_score(URI${}_1{}^2$) counts the number of URIs and categories appearing in both International Business Machines Corporation and Thomas Watson, Jr. pages.
After calculation, we have:
mutual_relation_score(URI${}_1{}^1$) mutual_relation_score(URI${}_1{}^2$) The candidate URIs for [IBM] are re-ranked accordingly, and International Business Machines Corporation becomes its first rank candidate.