On Infinite Divisibility of Convolution and Mapping Kernels

Article type: Research Article

Authors: Shin, Kilho^*

Affiliations: Graduate School of Applied Informatics, University of Hyogo, Chuo, Kobe, Japan. yshin@ai.u-hyogo.ac.jp

Correspondence: [*] Address for correspondence: Graduate School of Applied Informatics, University of Hyogo, Chuo, Kobe, Japan.

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 c ∈ (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.

Keywords: kernel, infinite divisibility

DOI: 10.3233/FI-2017-1513

Journal: Fundamenta Informaticae, vol. 152, no. 1, pp. 87-105, 2017