We describe our approach for the extraction of drug-drug interactions from literature. The proposed method builds majority voting ensembles of contrasting machine learning methods, which exploit different linguistic feature spaces. We evaluated our approach in the context of the DDI Extraction 2011 challenge, where using document-wise crossvalidation, the best single classifier achieved an F1 of 57.3 % and the best ensemble achieved 60.6 %. On the held out test set, our best run achieved an F1 of 65.7 %.
Most biomedical knowledge appears first as research results in scientific publications before it is distilled into structured knowledge bases. For researchers and database curators there is an urgent need to cope with the fast increase of biomedical literature [6]. Biomedical text mining currently achieves good results for named entity recognition (NER), e.g. gene/protein-names and recognition of single nucleotide polymorphisms [3,11]. A recent trend is the extraction of simple or complex relations between entities [7].
In this work, we describe our approach for the extraction of drug-drug interactions (DDI) from text that was also the core task of the DDI Extraction 2011 challenge 1 . DDIs describe the interference of one drug with another drug and usually lead to an enhanced, reduced, neutralized, or even toxic drug effect. For example: "Aspirin administered in combination with Warfarin can lead to bleeding and has to be avoided." DDI effects are thus crucial to decide when (not) to administer specific drugs to patients.
The DDI challenge 1 consisted of one task, namely the identification of interactions between two drugs. This interaction is binary and undirected, as target and agent roles are not labeled. In the challenge setting, recognition of drug names was readily available.
Binary relation extraction is often tackled as a pair-wise classification problem between all entities mentioned within one sentence. Thus a sentence with n entities contains at most n 2 interacting pairs. Corpus annotations have been made available in two different formats. (1) contained only the documents with respective drug annotations in a format previously used for protein-protein interactions (PPIs) [13]. (2) additionally contained linguistic information such as part-of-speech tags and shallow parses. Further phrases were annotated with corresponding UMLS concepts. This information has been automatically derived using MetaMap and incorporated by the organizers. We exclusively used (1) and extended it with linguistic information as described in the following subsection.
Sentences have been parsed using Charniak-Lease parser [8] with a self-trained re-ranking model augmented for biomedical texts [10]. Resulting constituent parse trees have been converted into dependency graphs using the Stanford converter [4]. In the last step we created an augmented XML following the recommendations of [2]. This XML encompasses tokens with respective part-of-speech tags, constituent parse tree, and dependency parse tree information. Properties of the training and test corpora are shown in Table 1. Please note that the number of positive and negative instances in the test set has been made available after the end of the challenge. A more detailed description of the DDI corpus can be found in [14].
Tikk et al. [17] systematically analyzed 9 different machine learning approaches for the extraction of undirected binary protein-protein interactions. In their analysis, three kernel have been identified of being superior to the remaining six approaches, namely all-paths graph (APG) [2], k -band shortest path spectrum (kBSPS) [17], and the shallow linguistic (SL) [5] kernel. The SL kernel uses only shallow linguistic features, i.e. word, stem, part-of-speech tag and morphologic properties of the surrounding words. kBSPS builds a classifier on the shortest dependency path connecting the two entities. It further allows for variable mismatches and also incorporates all nodes within distance k from the shortest path. APG builds a classifier using surface features and a weighting scheme for dependency parse tree features. For a more detailed description of the kernel we refer to the original publications. The advantage of these three methods has been replicated and validated in a follow up experiment during the i2b2 relation extraction challenge [15]. In the current work we also focus on these three methods.
Experiments have been done using an open-source relation extraction framework. 2 Entities were blinded by replacing the entity name with a generic string to ensure the generality of the approach. Without entity blinding a classifier uses drug names as features, which clearly affects its generalization abilities on unseen entity pairs.
In addition to kernel classifiers, we also used a customized version of Moara, an improvement of the system that participated in the BioNLP'09 Event Extraction Challenge [12]. It uses case-based reasoning (CBR) for classifying the drug pairs. CBR [1] is a machine learning approach that represents data with a set of features. In the training step, first the cases from the training data are learned and then saved in a knowledge base. During the testing step, the same representation of cases is used for the input data, the documents are converted to cases and the system searches the base for cases most similar to the case-problem.
Each drug pair corresponds to one case. This case is represented by the local context, i.e., the tokens between a drug pair. We have limited the size of the context to 20 tokens (pairs separated by more tokens are treated as false). The features may be related to the context as a whole or to each of the tokens that is part of the context. Features may be set as mandatory or optional, here no feature was defined as mandatory. As features we considered part-of-speech tag, role and lemma.
The part-of-speech tag is the one obtained during the pre-processing of the corpus. The role of the token is set to DRUG in case that the token is annotated as drug that takes part in the interaction. No role is set to drugs which are part of the context and are not part of the interaction pair, as well as the remaining tokens. The lemma feature is only assigned for the non-role tokens using the Dragon toolkit [18], otherwise the feature is not set. See Table 2 The lemma drug is the result of entity blinding.
During the searching step, Moara uses a filtering strategy in which it looks for a case with exactly the same values for the features, i.e., it tries to find cases with exactly the same values for the mandatory features and matching as many optional features as possible. For the case retrieved in this step, a similarity between those and the original case is calculated by comparing the values of the corresponding features using a global alignment. This methodology was proposed as part of the CBR algorithm for biomedical term classification in the MaSTerClass system [16]. By default, for any feature, the insertion and deletion costs are 1 (one) and the substitution cost is 0 (zero) for equal features with equal values, and 1 (one) otherwise. However, we have also defined specific costs for the part-of-speech tag feature which were based on the ones used in the MaSTerClass system. We decided to select those cases whose global alignment score is below a certain threshold, automatically defined as proposed in [16]. The final solution, i.e., whether the predicted category is "positive" or "negative", is given by a voting scheme among the similar cases. When no similar case if found for a determined pair, or if the pair was not analyzed at all due to its length (larger than 20), the "negative" category is assigned by default.
Previous extraction challenges showed that combinations of classifiers may achieve better results than any single classifier itself [7,9]. Thus we experimented with different combinations of classifiers by using a majority voting scheme.
In order to compare the different approaches, we performed document-wise 10-fold cross validation on the training set (see Table 3). It has been shown that such a setting provides more realistic performance estimates than instancewise cross validation [2]. All approaches have been tested using the same splits to ensure comparability. For APG, kBSPS, and SL; we followed the parameter optimization strategy described in [17]. Table 3: Document-wise cross-validation results on the training set for selected methods.
For the test set we submitted results for APG, SL, Moara, and the two majority voting ensembles. Results for kBSPS have been excluded, as only 5 submissions were permitted and kBSPS and Moara achieve similar results in F 1 . The official results achieved on the test set are shown Table 4. Single method results are in line with previously published results using these kernel for other domains [15,17]. Again the SL kernel, which uses only shallow linguistic information, achieves considerably good results. This indicates that shallow information is often sufficient for relation extraction.
We estimated the effect of entity blinding by temporarily disabling it. This experiment has been performed for SL exclusively and yielded an increase of 1.7 pp in F 1 . This effect was accompanied by an increase of 3.6 pp in precision and a decrease of 3 pp in recall. We did not disable entity blinding for the submitted runs, as such classifiers would be biased towards known DDIs and less capable of finding novel DDIs, the ultimate goal of DDI extraction.
For the challenge all four classifier have been retrained using the whole training corpus using the parameter setting yielding the highest F 1 in the training phase. Our best run achieved 65.7 % in F 1 .
Between training and test results we observe a perfect correlation for F 1 (Kendall's tau (τ ) of 1.0). Thus the evaluation corpus affirms the general ranking of methods determined on the training corpus. The effect of ensemble learning is less pronounced on the test set but with 2.3 pp still notable.
To have an impression about the errors generated by these classifiers, we manually analyzed drug mention pairs that were not correctly classified by any method (APG, kBSPS, Moara, and SL). Performing cross-validation, the DDI training corpus contained 442 (1.85 %) such pairs, examples are given in Figure 1.
We identified a few situations that may have caused difficulties: issues with the annotated corpus and linguistic constructs not or incorrectly handled by our methods. Annotation inconsistencies we encountered include dubious drug entity annotations (B1, B6 in Figure 1), and ground truth annotations that were either likely incorrect (B3) or could not be verified without the context (A4, B4). As for linguistic constructs, our methods lack co-reference resolution (A1, B5) and negation detection (A6, B7), and they also fail to recognize complex formulations (A5, B2). As a special case, conditional constructs belong to both A1 Probenecid interferes with renal tubular secretion of ciprofloxacin and produces an increase in the level of ciprofloxacin in serum. A2 Drugs which may enhance the neuromuscular blocking action of TRACRIUM include: enflurane; A3 While not systematically studied, certain drugs may induce the metabolism of bupropion (e.g., carbamazepine, phenobarbital, phenytoin). A4 Auranofin should not be used together with penicillamine (Depen, Cuprimine), another arthritis medication. A5 These drugs in combination with very high doses of quinolones have been shown to provoke convulsions A6 Diclofenac interferes minimally or not at all with the protein binding of salicylic acid (20% decrease in binding), tolbutamide, prednisolone (10% decrease in binding), or warfarin.
(a) False negatives groups, they are nor consistently annotated nor consistently classified by our methods (A2, A3, B2). Furthermore, we found several examples that are not affected by any of the above situations.
In this paper we presented our approach for the DDI Extraction 2011 challenge. Primarily, we investigated the re-usability of methods previously proven efficient for relation extraction in other biomedical sub-domains, notably protein-protein interaction (PPI) extraction. In comparison to PPI extraction corpora, the training corpus is substantially larger and also exhibits a higher class imbalance towards negative instances. Furthermore, we experimented with basic ensembles to increase overall performance and conducted a manual error analysis to pinpoint weaknesses in the applied methods. Our best result consisted of a majority voting ensemble of three methodically different classifiers.
PT was supported by German Federal Ministry of Education and Research (grant No 0315417B), MN by German Research Foundation, and DT by Alexander von Humboldt Foundation.