A Local Alignment Kernel in the Context of NLP

Proceedings of the 22nd International Conference on Computational Linguistics (Coling 2008), pages 417–424 Manchester, August 2008 A Local Alignment Kernel in the Context of NLP Sophia Katrenko Informatics Institute University of Amsterdam the Netherlands katrenko@science.uva.nl Pieter Adriaans Informatics Institute University of Amsterdam the Netherlands pietera@science.uva.nl Abstract This paper discusses local alignment ker- nels in the context of the relation extrac- tion task. We define a local alignment kernel based on the Smith-Waterman mea- sure as a sequence similarity metric and proceed with a range of possibilities for computing a similarity between elements of sequences. We propose to use distri- butional similarity measures on elements and by doing so we are able to incorporate extra information from the unlabeled data into a learning task. Our experiments sug- gest that a LA kernel provides promising results on some biomedical corpora largely outperforming a baseline. 1 Introduction Relation extraction is one of the tasks in the natural language processing which is constantly revisited. To date, there are many methods which have been proposed to tackle it. Such ap- proaches often benefit from using syntactic infor- mation (Bunescu and Mooney, 2006) and back- ground knowledge (Sekimizu et al., 1998). How- ever, it would be interesting to employ additional information not necessarily contained in the train- ing set. This paper presents a contribution to the work on relation extraction by combining statisti- cal information with string distance measures. In particular, we propose to use a local alignment ker- nel to detect relations. The paper is organized as follows. We start with the definition of a local alignment kernel and show c⃝ 2008. Licensed under the Creative Commons Attribution-Noncommercial-Share Alike 3.0 Unported li- cense (http://creativecommons.org/licenses/by-nc-sa/3.0/). Some rights reserved. how it is defined on the Smith-Waterman measure. We proceed by discussing how a substitution ma- trix can be constructed in the context of natural language processing tasks. Once a method is de- scribed, we turn to the task of relation extraction and present an experimental part. We conclude by mentioning possible future directions. 2 A Local Aligment Kernel Kernel methods are widely used for a variety of natural language processing task, starting from PoS tagging to information extraction. Many of the approaches employ the idea of combining ker- nels together which leads to a convolution kernel (Haussler, 1999). The examples of convolution methods being successfully used in NLP are ker- nels based on dependency trees and shallow pars- ing (Moschitti, 2006; Zelenko et al., 2003). Local alignment (LA) kernels also belong to the family of convolution kernels but have not yet been ap- plied to NLP problems. Although the approaches listed above proved to be accurate, they only use kernels which are de- signed by computing inner products between vec- tors of sequences. Intuitively, methods using more elaborate measures of similarity could provide bet- ter results but kernels defined on such measures are not necessarily positive semi-definite. Recent work in the biomedical field shows that it is pos- sible to design valid kernels based on a similarity …

Content truncated to 500 words