Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Wydawca
Czasopismo
Rocznik
Tom
Strony
87--105
Opis fizyczny
Bibliogr. 20 poz., rys.
Twórcy
autor
- 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).
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-87e37228-0638-4892-92df-7f762377b520