Machine learning approaches based on supervised classification have emerged as effective methods for Biomedical relation extraction such as the Chemical-Induced-Disease (CID) task. These approaches owe their success to a rich set of features crafted from the lexical and syntactic regularities in the text. Kernel methods are an effective alternative to manual feature engineering and have been successfully used in similar tasks such as text classification.
In this paper, we study the effectiveness of tree kernels for Chemical-Disease relation extraction. Our experiments demonstrate that subset tree kernels increase the F-score to 61.7% as compared to 57.9% achieved with simple feature engineering. We also describe the strengths and shortcomings of tree kernel approaches for the CID relation extraction task.
Scientific publications in the fields of biomedical and life sciences are vast and growing fast (Haas et al., 2014). Prior research has shown that Chemicals and Diseases and their relationships are among the most searched topics by PubMed users (Dogan et al., 2009), due to their importance in applications such as toxicology, drug discovery and safety surveillance. Efforts to manually curate and extract these important concepts such as Chemicals and Diseases and their relationships have led to the creation of structured databases such as the Comparative Toxicogenomics Database (CTD) (Davis et al., 2012). However, manual curation is unlikely to scale (Baumgartner et al., 2007) and has stimulated research interest in automated relation extraction.
The recent shared task for Chemical-Induced-Disease relation extraction (CID) organized by BioCreative-V (Wei et al., 2015), has made available a large body of annotated PubMed abstracts for the valuable Chemical-Disease relations. The shared task revealed that CID relation extraction is a difficult task with best reported systems achieving an F-score of about 57%. Study of the participating teams' approaches reveals that most approaches (14 out of 18) were based on Support Vector Machines (SVMs) (Burges, 1998), modeling relation extraction as a supervised classification problem. Most of these systems obtain their performance through a rich feature set that is manually crafted by studying the syntactic and lexical regularities in the text. Substantial performance boost is also drawn from custom heuristics such as postprocessing rules (Zhou et al., 2016). Designing such an effective relation extraction system involves extensive feature engineering and domain expertise.
Kernel methods in NLP (Collins and Duffy, 2001) have been designed precisely to address this problem of manual feature engineering. These methods enable an efficient and comprehensive exploration of a very high dimensional feature space and to automatically adapt to the dominant patterns expressed in the training set.
In our work, we show that kernel methods can be used for boosting relation extraction performance without having to manually engineer additional features. We demonstrate through experiments that combining tree kernels over constituent parses with simple lexical and syntactic features can substantially enhance the performance of the CID task. We also discuss the strengths and weaknesses of these methods which can assist in the design of better methods in the future.
Our system is developed in the context of the CID subtask described in BioCreative-V (Wei et al., 2015). Many teams, including the top scoring team (Wei et al., 2015), model the CID task as a supervised binary classification problem. In addition to the annotated PubMed abstracts, alternate sources of information such as the Chemical Toxicology Database (CTD) (Davis et al., 2012) were used. Similar biomedical relation extraction tasks that have been studied are drug-drug interaction (Bjorne et al., 2011) and protein-protein interaction (Lan et al., 2009). A subsequence kernel was presented by (Bunescu and Mooney, 2005) for protein-protein interaction extraction. Richer kernels that use constituent parses or dependency structures are studied in (Chowdhury et al., 2011;Airola et al., 2008) for the protein-protein interaction extraction. Recent approaches have focused on broadening the scope of word matching from a simple lexical match to more complex semantic matching (Saleh et al., 2014). The suitability of these methods for the CID task remains to be explored.
Our goal is to minimize task specific and domain specific feature engineering. We therefore explore the power of domain independent techniques such as kernel methods for effective relation extraction. Kernel methods automatically explore a large feature space and can reduce the need for rich hand crafted features. In our system, we do not employ any preprocessing or custom filtering techniques. We use simple text based features and a knowledge base (CTD) look up as our primary feature set. Further knowledge extraction from text is accomplished through tree kernels.
We cast the CID relation extraction as a binary classification problem. The input to the classifier is a pair of chemical and disease mentions. From the set of predicted relation mentions, we extract their normalized entity ids (MeSH Ids) and add it to the final list of Chemical-Disease relations. We built and tested two types of classifiers, namely linear classifier and tree kernel classifier. The linear classifier uses a flat list of simple features. The tree kernel classifier uses kernel methods over constituent parse trees of input sentences. The detailed steps are described below: We used a Support Vector Machine (SVM) with linear kernel from Scikit (Pedregosa et al., 2011) to classify candidate entity pairs. The predicted (C-D) pairs from the sentence level and document level classifiers are combined to form the final list of document level CID relations. We refer to this system as "Linear Classifier".
Kernel methods have gained wide spread acceptance, because they allow direct computation of similarity (dot product) between two examples in an implicitly mapped high dimensional Entity focus is incorporated by prefixing special tags such as "pre", "mid", "post", "Chemical" and "Disease". . space (Collins and Duffy, 2001;Zelenko et al., 2002). A tree kernel implicitly maps a given tree into a very high dimensional feature space of tree fragments, as illustrated with an example in Figure 1. The kernel score between two trees is the count of common tree fragments between them. We used tree kernels over constituent parse trees of sentences, to efficiently compute the syntactic similarity between two sentences. Different variants of the tree kernels are proposed based on what constitutes a tree fragment, such as subtrees or subsets of nodes. Efficient algorithms with linear time complexity in the average case are presented in (Moschitti, 2006b). The formal definition of the tree kernel is discussed below.
Given two trees T 1 and T 2 and the set of all possible tree fragments F = {f 1 , f 2 , . . .}, an indicator function I i (n) is defined which evaluates to 1 if the fragment f i is rooted at node n and 0 other-wise. The unnormalized kernel score is given by
where N T 1 and N T 2 are the sets of nodes of T 1 and T 2 respectively and ∆(n1, n2) = |F | i=1 I i (n 1 )I i (n 2 ). The normalized kernel score is given by
We experimented with subtree and subset tree kernels over constituent parse trees and found subset tree kernels to be superior for our task. In the rest of the paper, we mean subset tree kernel when we refer to tree kernels. We used Stanford CoreNLP (Manning et al., 2014) to generate the constituent parse trees. For tree kernels we use the SVM-LIGHT-TK toolkit1 (Moschitti, 2006a) that offers kernel implementation within SVM2 (Joachims, 1999). For each intrasentence (C-D) pair we get a single parse tree and for each intersentence pair we get a forest of two constituent parse trees, from each sentence containing one of the two entity mentions.
The contribution from flat features as defined in the section 3.1 can be combined with tree kernels by linearly combining the dot products of the flat feature vectors and the tree kernel. That is, the kernel for the new classifier (linear + tree kernel) is computed as the sum of the linear kernel over flat features and the tree kernel over the constituent parse trees. We report results for these classifiers, namely Linear, Tree Kernel and Linear + Tree Kernel classifier in Section 4.
Tree kernels attempt to classify a sentence in its entirety and in its default form are unaware of the entity mentions in the sentence. This approach is suitable if our goal is to simply detect if a sentence expresses a relation or not. However, to render greater focus on the entity mentions, we can preprocess the sentence to highlight the location of a word with reference to entity mentions. We prefixed all words in the sentence with "pre", "mid", and "post" tags, based on whether they are located prior to, in between, or post entity mentions, before generating the constituent parse trees.
We work with the dataset provided by BioCreative-V (Wei et al., 2015). It comprises 3 subsets, referred to as training, development and test set. Each subset consists of 500 PubMed articles (Title and Abstract only), that are fully annotated with Chemical and Disease mentions and the CID relations. Our goal is to extract Chemical-Disease relations at the document (PubMed abstract) level and the metrics are standard Precision (P), Recall (R) and F1 measure ( 2P R P +R ).
We measure the effectiveness of our relation extraction system over the provided test data set, as set out in the CID task. We use the standard entity annotations provided with the data set. Given the limited annotated data, we decided to use both the training and development data set for classifier training with default settings and no custom parameter tuning. Results for intersentence, intrasentence and the full set of (C-D) pairs are presented for linear classifier, tree kernel classifier and their combination, in Table 1. We also present the results for the Linear classifier without the CTD feature. Finally, the table also contains the results reported in a prior work by (Zhou et al., 2016) for the CID task. A comparative study with this prior work is presented in Section 5.
To summarize, our final system (linear + tree kernel) achieves an F-score of 61.7% over the CID test data. Note that the combination of linear and tree kernels outperforms the linear and tree kernel classifiers individually. The Table also reveals the substantial contribution of the CTD look up feature towards the linear classifier's performance.
Comparison with prior art. Previously published results in the CID BioCreative-V task used custom entity recognition tools. Therefore, their CID performance is not directly comparable without replicating their entity annotation process. A more accurate comparison can be made with (Zhou et al., 2016) who follow a similar evaluation process. Their system uses gold standard entity annotations and is trained on the CID training and development datasets and evaluated on the CID test data. They report an F-score of 61.3%. Significantly, their system relies on task specific post-processing rules, without which their F1 score drops to 56.0%. Our system performs better (61.7%), reflecting a substantive advantage in precision, without using heuristics or task specific rules.
Effectiveness of Tree Kernels. We note that tree kernels can significantly improve the performance of CID relation extraction as illustrated in the results. Also, this additional performance is obtained using PubMed abstracts and not external information sources. These results suggest that a greater amount of information exists in annotated text that is easier to extract with tree kernels as compared to manual feature mining for richer patterns. Further, tree kernels have an effect of increasing the precision of the classifiers, specially for intersentence cases. This is likely due to the fact that tree kernels enable stringent comparison of sentence structures (constituent parse trees) as compared to the lenient approach of bag of words matching with linear kernels.
Further enhancements. Incorporating entity focus to tree kernels (section 3.2.1) produced a slight improvement (to 61.7% from 61.0%). This approach is likely to be beneficial for sentences that express multiple relations (> 1) between multiple entity pairs. In the CID dataset, we found that sentences expressing multiple relations constitute around 14%, 15% and 14% of training, development and test datasets respectively. Alternate approaches that discriminate parts of the sentence based on the relation expressed are likely to further improve the performance.
In the context of intersentence (C-D) pairs, we are currently using only the two sentences s i , s j that contain the entity mentions. However, the actual relationship might be collectively expressed by any subset of the sentences in the document. We attempted to model the whole of the document as a forest of parse trees of all its sentences, but did not observe any improvement in performance. For the CID task where more than 30% of the (C-D) pairs cross sentence boundaries, effective intersentence relation extraction remains a challenge.
In this work, we show that tree kernels were very effective in CID relation extraction and boosted F1 score to 61.7% as compared to 57.9% achieved with a linear classifier using simple handcrafted features alone. In future work, we seek to improve intersentence relation extraction from documents.