ASM Kernel: Graph Kernel using Approximate Subgraph Matching for Relation Extraction

ASM Kernel: Graph Kernel using Approximate Subgraph Matching for 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 Kernel methods have been widely stud- ied in several natural language process- ing tasks such as relation extraction and sentence classification. In this work, we present a new graph kernel that is de- rived from a distance measure described in prior work as Approximate Subgraph Matching (ASM). The classical ASM dis- tance, shown to be effective for event ex- traction, is not a valid kernel and was pri- marily designed to work with rule based systems. We modify this distance suitably to render it a valid kernel (ASM kernel) and enable its use in powerful learning al- gorithms such as Support Vector Machine (SVM). We compare the ASM kernel with SVMs to the classical ASM with a rule based ap- proach, for two relation extraction tasks and show an improved performance with the kernel based approach. Compared to other kernels such as the Subset tree ker- nel and the Partial tree kernel, ASM ker- nel outperforms in relation extraction tasks and is of comparable performance in a general sentence classification task. We describe the advantages of the ASM ker- nel such as its flexibility and ease of modi- fication, which offers further directions for improvement. 1 Introduction Many natural language processing tasks such as relation extraction or question classifica- tion are cast as supervised classification prob- lems (Bunescu and Mooney, 2005), with the ob- ject to classify being an entity pair or a sentence. Traditional approaches have typically focussed on transforming the input into a feature vector which is then classified using learning algorithms such as decision trees or SVM. A primary limitation of this approach has been the manual effort required to construct a rich set of features that can yield a high performance classification. This effort is evident for the construction of features from the syntactic parse of the text, which is often repre- sented as an ordered structure such as a tree or a graph. Linearizing a highly expressive structure such as a graph, by transforming it into a flat array of features is inherently harder. This problem of constructing explicit feature sets for complex ob- jects is generally overcome by kernel methods for classification. Kernel methods allow for an im- plicit exploration of a vast high dimensional fea- ture space and shift the focus from feature engi- neering to similarity score design. Importantly, such a kernel must be shown to be symmetric and positive semi-definite (Burges, 1998), to be valid for use with kernelized learning algorithms such as SVM. Deep learning based approches (Zeng et al., 2014; Xu et al., 2015) are other alternatives to eliminate the manual feature engineering efforts. However, in this work we are primarily focussed on kernel methods. In NLP, kernel methods have been effectively used for relation extraction and sentence classifi- cation. Subset tree …

Content truncated to 500 words