Optimizing Differentiable Relaxations of Coreference Evaluation Metrics

Abstract: Coreference evaluation metrics are hard to optimize directly as they are non-differentiable functions, not easily decomposable into elementary decisions. Consequently, most approaches optimize objectives only indirectly related to the end goal, resulting in suboptimal performance. Instead, we propose a differentiable relaxation that lends itself to gradient-based optimisation, thus bypassing the need for reinforcement learning or heuristic modification of cross-entropy. We show that by modifying the training objective of a competitive neural coreference system, we obtain a substantial gain in performance. This suggests that our approach can be regarded as a viable alternative to using reinforcement learning or more computationally expensive imitation learning.

Coreference resolution is the task of identifying all mentions which refer to the same entity in a document. It has been shown beneficial in many natural language processing (NLP) applications, including question answering BIBREF0 and information extraction BIBREF1 , and often regarded as a prerequisite to any text understanding task.
Coreference resolution can be regarded as a clustering problem: each cluster corresponds to a single entity and consists of all its mentions in a given text. Consequently, it is natural to evaluate predicted clusters by comparing them with the ones annotated by human experts, and this is exactly what the standard metrics (e.g., MUC, B INLINEFORM0 , CEAF) do. In contrast, most state-of-the-art systems are optimized to make individual co-reference decisions, and such losses are only indirectly related to the metrics.
One way to deal with this challenge is to optimize directly the non-differentiable metrics using reinforcement learning (RL), for example, relying on the REINFORCE policy gradient algorithm BIBREF2 . However, this approach has not been very successful, which, as suggested by clark-manning:2016:EMNLP2016, is possibly due to the discrepancy between sampling decisions at training time and choosing the highest ranking ones at test time. A more successful alternative is using a `roll-out' stage to associate cost with possible decisions, as in clark-manning:2016:EMNLP2016, but it is computationally expensive. Imitation learning BIBREF3 , BIBREF4 , though also exploiting metrics, requires access to an expert policy, with exact policies not directly computable for the metrics of interest.
In this work, we aim at combining the best of both worlds by proposing a simple method that can turn popular coreference evaluation metrics into differentiable functions of model parameters. As we show, this function can be computed recursively using scores of individual local decisions, resulting in a simple and efficient estimation procedure. The key idea is to replace non-differentiable indicator functions (e.g. the member function INLINEFORM0 ) with the corresponding posterior probabilities ( INLINEFORM1 ) computed by the model. Consequently, non-differentiable functions used within the metrics (e.g. the set size function INLINEFORM2 ) become differentiable ( INLINEFORM3 ). Though we assume that the scores of the underlying statistical model can be used to define a probability model, we show that this is not a serious limitation. Specifically, as a baseline we use a probabilistic version of the neural mention-ranking model of P15-1137, which on its own outperforms the original one and achieves similar performance to its global version BIBREF5 . Importantly when we use the introduced differentiable relaxations in training, we observe a substantial gain in performance over our probabilistic baseline. Interestingly, the absolute improvement (+0.52) is higher than the one reported in clark-manning:2016:EMNLP2016 using RL (+0.05) and the one using reward rescaling (+0.37). This suggests that our method provides a viable alternative to using RL and reward rescaling.
The outline of our paper is as follows: we introduce our neural resolver baseline and the B INLINEFORM0 and LEA metrics in Section SECREF2 . Our method to turn a mention ranking resolver into an entity-centric resolver is presented in Section SECREF3 , and the proposed differentiable relaxations in Section SECREF4 . Section SECREF5 shows our experimental results.
In this section we introduce neural mention ranking, the framework which underpins current state-of-the-art models BIBREF6 . Specifically, we consider a probabilistic version of the method proposed by P15-1137. In experiments we will use it as our baseline.
Let INLINEFORM0 be the list of mentions in a document. For each mention INLINEFORM1 , let INLINEFORM2 be the index of the mention that INLINEFORM3 is coreferent with (if INLINEFORM4 , INLINEFORM5 is the first mention of some entity appearing in the document). As standard in coreference resolution literature, we will refer to INLINEFORM6 as an antecedent of INLINEFORM7 . Then, in mention ranking the goal is to score antecedents of a mention higher than any other mentions, i.e., if INLINEFORM8 is the scoring function, we require INLINEFORM9 for all INLINEFORM10 such that INLINEFORM11 and INLINEFORM12 are coreferent but INLINEFORM13 and INLINEFORM14 are not.
Let INLINEFORM0 and INLINEFORM1 be respectively features of INLINEFORM2 and features of pair INLINEFORM3 . The scoring function is defined by: INLINEFORM4 
where INLINEFORM0 
 and INLINEFORM0 are real vectors and matrices with proper dimensions, INLINEFORM1 are real scalars.
Unlike P15-1137, where the max-margin loss is used, we define a probabilistic model. The probability that INLINEFORM0 and INLINEFORM1 are coreferent is given by DISPLAYFORM0 
Following D13-1203 we use the following softmax-margin BIBREF8 loss function: INLINEFORM0 
where INLINEFORM0 are model parameters, INLINEFORM1 is the set of the indices of correct antecedents of INLINEFORM2 , and INLINEFORM3 . INLINEFORM4 is a cost function used to manipulate the contribution of different error types to the loss function: INLINEFORM5 
The error types are “false anaphor”, “false new”, “wrong link”, and “no mistake”, respectively. In our experiments, we borrow their values from D13-1203: INLINEFORM0 . In the subsequent discussion, we refer to the loss as mention-ranking heuristic cross entropy.
We use five most popular metrics,
MUC BIBREF9 ,
B INLINEFORM0 BIBREF10 ,
CEAF INLINEFORM0 , CEAF INLINEFORM1 BIBREF11 ,
BLANC BIBREF12 ,
LEA BIBREF13 .
for evaluation. However, because MUC is the least discriminative metric BIBREF13 , whereas CEAF is slow to compute, out of the five most popular metrics we incorporate into our loss only B INLINEFORM0 . In addition, we integrate LEA, as it has been shown to provide a good balance between discriminativity and interpretability.
Let INLINEFORM0 and INLINEFORM1 be the gold-standard entity set and an entity set given by a resolver. Recall that an entity is a set of mentions. The recall and precision of the B INLINEFORM2 metric is computed by: INLINEFORM3 
 The LEA metric is computed as: INLINEFORM0 
 where INLINEFORM0 is the number of coreference links in entity INLINEFORM1 . INLINEFORM2 , for both metrics, is defined by: INLINEFORM3 
 INLINEFORM0 is used in the standard evaluation.
Mention-ranking resolvers do not explicitly provide information about entities/clusters which is required by B INLINEFORM0 and LEA. We therefore propose a simple solution that can turn a mention-ranking resolver into an entity-centric one.
First note that in a document containing INLINEFORM0 mentions, there are INLINEFORM1 potential entities INLINEFORM2 where INLINEFORM3 has INLINEFORM4 as the first mention. Let INLINEFORM5 be the probability that mention INLINEFORM6 corresponds to entity INLINEFORM7 . We now show that it can be computed recursively based on INLINEFORM8 as follows: INLINEFORM9 
 In other words, if INLINEFORM0 , we consider all possible INLINEFORM1 with which INLINEFORM2 can be coreferent, and which can correspond to entity INLINEFORM3 . If INLINEFORM4 , the link to be considered is the INLINEFORM5 's self-link. And, if INLINEFORM6 , the probability is zero, as it is impossible for INLINEFORM7 to be assigned to an entity introduced only later. See Figure FIGREF13 for extra information.
We now turn to two crucial questions about this formula:
The first question is answered in Proposition SECREF16 . The second question is important because, intuitively, when a mention INLINEFORM0 is anaphoric, the potential entity INLINEFORM1 does not exist. We will show that the answer is “No” by proving in Proposition SECREF17 that the probability that INLINEFORM2 is anaphoric is always higher than any probability that INLINEFORM3 , INLINEFORM4 refers to INLINEFORM5 .
Proposition 1 INLINEFORM0 is a valid probability distribution, i.e., INLINEFORM1 , for all INLINEFORM2 .
We prove this proposition by induction.
Basis: it is obvious that INLINEFORM0 .
Assume that INLINEFORM0 for all INLINEFORM1 . Then, INLINEFORM2 
 Because INLINEFORM0 for all INLINEFORM1 , this expression is equal to INLINEFORM2 
Therefore, INLINEFORM0 
(according to Equation EQREF5 ).
Proposition 2 INLINEFORM0 for all INLINEFORM1 .
We prove this proposition by induction.
Basis: for INLINEFORM0 , INLINEFORM1 
Assume that INLINEFORM0 for all INLINEFORM1 and INLINEFORM2 . Then INLINEFORM3 
Having INLINEFORM0 computed, we can consider coreference resolution as a multiclass prediction problem. An entity-centric heuristic cross entropy loss is thus given below: INLINEFORM1 
where INLINEFORM0 is the correct entity that INLINEFORM1 belongs to, INLINEFORM2 . Similar to INLINEFORM3 in the mention-ranking heuristic loss in Section SECREF2 , INLINEFORM4 is a cost function used to manipulate the contribution of the four different error types (“false anaphor”, “false new”, “wrong link”, and “no mistake”): INLINEFORM5 
There are two functions used in computing B INLINEFORM0 and LEA: the set size function INLINEFORM1 and the link function INLINEFORM2 . Because both of them are non-differentiable, the two metrics are non-differentiable. We thus need to make these two functions differentiable.
There are two remarks. Firstly, both functions can be computed using the indicator function INLINEFORM0 : INLINEFORM1 
 Secondly, given INLINEFORM0 , the indicator function INLINEFORM1 , INLINEFORM2 is the converging point of the following softmax as INLINEFORM3 (see Figure FIGREF19 ): INLINEFORM4 
where INLINEFORM0 is called temperature BIBREF14 .
Therefore, we propose to represent each INLINEFORM0 as a soft-cluster: INLINEFORM1 
where, as defined in Section SECREF3 , INLINEFORM0 is the potential entity that has INLINEFORM1 as the first mention. Replacing the indicator function INLINEFORM2 by the probability distribution INLINEFORM3 , we then have a differentiable version for the set size function and the link function: INLINEFORM4 
 INLINEFORM0 and INLINEFORM1 are computed similarly with the constraint that only mentions in INLINEFORM2 are taken into account. Plugging these functions into precision and recall of B INLINEFORM3 and LEA in Section SECREF6 , we obtain differentiable INLINEFORM4 and INLINEFORM5 , which are then used in two loss functions: INLINEFORM6 
 where INLINEFORM0 is the hyper-parameter of the INLINEFORM1 regularization terms.
It is worth noting that, as INLINEFORM0 , INLINEFORM1 and INLINEFORM2 . Therefore, when training a model with the proposed losses, we can start at a high temperature (e.g., INLINEFORM3 ) and anneal to a small but non-zero temperature. However, in our experiments we fix INLINEFORM4 . Annealing is left for future work.
We now demonstrate how to use the proposed differentiable B INLINEFORM0 and LEA to train a coreference resolver. The source code and trained models are available at https://github.com/lephong/diffmetric_coref.
We run experiments on the English portion of CoNLL 2012 data BIBREF15 which consists of 3,492 documents in various domains and formats. The split provided in the CoNLL 2012 shared task is used. In all our resolvers, we use not the original features of P15-1137 but their slight modification described in N16-1114 (section 6.1).
We build following baseline and three resolvers:
baseline: the resolver presented in Section SECREF2 . We use the identical configuration as in N16-1114: INLINEFORM0 , INLINEFORM1 , INLINEFORM2 (where INLINEFORM3 are respectively the numbers of mention features and pair-wise features). We also employ their pretraining methodology.
 INLINEFORM0 : the resolver using the entity-centric cross entropy loss introduced in Section SECREF18 . We set INLINEFORM1 .
 INLINEFORM0 and INLINEFORM1 : the resolvers using the losses proposed in Section SECREF4 . INLINEFORM2 is tuned on the development set by trying each value in INLINEFORM3 .
To train these resolvers we use AdaGrad BIBREF16 to minimize their loss functions with the learning rate tuned on the development set and with one-document mini-batches. Note that we use the baseline as the initialization point to train the other three resolvers.
We firstly compare our resolvers against P15-1137 and N16-1114. Results are shown in the first half of Table TABREF25 . Our baseline surpasses P15-1137. It is likely due to using features from N16-1114. Using the entity-centric heuristic cross entropy loss and the relaxations are clearly beneficial: INLINEFORM0 is slightly better than our baseline and on par with the global model of N16-1114. INLINEFORM1 outperform the baseline, the global model of N16-1114, and INLINEFORM2 . However, the best values of INLINEFORM3 are INLINEFORM4 , INLINEFORM5 respectively for INLINEFORM6 , and INLINEFORM7 . Among these resolvers, INLINEFORM8 achieves the highest F INLINEFORM9 scores across all the metrics except BLANC.
When comparing to clark-manning:2016:EMNLP2016 (the second half of Table TABREF25 ), we can see that the absolute improvement over the baselines (i.e. `heuristic loss' for them and the heuristic cross entropy loss for us) is higher than that of reward rescaling but with much shorter training time: INLINEFORM0 (7 days) and INLINEFORM1 (15 hours) on the CoNLL metric for clark-manning:2016:EMNLP2016 and ours, respectively. It is worth noting that our absolute scores are weaker than these of clark-manning:2016:EMNLP2016, as they build on top of a similar but stronger mention-ranking baseline, which employs deeper neural networks and requires a much larger number of epochs to train (300 epochs, including pretraining). For the purpose of illustrating the proposed losses, we started with a simpler model by P15-1137 which requires a much smaller number of epochs, thus faster, to train (20 epochs, including pretraining).
Table TABREF28 shows the breakdown of errors made by the baseline and our resolvers on the development set. The proposed resolvers make fewer “false anaphor” and “wrong link” errors but more “false new” errors compared to the baseline. This suggests that loss optimization prevents over-clustering, driving the precision up: when antecedents are difficult to detect, the self-link (i.e., INLINEFORM0 ) is chosen. When INLINEFORM1 increases, they make more “false anaphor” and “wrong link” errors but less “false new” errors.
In Figure FIGREF29 (a) the baseline, but not INLINEFORM0 nor INLINEFORM1 , mistakenly links INLINEFORM2 [it] with INLINEFORM3 [the virus]. Under-clustering, on the other hand, is a problem for our resolvers with INLINEFORM4 : in example (b), INLINEFORM5 missed INLINEFORM6 [We]. This behaviour results in a reduced recall but the recall is not damaged severely, as we still obtain a better INLINEFORM7 score. We conjecture that this behaviour is a consequence of using the INLINEFORM8 score in the objective, and, if undesirable, F INLINEFORM9 with INLINEFORM10 can be used instead. For instance, also in Figure FIGREF29 , INLINEFORM11 correctly detects INLINEFORM12 [it] as non-anaphoric and links INLINEFORM13 [We] with INLINEFORM14 [our].
Figure FIGREF30 shows recall, precision, F INLINEFORM0 (average of MUC, B INLINEFORM1 , CEAF INLINEFORM2 ), on the development set when training with INLINEFORM3 and INLINEFORM4 . As expected, higher values of INLINEFORM5 yield lower precisions but higher recalls. In contrast, F INLINEFORM6 increases until reaching the highest point when INLINEFORM7 for INLINEFORM8 ( INLINEFORM9 for INLINEFORM10 ), it then decreases gradually.
Because the resolvers are evaluated on F INLINEFORM0 score metrics, it should be that INLINEFORM1 and INLINEFORM2 perform the best with INLINEFORM3 . Figure FIGREF30 and Table TABREF25 however do not confirm that: INLINEFORM4 should be set with values a little bit larger than 1. There are two hypotheses. First, the statistical difference between the training set and the development set leads to the case that the optimal INLINEFORM5 on one set can be sub-optimal on the other set. Second, in our experiments we fix INLINEFORM6 , meaning that the relaxations might not be close to the true evaluation metrics enough. Our future work, to confirm/reject this, is to use annealing, i.e., gradually decreasing INLINEFORM7 down to (but larger than) 0.
Table TABREF25 shows that the difference between INLINEFORM0 and INLINEFORM1 in terms of accuracy is not substantial (although the latter is slightly better than the former). However, one should expect that INLINEFORM2 would outperform INLINEFORM3 on B INLINEFORM4 metric while it would be the other way around on LEA metric. It turns out that, B INLINEFORM5 and LEA behave quite similarly in non-extreme cases. We can see that in Figure 2, 4, 5, 6, 7 in moosavi-strube:2016:P16-1.
Mention ranking and entity centricity are two main streams in the coreference resolution literature. Mention ranking BIBREF17 , BIBREF18 , BIBREF19 , BIBREF20 considers local and independent decisions when choosing a correct antecedent for a mention. This approach is computationally efficient and currently dominant with state-of-the-art performance BIBREF5 , BIBREF6 . P15-1137 propose to use simple neural networks to compute mention ranking scores and to use a heuristic loss to train the model. N16-1114 extend this by employing LSTMs to compute mention-chain representations which are then used to compute ranking scores. They call these representations global features. clark-manning:2016:EMNLP2016 build a similar resolver as in P15-1137 but much stronger thanks to deeper neural networks and “better mention detection, more effective, hyperparameters, and more epochs of training”. Furthermore, using reward rescaling they achieve the best performance in the literature on the English and Chinese portions of the CoNLL 2012 dataset. Our work is built upon mention ranking by turning a mention-ranking model into an entity-centric one. It is worth noting that although we use the model proposed by P15-1137, any mention-ranking models can be employed.
Entity centricity BIBREF21 , BIBREF22 , BIBREF23 , BIBREF24 , BIBREF25 , on the other hand, incorporates entity-level information to solve the problem. The approach can be top-down as in haghighi2010coreference where they propose a generative model. It can also be bottom-up by merging smaller clusters into bigger ones as in clark-manning:2016:P16-1. The method proposed by ma-EtAl:2014:EMNLP2014 greedily and incrementally adds mentions to previously built clusters using a prune-and-score technique. Importantly, employing imitation learning these two methods can optimize the resolvers directly on evaluation metrics. Our work is similar to ma-EtAl:2014:EMNLP2014 in the sense that our resolvers incrementally add mentions to previously built clusters. However, different from both ma-EtAl:2014:EMNLP2014,clark-manning:2016:P16-1, our resolvers do not use any discrete decisions (e.g., merge operations). Instead, they seamlessly compute the probability that a mention refers to an entity from mention-ranking probabilities, and are optimized on differentiable relaxations of evaluation metrics.
Using differentiable relaxations of evaluation metrics as in our work is related to a line of research in reinforcement learning where a non-differentiable action-value function is replaced by a differentiable critic BIBREF26 , BIBREF27 . The critic is trained so that it is as close to the true action-value function as possible. This technique is applied to machine translation BIBREF28 where evaluation metrics (e.g., BLUE) are non-differentiable. A disadvantage of using critics is that there is no guarantee that the critic converges to the true evaluation metric given finite training data. In contrast, our differentiable relaxations do not need to train, and the convergence is guaranteed as INLINEFORM0 .
We have proposed
Experimental results show that our approach outperforms the resolver by N16-1114, and gains a higher improvement over the baseline than that of clark-manning:2016:EMNLP2016 but with much shorter training time.
We would like to thank Raquel Fernández, Wilker Aziz, Nafise Sadat Moosavi, and anonymous reviewers for their suggestions and comments. The project was supported by the European Research Council (ERC StG BroadSem 678254), the Dutch National Science Foundation (NWO VIDI 639.022.518) and an Amazon Web Services (AWS) grant.

Figure and table captions:
Figure 1: For each mention mu there is a potential entity Eu so that mu is the first mention in the chain. Computing p(mi ∈ Eu), u < i takes into the account all directed paths from mi to Eu (black arrows). Noting that there is no directed path from any mk, k < u to Eu because p(mk ∈ Eu) = 0. (See text for more details.)
Figure 2: Softmax exp{πi/T}∑ j exp{πj/T} with different values of T . The softmax becomes more peaky when the value of T gets smaller. As T → 0 the softmax converges to the indicator function that chooses arg maxi πi.
Figure 3: Example predictions: the subscript before a mention is its index. The superscript / subscript after a mention indicates the antecedent predicted by the baseline / Lβ=1,B3 , Lβ= √ 1.4,B3 . Mentions with the same color are true coreferents. “*”s mark incorrect decisions.
Table 1: Results (F1) on CoNLL 2012 test set. CoNLL is the average of MUC, B3, and CEAFe.
Table 2: Number of: “false anaphor” (FA, a non-anaphoric mention marked as anaphoric), “false new” (FN, an anaphoric mention marked as non-anaphoric), and “wrong link” (WL, an anaphoric mention is linked to a wrong antecedent) errors on the development set.
Figure 4: Recall, precision, F1 (average of MUC, B3, CEAFe), on the development set when training with Lβ,B3 (left) and Lβ,LEA (right). Higher values of β yield lower precisions but higher recalls.

Questions about this paper:
How long is the training dataset?

Answers:
3492