2012/06/18 by Daisuke Kimura, Hisashi Kashima, Kimura, Daisuke +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning in Bioinformatics #Network Packet Processing and Optimization #cs.DS #cs.LG #stat.ML
paper · pdf · doi:10.48550/arxiv.1206.4642
ICML2012
arxiv created 2012/06/18 · openalex publication_date 2012/06/18 · arxiv updated 2012/06/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The kernel method is a potential approach to analyzing structured data such as sequences, trees, and graphs; however, unordered trees have not been investigated extensively. Kimura et al. (2011) proposed a kernel function for unordered trees on the basis of their subpaths, which are vertical substructures of trees responsible for hierarchical information in them. Their kernel exhibits practically good performance in terms of accuracy and speed; however, linear-time computation is not guaranteed theoretically, unlike the case of the other unordered tree kernel proposed by Vishwanathan and Smola (2003). In this paper, we propose a theoretically guaranteed linear-time kernel computation algorithm that is practically fast, and we present an efficient prediction algorithm whose running time depends only on the size of the input tree. Experimental results show that the proposed algorithms are quite efficient in practice.