#  Technical Report:
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
<EMAIL_ADDRESS>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].

###### 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+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).
(2)

Roman superscripts denote mention IDs, chains in this text are as follows:
$\\{(i)$, $(\mathit{iii})$, $(\mathit{ix})$, $(x)\\}$ (John, He, my, John);
$\\{(\mathit{iv}),\mathit{(vi)},\mathit{(vii)}\\}$ (a new song, the song, It);
and $\\{(v),\mathit{(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, [Car+04] use it for complex opinion
extraction, [Mue04] uses it for script-based story understanding, [WKR10]
perform reasoning on coreference chains to create OWL Ontologies from texts,
and [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_
,111https://bitbucket.org/knowlp/asp-coreference-benchmark 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+15] 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 tool222https://github.com/knowlp/caspr-coreference-
tool 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.

######  Definition 2.1.

A _document_ $D$ is a sequence of tokens $w_{1},\ldots,w_{n}$ with indexes
$1,\ldots,n$. A _mention_ is a pair $(s,e)$ of indexes,
$1\,{\leq}\,s\,{\leq}\,e\,{\leq}\,n$, pointing to start index $s$ and end
index $e$ in $D$, such that the sequence $w_{s}w_{s+1}\cdots w_{e}$ is a
natural language expression that refers to a discourse entity [Cho02].
_Mention detection_ is the task of finding the set
$M\,{=}\,\\{(s_{1},e_{1}),\ldots,(s_{m},e_{m})\\}$ of all mentions in a
document.

######  Example 2.

In Example 1 the document (2) 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 (2), 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^{\prime}$ are
overlapping, either $m$ is properly contained in $m^{\prime}$ 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 $(\mathit{i})$/$(\mathit{ii})$ and
$(\mathit{vii})$/$(\mathit{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 $\mathcal{C}$ and $\mathcal{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_
$\mathcal{T}$ is recursively defined, it is the smallest set containing
$\mathbb{N}\,{\cup}\,\mathcal{C}\,{\cup}\,\mathcal{X}$ as well as
uninterpreted function terms of form $f(t_{1},\ldots,t_{n})$ where
$f\,{\in}\,\mathcal{C}$ and $t_{1},\ldots,t_{n}\,{\in}\,\mathcal{T}$. An
_ordinary atom_ is of the form $p(t_{1},\dots,t_{n})$, where
$p\,{\in}\,\mathcal{C}$, $t_{1},\dots,t_{n}\,{\in}\,\mathcal{T}$, and $n\geq
0$ is the _arity_ of the atom. An _aggregate atom_ is of the form
$X\,{=}\,\\#\mathit{agg}\\{\ t\,{:}\,b_{1},\ldots,b_{k}\ \\}$ with variable
$X\,{\in}\,\mathcal{X}$, aggregation function
$\\#\mathit{agg}\,{\in}\,\\{\\#\mathit{max},\\#\mathit{count}\\}$, with
$1\,{<}\,k$, $t\,{\in}\,\mathcal{T}$ and $b_{1},\ldots,b_{k}$ 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

$\alpha_{1}\,{\lor}\,\cdots\,{\lor}\,\alpha_{k}\leftarrow\beta_{1},\dots,\beta_{n},\mathbf{not}\,\,\beta_{n\,{+}\,1},\dots,\mathbf{not}\,\,\beta_{m}$
(3)

where $0\,{\leq}\,k$, $0\,{\leq}\,n\,{\leq}\,m$, each head element
$\alpha_{i}$, $0\,{\leq}\,i\,{\leq}\,k$, is an ordinary atom, and each head
element $\beta_{j}$, $0\,{\leq}\,j\,{\leq}\,m$, is an atom. A rule $r$ is a
constraint, if $k\,{=}\,0$, and a _fact_ if $k\,{=}\,1$ and $m\,{=}\,0$.

A weak constraint is of form

${\reflectbox{$\leadsto$}}\,\beta_{1},\dots,\beta_{n},\mathbf{not}\,\,\beta_{n\,{+}\,1},\dots,\mathbf{not}\,\,\beta_{m}.\
[w@1,t_{1},\ldots,t_{l}]$ (4)

where $0\,{\leq}\,n\,{\leq}\,m$, $0\,{\leq}\,l$, $w\in\mathbb{Z}$,
$\beta_{j}$, $0\,{\leq}\,j\,{\leq}\,m$, is an atom, and $t_{i}$,
$0\,{\leq}\,i\,{\leq}\,l$, is a term. (Note that $@1$ determines the ‘level’
of the weak constraint which we do not use.)

We denote by $H(r)=\\{\alpha_{1},\ldots,\alpha_{k}\\}$ the head of a rule $r$.
We denote by $B^{+}(r)=\\{\beta_{1},\dots,\beta_{n}\\}$ the positive body, by
$B^{-}(r)=\\{\beta_{n\,{+}\,1},\dots,\beta_{m}\\}$ the negative body, and by
$B(r)=\\{\beta_{1},\dots,\beta_{n},\mathbf{not}\,\ \beta_{n\,{+}\,1},\dots$,
$\mathbf{not}\,\ \beta_{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 $\mathit{H\\!B}_{P}$ and its ground instantiation $\mathit{grnd}(P)$.
Given an interpretation $I\,{\subseteq}\,\mathit{H\\!B}_{P}$, an atom $a$ is
true wrt. $I$ iff $a\,{\in}\,I$ and an aggregate atom
$X\,{=}\,\\#\mathit{agg}\\{\ t\,{:}\,b_{1},\ldots,b_{k}\ \\}$ is true wrt. $I$
iff $X\,{=}\,f_{\mathit{\\#agg}}(\\{\
\sigma(t)\mid\sigma(b_{1})\,{\in}\,I,\ldots,\sigma(b_{k})\,{\in}\,I\ \\})$
where $\sigma$ is a substitution from variables $\mathcal{X}$ to nonground
terms in $\mathcal{T}$, $f_{\mathit{\\#max}}(X)=\max(X)$ and
$f_{\mathit{\\#count}}(X)=|X|$. The body of a rule or weak constraint is
satisfied wrt. $I$ iff all $a\,{\in}\,B^{+}(r)$ are true wrt. $I$ and no
$a\,{\in}\,B^{-}(r)$ is true wrt. $I$. A rule $r$ is satisfied wrt. $I$ iff
$H(r)\,{\cap}\,I\,{=}\,\emptyset$ 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] $fP^{I}$ reduces a program $P$ using an answer set
candidate $I$: $fP^{I}=\\{r\in\mathit{grnd}(P)\mid B(r)\text{ is satisfied
wrt.\ }I\\}$. An interpretation $I$ is an _answer set_ of $P$ iff $I$ is a
$\subseteq$-minimal model of $fP^{I}$.

Let $W(I)$ be the set of ground weak constraints $r\,{\in}\,P$ that are not
satisfied wrt. $I$. Then the set $C(I)\,{=}\,\\{(w,t_{1},\ldots,t_{k})\mid
r\in W(I)\\}$ is the set of all tuples of weak constraints of form (4) 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(\vec{x}):q(\vec{x})\ \\}\ ub$ where lower bound $lb$ and
upper bound $ub$ are natural numbers and can also be omitted (then,
$lb\,{=}\,0$ and $ub\,{=}\,\infty$), and $\vec{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(\vec{x})\,{\lor}\,\hat{p}(\vec{x})$ for all $q(\vec{x})$, and into a
constraint which enforces that at least $lb$ and at most $ub$ atoms
$p(\vec{x})$ are true whenever the rule body is true. For example, the rule
$1\ \\{p(a);p(b)\\}\ 2\leftarrow 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\,{\geq}\,2$ sets of mentions $M_{1},\ldots,M_{u}$ over a document $D$
and corresponding chains $P_{1},\ldots,P_{u}$ of the respective sets of
mentions, the _coreference adjudication problem_ is to find the set of
mentions $\hat{M}$ and the set of chains $\hat{P}$ (with $\hat{P}$ a partition
of $\hat{M}$) such that $\hat{P}$ and $\hat{M}$ observe structural constraints
described in Section 2, and that resulting chains $\hat{P}$ correspond best
with the given chains $P_{1},\ldots,P_{u}$.

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 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 $\mathit{\\{(i),(ii),(x)\\}}$ (John, a
musician, John). If we merge this chain with the chain
$\mathit{\\{(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
$\mathit{\\{(i),(ii),(iii),(ix),(x)\\}}$ (John, a musician, He, my, John)
although no annotator indicated that the mentions $\mathit{(ii)}$ and
$\mathit{(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)$. ∎

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

(a) in1.conll

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

(b) in2.conll

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

(c) in3.conll

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

(d) in4.conll

Figure 1: Minimalistic example CoNLL input files containing two columns: token
index (first column) and coreference chains (second column).

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 $P_{1},\ldots,P_{u}$ and the solution
chain $\hat{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.

  1. (C1)

Not using a link provided by an annotator in the solution.

  2. (C2)

Using a link provided by an annotator where a number of other annotators did
not provide the same link.

  3. (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:

  * U[V]

Cost 2 for (C1), cost 1 for (C2), and (C3) is a hard constraint (infinite
cost).

  * U[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.

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

(a) [U]

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

(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.

######  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) 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).

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

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

1 (2 (3 (1(2) (2 =(1 2 (3) - - (4) (2) 3 2) 3) 1) 2) =1) 4 (3) - (2) - (2) 5 -
(3) - (2) - 6 (2) - (1) (4) =(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 ‘=’.

######  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. ∎

##  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$,
$\mathit{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 $P_{1},\ldots,P_{u}$
which are partitions of sets of mentions $M_{1},\ldots,M_{u}$ over $D$. We
associate unique IDs $1,\ldots,u$ with annotations. For each annotation
$P_{a}$, $1\,{\leq}\,a\,{\leq}\,u$ we have a set of chains
$P_{a}=\\{C_{1},\ldots,C_{k}\\}$ and we associate unique IDs $1,\ldots,k$ with
these chains. The corresponding mentions are
$M_{a}=\\{(s_{1},e_{1}),\ldots,(s_{m},e_{m})\\}$ and we associate unique IDs
$1,\ldots,m$ with the mentions in $M_{a}$. (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
$\mathit{mention(a,j,s_{j},e_{j})}$ for each mention $(s_{j},e_{j})$ with ID
$j$ in the annotation with ID $a$. Moreover, we create facts of the form
$\mathit{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 $a_{1}$ created the chain $c_{1}\,{=}\,\\{m_{1},m_{2},m_{3}\\}$
containing mentions $m_{1}\,{=}\,(1,1)$ ‘John’, $m_{2}\,{=}\,(3,4)$ ‘a
musician’, and $m_{3}\,{=}\,(6,6)$ ‘He’. Annotator $a_{2}$ created the chain
$c_{2}\,{=}\,\\{m_{4},m_{5}\\}$ containing mentions $m_{4}\,{=}\,(12,13)$ ‘a
girl’ and $m_{5}\,{=}\,(30,30)$ ‘her’. These annotations are represented in
ASP as follows:

$\displaystyle\mathit{mention(a_{1},m_{1},1,1).}$
$\displaystyle\mathit{mention(a_{1},m_{2},3,4).}$
$\displaystyle\mathit{mention(a_{1},m_{3},6,6).}$
$\displaystyle\mathit{cm(a_{1},c_{1},m_{1}).}$
$\displaystyle\mathit{cm(a_{1},c_{1},m_{2}).}$
$\displaystyle\mathit{cm(a_{1},c_{1},m_{3}).}$
$\displaystyle\mathit{mention(a_{2},m_{4},12,13).}$
$\displaystyle\mathit{mention(a_{2},m_{5},30,30).}$
$\displaystyle\mathit{cm(a_{2},c_{2},m_{4}).}$
$\displaystyle\mathit{cm(a_{2},c_{2},m_{5}).}$

where we use constants $a_{1},a_{2},c_{1},c_{2},m_{1},\ldots,m_{5}$ 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
$\mathit{result_{cm}(C,mid(S,E))}$, which indicates that in chain $\mathit{C}$
there is a mention that is a span from start token $\mathit{S}$ to end token
$\mathit{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:

$\displaystyle\mathit{result_{cm}(v,mid(1,1))}$
$\displaystyle\mathit{result_{cm}(v,mid(6,6))}$
$\displaystyle\mathit{result_{cm}(w,mid(12,13))}$
$\displaystyle\mathit{result_{cm}(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
‘$\mathit{forced}$’. A token $\mathit{Token}$ without any mention boundary is
represented as a fact of form $\mathit{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.

$\displaystyle\mathit{mention(forced,m_{1},1,3)\,{\leftarrow}\,.}$
$\displaystyle\mathit{mention(forced,m_{2},6,6)\,{\leftarrow}\,.}$
$\displaystyle\mathit{cm(forced,c_{1},m_{1})\,{\leftarrow}\,.}$
$\displaystyle\mathit{cm(forced,c_{1},m_{2})\,{\leftarrow}\,.}$

where the chain is represented by constant $c_{1}$ and the mentions by $m_{1}$
and $m_{2}$. ∎

We next describe our encodings.

$\displaystyle\mathit{na(N)}$
$\displaystyle\,{\leftarrow}\,\mathit{N\,{=}\,\\#count\,\\{\,A\,{:}\,mention(A,\\_,\\_,\\_)\,\\}.}$
(5) $\displaystyle\mathit{acmen(A,Am,mid(S,E))}$
$\displaystyle\,{\leftarrow}\,\mathit{mention(A,Am,S,E).}$ (6)
$\displaystyle\mathit{asamechain(A,Am_{1},Am_{2})}$
$\displaystyle\,{\leftarrow}\,\mathit{cm(A,C,Am_{1}),\,cm(A,C,Am_{2}),\,Am_{1}\,{\neq}\,Am_{2}.}$
(7) $\displaystyle\mathit{csamechain(M_{1},M_{2})}$
$\displaystyle\,{\leftarrow}\,\mathit{acmen(A,Am_{1},M_{1}),\,acmen(A,Am_{2},M_{2}),}$
$\displaystyle\hphantom{\,{\leftarrow}\,}\mathit{asamechain(A,Am_{1},Am_{2}),\,M_{1}\,{<}\,M_{2}.}$
(8) $\displaystyle\mathit{evidence(M_{1},M_{2},Ev)}$
$\displaystyle\,{\leftarrow}\,\mathit{csamechain(M_{1},M_{2}),\,Ev\,{=}\,\\#count\,\\{}$
$\displaystyle\hphantom{\,{\leftarrow}\,}\
\mathit{A\,{:}\,asamechain(A,Am_{1},Am_{2}),\,Am_{1}\,{<}\,Am_{2},}$
$\displaystyle\hphantom{\,{\leftarrow}\,}\
\mathit{\hphantom{F\,{:}\,}acmen(A,Am_{1},M_{1}),\,acmen(A,Am_{2},M_{2})}$
$\displaystyle\hphantom{\,{\leftarrow}\,}\mathit{\\},\,Ev\,{>}\,0}.$ (9)
$\displaystyle\mathit{cmomitcost(M_{1},M_{2},2\,{\cdot}\,K)}$
$\displaystyle\,{\leftarrow}\,\mathit{csamechain(M_{1},M_{2}),\,evidence(M_{1},M_{2},K).}$
(10) $\displaystyle\mathit{cmusecost(M_{1},M_{2},N\,{-}\,K)}$
$\displaystyle\,{\leftarrow}\,\mathit{csamechain(M_{1},M_{2}),\,evidence(M_{1},M_{2},K),}$
$\displaystyle\hphantom{\,{\leftarrow}\,}\mathit{N\,{-}\,K\,{>}\,0,\,na(N).}$
(11) Figure 4: Common deterministic definitions used in objective function
constraints.

###  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 (5) represents the number of annotations in the input in predicate
$\mathit{na}/1$. This number is used for relating the weight of one
annotator’s input compared with all annotators. Rule (6) defines predicate
$\mathit{acmen}/3$ which relates annotated mentions with their canonical
representation in a term of the form $\mathit{mid(S,E)}$ where $S$ and $E$ are
the starting and ending token of the mention in the document, respectively.
Rule (7) represents in atoms of the form
$\mathit{asamechain}(A,\mathit{Am}_{1},\mathit{Am}_{2})$ all pairs of distinct
mentions $\mathit{Am}_{1}$ and $\mathit{Am}_{2}$ that were put into the same
chain by annotator $A$. Rule (8) represents the same pairs of mentions but
projects away annotator information and relates pairs of cmentions in atoms of
the form $\mathit{csamechain}(M_{1},M_{2})$.

Based on $\mathit{csamechain}$ and $\mathit{asamechain}$, rule (9) represents
for each pair of canonical mentions $(M_{1},M_{2})$ the number of annotators
who put $M_{1}$ and $M_{2}$ into the same chain. This value is represented
only if it is above zero. Rule (10) 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 (11) defines cost
component (C2) which is a cost of 1 for each annotator who did not put both
canonical mentions $M_{1}$ and $M_{2}$ into the same chain, while at least one
other annotator did so.

$\displaystyle\mathit{link(A,Am_{1},Am_{2})}$
$\displaystyle\,{\leftarrow}\,\mathit{cm(A,C,Am_{1}),\,cm(A,C,Am_{2}),\,Am_{1}\,{<}\,Am_{2}.}$
(12) $\displaystyle\mathit{\\{\,uselink(A,Am_{1},Am_{2})\,\\}}$
$\displaystyle\,{\leftarrow}\,\mathit{link(A,Am_{1},Am_{2}).}$ (13)
$\displaystyle\mathit{clink(M_{1},M_{2})}$
$\displaystyle\,{\leftarrow}\,\mathit{uselink(A,Am_{1},Am_{2}),\,M_{1}\,{<}\,M_{2},}$
$\displaystyle\hphantom{\,{\leftarrow}\,}\mathit{acmen(A,Am_{1},M_{1}),\,mention(A,Am_{,}M_{2}).}$
(14) $\displaystyle\mathit{clink(M_{1},M_{2})}$
$\displaystyle\,{\leftarrow}\,\mathit{uselink(A,Am_{2},Am_{1}),\,M_{1}\,{<}\,M_{2},}$
$\displaystyle\hphantom{\,{\leftarrow}\,}\mathit{acmen(A,Am_{1},M_{1}),\,mention(A,Am_{2},M_{2}).}$
(15) Figure 5: Common link selection and canonicalization encoding.

###  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 mention-mention links are represented
canonically in predicate $\mathit{clink}/2$.

In detail, Rule (12) represents annotated mention-mention links in predicate
$\mathit{link}/3$, and rule (13) is a guess whether to use each of these
links. Used links are represented as cmentions in rules (14) and (15), i.e.,
their annotator information is projected away.333This projection requires two
rules because mention and cmention IDs can have different lexicographic order.
Note that these rules make use of deterministically defined predicate
$\mathit{acmen}/3$ from the common program module given in Figure 4.

$\displaystyle\mathit{cc(M_{1},M_{2})}$
$\displaystyle\,{\leftarrow}\,\mathit{clink(M_{1},M_{2}).}$ (16)
$\displaystyle\mathit{cc(M_{2},M_{1})}$
$\displaystyle\,{\leftarrow}\,\mathit{cc(M_{1},M_{2}).}$ (17)
$\displaystyle\mathit{cc(M_{1},M_{3})}$
$\displaystyle\,{\leftarrow}\,\mathit{cc(M_{1},M_{2}),\,cc(M_{2},M_{3}).}$
(18) $\displaystyle\mathit{notrepresentative(M_{2})}$
$\displaystyle\,{\leftarrow}\,\mathit{cc(M_{1},M_{2}),\,M_{1}\,{<}\,M_{2}.}$
(19) $\displaystyle\mathit{result_{cm}(M_{1},M_{2})}$
$\displaystyle\,{\leftarrow}\,\mathit{cc(M_{1},M_{2}),\,\mathbf{not}\,notrepresentative(M_{1}).}$
(20) $\displaystyle\mathit{resultchain(C)}$
$\displaystyle\,{\leftarrow}\,\mathit{result_{cm}(C,\\_).}$ (21) Figure 6: MM
encoding.
$\displaystyle\,{\reflectbox{$\leadsto$}}\,\mathbf{not}\,\mathit{clink(M_{1},M_{2}),cmomitcost(M_{1},M_{2},Cost).}$
$\displaystyle\mathit{[Cost@1,M_{1},M_{2},omit]}$ (22)
$\displaystyle\,{\reflectbox{$\leadsto$}}\,\mathit{clink(M_{1},M_{2}),cmusecost(M_{1},M_{2},Cost).}$
$\displaystyle\mathit{[Cost@1,M_{1},M_{2},use]}$ (23)
$\displaystyle\,{\leftarrow}\,\mathit{cc(M_{1},M_{2}),M_{1}\,{<}\,M_{2},\mathbf{not}\,clink(M_{1},M_{2}).}$
(24)
$\displaystyle\,{\reflectbox{$\leadsto$}}\,\mathit{cc(M_{1},M_{2}),M_{1}\,{<}\,M_{2},\mathbf{not}\,clink(M_{1},M_{2}).}$
$\displaystyle\mathit{[1@1,M_{1},M_{2}]}$ (25) Figure 7: MM objective function
variations.

###  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 (16)–(18) represent the
reflexive, symmetric, and transitive closure of predicate $\mathit{clink/2}$
in predicate $\mathit{cc/2}$. This represents result chains in an explicit
equivalence relation over cmentions: each strongly connected component (SCC)
of predicate $\mathit{cc/2}$ is equivalent to a coreference chain. Rule (19)
defines which elements of the equivalence relation is not the
lexicographically smallest element in the SCC, and rule (20) defines result
chains by using the smallest cmention in each SCC as a representative for the
corresponding chain. Rule (21) defines that these cmentions represent chains.

Figure 7 shows constraints for realizing objective functions for the MM
encoding. Weak constraint (22) incurs a cost for non-existing links in atoms
of form $\mathit{clink}(M_{1},M_{2})$, corresponding to cost (C1) in Section
3.1. Similarly, (23) incurs cost for existing links, corresponding to (C2).
Finally, corresponding to (C3), constraint (24) strictly forbids to put two
mentions into a chain if there is no evidence for that from annotators, and
weak constraint (25) alternatively incurs a cost for such mention pairs.
Recall that predicates $\mathit{cmomitcost}/3$ and $\mathit{cmusecost}/3$ are
defined deterministically from input facts (see Section 4.2 and Figure 4),
therefore weak constraints (22) and (23) contain only one body literal after
intelligent instantiation.

$\displaystyle\begin{aligned}
\mathit{countchain(A,N)}&\,{\leftarrow}\,\mathit{cm(A,\\_,\\_),}\\\
&\hphantom{\,{\leftarrow}\,}\mathit{N\,{=}\,\\#count\,\\{\,C\,{:}\,cm(A,C,\\_)\,\\}.}\\\
\mathit{maxchain(N)}&\,{\leftarrow}\,\mathit{N\,{=}\,\\#max\,\\{\,C\,{:}\,countchain(\\_,C)\,\\}.}\\\
\mathit{chainlimit(6/5\,{\cdot}\,N)}&\,{\leftarrow}\,\mathit{maxchain(N).}\\\
\mathit{\\{\,resultchain(C)\ {:}\
C\,{\in}\,\\{1,\ldots,N\\}\,\\}\,}&\,{\leftarrow}\,\mathit{chainlimit(N).}\\\
\mathit{resultchain(C_{2})}&\,{\leftarrow}\,\mathit{resultchain(C_{1}),\,C_{2}\,{\in}\,\\{1,\ldots,C_{2}\,{-}\,1\\}.}\\\
\mathit{cmention(M)}&\,{\leftarrow}\,\mathit{clink(M,\\_).}\\\
\mathit{cmention(M)}&\,{\leftarrow}\,\mathit{clink(\\_,M).}\\\
\mathit{1\,\\{\,result_{cm}(C,M)\ {:}\
resultchain(C)\,\\}}\,1&\,{\leftarrow}\,\mathit{cmention(M).}\end{aligned}$
$\displaystyle\begin{aligned}
&\,{\leftarrow}\,\mathit{clink(M_{1},M_{2}),\,result_{cm}(C,M_{1}),\,\mathbf{not}\,result_{cm}(C,M_{2}).}&\\\
&\,{\leftarrow}\,\mathit{clink(M_{1},M_{2}),\,\mathbf{not}\,result_{cm}(C,M_{1}),\,result_{cm}(C,M_{2}).}&\end{aligned}$
(26) Figure 8: CM encoding.

###  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 $\mathit{resultcm/2}$
instead of deriving it from predicate $\mathit{clink/2}$.

Rules (8)–(8) deterministically depend on input facts. Rule (8) counts the
number of chains per annotator, (8) represents the maximum number of chains
that any of the annotators created, and (8) 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 (8) we nondeterministically guess which chains of the assumed maximum
of $N$ chains actually exists in the result. Rule (8) performs symmetry
breaking on this guess to use a gap-free sequence of chain IDs starting at 1.

Rules (8) and (8) represent all cmentions that appear in canonical links which
are represented in $\mathit{clink}/2$. (Note that these are defined in the
module in Figure 5.) In rule (8) we guess which cmention is contained in which
result chain. Constraints (LABEL:eqCMSync1) and (LABEL:eqCMSync2) ensure that
the links represented in $\mathit{clink/2}$ which were selected by the guess
in rule (13) are fully represented by predicate $\mathit{resultcm/2}$.

$\leadsto$

$\mathbf{not}$$\mathit{clink(M_{1},M_{2}),cmomitcost(M_{1},M_{2},Cost).}$
$\mathit{[Cost@1,M_{1},M_{2},omit]}$ (27)

$\leadsto$

$\mathit{clink(M_{1},M_{2}),cmusecost(M_{1},M_{2},Cost).}$
$\mathit{[Cost@1,M_{1},M_{2},use]}$ (28)
$\displaystyle\,{\leftarrow}\,\mathit{result_{cm}(C,M_{1}),\,result_{cm}(C,M_{2}),\,M_{1}\,{<}\,M_{2},\,\mathbf{not}\,clink(M_{1},M_{2}).}$
(29)
$\displaystyle\,{\reflectbox{$\leadsto$}}\,\mathit{result_{cm}(C,M_{1}),\,result_{cm}(C,M_{2}),\,M_{1}\,{<}\,M_{2},\,\mathbf{not}\,clink(M_{1},M_{2}).}$
$\mathit{[1@1,M_{1},M_{2}]}$ (30) Figure 9: CM objective function variations.

Figure 9 shows objective functions for CM. Weak constraints (27) and (28) for
cost components (C1) and (C2) are the same as (22) and (23) in the MM
encoding. Constraints for realizing (C3) are different because in the CM
encoding we have no transitive closure $\mathit{cc}/2$ at our disposal.
Therefore, in constraint (29) we need to make an explicit join over
$\mathit{resultcm}/2$ to rule out mention-mention links in the result that
have no corresponding link in $\mathit{clink}/2$. Weak constraints (30)
alternatively incur a cost for such links.

Table 1: Objective functions and (weak) constraints that are used to realize them in MM and CM encodings. | Encoding MM | Encoding CM
---|---|---
(Weak) constraint | [V] | [U] | [VA] |  [UA] | [V] | [U] | [VA] | [UA]
(22) = (27) | X | X | X | X | X | X | X | X
(23) = (28) | X |  | X |  | X |  | X |
(24) | X | X |  |  |  |  |  |
(25) |  |  | X | X |  |  |  |
(29) |  |  |  |  | X | X |  |
(30) |  |  |  |  |  |  | X | X

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 (22), in objectives containing V we additionally incur a
cost for using mention-mention links that were not annotated by all annotators
via (23). 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 (24) or
we incur an additional cost via (25).

###  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 (31)
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 (32)
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.

$\displaystyle\,{\leftarrow}\,\mathit{resultchain(C),\,\\#count\,\\{\,M\,{:}\,result_{cm}(C,M)\,\\}\,{\leq}\,1.}$
(31)
$\displaystyle\,{\leftarrow}\,\mathit{result_{cm}(C,mid(S_{1},E_{1})),\,result_{cm}(C,mid(S_{2},E_{2})),}$
$\displaystyle\hphantom{\,{\leftarrow}\,}\mathit{S_{1}\,{\leq}\,S_{2},\,E_{2}\,{\leq}\,E_{1},\,(S_{1},E_{1})\,{\neq}\,(S_{2},E_{2}).}$
(32) Figure 10: Common structural constraints on adjudication solutions.
$\displaystyle\begin{aligned}
\mathit{force_{\mathit{tok}}(Token)}&\,{\leftarrow}\,\mathit{empty(Token).}\\\
\mathit{force_{\mathit{tok}}(S)}&\,{\leftarrow}\,\mathit{mention(forced,\\_,S,E).}\\\
\mathit{force_{\mathit{tok}}(E)}&\,{\leftarrow}\,\mathit{mention(forced,\\_,S,E).}\\\
\mathit{force_{\mathit{same}}(M_{1},M_{2})}&\,{\leftarrow}\,\mathit{cm(forced,C,Am_{1}),\,cm(forced,C,Am_{2}),\,Am_{1}\,{\neq}\,Am_{2},\,M_{1}\,{<}\,M_{2},}\\\
&\hphantom{\,{\leftarrow}\,}\mathit{acmen(forced,Am_{1},M_{1}),\,acmen(forced,Am_{2},M_{2}).}\\\
\mathit{force_{\mathit{diff}}(M_{1},M_{2})}&\,{\leftarrow}\,\mathit{cm(forced,C_{1},Am_{1}),\,cm(forced,C_{2},Am_{2}),\,C_{1}\,{<}\,C_{2},}\\\
&\hphantom{\,{\leftarrow}\,}\mathit{acmen(forced,Am_{1},M_{1}),\,acmen(forced,Am_{2},M_{2}).}\end{aligned}$
$\displaystyle\begin{aligned}
&\,{\leftarrow}\,\mathit{force_{\mathit{tok}}(S),\,result_{cm}(\\_,mid(S,E)),\,\mathbf{not}\,\,mention(forced,\\_,S,E).}\\\
&\,{\leftarrow}\,\mathit{force_{\mathit{tok}}(E),\,result_{cm}(\\_,mid(S,E)),\,\mathbf{not}\,\,mention(forced,\\_,S,E).}\\\
&\,{\leftarrow}\,\mathit{mention(forced,\\_,S,E),\,\mathbf{not}\,\
result_{cm}(\\_,mid(S,E)).}\\\
&\,{\leftarrow}\,\mathit{force_{\mathit{same}}(M_{1},M_{2}),\,result_{cm}(C_{1},M_{1}),\,result_{cm}(C_{2},M_{2}),\,C_{1}\,{\neq}\,C_{2}.}\\\
&\,{\leftarrow}\,\mathit{force_{\mathit{diff}}(M_{1},M_{2}),\,result_{cm}(C,M_{1}),\,result_{cm}(C,M_{2}).}\end{aligned}$
(33) 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.

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 ‘$\mathit{forced}$’ are reproduced in every solution, we first represent
several auxiliary concepts. Rules (11)–(11) represent which tokens contain
(en-)forced annotations, rule (11) represents pairs of canonical mentions that
must be part of the same chain, and rule (11) represents pairs that must be
part of different chains. Constraint (33) ensures that no canonical mention
starts at an enforced token if that mention was not enforced, and (33) ensures
the same for ends of mentions. Note that these two constraints and (11) ensure
that enforced empty tokens obtain no mention annotations.

Constraint (33) ensures that all enforced mentions exist in the solution as
canonical mentions. Finally, constraint (33) ensures that mentions which
should be in the same chain are not in different chains, and constraint (33)
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.

##  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. 1.

Use CaspR to obtain a consistent adjudication of annotations with optimal
usage of given information.

  2. 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. 3.

Run the re-adjudication mode of CaspR, which creates an optimal adjudication
relative to manually enforced tokens.

  4. 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].

##  6 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.

Table 2: Properties of our real-world datasets which are based on the METU-Sabanci Turkish Treebank. Dataset | DS1 (21 instances) | DS2 (33 instances)
---|---|---
| min | avg | max | min | avg | max
# Annotators | 6 | 6.5 | 8 | 9 | 10.3 | 11
# Chains | 78 | 132.7 | 197 | 34 | 294.6 | 599
# Annotated mentions | 247 | 596.6 | 1289 | 117 | 1561.4 | 3897
# Distinct mentions | 169 | 316.7 | 702 | 17 | 159.8 | 358
Longest chain | 7 | 33.1 | 66 | 6 | 28.4 | 70

###  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+15]. 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.444http://fmv.jku.at/runlim/ Columns $T_{\mathit{grd}}$, $\mathit{Opt}$,
$\mathit{Chc}$, and $\mathit{Cnf}$ show average instantiation time, optimality
of the solution ($\frac{\mathit{UB}{-}\mathit{LB}}{\mathit{LB}}$), number of
choices, and number of conflicts encountered in the solver. To make values
comparable, columns $T_{\mathit{grd}}$ through $\mathit{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.

Table 3: Experimental results, accumulated over ASP tools, encodings, and objective functions, and accumulated over eight practically relevant use cases. |  |  | MO | TO | SAT | OPT | OPT | $T$ | $M$ | $T_{\mathit{grd}}$ | $\mathit{Opt}$ | $\mathit{Opt}$ | $\mathit{Chc}$ | $\mathit{Cnf}$
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---
Accumulation | # | # | # | # | % | sec | MB | sec | avg | max | # | #
Clingo | 20 | 0 | 111 | 301 | 70 | 96 | 738 | 5.7 |  |  |  |
Gringo+Clasp | 20 | 0 | 111 | 301 | 70 | 96 | 695 | 2.7 |  |  |  |
Gringo+Wasp | 34 | 81 | 89 | 228 | 53 | 145 | 1075 | 2.6 |  |  |  |
CM | 4 | 0 | 87 | 125 | 58 | 137 | 567 | 3.7 | 6.8 | 368.9 | 1M | 331K
MM | 16 | 0 | 24 | 176 | 82 | 54 | 822 | 1.6 | 1.0 | 84.7 | 132K | 5K
[U] | 2 | 0 | 38 | 68 | 63 | 125 | 398 | 1.8 | 1.2 | 15.2 | 2M | 538K
[V] | 2 | 0 | 3 | 103 | 95 | 24 | 397 | 1.8 | 0.0 | 0.0 | 177K | 22K
[UA] | 8 | 0 | 58 | 42 | 39 | 177 | 994 | 3.5 | 14.4 | 368.9 | 606K | 99K
[VA] | 8 | 0 | 12 | 88 | 81 | 58 | 990 | 3.5 | 0.0 | 0.6 | 132K | 13K
DS1 | [U] | CM | 0 | 0 | 21 | 0 | 0 | 300 | 384 | 2.8 | 5.8 | 15.2 | 5M | 2M
DS1 | [U] | MM | 2 | 0 | 1 | 18 | 86 | 36 | 806 | 1.0 | 0 | 0 | 8K | 314
DS1 | [UA] | CM | 2 | 0 | 19 | 0 | 0 | 282 | 1474 | 8.3 | 37.1 | 368.9 | 1M | 338K
DS1 | [UA] | MM | 4 | 0 | 8 | 9 | 43 | 136 | 1206 | 1.0 | 5.9 | 84.7 | 458K | 38K
DS2 | [V] | CM | 0 | 0 | 2 | 31 | 94 | 35 | 166 | 1.6 | 0.0 | 0.0 | 465K | 69K
DS2 | [V] | MM | 0 | 0 | 0 | 33 | 100 | 13 | 376 | 1.9 | 0 | 0 | 70K | 35
DS2 | [VA] | CM | 0 | 0 | 7 | 26 | 79 | 87 | 506 | 3.7 | 0.0 | 0.6 | 323K | 39K
DS2 | [VA] | MM | 2 | 0 | 5 | 26 | 79 | 64 | 1034 | 2.0 | 0.0 | 0.0 | 84K | 134

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 $T_{\mathit{grd}}$,
$\mathit{Opt}$, $\mathit{Chc}$, $\mathit{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,
$T_{\mathit{grd}}$ 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 ($\mathit{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.

To analyze instantiation bottlenecks, we have modified Gringo 4.5 to print the
number of instantiations of each non-ground
rule.555https://github.com/peschue/clingo/tree/grounder-stats For an instance
of average difficulty and the UA objective function, the main instantiation
effort of MM encoding is the transitive closure rule (18) with 725K
instantiations, while for CM it is the weak constraint (30) 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
$\mathit{cc}/2$ in rules (16)–(18).

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
(LABEL:eqCMSync1) and (LABEL:eqCMSync2) by the following rule and constraint

$\displaystyle\mathit{clink_{good}}(M_{1},M_{2})$
$\displaystyle\,{\leftarrow}\,\mathit{result_{cm}(C,M_{1}),\,result_{cm}(C,M_{2})},\,M_{1}\,{<}\,M_{2}.$
$\displaystyle\,{\leftarrow}\,\mathit{clink(M_{1},M_{2}),\,\mathbf{not}\,\
clink_{good}(M_{1},M_{2})}.$

makes the encoding perform significantly worse.666Due to symmetry breaking
(‘$<$’) in (14) and (15), this encoding alternative is correct. 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 [Sch16] 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+15a] 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 [Sch16a, Cut+17] have not yielded
performance improvements.

###  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
[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. [DB09] described an approach for coreference
resolution and named entity classification based on Integer Linear
Programming, which includes transitivity of mention-mention links. [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].
[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 [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 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 [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+15] Mario Alviano, Carmine Dodaro, Nicola Leone and Francesco Ricca  “Advances in WASP”  In _International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR)_ , 2015, pp. 40–54
  * [Alv+15a] Mario Alviano, Carmine Dodaro, Joao Marques-Silva and Francesco Ricca  “Optimum stable model search: algorithms and implementation”  In _Journal of Logic and Computation_ , 2015
  * [And+12] Benjamin Andres, Benjamin Kaufmann, Oliver Matheis and Torsten Schaub  “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
  * [Bar04] Chitta Baral  “Knowledge Representation, Reasoning, and Declarative Problem Solving”  Cambridge University Press, 2004, pp. 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”, 2012  URL: https://www.mat.unical.it/aspcomp2013/ASPStandardization
  * [Car+04] C Cardie, J Wiebe, T Wilson and D Litman  “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, Valentin Tablan, Angus Roberts and Kalina Bontcheva  “Getting more out of biomedical documents with GATE’s full lifecycle open source text analytics.”  In _PLoS computational biology_ 9.2, 2013, pp. e1002854
  * [Cut+17] Bernardo Cuteri, Carmine Dodaro, Francesco Ricca and Peter Schüller  “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, Michael Fink, Peter Schüller and Antonius Weinzierl  “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 Elsevier B.V., 2011, pp. 278–298
  * [FSM12] Eraldo Rezende Fernandes, Cícero Nogueira 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
  * [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, Roland Kaminski, Arne König and Torsten Schaub  “Advances in gringo series 3”  In _International Conference on Logic Programming and Non-monotonic Reasoning (LPNMR)_ , 2011, pp. 345–351
  * [Geb+12] Martin Gebser, Roland Kaminski, Benjamin Kaufmann and Torsten Schaub  “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_ , 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, Ekaterina Ovchinnikova, Kentaro Inui and Jerry Hobbs  “Coreference Resolution with ILP-based Weighted Abduction”  In _International Conference on Computational Linguistics (COLING)_ , 2012, pp. 1291–1308
  * [Keh+08] Andrew Kehler, Laura Kertz, Hannah Rohde and Jeffrey L Elman  “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 LanguagesEuropean 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, Bilge Say, Dilek Zeynep Hakkani-Tür and Gökhan Tür  “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, Rahul Mehta, Axel Maroudas and Janet Hitzeman  “Learning to resolve bridging references” Paper #143  In _Annual Meeting on Association for Computational Linguistics_ , 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
  * [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, Deniz Zeyrek, Kemal Oflazer and Umut Özge  “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”, 2017  arXiv:1706.01863
  * [Sch16] 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
  * [Sch16a] 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 press  In _Journal of Experimental & Theoretical Artificial Intelligence_ Taylor & Francis Online, 2018
  * [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”, 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