2006 FlexTreeKernelsBasedOnTreeMappings
- (KuboyamaSK, 2006) ⇒ Tetsuji Kuboyama, Kilho Shin, Hisashi Kashima.. Flexible Tree Kernels based on Counting the Number of Tree Mappings. ECML/PKDD Workshop on Mining and Learning with Graphs.
Subject Headings: Tree Kernel Function
Notes
Cited By
Quotes
Abstract
Functions counting the number of common sub-patterns between trees have been promising candidates for kernel functions for trees in learning systems. There are several viewpoints of how two patterns between two trees can be regarded as the same. In the tree edit distance, these viewpoints have been well formalized as the class of tree mappings, and several distance measures have been proposed according to the classes of tree mappings. In this paper, we address the design problem of new flexible tree kernels corresponding to four representative classes of tree mappings. Therefore, first, we develop four counting functions for tree mappings according to the four classes. Secondly, we prove that three of the four counting functions are kernel functions, and the other is not.
References
- 1. John Shawe-Taylor, Cristianini, N.: Kernel Methods for Pattern Analysis. Cambridge
University Press (2004)
- 2. Michael Collins, Du y, N.: Convolution Kernels for Natural Language. Advances in
Neural Information Processing Systems 14, Vol.1 (NIPS). (2001) 625–632
- 3. Kashima, H., Koyanagi, T.: Kernels for Semi-Structured Data. Proceedings of the 9th
International Conference on Machine Learning (ICML). (2002). 291–298
- 4. Tai, K.C.: The Tree-to-Tree Correction Problem. JACM 26 (1979) 422–433
- 5. Zhang, K.: Algorithms for The Constrained Editing Distance between Ordered
Labeled Trees and Related Problems. Pattern Recognition 28 (1995) 463–474
- 6. Lu, C.L., Su, Z.Y., Tang, G.Y.: A New Measure of Edit Distance between Labeled
Trees. LNCS 2108 (2001) 338–348
- 7. Richter, T.: A New Measure of The Distance between Ordered Trees and its
Applications. Technical Report 85166-CS, Dept. of Computer Science, Univ. of Bonn (1997)
- 8. Jiang, T., Wang, L., Zhang, K.: Alignment of Trees — An Alternative to Tree
Edit. Theoretical Computer Science 143 (1995) 137–148
- 9. Wang, J.L., Zhang, K.: Finding Similar Consensus between Trees: An Algorithm
and A Distance Hierarchy. Pattern Recognition 34 (2001) 127–137
- 10. Kuboyama, T., Shin, K., Miyahara, T., Yasuda, H.: A Theoretical Analysis of Alignment and Edit Problems for Trees. Theoretical Computer Science, The 9th Italian Conference. LNCS 3701 (2005) 323–337
- 11. Shin, K., Kuboyama, T.: An algebraic Foundation of The Tree Edit Distance.
Technical report, Center for Collaborative Research, University of Tokyo (2005)
- 12. Haussler, D.: Convolution kernels on discrete structures. UCSC-CRL 99-10, Dept.
of Computer Science, University of California at Santa Cruz (1999),
| Author | volume | Date Value | title | type | journal | titleUrl | doi | note | year | |
|---|---|---|---|---|---|---|---|---|---|---|
| 2006 FlexTreeKernelsBasedOnTreeMappings | Tetsuji Kuboyama Kilho Shin Hisashi Kashima. | Flexible Tree Kernels based on Counting the Number of Tree Mappings | http://www.inf.uni-konstanz.de/mlg2006/06.pdf |