End-to-End Coreference Resolution for Clinical Narratives

1 Introduction

This paper addresses the task of coreference resolution for clinical narratives. Coreference resolution is the task of finding referring expressions in a text that refer to the same entity, i.e., finding expressions that corefer. Consider the following text sampled from the corpora we used:

This 63-year-old man had [malignant fibrous histiocytoma of duodenum], discovered in 02/95. Other than [a mass in the duodenum], the patient was also diagnosed with anemia. A [leiomyosarcoma] was resected after embolization of the splenic artery. However, [it] could not be completely excised; moreover [the tumor] metastasized to the liver as was discovered on follow up scan in 06/95.

In the above text, all the phrases which are shown in brackets refer to the same entity and hence form a coreference chain. It is clear that identifying such coreference chains requires a lot of medical knowledge. For example, we need to know that mass can refer to a malignant histiocytoma. To address this need, we need to use domain-specific knowledge sources. While the literature on coreference resolution heavily discusses the need to incorporate background knowledge [Ratinov and Roth, 2012; Rahman and Ng, 2011], there has been very limited success in doing it. The first contribution of this paper is that it provides a principled way for incorporating knowledge-based constraints into the coreference resolution process and also exhibits its significant contribution to performance.

Best-link strategy has been successfully used in coreference resolution on different types of datasets [Xu et al., 2012b; Bengtson and Roth, 2008]. Chang et al. [2011] proposed a variation of best-link strategy where they also incorporated several constraints in its objective function. In this paper, we use the coreference model similar to that of Chang et al. [2011]. However, our constraints are quite different from that of Chang et al. Many of our constraints are obtained from the context in which the mentions appear. Unlike Chang et al., we received significant improvements by using the constraints. This shows that the context in which the mentions appear is quite important.

The second contribution of this paper is in pronominal resolution. Quite often, we find in coreference resolution literature [Bengtson and Roth, 2008; Raghunathan et al., 2010; Poon and Domingos, 2008; Chang et al., 2011] that researchers use the same model for resolving all kinds of pronouns. We, however, found that different pronouns behave quite differently. So, we developed separate modules for finding the antecedents of different kinds of pronouns. The method that we used for pronominal resolution is quite general and will be useful for coreference resolution on other domains as well.

For our experiments, we used the datasets provided by i2b2/VA challenge organizers in 2011 shared task on coreference resolution for clinical narratives. To the best of our knowledge, we report the best results on this corpora. Finally, we also report, for the first time, results on end-to-end coreference resolution on i2b2 corpora.

To summarize, the key contributions of our paper are as follows: (1) This paper shows that well-informed constraints can give significant performance improvements in coreference resolution, (2) It exhibits the distinct behavior of different pronouns and makes use of it in resolving their coreference, and (3) It reports state-of-the-art results on coreference resolution on clinical text, including an end-to-end system.

2 Task Description

Coreference resolution aims at clustering together textual mentions within a single document based on underlying referent entities. For our experiments, we used the datasets provided by i2b2 team as part of coreference challenge. We address the task of coreference resolution in two different settings as explained below.

In the first setting, we use the same problem definition as was specified in the Task 1C of i2b2 coreference challenge. In this setting, mentions have already been identified and classified into 4 types: test (TEST), treatment (TRE), problem (PROB) and pronoun (PRON). Coreference relation can exist only within the mentions of same type. However, PRON mentions can corefer with any other mention. Given the entity mentions along with the types, the aim is to build coreference chains for the first 3 types: TEST, TRE and PROB. Since PRON mentions can corefer with the mentions of other types, there are no separate PRON chains. In the following, we will use the term "medical mentions" to collectively refer to mentions of type TEST, TRE and PROB.

In the second setting, we perform end-to-end coreference resolution for clinical notes. In this setting, the input consists of clinical notes in free-text format and the aim is to build coreference chains for the medical concepts. To perform end-to-end coreference resolution, we first identify mention boundaries and then classify the mentions into 4 types: TEST, TRE, PROB and PRON. Then coreference chains are found in a way similar to that of first setting.

In next few sections, we describe our approach for coreference resolution when the mentions are already given (i.e. according to first setting). In §9, we describe our approach for end-to-end coreference resolution.

3 Coreference Model

We view coreference resolution as a graph problem: Given a set of mentions and their context as nodes, generate a set of edges such that any two mentions that refer to the same entity are connected by some path in the graph. We construct this entity-mention graph by finding out the best antecedent of each given mention (anaphor) such that the antecedent refers to the same entity as the anaphor. For finding the best antecedent for medical mentions, we use a variant of BestLink strategy. The Best-Link strategy [Ng and Cardie, 2002b; Bengtson and Roth, 2008; Chang et al., 2011] for selecting the antecedent of a mention chooses that candidate as the antecedent which gets the maximum score according to a pairwise coreference function pc. We extend the Best-Link strategy by including a distance term and several constraints in its objective function as discussed below. For finding the best antecedent for pronominal mentions, we use a different approach which will be explained in §6.

3.1 DecisionModel: Constrained Best-Link

Given a document d and a pairwise coreference scoring function pc that maps an ordered pair of mentions to a value indicating the probability that they are coreferential, we generate a coreference graph Gd according to the following decision model: For each mention mi in document d, let Bmi = {m1,m2, ...,mi-1} be the set of mentions appearing before mi in d. Let a be the highest scoring antecedent. Then, we have:

In the above equation, d(mj,mi) refers to a normalized distance between mj and mi which takes values between 0 and 1. Cl refers to the lth constraint and is defined as follows (for all values of l):

where pl is the penalty associated with the lth constraint. Thus, different constraints can have different penalties. The higher the penalty associated with the constraint, the stronger it is enforced. If scorei(a) is greater than a threshold δ, then we add the edge (a,mi) to the coreference graph Gd. The value of pc(mj,mi) lies between 0 and 1. The value of k is chosen to be sufficiently greater than 1 so that the pairwise classifier is given preference over the distance term in choosing the best antecedent. But if the pc values of any two candidates are almost similar, then the antecedent which is closer to the anaphor gets the higher score because of the distance term in Equation (1). Thus, our decision model combines the advantages of both "best-link" and "closest-first" models which are generally used for coreference resolution. Setting k = ∞ and L = 0 reduces our model to the standard "bestlink" decision model.

The resulting graph produced by the decoding technique mentioned above contains connected components (determined by transitive closure) with all the mentions in the component referring to the same entity.

3.2 Pairwise Coreference Function

Coreference function pc in Equation (1) consists of 3 different classifiers, one each for TEST, TRE and PROB classes. Each of these classifiers takes as input an ordered pair of mentions (a, m) such that a precedes m in the document, and produces as output a value that is interpreted as the conditional probability that a and m belong in the same equivalence class.

4 Description of Features

In this section, we describe the features used by pairwise classifiers. We divide the features into two main categories as described in the following two subsections.

4.1 Baseline Features

Baseline features refer to those features which are typically used for coreference resolution. These features are subdivided into the following 3 categories: (1) Lexical Features: Similar to Bengtson and Roth [2008], we used the following lexical features: (a) Exact (or extent) match, (b) Substring relation and (c) Head match. (2) Syntactic Features: For syntactic features, we used Apposition and Predicate Nominative as described in Raghunathan et al. [2010]. (3) Semantic Features: Similar to Bengtson and Roth [2008], we used WordNet to check whether given mentions are synonyms or hypernyms of one another.

4.2 Features Using Domain-Specific Knowledge

In medical text, the same concept can be represented in several different ways. For example, headache, cranial pain and cephalgia all refer to the same concept. Similarly, Atrial Fibrillation, AF and AFib also refer to the same concept. The baseline features are not sufficient to address the ambiguity and variability that exists in medical terminology. To improve the performance of coreference resolution, we used several types of domain-specific knowledge as explained below. The importance of using knowledge has been emphasized in other domains as well [Rahman and Ng, 2011; Bryl et al., 2010; Ratinov and Roth, 2012].

Expanding the abbreviations Clinical narratives use a lot of abbreviations. A few examples are: MRI (Magnetic Resonance Imaging), COPD (Chronic Obstructive Pulmonary Disease) etc. Abbreviations were expanded to their full forms as a normalization step. We collected abbreviations from several sources like training data, Wikipedia 1 etc. For ambiguous abbreviations, we considered all possible expansions.

Converting Hyponyms to Hypernyms During preprocessing, we converted some of the common hyponyms to the corresponding hypernyms. Examples of such conversions are: chemotherapy→ therapy, hemicolectomy→colectomy. Such conversions are quite helpful because it is a common practice in clinical documents to refer to some of the problems and treatments introduced earlier in the document with their more general names later on. These hyponym-hypernym pairs were collected from the training data.

Mapping to Biomedical Vocabularies We used MetaMap [Aronson and Lang, 2010] and MetamorphoSys tools to map the mentions to concepts in biomedical vocabularies like UMLS 2 , MeSH 3 and SNOMED CT 4 . Such mapping helps us to determine whether any two mentions are equivalent or not. For example, cancer and malignancy both map to same UMLS concept namely Primary Malignant Neoplasm. From such mapping, we can infer that cancer and malignancy can be coreferential to one another even though they are lexically quite different.

5 Description of Constraints

Although our model allows for both hard and soft constraints, we used only hard constraints in the current work. These constraints allow us to override the decision of the pairwise classifier, where appropriate. Following is a list of constraints we used.

1 http://en.wikipedia.org/wiki/List of medical abbreviations

2 http://www.nlm.nih.gov/research/umls/

3 http://www.nlm.nih.gov/mesh/meshhome.html

4 http://www.ihtsdo.org/snomed-ct/

• Length Constraint: Surface form of both the mentions must be at least 2 characters long.
• Body Parts Constraint: If body parts (like chest, arm, head) are specified, they should not be incompatible. For example, "pain" in chest and "pain" in leg cannot be coreferential.
• Anatomical Terms Constraint: If anatomical terms 5 (like proximal, anterior, dorsal) are specified, they should not be incompatible. For example, "pain" in right hand and "pain" in left hand cannot be coreferential.
• Temporal Constraint: Certain words like follow-up or repeat convey temporal information about the mentions. For example, the word repeat in the mention repeat chest x-ray indicates that chest x-ray is being done for the second time. If two mentions refer to tests or treatments which were done at different times, then they cannot be coreferential.
• Section Constraint: Clinical reports often specify different sections like History of Present Illness, Laboratory Data, Medications on Discharge etc. We developed an algorithm for finding and normalizing the section headings. If a mention appears in either Family History section or Social History section in a clinical report, we do not consider it for coreference. This is because such mentions generally describe the problems associated with family members of the patient and not the patient himself/herself.
• Value Constraint: TEST mentions generally have a value associated with them. If any two TEST mentions do not have the same value, then they cannot be coreferential.
• Assertion Constraint: We implemented an algorithm for finding the assertion status (like present, absent etc.) of PROB mentions as described by Xu et al. [Xu et al., 2012a]. Two mentions cannot be coreferential if they do not have the same assertion status.

6 Pronominal Coreference Resolution

In the medical corpora we worked with, pronominal resolution is primarily limited to 4 types of pronouns: (1) which (2) that (3) this and (4) it. Other pronouns like these, those, whichever etc. hardly participate in coreference relation in our datasets. Also, personal pronouns like he, she, him, you, yourself etc. refer to persons and hence are not relevant to us because we are interested in forming coreference chains for only medical mentions (TEST, TRE and PROB).

Features commonly used for pronominal resolution [Raghunathan et al., 2010; Poon and Domingos, 2008] include distance, number agreement, gender agreement, entity type, grammatical person (first, second and third) etc. However, many of these features are not very helpful in our case. For example, all the medical mentions have neuter gender. So, gender agreement is not helpful. Similarly, grammatical person feature is also not helpful because it is relevant only for personal pronouns. It should also to be noted that researchers [Raghunathan et al., 2010; Poon and Domingos, 2008] commonly use the same technique for resolving different types of pronouns. However, in our experiments, we found that different pronouns behave very differently and therefore, we designed separate modules for finding the antecedent for different types of pronouns. Next two subsections describe our overall strategy for pronominal resolution.

5 http://en.wikipedia.org/wiki/Anatomical terms of location

6.1 Determining Anaphoricity

We first determine whether the given pronoun is anaphoric or not. Ng and Cardie [2002a] have previously shown the benefits of predicting anaphoricity. To identify nonreferential cases for pronoun it, we implemented the heuristics mentioned by Paice and Husk [1987]. To determine the anaphoricity for the remaining pronouns (this, that and which), we learned a classifier with the following features: (a) Pronoun under consideration (this, that or which), (b) Partof-Speech tag of pronoun and (c) Number of tokens in the immediate noun phrase encompassing the pronoun.

6.2 Finding the Antecedent

In the previous step, we filtered out the pronouns which were non-referential. For the remaining pronouns, we need to find the best antecedent. Depending on the pronoun under consideration, we used different techniques for finding the antecedent as described below.

which and that Referential cases of pronouns which and that behave quite similarly. Therefore, we use the same strategy for determining their antecedents. Both these pronouns are often used as a relative pronoun and they mark the beginning of a dependent clause. We select the closest medical mention in the associated independent clause as the antecedent for such pronouns. However, if there is any intervening noun phrase between the pronoun and the closest medical mention, then we leave such a pronoun as a singleton and mark its antecedent as NULL. It should be clear from the above description that we restrict the antecedent of pronouns which and that to come from the same sentence.

this and it For pronouns which and that, we could simply select the closest medical mention (subject to some constraints) as the antecedent. However, the antecedent of this and it can be separated from them by one or more medical mentions. Thus, antecedent of these pronouns is not necessarily in the same sentence.

To determine the antecedent of pronouns this and it, we trained an SVM classifier to identify whether the pronoun under consideration is being used as a test, treatment or problem. Thus, this classifier has 3 possible outputs: TEST, TRE or PROB. The features used for training this classifier are: (a) Pronoun under consideration (this or it), (b) Verb in the associated clause, (c) Is pronoun acting as a subject or an object,

(d) Is there a preposition in the path from pronoun to its associated verb and (e) Part-of-Speech of pronoun.

Finally, we selected the closest medical mention which satisfied the following criteria as the antecedent for pronouns this and it:

1. The antecedent should either be in the preceding sentence or, if it is in the same sentence, it should be separated from pronoun by a conjunction (and, but, although etc.).
2. The antecedent should have the same type (TEST, TRE or PROB) as the pronoun (as given by SVM classifier).

7 Experimental Setup

Datasets: For our experiments, we used the coreference datasets made available by the i2b2 team as part of 2011 i2b2 shared task. The datasets consist of EHRs from two different organizations: Partners HealthCare (Part) and Beth Israel Deaconess Medical Center (Beth). All records have been fully de-identified and manually annotated for coreference.

The total number of documents in the training set of Part and Beth are 136 and 115 respectively. The test set of Part and Beth contains 94 and 79 documents respectively. Total number of mentions in Part and Beth datasets are 28857 and 40185 respectively. For more information about the datasets, please refer to Uzuner et al. [2012] or Bodnari et al. [2012]. We used B-cubed [Bagga and Baldwin, 1998], MUC [Vilain et al., 1995] and CEAF [Luo, 2005] as the evaluation metrics in our experiments. We also report the unweighted average of F1 scores of these 3 metrics because it was the official metric in i2b2 coreference challenge.

Choice of Parameters: We use cross-validation to determine the system parameters. In Equation (1), we set k = 100. With this choice of k, distance term becomes significant only if the scores given by pairwise classifier for different mention pairs differ by less than 0.01. Threshold parameter δ is chosen to be 0.5. As far as constraints are concerned, we decided to formulate all our constraints as hard constraints. To formulate all our constraints as hard constraints, we chose pl = 1.0 in Equation (2) for all values of l.

8 Results

Table 1 compares the performance of four systems as described below:

1. Baseline (B): Baseline systemuses only the baseline features described in §4.1. It does not perform pronominal resolution and also does not use any constraints.
2. Baseline + Knowledge (BK): This system uses all the features described in §4. In other aspects, it is similar to Baseline system.
3. Baseline + Knowledge + Pronouns (BKP): This system adds pronominal resolution to BK system.
4. Baseline + Knowledge + Pronouns + Constraints (BKPC): This is the final system. It adds the ability to deal with constraints to the BKP system.

In Table 1, we compare the performance of these 4 systems for TEST, TRE and PROB categories on Part corpus. We don't show the detailed results for Beth corpus because of space limitations. But it follows a very similar trend. Table 1 reports precision (P), recall (R) and F1 scores for MUC, B-cubed and CEAF evaluation metrics. It also shows the average F1 score of these three metrics. Please note that there are no separate scores for PRON category because there are no separate PRON chains. PRON mentions are included within the TEST, TRE and PROB chains.

It is interesting to note that adding knowledge to the system always leads to higher recall values. On the other hand, addition of constraints always leads to higher precision values. Next, we note that different metrics behave differently in evaluating the performance of the systems. It can be seen that the B-cubed metric gives the highest scores. Even for Baseline system, B-cubed metric gives about 95% F1 score. This is because of the fact that the corpora that we used contain a very large number of singletons. B-cubed gives very high scores because it highly awards the correct prediction of singletons. MUC, on the other hand, is totally insensitive to singletons. CEAF is intermediate between B-cubed and MUC as far as singletons are concerned. From this discussion, we can see that B-cubed metric is not very discriminative for our corpora. But MUC and CEAF are quite good for comparing the performance of different systems. Average F1 score shown in Table 1 is the official metric used in i2b2 shared task and is a good indicator of the performance of the system. Next, we note the following major points about each category of mentions.

Test: We do not use the features derived from domainspecific knowledge sources for TEST mentions because coreferring mentions of TEST type tend to have similar surface forms. So, knowledge-based features are not helpful for TEST mentions. In Table 1, we see from average F1 score that constraints and pronominal resolution are very helpful for TEST mentions. The average F1 score jumps from 73.6 to 78.7 on adding pronouns to baseline system. On further addition of constraints, average F1 jumps from 78.7 to 84.0 (an increase of 5.3 F1 points).

Treatment: Just as in the case for TEST mentions, we don't use features derived from domain-specific knowledge sources for TRE mentions as well. Average F1 score shows that pronominal resolution gives small improvement of 0.2 F1 points for TRE mentions.

Problem: For PROB mentions, both knowledge and constraints were used. The average F1 scores in Table 1 show that PROB mentions benefit significantly from knowledge, pronouns and constraints. Average F1 score goes from 84.3 to 84.9 on adding knowledge to baseline system. It further increases to 86.0 and then to 86.9 on adding pronominal resolution and constraints respectively.

The improvements obtained by adding knowledge, pronominal resolution and constraints shown in Table 1 are statistically significant at p = 0.05 (indicated by dagger sign (†)) according to Bootstrap Resampling Test [Koehn, 2004]. The only exception to this is the TRE category which didn't get significant improvement by the addition of constraints.

Finally, in Table 2, we compare our system with several other state-of-the-art systems for coreference resolution in the medical domain. The numbers reported in Table 2 refer to the unweighted average of B-cubed, MUC and CEAF F1 scores. We chose unweighted average for comparison because it was the official metric of i2b2 2011 shared task on coreference. For both Part and Beth corpora, our system outperformed all other systems. Xu et al. [Xu et al., 2012b] got the highest scores in i2b2 2011 shared task on coreference. We can see from Table 2 that for TEST and TRE categories, we got significantly higher scores than Xu et al. for both Part and Beth corpora. In particular, we improved over Xu et al.'s score by 1.3 and 0.7 F1 points respectively for TEST and TRE categories (when averaged over both Part and Beth corpora). This improvement is statistically significant at p = 0.05 (indicated by dagger sign (†)) according to Bootstrap Resampling Test. For PROB category, we got an improvement of 0.1 F1 points for Part corpus. But it is not statistically significant. For PROB category in Beth corpus, our score is similar to that of Xu et al. As far as other systems [Jindal and Roth, 2012; Dai et al., 2012; Gooch and Roudsari, 2012] are concerned, our scores are much higher than theirs for all mention categories and all the differences are statistically significant at p = 0.05. Thus, we report the best results on the i2b2 shared task corpora.

9 End-to-End Coreference Resolution

In this section, we describe our approach for end-to-end coreference resolution. To perform end-to-end coreference resolution, we first identify mention boundaries along with mention types. We used a CRF model [Lafferty et al., 2001] to perform mention detection. CRF model used BIO encoding for representing chunks and was implemented using MALLET toolkit [McCallum, 2002]. The features used by CRF model include surface forms of words, part-ofspeech labels, shallow parse labels and features derived from MetaMap. We also used conjunction of these features. Once we have the mentions along with their types, we perform coreference resolution in the same way as described in §3 to §6.

For evaluating the end-to-end coreference resolution system, we used the script provided by i2b2 2011 challenge organizers. Table 3 shows the performance of our final system for end-to-end coreference resolution. It reports precision (P), recall (R) and F1 scores for MUC, B-cubed and CEAF evaluation metrics. It also shows the average F1 score of these 3 metrics. This table shows the results for TEST, TRE and PROB categories on both Part and Beth corpora. As far as we know, end-to-end results have not been reported previously on both these corpora. By comparing the average F1 scores in Tables 1 and 3, we notice that the scores of our final system are about 5-8% lower for end-to-end task than the task where gold mentions were given. The decrease in performance is because of errors made in mention detection. However, it is very encouraging to see that the performance on the end-to-end task is still quite high. For example, on Part dataset, the average F1 score is higher than 79% for all the categories (TEST, TRE and PROB). This is much higher than the best result of 63.4% F1 in CoNLL 2012 shared task on coreference [Pradhan et al., 2012]. Zheng et al. [2012] performed end-to-end coreference resolution on ODIE corpus. However, their average F1 score is quite low (50.9%).

Conclusion

This paper studied the problem of coreference resolution on clinical narratives. We reported the best results on the datasets used by us. This is attributed to better pronominal resolution and the use of constraints. Our successful use of constraints highlights the importance of the context in which the mentions appear. Our method for pronominal resolution is quite general and would benefit other types of text as well. Finally, we also report results on end-to-end coreference resolution.

Acknowledgments

We would like to thank the anonymous reviewers for their valuable suggestions. This research was supported by Grant HHS 90TR0003/01. Its contents are solely the responsibility of the authors and do not necessarily represent the official views of the HHS or the US government.