∎

11institutetext: Rhea Sukthanker 22institutetext: School of Information
Technology and Engineering, VIT University, Vellore, India
22email<EMAIL_ADDRESS>33institutetext: Soujanya Poria
44institutetext: Temasek Laboratories, Nanyang Technological University,
Singapore
44email<EMAIL_ADDRESS>Erik Cambria 66institutetext:
School of Computer Science and Engineering, Nanyang Technological University,
Singapore
66email<EMAIL_ADDRESS>77institutetext: Ramkumar Thirunavukarasu
88institutetext: School of Information Technology and Engineering, VIT
University, Vellore, India
88email<EMAIL_ADDRESS>
# Anaphora and Coreference Resolution: A Review

Rhea Sukthanker  Soujanya Poria  Erik Cambria  Ramkumar Thirunavukarasu

(Received: date / Accepted: date)

###### Abstract

Entity resolution aims at resolving repeated references to an entity in a
document and forms a core component of natural language processing (NLP)
research. This field possesses immense potential to improve the performance of
other NLP fields like machine translation, sentiment analysis, paraphrase
detection, summarization, etc. The area of entity resolution in NLP has seen
proliferation of research in two separate sub-areas namely: anaphora
resolution and coreference resolution. Through this review article, we aim at
clarifying the scope of these two tasks in entity resolution. We also carry
out a detailed analysis of the datasets, evaluation metrics and research
methods that have been adopted to tackle this NLP problem. This survey is
motivated with the aim of providing the reader with a clear understanding of
what constitutes this NLP problem and the issues that require attention.

###### Keywords:

Entity Resolution Coreference Resolution Anaphora Resolution Natural Language
Processing Sentiment Analysis Deep Learning

††journal: Artificial Intelligence Review

##  1 Introduction

A discourse is a collocated group of sentences which convey a clear
understanding only when read together. The etymology of anaphora is $ana$
(Greek for back) and $pheri$ (Greek for to bear), which in simple terms means
repetition. In computational linguistics, anaphora is typically defined as
references to items mentioned earlier in the discourse or “pointing back”
reference as described by (Mitkov, 1999). The most prevalent type of anaphora
in natural language is the pronominal anaphora (Lappin and Leass, 1994).
Coreference, as the term suggests refers to words or phrases referring to a
single unique entity in the world. Anaphoric and co-referent entities
themselves form a subset of the broader term “discourse parsing” (Soricut and
Marcu, 2003), which is crucial for full text understanding.

In spite of having a rich research history in the NLP community, anaphora
resolution is one of the sub-fields of NLP which has seen the slowest progress
thus establishing the intricacy involved in this task. Some applications of
this task in NLP span crucial fields like sentiment analysis (Cambria, 2016),
summarization (Steinberger et al, 2007), machine translation (Preuss, 1992),
question answering (Castagnola, 2002), etc. Anaphora resolution can be seen as
a tool to confer these fields with the ability to expand their scope from
intra-sentential level to inter-sentential level.

This paper aims at providing the reader with a coherent and holistic overview
of anaphora resolution (AR) and coreference resolution (CR) problems in NLP.
These fields have seen a consistent and steady development, starting with the
earlier rule-based systems (Hobbs, 1978; Lappin and Leass, 1994) to the recent
deep learning based methodologies (Wiseman et al, 2016; Clark and Manning,
2016b, a; Lee et al, 2017b; Young et al, 2018b). Though there have been some
thorough and intuitive surveys, the most significant ones are by (Mitkov,
1999) for AR and (Ng, 2010) for CR.

The detailed survey on AR by (Mitkov, 1999) provides an exhaustive overview of
the syntactic constraints and important AR algorithms. It also analyzes the
applications of AR in other related NLP fields. The most recent survey by (Ng,
2010) targets the research advances in the related field of CR delineating the
mention-pair, entity-mention and mention-ranking models proposed till date.
Both of these surveys are a great resource to gain a deeper understanding of
research methodologies which have been attempted earlier for AR and CR.

The advent of neural networks in NLP has demonstrated performance strides in
most of its sub-fields like POS tagging (Collobert and Weston, 2008), social
data analysis (Oneto et al, 2016), dependency parsing (Chen and Manning,
2014), etc. and this is no different to the field of CR. Thus, this paper is
fueled by the necessity for detailed analysis of state-of-the-art approaches
pertaining to this field. Here, we seek to build on the earlier surveys by
delineating the pioneering research methodologies proposed for these two very
closely related, yet significantly different fields of research. Often the
proposed methodologies differ in the evaluation metrics adopted by them, thus
making comparison of their performance a major challenge. We also provide a
comprehensive section on the evaluation metrics adopted, with the aim of
establishing well defined standards for comparison. Another motivation factor
for this survey is the requirement to establish the standard datasets and open
source toolkits for researchers and off-the-shelf users, respectively.

AR and CR have seen a shifting trend, from methods completely dependent on
hand-crafted features to deep learning based approaches which attempt to learn
feature representations and are loosely based on hand engineered features.
This future trend looks very promising and, hence, we have discussed this in
the comparison section. Another issue which requires to be addressed is the
type of references that can occur in language and the constraints to be
applied to identify the possible co-referring entities. Though state-of-the-
art approaches have demonstrated a significant margin of improvement from the
earlier ones, some rare types of references have gone unnoticed and, hence,
demand attention. This field has faced a long history of debate with regards
to comparison of different types of approaches, the appropriate metrics for
evaluation, the right preprocessing tools, etc. Another topic of debate
pertaining to CR is whether induction of commonsense knowledge aids the
resolution process. We also aim at providing an overview of these issues and
controversies. Through this survey we also aim at analyzing the application of
CR in other NLP tasks with special attention to its application in sentiment
analysis (Chaturvedi et al, 2018), as recently this is one of the hottest
topics of NLP research due to the exponential growth of social media. Finally,
this survey forms building blocks for the reader to better understand this
exciting field of research.

##  2 Types of References in Natural Language

AR is a particularly challenging task because of the different forms the
“references” can take. Most AR and CR algorithms face the “coverage” issue.
This means that most algorithms are designed to target only specific types of
references. Before proceeding to the current state-of-the-art research
methodologies proposed for this task, it is necessary to understand the scope
of this task to its entirety. In this section, we will be discussing the
different semantic and syntactic forms in which the references can occur.

###  2.1 Zero Anaphora

This type of anaphora is particularly common in prose and ornamental English
and was first introduced by (Fillmore, 1986). It is perhaps one of the most
involved type of AR task which uses a gap in a phrase or a clause to refer
back to its antecedent. For example, in the sentence “ _You always have two
fears(1): your commitment(2) versus your fear(3)_” phrases (2) and (3) refer
back (are anaphoric) to the same phrase (1). Hence, the above sentence serves
as an example for a combination of zero anaphora with m-anaphors.

###  2.2 One Anaphora

In this type of anaphora, the word “one” is used to refer to the antecedent.
This type of anaphora, though not very common, has received sufficient
attention from the research community, particularly the machine learning
approach by (Ng and Cardie, 2002b) which specifically targeted this type. The
one anaphora phenomenon can be best illustrated with an example. In the
sentence “ _Since Samantha has set her eyes on the beautiful villa by the
beach(1), she just wants to buy that one (2)_”, the phrase (2) refers back to
the entity depicted by (1).

###  2.3 Demonstratives

This type of reference as explained by (Dixon, 2003) is typically used in
contexts when there is a comparison between something that has occurred
earlier. For example, in the sentence “ _This car is much more spacious and
classy than that(1)_”, phrase (1) refers to a comparison with a car that the
speaker has seen earlier. This is an interesting case of AR wherein the
anaphor is not specified explicitly in the text.

###  2.4 Presuppositions

In this type of references, the pronouns used are someone, anybody, nobody,
anyone, etc. Here, the entity resolution is complicated as there is a degree
of ambiguity involved in the consideration of the noun phrases (NPs) which the
referents can be corresponding to. The projection of presupposition as an AR
task was first introduced by (Van der Sandt, 1992). For example, in the
sentence “ _If there is anyone(1) who can break the spell, it is you(2)_”, the
phrase (2) co-refers with (1). Here, the major source of ambiguity is the
phrase “anyone”.

###  2.5 Discontinuous Sets (Split anaphora)

The issue of clause splitting in AR has been delineated by (Mitkov, 2014). In
this type of anaphora, the pronoun may refer to more than one antecedents.
Commonly the pronouns which refer to more than one antecedents are they, them,
us, both, etc. For example, in the sentence “ _Kathrine(1) and Maggie(2) love
reading. They(3) are also the members of the reader’s club._”, the pronoun (3)
refers to Maggie (2) and Katherine (1) together as a single entity. Most of
the prominent algorithms in anaphora and CR fail to consider this phenomenon.
In this paper, we will be discussing one significantly recent research
methodology which specifically focuses on this issue.

###  2.6 Contextual disambiguation

The issue of contextual disambiguation in AR has been described by (Mitkov,
2014) in his book on AR and attempted by many like (Bean and Riloff, 2004).
Though this problem does not semantically fit into the category of entity
resolution, this issue provides an insight into how two fields in NLP, i.e.,
word sense disambiguation and CR serve to complement each other. For example,
in the sentence “ _The carpenter built a laminate(1) and the dentist built
one(2) too._”, though phrase (2) refers to (1) by the One Anaphora as
discussed earlier, the challenge here lies in understanding how the word
“laminate” can actually refer to very different real world entities based on
the context in which they occur, i.e., the dentist or the carpenter.

###  2.7 Pronominal anaphora

This is one of the most common and prevalent types of anaphora which occur in
day-to-day speech and constitutes a significant portion of the anaphors we
commonly see in web data like reviews, blog posts, etc. This type of anaphora
introduced by (Roberts, 1989; Heim, 1982), has been the focus of many papers.
The earliest one being the paper of (Lappin and Leass, 1994) which aimed at
pronominal resolution. There exist three types of pronominal anaphors:
indefinite pronominal, definite pronominal and adjectival pronominal.

####  2.7.1 Indefinite Pronominal

In this reference type, the pronoun refers to an entity or object which is not
well-defined or well-specified. An example of this type is “ _Many(1) of the
jurors(2) held the same opinion_”, where (2) refers back to (1), though the
exact relation between the referents is ambiguous.

####  2.7.2 Definite Pronominal

This type of reference is definite since it refers to a single unique entity
in the universe. For example, in the sentence “ _She had seen the car(1) which
had met with an accident. It(2) was an old white ambassador_”, pronoun (2)
refers back to entity (1).

####  2.7.3 Adjectival Pronominal

In this type of anaphora, there is reference to adjectival form of the entity
which has occurred earlier. For example, in the sentence “ _A kind stranger(1)
returned my wallet. Such people(2) are rare_”, (2) refers back to (1). Thus,
(1) here is an adjectival form that has been referred to by the anaphor (2).
This example also serves to illustrate that adjectival noun forms can also be
anaphoric.

###  2.8 Cataphora

Cataphora as defined by (Mitkov et al, 2002) is said to be the opposite of
anaphora. A cataphoric expression serves to point to real world entities which
may succeed it. The phenomenon of cataphora is most commonly seen in “poetic”
English. This type is not very common in literature and, hence, most recent
approaches don’t focus on this issue in particular. For example, in the
sentence “ _If she(1) does n’t show up for the examination even today, chances
of Clare(2) clearing this semester are meagre_”, (1) refers to an entity that
precedes it, i.e., (2). In this paper, we will not be reviewing techniques for
cataphora resolution in particular mainly because cataphora are rarely used in
spoken language.

###  2.9 Inferable or Bridging Anaphora

Bridging anaphora (Hou et al, 2013) type of references in natural language are
perhaps one of the most ambiguous ones. They may not explicitly seem to be
pointing to an antecedent but can be said to belong to or refer to an entity
mentioned at some point earlier in time. For example, in the sentence “ _I was
about to buy that exquisite dress(1); just when I noticed a coffee stain on
the lace(2)_”, the entity that (2) refers to, though not stated explicitly, is
entity (1) which can be inferred by their context.

##  3 Non-Anaphoric pronominal references

A major issue which is unanimously tackled by all state-of-the-art methods is
the identification and elimination of empty referents or referents which
potentially do not refer back to any antecedent. The major categories of non-
referential usage are: clefts, pleonastic “it” and extraposition.

###  3.1 Clefts

A cleft sentence is a complex sentence (one having a main clause and a
dependent clause) that has a meaning that could be expressed by a simple
sentence. A cleft sentence typically puts a particular constituent into focus.
Clefts were introduced by (Atlas and Levinson, 1981). For example, in the
sentence “it” cleft is: “ _It(1) was Tabby who drank the milk_”, (1) does not
serve to refer to an antecedent but is a potential trap for most AR systems.

###  3.2 Pleonastic “It”

This issue in AR has received a lot of attention and has been delineated by
(Mitkov, 2014). This type of non-anaphoric referent is very common in natural
language. For example, in the sentence “ _It(1) was raining heavily_”, (1) in
spite of being a pronoun does not refer to any specific entity.

###  3.3 Extraposition

Extraposition is one of the many issues in AR as described by (Gundel et al,
2005). An example of extraposition is the sentence, “ _It was not justified on
her part to insult the waitress_”, where “it” is semantically empty and serves
to imply a behavioural characteristic.

##  4 Constraints for Anaphoric resolution

Most proposed approaches in AR and CR are based on some trivial syntactic and
semantic constraints. Though all constraints may not be relevant for every
type of referent, most methods do apply some if not all of these constraints.
Syntactic approaches are solely based on these constraints and exploit them to
a large extent for AR. Most statistical and machine learning approaches use
these constraints in feature extraction or mention-filtering phase. Recently,
there has been a growing trend towards knowledge poor AR (Mitkov, 1998). This
mainly aims at reducing the level of dependency on these hand-crafted rules.
Also, it is important to understand here that these constraints are not
universally acceptable, i.e., some may not hold true across different
languages. The constraints below are necessary but not sufficient by
themselves to filter out the incorrect references. This section aims at
delineating the linguistic constraints for AR.

###  4.1 Gender agreement

Any co-referring entity should agree on their gender, i.e., male, female or
non-living entity. Gender is a very important constraint in AR as mentioned by
(Mitkov, 2014). Antecedents which do not agree in terms of their gender, need
not be considered further for evaluation of their correctness. This is one of
the crucial constraints which serves to prune the antecedent search space to a
large extent. For example, in the sentence “ _Tom(1) bought a puppy(2). It (3)
is adorable_”, on application of this constraint, (1) is eliminated due to
gender disagreement with (3), thus culminating in (it=puppy). The question
which arises here is what happens when there are multiple antecedents
satisfying gender constraint. This brings about the necessity to enforce some
other syntactic and semantic constraints.

###  4.2 Number agreement

An entity may corefer with another entity if and only if they agree on the
basis of their singularity and plurality. This constraint is even incorporated
into machine learning systems like (Ng and Cardie, 2002b). This constraint is
necessary but not sufficient and the final resolution may be subject to the
application of other constraints. For example, in the sentence “ _ Fatima and
her sisters(1) bought groceries(2) for the week(3). Recently, there has been a
huge hike in their(4) prices_”, the pronominal reference (4) refers to (2) and
(1). Referent (3) is successfully eliminated on the basis of number
disagreement.

###  4.3 Constraints on the verbs (Selectional constraints)

Human language type-casts certain verbs to certain entities. There are certain
verbs which occur with only animate or living entities and some others
specifically on the inanimate ones. Constraints on verbs have been exploited
in many methods like (Haghighi and Klein, 2009). The sentence “ _I sat on the
tortoise(1) with a book(2) in my hand, assuming it to be a huge pebble and
that’s when it(3) wiggled_”, for example is very difficult for a computer to
interpret. Here, (3) can refer to (2) or (1). The reference (2) should be
filtered out here using the animacy constraint. This constraint brings about
the necessity to incorporate world knowledge into the system.

###  4.4 Person agreement

Linguistics has three persons namely the first (i.e., I, me), second (i.e.,
you) and third (i.e., he, him, she, it, they). This feature has been exploited
by many approaches like (Lappin and Leass, 1994). The co-referent nouns or
entities must agree with respect to their person. For example, in the sentence
“ _John and Sally(1) are siblings. It’s amazing how significantly different
they(2) are from each other_”, (2) refers to (1) as they agree with respect to
their person. In case the pronoun (2) had been “we” this possible antecedent
would have been eliminated.

###  4.5 Grammatical role

Any given sentence can be decomposed to its subject, verb and object part and
these roles of the words in the sentence can aid AR as mentioned by (Kennedy
and Boguraev, 1996). Entities occurring in the subject portion of a sentence
are given a higher priority than the entity in object position. For example,
in the sentence “ _Kavita(1) loves shopping. She goes shopping with her
sister(2) every weekend. She(3) often buys stuff that she may never use_, (3)
refers to (1) and not to (2) as (1) being the subject has more priority or
salience over (2).

###  4.6 Recency

As mentioned in (Carbonell and Brown, 1988) recency is an important factor of
consideration in AR. Entities introduced recently have more salience than
entities which have occurred earlier in the discourse. For example, in the
sentence “ _I have two dogs. Steve(1), a grey hound, is a guard dog. Bruno(2)
who is a Labrador is pampered and lazy. Sally often takes him(3) for a
stroll_”, (3) may refer to (1) or (2) syntactically. To resolve this ambiguity
this constraint gives more salience to (2) over (3) due to the entity’s
recency.

###  4.7 Repeated mention

Repeated mention forms a feature of many system like the statistical method of
(Ge et al, 1998). Entities which have been introduced repeatedly in the
context or have been the main focus or topic of the earlier discourse are
given a higher priority than the rest. For example, in the sentence “
_Katherine(1) is an orthopaedic surgeon. Yesterday she ran into a patient(2),
she had not been in contact with her since ages. She(3) was amazed at her
speedy recovery_”, the referent (3) refers to (1) and not (2) because
Katherine (1) here is an entity that has been in focus in prior discourse and,
hence, is more salient.

###  4.8 Discourse structure

The preference of one entity over another can also be due to the structural
idiosyncrasies of the discourse like parallelism. These phenomenon are
discussed by (Carbonell and Brown, 1988) in their paper and form a crucial
component of Centering Theory. For example, in the sentence “ _Aryan(1) passed
a note to Shibu(2) and Josh(3) gave him (4) a chocolate_”, (4) refers to (2)
and not (1) due to the discourse structure involved here. Though the
occurrence of this type of discourse is tough to spot and disambiguate, if
exploited appropriately this can increase the precision factor involved in the
CR to a large extent.

###  4.9 World Knowledge

This is the constraint that has a very wide scope and generally cannot be
completely incorporated into any system. In spite of this, attempts to
incorporate this behavior in CR system has been made by (Rahman and Ng, 2011).
Though syntax does play a role in entity resolution, to some extent world
knowledge or commonsense knowledge does function as a critical indicator.
Commonsense concepts like “cat-meows” and “dog-barks” cannot be resolved only
by studying the syntactic properties. One obvious example where syntax by
itself fails to identify the appropriate antecedent are the sentences
_The city councilmen (1) refused the demonstrators (2) a permit because they
(3) advocated violence._
_The city councilmen (1) refused the demonstrators (2) a permit because they
(3) feared violence._

As cited by some researchers (Levesque et al, 2011), here world knowledge
needs to be incorporated to disambiguate “they”. In the first sentence (3)
refers to (2) and in the second sentence (3) refers to (1). What results in
this transition here is only the change of the verb involved in the discourse.

##  5 Evaluation metrics in CR

There are a number of metrics which have been proposed for the evaluation of
CR task. Here, we delineate the standard metrics used to evaluate the task.

###  5.1 Bagga and Baldwin’s B-cubed metric

This metric proposed by (Bagga and Baldwin, 1998) begins by computing a
precision and recall for each individual mention and, hence, takes weighted
sum of these individual precision and recalls. Greedy matching is undertaken
for evaluation of chain-chain pairings.

$FinalPrecision=\sum_{i=1}^{N}w_{i}*Precision$ (1)
$FinalRecall=\sum_{i=1}^{N}w_{i}*Recall$ (2)

Where N= Number of entities in the document and $w_{i}$ is the weight assigned
to entity i in the document. Usually the weights are assigned to $1/N$.

###  5.2 MUC- Link based F-measure

This metric, proposed during the 6th Message Understanding Conference by
(Vilain et al, 1995) considers a cluster of references as linked references,
wherein each reference is linked to at most two other references. MUC metric
primarily measures the number of link modifications required to make the
result-set identical to the truth-set.

$partition(c,s)=\mbox{\\{}s|s\in S\mbox{ \& }s\in c\neq\phi\mbox{\\}}$ (3)

The MUC Precision value is calculated as follows:

$MUCPrecision(T,R)=\sum_{r\in R}\frac{|r|-|partition(r,T)|}{|r|-1}$ (4)

Where, $|partition(r,T)|$ is the number of clusters within truth T that the
recall cluster _r_ intersects with. The MUC Recall value is calculated as
follows:

$MUCRecall(T,R)=\sum_{t\in T}\frac{|t|-|partition(t,R)|}{|t|-1}$ (5)

Where, $|partition(t,R)|$ represents the number of clusters within the result
R that truth set $|t|$ intersects with.

###  5.3 CEAF: Constrained Entity Alignment F-measure

This metric proposed by (Luo, 2005) is used for entity-based similarity
identification. It uses similarity measures to first create an optimal mapping
between result clusters and truth clusters. Using this mapping, CEAF leverages
self-similarity to calculate the precision and recall. This similarity measure
is computed using the following equations:

$\phi_{1}(T,R)=\begin{cases}1&\mbox{if R=T}\\\ 0&\mbox{otherwise}\end{cases}$
(6) $\phi_{2}(T,R)=\begin{cases}1,&\mbox{if R}\cap T\neq\phi\\\
0,&\mbox{otherwise}\end{cases}$ (7) $\phi_{3}(T,R)=|R\cap T|$ (8)
$\phi_{4}(T,R)=2.\frac{|R\cap T|}{|R|+|T|}$ (9)

The function $m(r)$ takes in a cluster _r_ and returns the true cluster _t_
that the result cluster _r_ is mapped to with constraint that one cluster can
be mapped to at most one result cluster.

$CEAF_{\phi_{i}}Precision(T,R)=max_{m}\frac{\sum_{r\in
R}\phi_{i}(r,m(r))}{\sum_{r\in R}\phi_{i}(r,r)}$ (10)
$CEAF_{\phi_{i}}Recall(T,R)=max_{m}\frac{\sum_{r\in
R}\phi_{i}(r,m(r))}{\sum_{r\in R}\phi_{i}(t,t)}$ (11)

###  5.4 ACE-Value

The ACE evaluation score (Doddington et al, 2004), proposed during the
Automatic Content Extraction Conference is also based on optimal matching
between the result and the truth like CEAF. The difference between the two is
that ACE’s precision and recall is calculated using true positives, false
positives, false negatives amongst the predicted co-referent entities. Another
difference is that ACE does not normalize its precision and recall values
unlike the CEAF metric.

###  5.5 CoNLL score

This score is calculated as the average of the B-cubed score, MUC score and
the CEAF score. This is the score used by the CoNLL-2012 shared task by
(Pradhan et al, 2012) which is based on CR in the OntoNotes corpus. Thus, the
CoNLL score is calculated as shown in the equation below.

$CoNLL=\frac{(MUC_{F1}+\mbox{B-Cubed}_{F1}+CEAF_{F1})}{3}$ (12)

###  5.6 BLANC metric

BLANC (Recasens et al, 2010; Pradhan et al, 2014) is a link-based metric that
adapts the Rand index (Rand, 1971) CR evaluation. Given that $C_{k}$ is the
key entity set and $C_{r}$ is the response entity set, the BLANC Precision and
Recall is calculated as follows. $R_{c}$ and $R_{n}$ refer to recall for
coreference links and non-coreference links, respectively. Precision is also
defined with a similar notation.

$R_{c}=\frac{|C_{k}\cap C_{r}|}{|C_{k}|}$ (13) $P_{c}=\frac{|C_{k}\cap
C_{r}|}{|C_{r}|}$ (14) $R_{n}=\frac{|N_{k}\cap N_{r}|}{|N_{k}|}$ (15)
$P_{c}=\frac{|N_{k}\cap N_{r}|}{|N_{r}|}$ (16) $Recall=\frac{R_{c}+R_{n}}{2}$
(17) $Precision=\frac{P_{c}+P_{n}}{2}$ (18)

The mention identification effect delineated by (Moosavi and Strube 2016)
affects BLANC metric very strongly and, hence, this metric is not widely
adopted.

###  5.7 LEA metric

Link-based Entity-Aware (LEA) metric proposed by (Moosavi and Strube, 2016)
aims at overcoming the mention identification effect of the earlier
coreference evaluation metrics which makes it impossible to interpret the
results properly. LEA considers how important the entity is and how well is it
resolved. LEA metric is dependent on two important terminologies which are
_importance_ and _resolution-score_. Importance is dependent on size of the
entity and Resolution-Score is calculated using link similarity. The link
function returns the total number of possible links between _n_ mentions of an
entity _e_.

$\text{importance}(e_{i})=|e_{i}|$ (19) $\text{resolution-
score}(k_{i})=\sum_{r_{j}\in R}\frac{link(k_{i}\cap r_{j})}{link(k_{i})}$ (20)
$Recall=\frac{\sum_{k_{i}\in K}importance(k_{i})*\sum_{r_{j}\in
R}\frac{link(k_{i}\cap r_{j})}{link(k_{i})}}{\sum_{k_{z}\in
K}importance(k_{z})}$ (21) $Precision=\frac{\sum_{r_{i}\in
R}importance(r_{i})*\sum_{k_{j}\in K}\frac{link(r_{i}\cap
k_{j})}{link(r_{i})}}{\sum_{r_{z}\in R}importance(r_{z})}$ (22)

In the above equations, $r_{i}$ represents the result set and $k_{i}$
represents the key set or the gold set.

###  5.8 Comparison of evaluation metrics

The MUC-score which was one of the earliest metric to be proposed for CR has
some drawbacks as pointed out by (Luo, 2005). Being link based MUC score
ignores singleton-mention entities, since no link can be found in the
entities. It also fails to distinguish the different qualities of system
outputs and favors system producing fewer entities. Thus, in some cases MUC-
score may result in higher F-measure for worse systems. B-cubed metric which
was MUC-score’s successor aimed at fixing some of the problems associated with
the metric. However, an important issue associated with B-cubed is that it is
calculated by comparing entities containing the mention and, hence, an entity
can be used more than once. The BLANC metric (Recasens and Hovy, 2011) is also
quite flawed because it considers the non-coreference links which increase
with increase in gold mentions, thus giving rise to the mention identification
effect. ACE metric which is very closely related to CEAF metric is not very
interpretable. CEAF metric solves the interpretability issue of the ACE-metric
and the drawbacks of MUC F1 score and B-cubed F1 score. However, CEAF metric
has problems of its own too. As mentioned by (Denis and Baldridge, 2009) CEAF
ignores all correct decisions of unaligned response entities that may lead to
un-reliable results. A recent paper which particularly targets this flaw
(Moosavi and Strube, 2016) discusses the issues with the existing metrics and
proposes a new link aware metric (LEA metric). The figure below represents the
different types of metrics proposed till date.

Coreference Resolution Evaluation Metrics Mention Based Link Based Optimal
Mapping Based Link Based Entity Aware B-Cubed metric MUC metric BLANC metric
ACE value CEAF metric LEA metric Figure 1: Evaluation Metrics

##  6 Comparison between Anaphora and Coreference Resolution

AR is an intra−linguistic terminology, which means that it refers to resolving
entities used within the text with a same “sense”. Also, these entities are
usually present in the text and, hence, the need of world-knowledge is
minimal. CR, on the other hand, has a much broader scope and is an extra-
linguistic terminology. Co-referential terms may have completely different
“senses” and yet, by definition, they refer to the same extra linguistic
entity. Coreference treats entities in a way more similar to how we understand
discourse, i.e., by treating each entity as a unique entity in real time.

The above explanation elicits that AR is a subset of CR. However, this claim
though commonly made fails in some cases as stated by (Mitkov, 2001a) in his
example: _Every speaker had to present his paper_. Here, if “his” and “every
speaker” are said to co-refer (i.e., considered the same entity), the sentence
is interpreted as “Every speaker had to present Every speaker’s paper” which
is obviously not correct. Thus, “his” here is an anaphoric referent and not
coreferential, hence demarcating the two very similar but significantly
different concepts. This is a typical case of the bound variable problem in
entity resolution. Hence, the often made claim that AR is a type of CR, fails
in this case.

Some researchers also claim that coreference is a type of AR. However, this
can often be seen as a misnomer of the term “anaphora”, which clearly refers
to something that has occurred earlier in the discourse. CR, on the other
hand, spans many fields like AR, cataphora resolution, split antecedent
resolution, etc. For example: _If he(1) is unhappy with your work, the CEO(2)
will fire you_. Here, the first reference is not anaphoric as it does not have
any antecedent, but (1) is clearly coreferent with (2). What we see here is
the occurrence of the “cataphora” phenomenon. Thus, this claim too fails to
capture these phenomenon adequately. Though these two concepts have a
significant degree of overlap, they are very different and can be represented
by the chart below.

Figure 2: Vein Diagram of Entity Resolution

There is a clear need for redefinition of the CR problem. We find that the
standard datasets like CoNLL 2012 (Pradhan et al, 2012) fail to capture the
problem to its entirety. To address the fuzziness involved in the
terminologies used in entity resolution, we suggest that the datasets created
for the task explicitly specify the coreference type they have considered for
annotation and the ones they have not. We also insist that future entity
resolution (CR, AR, etc.) models also perform exhaustive error analysis and
clearly state the types of references which their algorithms fail to resolve.
This will serve two purposes: first it will help the future researchers focus
their efforts on specific types of references like co-referent event
resolution which most models fail to resolve and secondly, this will also help
surface some clear issues in the way we currently define the task

##  7 Coreference and Anaphora Resolution Datasets

The datasets predominantly used for the task of CR differ based on a number of
factors like their domain, their annotation schemes, the types of references
which are labelled, etc. Thus, it is crucial to develop a clear understanding
of the AR and CR datasets before proceeding to the research methodologies
pertaining to the task which use these datasets either for training or for
deriving effective rules. Every new dataset for AR and CR was introduced with
the aim of addressing the issues with the earlier ones.

Though there are myriad datasets available for this task there are some major
ones which have been widely popular for evaluation purposes. The three main
corpora created targeting this task were the MUC, the ACE and the OntoNotes
corpora. The MUC-6 (Grishman and Sundheim, 1996) and MUC-7 (Chinchor, 1998)
have been typically prepared by human annotators for training, dry run text
and formal run test usage. The MUC datasets which were the first corpora of
any size for CR, are now hosted by Linguistic Data Consortium. These dataset
contains 318 annotated Wall Street Journal (WSJ) Articles mainly based on
North American news corpora. The co-referring entities are tagged using SGML
tagging based on the MUC format. The evaluation on this dataset is carried out
using the MUC scoring metric. Now that larger resources containing multi-genre
documents are available these datasets are not widely used any more except for
comparison with baselines. The ACE corpus (Doddington et al, 2004) which was
the result of series of evaluations from 2000 to 2008 is labelled for
different languages like English, Chinese and Arabic. Though initial version
of this corpus was based on news-wire articles like MUC the later versions
also included broadcast conversations, web-log, UseNet and conversational
telephonic speech. Thus, this dataset is not genre specific and is
heterogeneous. ACE is mainly annotated for pronominal AR and is evaluated
using the ACE-score metric.

The Task-1 of SemEval 2010 defined by (Recasens et al, 2010) was CR. This
dataset is made freely available for the research community. The annotation
format of the SemEval Dataset is similar to the CoNLL dataset and it is
derived from the OntoNotes 2.0 corpus. SemEval 2010 CR task can be seen as a
predecessor of the CoNLL-2012 shared task. The CoNLL 2012 shared task (Pradhan
et al, 2012) targeted the modeling of CR for multiple languages. It aimed at
classifying mentions into equivalence classes based on the entity they refer
to. This task was based on the OntoNotes 5.0 dataset which mainly contains
news corpora. This dataset has been widely used recently and is freely
available for research purposes.

Unlike the datasets discussed earlier, the GNOME corpus by (Poesio, 2004)
contains annotated text from the museum, pharmaceutical and tutorial dialogue
domains and, hence, is very useful for cross-domain evaluation of AR and CR
algorithms. Since this corpus was mainly developed for study of centering
theory, it focuses on “utterance” labelling. The GNOME corpus is not freely
distributed. The Anaphora Resolution and Underspecification (ARRAU) corpus
(Poesio et al, 2008) is a corpus labelled for anaphoric entities and
maintained by LDC. This corpus is a combination of TRAINS (Gross et al, 1993;
Heeman and Allen, 1995), English Pear (Watson-Gegeo, 1981), RST (Carlson et
al, 2003) and GNOME datasets. It is labelled for multi-antecedent anaphora,
abstract anaphora, events, actions and plans. It is labelled using the MMAX2
format which uses hierarchical XML files for each document, sentence and
markable. This is a multi-genre corpora, based on news corpora, task oriented
dialogues, fiction, etc. The ARRAU guidelines were also adapted for the
LIVEMEMORIES corpus (Recasens and Martí, 2010) for AR in the Italian Language.

In addition to the above corpora, there were some corpora which were created
for task-specific CR. The ParCor dataset by (Guillou et al, 2014) is mainly
for parallel pronoun CR across multiple languages. It is based on the genre of
TEDx talks and Bookshop publications. The corpora is annotated using the MMAX2
format. This parallel corpus is available in two languages German and English
and mainly aims at CR for machine translation. The Character Identification
Corpus is a unique corpus by (Chen and Choi, 2016) which contains multi-party
conversations (TV show transcripts) labelled with their speakers. This dataset
is freely available for research and is annotated using the popular CoNLL
format. This dataset like GNOME is extremely useful for cross-domain
evaluation. This corpus was introduced mainly for the task of character-
linking in multi-party conversations. The task of Event CR has also received
significant amount of attention. The NP4E corpora (Hasler and Orasan, 2009) is
labelled for corefering events in the texts. This corpus is based on terrorism
and security genres and is annotated in the MMAX2 format. Another event
coreference dataset is the Event Coreference Bank (ECB$+$) (Cybulska and
Vossen, 2014) dataset for topic-based event CR. The dataset is available for
download and is annotated according to the ECB$+$ format.

The GUM corpus (Zeldes, 2017) is another open source multilayer corpus of
richly annotated web texts. It contains conversational, instructional and news
texts. It is annotated in the CoNLL format. The WikiCoref dataset (Ghaddar and
Langlais, 2016), maps the CR task to Wikipedia. The dataset mainly consists of
30 annotated Wikipedia articles. Each annotated entity also provides links to
FreeBase knowledge repository for the mentions. The dataset is annotated in
OntoNotes schema using the MaxNet tagger and is freely available for download.
GUM and WikiCoref are both mainly based on Wikipedia data. These datasets
aimed to address two main issues in CR datasets: domain adaptation and world
knowledge induction.

In this article, our main focus is the study of the CR task in English, but it
is very interesting to note that there are datasets available to address this
issue in multiple languages. The ACE corpora (Doddington et al, 2004) and the
CoNLL-2012 (Pradhan et al, 2012) shared task in addition to English are also
labelled for the Chinese and Arabic languages. The SemEval 2010 Task-1
(Recasens et al, 2010) also provides datasets for CR in Catalan, Dutch,
German, Italian and Spanish languages. The ParCor (Guillou et al, 2014) corpus
is also labelled for German language. The AnCora-Co (Recasens and Martí, 2010)
corpus has also been labelled for coreference in Spanish and Catalan.

Table 1: AR and CR datasets Comparison Dataset | Multi-lingual | Multi-Domain |  | Intra-Document
---
Annotation
| Inter-Document
---
Annotation
CoNLL-2012 | ✓ | ✓ | ✓ | ✗
ECB+ | ✗ | ✗ | ✓ | ✓
SemEval 2010 | ✓ | ✓ | ✓ | ✗
ARRAU | ✗ | ✓ | ✓ | ✗
CIC | ✗ | ✗ | ✓ | ✗
MUC 6 & 7 | ✗ | ✗ | ✓ | ✗
ParCor | ✓ | ✓ | ✓ | ✗
GUM | ✗ | ✓ | ✓ | ✗
NP4E | ✗ | ✗ | ✓ | ✓
ACE | ✓ | ✓ | ✓ | ✗
WikiCoref | ✗ | ✓ | ✓ | ✗
GNOME | ✗ | ✓ | ✓ | ✗
Table 2: English Coreference and Anaphora Resolution Datasets Dataset | Source Corpora | Statistics | Genre | Annotation Scheme | Availability
---|---|---|---|---|---
CoNLL-2012 (Pradhan et al, 2012) | OntoNotes 5.0 Corpus |  | Train docs:2802
---
Test docs:348
Dev docs:343
Total docs: 3493
| News, conversational
---
telephone speech,
web-logs, UseNet
newsgroups, talk shows
CoNLL format |  | Freely available
---
through LDC
ECB+ (Cybulska and Vossen, 2014) | Google News | Total docs:982 | News | ECB+ format | Freely available
SemEval 2010 (Recasens et al, 2010) | English: OntoNotes 2.0 |  | Train docs:229
---
Test docs:85
Dev docs:39
| News, conversational
---
telephone speech, web-logs,
UseNet newsgroups,
talk shows
CoNLL format |  | Freely available
---
through LDC
ARRAU 2 (Poesio et al, 2008) |  | TRAINS, English Pear,
---
RST, GNOME
Total docs:552 |  | News (RST),
---
task-oriented dialogues
(TRAINS), fiction
(PEAR) and medical
leaflets (GNOME)
MMAX2 format |  | Available by payment
---
through LDC
|  CIC (Chen and Choi, 2016)
---
| Dialogue Scripts of
---
Friends TV Show (Season 1
and 2), and The Big Bang
Theory TV Show (Season 1)
| Train docs(Episodes+ Scenes): 478
---
Dev docs(Episodes+ Scenes):51
Test docs(Episodes+Scenes):77
TV Show Dialogues | CoNLL format |  | Freely available
---
for download
MUC 6 & 7 (Grishman and Sundheim, 1996) |  | MUC 6:WSJ corpus,
---
MUC 7: NY Times Corpu
| MUC 6-Train docs:30, Test docs:30,
---
Total docs:60
MUC 7-Train docs:30, Test docs:20,
Total docs:50
News |  | MUC SGML tagging
---
format
| Available by payment
---
through LDC
ParCor (Guillou et al, 2014) | Multilingual SMT Corpora | Total docs:19 |  | EU Bookshop and TED Talks
---
MMAX2 | Freely Available
GUM (Zeldes, 2017) |  | Wikinews, WikiHow,
---
WikiVoyage, Reddit,
Wikipedia
Total docs:101 |  | News (narrative)
---
Interview (conversational)
How-to (instructional)
Travel guide (informative),
Academic Writing,
Biographies, Fiction,
Forum Discussions
| Richly annotated
---
with multiple layers
of annotation like
RST, CoNLL,
WebAnno, ISO
date/time,
Dependencies etc
Freely Available
NP4E (Hasler and Orasan, 2009) | Reuters Corpus |  | Total docs:
---
(NP+Event Coreference)
104+20=124
| News in domain of
---
Terrorism/Security
| Available in NP4E
---
defined annotation and
MMAX format
Freely Available
ACE 2007 (Doddington et al, 2004) |  | News articles from:
---
New York Times,
Cable News Network, etc.
Total docs: 599 |  | Weblogs, Broadcast
---
Conversation, Broadcast
News, News Groups
ACE format |  | Available by payment
---
through LDC
WikiCoref (Ghaddar and Langlais, 2016) | Wikipedia | Total docs:30 |  | People, Organization,
---
Human made Object,
Occupation
CoNLL format | Freely Available
GNOME corpus (Poesio, 2004) |  | Museum:ILEX, SOLE
---
corpora Pharmaceuticals:
ICONOCLAST corpora,
and Dialogues:
Sherlock corpus
Total docs:5 |  | Museum, Pharmaceuticals,
---
Tutorial Dialogues
GNOME format | Not Available

The preceding datasets are labelled on multiple text genres. Recently, there
has also been a surge of interest in the area of domain specific CR,
particularly biomedical CR. This can be attributed to the BioNLP-2011 (Kim et
al, 2011) CR task which was built on the GENIA corpus and contains Pubmed
abstracts. There are mainly two lines of research in the biomedical CR task:
annotation of abstract and full-text annotations.

In abstract annotation, biomedical abstracts are labelled with co-referent
entity types. These datasets mainly use annotation scheme like MUC-7 and
restrict to labelling of only biomedical entity types. The MedCo1 corpus
described by (Su et al, 2008) consists of coreference annotated Medline
abstracts from GENIA dataset. The Protein Coreference resolution task was a
part of BioNLP-2011 shared task (Kim et al, 2011). The dataset for the task
was a combination of three resources: MedCo coreference annotation (Su et al,
2008), Genia event annotation (Kim et al, 2008), and Genia Treebank (Tateisi
et al, 2005) all of which were based on the GENIA corpus by (Kim et al, 2003).
This task focused on resolution of names of proteins. Medstract is a large
corpus of medline abstracts and articles labelled for CR which was introduced
by (Pustejovsky et al, 2002). The coherence and anaphora module of this
dataset focuses on resolution of biologically relevant sortal terms (proteins,
genes as well as pronominal anaphors). It is mainly concerned with two types
of anaphora namely pronominal and sortal anaphora. DrugNerAR corpus proposed
by (Segura-Bedmar et al, 2009) aims at resolving anaphoras for extraction
drug-drug interactions in pharmacological literature. It is derived from the
DrugBank corpus which contains 4900 drug entries. This corpus was created by
extracting 49 structured and plain unstructured and plain documents which were
randomly taken from field interactions and, hence, annotated for nominal and
pronominal anaphora.

There are a lot of benefits associated with using full-text instead of
abstracts for biomedical CR. Though such fully annotated biomedical texts are
not very accessible, there are three very interesting projects which aim at
creating this type of corpora. The Corlando Richly Annotated Full-Text or
CRAFT corpus (Cohen et al, 2010) contains 97 full-length open access
biomedical journal articles that have been annotated both semantically and
syntactically to serve as a resource for the BioNLP community. Unlike the
other corpora created for CR in biomedical literature this corpus is drawn
from diverse biomedical disciplines and are marked up to their entirety. The
FlySlip corpus (Gasperin and Briscoe, 2008) was introduced with the aim of
addressing the issues associated with the earlier BioNLP Corpora which mainly
considered only short abstracts. Since anaphora is a phenomenon that develops
through a text, this paper posited that short abstracts are not he best
resources to work with. The domain of this corpora is fruit fly genomics and
it labels direct and indirect sortal anaphora types. The HANNAPIN corpus
(Batista-Navarro and Ananiadou, 2011) was a successor of CRAFT corpus which
also annotates full biomedical articles for CR. The annotated 20 full-text
covers several semantic types like proteins, enzymes, cell lines and
pathogens, diseases, organisms, etc. This resource is openly available for
researchers.

Table 3: Comparison of Biomedical coreference datasets Dataset | Type | Statistics | Annotation | Availability
---|---|---|---|---
MEDSTRACT | Abstract Annotation | 100 abstracts | MUCCS | publicly available
MEDCo-A | Abstract Annotation | 1999 abstracts | MUCCS | publicly available
MEDCo-B | Full-Text Annotation | 43 full texts | MUCCS | currently unavailable
FlySlip | Full-Text Annotation | 5 full texts | FlySlip scheme | publicly available
CRAFT | Full-Text Annotation | 97 full texts | OntoNotes | currently unavailable
DrugNERAr | Full-Text Annotation | 49 full texts | MUCCS | publicly available
HANNAPIN | Full-Text Annotation | 20 full texts | MEDCo-scheme | publicly available

.

##  8 Reference Resolution Algorithms

###  8.1 Rule-based entity resolution

Reference resolution task in NLP has been widely considered as a task which
inevitably depends on some hand-crafted rules. These rules are based on
syntactic and semantic features of the text under consideration. Which
features aid entity resolution and which do not has been a constant topic of
debate. There have also been studies conducted specifically targeting this
issue (Bengtson and Roth, 2008; Moosavi and Strube, 2017). Thus, most of the
earlier AR and CR algorithms were dependent on a set of hand-crafted rules
and, hence, were “knowledge rich”.

Hobb’s naïve algorithm (Hobbs, 1978) was one of the first algorithm to tackle
AR. This algorithm used a rule-based, left to right breadth-first traversal of
the syntactic parse tree of a sentence to search for an antecedent. The Hobb’s
algorithm also used world knowledge based selectional constraints for
antecedent elimination. The rules and selectional constraints were used to
prune the antecedent search space till the algorithm converged to a single
antecedent. This algorithm was manually evaluated on different corpora like
fiction and non-fiction books and news magazines.

Another knowledge-rich algorithm was the Lappin and Leass algorithm (Lappin
and Leass, 1994) for pronominal AR. This algorithm was based on the salience
assignment principle. This algorithm maintained a discourse model consisting
of all potential antecedent references corresponding to a particular anaphor.
Each antecedent was assigned a salience value based on a number of features.
The salience categories were recency, subject emphasis, existential emphasis,
accusative emphasis, indirect object emphasis, non-adverbial emphasis and head
noun emphasis. The strategy followed here was to penalize or reward an
antecedent based on its syntactic features. The algorithm started with
generation of a list of possible antecedents extracted using the syntactic and
semantic constraints mentioned earlier. Then, a salience value was assigned to
each antecedent. The salience was calculated as a sum over all the
predetermined salience values corresponding to the salience category
satisfied. The antecedent with the maximum salience value was proposed as the
appropriate antecedent. The Lappin and Leass algorithm also incorporated a
signal attenuation mechanism wherein the influence or salience of an
antecedent was halved on propagation to next sentence in the discourse and was
evaluated on a dataset consisting of five computer science manuals.

The earliest attempt at exploiting discourse properties for pronoun resolution
was the BFP algorithm (Brennan et al, 1987). This algorithm motivated the
centering theory. The centering theory (Grosz et al, 1995) was a novel
algorithm used to explain phenomenon like anaphora and coreference using
discourse structure. In centering theory, the center was defined as an entity
referred to in the text which linked multiple “utterances” or sentences in the
discourse. Forward looking centers were defined as set of centers that were
referred to in an utterance. The backward looking center was defined as a
single center belonging to the intersection of the sets of forward centers of
the current and the preceding utterance. This algorithm started with creation
of all possible anchors, i.e., pairs of forward centers and backward entities.
The ordering of the centers was done according to their prominence and their
position in the utterance. The backward looking center was defined as the
current topic and the preferred center was the potential new topic. The three
major phases in center identification were: center continuation, where same
center was continued for the next sentence in discourse, center retaining,
wherein there was a possible indication for shift of the center and center-
shifting wherein there was a complete shift in the center involved. As
summarized by (Kibble, 2001) there were two key rules governing centering
theory. The Rule 1 stated that the center of attention was the entity that was
most likely to be pronominalized and Rule 2 stated that there was a preference
given to keep the same entity as the center of attention. Apart from these
rules various discourse filters were also applied to filter out good and bad
anchors and the remaining good ones were ranked according to their transition
type. The centering algorithm was evaluated on Hobb’s datasets and some other
Human-Keyword task oriented databases. There were many modifications proposed
on centering theory and the most significant one was the Left Right Centering
theory (Tetreault, 2001, 1999). This was based on the observation in
Psycholinguistic research that listeners attempted to resolve an anaphor as
soon as they heard it. LRC (Tetreault, 1999) first attempted to find the
antecedent in the current utterance itself and if this does not work it
proceeds to process the previous utterances in a left to right fashion.
Another modification on LRC, i.e., LRC-F (Tetreault, 2001) also encoded
information about the current subject into the centering theory.

Though most of the rule-based algorithms were knowledge rich, there were some
(Baldwin, 1997; Harabagiu et al, 2001; Haghighi and Klein, 2009; Lee et al,
2013; Zeldes and Zhang, 2016) that aimed at reducing the level of dependency
of rules on external knowledge. These were categorized as the “knowledge-poor
algorithms”. CogNIAC (Baldwin, 1997) was a high precision coreference resolver
with limited resources. This early method moved a step closer to how human
beings resolve references. Take, for example, the sentence: _Charles (1) went
to the concert with Ron (2) and he hurt his (3) knee on the way back._ Here,
the resolution of (3) is an intricate task for a human being due to inevitable
requirement of knowledge beyond the discourse. Thus, CogNIAC was based on the
simple but effective assumption that there existed a sub class of anaphora
that did not require general purpose reasoning. Thus, if an anaphoric
reference required external world resources in its resolution CogNIAC simply
did not attempt its resolution. Here, CogNIAC could be considered to be
analogous to a human who recognizes knowledge intensive resolutions and makes
a decision on when to attempt resolution. CogNIAC was evaluated on myriad
datasets like narratives and newspaper articles and in scenarios with almost
no linguistic preprocessing to partial parsing. The core rules defining
CogNIAC were picking a unique or single existent antecedent in current or
prior discourse, the nearest antecedent for a reflexive anaphor, picking exact
prior or current string match for possessive pronoun, etc. Adhering to the
these core rules or presuppositions, the CogNIAC’s algorithm proceeded to
resolve pronouns from left to right in the given text. Rules were followed in
an orderly fashion and once a given rule was satisfied and antecedent match
occurred no further rules are attempted. On the other hand, if none of the
rules were satisfied CogNIAC left the anaphor unresolved. Two additional
constraints were deployed during the evaluation phase of CogNIAC. These two
constraints were picking the backward center which is also the antecedent as
the target solution and the second one was picking the most recent potential
antecedent in the text. CogNIAC was evaluated on multiple datasets like
narratives and newspaper articles.

Apart from the methods discussed earlier which were a combination of salience,
syntactic, semantic and discourse constraints, attempts have also been made to
induce world knowledge into the CR systems. The COCKTAIL system (Harabagiu and
Maiorano, 1999), basically a blend of multiple rules, was one such system
which took a knowledge-based approach to mining coreference rules. It used
WordNet for semantic consistency evidence and was based on structural
coherence and cohesion principles. It was evaluated on the standard MUC 6 CR
dataset.

Another rule-based algorithm which took a knowledge-based approach to entity
resolution specifically for pronominal AR was the rule-based algorithm by
(Liang and Wu, 2004) for automatic pronominal AR. In this algorithm, WordNet
ontology and heuristic rules were deployed to develop an engine for both
intra-sentential and inter-sentential antecedent resolution. This algorithm
started with parsing each sentence in the text, POS tagging and lemmatizing
it. These linguistic features were stored in an internal data structure. This
global data structure was appended with some other features like base nouns,
number agreement, person name identification, gender, animacy, etc. This model
also constructed a finite state machine with the aim of identifying the NPs.
The parsed sentence was then sequentially checked for anaphoric references and
pleonastic it occurrences. The remaining mentions were considered as possible
candidates for antecedents and were heuristically evaluated using a scoring
function. The toolkit was extensively evaluated on reportage, editorials,
reviews, religion, fiction, etc.

As the research in CR started to shift towards machine learning algorithms
which used classification and ranking it slowly became clear that to beat the
machine learning systems, rules had to be ordered according to their
importance. A rule-based CR baseline which gained wide acclaim was the
deterministic CR system by Haghini and Klein (H and K model) (Haghighi and
Klein, 2009), who proposed a strong baseline by modularizing syntactic,
semantic and discourse constraints. In spite of its simplicity it outperformed
all the unsupervised and most of the supervised algorithms proposed till then.
This algorithm first used a module to extract syntactic paths from mentions to
antecedents using a syntactic parser. It then proceeded by eliminating some
paths based on deterministic constraints. After this, another module was used
evaluate the semantic compatibility of headwords and individual names.
Compatibility decisions were made from compatibility lists extracted from
corpora. The final step was the elimination of incompatible antecedents and
selection of the remaining antecedents so as to minimize the tree distance.
This algorithm was evaluated on multiple versions of the ACE corpus and the
MUC-6 dataset and achieved significant improvements in accuracy.

The H and K model (Haghighi and Klein, 2009) motivated the use of “successive
approximations” or multiple hierarchical sieves for CR. The current version of
Stanford CoreNLP deterministic CR system is a product of extensive
investigations conducted on deciding the precise rules to govern the task of
CR. This system was an outcome of three widely acclaimed papers (Raghunathan
et al, 2010; Lee et al, 2011, 2013). Though rule-based systems have lost their
popularity in favor of deep learning algorithms, it is very interesting to
understand how this multi-sieve based approach for CR improved over time. The
work of (Raghunathan et al, 2010) was motivated by the hypothesis that a
single function over a set of constraints or features did not suffice for CR
as lower precision features could often overwhelm higher precision features.
This multi-sieve approach proposed a CR architecture based on a sieve that
applied tiers of deterministic rules ordered from high precision to lowest
precision one be one. Each sieve built on the result of the previous cluster
output. The sieve architecture guaranteed that the important constraints were
given higher precedence. This algorithm had two phases. The first one was the
mention processing phase wherein the mentions were extracted, sorted and
pruned by application of myriad constraints. The second phase was the multi-
pass sieve phase which used multiple passes like string match, head match,
precise constraints like appositives, shared features like gender, animacy,
number, etc. This system was evaluated on the same datasets as the H and K
model (Haghighi and Klein, 2009) and outperformed most of the baselines.

An extension of the multi-sieve approach (Raghunathan et al, 2010) was
presented at the CoNLL 2011 shared task (Pradhan et al, 2011). The major
modifications made to the earlier system were addition of five more sieves, a
mention detection module at the beginning and, finally, a post-processing
module at the end to provide the result in OntoNotes format. This system was
ranked first in both the open and closed tracks of the task. A more detailed
report and more extensive evaluation of this system was also reported by Lee
et al. (Lee et al, 2013), who delineated the precise sieves applied using an
easy to understand and intuitive example. Like the earlier system (Raghunathan
et al, 2010) this approach also incorporated shared global entity-level
information like gender, number and animacy into the system to aid CR. The
figure below shows the composition of different sieves used in this
deterministic system.

Figure 3:  Coreference Resolution Sieve (Lee et al, 2013)

The shifting trend of CR research from rule-based systems to deep learning
systems has come at the cost of loss of the ability of the CR systems to adapt
to different coreference phenomenon and border definitions, when there is no
access to large training data in the desired target scheme (Zeldes and Zhang,
2016). A recent rule-based algorithm (Zeldes and Zhang, 2016) also used
dependency syntax as input. It aimed at targeting the coreference types which
were not annotated by the CoNLL 2012 shared task like cataphora, compound
modifier, i-within-i, etc. This system was called Xrenner and was evaluated on
two very different corpora, i.e., the GUM corpus and the WSJ. It used semantic
and syntactic constraints and rules for antecedent filtering. Xrenner was
compared with other well-known rule-based systems like Stanford CoreNLP (Lee
et al, 2013) and Berkeley systems (Durrett and Klein, 2013) on the datasets
mentioned earlier and outperformed all of them. Xrenner raised a very
important question of the domain-adaptation problem of learning-based systems.

Hobbs algorithm (Hobbs, 1978) was a syntax-based algorithm while centering
theory (Grosz et al, 1995) was discourse-based algorithm. Lappin and Leass
(Lappin and Leass, 1994) algorithm, on the other hand, can be seen as a hybrid
since it was both syntax- and discourse-based. In addition, it also made use
of knowledge resources and morphological and semantic information to rank the
possible antecedents. These three algorithms were amongst the earliest
algorithms for AR and, hence, the evaluation metrics and datasets used for
their evaluation were not the standardized ones. This makes comparison of
these algorithms with the recent rule-based algorithms extremely difficult.
Also, the Hobb’s algorithm (Hobbs, 1978) was hand evaluated and, hence, was
prone to human errors. The datasets used for evaluation of this algorithm also
raise a concern. As pointed out by contemporaries, in most cases the
resolution of the antecedent was trivial. Another issue with the algorithm is
that it was based on the assumption that the correct syntax parse of the
sentence always exits. Nonetheless, this algorithm is still highly regarded as
a strong baseline given its simplicity and ease of implementation.

The Lappin and Leass algorithm (Lappin and Leass, 1994) which is still highly
regarded in AR research also had some drawbacks. First is that Lappin and
Leass algorithm was mainly aimed only at pronominal AR which only forms a
small subset of the AR task. Another drawback is that the Lappin and Leass
algorithm is highly knowledge driven. This dependency on knowledge resources
can become very problematic especially when the required knowledge resources
were not accessible. Another loophole of this algorithm is the weight
assignment scheme for the different salience categories. These weights are
decided by extensive corpus experiments. Hence, the fundamental question which
arises here is are these values corpus-dependent. The weight initialization
stage can be very problematic when trying to adapt this algorithms to other
corpora. The Lappin and Leass algorithm (RAP) was compared with the Hobb’s
algorithm for intra-sentential and intra-sentential case on a dataset of
computer manuals. The Hobb’s algorithm outperformed the RAP algorithm for the
inter-sentential case (87% vs 74%) while the RAP algorithm outperformed the
Hobb’s algorithm for the intra sentential case (89% vs 81%). Overall, RAP
algorithm outperformed Hobb’s algorithm by 4%. In spite of Lappin and Leass
algorithm’s success, it is important to bear in mind that this algorithm was
tested on the same genre as its development set, while the genre used by Hobbs
for the development of his own algorithm was very different from the test set.
High Precision systems like CogNIAC (Baldwin, 1997) aimed at circumscribing
the heavy dependency of the RAP algorithm on external knowledge resources by
taking a knowledge-minimalistic approach. CogNIAC achieved performance at-par
with Hobb’s algorithm in the “resolve-all” setting. In spite of this CogNIAC
had issues of its own. Its rules were defined only for specific reference
types and it was mainly useful for systems which required high precision
resolution at the cost of a low recall. As a result of this, the defined rules
performed well on the narratives dataset but CogNIAC failed to meet a high
precision when evaluated on the MUC-6 corpus.

The centering theory (Grosz et al, 1995; Walker et al, 1998) was a discourse-
based algorithm that took a psycholinguistic approach to AR. Centering theory
was an attractive algorithm for researchers mainly because the discourse
information it requires could be obtained from structural properties of
utterances alone. Thus, eliminating the need for any extra-linguistic semantic
information. One possible disadvantage of CT was its preference for inter-
sentential references as compared to intra-sentential references. In some ways
we can even consider that Lappin and Leass algorithm incorporated centering
theory’s discourse constraint and modified it by assigning weights to these
discourse phenomenon. A manual comparison of Hobb’s algorithm (Hobbs, 1978)
and CT-based algorithm by (Walker, 1989) showed that the two performed equally
over a fictional dataset of 100 utterances, but the Hobb’s algorithm
outperformed CT for news paper articles domain (89% vs 79%) and task domain
(51% vs 49%). In spite of this spurge in interest in this field with the
methods discussed earlier, it is important to note one important thing. The
evaluation standards of these algorithms were very inconsistent (Mitkov,
2001b) and this slowly started to change with the evaluation guidelines laid
by the MUC (Grishman and Sundheim, 1996), ACE (Doddington et al, 2004) and
CoNLL (Pradhan et al, 2011) corpora.

Another widely accepted and extensively evaluated rule-based system was the
coreference system by Haghini and Klein (Haghighi and Klein, 2009). This
system was evaluated on multiple standard datasets like the MUC and ACE
corpora. This simple but effective algorithm was purely based on syntax and
had well-defined antecedent pruning rules. Instead of weighting the salience
categories like Lappin and Leass, this algorithm defined rules which were
successively applied starting with the most important ones. This algorithm
formed the first effective baseline comparison of rule-based CR approaches.
Its main strength was its simplicity and effectiveness. The idea of defining
rules was further developed and delineated more intuitively using a novel
sieve architecture for CR (Raghunathan et al, 2010). Overtime there were a
couple of additions and modifications made to this architecture to improve its
performance (Lee et al, 2013), result of which is the current version of the
best performing rule-based system of Stanford CoreNLP. This coreference system
is extremely modular and new coreference models can be easily incorporated
into it. Overall, we observe that the rules and constraints deployed became
even more fine-grained as the CR research took pace. This was mainly because
the focus of the task started to shift towards CR which has a much broader
scope than AR. [htbp] Rule-based entity resolution algorithm

Algorithm | Dataset | Evaluation Metric | Metric Value | Algorithm Rule Types
---|---|---|---|---
(Hobbs, 1978) |  | Fictional, Non-fictional,
---
Books, Magazines, Part of
Brown Corpus
Hobb’s metric* |  | 88.3% (without selectional constraints)
---
91.7% (with selectional constraints)
| Syntax-based rules+
---
Selectional rules
| (Lappin and Leass, 1994)
---
| Five Computer
---
Science Manuals
Hobb’s metric |  | 74% (inter-sentential)
---
89% (intra-sentential)
| Hybrid of: Syntax Rules+
---
Discourse Rules +Morphological+
Semantic
(Walker et al, 1998) |  | 2 of the fiction and
---
non fiction books
same as Hobb’s+ 5
Human-keyword and task-oriented
and task oriented databased
Hobb’s metric | Overall: 77.6% |  | Discourse-based rules
---
and constraints
(Baldwin, 1997) | Narratives |  Precision and Recall | P:92% R:64% | Discourse rules+Syntax rules
MUC-6 | P:73% R:75%
(Liang and Wu, 2004) |  | Random Texts from
---
Brown Corpora
Hoobs’s metric | Overall:77% |  | Semantic constraints+Discourse
---
constraints+ Syntactic Constraints
(Haghighi and Klein, 2009) | ACE 2004 Roth-dev |  MUC,$B^{3}$, CEAF (F1 values) |  MUC:75.9, $B^{3}$:77.9,CEAF:72.5 |  Syntactic rules+ Semantic rules
ACE 2004 Culotta-test |  MUC:79.6,$B^{3}$:79,CEAF:73.3
MUC-6 Test |  MUC:81.9, $B^{3}$:75.0,CEAF:72
ACE 2004 nwire |  MUC:76.5, $B^{3}$:76.9, CEAF:71.5
(Raghunathan et al, 2010) | ACE 2004 Roth-dev | MUC, $B^{3}$ |  MUC: 78.6, $B^{3}$:80.5 |  Syntactic rules+ Semantic rules(minimal)
ACE 2004 Culotta-test |  MUC:75.8, $B^{3}$:80.4
MUC-6 Test |  MUC:77.7, $B^{3}$:73.2
ACE 2004 nwire |  MUC:78.1, $B^{3}$:78.9
(Lee et al, 2013) | ACE 2004 Culotta-test | MUC, $B^{3}$ |  MUC:75.9, $B^{3}$:81 | Syntactic rules+Semantic rules
ACE 2004 nwire |  MUC:79.6, $B^{3}$:80.2
MUC6-Test |  MUC:78.4, $B^{3}$:74.4
CoNLL 2012 |  MUC, $B^{3}$, CEAF, CoNLL |  |  MUC:63.72, $B^{3}$:52.08,
---
CEAF:47.79, CoNLL:60.13
(Zeldes and Zhang, 2016) | GUM corpus | MUC, $B^{3}$, CEAF, CoNLL |  |  MUC:55.95, $B^{3}$:49.09,
---
CEAFe: 44.47, CoNLL:49.84
Syntactic Rules
Wall Street Journal Corpus |  |  MUC:49.23, $B^{3}$:41.52,
---
CEAFe:41.13, CoNLL: 43.96

  * *

$\text{Hobbs metric}=\frac{\text{Number of correct resolutions}}{\text{Total
No. of Resolutions attempted}}$

###  8.2 Statistical and machine learning based entity resolution

The field of entity resolution underwent a shift during the late nineties from
heuristic- and rule-based approaches to learning-based approaches. Some of the
early learning-based and probabilistic approaches for AR used decision trees
(Aone and Bennett, 1995), genetic algorithms (Mitkov et al, 2002; Mitkov,
2001b) and Bayesian rule (Ge et al, 1998). These approaches set the foundation
for the learning-based approaches for entity resolution which improved
successively over time and, finally, outperformed the rule-based algorithms.
This shift was mainly because of the availability of tagged coreference
corpora like the MUC and ACE corpora. The research community of CR expanded
from linguists to machine learning enthusiasts. Learning-based coreference
models can be classified into three broad categories of mention-pair, entity-
mention and ranking model.

The mention-pair model treated coreference as a collection of pairwise links.
It used a classifier to make a decision whether two NPs are co-referent. This
stage was followed by the stage of reconciling the links using methods like
greedy partitioning or clustering to create an NP partition. This idea was
first proposed for pronoun resolution (Aone and Bennett, 1995; McCarthy and
Lehnert, 1995) in the early nineties using the decision tree classifier
(Quinlan, 1986) and is still regarded as a simple but very effective model.
The mention pair model had three main phases each of which acquired
significant research attention. It is important to note here that every phase
of the mention-pair model was independent and improvement in the performance
of one stage did not necessarily imply improvement in accuracy of the
subsequent phases.

The first phase of the mention-pair model was the creation of training
instances. Since most entities in the text were non-coreferent, the aim of
training instance creation was to reduce the skewness involved in the training
samples. The most popular algorithm for mention instance creation was the Soon
et al. ’s heuristic mention creation method (Soon et al, 2001). Soon’s method
created a positive instance between a NP _A1_ and its closest preceding
antecedent _A2_ and a negative instance by pairing _A1_ with each of the NPs
intervening between _A1_ and _A2_. It only considered annotated NPs for
instance creation. A modification on this approach (Ng and Cardie, 2002b)
enforced another constraint that a positive instance between a non-pronominal
instance _A1_ and antecedent _A2_ could only be created if _A2_ was non-
pronominal too. Other modifications on Soon’s instance creation (Yang et al,
2003; Strube et al, 2002) used number, gender agreement, distance features for
pruning of incorrect instances. There have also been some mention creation
systems (Harabagiu et al, 2001; Ng and Cardie, 2002a) which learnt a set of
rules with the aim of excluding the hard training instances whose resolution
was difficult even for a human being.

The second phase of mention-pair models was the training of a classifier.
Decision trees and random forests were widely used as classifiers (Aone and
Bennett, 1995; McCarthy and Lehnert, 1995; Lee et al, 2017a) for CR. In
addition, statistical learners (Berger et al, 1996; Ge et al, 1998), memory
learners like Timbl (Daelemans et al, 2004) and rule-based learners (Cohen and
Singer, 1999) were also widely popular.

The next phase of the mention pair model was the phase of generating an NP
partition. Once the model was trained on an annotated corpus it could be
tested on a test-set to obtain the coreference chains. Multiple clustering
techniques were deployed to tackle this task. Some of the most prominent ones
were best-first clustering (Ng and Cardie, 2002b), closest-first clustering
(Soon et al, 2001), correlational clustering (McCallum and Wellner, 2005),
Bell Tree beam search (Luo, 2005) and graph partitioning algorithms (Nicolae
and Nicolae, 2006; McCallum and Wellner, 2003). In the closest first
clustering (Soon et al, 2001) all possible mentions before the mention under
consideration were processed from right to left, processing the nearest
antecedent first. Whenever the binary classifier returned true the two
references were linked together and the further antecedents were not
processed. Further, the references could be clustered using transitivity
between the mentions. A modification on this approach (Ng and Cardie, 2002b)
linked the current instance instead with the antecedent which is classified as
true and has the maximum likelihood, i.e., the best antecedent. Though this
method had an overhead of processing all possible antecedent before
conclusively deciding on one, the state-of-the-art model (Lee et al, 2017b)
also uses a version of this clustering albeit by restricting the search-space
of the antecedent. Another kind of clustering deployed to generate the NP
partition was the correlational clustering algorithm (McCallum and Wellner,
2005). This algorithm measured the degree of inconsistency incurred by
including a node in a partition and making repairs. This clustering type was
different from the ones discussed earlier as the assignment to the partition
was not only dependent on the distance measure with one node but on a distance
measurement between all the nodes in a partition. For example, this clustering
type avoided assigning the reference _she_ to a cluster containing _Mr.
Clinton_ and _Clinton_. Though the classifier could have predicted that
_Clinton_ is an antecedent of _she_ this link was avoided by using
correlational clustering. Another variant of clustering algorithms used graph-
partitioning. The nodes of the graph represented the mentions and the edge
weights represented the likelihood of assignment of the pairs. Bell trees
(Luo, 2005) were also used for creating an NP partition. In a Bell Tree, the
root node was the initial state of the process which consisted of a partial
entity containing the first mention of the document. The second mention was
added in the next step by either linking to the existing entity or starting a
new entity. The second layer of nodes was created to represent possible
outcomes and subsequent mentions are added to the tree in a similar manner.
The process was mention synchronous and each layer of the tree nodes was
created by adding one mention at a time.

Another direction of research in mention pair models attempted at combining
the phases of classification and effective partitioning using Integer Linear
Programming (Denis and Baldridge, 2007; Finkel and Manning, 2008). As posited
by Finkel and Manning (Finkel and Manning, 2008) this task was suitable for
integer linear programming (ILP) as CR required to take into consideration the
likelihood of two mentions being coreferent during two phases: pair-wise
classification and final cluster assignment phase. The ILP models first
trained a classifier over pairs of mentions and encode constraints on top of
probability outputs from pairwise classifiers to extract the most probable
legal entity assignments. The difference between two ILP models mentioned
earlier was that the former does not enforce transitivity while the latter
encodes the transitivity constraint while making decisions. However, the ILP
systems had a disadvantage that ILP is an NP-hard problem and this could
create issues when the length of the document decreased. Another recently
proposed model which eliminated the classification phase entirely was the
algorithm by Fernandes et al. (Fernandes et al, 2012). Their model had only
two phases of mention detection and clustering. The training instances were a
set of mentions _x_ in the document and the correct co-referent cluster _y_.
The training objective was a function of the cluster features (lexical,
semantic, syntactic, etc.). This algorithm achieved an official CoNLL score of
58.69 and was one of the best performing systems in closed track of CoNLL 2012
shared-task.

Table 4: Mention pair variants

Algorithm | NP Partitioning Algorithm | Learning Algorithm | Dataset | Performance metrics
---|---|---|---|---
Accuracy | MUC | $B^{3}$
(McCarthy and Lehnert, 1995) |  Used Symmetricity and Transitivity to link mentions | Decision Tree C4.5 |  | English
---
Joint Venture
Articles
86.5 | - | -
MUC-6 | - | 47.2 | -
(Soon et al, 2001) | Closest first clustering | Decision Tree C5 | MUC-6 | - | 62.6 | -
MUC-7 | - | 60.4 | -
(Ng and Cardie, 2002b) | Best first clustering | RIPPER | MUC-6 | - | 70.4 | -
Decision Tree | MUC-7 | - | 63.4 | -
(Bengtson and Roth, 2008) | Best first clustering |  | Averaged Perceptron
---
Algorithm
| ACE-Culotta
---
test
- | 75.8 | 80.8
(Denis and Baldridge, 2007) |  Global inference with Integer Linear Programming |  Maximum Entropy Model | ACE-BNEWS | - | 69.2 | -
ACE-NPAPER | - | 72.5 | -
ACE-NWIRE | - | 67.5 | -
(Finkel and Manning, 2008) | Logistic Classifier | MUC-6 | - | 68.3 | 64.3
ACE-NWIRE | - | 61.1 | 73.1
ACE-BNEWS | - | 67.1 | 74.5
| (McCallum and Wellner, 2005)
---
Graph Partitioning Algorithm |  | Conditional Random
---
Fields over hidden Markov
models
MUC-6 | - | 73.42 | -
(Nicolae and Nicolae, 2006) | Graph Partitioning |  | Maximum Entropy
---
Model
MUC-6 | - | 89.63 | -
| (McCallum and Wellner, 2003)
---
Correlational Clustering |  | Conditional Random
---
Fields over hidden
markov models
MUC-6 | - | 91.59 | -

In spite of being a widely used model even today for CR, there were some
fundamental deficits with the mention-pair model. The first one was the
constraint of transitivity which was enforced did not always hold good. This
meant that if an entity _A_ referred to entity _B_ and entity _B_ referred to
entity _C_ it was not always true that _A_ co-referred with _C_ , e.g.,
consider the case when _she_ is predicted antecedent of _Obama_ and _Obama_ is
predicted antecedent of _he_ , but since _he_ is not co-referent with _she_ by
violation of gender constraint, transitivity condition should not be enforced
here. This flaw was mainly because the decisions made earlier by the co-
reference classifier were not exploited to correct future decisions. The
information from only two NP’s here _Obama_ and _he_ did not suffice to make
an informed decision that they are co-referent, as the pronoun here was
semantically empty. In addition, the NP _Obama_ was itself ambiguous and could
not be assigned any semantic feature like gender. Another disadvantage of the
mention-pair model was that it only determined how good an antecedent was with
respect to the anaphoric NP and not how good it was with respect to other
antecedents available. The entity-mention models and the mention-ranking
models were proposed with the aim of overcoming the disadvantages of the
mention-pair models.

The entity mention model for CR focuses on a single underlying entity of each
referent in discourse. This genre of algorithms was motivated by the fact that
instead of making coreference decisions independently for every mention-
antecedent pair it was necessary to exploit the past coreference decisions to
inform the future ones. The entity mention model aimed at tackling this
“expresiveness” issue (Ng, 2010) with the mention-pair model by attempting to
classify whether an NP was coreferent with a preceding partially formed
cluster instead of an antecedent. Thus, the training instances for the
classifier were modified to a pair of NP _N_ and cluster _C_ and a label
depicting whether the assignment of the NP to the partial cluster was positive
or negative. Instances were represented as cluster-level features instead of
pair wise features. The cluster-level features, e.g., gender, number, etc.
were defined over subsets of clusters using the “ANY”, “ALL”, “MOST”, etc.
predicates. Entity mention model was evaluated by many researchers (Yang et
al, 2004; Luo, 2005). The former evaluated the entity-mention model in
comparison to mention pair model on the ACE datasets using the decision tree
classifier and inductive logic programming. The results for the entity-mention
model as compared to the mention-pair model showed a slight decrease in
performance using C4.5 classifier and a marginal increase in performance using
inductive logic programming. The “ANY” constraint to generate cluster-level
features was also encoded by the Bell Tree algorithm (Luo, 2005). However,
even in this case the performance of the entity mention model was not at par
with the mention-pair model. The major reason for this was that it was
extremely difficult to define cluster-level features for the entity-mention
model. Most of the referents did not contribute anything useful to the cluster
features because they were semantically empty (e.g., pronouns). Another model
which attempted using features defined over clusters for CR was the first
order probabilistic model by (Culotta et al, 2007). Most recent models (Clark
and Manning, 2015, 2016b) also attempt at learning cluster-level features.

Mention-pair models faced an issue that they used a binary classifier to
decide whether an antecedent was coreferent with the mention. The binary
classifier could only provide a “YES” or “NO” result and failed to provide an
intuition on how good one antecedent was compared to the other antecedent. The
ranking models circumvented this flaw by ranking the mentions and choosing the
best candidate antecedent. Ranking was considered to be a more natural way to
predict the coreference links as it captured the competition between different
antecedents. Some proposed models to realize this purpose were the tournament
models and the twin candidate model by (Yang et al, 2008). On a closer
observation, the earlier rule-based approaches (Hobbs, 1978; Lappin and Leass,
1994) also used constraints or sieves in a hierarchical manner starting with
the most crucial ones to converge to the best antecedent. Hence, they too in
principle ranked the antecedents using constraints which were ordered by their
importance. A particularly prominent work which incorporated mention-ranking
was the algorithm by Dennis and Baldridge (Denis and Baldridge, 2008) who
replaced the classification function by a ranking loss. Another mention
ranking model which used only surface features (Durrett and Klein, 2013) and
deployed a log-linear model for antecedent selection, outperformed the
Stanford system (Lee et al, 2011) which was the winner of CoNLL 2011 shared
task (Pradhan et al, 2011) by a margin of 3.5% and the IMS system (Björkelund
and Farkas, 2012) which was the then best model for CR by a margin of 1.9%.

In spite of its wide spread popularity, the mention rankers were still not
able to effectively exploit past decisions to make current decisions. This
motivated the “cluster ranking” algorithms. The cluster ranking approaches
aimed at combining the best of the entity-mention models and the ranking
models. Recent deep learning models (Clark and Manning, 2016b) have also used
a combination of mention ranker and cluster ranker for CR. Another issue with
the mention-ranking model was that it did not differentiate between anaphoric
and non-anaphoric NP’s. The recent deep learning based mention ranking models
(Clark and Manning, 2016a, b; Wiseman et al, 2015, 2016) overcome this flaw by
learning anaphoricity jointly with mention ranking. One of the earlier machine
learning approaches which aimed at achieving this was the work of (Rahman and
Ng, 2009).

Until recently, the best performing model on the CoNLL 2012 shared task was an
entity centric model (Clark and Manning, 2015). Like other machine learning
approaches, it also was feature rich. Defining features for mentions and
especially for clusters is a very challenging task. Also, the extraction of
the features is a time consuming task. This slowly started to change with the
introduction of deep learning for NLP.

###  8.3 Deep learning models for CR

Since its inception, the aim of entity resolution research has been to reduce
the dependency on hand-crafted features. With the introduction of deep
learning in NLP, words could be represented as vectors conveying semantic
dependencies (Mikolov et al, 2013; Pennington et al, 2014). This gave an
impetus to approaches which deployed deep learning for entity resolution
(Wiseman et al, 2015, 2016; Clark and Manning, 2016a, b; Lee et al, 2017b).

The first non-linear mention ranking model (Wiseman et al, 2015) for CR aimed
at learning different feature representations for anaphoricity detection and
antecedent ranking by pre-training on these two individual subtasks. This
approach addressed two major issues in entity resolution: the first being the
identification of non-anaphoric references which are abound in text and the
second was the complicated feature conjunction in linear models which was
necessary because of the inability of simpler features to make a clear
distinction between truly co-referent and non-coreferent mentions. This model
handled the above issues by introducing a new neural network model which took
only raw un-conjoined features as inputs and attempted to learn intermediate
representations.

The algorithm started with liberal mention extraction using the Berkeley
Coreference resolution system (Durrett and Klein, 2013) and sought to capture
relevant aspects of the task better using representation learning. The authors
proposed an extension to the original mention-ranking model using a neural
network model, for which the scoring function is defined as:

$s(x,y)\triangleq\begin{cases}u^{T}g\Bigg{(}\begin{bmatrix}h_{a}(x)\\\
h_{p}(x,y)\\\ \end{bmatrix}\Bigg{)}+u_{0}&\text{if $y\neq\epsilon$}\\\
v^{T}h_{a}(x)+v_{0}&\text{if $y=\epsilon$}\\\ \end{cases}$ (23)
$h_{a}(x)\triangleq tanh(W_{a}\theta_{a}(x)+b_{a})$ (24) $h_{p}(x,y)\triangleq
tanh(W_{p}\theta_{p}(x,y)+b_{p})$ (25)

Hence, $h_{a}$ and $h_{p}$ represented the feature representations which were
defined as non-linear functions on mention and mention-pair features
$\theta_{a}$ and $\theta_{b}$, respectively, and the function g’s two settings
were a linear function $g_{1}$ or a non-linear (tanh) function $g_{2}$, on the
representations. The only raw features defined were $\theta_{a}$ and
$\theta_{p}$. According to the model, $C^{\prime}(x)$ corresponded to the
cluster the mention belongs to or $\epsilon$ if the mention was non-anaphoric.
$y_{n}^{l}$ corresponded to the highest scoring antecedent in cluster
$C^{\prime}(x)$ and was ${\epsilon}$ if x was non-anaphoric The neural network
was trained to minimize the slack rescaled latent-variable loss which the
authors’ define as:

$L(\theta)=\sum_{n=1}^{N}max_{\hat{y}\in\mathcal{Y}(x_{n})}\Delta(x_{n},\hat{y})(1+s(x_{n},\hat{y})-s(x_{n},y_{n}^{l}))$
(26)

$\Delta$ was defined as a mistake specific cost function. The full set of
parameters to be optimized was $W$,$u$,$v$,$W_{a}$,$W_{p}$,$b_{a}$,$b_{p}$.
$\Delta$ could take on different values based on the type of errors possible
in a CR task (Durrett and Klein, 2013), i.e., false link(FL), false new(FN)
and wrong link(WL), error types.

The subtask of anaphoricity detection aimed at identifying the anaphors
amongst the extracted mentions. Generally the extracted mentions were non-
anaphoric, thus this subtask served as an important step to filter out the
mentions which needed further processing for antecedent ranking. The pre-
trained parameters from this task were used for initializing weights of the
antecedent ranking task. The antecedent ranking task was undertaken after
filtering the non anaphoric mentions from the antecedent discovery process.
The scoring procedure followed was similar to one discussed earlier.

The model was trained on two sets of BASIC (Durrett and Klein, 2013) and
modified BASIC$+$ raw features. The baseline model used for anaphoricity
prediction was an L1-regularized SVM using raw and conjoined features. The
baseline model used for subtask two was the neural network based non-linear
mention ranking model using the margin-based loss. The proposed neural network
based model outperformed the two baseline models for both of the subtasks. The
full model (g1 and g2) also achieved the best $F_{1}$ score with improvement
of 1.5 points over the best reported models and 2 over the best mention
ranking system(BCS). It outperformed all the state-of-the-art models (as of
2014) (Durrett and Klein, 2013; Björkelund and Farkas, 2012).

The first non-linear coreference model which proved that coreference task
could benefit from modeling global features about entity clusters (Wiseman et
al, 2016) augmented the neural network based mention-ranking model (Wiseman et
al, 2015) by incorporating entity-level information produced by a recurrent
neural network (RNN) running over the candidate antecedent-cluster. This model
modified the scoring function of the antecedent ranking model by adding a
global scoring term to it. The global score aimed to capture how compatible
the current mention was with the partially formed cluster of the antecedent.
The clusters were represented using separate weight sharing RNNs which
sequentially consumed the mentions being assigned to each cluster. The idea
was to capture the history of previous decisions along with the mention-
antecedent compatibility. The Clark and Manning algorithm which was proposed
roughly during the same time (Clark and Manning, 2016b) instead defined a
significantly different cluster ranking model to induce global information.

This approach was based on the idea of incorporation of entity-level
information, i.e., features defined over clusters of mention pairs. The
architecture of this neural network consisted of mainly four sub-parts which
were – the mention-pair encoder which passes features (described later)
through a feed-forward neural network (FFNN) to produce distributed
representations of mentions, a cluster-pair encoder which uses pooling over
mention pairs to produce distributed representations of cluster pairs, a
mention ranking model to mainly pre-train weights and obtain scores to be used
further in cluster ranking and the cluster ranking module to score pairs of
clusters by passing their representations through a single-layer neural
network.

Figure 4: The Mention-pair and the Cluster-pair encoder (Clark and Manning,
2016b)

The features used for the entire model were: the average of the embeddings of
words in each mention, binned distance between the mentions, head word
embedding, dependency parent, first word’s, last word’s and two preceding
word’s embedding and average of 5 preceding and succeeding words of the
mention, the type of mention, position of mention, sub-mention, mention-
length, document genre, string match, etc. These features were concatenated
into an input vector and fed into a FFNN consisting of three fully-connected
hidden rectified linear layers. The output of the last layer was the vector
representation of the mention pair. The cluster pair encoder, given the two
clusters of mentions $c_{i}$ =$m^{i}_{1}$, $m^{i}_{2}$, …, $m^{i}_{|ci|}$ and
$c_{j}$ = $m^{j}_{1}$,$m^{j}_{2}$, …, $m^{j}_{|cj|}$, produces a distributed
representation $r_{c}$($c_{i}$, $c_{j}$)$\in$ $R^{2d}$. This matrix was
constructed by using max and average pooling over the mention-pair
representations. Next, a mention-pair model was trained on the representations
produced by the mention pair encoder which servers the purpose of pre-training
weights for the cluster ranking task and to provide a measure for coreference
decisions. This mention ranking model was trained on the slack rescaled
objective (Wiseman et al, 2015) discussed earlier. The final stage was cluster
ranking which used the pre-trained weights of the mention ranking model to
obtain a score by feeding the cluster representations of the cluster encoder
to a single-layered fully-connected neural network. The two available actions
based on scores were merge (combine two clusters) and pass (no action). During
inference, the highest-scoring (most probable) action was taken at each step.
This ensemble of cluster ranking beat the earlier state-of-the-art approaches
achieving an F1 score of 65.39 on the CoNLL English task and 63.66 on the
Chinese task.

Another algorithm which complemented the earlier work (Clark and Manning,
2016a) attempted at effectively replacing the heuristic loss functions which
complicated training, with the reinforce policy gradient algorithm and reward-
rescale max-margin objective. This approach exploited the immense importance
of independent actions in mention ranking models. The independence of actions
implied that the effect of each action on the final result was different thus
making this scenario a suitable candidate for reinforcement learning. This
model used neural mention ranking model (Clark and Manning, 2016b) described
earlier as the baseline and replaced the heuristic loss with reinforcement
learning based loss functions. Reinforcement learning was utilized here to
provide a feedback on different set of actions and linkages performed by the
mention ranking models. Thus, the model could optimize its actions in such a
way that the actions were performed to maximize the reward (called the reward
rescaling algorithm). The reward rescaling algorithm achieves an average
$F_{1}$ score of 65.73 and 63.4 on the $CEAF_{\theta 4}$ and $B^{3}$ metric
respectively on the CoNLL 2012 English Test Data, thus beating the earlier
systems. This algorithm was novel because it avoided making costly mistakes in
antecedent resolution which could penalized the recall value. On the other
hand, unimportant mistakes are not penalized as heavily. The approach is novel
with regards to it being the first one to apply reinforcement learning to CR.
The most challenging task in this algorithm was the assignment of reward costs
which could be corpus specific.

The state-of-the-art model is an end-to-end CR system which outperformed the
previous approaches in spite of being dependent on minimal features. This end-
to-end neural model (Lee et al, 2017b) is jointly modeled mention detection
and CR. This model began with the construction of high-dimensional word
embeddings to represent the words of an annotated documents. The word
embeddings used were a concatenation of Glove, Turian and character
embeddings. The character embeddings were learnt using a character-level
convolutional neural network (CNN) of three different window sizes. The
vectorized sentences of the document were fed into a bidirectional long short-
term memory (LSTM) network to learn effective word representations. Next, all
the possible mentions in a document were extracted and represented as a one
dimensional vector. This mention representation was a conjugation of the start
word embedding, head word embedding, end word embedding and some other
mention-level features. The head word embedding was learnt using attention
mechanism over the entire mention span. The mention representation $g_{i}$ was
defined as:

$g_{i}=[x^{*}_{START(i)},x^{*}_{END(i)},x^{\prime}_{i},\phi(i)]$ (27)

where $x^{\prime}_{i}$ represented an attention-weighted sum of the word
vectors in span i and $x^{*}_{START(i)}$ and $x^{*}_{END(i)}$ are the span
boundaries. The approach pruned candidates greedily for training and
evaluation and considered only spans of maximum width ten. The mentions were
scored using a FFNN and only a fraction of the top scoring spans were
preserved further for CR.

Figure 5: Bi-LSTM to encode sentences and Mention scoring (Lee et al, 2017b)

These top scoring mentions served as input to the CR model. The preceding 250
mentions were considered as the candidate antecedents. The scores of the
mention-antecedent pairs were computed using the equation below. The mention-
antecedent pair representation was a concatenation of individual mention
representations $g_{i}$ and $g_{j}$, the similarity between the two mentions
$g_{i}\circ g_{j}$ and pairwise features $\phi(i,j)$ representing speaker and
distance features. The final scoring function optimized is a sum of the of the
two individual mention scores of the candidate mentions and the mention-
antecedent pair score represented by the equation below.

$s_{a}(i,j)=w_{a}\cdot FFNN_{a}([g_{i},g_{j},g_{i}\circ g_{j},\phi(i,j)])$
(28)

Figure 6: Antecedent Scoring (Lee et al, 2017b)

The optimization function used for the model was the marginal log-likelihood
of all correct antecedents on basis of the gold-clustering.

$\log\prod_{i=1}^{N}\sum\limits_{y^{\prime}\in\mathcal{Y}\hat{i}GOLD(i)}P(y^{\prime})$
(29)

During inference the best scoring antecedent was chosen as the most probable
antecedent and coreference chains were formed using the property of
transitivity.

The authors report the ensembling experiments using five models with different
initializations and prune the spans here using average of the mention scores
over each model. The proposed approach was extensively evaluated for
precision, recall and F1 on the MUC,$B^{3}$ and CEAF metrics. The authors also
provide a quantitative and qualitative analysis of the model for better
interpretability.

Challenging aspect of this model was that its high computational time and
large number of trainable parameters. This model used a very large deep neural
network and, hence, is very difficult to maintain. This creates a challenge
for deploying this system as an easy to use off-the-shelf system.

Table 5: Deep learning based entity resolution

Algorithm |  | Neural Network
---
architecture(s) used
| Pre-trained Word Embeddings
---
Used
| Cluster-level features
---
used (Y/N)
| Loss function used for Mention
---
Ranking
| External Tools
---
Used
(Wiseman et al, 2015) | FFNN | - | No |  | Heuristic Regularized Slack
---
rescaled latent variable
Loss
| Berkeley Coreference System
---
for mention extraction and
Stanford Coref System’s
Rules for animacy feature
(Wiseman et al, 2016) | FFNN and RNN | - | Yes |  | Heuristic Slack Rescaled
---
Margin objective
| Berkeley Coreference System
---
for mention extraction
and Stanford deterministic
system animacy rules
(Clark and Manning, 2016b) | FFNN |  | English:50d word2vec
---
Chinese:Polyglot 64d
Yes |  | Heuristic Slack Rescaled
---
Max-margin objective
| Stanford Deterministic Coref
---
System rules to extract
mentions
(Clark and Manning, 2016a) | FFNN |  | English:50d word2vec
---
Chinese:Polyglot 64d
Yes |  | Heuristic Max-margin objective,
---
REINFORCE policy gradient,
Reward Rescaling Algorithm
| Stanford Deterministic Coref
---
System rules to extract
mentions
(Lee et al, 2017b) |  | FFNN+Bi-LSTM+
---
CNN+Neural Attention
Glove300d+turian 50d | No | Marginal Log-likelihood | -

Deep learning CR systems (Clark and Manning, 2016a, b; Lee et al, 2017b)
represent words using vectors which are known depict semantic relationships
between words (Mikolov et al, 2013; Pennington et al, 2014). These models,
hence, use less features than the machine learning models. These systems also
implicitly capture the dependencies between mentions particularly using RNN
and its adaptations like LSTMs and gated recurrent units (GRUs). One
disadvantage of these systems is that they are difficult to maintain and often
require some amount of genre or domain specific adaptation before use. Amongst
the deep learning based CR algorithms discussed earlier we observe that the
dependency on features decreased over time. This was mainly because of the
pre-trained word embeddings which captured some amount of semantic similarity
between the words. Unlike the Stanford deep coref system (Clark and Manning,
2016b, a), the state-of-the-art system used minimal mention-level and mention-
antecedent pair features. This system also did not use any external mention-
extractor and proceeds by extracting all possible spans up to a fixed width,
greedily. Another advantage of this system was that it did not use any
heuristic loss function unlike the other deep learning models (Wiseman et al,
2015, 2016; Clark and Manning, 2016b, a) and still managed to beat the earlier
models with a very simple log-likelihood loss function. The previous models
used heuristic loss functions which were dependent on a mistake specific cost
function whose values were set after exhaustive experiments. Though this
system is difficult to maintain mainly because of its high-dimensionality, it
is a strong evidence of the effectiveness of LSTMs and their ability to
capture long term dependencies. Another possible disadvantage of this model is
that it is still basically a mention ranking model and chooses the highest
scoring antecedent without using any cluster-level information. As posited by
many earlier deep learning works which used cluster-level information (Clark
and Manning, 2016b; Wiseman et al, 2016) this information is necessary to
avoid linking of incompatible mentions to partially formed coreference chains.
In spite of some of the disadvantages of the deep CR systems, future strides
in CR can only be achieved by either defining better features to be learnt or
by introducing better deep learning architectures for CR.

##  9 An analysis of entity resolution research progress on different datasets

In previous sections, we have discussed several types of entity resolution
algorithms. In this section, we aim at providing an overview of the research
progress made in the field of entity resolution over the past few years. Here,
we will be analyzing the progress made on mainly three important publicly
available datasets: the MUC corpus, the ACE corpora and the CoNLL Shared task
(OntoNotes 5.0).

The MUC datasets were the first annotated corpora to be publicly available for
CR. Though these datasets were small they have been widely used for evaluation
and training. The first system to be evaluated on the MUC dataset was Soon’s
mention-pair model (Soon et al, 2001). This was followed by Ng and Cardie’s
series of improvements on the dataset (Ng and Cardie, 2002b, a). Followed by
these were some mention ranking models have also been attempted on the MUC
datasets one of them was Yang’s twin candidate model (Yang et al, 2008) which
aimed at capturing competition between between the antecedents. Conditional
random fields (CRFs) (McCallum and Wellner, 2005) have also been trained on
this dataset to directly model global coreference chains. In addition, some
other approaches like Integer Linear Programming (Finkel and Manning, 2008)
and non-parametric Bayesian models (Haghighi and Klein, 2007) have also been
attempted. The MUC-6 and 7 datasets in spite of being widely popular were
quite small in size thus making training on a small corpus very hard. This
also meant that some types of references were ignored. The evaluation
standards were also not very well defined, hence making comparison of
different algorithms a challenge. The ACE and CoNLL datasets aimed at
overcoming these disadvantages by providing a much larger training corpus.

When coming to the ACE datasets, we observe a huge disparity in the evaluation
standards, train-test splits and metrics used. This was mainly because the
test sets of the dataset were not publicly released and, hence, were
unavailable to non-participants. This made comparative evaluation with
research methodologies which did not participate in this task difficult. Many
researchers were hence forced to define their own train-test split (Culotta et
al, 2007; Bengtson and Roth, 2008). In addition, the ACE datasets were also
released in iterations and phases from 2002 to 2005, thus algorithms tested on
newer releases could not be directly compared with the earlier approaches.
Multiple algorithms were evaluated on different versions of the ACE datasets
like the mention pair models (Bengtson and Roth, 2008), mention ranking models
(Denis and Baldridge, 2008; Rahman and Ng, 2009) and joint inference models
(Poon and Domingos, 2008; Haghighi and Klein, 2010). Some rule-based
approaches (Lee et al, 2011) were also tested on the ACE datasets mainly with
the aim of comparison with past research methodologies, which were not
evaluated on the newly introduced CoNLL shared task.

The best performing rule-based systems on the current version of the CoNLL
shared task is the multi-sieve based Stanford deterministic system (Lee et al,
2013). Most of the early systems which outperformed the rule-based system were
machine learning based. There have been multiple variants of the mention-pair
models which used structured perceptron models for CR on the CoNLL 2012
dataset (Fernandes et al, 2012; Chang et al, 2013; Durrett and Klein, 2013).
This was followed by a model which jointly modeled Coreference, Named Entity
Recognition and Entity Linking using a structured CRF. Models which used
cluster-level features were very well known in CR by then and some models (Ma
et al, 2014) also used average across all pairs in clusters involved to
incorporate cluster-level features. The entity-centric model (Clark and
Manning, 2015) which achieved a vast margin of improvement on the earlier
systems proposed a novel way of defining cluster-level features. It combined
information from involved mention pairs in variety of ways with higher order
features produced from scores of the mention pair models. As observed from the
table below, since 2015 the best performing systems on CoNLL 2012 datasets
have been deep learning systems. These used neural networks to individually
model different subtasks like antecedent ranking and cluster ranking or to
jointly model mention prediction and CR. Though the most common use of deep
neural networks in CR has been for scoring mention-pairs and clusters, some
methods (Wiseman et al, 2016) also used RNN’s to sequentially store cluster
states, with the aim of modeling cluster-level information. The current best
performing system on the CR task is a very deep end to end system which is an
amalgamation of LSTM, CNN, FFNN and neural attention. Since deep learning
systems are typically hard to maintain some recent systems have also proposed
a hybrid of rule-based and machine learning systems (Lee et al, 2017a). Though
this system does not perform at par with the deep learning system, it is easy
to maintain and use and even outperforms some of the machine learning systems.
Overall, the deep learning trend in CR looks very exciting and future progress
could be expected by incorporating better features and using more
sophisticated neural network architectures. As stated by many (Lee et al,
2017b; Durrett and Klein, 2013), this could be modeled by developing an
intuitive way to incorporate differences between entailment, equivalence and
alteration phenomenon.

As observed from the table below, until about a few years ago we observe that
the CR datasets and mainly the evaluation metrics were not standardized. This
made comparison of algorithms very difficult. The early corpora like MUC and
ACE did not release very strict evaluation guidelines for the task. Also,
there were multiple releases, few of which were publicly available. The test
datasets of the ACE corpora were initially not available to non-participants
which also created issues with the comparison of algorithms. Hence, most
authors often defined train and test splits of their own on the datasets
(Culotta et al, 2007; Bengtson and Roth, 2008). Though future approaches tried
to stick to the earlier train-test splits for comparative evaluation (Haghighi
and Klein, 2009), it was difficult as often the datasets needed for comparison
were not freely available. Another issue was with the very definition of the
Coreference Task. Some approaches (Luo, 2005) which reported highest accuracy
on the ACE and MUC corpus could not be compared with others because they
reported performance on true labelled mentions instead of system predicted
mentions. This was different from other approaches which jointly modeled the
tasks of mention prediction and CR. This, however, changed with the
introduction of CoNLL 2012 shared task (Pradhan et al, 2012) which defined
strict evaluation guidelines for CR. After this, CR research gained momentum
and has seen more consistent progress and clearer evaluation standards.

Table 6: Dataset-wise comparison of baselines

Dataset | Release | Algorithm | Scoring metrics F1 values |  Algorithm Type
---|---|---|---|---
MUC | B-cubed | CEAFe | CoNLL
CoNLL Shared Task (OntoNotes 5.0) | CoNLL 2011 | (Lee et al, 2011) | 61.51 | 63.27 | 45.17 | 56.65 | Rule-based
(Björkelund and Farkas, 2012) | 64.71 | 64.73 | 45.35 | 58.26 | Machine Learning
(Durrett and Klein, 2013) | 66.43 | 66.16 | 47.79 | 60.13
CoNLL 2012 | (Lee et al, 2013) | 63.72 | 52.08 | 48.65 | 54.82 | Rule-based
(Chang et al, 2013) | 69.48 | 57.44 | 53.07 | 60.00 | Probabilistic
(Fernandes et al, 2012) | 70.51 | 57.58 | 53.86 | 60.65 | Machine Learning
(Durrett and Klein, 2013) | 70.51 | 58.33 | 55.36 | 61.40
(Ma et al, 2014) | 72.84 | 57.94 | 53.91 | 61.56
(Björkelund and Farkas, 2012) | 70.72 | 58.58 | 55.61 | 61.63
(Durrett and Klein, 2014) | 71.24 | 58.71 | 55.18 | 61.71
(Clark and Manning, 2015) | 72.59 | 60.44 | 56.02 | 63.02
(Lee et al, 2017a) | 72.37 | 60.46 | 56.76 | 63.20 | Hybrid=ML+Rules
(Wiseman et al, 2015) | 72.6 | 60.52 | 57.05 | 63.39 | Deep Learning
(Wiseman et al, 2016) | 73.42 | 61.50 | 57.7 | 64.21
(Clark and Manning, 2016b) | 74.06 | 62.86 | 58.96 | 65.29
(Clark and Manning, 2016a) | 74.56 | 63.40 | 59.23 | 65.73
(Lee et al, 2017b) | 77.20 | 66.60 | 62.60 | 68.80
Automatic Content Extraction | ACE 2004 Culotta Test | (Stoyanov et al, 2010) | 62.0 | 76.5 | - | - | Machine Learning
| (Haghighi and Klein, 2009)
---
(true)
79.60 | 79.00 | - | - | Rule-based
| (Haghighi and Klein, 2009)
---
(system)
64.4 | 73.2 | - | - | Rule-based
(Haghighi and Klein, 2010) | 67.0 | 77.0 | - | - | Machine Learning
(Culotta et al, 2007) | - | 79.30 | - | - | Probabilistic
(Bengtson and Roth, 2008) | 75.80 | 80.80 | - | - | Machine Learning
(Lee et al, 2013) | 75.90 | 81.00 | - | - | Rule-based
ACE 2004 -training datasets BNEWS,NWIRE | (Haghighi and Klein, 2007) | 62.3,64.2 | - | - | - | Rule-based
(Finkel and Manning, 2008) | 67.1,61.1 | 74.5,73.1 | - | - |  | ML+ Integer Linear
---
Programming
(Poon and Domingos, 2008) | 70.90,67.3 | - | - | - | Machine Learning
| (Haghighi and Klein, 2009)
---
76.50,- | 76.90,- | - | - | Rule-based
(Lee et al, 2013) | 79.60,- | 80.20,- | - | - | Rule-based
ACE -Phase 2 Test sets BNEWS,NWIRE,NPAPER | (Ng, 2005) | 64.9,54.7,69.3 | 65.6,66.4,66.4 | - | - | Machine Learning
(Denis and Baldridge, 2009) | 69.2,67.5,72.5 | - | - | -
- | (Poon and Domingos, 2008) | 67.4,67.4,70.4 | 67.7,71.6,68.2 | - | -
ACE 2005 Stoyanov Test | (Stoyanov et al, 2010) | 67.4 | 73.7 | - | -
(Haghighi and Klein, 2009) | 65.2 | 71.8 | - | - | Rule-based
(Haghighi and Klein, 2010) | 68.1 | 75.1 | - | - | Machine Learning
ACE 2005 Rahman and Ng | (Rahman and Ng, 2009) | 69.3 | 61.4 | - | -
(Haghighi and Klein, 2009) | 67.0 | 60.6 | - | - | Rule-based
(Haghighi and Klein, 2010) | 71.6 | 62.7 | - | - | Machine Learning
Message Understanding Conference | MUC 6 | (Soon et al, 2001) | 62.6 | - | - | - | Machine Learning
(Ng and Cardie, 2002a) | 69.5 | - | - | -
(Ng and Cardie, 2002b) | 70.4 | - | - | -
(Yang et al, 2003) | 71.3 | - |  | -
(McCallum and Wellner, 2005) | 73.4 | - | - | -
(Haghighi and Klein, 2007) | 63.9 | - | - | -
(Finkel and Manning, 2008) | 68.30 | 64.30 | - | - |  | ML+ Integer Linear
---
Programming
(Stoyanov et al, 2010) | 68.5 | 70.88 | - | - | Machine Learning
(Poon and Domingos, 2008) | 79.20 | - | - | -
(Haghighi and Klein, 2009) | 81.90 | 75.0 | - | - | Rule-based
(Lee et al, 2013) | 78.40 | 74.40 | - | -
MUC 7 | (Soon et al, 2001) | 60.4 | - | - | - | Machine Learning
(Ng and Cardie, 2002b) | 63.4 | - | - | -
(Yang et al, 2003) | 60.2 | - | - | -
(Stoyanov et al, 2010) | 62.8 | 65.86 | - | -

##  10 Open source tools

Computer science has now stumbled upon an era wherein sharing research output
is both a demand and necessity. On the one hand, it helps the researchers to
think about possible improvements from peer suggestions and, on the other
hand, it allows researchers mainly interested in its application to pick an
off-the-shelf model. Given the wide range of applications of CR, practical
tools to tackle this issue are a necessity. These tools may deploy a specific
approach like (Mitkov et al, 2002) and or others like Reconcile (Stoyanov et
al, 2010) could be a combination of many research methodologies.

The GuiTAR tool (Poesio and Kabadjov, 2004) aimed at making an open source
tool available for researchers mainly interested in applying AR to NLP
applications like question answering, summarization, sentiment analysis and
information retrieval. This tool has primarily been developed for the tasks of
segmentation and summarization. This is a domain dependent AR tool. Stanford
coref toolkit provides 3 models which were pioneered by the Stanford NLP
group. These three algorithms are Deterministic (Lee et al, 2013; Recasens et
al, 2013; Raghunathan et al, 2010), Statistical (Clark and Manning, 2015) and
Neural (Clark and Manning, 2016a, b). BART (Versley et al, 2008) is one of the
few highly modular toolkit for CR that supports the statistical approaches.
BART is multilingual and is available for German, English and Italian. BART
relies on a maximum entropy model for classification of mention-pairs.
Currently, it supports a novel Semantic Tree based approach (for English). As
mentioned earlier, coreference constraints and coreference types varies from
language to language and BART aims at separation of linguistic and machine
learning aspects of the problem. BART proceeds by converting input document
into a set of linguistic layers represented by separate XML layers. They are
used to extract mentions, assign syntactic properties and define pairwise
features for the mention. A decoder generates training examples through sample
selection and learns pairwise classifier. The encoder generates testing
examples through sample selections and partitions them based on trained
coreference chains. This toolkit aimed at combining the best state-of-the-art
models into a modular toolkit which has been widely used for broader
applications of AR. ARKref (O’Connor and Heilman, 2013) is a tool for NP CR
that is based on system described by Haghighi and Klein (Haghighi and Klein,
2009). ARKref is deterministic, rule-based that uses syntactic information
from a constituency parser, semantic information from an entity recognition
component to constraint the set of possible antecedent candidate that could be
referred by a given mention. It was trained and tested on CoNLL shared task
(Pradhan et al, 2012). The Reconcile System (Stoyanov et al, 2010) solved a
problem of comparison of various CR algorithms. This problem mainly arises due
to high cost of implementing a complete end to end CR system, thus giving way
to inconsistent and often unrealistic evaluation scenarios. Reconcile is an
infrastructure for development of learning based NP CR system Reconcile can be
considered an amalgamation of rapid creation of CR systems, easy
implementation of new feature sets and approaches to CR and empirical
evaluation of CR across a variety of benchmark datasets and scoring metrics.
Reconcile is evaluated on six most commonly used CR datasets (MUC-6, MUC-7
ACE, etc.). Performance is evaluated according to B3 and MUC scoring metrics.
Reconcile aims to address one of the issues in AR (Mitkov, 2001a), which is
the huge disparity in the evaluation standards used. It further makes an
attempts to reduce the labelling standards disparity too.

Table 7: Off-the-shelf entity resolution systems Toolkit | Algorithm |  | Development and
---
Evaluation Corpus
Languages | Type
| GuiTAR
---
(Poesio and Kabadjov, 2004)
| General toolkit which
---
incorporates many
algorithms like
(Mitkov et al, 2002),
(Vieira et al, 2005), etc. and
can be extented to include
other algorithms
GNOME corpus | English |  | Hybrid: Rule-based+
---
Machine Learning
| BART
---
(Versley et al, 2008)
|  Primarily (Soon et al, 2001)
---
and some other
machine learning
approaches to CR
ACE-2 corpora | English | Machine Learning
| PARKref
---
(O’Connor and Heilman, 2013)
| PHaghini and Klein Model
---
(Haghighi and Klein, 2009)
| ACE2004-ROTH-DEV
---
ACE2004-CULOTTA
-TEST
| German,
---
English and
Italian
Rule-based
Reconcile (Stoyanov et al, 2010) |  | Abstracts the basic
---
architecture of most
contemporary
supervised learning-
based coreference
resolution systems
e.g., (Soon et al, 2001),
(Ng and Cardie, 2002b),
(Bengtson and Roth, 2008)
| 2 MUC datasets (MUC-6
---
and MUC-7)
4 ACE datasets
English |  | Supervised Machine
---
Learning Classifiers
| Stanford CoreNLP deterministic,
---
rule-based system
(Lee et al, 2013) |  | CoNLL 2011 (OntoNotes
---
Corpus), ACE2004-
Culotta- Test, ACE
2004-nwire, MUC6-Test
| Chinese
---
English
Rule-based
| Stanford Core NLP Statistical
---
System
(Clark and Manning, 2015) | CoNLL 2012 | English | Statistical
| Stanford CoreNLP Neural
---
Coreference Resolution
(Clark and Manning, 2016b, a) | CoNLL 2012 | English | Deep Neural Network

##  11 Reference Resolution in sentiment analysis

Being one of the core component of NLP, CR has many potential downstream
applications in NLP like machine translation (Hardmeier and Federico, 2010;
Werlen and Popescu-Belis, 2017; Bawden et al, 2017), paraphrase detection
(Recasens and Vila, 2010; Regneri and Wang, 2012), summarization (Bergler et
al, 2003; Witte and Bergler, 2003), question answering (Vicedo and Ferrández,
2000; Weston et al, 2015; Young et al, 2018a), sentiment analysis (Cambria et
al, 2018; Valdivia et al, 2018), etc. The application of most interest to us
is sentiment analysis. Though AR is said to be one of the most commonly faced
challenge in sentiment analysis, we observe that there is scarcity of research
work targeting the question of how could CR be effectively incorporated into a
sentiment analysis system and which issues will it most likely solve. In this
section, we provide a background of the scenarios in sentiment analysis which
necessitate entity resolution. We also discuss some of the prominent
approaches in the intersection of these two fields.

On analyzing the use of AR in sentiment analysis, we come across two main
scenarios where AR can prove beneficial to sentiment analysis. The first place
where this could prove beneficial is for “global entity resolution”. An often
observed phenomenon in reviews which are used for sentiment analysis is that
the reviews are often centered around one particular entity which is trivial.
Hence, most reviewers do not explicitly specify the entity that they are
reviewing. Some others do specify this entity. Thus, this cross-review
information can be exploited effectively to resolve the pronominal references
to the global entity. An example of this taken from the SemEval aspect-based
sentiment analysis dataset is depicted in the figure below. In the example
below, multiple reviews could be used to chain the references to a global
entity (i.e., HP Pavillion Laptop). Global entity resolution can aid the
process of extracting the sentiment associated with the general entity.

Figure 7: Global Entity Resolution (Neural Coref Api)

Another possible use of AR in sentiment analysis is mainly for fine-grained
aspect-based sentiment analysis (Ma et al, 2018). AR can help infer multiple
pronominal references to a particular aspect of the product.This in turn can
help extract the opinion associated with that particular aspect. An example of
this can be seen in the figure below. In the example below, the resolution of
the pronouns to the aspects as depicted by the links between them could aid in
the procedure of extraction of fine grained opinion on the aspect. These two
images were the resolved references returned by the hugging face api  which
deploys the Stanford Deep Coref System (Clark and Manning, 2016a).

Figure 8: Fine-grained aspect resolution (Neural Coref Api)

Now that we have established the importance of AR for sentiment analysis, we
will be providing an overview of the approaches which have worked at the
intersection of these two fields. The importance of AR in sentiment analysis
has been delineated in many significant research works which consider
sentiment analysis as a suitcase research problem (Cambria et al, 2017).

AR and CR enables sentiment analysis to break beyond the sentence-level
opinion mining task. A recent approach which targets this (Le et al, 2016)
addresses the problem of aspect extraction which is a crucial task for aspect-
based sentiment analysis. AR in sentiment analysis aids the task of extracting
aspect-opinion word pair. This approach to aspect extraction proceeds by
construction of sentiment ontology knowledge base. This is followed by
lightweight NLP on the text. There is Ontological resolution engine
constructed which discovers the implied by and mentioned by relations in
aspect-based sentiment ontology. The sentiment rating engine (i.e., assigns
rating (polarity) to the aspect extracted.

Another paper (Nicolov et al, 2008) aimed at investigating whether a
performance boost is obtained on taking coreference information into account
in sentiment analysis. Take, for example, _The canon G3 power shot has
impressed me. This camera combines amazing picture quality with ease of use._
As human annotators it is easy for us to understand that the term camera here
co-refers with canon G3 power shot. However, this task is a major challenge
faced by most algorithms. The sentiment analysis algorithm introduced here is
proximity-based for focused sentiment identification. If first calculates the
anchor-level sentiment by considering sentiment window of 8 tokens before and
after a phrase using distance weighting approach. The anchor weighted scores
are aggregated and sentiment phrases are created. Finally, the co-referring
entities are identified and the algorithm is evaluated over an opinionated
corpus. The percentage improvement obtained over baseline CR modules is on an
average 10% and varies over different datasets used for evaluation.

Another algorithm (Jakob and Gurevych, 2010) aimed at tackling the issue of
extracting opinion targets expressed by anaphoric pronouns. Opinion word and
target pair extraction can benefit from AR to a great extent. The algorithm
presented by (Zhuang et al, 2006) is used as a baseline for the experiment
using opinion target and opinion word extraction. A modified version of
CogNIAC (Baldwin, 1997) is used for CR. The best configuration of this
algorithm reaches approximately 50% of the improvements which are
theoretically possible with perfect AR.

Another recent interesting work (Ding and Liu, 2010) posits that object and
attribute co-reference is important because without solving it a great deal of
opinion information will be lost and opinions may be assigned to wrong
entities. Major loss encountered in case pronouns are not resolved is of
opinion words. The paper elicits the importance of the issue with an example:
_I bought the cannon S500 camera yesterday. It looked beautiful. I took a few
photos last night. They were amazing._ In the example, the last two sentences
express opinions but it is difficult to specify the target at which the
opinion is aimed. Target extraction becomes meaningless if the association
between the target and the opinion word is not captured appropriately or is
obscure due to co-referent phrases. The paper describes two basic entities
object and attribute, e.g., camera (object) and Picture quality (attribute).
The pairwise learning approach followed is supervised model based on (Soon et
al, 2001) CR feature model and the annotation is performed as per the MUC-7
standards. The datasets used are blog conversations on products of myriad
categories like dvd, cars, TV, lcd, etc. The algorithm first pre-processes the
text and then constructs features in a way similar to (Soon et al, 2001) with
addition of some other features like sentiment consistency, comparative
sentences and entity-opinion word pair association. Pre-processing POS, NP
finder. A decision tree is trained on these features and the algorithm is
tested on an un-annotated dataset.

As observed from the research methodologies discussed earlier, the
amalgamation of entity resolution systems into a sentiment analysis systems is
a challenging task. This is further accentuated by the fact that current
entity resolution systems are themselves not perfect and resolving references
before sentiment analysis could in fact prove detrimental to the performance
of sentiment analysis systems if not incorporated correctly. Future research
methodologies in this area should focus on more exhaustive evaluations on
standard sentiment analysis datasets.

##  12 Reference Resolution: Issues and Controversies

In this section, we will be discussing the major issues and controversies