Fast Computation of Subpath Kernel for Trees
This work addresses a computational bottleneck for researchers and practitioners using kernel methods to analyze hierarchical data like trees, representing an incremental improvement over prior methods.
The paper tackles the problem of efficiently computing a subpath kernel for unordered trees, proposing a theoretically guaranteed linear-time algorithm that is also practically fast, with experimental results demonstrating high efficiency.
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.