Technical Report:

arXiv:1802.00033v1 [cs.CL] 31 Jan 2018

Adjudication of Coreference Annotations via Answer Set
Optimization
Peter Schüller∗
Institut für Logic and Computation, Knowledge-Based Systems Group
Technische Universität Wien, Austria
Faculty of Engineering, Marmara University, Turkey
schueller.p@gmail.com
February 2, 2018

Abstract
We describe the first automatic approach for merging coreference annotations obtained from
multiple annotators into a single gold standard. This merging is subject to certain linguistic hard
constraints and optimization criteria that prefer solutions with minimal divergence from annotators.
The representation involves an equivalence relation over a large number of elements. We use Answer
Set Programming to describe two representations of the problem and four objective functions suitable
for different datasets. We provide two structurally different real-world benchmark datasets based on
the METU-Sabanci Turkish Treebank and we report our experiences in using the Gringo, Clasp, and
Wasp tools for computing optimal adjudication results on these datasets.

1

Introduction

Coreference Resolution [Ng10; SPT08] is the task of finding phrases in a text that refer to the same
real-world entity. Coreference is commonly annotated by marking subsequences of tokens in the input
text as mentions and putting sets of mentions into chains such that all mentions in a chain refer to the
same, clearly identifiable entity in the world.
Example 1 (Lee et al. [Lee+13]). In the text “John is a musician. He played a new song. A girl was
listening to the song. ‘It is my favorite,’ John said to her.” we can identify the following mentions.
[John] (i) is [a musician] (ii) . [He] (iii) played [a new song] (iv) .
[A girl] (v) was
listening to [the
song] (vi) .


“[It] (vii) is [my] (ix) favorite (viii) ,” [John] (x) said to [her] (xi) .

(1)

Roman superscripts denote mention IDs, chains in this text are as follows: {(i), (iii ), (ix ), (x)} (John,
He, my, John); {(iv ), (vi), (vii)} (a new song, the song, It); and {(v), (xi)} (A girl, her), where roman
numbers again refer to mention IDs.
For building and testing automatic coreference resolution methods, annotated corpora, i.e., texts
with mention and chain annotations, are an important resource. Once trained, coreference resolution
systems can be applied in various applications, for example, Cardie et al. [Car+04] use it for complex
opinion extraction, Mueller [Mue04] uses it for script-based story understanding, Witte, Khamis, and
Rilling [WKR10] perform reasoning on coreference chains to create OWL Ontologies from texts, and
∗ This work extends prior work [Sch17] with a semi-automatic adjudication encoding, extended formal descriptions and
discussions, a tool description, and several additional examples. This is a preprint of [Sch18].

1

Tuggener [Tug14] compares the accuracy of coreference resolution systems when used as preprocessing
for discourse analysis, summarization, and finding entity contexts.
Adjudication is the task of combining mention and chain information from several human annotators
into one single gold standard corpus. These annotations are often mutually conflicting and resolving
these conflicts is a task that is global on the document level, i.e., it is not possible to decide the truth of
the annotation of one token, mention, or chain, without considering other tokens, mentions, and chains
in the same document.
We here present results and experiences obtained in a two-year project for creating a Turkish coreference corpus [Sch+17], which included an effort for developing and improving a (semi)automatic solution
for coreference adjudication. We produced two datasets which are assembled from 475 individual annotations of 33 distinct documents from the METU-Sabanci Turkish Treebank [Say+04]. Adjudicating
documents manually with tools such as BART [Ver+08] is usually done on a small set of annotations,
for example, coreference annotations in the OntoNotes corpus [Pra+07] were created by at most two independent annotators per document. In the Turkish corpus, we needed to adjudicate between eight and
twelve independent coreference annotations. Given such a high number of annotations, it is suggestive
to use majorities of annotator decisions for suggesting an adjudication solution to the human annotator.
In this paper, we describe a (semi-)automatic solution for supporting adjudication of coreference
annotations based on Answer Set Programming (ASP) [Bar04; Lif08; BET11; Geb+12]. ASP is a
logic programming and knowledge representation paradigm that allows for a declarative specification of
problems and is suitable for solving large-scale combinatorial optimization problems.
Our contributions are as follows.
• We formalize the problem of coreference adjudication, introduce four objective functions that have
practical relevance for both our datasets, and we describe the basic idea of semi-automatic adjudication in Section 3.
• We propose two ASP encodings in Section 4: the MM (mention-mention) encoding explicitly represents a transitive closure over the equivalence relation of chains, while the CM (chain-mention) encoding avoids this explicit representation. Moreover, we provide an ASP module for semi-automatic
adjudication.
• We describe our tool and the intended adjudication workflow in Section 5.
• We describe and provide two real-life datasets,1 outline their properties and differences, and report
on empirical experiments with unsatisfiable-core optimization and stratification using the tools
Gringo [Geb+11], Clasp [GKS12], and Wasp [Alv+15a] in Section 6.
• We formulate insights about developing ASP applications, analyzing bottlenecks in such applications, and specific issues we encountered with optimization in Section 7.
We describe related work in Section 8 and conclude in Section 9.
Our approach is not specific to Turkish, and we have implemented it in the publicly available CaspR
tool2 for performing (semi-)automatic adjudication of coreference annotations based on the popular
CoNLL data format. CaspR is the first automatic tool for coreference adjudication, and our datasets are
the first published datasets for automatic coreference adjudication.

2

Preliminaries

2.1

Coreference Resolution

Coreference resolution is the task of finding phrases in a text that refer to the same entity [SPT08;
Ng10]. We call such phrases mentions, and we call a group of mentions that refer to one entity a chain.
Formally we can describe mention detection and coreference resolution as follows.
1 https://bitbucket.org/knowlp/asp-coreference-benchmark
2 https://github.com/knowlp/caspr-coreference-tool

2

Definition 2.1. A document D is a sequence of tokens w1 , . . . , wn with indexes 1, . . . , n. A mention
is a pair (s, e) of indexes, 1 ≤ s ≤ e ≤ n, pointing to start index s and end index e in D, such that the
sequence ws ws+1 · · · we is a natural language expression that refers to a discourse entity [Cho02]. Mention
detection is the task of finding the set M = {(s1 , e1 ), . . . , (sm , em )} of all mentions in a document.
Example 2. In Example 1 the document (1) contains 31 tokens with indexes as follows.
John1 is2 a3 musician4 .5 He6 played7 a8 new9 song10 .11
A12 girl13 was14 listening15 to16 the17 song18 .19
“ 20 It21 is22 my23 favorite24 ,26 ” 25 John27 said28 to29 her30 .31
The phrases ‘John’, ‘a musician’, ‘he’, and ‘a new song’ in the first line are mentions, and they are represented as pairs (1, 1), (3, 4), (6, 6), and (8, 10), respectively. The overall set of mentions is M = {(1, 1),
(3, 4), (6, 6), (8, 10), (12, 13), (17, 18), (21, 21), (23, 23), (23, 24), (27, 27), (30, 30)}.
Definition 2.2. Given a set M of mentions, coreference resolution is the task of partitioning M such
that for each partition, all mentions refer to the same discourse entity. The resulting partitions of M are
called chains or entities.
Example 3. The chains of document (1), described in Example 1, are formally represented as P = {{(1, 1),
(6, 6), (23, 23), (27, 27)}, {(12, 13), (30, 30)}, {(12, 13), (30, 30)}}.
Mentions can be part of other mentions, but in that case, they (usually) cannot be coreferent. Moreover, mentions are (usually) noun phrases [SPT08], which has the consequence that whenever two mentions m and m′ are overlapping, either m is properly contained in m′ or vice versa. Per usual linguistic
convention, mention pairs that are in a predicative relationship (e.g., ‘John is a musician’) are not coreferent. In Example 1, mention pairs (i)/(ii ) and (vii )/(viii ) are in such a predicative relationship. This
condition cannot be verified automatically without a structural analysis of the given text, therefore we
do not use it as part of formal constraints on adjudication solutions.
Given a set of mentions, there are exponentially many potential solutions to the coreference resolution
problem, and finding a globally optimal solution is NP-hard according to most measures of coreference
optimality [SE12].
Note that anaphora resolution [Hir81; Mit99; CG08; Keh+08] is a different task than coreference
resolution. The former deals only with references to earlier parts of a text and sometimes even only with
references where a pronoun points to another phrase. Contrary to that, coreference resolution also deals
with noun phrases that can refer to each other, and references can be in any direction within the text.

2.2

Answer Set Programming

ASP is a logic programming paradigm which is suitable for knowledge representation and finding solutions
for computationally (NP-)hard problems [GL88; Lif08; BET11]. We next give brief preliminaries of ASP
programs with (uninterpreted) function symbols, aggregates, choices, and weak constraints. For a more
elaborate description, we refer to the ASP-Core-2 standard [Cal+12], or to books about ASP [Bar04;
GK14; Geb+12].
Syntax. Let C and X be mutually disjoint sets of constants and variables, which we denote with the first
letter in lower case and upper case, respectively. Constant names are used for constant terms, predicate
names, and names for uninterpreted functions. The set of terms T is recursively defined, it is the smallest
set containing N ∪ C ∪ X as well as uninterpreted function terms of form f (t1 , . . . , tn ) where f ∈ C and
t1 , . . . , tn ∈ T . An ordinary atom is of the form p(t1 , . . . , tn ), where p ∈ C, t1 , . . . , tn ∈ T , and n ≥ 0 is
the arity of the atom. An aggregate atom is of the form X = #agg{ t : b1 , . . . , bk } with variable X ∈ X ,
aggregation function #agg ∈ {#max , #count }, with 1 < k, t ∈ T and b1 , . . . , bk a sequence of atoms. A
term or atom is ground if it contains no sub-terms that are variables.
A rule r is of the form
α1 ∨ · · · ∨ αk ← β1 , . . . , βn , not βn + 1 , . . . , not βm

(2)

where 0 ≤ k, 0 ≤ n ≤ m, each head element αi , 0 ≤ i ≤ k, is an ordinary atom, and each head element βj ,
0 ≤ j ≤ m, is an atom. A rule r is a constraint, if k = 0, and a fact if k = 1 and m = 0.
3

A weak constraint is of form
β1 , . . . , βn , not βn + 1 , . . . , not βm . [w@1, t1 , . . . , tl ]

(3)

where 0 ≤ n ≤ m, 0 ≤ l, w ∈ Z, βj , 0 ≤ j ≤ m, is an atom, and ti , 0 ≤ i ≤ l, is a term. (Note that @1
determines the ‘level’ of the weak constraint which we do not use.)
We denote by H(r) = {α1 , . . . , αk } the head of a rule r. We denote by B + (r) = {β1 , . . . , βn } the
positive body, by B − (r) = {βn + 1 , . . . , βm } the negative body, and by B(r) = {β1 , . . . , βn , not βn + 1 , . . . ,
not βm } the body of a rule or weak constraint r.
A program is a finite set P of rules and weak constraints.
To ensure finite instantiation, all variables in an ASP rules and weak constraints must be safe, i.e.,
they must occur in a positive body literal. For details see the ASP-Core-2 standard [Cal+12].
Semantics. The semantics of an ASP program P is defined using its Herbrand Base HB P and its ground
instantiation grnd(P ). Given an interpretation I ⊆ HB P , an atom a is true wrt. I iff a ∈ I and an aggregate atom X = #agg { t : b1 , . . . , bk } is true wrt. I iff X = f#agg ({ σ(t) | σ(b1 ) ∈ I, . . . , σ(bk ) ∈ I }) where σ
is a substitution from variables X to nonground terms in T , f#max (X) = max(X) and f#count (X) = |X|.
The body of a rule or weak constraint is satisfied wrt. I iff all a ∈ B + (r) are true wrt. I and no a ∈ B − (r)
is true wrt. I. A rule r is satisfied wrt. I iff H(r) ∩ I = ∅ or B(r) is not satisfied wrt. I. A weak r
constraint is satisfied wrt. I iff B(r) is not satisfied wrt. I. An interpretation I is a model of a program
P if I satisfies all rules in P .
The FLP-reduct [FPL11] f P I reduces a program P using an answer set candidate I: f P I = {r ∈
grnd (P ) | B(r) is satisfied wrt. I}. An interpretation I is an answer set of P iff I is a ⊆-minimal model
of f P I .
Let W (I) be the set of ground weak constraints r ∈ P that are not satisfied wrt. I. Then the set
C(I) = {(w, t1 , . . . , tk ) | r ∈ W (I)} is the set of all tuples of weak constraints of form (3) in W (I), and
the cost of answer set I is the sum over the first elements of all tuples in C(I). Answer sets of the lowest
cost are preferred.
Syntactic Sugar. Anonymous variables of form ‘_’ are replaced by new variable symbols. Choice
constructions can occur instead of rule heads of the form lb { p(~x) : q(~x) } ub where lower bound lb
and upper bound ub are natural numbers and can also be omitted (then, lb = 0 and ub = ∞), and ~x
symbolizes a list of argument terms containing a shared set x of variables. A rule with a choice head is
rewritten into a set of rules with disjunctive heads of form p(~x) ∨ p̂(~x) for all q(~x), and into a constraint
which enforces that at least lb and at most ub atoms p(~x) are true whenever the rule body is true. For
example, the rule 1 {p(a); p(b)} 2 ← p(c) generates all solution candidates where at least 1 and at most
2 atoms of the set {p(a), p(b)} are true whenever p(c) is true. For details of choice constructions and the
rewriting to disjunctive rules plus constraints with aggregates, we refer to Section 3.2 of the ASP-Core-2
standard [Cal+12].

3

Automatic Coreference Adjudication

Coreference adjudication is the task of arbitrating several coreference resolution solutions of a single
document that were independently created by several human annotators. We assume that human annotators created these solutions to the best of their knowledge and abilities and we assume that humans
sometimes make mistakes. Therefore, we are dealing with a problem of merging multiple, potentially
mutually inconsistent, solutions of the mention detection and the coreference resolution problem. The
goal is to create a single solution that optimally corresponds to the given inputs.
We formalize coreference adjudication as follows.
Definition 3.1. Given u ≥ 2 sets of mentions M1 , . . . , Mu over a document D and corresponding chains
P1 , . . . , Pu of the respective sets of mentions, the coreference adjudication problem is to find the set of
mentions M̂ and the set of chains P̂ (with P̂ a partition of M̂ ) such that P̂ and M̂ observe structural
constraints described in Section 2, and that resulting chains P̂ correspond best with the given chains
P1 , . . . , Pu .
The problem of deciding what corresponds best is usually solved manually by domain experts, and
usually there is only a small set of given annotations which mostly coincide because they were created by
4

1 (2
2 (3)
3 2)
4 (3)
5 6 (2)

1 (3
2
3 3)
4
5 (3)
6
-

1 (1(2)
2
3
1)
4
(2)
5
6
(1)

1 (2
2 (4)
3 2)
4
5 (2)
6 (4)

(a) in1.conll

(b) in2.conll

(c) in3.conll

(d) in4.conll

Figure 1: Minimalistic example CoNLL input files containing two columns: token index (first column)
and coreference chains (second column).
trained experts. In our work on the Turkish corpus [Sch+17] we encountered the problem of adjudicating
a larger set of annotations (at least eight annotations per document) with a higher level of divergence
among (less trained) annotators.
We approach this problem by representing a given coreference chain in terms of all links between
pairs of mentions in that chain (mention-mention links). We represent adjudication by selecting a subset
of the given mention-mention links and constructing a new set of chains from these selected links. We
choose the optimal solution by defining quantitatively how ‘correspond best’ in Definition 3.1 can be
measured in terms of selected and non-selected links.
Note that a solution might also contain mention-mention links that are not present in any annotation.
This can happen because chains are equivalence relations: if we merge equivalence relations that are not
subsets of each other, the new equivalence relation is the reflexive, symmetric, and transitive closure of
the original relations.
Example 4. Assume that the chains in Example 1 are given by annotator A, and that annotator B
provides the chain {(i), (ii), (x )} (John, a musician, John). If we merge this chain with the chain
{(i), (iii), (ix ), (x )} (John, He, my, John) from annotator A in a naive way (i.e., by merging the sets),
then we obtain a single chain {(i), (ii), (iii), (ix ), (x )} (John, a musician, He, my, John) although no
annotator indicated that the mentions (ii) and (iii) (‘a musician’ and ‘He’) belong to the same chain.
Next, we give a symbolic and more comprehensive running example.
Example 5. Figure 1 shows an adjudication problem consisting of input from four annotators. We show
token index in the first column and coreference chains in the second column of the CoNLL format, where
single-token mentions are marked as ‘(X)’, multi-token mentions start with ‘(X’ and end with ‘X)’, where
X is the chain that the mention belongs to. The absence of any mention starting or ending at a token is
marked with ‘-’.
In this example, annotator (b) indicated a single chain with ID 3 containing mentions {(1, 3), (5, 5)},
and annotator (a) indicated a chain with ID 2 containing mentions {(1, 3), (6, 6)} as well as a chain with
ID 3 containing mentions {(2, 2), (4, 4)}.
There are several possible outcomes for merging these (input) annotations into a single (output) gold
standard annotation. Intuitively, annotators (a) and (c) indicated that mention (1, 3) is coreferent with
(6, 6), while annotators (b) and (d) indicated that (1, 3) is coreferent with (5, 5). Only annotator (c)
marked (1, 1) as a separate mention that is coreferent with (4, 4).
We next define the meaning of ‘correspond best’ in Definition 3.1 by defining an objective function
for selecting preferred solutions.

3.1

Objective Functions

We next represent the given annotations P1 , . . . , Pu and the solution chain P̂ as sets of links between
pairs of mentions (mention-mention links). We define a preference relation for filtering out undesired
solutions where we incur cost under the following conditions.
(C1) Not using a link provided by an annotator in the solution.
(C2) Using a link provided by an annotator where a number of other annotators did not provide the
same link.
5

1 (1(3)
2
(2)
3
1)
4
(3)
5
(1)
6
(2)

1 (1(2)
2
(2)
3
1)
4
(2)
5
(1)
6
(1)

(a) [U]

(b) [UA]

1 (1
2
3 1)
4
5
6 (1)

1 (1
2
3 1)
4
5 (1)
6
-

(c) [V]

1 (1
2
3 1)
4
5 (1)
6 (1)
(d) [VA]

Figure 2: Optimal solutions of automatic adjudication of inputs in Figure 1 with all four objectives.
(C3) Putting two mentions into a chain where no annotator gave any evidence for this (see Example 4).
We incur separate cost for each annotator who provided a link in (C1), and for each annotator who did
not provide a link that was used in (C2).
Concretely we use the following objective functions in our application:
[V] Cost 2 for (C1), cost 1 for (C2), and (C3) is a hard constraint (infinite cost).
[U] Cost 2 for (C1), no cost for (C2), and (C3) is a hard constraint.
[VA] Cost 2 for (C1), cost 1 for (C2), and cost 1 for (C3).
[UA] Cost 2 for (C1), no cost for (C2), and cost 1 for (C3).
Note that cost for (C1) is higher than for (C2) because we observed in an initial manual adjudication of
two documents of the Turkish corpus that annotators miss links more frequently than they add spurious
links. In [U] only one cost component (C1) is active, therefore the absolute value of the cost incurred for
each link does not matter. We use the value of 2 in [U] because this makes the coefficient of (C1) uniform
across all objective variations and permits a modular ASP translation of all objective cost components.
Intuitively, objectives containing letter V apply “voting” to prefer certain solutions: a link given by
only one annotator can be dismissed if many other annotators do not give the same link. On the other
hand, objectives with letter U use “as many mentions as possible”: there is no cost for (C2). Finally,
objectives containing letter A allow additional links at a cost. In our real-world application of the Turkish
coreference corpus, we opted to use objective [V] where (C3) is a strict constraint. On our data, using
[VA] and choosing a higher value than 1 for the cost of (C3) had a similar effect as using a strict
constraint. This is because a solution that merges two chains such that a cost of type (C3) is incurred
usually incurs also several costs of type (C2) in other links. For other adjudication projects which use
objectives [UA] or [VA], the coefficient of cost type (C3) might need to be adjusted.
Cost components are optimized such that their sum is minimized. There is no lexicographic order
(priority) among costs where one type of cost would be minimized before another type of cost. For
example, the objective function [V] finds a balance between ignoring and using annotations that were
given by some and not given by other annotators. Using a priority would strictly prefer one over the
other.
Example 6. Figure 2 shows automatically adjudicated results for all objective functions, based on Example 5 and Figure 1.
Objective [U] in Figure 2(a) produces a single optimal adjudication solution where both chains from
Figure 1(a) and chain 1 from Figure 1(c) are ignored, which yields a total cost of 6 and ignores three
mention-mention links.
Objective [UA] in Figure 2(b) produces a single optimal adjudication solution of cost 4: chain 4 from
Figure 1(d) is ignored (cost 2) and two links that are not present in any annotation are created (each
incurs cost 1): between (1, 1) and (2, 2), and between (5, 5) and (6, 6).
Objective [V] produces two optimal adjudication solutions, each with cost 12. The left solution in
Figure 2(c) uses chain 2 from Figure 1(a), which is equivalent to chain 1 in Figure 1(c). This incurs a
cost of 2 because links of this chain are absent in Figures 1(b) and 1(d). All other chains (one each in
Figures 1(a), 1(b), and 1(c), and two in Figure 1(d)) are ignored at a total cost of 10 (each of these chains
contains one link). Using any of these ignored chains would incur a cost of 3 per chain because the chain
was not given by three out of four annotators. Using chain 3 in Figure 1(b) or chain 2 in Figure 1(d)
6

1
2
3
4
5
6

(2
(3)
2)
(3)
(2)

(3
3)
(3)
-

(1(2)
1)
(2)
(1)

(2
(4)
2)
(2)
(4)

1
2
3
4
5
6

=(1
(2)
=1)
(3)
(1)
=(1)

(a) Full output of automatic adjudication after
manually enforcing mentions (1, 3) and (6, 6) in
chain 1.

(2
(3)
2)
(3)
(2)

(3
3)
(3)
-

(1(2)
1)
(2)
(1)

(2
(4)
2)
(2)
(4)

=(1
(2)
=1)
(2)
=(1)

(b) Result of performing automatic adjudication
relative to enforced coreference information in
(a).

Figure 3: Semi-automatic adjudication of annotations given in Figure 1 using objective [U]. Manually
enforced coreference information in the last column of the CoNLL format is prefixed with ‘=’.
would create an additional link between (5, 5) and (6, 6), which is not permitted in objective [V]. The
second solution (Figure 2(c) right) is symmetric to the first one: it uses only chain 3 from Figure 1(b),
which is equivalent to chain 2 in Figure 1(d).
Objective [VA] produces a single optimal solution of cost 11 that is shown in Figure 2(d). Intuitively,
this solution merges both solutions of [V]. Using chain 2 from Figure 1(a), chain 3 from Figure 1(b),
chain 1 from Figure 1(c), and chain 2 from Figure 1(d) incurs cost 4 because each link is not annotated
by two out of four annotators. Moreover, three links (chains 3 in Figure 1(a), chain 2 in Figure 1(c), and
chain 4 in Figure 1(d)) are ignored, which contributes an additional cost of 6. The link between (5, 5)
and (6, 6), which was not specified by any annotator, incurs a cost of 1.
The main idea of these preferences is to use the given information optimally while producing an
overall consistent solution. The preferences are motivated by properties of our datasets: if mentions are
given to annotators, they can only disagree on the assignment of mentions to chains. Objectives [V]
and [VA] make sure that the solution reflects the opinion of the majority of annotators. Contrarily, if
mentions are not given, annotators must produce mentions and chains, and often disagree on mentions,
such that [V] and [VA] eliminate most mentions and chains completely. In the latter case, [U] and [UA]
combined with a semi-automatic workflow is the better choice.

3.2

Semi-automatic Adjudication

Automatic adjudication works well if enough annotations with high inter-annotator agreement [Pas04]
are available. Otherwise, automatic adjudication is merely a preprocessing step for human adjudication.
In case of a low number of annotations per document, or highly divergent annotator opinions, making
the final decision on the correctness of an annotation should be done by a human expert.
For that purpose, we allow a partial specification of chain and mention information as additional input.
We extend our approach so that it produces an optimal solution relative to this given information.
In practice, we do this by producing a human-readable output format in automatic adjudication.
This format is in the popular CoNLL format (see Figure 3) and contains tokens and coreference information from all annotators and from the automatic adjudication. The idea is that a human adjudicator
can inspect the output and manually specify parts of the output, followed by re-optimization of the
adjudication relative to these manually enforced parts of the output (more details about this is given in
Section 5).
Example 7. Figure 3 shows a CoNLL file that was generated from automatic adjudication of annotations
in Figure 1 using objective [U]. The rightmost column originally was the same as in Figure 2(a) but
the human adjudicator has specified the following coreference information (prefixed with ‘=’): mentions
(1, 3) and (6, 6) must be in a chain, and mention (1, 1), which was coreferent with (4, 4), does not exist.
Re-optimizing the input in Figure 3(a) yields the output Figure 3(b) where the result of automatically
adjudicating relative to enforced mention and chain information is put into the last column. Different
from the adjudication result explained in Example 6, coreference between (1, 3) and (5, 5) is no longer
possible because it would generate a non-annotated link between (5, 5) and (6, 6). Therefore token 5
carries no mention information (‘-’). Moreover, the link between (1, 1) and (4, 4) is ruled out because
mention (1, 1) was enforced to be absent, which makes the link between (2, 2) and (4, 4) appear in the
optimal solution.
7

4

ASP Encodings

We next describe ASP input and output representations for the adjudication problem. Then we provide
two ASP encodings which model coreference adjudication and assign a cost to solutions according to
Section 3.1. The MM Encoding explicitly represents the transitive closure of mention-mention links,
while the CM encoding avoids this representation by assuming an upper limit on the number of chains
and guessing which mention belongs to which chain.
In all encodings, we use the convention that variables C, A, Am, S, and E, will be substituted with
chain IDs, annotator IDs, annotator mention IDs, start token indexes, and end token indexes, respectively.
Moreover, variable M holds terms of the form mid(S, E) for representing a mention without annotator
information. We call mentions that are represented in this way canonical mentions or short cmentions.
We use subscripted versions of the variables introduced above.

4.1

Input and Output ASP Representation

Given a document D and u coreference annotations P1 , . . . , Pu which are partitions of sets of mentions
M1 , . . . , Mu over D. We associate unique IDs 1, . . . , u with annotations. For each annotation Pa , 1 ≤ a ≤ u
we have a set of chains Pa = {C1 , . . . , Ck } and we associate unique IDs 1, . . . , k with these chains. The
corresponding mentions are Ma = {(s1 , e1 ), . . . , (sm , em )} and we associate unique IDs 1, . . . , m with the
mentions in Ma . (In the general case, each annotator produces her own set of mentions.)
Definition 4.1. To represent an adjudication instance in ASP, we create facts of the form
mention(a, j , sj , ej ) for each mention (sj , ej ) with ID j in the annotation with ID a. Moreover, we
create facts of the form cm(a, c, j ) for each mention with ID j that is in the chain with ID c in the
annotation with ID a.
Example 8. Given the document in Example 1 and token indexes shown in Example 2. Consider that
annotator a1 created the chain c1 = {m1 , m2 , m3 } containing mentions m1 = (1, 1) ‘John’, m2 = (3, 4)
‘a musician’, and m3 = (6, 6) ‘He’. Annotator a2 created the chain c2 = {m4 , m5 } containing mentions
m4 = (12, 13) ‘a girl’ and m5 = (30, 30) ‘her’. These annotations are represented in ASP as follows:
mention(a1 , m1 , 1 , 1 ).
cm(a1 , c1 , m1 ).

mention(a1 , m2 , 3 , 4 ).
cm(a1 , c1 , m2 ).

mention(a2 , m4 , 12 , 13 ).

mention(a2 , m5 , 30 , 30 ).

cm(a2 , c2 , m4 ).

cm(a2 , c2 , m5 ).

mention(a1 , m3 , 6 , 6 ).
cm(a1 , c1 , m3 ).

where we use constants a1 , a2 , c1 , c2 , m1 , . . . , m5 as IDs for representing the corresponding annotators,
chains, and mentions.
The answer sets of our logic program represent a set of chains without annotator information, represented as atoms of the form resultcm (C , mid (S , E )), which indicates that in chain C there is a mention
that is a span from start token S to end token E , inclusive.
Example 9. Assume we have adjudicated the annotations of Example 8 such that the solution comprises
two chains v = {(1, 1), (6, 6)} and w = {(12, 13), (30, 30)}. This is represented by the following atoms:
resultcm (v , mid (1 , 1 ))
resultcm (w , mid (12 , 13 ))

resultcm (v , mid (6 , 6 ))
resultcm (w , mid (30 , 30 ))

Intuitively, this means that ‘John’ and ‘He’ are coreferent, as well as ‘a girl’ and ‘her’, however ‘John’ is
not coreferent with ‘a musician’.
Input for semi-automatic adjudication consists of mentions, chains, and indicators for the absence
of mention boundaries. Mentions and chains are represented as a separate annotation with a special
annotator ID ‘forced ’. A token Token without any mention boundary is represented as a fact of form
empty(Token).
Example 10. In Example 7 (Figure 3(a)) the human adjudicator specified that mention (1, 3) is coreferent
with (6, 6). This is represented by the following facts.
mention(forced , m1 , 1 , 3 ) ← .

mention(forced , m2 , 6 , 6 ) ← .

cm(forced , c1 , m1 ) ← .

cm(forced , c1 , m2 ) ← .
8

na(N ) ← N = #count { A : mention(A, _, _, _) }.
acmen(A, Am, mid (S , E )) ← mention(A, Am, S , E ).
asamechain(A, Am1 , Am2 ) ← cm(A, C , Am1 ), cm(A, C , Am2 ), Am1 6= Am2 .
csamechain(M1 , M2 ) ← acmen(A, Am1 , M1 ), acmen(A, Am2 , M2 ),
asamechain(A, Am1 , Am2 ), M1 < M2 .
evidence(M1 , M2 , Ev ) ← csamechain(M1 , M2 ), Ev = #count {

(4)
(5)
(6)
(7)

A : asamechain(A, Am1 , Am2 ), Am1 < Am2 ,
acmen(A, Am1 , M1 ), acmen(A, Am2 , M2 )
}, Ev > 0 .
cmomitcost (M1 , M2 , 2 · K ) ← csamechain(M1 , M2 ), evidence(M1 , M2 , K ).

(8)
(9)

cmusecost (M1 , M2 , N − K ) ← csamechain(M1 , M2 ), evidence(M1 , M2 , K ),
N − K > 0 , na(N ).

(10)

Figure 4: Common deterministic definitions used in objective function constraints.

link (A, Am1 , Am2 ) ← cm(A, C , Am1 ), cm(A, C , Am2 ), Am1 < Am2 .
{ uselink (A, Am1 , Am2 ) } ← link (A, Am1 , Am2 ).

(11)
(12)

clink (M1 , M2 ) ← uselink (A, Am1 , Am2 ), M1 < M2 ,
acmen(A, Am1 , M1 ), mention(A, Am, M2 ).

(13)

clink (M1 , M2 ) ← uselink (A, Am2 , Am1 ), M1 < M2 ,
acmen(A, Am1 , M1 ), mention(A, Am2 , M2 ).

(14)

Figure 5: Common link selection and canonicalization encoding.
where the chain is represented by constant c1 and the mentions by m1 and m2 .
We next describe our encodings.

4.2

Common Rules for Objective Costs

Figure 4 shows a common program module which defines helpful concepts for realizing cost aspects
(C1)–(C3) from Section 3.1. The rules contain no disjunctions or guesses and depend only on input
facts, hence this module is deterministic and a modern grounder like Gringo will transform it into facts
during instantiation.
Rule (4) represents the number of annotations in the input in predicate na/1. This number is
used for relating the weight of one annotator’s input compared with all annotators. Rule (5) defines
predicate acmen/3 which relates annotated mentions with their canonical representation in a term of
the form mid (S , E ) where S and E are the starting and ending token of the mention in the document,
respectively. Rule (6) represents in atoms of the form asamechain (A, Am 1 , Am 2 ) all pairs of distinct
mentions Am 1 and Am 2 that were put into the same chain by annotator A. Rule (7) represents the
same pairs of mentions but projects away annotator information and relates pairs of cmentions in atoms
of the form csamechain (M1 , M2 ).
Based on csamechain and asamechain , rule (8) represents for each pair of canonical mentions
(M1 , M2 ) the number of annotators who put M1 and M2 into the same chain. This value is represented
only if it is above zero. Rule (9) defines cost component (C1) which is a cost of 2 for each annotator
who provided positive evidence for the respective link. Similarly, using the total number of annotators,
rule (10) defines cost component (C2) which is a cost of 1 for each annotator who did not put both
canonical mentions M1 and M2 into the same chain, while at least one other annotator did so.

9

cc(M1 , M2 ) ← clink (M1 , M2 ).
cc(M2 , M1 ) ← cc(M1 , M2 ).

(15)
(16)

cc(M1 , M3 ) ← cc(M1 , M2 ), cc(M2 , M3 ).
notrepresentative(M2 ) ← cc(M1 , M2 ), M1 < M2 .

(17)
(18)

resultcm (M1 , M2 ) ← cc(M1 , M2 ), not notrepresentative(M1 ).
resultchain(C ) ← resultcm (C , _).

(19)
(20)

Figure 6: MM encoding.

[Cost @1 , M1 , M2 , omit ]

(21)

clink (M1 , M2 ), cmusecost (M1 , M2 , Cost ).
← cc(M1 , M2 ), M1 < M2 , not clink (M1 , M2 ).

[Cost @1 , M1 , M2 , use]

(22)
(23)

cc(M1 , M2 ), M1 < M2 , not clink (M1 , M2 ).

[1 @1 , M1 , M2 ]

(24)

not clink (M1 , M2 ), cmomitcost (M1 , M2 , Cost ).

Figure 7: MM objective function variations.

4.3

Common Link Guess and Canonicalization Encoding

Figure 5 shows a nondeterministic common module of both encodings. This module guesses for each
mention-mention link that was annotated whether it will be part of the solution. Selected mentionmention links are represented canonically in predicate clink /2.
In detail, Rule (11) represents annotated mention-mention links in predicate link /3, and rule (12) is
a guess whether to use each of these links. Used links are represented as cmentions in rules (13) and (14),
i.e., their annotator information is projected away.3 Note that these rules make use of deterministically
defined predicate acmen/3 from the common program module given in Figure 4.

4.4

Mention-Mention Encoding (MM)

Figure 6 shows the core module of the MM encoding which is used in addition to the common program
modules in Figures 4 and 5. Rules (15)–(17) represent the reflexive, symmetric, and transitive closure of
predicate clink /2 in predicate cc/2 . This represents result chains in an explicit equivalence relation over
cmentions: each strongly connected component (SCC) of predicate cc/2 is equivalent to a coreference
chain. Rule (18) defines which elements of the equivalence relation is not the lexicographically smallest
element in the SCC, and rule (19) defines result chains by using the smallest cmention in each SCC as
a representative for the corresponding chain. Rule (20) defines that these cmentions represent chains.
Figure 7 shows constraints for realizing objective functions for the MM encoding. Weak constraint (21)
incurs a cost for non-existing links in atoms of form clink (M1 , M2 ), corresponding to cost (C1) in Section 3.1. Similarly, (22) incurs cost for existing links, corresponding to (C2). Finally, corresponding
to (C3), constraint (23) strictly forbids to put two mentions into a chain if there is no evidence for that
from annotators, and weak constraint (24) alternatively incurs a cost for such mention pairs. Recall that
predicates cmomitcost /3 and cmusecost /3 are defined deterministically from input facts (see Section 4.2
and Figure 4), therefore weak constraints (21) and (22) contain only one body literal after intelligent
instantiation.

4.5

Chain-Mention Encoding (CM)

Figure 8 shows the core of the CM encoding, which is also based on the common program modules in
Figures 4 and 5. Different from the MM encoding, in the CM encoding we directly guess the extension
of predicate resultcm/2 instead of deriving it from predicate clink /2 .
3 This

projection requires two rules because mention and cmention IDs can have different lexicographic order.

10

countchain(A, N ) ← cm(A, _, _),
N = #count { C : cm(A, C , _) }.
maxchain(N ) ← N = #max { C : countchain(_, C ) }.
chainlimit (6 /5 · N ) ← maxchain(N ).
{ resultchain(C ) : C ∈ {1 , . . . , N } } ← chainlimit (N ).
resultchain(C2 ) ← resultchain(C1 ), C2 ∈ {1 , . . . , C2 − 1 }.
cmention(M ) ← clink (M , _).
cmention(M ) ← clink (_, M ).
1 { resultcm (C , M ) : resultchain(C ) } 1 ← cmention(M ).

(25)
(26)
(27)
(28)
(29)
(30)
(31)
(32)

← clink (M1 , M2 ), resultcm (C , M1 ), not resultcm (C , M2 ).

(33)

← clink (M1 , M2 ), not resultcm (C , M1 ), resultcm (C , M2 ).

(34)

Figure 8: CM encoding.

not clink (M1 , M2 ), cmomitcost (M1 , M2 , Cost ).
[Cost @1 , M1 , M2 , omit ]

(35)

clink (M1 , M2 ), cmusecost (M1 , M2 , Cost ).
[Cost @1 , M1 , M2 , use]

(36)

← resultcm (C , M1 ), resultcm (C , M2 ), M1 < M2 , not clink (M1 , M2 ).

(37)

resultcm (C , M1 ), resultcm (C , M2 ), M1 < M2 , not clink (M1 , M2 ).
[1 @1 , M1 , M2 ]

(38)

Figure 9: CM objective function variations.
Rules (25)–(27) deterministically depend on input facts. Rule (25) counts the number of chains per
annotator, (26) represents the maximum number of chains that any of the annotators created, and (27)
multiplies this number with 6/5. This value serves as an assumption for the maximum number N of
chains in the result and deterministically depends on the given instance. We found that this assumption
can safely be used in practice because annotators are consistent in the number of chains they produce over
the whole document, i.e., annotators either create many chains or few chains relative to other annotators,
but they never create many chains in some part of the document and few chains in other parts of the
same document. (Here, many and few are relative to other annotators.)
In rule (28) we nondeterministically guess which chains of the assumed maximum of N chains actually
exists in the result. Rule (29) performs symmetry breaking on this guess to use a gap-free sequence of
chain IDs starting at 1.
Rules (30) and (31) represent all cmentions that appear in canonical links which are represented in
clink /2. (Note that these are defined in the module in Figure 5.) In rule (32) we guess which cmention is
contained in which result chain. Constraints (33) and (34) ensure that the links represented in clink /2
which were selected by the guess in rule (12) are fully represented by predicate resultcm/2 .
Figure 9 shows objective functions for CM. Weak constraints (35) and (36) for cost components
(C1) and (C2) are the same as (21) and (22) in the MM encoding. Constraints for realizing (C3) are
different because in the CM encoding we have no transitive closure cc/2 at our disposal. Therefore, in
constraint (37) we need to make an explicit join over resultcm/2 to rule out mention-mention links in
the result that have no corresponding link in clink /2. Weak constraints (38) alternatively incur a cost
for such links.
Table 1 shows the combinations of constraints that realize each objective function. Intuitively, we
always incur a cost for not using annotated mention-mention links via (21), in objectives containing V
we additionally incur a cost for using mention-mention links that were not annotated by all annotators
11

Table 1: Objective functions and (weak) constraints that are used to realize them in MM and CM
encodings.
(Weak) constraint
(21) = (35)
(22) = (36)
(23)
(24)
(37)
(38)

[V]
X
X
X

Encoding MM
[U] [VA] [UA]
X

X
X

X

X

X

[V]

Encoding CM
[U] [VA] [UA]

X
X

X

X

X

X
X

X

X

X

X

← resultchain(C ), #count { M : resultcm (C , M ) } ≤ 1 .

(39)

← resultcm (C , mid (S1 , E1 )), resultcm (C , mid (S2 , E2 )),
S1 ≤ S2 , E2 ≤ E1 , (S1 , E1 ) 6= (S2 , E2 ).

(40)

Figure 10: Common structural constraints on adjudication solutions.
via (22). Those mention-mention links that were not annotated at all but appear in the solution
(due to building a transitive closure over links annotated by multiple annotators) we either forbid them
completely via (23) or we incur an additional cost via (24).

4.6

Module for Common Structural Constraints

Figure 10 shows an encoding module for common structural constraints of adjudication solutions.
In most coreference corpora, singleton chains, i.e., chains that contain only a single mention, are not
permitted. For that purpose, constraint (39) enforces that each chain contains at least two mentions.
Moreover, it is linguistically motivated that a mention cannot corefer to another mention that is a
sub-phrase of the former mention. Constraint (40) requires that no chain contains two mentions where
one is contained in the other.

4.7

Semi-automatic Encoding Module

So far we have covered only automatic adjudication. Semi-automatic adjudication is based on enforced
mention and chain information, and on tokens that are enforced to be empty as described in Section 4.1.
Figure 11 contains an encoding module for semi-automatic adjudication which can be used in addition
to the CM or MM encodings and in combination with any of the objective functions. To ensure that
annotations with special annotator ID ‘forced ’ are reproduced in every solution, we first represent several
auxiliary concepts. Rules (41)–(43) represent which tokens contain (en-)forced annotations, rule (44)
represents pairs of canonical mentions that must be part of the same chain, and rule (45) represents
pairs that must be part of different chains. Constraint (46) ensures that no canonical mention starts at
an enforced token if that mention was not enforced, and (47) ensures the same for ends of mentions. Note
that these two constraints and (41) ensure that enforced empty tokens obtain no mention annotations.
Constraint (48) ensures that all enforced mentions exist in the solution as canonical mentions. Finally,
constraint (49) ensures that mentions which should be in the same chain are not in different chains, and
constraint (50) ensures that mentions which should be in distinct chains are not in the same chain.
Adding these rules to encoding MM or CM is sufficient for ensuring that only solutions that reproduce
the user-specified annotations remain as answer sets.

12

forcetok (Token) ← empty(Token).

(41)

forcetok (S ) ← mention(forced , _, S , E ).
forcetok (E ) ← mention(forced , _, S , E ).
forcesame (M1 , M2 ) ← cm(forced , C , Am1 ), cm(forced , C , Am2 ), Am1 6= Am2 , M1 < M2 ,
acmen(forced , Am1 , M1 ), acmen(forced , Am2 , M2 ).
forcediff (M1 , M2 ) ← cm(forced , C1 , Am1 ), cm(forced , C2 , Am2 ), C1 < C2 ,
acmen(forced , Am1 , M1 ), acmen(forced , Am2 , M2 ).

(42)
(43)
(44)
(45)

← forcetok (S ), resultcm (_, mid (S , E )), not mention(forced , _, S , E ).

(46)

← forcetok (E ), resultcm (_, mid (S , E )), not mention(forced , _, S , E ).
← mention(forced , _, S , E ), not resultcm (_, mid (S , E )).

(47)
(48)

← forcesame (M1 , M2 ), resultcm (C1 , M1 ), resultcm (C2 , M2 ), C1 6= C2 .
← forcediff (M1 , M2 ), resultcm (C , M1 ), resultcm (C , M2 ).

(49)
(50)

Figure 11: Program module for semi-automatic mode that allows for enforcing certain mentions and
chains, moreover empty tokens, i.e., tokens without coreference information.

5

Tool and Adjudication Workflow

We have implemented our method in an open source tool called CaspR which is available publicly at
https://github.com/knowlp/caspr-coreference-tool and implements encodings MM (Figures 4, 5,
and 6) and CM (Figures 4, 5, and 8). For both encodings, all four objective functions [U], [UA], [V],
and [VA] (Figures 7 and 9) can be selected. Structural constraints (Figure 10) are activated per default.
Semi-automatic mode (Figure 11) can be activated on the command line.
CaspR reads multiple files in CoNLL format (similar to our examples, potentially with additional
columns), where each file contains annotations from one annotator. After automatic adjudication, a new
CoNLL file is produced that contains either only the resulting annotation or all input annotations and
the adjudication solution in separate columns of a single file for manual inspection. The result column
of this file can be edited in order to enforce mentions or absence thereof, and CaspR can reprocess this
file in semiautomatic mode. CaspR is realized based on Gringo [Geb+11] and Clasp [GKS12] version 5.
Our tool facilitates the following semiautomatic coreference adjudication process.
1. Use CaspR to obtain a consistent adjudication of annotations with optimal usage of given information.
2. Review the resulting CoNLL file in an editor, and enforce coreference information of certain tokens if
they are clearly wrong according to the expertise of the human adjudicator. Coreference information
at a token is enforced by prefixing it with the character ‘=’.
3. Run the re-adjudication mode of CaspR, which creates an optimal adjudication relative to manually
enforced tokens.
4. Iterate the steps (2) and (3) until a satisfactory gold standard result is obtained.
Importantly, step (3) only changes tokens that have not been enforced, hence an incremental workflow,
starting with the most clear-cut cases, and ending with the most difficult cases, can be followed.
The CoNLL data format used in CaspR is variation used by the CorScorer [Pra+14] reference coreference resolution scoring tool. Similar to CorScorer, CaspR expects #begin document and #end document
tags (which have been omitted in figures for brevity), considers the last column to be the coreference
annotation column, and silently copies all other columns into the result.
For our purposes, it was sufficient to use CaspR directly on CoNLL files and to use a text editor as
GUI. To make the tool accessible to a wider part of the community, we consider integrating it into an
existing coreference annotation toolkit, for example into BART [Ver+08].

13

Table 2: Properties of our real-world datasets which are based on the METU-Sabanci Turkish Treebank.
Dataset

DS1 (21 instances)
min

# Annotators
# Chains
# Annotated mentions
# Distinct mentions
Longest chain

6

avg

max

6
6.5
8
78 132.7 197
247 596.6 1289
169 316.7 702
7
33.1
66

DS2 (33 instances)
min

avg

max

9
10.3
11
34
294.6 599
117 1561.4 3897
17
159.8 358
6
28.4
70

Evaluation

We first describe our datasets and then the experimental results.

6.1

Datasets

The datasets that prompted development of this application are based on the METU-Sabanci Turkish
Treebank [Say+04; AOS03; Ofl+03]. Table 2 shows the properties of both datasets. Documents were
annotated in two distinct annotation cycles: for DS1, annotators had to produce mentions and chains,
while for DS2, mentions were given and could be assigned to chains or removed by annotators. This
yielded a large number of distinct mentions, i.e., mentions over all annotators with distinct mention
boundaries for DS1 (on average 316.7 per document), while DS2 contains fewer distinct mentions (159.8)
although it contains by far more annotated mentions (1561.4) than DS1. DS1 is also smaller; it is based
on 21 documents from the corpus while DS2 covers the whole corpus of 33 documents and has more
annotations per document. The average document size is 1634 tokens per document.
In practice we observed the following: due to disagreement on canonical mention boundaries in DS1,
adjudication with [V] or [VA] eliminates most data, hence using [U] or [UA] is more useful. On the
other hand, the ‘voting’ of [V] and [VA] can utilize the larger number of annotations per canonical
mention in DS1, which yields practically very usable results that do not require manual intervention for
creating a gold standard. DS1 and DS2 are structurally quite different: DS1 has several instances where
nearly all mentions are (transitively) connected to all other mentions, while this does not occur in DS2.

6.2

Experiments

Experiments were performed on a computer with 48 GB RAM and two Intel E5-2630 CPUs (total 16 cores) using Debian 8 and at most seven concurrently running jobs, each job using at most
two cores (we did not use tools in multi-threaded mode). As systems, we used Gringo and Clasp
from Clingo 5 (git hash 933fce) [Geb+11; GKS12] and Wasp 2 (git hash ec8857) [Alv+15a]. We use
Clasp with parameter --opt-strategy=usc,9 and Wasp with parameter --enable-disjcores, i.e., both
systems use unsat-core based optimization with stratification and disjoint core preprocessing. We always activate unsat-core based optimization because branch-and-bound (--opt-strategy=bb for Clasp
and --weakconstraints-algorithm=basic for Wasp) yielded timeouts for nearly all instances in preliminary experiments. We enabled disjunctive cores for unsat-core optimization because it slightly increased
performance in preliminary experiments.
Table 3 shows experimental results. We limited memory usage to 5 GB and time usage to 300 sec and
we show results averaged over 5 repeated runs for each configuration. Columns MO, respectively TO,
show the number of runs that aborted because of exceeding the memory limit (memory out), respectively
the time limit (timeout). Columns SAT and OPT show the number of runs that found some solution
and the first optimal solution, respectively, moreover, we show the percentage of runs that found an
optimal solution. Columns T and M give average time and memory usage which was measured with
the runlim tool.4 Columns Tgrd , Opt , Chc, and Cnf show average instantiation time, optimality of the
−LB
), number of choices, and number of conflicts encountered in the solver. To make values
solution ( UBLB
4 http://fmv.jku.at/runlim/

14

Table 3: Experimental results, accumulated over ASP tools, encodings, and objective functions, and
accumulated over eight practically relevant use cases.
Accumulation

MO TO SAT OPT OPT T
# #
#
#
% sec

Clingo
Gringo+Clasp
Gringo+Wasp

20
20
34

0 111
0 111
81
89

CM
MM

4
16

0
0

[U]
[V]
[UA]
[VA]

2
2
8
8

DS1 [U] CM
DS1 [U] MM
DS1 [UA] CM
DS1 [UA] MM
DS2 [V] CM
DS2 [V] MM
DS2 [VA] CM
DS2 [VA] MM

0
2
2
4
0
0
0
2

M Tgrd Opt
MB sec avg

Opt
max

Chc
#

Cnf
#

301
301
228

70 96 738
70 96 695
53 145 1075

5.7
2.7
2.6

87
24

125
176

58 137
82 54

0
0
0
0

38
3
58
12

68
103
42
88

63 125 398 1.8 1.2 15.2
2M 538K
95 24 397 1.8 0.0
0.0 177K 22K
39 177 994 3.5 14.4 368.9 606K 99K
81 58 990 3.5 0.0
0.6 132K 13K

0
0
0
0
0
0
0
0

21
1
19
8
2
0
7
5

567 3.7 6.8 368.9
1M 331K
822 1.6 1.0 84.7 132K
5K

0
0 300 384
18 86 36 806
0
0 282 1474
9
43 136 1206
31 94 35 166
33 100 13 376
26 79 87 506
26 79 64 1034

2.8 5.8 15.2
5M
2M
1.0
0
0
8K 314
8.3 37.1 368.9
1M 338K
1.0 5.9 84.7 458K 38K
1.6 0.0
0.0 465K 69K
1.9
0
0 70K
35
3.7 0.0
0.6 323K 39K
2.0 0.0
0.0 84K 134

comparable, columns Tgrd through Cnf are accumulated only over those 44 instances where Gringo+Clasp
never exceeded memory or time limits.
Overall we performed runs for 3 systems, 2 encodings, 4 objectives, and both datasets (54 instances),
which yields 1296 distinct configurations. We note that memory or time limits (MO and TO) were always
exceeded by the solver, and never by the grounder.
The first section of accumulated results is a comparison of ASP systems, i.e., Clingo, Gringo+Clasp,
and Gringo+Wasp. Wasp clearly has worse performance in this application with respect to memory as
well as time compared with Clasp-based configurations. Columns Tgrd , Opt , Chc, Cnf cannot be obtained
for all runs of Wasp due to timeouts, therefore we omit them in these table rows. Clingo requires more
memory than running Gringo+Clasp in a pipe, moreover, Tgrd of Clingo includes preprocessing time (we
discuss these issues in Section 7.3). In the remaining table we present only results for Gringo+Clasp
because Wasp exceeds the memory and time limit comparatively often.
In the second accumulation section of Table 3, we show a comparison between encodings CM and
MM. Choosing between MM and CM means a trade-off between time and memory: while CM exceeds
the memory limit less often than MM, the latter finds optimal solutions for more runs, and solutions of
CM are further away from the optimum (on average 6.8) in comparison with MM (on average 1.0).
The next section of the table compares objective functions: voting-based objectives ([V] and [VA])
yield more optimal solutions in a shorter time compared with the other objectives ([U] and [UA]), and
even suboptimal solutions of the former objectives are often close to optimal (Opt is 0.0 on average for
the 44 easiest instances). Moreover, strict constraints for transitive links, as used in [U] and [V], require
significantly less memory and instantiation time compared with weak constraints, which are used in [UA]
and [VA] for realizing condition (C3) of Section 3.1.
The last section of the table shows practically relevant scenarios, accumulated over single datasets.
For DS1, non-voting-objectives are practically relevant, while for DS2 the opposite holds. DS2 can be
automatically adjudicated with the MM encoding and objective [V] with all optimal solutions in the
given time and memory. For DS1 the most feasible configuration is [U] with encoding CM: it never
exceeds memory but unfortunately also yields no optimal solutions. In practice, having any solution is
better than running out of memory. Moreover, if we increase resource limits to 8 GB and 1200 sec (not
shown in the table) then we obtain optimal solutions for all documents of DS1 with [U] and MM, and
suboptimal solutions for all documents with [UA] and CM.
15

To analyze instantiation bottlenecks, we have modified Gringo 4.5 to print the number of instantiations
of each non-ground rule.5 For an instance of average difficulty and the UA objective function, the
main instantiation effort of MM encoding is the transitive closure rule (17) with 725K instantiations,
while for CM it is the weak constraint (38) for transitivity with 5M instantiations. These rules clearly
dominate over the next most frequently instantiated rules (12K instances for MM, 112K instances for
CM). Although in encoding CM we obtain significantly more ground rules than in MM, the former
requires less memory. A significant difference between the structures of CM and MM encodings is that
encoding CM is tight [EL03] while encoding MM is not, due to the transitive closure over predicate cc/2
in rules (15)–(17).
Note that to the best of our knowledge there are no other tools for automatic adjudication, and there
are no other published datasets. Therefore we have no possibility for empirically comparing our approach
with other tools or on other datasets.

7

Discussion

We have learned the following lessons in this project.

7.1

Approximation, Modularity, and Declarativity

The abstract task we solve is quite straightforward. However, to make its computation feasible, we need
to resort to approximations (as in assuming a maximum number of chains in the CM encoding), and
we have the possibility to ‘trade time for space’, just as in classical algorithm development (choosing
between the MM and CM encoding is such a trade-off).
Careful tuning of encodings is necessary. For example, replacing constraints (33) and (34) by the
following rule and constraint
clinkgood (M1 , M2 ) ← resultcm (C , M1 ), resultcm (C , M2 ), M1 < M2 .
← clink (M1 , M2 ), not clinkgood (M1 , M2 ).
makes the encoding perform significantly worse.6 The need for such tuning makes ASP less declarative
than we would expect (or want) it to be. Still, the modularity of ASP also facilitates tuning and finding
better formulations: our encodings share many rules although their essential way of representing the
search space is very different.
Note that preliminary encodings [Sch16a] used different objective function formulations, however,
these encodings were not usable in practice without resorting to aggressive approximations that degraded
results, see also Section 7.3.

7.2

ASP Optimization

Unsatisfiable-core-based optimization (USC) [And+12] and stratification [Alv+15b] are both essential to
the applicability of ASP in this application. Obtaining a suboptimal solution is always better than obtaining no solution at all, in particular in semi-automatic adjudication. Branch-and-bound optimization
(BB) performed so much worse than USC in this application that we omitted any numbers.
We also experimented with additional symmetry breaking for the CM encoding, such that solutions
with permutated chain IDs are prevented. With this extension of the encoding, we noticed that USC
performance was reduced, while with BB the frequency of finding better solutions increased (although it
did not increase enough to reach the performance of USC optimization).
Experiments with unsat-core-shrinking of WASP [AD16] have not yielded better results than with
the normal WASP configuration. Similarly, experiments with lazy instantiation of constraints [Sch16b;
Cut+17] have not yielded performance improvements.
5 https://github.com/peschue/clingo/tree/grounder-stats
6 Due

to symmetry breaking (‘<’) in (13) and (14), this encoding alternative is correct.

16

7.3

Instantiation Issues

Analyzing the number of rules instantiated by non-ground rules can be useful, but it can also be misleading: in this application the encoding instantiating more constraints (CM) requires less memory in
search (probably because of the tightness of CM).
Another practical issue is, that measuring instantiation time with Clingo is impossible, as Clingo
reports only the sum of preprocessing and instantiation times. This makes comparisons with other
systems difficult, hence we opted to compare mainly with Gringo+Clasp.
A small surprising observation is that Clingo consistently requires slightly more memory than
Gringo+Clasp.

8

Related Work

Our tool is the first automatic tool for coreference adjudication. Adjudication is usually performed
manually on a small number of annotations per document and it is usually performed using graphical
interactive tools such as BART [Ver+08], BRAT [Ste+12], or GATE [Gai+96; Cun+13].
Our work on automatic adjudication is enabled by the number of annotations we collected for each
document, which is larger than in usual coreference annotation projects (we collected at least eight
annotations per document) and thus permits automatic adjudication under the assumption that the
majority of annotators provides correct annotations.
The computational problem of finding minimal repairs for inconsistent annotations is related to
finding minimal repairs for databases [CM05] or ontologies [EFS14], and to managing inconsistency in
multi-context systems [Eit+14]. In these problems, the aim is to find a minimal change in a system such
that the modified system is globally consistent, which is similar to our problem of merging mutually
inconsistent coreference annotations into a single consistent gold standard result. All these problems
have in common, that a change that fixes one inconsistency might introduce another one, potentially in
a part of the system that is not obviously related to the changed part.
Scoring coreference annotations based on existing and non-existing mention-mention links (as we do
in the [V] and [VA] objectives) is related to the BLANC [RH10] evaluation measure for coreference
analysis. Scoring only based on existing mention-mention links (as in [U] and [UA] objectives) is related
to the MUC [Vil+95] evaluation measure, which scores precision and recall of mention-mention links over
all gold chains compared with all predicted chains. In adjudication, we produce one set of gold chains
from many other gold chains, while these scores are defined for comparing pairwise scores between two
sets of chains (one set of predicted chains and one set of gold standard chains).
ASP encodings for transitivity are present in many applications. In particular, ASP encodings for
acyclicity properties have been studied by Gebser, Janhunen, and Rintanen [GJR15], who included
transitive closure in several of their encodings. Similar as in our experiments, tightness makes a relevant
difference.
While coreference resolution is different from coreference adjudication, methods related with Answer
Set Programming have been used to perform coreference resolution. Denis and Baldridge [DB09] described an approach for coreference resolution and named entity classification based on Integer Linear
Programming, which includes transitivity of mention-mention links. Inoue et al. [Ino+12] created an approach for coreference resolution based on weighted abduction that is evaluated using an Integer Linear
Programming formulation. Note that Integer Linear Programming is a formalism that is related to ASP
[LJN12]. Mitra and Baral [MB16] describe an approach for question answering based on Inductive Logic
Programming under ASP semantics, which includes coreference resolution as a subtask.
More remotely related approaches for coreference resolution include mostly methods for building
coreference chains from scores on mention-mention links obtained from some machine learning solution
on a labeled coreference corpus. Such methods include local greedy heuristics [BR08; SE12], global optimization formulations such as relaxation labeling [SPT12] or ranking with Markov Logic [CWM07], and
representations of trees of mention-mention links [FSM12; CSR13]. Rule-based algorithms for anaphora
resolution were first described by Hobbs [Hob78], more recent systems merge chains in a multi-stage
filtering approach [Lee+13]. Hybrid systems combine rules and machine learning and use curated or distributed knowledge sources such as WordNet, Google distance, and Wikipedia [Poe+04; CN12; Zhe+13].
Most of these systems must be trained on a gold standard corpus that is the outcome of adjudication

17

and all of these systems are evaluated on such gold standard corpora.

9

Conclusion

We have developed an ASP application for automatic adjudication of coreference annotations along with
two structurally different real-world benchmark datasets.
As our work is the first automatic adjudication approach, we could not compare with systems performing the same or a similar task. Moreover, there are no standard datasets published about the
problem, because usually only the final result of adjudication — the gold standard — is published.
To solve the automatic adjudication problem for all practically relevant instances that we encountered,
significant effort and several iterations of encoding improvement were necessary. We have the impression
that ASP tools do not yet provide sufficient feedback about problems in encodings to make the process
of encoding optimization an easy task.
Still, for our datasets, we consider this computational problem as solved, and we have integrated our
encodings in the publicly available CaspR tool that supports automatic and semiautomatic adjudication
of coreference data in CoNLL-format.

Future Work
Future work related to ASP can be the development of automatic methods for encoding optimization,
similar to initial work by Buddenhagen and Lierler [BL15]. To be useful, such methods need to be
integrated into tools, in the best case into grounders and solvers that directly give hints how to improve
an encoding.
A future topic of research on coreference resolution and adjudication can be partially or largely
overlapping mentions that are not annotated on exactly the same boundaries. This issue, in particular,
arises with agglutinating languages such as Turkish where splitting long words into several tokens and
annotating parts of a token can sometimes be desired. Currently, in our approach, as well as in common
coreference scoring schemes, overlapping and non-overlapping mentions are treated equally as if they are
completely distinct mentions.

Acknowledgements
We are grateful for the feedback of reviewers at the RCRA workshop, at the LPNMR conference, and at
the Journal of Experimental & Theoretical Artificial Intelligence.

Funding
This work has been supported by The Scientific and Technological Research Council of Turkey
(TUBITAK) under grant agreements 114E430 and 114E777.

References
[AD16]

Mario Alviano and Carmine Dodaro. “Anytime answer set optimization via unsatisfiable
core shrinking”. In: Theory and Practice of Logic Programming 16.5–6 (2016), pp. 533–551.

[Alv+15a]

Mario Alviano et al. “Advances in WASP”. In: International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR). 2015, pp. 40–54.

[Alv+15b] Mario Alviano et al. “Optimum stable model search: algorithms and implementation”. In:
Journal of Logic and Computation (2015).
[And+12]

Benjamin Andres et al. “Unsatisfiability-based optimization in clasp”. In: International Conference on Logic Programming (ICLP), Technical Communications. 2012, pp. 212–221.

[AOS03]

Nart B Atalay, Kemal Oflazer, and Bilge Say. “The Annotation Process in the Turkish
Treebank”. In: International Workshop on Linguistically Interpreted Corpora (LINC). 2003.

18

[Bar04]

Chitta Baral. Knowledge Representation, Reasoning, and Declarative Problem Solving. Cambridge University Press, 2004, 530 pages.

[BET11]

Gerhard Brewka, Thomas Eiter, and Miroslaw Truszczynski. “Answer set programming at
a glance”. In: Communications of the ACM 54.12 (2011).

[BL15]

Matt Buddenhagen and Yuliya Lierler. “Performance Tuning in Constraint Programming”.
In: International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR). 2015, pp. 186–198.

[BR08]

Eric Bengtson and Dan Roth. “Understanding the value of features for coreference resolution”. In: Empirical Methods in Natural Language Processing (EMNLP). 2008, pp. 294–
303.

[Cal+12]

Francesco Calimeri et al. ASP-Core-2 Input Language Format. Tech. rep. ASP Standardization Working Group, 2012. url: https : / / www . mat . unical . it / aspcomp2013 /
ASPStandardization.

[Car+04]

C Cardie et al. “Low-Level Annotations and Summary Representations of Opinions for
Multiperspective QA.” In: New Directions in Question Answering. 2004, pp. 87–98.

[CG08]

Jonathan H Clark and José P González-Brenes. “Coreference Resolution: Current Trends
and Future Directions”. In: Language and Statistics II Literature Review (2008).

[Cho02]

Noam Chomsky. Syntactic Structures. Walter de Gruyter, 2002.

[CM05]

Jan Chomicki and Jerzy Marcinkowski. “Minimal-change integrity maintenance using tuple
deletions”. In: Information and Computation 197.1 (2005), pp. 90–121.

[CN12]

Chen Chen and Vincent Ng. “Combining the Best of Two Worlds: A Hybrid Approach to
Multilingual Coreference Resolution”. In: Empirical Methods in Natural Language Processing
and Computational Natural Language Learning, Shared Task. 2012, pp. 56–63.

[CSR13]

Kai-Wei Chang, Rajhans Samdani, and Dan Roth. “A Constrained Latent Variable Model for
Coreference Resolution”. In: Empirical Methods in Natural Language Processing (EMNLP).
2013, pp. 601–612.

[Cun+13]

Hamish Cunningham et al. “Getting more out of biomedical documents with GATE’s full
lifecycle open source text analytics.” In: PLoS computational biology 9.2 (2013), e1002854.

[Cut+17]

Bernardo Cuteri et al. “Constraints, Lazy Constraints, or Propagators in ASP Solving: An
Empirical Analysis”. In: Theory and Practice of Logic Programming 17.5–6 (2017), pp. 780–
799.

[CWM07]

Aron Culotta, Michael Wick, and Andrew Mccallum. “First-Order Probabilistic Models for
Coreference Resolution”. In: Conference of the North American Chapter of the Association
for Computational Linguistics: Human Language Technologies. 2007, pp. 81–88.

[DB09]

Pascal Denis and Jason Baldridge. “Global joint models for coreference resolution and named
entity classification”. In: Procesamiento del Lenguaje Natural 42 (2009), pp. 87–96.

[EFS14]

Thomas Eiter, Michael Fink, and Daria Stepanova. “Towards Practical Deletion Repair of Inconsistent DL-programs”. In: European Conference on Artificial Intelligence. 2014, pp. 285–
290.

[Eit+14]

Thomas Eiter et al. “Finding Explanations of Inconsistency in Multi-Context Systems”. In:
Artificial Intelligence 216 (2014), pp. 233–274.

[EL03]

Esra Erdem and Vladimir Lifschitz. “Tight logic programs”. In: Theory and Practice of Logic
Programming 3.4-5 (2003), pp. 499–518.

[FPL11]

Wolfgang Faber, Gerald Pfeifer, and Nicola Leone. “Semantics and complexity of recursive
aggregates in answer set programming”. In: Artificial Intelligence 175.1 (2011), pp. 278–298.

[FSM12]

Eraldo Rezende Fernandes, Cícero Nogueira dos Santos, and Ruy Luiz Milidiú. “Latent
structure perceptron with feature induction for unrestricted coreference resolution”. In: Joint
Conference on EMNLP and CoNLL: Shared Task. 2012, pp. 41–48.

19

[Gai+96]

R. Gaizauskas et al. “GATE: an environment to support research and development in natural language engineering”. In: International Conference on Tools with Artificial Intelligence
(ICTAI). 1996, pp. 58–66.

[Geb+11]

Martin Gebser et al. “Advances in gringo series 3”. In: International Conference on Logic
Programming and Non-monotonic Reasoning (LPNMR). 2011, pp. 345–351.

[Geb+12]

Martin Gebser et al. Answer Set Solving in Practice. Morgan Claypool, 2012.

[GJR15]

Martin Gebser, Tomi Janhunen, and Jussi Rintanen. “ASP Encodings of Acyclicity Properties”. In: Journal of Logic and Computation exv063 (2015).

[GK14]

Michael Gelfond and Yulia Kahl. Knowledge Representation, Reasoning, and the Design of
Intelligent Agents: The Answer-Set Programming Approach. Cambridge University Press,
2014.

[GKS12]

Martin Gebser, Benjamin Kaufmann, and Torsten Schaub. “Conflict-driven answer set solving: From theory to practice”. In: Artificial Intelligence 187-188 (2012), pp. 52–89.

[GL88]

Michael Gelfond and Vladimir Lifschitz. “The Stable Model Semantics for Logic Programming”. In: International Conference and Symposium on Logic Programming. 1988, pp. 1070–
1080.

[Hir81]

Graeme Hirst. Anaphora in Natural Language Understanding: A Survey. Springer-Verlag,
1981.

[Hob78]

Jerry R Hobbs. “Resolving Pronoun References”. In: Lingua 44.4 (1978), pp. 311–338.

[Ino+12]

Naoya Inoue et al. “Coreference Resolution with ILP-based Weighted Abduction”. In: International Conference on Computational Linguistics (COLING). 2012, pp. 1291–1308.

[Keh+08]

Andrew Kehler et al. “Coherence and Coreference Revisited.” In: Journal of Semantics 25.1
(2008), pp. 1–44.

[Lee+13]

Heeyoung Lee et al. “Deterministic Coreference Resolution Based on Entity-Centric,
Precision-Ranked Rules”. In: Computational Linguistics 39.4 (2013), pp. 885–916.

[Lif08]

Vladimir Lifschitz. “What Is Answer Set Programming?” In: AAAI Conference on Artificial
Intelligence. 2008, pp. 1594–1597.

[LJN12]

Guohua Liu, Tomi Janhunen, and I Niemelä. “Answer set programming via mixed integer programming”. In: Principles of Knowledge Representation and Reasoning (KR). 2012,
pp. 32–42.

[MB16]

Arindam Mitra and Chitta Baral. “Addressing a Question Answering Challenge by Combining Statistical Methods with Inductive Rule Learning and Reasoning”. In: AAAI Conference
on Artificial Intelligence. 2016.

[Mit99]

Ruslan Mitkov. Anaphora Resolution: the State of the Art. School of Languages and European Studies, University of Wolverhampton, 1999, pp. 1–34.

[Mue04]

Erik T. Mueller. “Understanding script-based stories using commonsense reasoning”. In:
Cognitive Systems Research 5.4 (2004), pp. 307–340.

[Ng10]

Vincent Ng. “Supervised Noun Phrase Coreference Research: The First Fifteen Years”. In:
Association for Computational Linguistics (ACL). 2010, pp. 1396–1411.

[Ofl+03]

Kemal Oflazer et al. “Building a Turkish Treebank”. In: Treebanks, Building and Using
Parsed Corpora. Springer Netherlands, 2003, pp. 261–277.

[Pas04]

Rebecca J. Passonneau. “Computing reliability for coreference annotation”. In: Language
Resources and Evaluation (LREC). 2004, pp. 1503–1506.

[Poe+04]

Massimo Poesio et al. “Learning to resolve bridging references”. In: Annual Meeting on
Association for Computational Linguistics. Paper #143. 2004.

[Pra+07]

Sameer S. Pradhan et al. “Unrestricted Coreference: Identifying Entities and Events in
OntoNotes”. In: International Conference on Semantic Computing (ICSC). 2007, pp. 446–
453.

20

[Pra+14]

Sameer S. Pradhan et al. “Scoring Coreference Partitions of Predicted Mentions: A Reference Implementation”. In: Annual Meeting of the Association for Computational Linguistics
(ACL). 2014, pp. 30–35.

[RH10]

Marta Recasens and Eduard Hovy. “BLANC: Implementing the Rand Index for Coreference
Evaluation”. In: Natural Language Engineering 17.4 (2010), pp. 485–510.

[Say+04]

Bilge Say et al. “Development of a Corpus and a Treebank for Present day Written Turkish”. In: Current Research in Turkish Linguistics (Proceedings of the Eleventh International
Conference of Turkish Linguistics, 2002). 2004, pp. 182–192.

[Sch+17]

Peter Schüller et al. Marmara Turkish Coreference Corpus and Coreference Resolution Baseline. Tech. rep. Marmara University, 2017. arXiv: 1706.01863.

[Sch16a]

Peter Schüller. “Adjudication of Coreference Annotations via Finding Optimal Repairs of
Equivalence Relations”. In: International Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion (RCRA). 2016, pp. 57–71.

[Sch16b]

Peter Schüller. “Modeling Variations of First-Order Horn Abduction in Answer Set Programming”. In: Fundamenta Informaticae 149.1-2 (2016), pp. 159–207.

[Sch17]

Peter Schüller. “Adjudication of Coreference Annotations via Answer Set Optimization”. In:
International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR).
2017, pp. 343–357.

[Sch18]

Peter Schüller. “Adjudication of Coreference Annotations via Answer Set Optimization”. In:
Journal of Experimental & Theoretical Artificial Intelligence (2018). In press.

[SE12]

Veselin Stoyanov and Jason Eisner. “Easy-first Coreference Resolution”. In: International
Conference on Computational Linguistics (COLING). 2012, pp. 2519–2534.

[SPT08]

Emili Sapena, Lluís Padró, and Jordi Turmo. Coreference Resolution. Tech. rep. Barcelona,
Spain: TALP Research Center, Universitat Politècnica de Catalunya, 2008.

[SPT12]

Emili Sapena, Lluis Padro, and Jordi Turmo. “A Constraint-Based Hypergraph Partitioning
Approach to Coreference Resolution”. In: Computational Linguistics 39.4 (2012), pp. 847–
884.

[Ste+12]

Pontus Stenetorp et al. “Brat: a Web-based Tool for NLP-Assisted Text Annotation”. In:
European Chapter of the Association for Computational Linguistics (EACL). 2012, pp. 102–
107.

[Tug14]

Don Tuggener. “Coreference Resolution Evaluation for Higher Level Applications”. In: European Chapter of the Association for Computational Linguistics (EACL). 2014, pp. 231–
235.

[Ver+08]

Yannick Versley et al. “BART: A Modular Toolkit for Coreference Resolution”. In: Proceedings of the ACL-08: HLT Demo Session. 2008, pp. 9–12.

[Vil+95]

Marc Vilain et al. “A Model-Theoretic Coreference Scoring Scheme”. In: Message Understanding Conference (MUC). 1995, pp. 45–52.

[WKR10]

R Witte, Ninus Khamis, and Juergen Rilling. “Flexible Ontology Population from Text: The
OwlExporter”. In: International Conference on Language Resources and Evaluation (LREC).
2010, pp. 3845–3850.

[Zhe+13]

Jiaping Zheng et al. “Dynamic Knowledge-Base Alignment for Coreference Resolution”. In:
Computational Natural Language Learning (CoNLL). 2013, pp. 153–162.

21

