A Subpath Kernel for Rooted Unordered Trees

DOI Web Site 2 Citations 9 References
  • Kimura Daisuke
    Graduate School of Information Science and Technology, The University of Tokyo
  • Kuboyama Tetsuji
    Computer Centre, Gakushuin University
  • Shibuya Tetsuo
    Human Genome Center, Institute of Medical Science, The University of Tokyo
  • Kashima Hisashi
    Graduate School of Information Science and Technology, The University of Tokyo

Bibliographic Information

Other Title
  • 部分パスに基づいた木カーネル

Abstract

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 tree-structured data, since 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 proposed by Vishwanathan et al., and is also empirically faster than the existing kernel.

Journal

Citations (2)*help

See more

References(9)*help

See more

Related Projects

See more

Keywords

Details 詳細情報について

Report a problem

Back to top