Fast Computation of Subpath Kernel for Trees
Fast Computation of Subpath Kernel for Trees
复制标题
DOI：
--
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
D. Kimura;H. Kashima
中科院分区：
文献类型：
--
作者：
D. Kimura;H. Kashima
核方法是分析结构化数据（如序列、树和图）的一种潜在方法，然而，无序树尚未得到广泛研究。Kimura et al.（2011）提出了一种基于子路径的无序树的核函数，子路径是树的垂直子结构，负责其中的层次信息。他们的内核在精度和速度方面表现出实际上很好的性能;然而，线性时间计算在理论上不能保证，不像Vishwanathan和Smola（2003）提出的其他无序树内核。在本文中，我们提出了一个理论上保证线性时间内核计算算法，实际上是快速的，我们提出了一个有效的预测算法，其运行时间只取决于输入树的大小。实验结果表明，本文提出的算法在实际应用中是非常有效的.
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.