=Paper=
{{Paper
|id=Vol-1650/smbm16Chandrasekarasastry
|storemode=property
|title=Exploiting Tree Kernels for High Performance Chemical Induced Disease Relation Extraction
|pdfUrl=https://ceur-ws.org/Vol-1650/smbm16Chandrasekarasastry.pdf
|volume=Vol-1650
|authors=Nagesh Panyam Chandrasekarasastry,Karin Verspoor,Trevor Cohn,Ramamohanarao Kotagiri
|dblpUrl=https://dblp.org/rec/conf/smbm/Chandrasekarasastry16
}}
==Exploiting Tree Kernels for High Performance Chemical Induced Disease Relation Extraction==
https://ceur-ws.org/Vol-1650/smbm16Chandrasekarasastry.pdf
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.