On Infinite Divisibility of Convolution and Mapping Kernels.
Saved in:
| Title: | On Infinite Divisibility of Convolution and Mapping Kernels. |
|---|---|
| Authors: | Kilho Shin1 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 |
| FullText | Links: – Type: pdflink Text: Availability: 0 |
|---|---|
| Header | DbId: egs DbLabel: Engineering Source An: 121923334 AccessLevel: 6 PubType: Academic Journal PubTypeId: academicJournal PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: On Infinite Divisibility of Convolution and Mapping Kernels. – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Kilho+Shin%22">Kilho Shin</searchLink><relatesTo>1</relatesTo><i> yshin@ai.u-hyogo.ac.jp</i> – Name: TitleSource Label: Source Group: Src Data: <searchLink fieldCode="JN" term="%22Fundamenta+Informaticae%22">Fundamenta Informaticae</searchLink>. 2017, Vol. 152 Issue 1, p87-105. 19p. – Name: Subject Label: Subjects Group: Su Data: <searchLink fieldCode="DE" term="%22Mathematical+convolutions%22">Mathematical convolutions</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+mappings%22">Mathematical mappings</searchLink><br /><searchLink fieldCode="DE" term="%22Graph+theory%22">Graph theory</searchLink><br /><searchLink fieldCode="DE" term="%22Problem+solving%22">Problem solving</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+sequences%22">Mathematical sequences</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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] – Name: AbstractSuppliedCopyright Label: Group: Ab Data: <i>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.</i> (Copyright applies to all Abstracts.) |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=121923334 |
| RecordInfo | BibRecord: BibEntity: Identifiers: – Type: doi Value: 10.3233/FI-2017-1513 Languages: – Code: eng Text: English PhysicalDescription: Pagination: PageCount: 19 StartPage: 87 Subjects: – SubjectFull: Mathematical convolutions Type: general – SubjectFull: Mathematical mappings Type: general – SubjectFull: Graph theory Type: general – SubjectFull: Problem solving Type: general – SubjectFull: Mathematical sequences Type: general Titles: – TitleFull: On Infinite Divisibility of Convolution and Mapping Kernels. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Kilho Shin IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 03 Text: 2017 Type: published Y: 2017 Identifiers: – Type: issn-print Value: 01692968 Numbering: – Type: volume Value: 152 – Type: issue Value: 1 Titles: – TitleFull: Fundamenta Informaticae Type: main |
| ResultId | 1 |
