×

zbMATH — the first resource for mathematics

The weight function in the subtree kernel is decisive. (English) Zbl 07255098
Summary: Tree data are ubiquitous because they model a large variety of situations, e.g., the architecture of plants, the secondary structure of RNA, or the hierarchy of XML files. Nevertheless, the analysis of these non-Euclidean data is difficult per se. In this paper, we focus on the subtree kernel that is a convolution kernel for tree data introduced by Vishwanathan and Smola in the early 2000’s. More precisely, we investigate the influence of the weight function from a theoretical perspective and in real data applications. We establish on a 2-classes stochastic model that the performance of the subtree kernel is improved when the weight of leaves vanishes, which motivates the definition of a new weight function, learned from the data and not fixed by the user as usually done. To this end, we define a unified framework for computing the subtree kernel from ordered or unordered trees, that is particularly suitable for tuning parameters. We show through eight real data classification problems the great efficiency of our approach, in particular for small data sets, which also states the high importance of the weight function. Finally, a visualization tool of the significant features is derived.
MSC:
68T05 Learning and adaptive systems in artificial intelligence
Software:
Stony Brook; treex
PDF BibTeX XML Cite
Full Text: Link
References:
[1] Fabio Aiolli, Giovanni Da San Martino, Alessandro Sperduti, and Alessandro Moschitti. Fast on-line kernel learning for trees. InSixth International Conference on Data Mining (ICDM’06), pages 787-791. IEEE, 2006.
[2] Romain Aza¨ıs, Guillaume Cerutti, Didier Gemmerl´e, and Florian Ingels. treex: a python package for manipulating rooted trees.The Journal of Open Source Software, 4, 2019.
[3] Romain Aza¨ıs, Alexandre Genadot, and Benoˆıt Henry. Inference for conditioned GaltonWatson trees from their Harris path.To appear in ALEA, 2019.
[4] Maria-Florina Balcan, Avrim Blum, and Nathan Srebro. A theory of learning with similarity functions.Machine Learning, 72(1-2):89-112, 2008. doi: 10.1007/s10994-008-5059-5. URLhttps://doi.org/10.1007/s10994-008-5059-5.
[5] Karthik Bharath, Prabhanjan Kambadur, Dipak Dey, Rao Arvin, and Veerabhadran Baladandayuthapani. Statistical tests for large tree-structured data.Journal of the American Statistical Association, 2016.
[6] Philip Bille. A survey on tree edit distance and related problems.Theoretical Computer Science, 337(1-3):217 - 239, 2005. ISSN 0304-3975. doi: http://dx.doi.org/10.1016/j.tcs. 2004.12.030.
[7] Michael Collins and Nigel Duffy. Convolution kernels for natural language. InAdvances in neural information processing systems, pages 625-632, 2002.
[8] Gianni Costa, Giuseppe Manco, Riccardo Ortale, and Andrea Tagarelli. A tree-based approach to clustering xml documents by structure. In Jean-Fran¸cois Boulicaut, Floriana Esposito, Fosca Giannotti, and Dino Pedreschi, editors,Knowledge Discovery in Databases: PKDD 2004, pages 137-148, Berlin, Heidelberg, 2004. Springer Berlin Heidelberg. ISBN 978-3-540-30116-5.
[9] Nello Cristianini, John Shawe-Taylor, et al.An introduction to support vector machines and other kernel-based learning methods. Cambridge university press, 2000.
[10] Giovanni Da San Martino.Kernel methods for tree structured data. PhD thesis, alma, 2009.
[11] Ludovic Denoyer and Patrick Gallinari. Report on the xml mining track at inex 2005 and inex 2006: categorization and clustering of xml documents. InSIGIR Forum, volume 41, pages 79-90, 2007.
[12] Peter J. Downey, Ravi Sethi, and Robert Endre Tarjan.Variations on the common subexpression problem.J. ACM, 27(4):758-771, October 1980. ISSN 0004-5411. doi: 10.1145/322217.322228. URLhttp://doi.acm.org/10.1145/322217.322228.
[13] David S. Ebert and F. Kenton Musgrave.Texturing & modeling: a procedural approach. Morgan Kaufmann, 2003.
[14] E Faure, T Savy, B Rizzi, C Melani, M Remeˇs´ıkova, R ˇSpir, O Drbl´ıkov´a, R ˇCunderl´ık, G Recher, B Lombardot, et al. An algorithmic workflow for the automated processing of 3d+ time microscopy images of developing organisms and the reconstruction of their cell lineage.Nat. Commun, 2015.
[15] Christophe Godin and Pascal Ferraro. Quantifying the degree of self-nestedness of trees: application to the structural analysis of plants.IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), 7(4):688-703, 2010.
[16] Ghassan Hamarneh and Preet Jassi. Vascusynth: Simulating vascular trees for generating volumetric image data with ground truth segmentation and tree analysis.Computerized Medical Imaging and Graphics, 34(8):605-616, 2010. doi: 10.1016/j.compmedimag.2010. 06.002.
[17] John C. Hart and Thomas A. DeFanti. Efficient antialiased rendering of 3-d linear fractals. SIGGRAPH Comput. Graph., 25(4):91-100, July 1991. ISSN 0097-8930. doi: 10.1145/ 127719.122728. URLhttp://doi.acm.org/10.1145/127719.122728.
[18] David Haussler. Convolution kernels on discrete structures. Technical report, Department of Computer Science, University of California, 1999.
[19] Damien G Hicks, Terence P Speed, Mohammed Yassin, and Sarah M Russell. Maps of variability in cell lineage trees.PLoS computational biology, 15(2):e1006745, 2019.
[20] Preet Jassi and Ghassan Hamarneh. Vascusynth: Vascular tree synthesis software.Insight Journal, January-June:1-12, 2011. doi: 10380/3260.
[21] Daisuke Kimura, Tetsuji Kuboyama, Tetsuo Shibuya, and Hisashi Kashima. A subpath kernel for rooted unordered trees. InPacific-Asia Conference on Knowledge Discovery and Data Mining, pages 62-74. Springer, 2011.
[22] Shu-Yun Le, Ruth Nussinov, and Jacob V. Maizel.Tree graphs of RNA secondary structures and their comparisons.Computers and Biomedical Research, 22(5):461 - 473, 1989. ISSN 0010-4809. doi: https://doi.org/10.1016/0010-4809(89)90039-6. URL http://www.sciencedirect.com/science/article/pii/0010480989900396.
[23] M. A. Mart´ın-Delgado,J. Rodriguez-Laguna,and G. Sierra.Density-matrix renormalization-group study of excitons in dendrimers.Phys. Rev. B, 65:155116, Apr 2002. doi: 10.1103/PhysRevB.65.155116. URLhttps://link.aps.org/doi/10.1103/ PhysRevB.65.155116.
[24] James Mercer. Xvi. functions of positive and negative type, and their connection the theory of integral equations.Philosophical transactions of the royal society of London. Series A, containing papers of a mathematical or physical character, 209(441-458):415-446, 1909.
[25] Bernhard Sch¨olkopf and Alexander J. Smola.Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge, MA, USA, 2001. ISBN 0262194759.
[26] John Shawe-Taylor, Nello Cristianini, et al.Kernel methods for pattern analysis. Cambridge university press, 2004.
[27] Dan Shen, Haipeng Shen, Shankar Bhamidi, Yolanda Mu˜noz Maldonado, Yongdai Kim, and J. Stephen Marron. Functional data analysis of tree data objects.Journal of computational and graphical statistics : a joint publication of American Statistical Association, Institute of Mathematical Statistics, Interface Foundation of North America, 23 2:418- 438, 2014.
[28] Steven S Skiena. Sorting and searching. InThe Algorithm Design Manual, pages 103-144. Springer, 2012.
[29] Ivan E. Sutherland. Sketchpad: A man-machine graphical communication system. InProceedings of the May 21-23, 1963, Spring Joint Computer Conference, AFIPS ’63 (Spring), pages 329-346, New York, NY, USA, 1963. ACM. doi: 10.1145/1461551.1461591. URL http://doi.acm.org/10.1145/1461551.1461591.
[30] S.V.N. Vishwanathan and Alexander J Smola. Fast kernels on strings and trees.Advances on Neural Information Proccessing Systems, 14, 2002.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.