Exploiting Tree Kernels for High Performance Chemical Induced Disease Relation Extraction Nagesh C. Panyam, Karin Verspoor, Trevor Cohn and Kotagiri Ramamohanarao Department of Computing and Information Systems, The University of Melbourne, Australia npanyam@student.unimelb.edu.au {karin.verspoor, t.cohn, kotagiri}@unimelb.edu.au Abstract The recent shared task for Chemical-Induced- Disease relation extraction (CID) organized by Machine learning approaches based on su- BioCreative-V (Wei et al., 2015), has made avail- pervised classification have emerged as ef- able a large body of annotated PubMed abstracts fective methods for Biomedical relation for the valuable Chemical-Disease relations. The extraction such as the Chemical-Induced- shared task revealed that CID relation extraction is Disease (CID) task. These approaches a difficult task with best reported systems achiev- owe their success to a rich set of features ing an F-score of about 57%. Study of the par- crafted from the lexical and syntactic reg- ticipating teams’ approaches reveals that most ap- ularities in the text. Kernel methods are an proaches (14 out of 18) were based on Support effective alternative to manual feature en- Vector Machines (SVMs) (Burges, 1998), model- gineering and have been successfully used ing relation extraction as a supervised classifica- in similar tasks such as text classification. tion problem. Most of these systems obtain their In this paper, we study the effectiveness performance through a rich feature set that is man- of tree kernels for Chemical-Disease rela- ually crafted by studying the syntactic and lexical tion extraction. Our experiments demon- regularities in the text. Substantial performance strate that subset tree kernels increase the boost is also drawn from custom heuristics such as F-score to 61.7% as compared to 57.9% postprocessing rules (Zhou et al., 2016). Design- achieved with simple feature engineering. ing such an effective relation extraction system in- We also describe the strengths and short- volves extensive feature engineering and domain comings of tree kernel approaches for the expertise. CID relation extraction task. Kernel methods in NLP (Collins and Duffy, 1 Introduction 2001) have been designed precisely to address this Scientific publications in the fields of biomedical problem of manual feature engineering. These and life sciences are vast and growing fast (Haas methods enable an efficient and comprehensive et al., 2014). Prior research has shown that exploration of a very high dimensional feature Chemicals and Diseases and their relationships are space and to automatically adapt to the dominant among the most searched topics by PubMed users patterns expressed in the training set. (Dogan et al., 2009), due to their importance in ap- plications such as toxicology, drug discovery and In our work, we show that kernel methods can safety surveillance. Efforts to manually curate and be used for boosting relation extraction perfor- extract these important concepts such as Chem- mance without having to manually engineer addi- icals and Diseases and their relationships have tional features. We demonstrate through experi- led to the creation of structured databases such ments that combining tree kernels over constituent as the Comparative Toxicogenomics Database parses with simple lexical and syntactic features (CTD) (Davis et al., 2012). However, manual can substantially enhance the performance of the curation is unlikely to scale (Baumgartner et al., CID task. We also discuss the strengths and weak- 2007) and has stimulated research interest in auto- nesses of these methods which can assist in the mated relation extraction. design of better methods in the future. 2 Related Work 3.1 Linear classifier 1. Every chemical mention (C) that appears in Our system is developed in the context of the CID the article is paired with every other disease subtask described in BioCreative-V (Wei et al., mention (D) to generate an entity pair (C-D) 2015). Many teams, including the top scoring for classification. An entity pair in which team (Wei et al., 2015), model the CID task as a both the entity mentions are within a sen- supervised binary classification problem. In ad- tence are referred to as intrasentence pairs, dition to the annotated PubMed abstracts, alter- and those that cross a sentence boundary are nate sources of information such as the Chemical referred to as intersentence pairs. The full test Toxicology Database (CTD) (Davis et al., 2012) data is the union of intrasentence and inter- were used. Similar biomedical relation extraction sentence entity pairs. tasks that have been studied are drug-drug inter- 2. Intersentence and intrasentence pairs are action (Bjorne et al., 2011) and protein-protein in- grouped separately for training and testing teraction (Lan et al., 2009). A subsequence kernel with two separate classifiers. No further fil- was presented by (Bunescu and Mooney, 2005) tering or post-processing of (C-D) pairs is for protein-protein interaction extraction. Richer performed. kernels that use constituent parses or dependency 3. At training time, we label a (C-D) pair as pos- structures are studied in (Chowdhury et al., 2011; itive if there exists a valid CID relation be- Airola et al., 2008) for the protein-protein interac- tween these entities, using the relation anno- tion extraction. Recent approaches have focused tations. At test time, the label is inferred from on broadening the scope of word matching from the classifier output. a simple lexical match to more complex semantic 4. Features for intrasentence pairs include matching (Saleh et al., 2014). The suitability of verbs, bag of words, POS tags, dependency these methods for the CID task remains to be ex- parse and the token distance between entity plored. mentions in the sentence. 5. Features for intersentence pairs include the 3 Approach POS tags and bag of words of the two sen- tences containing entity mentions, distance Our goal is to minimize task specific and domain (number of sentences) between them, statisti- specific feature engineering. We therefore explore cal features of the entity mentions in the doc- the power of domain independent techniques such ument (frequency of mentions), entity fre- as kernel methods for effective relation extraction. quencies and zonal information (document Kernel methods automatically explore a large fea- zone containing the mentions). ture space and can reduce the need for rich hand 6. We use the Chemical Toxicology crafted features. In our system, we do not employ Database (Davis et al., 2012) to gener- any preprocessing or custom filtering techniques. ate a binary feature Ictd (C, D) that evaluates We use simple text based features and a knowl- to 1 if the (C-D) pair is known to be related edge base (CTD) look up as our primary feature in the CTD database and 0 otherwise. set. Further knowledge extraction from text is ac- complished through tree kernels. We used a Support Vector Machine (SVM) with We cast the CID relation extraction as a binary linear kernel from Scikit (Pedregosa et al., 2011) classification problem. The input to the classifier to classify candidate entity pairs. The predicted is a pair of chemical and disease mentions. From (C-D) pairs from the sentence level and document the set of predicted relation mentions, we extract level classifiers are combined to form the final list their normalized entity ids (MeSH Ids) and add it of document level CID relations. We refer to this to the final list of Chemical-Disease relations. We system as “Linear Classifier”. built and tested two types of classifiers, namely linear classifier and tree kernel classifier. The lin- 3.2 Tree Kernel Classifier ear classifier uses a flat list of simple features. The Kernel methods have gained wide spread ac- tree kernel classifier uses kernel methods over con- ceptance, because they allow direct computation stituent parse trees of input sentences. The de- of similarity (dot product) between two exam- tailed steps are described below: ples in an implicitly mapped high dimensional (a) Full constituent parse tree. wise. The unnormalized kernel score is given by S X X k 0 (T1 , T2 ) = ∆(n1, n2) n1 ∈NT1 n2 ∈NT2 NP VP where NT1 and NT2 are the sets of nodes of T1 and T2 respectively and ∆(n1, n2) = JJ NN VBN PP P|F | i=1 Ii (n1 )Ii (n2 ). The normalized kernel score Cyclic dysosmia is given by induced IN NP Pre Disease mid k 0 (T1 , T2 ) by NN K(T1 , T2 ) = p k 0 (T1 , T1 ) · k 0 (T2 , T2 ) mid PZA We experimented with subtree and subset tree Chemical kernels over constituent parse trees and found sub- (b) Few of its fragments (subset trees). set tree kernels to be superior for our task. In VP PP NN the rest of the paper, we mean subset tree ker- nel when we refer to tree kernels. We used Stan- VBN PP IN NP dysosmia ford CoreNLP (Manning et al., 2014) to gener- ate the constituent parse trees. For tree kernels by NN we use the SVM-LIGHT-TK toolkit1 (Moschitti, PZA 2006a) that offers kernel implementation within SVM2 (Joachims, 1999). For each intrasentence Figure 1: Illustration for the sentence “Cyclic (C-D) pair we get a single parse tree and for each dysosmia induced by PZA (Pyrazinamide)”: a) intersentence pair we get a forest of two con- Full constituent parse tree. b) Few of its fragments stituent parse trees, from each sentence containing (implicitly) considered by the subset tree kernel. one of the two entity mentions. Entity focus is incorporated by prefixing special The contribution from flat features as defined in tags such as “pre”, “mid”, “post”, “Chemical” and the section 3.1 can be combined with tree kernels “Disease”. 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 space (Collins and Duffy, 2001; Zelenko et al., flat features and the tree kernel over the constituent 2002). A tree kernel implicitly maps a given tree parse trees. We report results for these classifiers, into a very high dimensional feature space of tree namely Linear, Tree Kernel and Linear + Tree Ker- fragments, as illustrated with an example in Fig- nel classifier in Section 4. ure 1. The kernel score between two trees is the 3.2.1 Tree kernels with entity focus count of common tree fragments between them. Tree kernels attempt to classify a sentence in its We used tree kernels over constituent parse trees entirety and in its default form are unaware of the of sentences, to efficiently compute the syntactic entity mentions in the sentence. This approach is similarity between two sentences. Different vari- suitable if our goal is to simply detect if a sentence ants of the tree kernels are proposed based on what expresses a relation or not. However, to render constitutes a tree fragment, such as subtrees or greater focus on the entity mentions, we can pre- subsets of nodes. Efficient algorithms with linear process the sentence to highlight the location of a time complexity in the average case are presented word with reference to entity mentions. We pre- in (Moschitti, 2006b). The formal definition of fixed all words in the sentence with “pre”, “mid”, the tree kernel is discussed below. and “post” tags, based on whether they are located Given two trees T1 and T2 and the set of all pos- prior to, in between, or post entity mentions, be- sible tree fragments F = {f1 , f2 , . . .}, an indica- fore generating the constituent parse trees. tor function Ii (n) is defined which evaluates to 1 1 http://disi.unitn.it/moschitti/Tree-Kernel.htm 2 if the fragment fi is rooted at node n and 0 other- http://svmlight.joachims.org/ 4 Evaluation Test Data Classifier P R F1 Intrasentence Lin - CTD 54.1 71.5 61.6 4.1 Dataset and Evaluation metrics Intrasentence Lin 58.2 75.6 65.8 We work with the dataset provided by Intrasentence TK 55.7 53.6 54.6 BioCreative-V (Wei et al., 2015). It comprises Intrasentence Lin + TK 63.3 75.4 68.8 3 subsets, referred to as training, development Intersentence Lin - CTD 26.9 35.1 30.4 and test set. Each subset consists of 500 PubMed Intersentence Lin 33.7 39.8 36.5 articles (Title and Abstract only), that are fully Intersentence TK 53.8 2.3 4.5 annotated with Chemical and Disease mentions Intersentence Lin + TK 65.9 20.0 30.8 and the CID relations. Our goal is to extract Full test Lin - CTD 46.5 61.3 52.9 Chemical-Disease relations at the document Full test Lin 57.8 65.6 57.9 (PubMed abstract) level and the metrics are Full test TK 55.7 39.2 46.0 standard Precision (P), Recall (R) and F1 measure Full test Lin + TK 63.6 59.8 61.7 ( P2P+R R ). (Zhou et Full test 55.6 68.4 61.3 al., 2016) 4.2 Results We measure the effectiveness of our relation ex- Table 1: Results on CID test data for Linear classi- traction system over the provided test data set, as fier (Lin), Tree Kernel (TK) and their combination set out in the CID task. We use the standard en- (Lin+TK). The performance of the linear classifier tity annotations provided with the data set. Given without CTD feature (Lin - CTD) is also shown. the limited annotated data, we decided to use both the training and development data set for clas- the CID test data. They report an F-score of sifier training with default settings and no cus- 61.3%. Significantly, their system relies on task tom parameter tuning. Results for intersentence, specific post-processing rules, without which their intrasentence and the full set of (C-D) pairs are F1 score drops to 56.0%. Our system performs presented for linear classifier, tree kernel classi- better (61.7%), reflecting a substantive advantage fier and their combination, in Table 1. We also in precision, without using heuristics or task spe- present the results for the Linear classifier without cific rules. the CTD feature. Finally, the table also contains the results reported in a prior work by (Zhou et al., Effectiveness of Tree Kernels. We note that tree 2016) for the CID task. A comparative study with kernels can significantly improve the performance this prior work is presented in Section 5. of CID relation extraction as illustrated in the re- To summarize, our final system (linear + tree sults. Also, this additional performance is ob- kernel) achieves an F-score of 61.7% over the CID tained using PubMed abstracts and not external test data. Note that the combination of linear and information sources. These results suggest that a tree kernels outperforms the linear and tree kernel greater amount of information exists in annotated classifiers individually. The Table also reveals the text that is easier to extract with tree kernels as substantial contribution of the CTD look up fea- compared to manual feature mining for richer pat- ture towards the linear classifier’s performance. terns. Further, tree kernels have an effect of in- creasing the precision of the classifiers, specially 5 Discussion for intersentence cases. This is likely due to the fact that tree kernels enable stringent comparison Comparison with prior art. Previously pub- of sentence structures (constituent parse trees) as lished results in the CID BioCreative-V task used compared to the lenient approach of bag of words custom entity recognition tools. Therefore, their matching with linear kernels. CID performance is not directly comparable with- out replicating their entity annotation process. Further enhancements. Incorporating entity A more accurate comparison can be made with focus to tree kernels (section 3.2.1) produced a (Zhou et al., 2016) who follow a similar evalua- slight improvement (to 61.7% from 61.0%). This tion process. Their system uses gold standard en- approach is likely to be beneficial for sentences tity annotations and is trained on the CID train- that express multiple relations (> 1) between mul- ing and development datasets and evaluated on tiple entity pairs. In the CID dataset, we found that sentences expressing multiple relations con- of Protein-Protein Interaction. BioNLP 2011, stitute around 14%, 15% and 14% of training, de- (2011):124–133. velopment and test datasets respectively. Alternate Michael Collins and Nigel Duffy. 2001. Convolution approaches that discriminate parts of the sentence kernels for natural language. In Advances in neural based on the relation expressed are likely to fur- information processing systems, pages 625–632. ther improve the performance. In the context of intersentence (C-D) pairs, we Allan Peter Davis, Cynthia Grondin Murphy, Robin Johnson, Jean M Lay, Kelley Lennon-Hopkins, Cyn- are currently using only the two sentences si , sj thia Saraceni-Richards, Daniela Sciaky, Benjamin L that contain the entity mentions. However, the ac- King, Michael C Rosenstein, Thomas C Wiegers, tual relationship might be collectively expressed et al. 2012. The comparative toxicogenomics by any subset of the sentences in the document. database: update 2013. Nucleic acids research, page We attempted to model the whole of the document gks994. as a forest of parse trees of all its sentences, but Rezarta Islamaj Dogan, G Craig Murray, Aurélie did not observe any improvement in performance. Névéol, and Zhiyong Lu. 2009. Understanding For the CID task where more than 30% of the (C- pubmed R user search behavior through log analy- D) pairs cross sentence boundaries, effective inter- sis. Database, 2009:bap018. sentence relation extraction remains a challenge. Laura Haas, Melissa Cefkin, Cheryl Kieliszewski, Wil Plouffe, and Mary Roth. 2014. The ibm research 6 Summary and Conclusion accelerated discovery lab. SIGMOD Rec., 43(2):41– 48, December. In this work, we show that tree kernels were very effective in CID relation extraction and boosted F1 Thorsten Joachims. 1999. Advances in kernel meth- score to 61.7% as compared to 57.9% achieved ods. chapter Making Large-scale Support Vector with a linear classifier using simple handcrafted Machine Learning Practical, pages 169–184. MIT features alone. In future work, we seek to improve Press, Cambridge, MA, USA. intersentence relation extraction from documents. Man Lan, Chew Lim Tan, and Jian Su. 2009. Feature generation and representations for protein-protein interaction classification. Journal of Biomedical In- References formatics, 42:866–872. Antti Airola, Sampo Pyysalo, Jari Björne, Tapio Pahikkala, Filip Ginter, and Tapio Salakoski. 2008. Christopher D Manning, Mihai Surdeanu, John Bauer, A graph kernel for protein-protein interaction ex- Jenny Finkel, Steven J Bethard, and David Mc- traction. In Proceedings of the workshop on current Closky. 2014. The stanford corenlp natural lan- trends in biomedical natural language processing, guage processing toolkit. In Proceedings of 52nd pages 1–9. Association for Computational Linguis- Annual Meeting of the Association for Computa- tics. tional Linguistics: System Demonstrations, pages 55–60. William A Baumgartner, K Bretonnel Cohen, Lynne M Fox, George Acquaah-Mensah, and Lawrence Alessandro Moschitti. 2006a. Efficient convolution Hunter. 2007. Manual curation is not sufficient for kernels for dependency and constituent syntactic annotation of genomic databases. Bioinformatics, trees. In Machine Learning: ECML 2006, pages 23(13):i41–i48. 318–329. Springer. Jari Bjorne, Antti Airola, Tapio Pahikkala, and Tapio Alessandro Moschitti. 2006b. Making tree kernels Salakoski. 2011. Drug-drug interaction extraction practical for natural language learning. In EACL. from biomedical texts with SVM and RLS classi- fiers. CEUR Workshop Proceedings, 761:35–42. Fabian Pedregosa, Gaël Varoquaux, Alexandre Gram- fort, Vincent Michel, Bertrand Thirion, Olivier Razvan C. Bunescu and Raymond J. Mooney. 2005. Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Subsequence kernels for relation extraction. In Weiss, Vincent Dubourg, et al. 2011. Scikit-learn: NIPS. Machine learning in python. The Journal of Ma- Christopher JC Burges. 1998. A tutorial on support chine Learning Research, 12:2825–2830. vector machines for pattern recognition. Data min- ing and knowledge discovery, 2(2):121–167. I Saleh, Alessandro Moschitti, Preslav Nakov, L Màrquez, and S Joty. 2014. Semantic Kernels Faisal Mahbub Chowdhury, Alberto Lavelli, and for Semantic Parsing. Proceedings of the 2014 Con- Alessandro Moschitti. 2011. A Study on De- ference on Empirical Methods in Natural Language pendency Tree Kernels for Automatic Extraction Processing (EMNLP), pages 436–442. Chih-Hsuan Wei, Yifan Peng, Robert Leaman, Al- lan Peter Davis, Carolyn J Mattingly, Jiao Li, Thomas C Wiegers, and Zhiyong Lu. 2015. Overview of the biocreative v chemical disease re- lation (cdr) task. In Proceedings of the fifth BioCre- ative challenge evaluation workshop, Sevilla, Spain. Dmitry Zelenko, Chinatsu Aone, and Anthony Richardella. 2002. Kernel methods for relation ex- traction. Journal of Machine Learning Research, 3:1083–1106. Huiwei Zhou, Huijie Deng, Long Chen, Yunlong Yang, Chen Jia, and Degen Huang. 2016. Ex- ploiting syntactic and semantics information for chemical–disease relation extraction. Database, 2016:baw048.