IEICE TRANSACTIONS on Information
Alignment Kernels Based on a Generalization of Alignments
Summary :
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.
- Publication
- IEICE TRANSACTIONS on Information Vol.E97-D No.1 pp.1-10
- Publication Date
- 2014/01/01
- Publicized
- Online ISSN
- 1745-1361
- DOI
- 10.1587/transinf.E97.D.1
- Type of Manuscript
- PAPER
- Category
- Fundamentals of Information Systems
Authors
Kilho SHIN
University of Hyogo
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Kilho SHIN, "Alignment Kernels Based on a Generalization of Alignments" in IEICE TRANSACTIONS on Information,
vol. E97-D, no. 1, pp. 1-10, January 2014, doi: 10.1587/transinf.E97.D.1.
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.
URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.E97.D.1/_p
Copy
@ARTICLE{e97-d_1_1,
author={Kilho SHIN, },
journal={IEICE TRANSACTIONS on Information},
title={Alignment Kernels Based on a Generalization of Alignments},
year={2014},
volume={E97-D},
number={1},
pages={1-10},
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.},
keywords={},
doi={10.1587/transinf.E97.D.1},
ISSN={1745-1361},
month={January},}
Copy
TY - JOUR
TI - Alignment Kernels Based on a Generalization of Alignments
T2 - IEICE TRANSACTIONS on Information
SP - 1
EP - 10
AU - Kilho SHIN
PY - 2014
DO - 10.1587/transinf.E97.D.1
JO - IEICE TRANSACTIONS on Information
SN - 1745-1361
VL - E97-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2014
AB - 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.
ER -
English
