On Infinite Divisibility of Convolution and Mapping Kernels.

Saved in:

Bibliographic Details
Title:	On Infinite Divisibility of Convolution and Mapping Kernels.
Authors:	Kilho Shin¹ yshin@ai.u-hyogo.ac.jp
Source:	Fundamenta Informaticae. 2017, Vol. 152 Issue 1, p87-105. 19p.
Subjects:	Mathematical convolutions, Mathematical mappings, Graph theory, Problem solving, Mathematical sequences
Abstract:	Determining whether convolution and mapping kernels are always infinitely divisible has been an unsolved problem. The mapping kernel is an important class of kernels and is a generalization of the well-known convolution kernel. The mapping kernel has a wide range of application. In fact, most of kernels known in the literature for discrete data such as strings, trees and graphs are mapping (convolution) kernels including the q-gram and the all-sub-sequence kernels for strings and the parse-tree and elastic kernels for trees. On the other hand, infinite divisibility is a desirable property of a kernel, which claims that the c-th power of the kernel is positive definite for arbitrary ∈ 2 (0;∞). This property is useful in practice, because the c-th power of the kernel may have better power of classification when c is appropriately small. This paper shows that there are infinitely many positive definite mapping kernels that are not infinitely divisible. As a corollary to this discovery, the q-gram, all-sub-sequence, parse-tree or elastic kernel turns out not to be infinitely divisible. Although these are a negative result, we also show a method to approximate the c-th power of a kernel with a positive definite kernel under certain conditions. [ABSTRACT FROM AUTHOR]
	Copyright of Fundamenta Informaticae is the property of Polskie Towarzystwo Matematyczne and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database:	Engineering Source

Description
Abstract:	Determining whether convolution and mapping kernels are always infinitely divisible has been an unsolved problem. The mapping kernel is an important class of kernels and is a generalization of the well-known convolution kernel. The mapping kernel has a wide range of application. In fact, most of kernels known in the literature for discrete data such as strings, trees and graphs are mapping (convolution) kernels including the q-gram and the all-sub-sequence kernels for strings and the parse-tree and elastic kernels for trees. On the other hand, infinite divisibility is a desirable property of a kernel, which claims that the c-th power of the kernel is positive definite for arbitrary ∈ 2 (0;∞). This property is useful in practice, because the c-th power of the kernel may have better power of classification when c is appropriately small. This paper shows that there are infinitely many positive definite mapping kernels that are not infinitely divisible. As a corollary to this discovery, the q-gram, all-sub-sequence, parse-tree or elastic kernel turns out not to be infinitely divisible. Although these are a negative result, we also show a method to approximate the c-th power of a kernel with a positive definite kernel under certain conditions. [ABSTRACT FROM AUTHOR]
ISSN:	01692968
DOI:	10.3233/FI-2017-1513