🔗 Coreference resolution
Coreference resolution is the task of finding the expressions in a text that refer to the same entity as one another, such as names, descriptive noun phrases and pronouns. It groups those expressions into clusters, one cluster per entity, so that the document's mentions form a partition. Event coreference and cross-document coreference are related but separate tasks.
What it is
A text keeps returning to the same people, organisations and objects under different surface forms. In "Dell said the company would cut jobs; it expects savings next year", the strings "Dell", "the company" and "it" all point to one firm. Coreference resolution recovers that structure. Its input is a document. Its output is a set of clusters of mentions, where each cluster stands for one discourse entity, that is, something the text introduces and can later refer back to.
Early work often narrowed the problem to pronouns: given a third-person pronoun, choose the noun phrase it refers back to (Lappin & Leass 1994). The broader formulation treats all noun phrases and all entity types in unrestricted text (Soon et al. 2001). The standard task concerns identity relations between noun phrases. Other referential links, such as part–whole or set membership, are usually left out (Ng 2010).
The task naturally splits into two subproblems:
- Mention detection decides which spans are referring expressions. Gold mentions are the spans annotators marked; predicted mentions are the spans a system finds on its own.
- Linking or clustering decides which of those spans belong together.
Errors in the first step limit the second. For one rule-based system on CoNLL-2011 data, supplying gold mentions raised the CoNLL score (defined below) by about 15 points. Gold parse trees and named entities added only about 2 (Lee et al. 2011).
The key idea
Most systems reduce clustering to a sequence of local decisions. Each mention either picks an earlier mention as its antecedent or starts a new entity, and the clusters are then read off the antecedent links. Three model families follow this pattern (Ng 2010):
- Mention-pair classifiers judge two mentions at a time.
- Ranking models compare all candidate antecedents of a mention jointly.
- Entity-level models reason over partially built clusters.
The span-ranking formulation behind most current neural systems scores a candidate span i against each earlier span j (Lee et al. 2017):
s(i, j) = s_m(i) + s_m(j) + s_a(i, j) with s(i, ε) = 0
P(y_i = j) = exp s(i, j) / Σ_{j' ∈ Y(i)} exp s(i, j')
The symbols mean the following:
- i is a span of text, and j is an earlier span proposed as its antecedent.
- s_m(·) is a learned mention score saying how likely a span is to be a referring expression at all.
- s_a(i, j) is a learned antecedent score for the pair.
- ε is a dummy antecedent meaning "no antecedent", which covers new entities and non-referring spans; its score is fixed at zero.
- Y(i) is the set of candidates for span i, namely ε plus all earlier spans.
- P(y_i = j) is the probability that span i links to j.
Because the mention score is separate, unlikely spans can be pruned before the expensive pairwise step. The model keeps 0.4 spans per word and still covers about 92.7% of gold mentions (Lee et al. 2017). Training maximises a marginal log-likelihood: the summed probability of every candidate in the span's gold cluster, or of ε when the span has no gold antecedent (Lee et al. 2017).
Reading links transitively always yields a valid partition, but a cluster can still be incoherent. Each link may look plausible on its own while the whole does not fit together. For example, an ambiguous "you" can join a singular "I" to a plural "all of you" (Lee et al. 2018). Entity-level remedies include:
- a sieve architecture, in which ordered deterministic passes share attributes such as gender and number across a growing cluster (Raghunathan et al. 2010);
- a beam search over the Bell tree (Luo et al. 2004). In this tree, mentions arrive left to right, and each one either attaches to a partial entity built so far or opens a new one. Every leaf is therefore one complete partition;
- learned cluster-pair representations (Clark & Manning 2016);
- iterative refinement of span representations using the expected antecedent (Lee et al. 2018).
History and founding papers
Linguistic interest in anaphora predates computation. Two ideas shaped the early heuristic systems (Ng 2010):
- Hobbs' syntactic search procedure;
- centering theory, a model of how the local focus of attention shifts from sentence to sentence.
Lappin and Leass's RAP (Resolution of Anaphora Procedure) first applied syntactic and agreement filters. It then ranked the remaining pronoun candidates by salience, combining grammatical role, recency and frequency of mention. It reached 86% accuracy on 360 pronouns in computer manuals (Lappin & Leass 1994). Knowledge-poor alternatives followed:
- Mitkov's indicator-based scoring of part-of-speech-tagged text resolved 89.7% of pronouns in English technical manuals (Mitkov 1998).
- Ge, Hale and Charniak built a probabilistic model reaching 82.9% accuracy on pronouns (Ge et al. 1998). It combined:
- Hobbs distance, a candidate's position in the order proposed by a syntactic tree search;
- gender and animacy;
- selectional fit;
- mention counts.
The MUC-6 evaluation brought annotated data and a common metric. Vilain et al. scored systems by comparing the equivalence classes of key and response rather than individual links. This produced the "MUC score" (Vilain et al. 1995). For a single key class S, the recall component is (|S| − |p(S)|)/(|S| − 1), where p(S) is the partition of S induced by the response. Corpus-level recall sums over all key classes, Σ(|S| − |p(S)|)/Σ(|S| − 1), and precision mirrors this with key and response swapped (Vilain et al. 1995).
Later work criticised two existing metrics (Luo 2005):
- MUC ignores singletons (entities mentioned only once) and favours over-merging.
- B³ scores each mention by the overlap of its gold and system clusters, and can credit one entity more than once.
As an alternative it proposed CEAF, which aligns gold and system entities one-to-one. CEAF comes in a mention-based form and an entity-based form, CEAF_e (Luo 2005).
Soon, Ng and Lim showed that a decision tree over 12 inexpensive pair features could match the best rule-based systems on MUC-6 and MUC-7 (Soon et al. 2001). This mention-pair recipe became the reference baseline. Ng and Cardie extended it with best-first clustering and up to 53 features, reaching 70.4 MUC F on MUC-6 (Ng & Cardie 2002). The following years explored three directions:
- semantic knowledge from WordNet, Wikipedia and semantic roles (Ponzetto & Strube 2006);
- careful feature engineering for a simple pairwise classifier (Bengtson & Roth 2008);
- strong deterministic systems (Haghighi & Klein 2009). These need no coreference-annotated data and have no tunable parameters, although their semantic compatibility lists are mined from unlabeled parsed text.
A 2010 survey summarised the period (Ng 2010). It observed that differing corpora, scorers and preprocessing made results hard to compare. It urged baselines stronger than the Soon et al. model and public release of systems.
The CoNLL-2011 and CoNLL-2012 shared tasks standardised unrestricted, and later multilingual, coreference on OntoNotes (Pradhan et al. 2011; Pradhan et al. 2012). Systems were ranked by the CoNLL score, the mean of the MUC, B³ and CEAF_e F1 values (Lee et al. 2011). Stanford's multi-pass sieve ranked first in 2011 with predicted mentions (Lee et al. 2011):
- 57.8 CoNLL F1 in the closed track, which allows only the supplied data and resources;
- 58.3 in the open track.
A fuller account of the system appeared in 2013 (Lee et al. 2013).
Learned systems soon overtook rules. Durrett and Klein's log-linear mention ranker with surface feature templates reached 60.13 CoNLL F1 on the CoNLL 2011 test set. In their own comparison on that set, this was 3.5 points above the Stanford system (Durrett & Klein 2013). A joint model of coreference, typing and entity linking followed (Durrett & Klein 2014).
The figures below come from the CoNLL 2012 test set. It differs from the 2011 set, so they are not directly comparable with the numbers above:
- Clark and Manning's entity-level neural representations scored 65.29 CoNLL F1 on English (Clark & Manning 2016).
- Their mention rankers trained directly against B³ with reward rescaling reached 65.73 (Clark & Manning 2016).
The end-to-end span model of Lee et al. removed parsers and hand-built mention detectors altogether and improved on prior results by 1.5 F1 (Lee et al. 2017).
How it is used today
The standard benchmark remains English OntoNotes in the CoNLL-2012 format, scored with the CoNLL score. A reference scorer fixed earlier implementation bugs and handles predicted mentions under the original metric definitions (Pradhan et al. 2014).
Progress on this benchmark has come mostly from better encoders, such as ELMo (contextual word embeddings from a pretrained language model) and BERT. Pruning mainly bought efficiency:
| System | CoNLL avg. F1 (OntoNotes test) |
|---|---|
| Lee et al. 2017 + ELMo, tuned | 72.3 (Lee et al. 2018) |
| + coarse-to-fine pruning | 72.6 (Lee et al. 2018) |
| + second-order inference | 73.0 (Lee et al. 2018) |
| c2f-coref + BERT-large encoder | 76.9 (Joshi et al. 2019) |
Coarse-to-fine pruning sends only 50 candidate antecedents per span to the expensive scorer, compared with 250 under a distance heuristic. On the dev set, this cut costs under 0.2 F1 (Lee et al. 2018).
Coreference also serves as a component inside other systems:
- Scientific information extraction trains coreference jointly with entity and relation extraction. On the SciERC corpus of AI abstracts, adding coreference improved relation extraction by about 7.1% relative. Propagating coreference links also made the resulting knowledge graphs denser (Luan et al. 2018).
- Context-aware machine translation appears to learn anaphora resolution implicitly, because target-language pronouns must agree in gender with their antecedents (Voita et al. 2018).
- Coreference is a common testbed for social bias. The Winogender schemas (Rudinger et al. 2018) and the WinoBias set (Zhao et al. 2018) showed that rule-based, feature-based and neural systems all resolve pronouns differently depending on occupational stereotypes. Across the three WinoBias systems, the average gap between stereotypical and anti-stereotypical cases was 21.1 F1 (Zhao et al. 2018). The authors then applied three fixes to the end-to-end neural model of Lee et al. 2017: entity anonymisation, gender-swapped data augmentation and debiased embeddings. Together these shrank that model's gap on world-knowledge sentences from 26.6 to 1.1 F1, while its OntoNotes F1 fell only from 67.7 to 66.3.
By 2013, the sieve design had served as a component of hybrid systems for English, Chinese and Arabic. The Chinese port needed only small changes (Lee et al. 2013). Its authors had argued that new passes can be added without retraining, which suits low-resource pipelines (Raghunathan et al. 2010).
Open questions
World knowledge remains the clearest weakness. Missing semantic knowledge was already among the main causes of recall errors for the rule-based sieve (Raghunathan et al. 2010). For BERT-based systems, manual analysis finds three main error types (Joshi et al. 2019):
- missing world knowledge;
- paraphrased mentions;
- pronouns, especially in conversation.
Embeddings raise recall but also link entities that are similar yet distinct, such as "pilots" and "flight attendants" (Lee et al. 2017).
Long documents are another problem. Transformer encoders work on bounded segments, and F1 falls steadily as documents grow longer (Joshi et al. 2019):
- For BERT-large, segments of 384 word pieces worked best.
- Longer segments of 450 or 512 did worse.
- Half-overlapping segments gave no gain over independent ones.
Computational cost also matters. Exhaustive span-pair scoring grows as O(T⁴) in document length T, so every practical system depends on pruning (Lee et al. 2017).
Evaluation is still contested, because the metrics reward different behaviour. MUC can peak when a system outputs far too few entities, whereas CEAF peaks near the true entity count (Luo 2005). How to treat mentions that a system predicts but the gold standard lacks has also caused confusion (Pradhan et al. 2014).
Bias also remains open. Diagnostic sets can reveal skewed behaviour but cannot certify that a system is free of bias (Rudinger et al. 2018). Gender imbalance in the training corpus itself is one documented source of the problem (Zhao et al. 2018).
Finally, there is a structural question: should consistent entities emerge from local pairwise decisions or from explicit cluster-level reasoning? Measured gains from cluster-level reasoning are small:
- Second-order inference added 0.4 test F1 on top of coarse-to-fine pruning (Lee et al. 2018).
- A cluster ranker gained about 0.5 F1 over its own mention ranker (Clark & Manning 2016).
It therefore remains unclear how much explicit entity-level modelling adds.
Key papers
Related concepts
- Named entity recognition — Named entity recognition locates stretches of text that refer to specific real-world things, such as people, organizations, places…
- Discourse analysis — Discourse analysis is the study of how stretches of language beyond the single sentence form coherent wholes. It covers the relations that…
- Implicature — Implicature is the part of what a speaker communicates that goes beyond the literal content of the words. Hearers infer it by assuming the…
- Semantic role labeling — Semantic role labeling is the task of finding, for each predicate in a sentence, the phrases that act as its participants and labeling each…
More papers
Topics: 🔗 Coreference resolution · 🧵 Discourse analysis
Shelves: 🗣️ Linguistics & languages · 💬 Natural language processing
This page in Markdown → https://md.research.elamur.ai/free/en/concepts/coreference-resolution/