Alignment Kernels Based on a Generalization of Alignments

• SHIN Kilho

  Graduate School of Applied Informatics, University of Hyogo

Abstract

This paper shows a way to derive positive definite kernels from edit distances. It is well-known that, if a distance d is negative definite, e^-λd is positive definite for any λ > 0. This property provides us the opportunity to apply useful techniques of kernel multivariate analysis to the features of data captured by means of the distance. However, the known instances of edit distance are not always negative definite. Even worse, it is usually not easy to examine whether a given instance of edit distance is negative definite. This paper introduces alignment kernels to present an alternative means to derive kernels from edit distance. The most important advantage of the alignment kernel consists in its easy-to-check sufficient condition for the positive definiteness. In fact, when we surveyed edit distances for strings, trees and graphs, all but one are instantly verified to meet the condition and therefore proven to be positive definite.

Journal

• IEICE Transactions on Information and Systems

  IEICE Transactions on Information and Systems E97.D (1), 1-10, 2014

  The Institute of Electronics, Information and Communication Engineers

Keywords

• edit distance
• kernel
• tree
• graph

Details

• CRID: 1390282679355917184
• NII Article ID: 130003385469
• DOI: 10.1587/transinf.e97.d.1
• ISSN: 17451361
• ISSN: 09168532
• Web Site: https://www.jstage.jst.go.jp/article/transinf/E97.D/1/E97.D_1/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
  • KAKEN
• Abstract License Flag: Disallowed