On Infinite Divisibility of Convolution and Mapping Kernels

• Autorzy: Shin K.

Identyfikatory

DOI

10.3233/FI-2017-1513

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

kernel; infinite divisibility

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 152, nr 1
• Strony: 87--105
• Opis fizyczny: Bibliogr. 20 poz., rys.

Twórcy

autor

Shin K.

• Graduate School of Applied Informatics, University of Hyogo Chuo, Kobe, Japan

Bibliografia

• [1] Berg C, Christensen JPR, Ressel R. Harmonic Analysis on semigroups. Theory of positive definite and related functions, Springer, 1984. doi:10.1007/978-1-4612-1128-0.
• [2] Collins M, Duffy N. Convolution Kernels for Natural Language, Advances in Neural Information Processing Systems 14 [Neural Information Processing Systems: Natural and Synthetic, NIPS 2001], MIT Press, 2001. ISBN-10: 0262042088, 13: 978-0262042086.
• [3] Cortes C, Haffner P, Mohri M. Rational Kernels: Theory and Algorithm, Journal of Machine Learning Research, 2004;5:1035–1062. URL http://dl.acm.org/citation.cfm?id=1005332.1016793.
• [4] Cuturi M. Fast Global Alignment Kernels, ICML, 2011. URL http://www.icml-2011.org/papers/489_icmlpaper.pdf,
• [5] Cuturi M, Vert JP, Birkenes O, Matsui T. A kernel for time series based on global alignments, ICASSP 2007. doi:10.1109/ICASSP.2007.366260.
• [6] Haussler D. Convolution Kernels on Discrete Structures, UCSC-CRL 99-10, Dept. of Computer Science, University of California at Santa Cruz, 1999. URL http://citeseer.ist.psu.edu/haussler99convolution.html.
• [7] Kashima H, Koyanagi T. Kernels for Semi-Structured Data, The 9th International Conference on Machine Learning (ICML), 2002. URL http://dl.acm.org/citation.cfm?id=645531.656021.
• [8] Kuboyama T, Shin K, Kashima H. Flexible tree kernels based on counting the number of tree mappings, Proc. of Machine Learning with Graphs, 2006. URL http://www.inf.uni-konstanz.de/mlg2006/06.pdf.
• [9] Levenshtein VI. Binary codes capable of correcting deletions, insertions, and reversals, Soviet Physics Doklady, 1966;10(8):707–710.
• [10] Lu CL, Su ZY, Tang GY. A New Measure of Edit Distance between Labeled Trees, LNCS, 2108, Springer-Verlag Heidelberg, 2001. doi:10.1007/3-540-44679-6_37.
• [11] Lu SY. A tree-to-tree distance and its application to cluster analysis, IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), 1979;1(2):219–224. doi:10.1109/TPAMI.1979.6786615.
• [12] Neuhaus M, Bunke H. Bridging the gap between graph edit distance and kernel machines, World Scientific, 2007. ISBN: 9812708170, 9789812708175.
• [13] Shin K. Alignment Kernels based on a Generalization of Alignments., IEICE Trans. on Information and Systems, 2014;E97. D(1):1–10. URL http://doi.org/10.1587/transinf.E97.D.1
• [14] Shin K. A Theory of Subtree Matching and Tree Kernels based on the Edit Distance Concept, Annals of Mathematics and Artificial Intelligence, 2015;75(3):419–460. doi:10.1007/s10472-015-9467-5.
• [15] Shin K, Cuturi M, Kuboyama T. Mapping kernels for trees, ICML 2011.
• [16] Shin K, Kuboyama T. A generalization of Haussler’s convolution kernel-mapping kernel, ICML 2008.
• [17] Shin K, Kuboyama T. A Generalization of Haussler’s Convolution Kernel-Mapping Kernel and Its Application to Tree Kernels, J. Comput. Sci. Technol, 2010;25(5):1040–1054. doi:10.1007/s11390-010-9386-1.
• [18] Taï KC. The tree-to-tree correction problem, Journal of the ACM, 1979;26(3):422–433. doi:10.1145/322139.322143.
• [19] Zhang K. Algorithms for the constrained editing distance between ordered labeled trees and related problems, Pattern Recognition, 1995;28(3):463–474. URL http://dx.doi.org/10.1016/0031-3203(94)00109-Y.
• [20] Kimura D, Kashima H. Fast Computation of Subpath Kernel for Trees, Proceedings of the 29th International Conference on Machine Learning, ICML 2012. URL http://icml.cc/2012/papers/217.pdf.

Uwagi

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).