A Subpath Kernel for Rooted Unordered Trees

Kernel method is one of the promising approaches to learning with tree-structured data, and various efficient tree kernels have been proposed to capture informative structures in trees. In this paper, we propose a new tree kernel function based on “subpath sets” to capture vertical structures in rooted unordered trees, since such tree-structures are often used to code hierarchical information in data. We also propose a simple and efficient algorithm for computing the kernel by extending the multikey quicksort algorithm used for sorting strings. The time complexity of the algorithm is O((|

T

1

| + |

T

2

|)log(|

T

1

| + |

T

2

|)) time on average, and the space complexity is O(|

T

1

| + |

T

2

|), where |

T

1

| and |

T

2

| are the numbers of nodes in two trees

T

1

and

T

2

. We apply the proposed kernel to two supervised classification tasks, XML classification in web mining and glycan classification in bioinformatics. The experimental results show that the predictive performance of the proposed kernel is competitive with that of the existing efficient tree kernel for unordered trees proposed by Vishwanathan

et al.

[1], and is also empirically faster than the existing kernel.