Adjudication of Coreference Annotations via Finding Optimal Repairs of Equivalence Relations ? Peter Schüller Computer Engineering Department Faculty of Engineering Marmara University, Turkey peter.schuller@marmara.edu.tr Abstract. We describe encodings for merging multiple coreference annotations into a single annotation, subject to hard constraints (consistency) and optimiza- tion criteria (minimal divergence from annotators) using Answer Set Program- ming (ASP). This task requires guessing an equivalence relation with a large number of elements. We report on experiments with real-world instances based on the METU-Sabanci Turkish Treebank using the ASP tools Gringo, Clasp, and Wasp. We also describe a patch for Gringo which facilitates fine-grained instan- tiation analysis and use it to analyze experimental results. Keywords: Coreference Resolution, Adjudication, Answer Set Programming 1 Introduction Coreference Resolution [9, 14, 20, 21] is the task of finding phrases in a text that refer to the same 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. For example [22] 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) . Roman superscripts denote mention IDs. This text contains the following chains: {(i), (iii ), (ix ), (x)} (John, He, my, John); {(iv ), (vi ), (vii )} (a new song, the song, It); and {(v), (xi )} (A girl, her), where numbers refer to mention IDs.1 For supervised learning and verification of coreference resolution methods, anno- tated corpora are an important resource. For creating such resources, we usually give ? This work has been supported by Scientific and Technological Research Council of Turkey (TUBITAK) Grant 114E430. 1 Mention (viii) is in a predicative relationship with (vii). Per convention such mentions are not considered coreferent, hence (viii) is missing in the second chain. 57 P.Schüller Adjudication of coreference annotations the same document to several annotators who produce mention and chain annotations independently. Afterwards we enter a process of manually adjudicating these—often conflicting—annotations to produce a single gold standard. Annotations in coreference resolution are 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, men- tions, and chains in the same document. Merging such annotations is a tedious task, and the final decision on the gold standard is done based on the adjudicators’ expert opinion, however tool support for this task would be useful. We here present a method for automatic merging of coreference annotations based on combinatorial optimization, where the result combines the information provided by all annotators while performing minimal corrective modifications to ensure consistency of the output. Our method is based on ASP optimization and provides various parame- ters for defining which corrective modifications to prefer. We here focus on the experimental evaluation of two encodings for this task which use different underlying representations for the equivalence relation: – an encoding representing a transitive closure of mention-mention links, scoring repairs based on the closure, and deriving a mention-chain representation from the closure; and – another encoding which directly represents mention-chain links and scores repairs based on pairs of mention-chain links. We compare the Clasp [19] and Wasp [2] solver tools with branch-and-bound as well as with unsatisfiable-core optimization modes on both encodings and several objective function variations. Moreover we describe a patch to the Gringo [18] instantiation tool that allows us to shed more light on the reasons for performance of encoding variants by obtaining a detailed analysis of instantiation of nonground rules. In the following we provide preliminaries on Coreference Resolution and Answer Set Programming in Section 2, describe our approach for automatic adjudication in Section 3, provide ASP encodings in Section 4, discuss experimental evaluation and instantiation analysis with Gringo in Section 5, and conclude with related and future work in Section 6. 2 Preliminaries We next introduce coreference resolution informally and mathematically, and then give a brief introduction of Answer Set Programming. 2.1 Coreference Resolution Coreference resolution is the task of finding phrases in a text that refer to the same entity [9, 14, 20, 21, 26, 33]. We call such phrases mentions, and we call a group of mentions that refers to one entity chains. In formal mathematical terms, we can describe mention detection and coreference resolution as follows. Given a document D which is sequence of tokens w1 , . . . , wn , mention detection is the task of finding a set M = {(f1 , t1 ), . . . , (fm , tm )} of mentions, 58 P.Schüller Adjudication of coreference annotations i.e., pairs (fi , ti ) of indexes, 1 ≤ i ≤ m, into the sequence of tokens (1 ≤ fi ≤ ti ≤ n). Given a set M of mentions, coreference resolution is the task of partitioning M into k (disjoint) partitions (chains) P such that all sequences of tokens wfi , . . . , wti corre- sponding to mention (fi , ti ) in one chain refer to the same entity. Example 1 (Introduction example continued). We have 31 tokens (including punctu- ation). Some of the tokens are w1 = ‘John’, w2 = ‘is’, . . . , w30 = ‘her’, w31 = ‘.’, the set of mentions is M = {(1, 1), (3, 4), (6, 6), . . ., (30, 30)} and the correct coreference partitions are P = {{(1, 1), (6, 6), (23, 23), (27, 27)}, . . . , {(12, 13), (30, 30)}} where, (12, 13) represents ‘A girl’ and (30, 30) represents ‘her’. t u 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 ac- cording to most measures of coreference optimality [31]. In coreference annotation, humans create both mentions and chains, so the problem becomes more involved and automatic methods for creating consistent result annotations are helpful. 2.2 Answer Set Programming Answer Set Programming (ASP) is a logic programming paradigm which is suitable for knowledge representation and finding solutions for computationally (NP-)hard prob- lems [5, 6, 17, 23]. An ASP program consists of rules of the form Head ← Body. where Head is either a first-order atom or a choice construction, and Body is a conjunc- tion of first-order atoms. Intuitively, a rule makes the head logically true if the body is satisfied. Rules without body are facts (the head is always true) and rules without head are constraints (if the body is satisfied, the candidate solution is discarded). Choices of the form L {A1 ; . . . ; An } U generate all solution candidates where between L and U atoms from the set {A1 , . . . , An } are true. In addition to combinatorial search, by using weak constraints of the form ;Body. [Cost@Tuple] we can perform combinatorial optimization: a weak constraint incurs cost Cost for each unique tuple Tuple such that Body is satisfied in the answer set with respect to that tuple. For details of syntax and semantics we refer to the ASP-Core-2 standard [7]. Effi- cient solvers are available for computing answer sets, in this work we use the Gringo 4.5.0 [18] grounder and experiment with the Clasp 3.1.2 [19] and Wasp 2.0 [2] solvers. 3 Automatic Coreference Adjudication We first describe the problem more formally and give an example of inconsistent an- notations, then we describe how we approach the problem and its input and output in 59 P.Schüller Adjudication of coreference annotations ASP. Finally we provide and describe two logic programs that use different internal representations. Mathematically, we can describe adjudication of multiple coreference resolution annotations as follows. Given a document D of tokens as described in Section 2.1, and u ≥ 2 partitions P1 , . . . , Pu of mentions (where each partition can be based on a different un- derlying set of mentions) we need to create a single set of mentions M and a single partition P which groups the set M into chains. Clearly, annotations might be contradictory and we need to ensure certain structural constraints in the solution. For example mention A cannot be coreferent with mention B if A includes B. Moreover, a solution might contain equivalences between mentions that are not present in any annotation. This is because chains are equivalence relations, and if we merge equivalence relations that are not subsets of each other, the new equiva- lence relation is the reflexive, symmetric, and transitive closure of the original relations. Example 2 (continued). Assume that in parallel to chain {(i ), (iii ), (ix ), (x )} in the In- troduction, we obtain (from another annotator) a chain {(i ), (ii ), (x )} If we merge these chains naively by merging the sets, we obtain a single chain {(i ), (ii ), (iii ), (ix ), (x )} although no annotator indicated that (ii ) and (iii ) belong to the same chain. t u Therefore we need to merge chains in a more intelligent way. 3.1 Merge Representation and Merge Preferences We want to use as much information from annotations as possible, while keeping con- sistency of the solution. We achieve this by attaching a cost to ignored mentions, to ignored links between mentions, and to links that were not annotated but arise due to merged chains. Our conceptual model for merging annotations from multiple sources is as follows. – A subset of annotated chain-mention links is selected from all annotators. – From the resulting chains, each chain is represented as a set of links between all mentions it contains (i.e., as a symmetric, transitive relation). – A subset of these links is selected to build the combined result. – The transitive, and reflexive closure of these selected links is created, which pro- vides an equivalence relation over mentions of all annotators. – We use this equivalence relation as new set of chains. – We ensure the solution adheres to two constraints: no mention can be a part of itself, and each chain must contain more than one mention. We search for the choice of chain-mention and mention-mention links that opti- mizes an objective function. As objective functions we incur a cost of – costm (M ) for each ignored mention M in a chain; – costl (M , M 0 ) for each ignored link between mentions M and M 0 ; and – costa (M , M 0 ) for each link between mentions M and M 0 that is present in the result equivalence relation but not part of any annotation. In Section 4.3 we provide concrete preference configurations of these functions. 60 P.Schüller Adjudication of coreference annotations 3.2 Input and Output ASP Representation Given u partitions P1 , . . . , Pu where each chain C ∈ Pi contains a set of mentions of form (from, to) we create facts of form mention(A, M , Fr , To) where A represents the partition (i.e., which annotator created the annotation), M is a unique identifier for each mention, and (Fr , To) represents the mention. Moreover we create facts of form cm(A, Chain, M ) for each mention with identifier M that is in a chain with identifier Chain according to annotator A. Example 3 (continued). Given the text from our running example, we can mark tokens (including punctuation) with integers as follows. John1 is2 a3 musician4 .5 He6 played7 a8 new9 song10 .11 Consider that annotator a1 created chain {‘John’a , ‘a musician’b , ‘He’c } while an- notator a2 produced {‘musician’d , ‘He’e } where superscripts indicate mention IDs. These annotations would be represented by the following ASP facts. mention(a1 , a, 1 , 1 ) ← . cm(a1 , c1 , a) ← . mention(a1 , b, 3 , 4 ) ← . cm(a1 , c1 , b) ← . mention(a1 , c, 6 , 6 ) ← . cm(a1 , c1 , c) ← . mention(a2 , d , 4 , 4 ) ← . cm(a2 , c2 , d ) ← . mention(a2 , e, 6 , 6 ) ← . cm(a2 , c2 , e) ← . where c1 and c2 represent the first and second chain, respectively. t u The output of our logic program will be a set of chains without annotator informa- tion. Therefore we want to obtain atoms of the form resultcm (Chain, mid (Fr , To)) which indicate that in chain Chain there is a mention from token F r to token T o. Example 4 (continued). Assume we have merged the annotations of the previous ex- ample into two chains v = {‘John’, ‘a musician’} and w = {‘musician’, ‘He’}, this would be represented by the following atoms: resultcm (v, mid (1, 1)) resultcm (v, mid (3, 4)) resultcm (w, mid (4, 4)) resultcm (w, mid (6, 6)) Note that it is frequently the case that mentions contain other mentions, but this is usually forbidden in case these mentions belong to the same chain. t u 4 ASP Encodings We next provide two ASP encodings that realize the above merging strategy. The first encoding explicitly represents the transitive closure of mention-mention links, while the second encoding avoids such a representation by representing the resulting equiva- lence relation only as chain-mention links. We use functions cost X for configuring the preference relation; these are part of the encoding and resolved during instantiation. 61 P.Schüller Adjudication of coreference annotations { usecm (A, Chain, M ) : cm(A, Chain, M ) } ← . (1) ; cm(A, C , M ), not usecm (A, C , M ). [costm (M )@1 , A, C , M , cm] (2) link (A, M1 , M2 ) ← usecm (A, C , M1 ), usecm (A, C , M2 ), M1 < M2 . (3) { uselink (A, M1 , M2 ) } ← link (A, M1 , M2 ). (4) ; link (A, M1 , M2 ), not uselink (A, M1 , M2 ). [costl (M1 , M2 )@1 , A, M1 , M2 , mm] (5) clink (X , Y ) ← X = mid (Fr1 , To1 ), Y = mid (Fr2 , To2 ), X < Y , uselink (A, M1 , M2 ), mention(A, M1 , Fr1 , To1 ), mention(A, M2 , Fr2 , To2 ). (6) clink (X , Y ) ← X = mid (Fr1 , To1 ), Y = mid (Fr2 , To2 ), X < Y , uselink (A, M2 , M1 ), mention(A, M1 , Fr1 , To1 ), mention(A, M2 , Fr2 , To2 ). (7) clink → (X , Y ) ← clink (X , Y ). (8) → → clink (X , Y ) ← clink (Y , X ). (9) clink → (X , Z ) ← clink → (X , Y ), clink → (Y , Z ). (10) ; clink → (X , Y ), X < Y , not clink (X , Y ). [cost a (X, Y )@1, X, Y, add] (11) not repr (Y ) ← clink → (X, Y ), X < Y. (12) → resultc,m (X , Y ) ← clink (X , Y ), not notrepr (X ). (13) resultc (C ) ← resultc,m (C , _). (14) ← resultc (C ), #count { Y : resultc,m (C , Y ) } ≤ 1 . (15) ← clink (mid (F1 , T1 ), mid (F2 , T2 )),F1 ≤ F2 , T2 ≤ T1 ,(F1 , T1 ) 6= (F2 , T2 ). (16) Fig. 1. Encoding variant MM (full). 4.1 Mention-Mention Encoding (MM) Figure 1 shows encoding MM. Rule (1) guesses which subset of mention-chain anno- tations from all annotators is used, while the weak constraint (2) incurs cost costm (M ) for each mention-chain annotation that is not present in the solution. Each pair of dis- tinct mentions in the same chain induces a link between these mentions (3), rules (4) guess a subset of these links to be used in the result, and the weak constraint (5) in- curs a cost costl (M, M 0 ) for each link that is not present in the solution. Note that we canonicalize the symmetric link relation using the < operator based on link IDs. Rules (6) and (7) project away annotator information and use new constant terms of form mid (Fr , To) to identify links between mentions using just start and end tokens Fr and To, respectively.2 The relation clink (·, ·) is a full canonical representation of all mentions and mention-mention links in a candidate solution. Rules (8)–(10) define in clink → the symmetric, reflexive, and transitive closure of the clink relation. This closure represents an equivalence relation between mentions, i.e., the result chains, and is the distinguishing feature of the MM encoding. 2 Both rules are required because IDs of mentions could be sorted differently from their occur- rence in the text. 62 P.Schüller Adjudication of coreference annotations ann(A) ← cm(A, _, _). (17) count_chain(A, N ) ← ann(A), N = #count { C : cm(A, C , _) }. (18) maxchain(N ∗ 3 /2 ) ← N = #max { C : count_chain(_, C ) }. (19) { resultc (X ) : X = 1 ..Max } ← maxhain(Max ). (20) resultc (X −1 ) ← resultc (X ), 1 < X . (21) cmention(M ) ← clink (M , _). (22) cmention(M ) ← clink (_, M ). (23) 1 { resultcm (C , M ) : resultc (C ) } 1 ← cmention(M ). (24) ← clink (X , Y ), resultcm (C , X ), not resultcm (C , Y ). (25) ← clink (X , Y ), not resultcm (C , X ), resultcm (C , Y ). (26) ; resultcm (C , X ), resultcm (C , Y ), X < Y , not clink (X , Y ). [cost a (X, Y )@1, X, Y, add] (27) Fig. 2. ASP rules for encoding variation CM which replaces rules (8)–(11). Based on clink → , weak constraint (11) incurs cost cost a (M, M 0 ) for all pairs of mentions that are present in the result equivalence relation but not in any mention- mention link obtained from annotators (clink ). The equivalence relation clink → is transformed back into a chain-mention represen- tation in (13) and (14) by using the lexicographically smallest mention as representative for each chain, where (12) identifies lexicographically non-smallest mentions. Finally we impose two structural constraints on the result: a chain has to contain more than one mention (15) and a mention that is within another mention cannot be in the same chain with that mention (16). Note that, thanks to the elaboration tolerance [25] of ASP, constraints (15) and (16) can be removed if the respective restriction should not be applied, or can be made more restrictive (e.g., mentions in a chain cannot be neighbors) independent from the rest of the encoding. The encoding shown in Figure 1 admits as answer sets all possible consistent merges of the given annotations, including solutions where all annotations are ignored. Weak constraints prefer solutions where, according to the chosen cost functions, as many given annotations as possible are used and a single consistent solution is represented in the answer set. The balance between not ignoring annotations and not creating too many novel links between mentions can be adjusted using the cost functions. 4.2 Chain-Mention Encoding (CM) The difference between MM and CM is the way we represent the equivalence relation and how we check the preference function, in particular links in the solution that are not present in annotations. For reasons of brevity, we provide this encoding as a patch to encoding MM: encoding CM is obtained by using rules (17)–(27) shown in Figure 2 instead of rules (8)–(11) in encoding MM. 63 P.Schüller Adjudication of coreference annotations In the CM encoding variant, (17) represents annotators, (18) finds the number of chains for each annotator, and (19) computes 1.5 times the maximum of the largest number of chains annotated by any annotator in the input. Encoding CM is based on the assumption that the preferred result will not contain more chains than this amount of chains. This assumption can safely be made because differences in the amount of annotations are consistent over the whole document: some annotators produce more annotations, but this is true over the whole document, therefore using the maximum amount of chains times 1.5 is safe (using the preference relations we study, this number is never reached in practical solutions). Given the maximum number of resulting chains, (20) guesses which chain will ac- tually exist, and (21) ensures that if we use a certain chain ID, then we also use the ID below (this eliminates symmetries by ensuring the usage of consecutive chain IDs). Rules (22) and (23) represent all canonical mentions in cmention(·). For each of these mentions, (24) guesses in which chain that mention will be in the result. Constraints (25) and (26) enforce, that the guessed solution in resultcm corresponds to those links of an- notators that have been selected to be part of the solution in clink . To incur a cost for transitive edges that are not present in annotations, we cannot use clink → as in encoding MM. Instead, in weak constraint (27) we again join the resultcm relation with itself on the chain ID. 4.3 Weak and Strong Constraints for Preferences The encodings we have described so far impose a cost on chain/mention and men- tion/mention annotations that are not reflected in the solution, and a cost on men- tion/mention annotations in the solution that were not annotated by human annotators. If we replace the weak constraints by strict constraints (and remove the attached cost) then we obtain solutions corresponding to infinite cost of a constraint violation, i.e., the constraints must never be violated. Note that, if we replace all weak constraints by strict constraints, inconsistent annotations will not admit a solution. To guarantee existence of a solution, we must allow either to ignore chain/mention annotations, i.e., costm (M ) must be finite, or to ignore mention/mention annotations, i.e., costl (M, M 0 ) must be finite. Table 3 shows all objective function configurations we experiment with in this work. A dash ‘-’ indicates that the constraint was used as a strict constraint, an integer indi- cates a constant cost per ignored annotation, while L indicates a cost depending on the length |M | of mention M , computed as follows.    3 if |M | = 1  3 if |M | + |M 0 | = 2 0 cost m (M ) = 2 if 2 ≤ |M | ≤ 4 cost l (M, M ) = 2 if 3 ≤ |M | + |M 0 | ≤ 8   1 otherwise 1 otherwise Some rationale for the choice of objectives in Table 3 is as follows. Annotators make more mistakes with longer mentions, and for this reason it can be useful to assign a higher cost to ignoring mentions that contain fewer tokens. Therefore cost functions 64 P.Schüller Adjudication of coreference annotations Encoding/Approximation OOM OOT SAT OPT T M Tgrd # # # # sec MB sec CM/25 0 182 592 234 239 498 4.0 CM/∞ 96 245 562 105 250 1372 10.1 MM/25 181 150 324 353 175 1329 10.8 MM/∞ 181 162 354 311 186 1339 10.9 Table 1. Variation of encoding variant and approximation. can be constant or depend on the length of the involved mentions. We can ensure tran- sitivity by enforcing that we never merge chains that would require additional mention- mention links, however this would cause more mentions or their links to be ignored, and we would like to believe that human annotators create annotations for a reason. There- fore we put a cost on additional links that is lower than the cost of ignoring a given annotation (in some cases the cost is even zero). Moreover ignoring a chain-mention link implicitly removes at least one mention-mention link, and in large chains removes many mention-mention links. Therefore we put higher cost on ignoreing chain-mention links than on ignoring mention-mention links. A more comprehensive analysis of the implications of cost functions in Table 3 for the practical usefulness of solutions is a topic of future work. In this work our purpose is to provide a configurable framework and study the influence on the cost function on feasibility of computation. 5 Experimental Evaluation To evaluate our approach we used 21 documents from the METU-Sabanci Turkish Tree- bank [29] where documents have between 494 and 2600 mentions (1199 on average) and between 247 and 1300 chains (600 on average) with each chain containing between 19 and 53 mentions (34 on average). Each document was annotated by between 6 and 9 annotators (8 on average). 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 8 concurrently running jobs (each job using a single core, as we did not use solvers in multithreaded mode). We lim- ited memory usage to 5 GB and time usage to 300 sec. For instantiation we used Gringo 4.5.0 [18], for solving Clasp 3.1.2 [19] and Wasp 2.0 [2]. We use Clasp with parame- ters -opt-strategy=bb and -opt-strategy=usc and Wasp with parameters -weakconstraints-algorithm=basic and without arguments (which corre- sponds to unsat-core based optimization). As our instances are very hard for the abovementioned memory and time con- straints, we additionally experiment with an approximation for the preference relation: we only use a subset of weak constraints, concretely we omit weak constraints (for ig- noring or adding mention-mention links) whenever the pair of mentions has a distance of more than 25 tokens in the document. In our experimental results, columns OOM, OOT, SAT, and OPT, shows the number of runs that exceeded 5 GB, exceeded 300 sec, found at least one satisfiable solution, 65 P.Schüller Adjudication of coreference annotations Encoding/Solver OOM OOT SAT OPT T M Tgrd Chc Conf Lem # # # # sec MB sec # # # CM/Clasp/B 0 0 241 11 291 402 4.1 8M 1M 1M CM/Wasp/B 0 0 247 5 297 1039 4.0 1M 41M 297K CM/Clasp/U 0 120 0 132 156 248 4.0 1M 492K 492K CM/Wasp/U 0 62 104 86 213 305 4.0 1M 2M 31K MM/Clasp/B 42 0 199 11 269 1158 10.8 3M 1M 1M MM/Wasp/B 49 83 112 8 251 1641 10.9 514K 11M 295K MM/Clasp/U 42 27 0 183 79 1055 10.8 316K 10K 10K MM/Wasp/U 48 40 13 151 102 1462 10.7 114K 478K 2K Table 2. Variation of computation method and encodings with 25-token approximation. and found the first optimal solution and proved its optimality, respectively. Moreover columns T , M , and Tgrd give the average total time, memory, and instantiation time of all runs. In our experiments, all OOM and OOT conditions were reached during solving, never during grounding. For comparing the feasibility of computing solutions with MM and CM encodings and with or without approximation, Table 1 depicts accumulated results over all 21 documents, 4 solver variations, and 12 objective functions (i.e., each table row summa- rizes 1008 runs). We can observe that encoding MM exhausts memory much more than encoding CM, and that we can only fit into 5 GB by using CM and the 25-token approx- imation. Although CM fits into less memory, it requires more time on average and we find more optimal solutions with encoding MM, both with and without the 25-token ap- proximation. Instantiation times are similar for all configurations, except for the CM/25 combination which requires half the time of the other configurations for reasons we try to explain in Section 5.1. Table 2 compares computational methods for both encodings with 25-token ap- proximation across all 21 instances and 12 objective functions. We see that for getting some answer set (SAT or OPT), bound-based optimization and CM encoding are better than configurations with unsat-core optimization or encoding MM, i.e., CM/·/B pro- vides (suboptimal) solutions for all instances. However, the highest number of optimal solutions is obtained with encoding MM and unsat-core optimization: here Clasp per- forms better (183 optimal solutions) than Wasp (151) in this setting. The columns Chc, Conf , and Lem, show the number of choices, conflicts, and learned clauses, re- spectively (in runs that did not exhaust memory). Clasp did not find any satisfiable solutions in unsat-core (U) mode (either the solutions were optimal or the timeout was reached), while Wasp found many solutions before optimality. On the other hand, in branch-and-bound mode (B) Clasp finds more optimal and more satisfiable solutions than Wasp. The memory usage of Wasp is significantly higher than the one of Clasp in mode B, while for CM/·/U this difference is smaller (248 MB vs 305 MB). In summary, for branch-and-bound optimization Clasp seems more suitable, while for unsat-core optimization, Wasp seems more suitable. As only the CM encoding with 25-token approximation fits into memory for all configurations, and because only branch-and-bound optimization finds solutions in all 66 P.Schüller Adjudication of coreference annotations Objective Clasp/B Wasp/B cost m cost l cost a SAT OPT T M SAT OPT T M # # sec MB # # sec MB - 1 - 21 0 300 560 21 0 300 804 - 1 0 19 2 274 443 20 1 287 1132 1 - - 21 0 300 547 21 0 300 1981 1 - 0 19 2 274 161 20 1 292 1686 2 - 1 20 1 295 190 21 0 300 1383 2 1 - 21 0 300 567 21 0 300 706 2 1 0 19 2 281 520 20 1 295 727 3 2 1 21 0 300 366 21 0 300 888 6 3 1 20 1 294 423 21 0 300 857 - L 1 20 1 287 450 20 1 288 806 L - 1 20 1 288 194 20 1 291 770 2L L 1 20 1 292 402 21 0 300 721 Table 3. Variation of objective with encoding CM, branch-and-bound, 25-token approximation. cases, we compared several possible objective functions using the CM/25 configuration. Table 3 shows the result, both with Clasp and Wasp in branch-and-bound optimiza- tion mode. We see that there are no big differences between the feasibility of various objective functions: only few instances are solved to the optimal solution and therefore average time requirements are very close to the timeout of 300 seconds. However, we can observe interesting memory requirement, which is high for Wasp in those cases where it is low for Clasp: for an objective function which does not permit ignoring mention-mention links, uses fixed cost 2 on ignoring chain-mention annotations, and either uses cost 1 or no cost for additional mention-mention links. Moreover, memory requirement is more stable for Clasp while it varies more and is higher in general for Wasp. 5.1 Instantiation Analysis with Gringo To gain additional insights about the instantiated program, we have modified Gringo 4.5.0 to count instantiations of each nonground rule and extend the output of gringo -verbose with a table that shows for each nonground rule the number of times it was instantiated with 0 body conditions (i.e., as facts), with 1 and 2 body conditions (i.e., as rules that can be propagated particularly efficiently), and as rules with 3 or more body conditions. Our publicly available patch3 shows these counts for the intermediate representation of Gringo. Table 4 shows those parts of the instantiation analysis table where rules have been instantiated more than 10k times for an instance of average difficulty (1298 mentions, 649 chains, max 35 mentions per chain). In the MM encoding, the main instantiation effort (725k rules) originates in the tran- sitive closure rules (10). On the other hand, in the CM encoding the main instantiation 3 https://github.com/peschue/clingo/tree/grounder-stats 67 P.Schüller Adjudication of coreference annotations Variables in body Nonground Rule 0 1 2 3+ MM encoding 0 12K 0 0 clink_tr(X,Y):-clink_tr(Y,X). 0 0 725K 0 clink_tr(X,Z):-clink_tr(Y,Z),clink_tr(X,Y). 0 453 12K 0 result_cm(X,Y):-clink_tr(X,Y),not not_repr(X). 0 12K 0 0 result_c(C):-result_cm(C,_). 0 1 2 3+ CM encoding 0 0 0 112K :-result_cm(C,X),clink(X,Y),not result_cm(C,Y). 0 0 0 112K :-result_cm(C,Y),clink(X,Y),not result_cm(C,X). 0 0 5212K 112K :~result_cm(C,Y),X