research-article

Route kernels for trees

Authors:

Giovanni Da San Martino,

Alessandro SperdutiAuthors Info & Claims

ICML '09: Proceedings of the 26th Annual International Conference on Machine Learning

Pages 17 - 24

https://doi.org/10.1145/1553374.1553377

Published: 14 June 2009 Publication History

Abstract

Almost all tree kernels proposed in the literature match substructures without taking into account their relative positioning with respect to one another. In this paper, we propose a novel family of kernels which explicitly focus on this type of information. Specifically, after defining a family of tree kernels based on routes between nodes, we present an efficient implementation for a member of this family. Experimental results on four different datasets show that our method is able to reach state of the art performances, obtaining in some cases performances better than computationally more demanding tree kernels.

References

[1]

Bloehdorn, S., & Moschitti, A. (2007). Structure and semantics for expressive text kernels. Proceedings of the sixteenth ACM Conference on Information and Knowledge Management (pp. 861--864). Lisbon, Portugal.

Digital Library

[2]

Collins, M., & Duffy, N. (2002). New ranking algorithms for parsing and tagging: Kernels over discrete structures, and the voted perceptron. Proceedings of the Fortieth Annual Meeting on Association for Computational Linguistics (pp. 263--270). Philadelphia, PA, USA.

Digital Library

[3]

Denoyer, L., & Gallinari, P. (2007). Report on the XML mining track at INEX 2005 and INEX 2006: categorization and clustering of XML documents. ACM SIGIR Forum, 41, 79--90.

Digital Library

[4]

Diligenti, M., Frasconi, P., & Gori, M. (2003). Hidden tree markov models for document image classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25, 519--523.

Digital Library

[5]

Haussler, D. (1999). Convolution kernels on discrete structures (Technical Report UCSC-CRL-99-10). University of California, Santa Cruz.

[6]

Jaakkola, T. S., & Haussler, D. (1999). Exploiting generative models in discriminative classifiers. Proceedings of the 1998 conference on Advances in Neural Information Processing Systems II (pp. 487--493). Cambridge, MA, USA: MIT Press.

Digital Library

[7]

Kashima, H., & Koyanagi, T. (2002). Kernels for semi-structured data. Proceeding of the International Conference on Machine Learning (pp. 291--298).

Digital Library

[8]

Kingsbury, P., & Palmer, M. (2002). From Treebank to PropBank. Proceedings of the 3rd International Conference on Language Resources and Evaluation (pp. 1989--1993). Las Palmas, Spain.

[9]

Kuboyama, T., Hirata, K., Kashima, H., Aoki-Kinoshita, K. F., & Yasuda, H. (2007). A spectrum tree kernel. Information and Media Technologies, 2, 292--299.

[10]

Moschitti, A. (2006). Efficient convolution kernels for dependency and constituent syntactic trees. Proc. of the European Conference on Machine Learning (pp. 318--329).

Digital Library

[11]

Nicotra, L., Micheli, A., & Starita, A. (2004). Tree fisher kernel. Proceedings. 2004 IEEE International Joint Conference on Neural Networks (pp. 1917--1922).

[12]

Rieck, K., Brefeld, U., & Krger, T. (2008). Approximate kernels for trees (Technical Report). Fraunhofer Publica {http://publica.fraunhofer.de/oai.har} (Germany).

[13]

Shin, K., & Kuboyama, T. (2008). A generalization of haussler's convolution kernel: mapping kernel. Proceeding of the International Conference on Machine Learning (pp. 944--951).

Digital Library

[14]

Suzuki, J., & Isozaki, H. (2006). Sequence and tree kernels with statistical feature mining. In Y. Weiss, B. Schöölkopf and J. Platt (Eds.), Advances in neural information processing systems 18, 1321--1328. Cambridge, MA: MIT Press.

[15]

Vishwanathan, S., & Smola, A. J. (2002). Fast kernels on strings and trees. Proceedings of Neural Information Processing Systems 2002 (pp. 569--576).

[16]

Zhang, M., Che, W., Aw, A., Tan, C. L., Zhou, G., Liu, T., & Li, S. (2007). A grammar-driven convolution tree kernel for semantic role classification. Proc. of the 45th Annual Meeting of the Association for Computational Linguistics (pp. 200--2007).

Cited By

Filice SCastellucci GDa San Martino GMoschitti ACroce DBasili R(2017)KeLPThe Journal of Machine Learning Research10.5555/3122009.324204818:1(6993-6997)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.5555/3122009.3242048
Da San Martino GNavarin NSperduti A(2016)Ordered Decompositional DAG kernels enhancementsNeurocomputing10.1016/j.neucom.2015.12.110192(92-103)Online publication date: Jun-2016
https://doi.org/10.1016/j.neucom.2015.12.110
Aiolli FDa San Martino GSperduti A(2015)An Efficient Topological Distance-Based Tree KernelIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2014.232933126:5(1115-1120)Online publication date: May-2015
https://doi.org/10.1109/TNNLS.2014.2329331
Show More Cited By

Index Terms

Route kernels for trees
1. Computing methodologies
2. Mathematics of computing
  1. Probability and statistics
    1. Statistical paradigms
      1. Exploratory data analysis

Recommendations

Mapping Kernels Between Rooted Labeled Trees Beyond Ordered Trees
New Frontiers in Artificial Intelligence
Abstract
In this paper, we investigate several mapping kernels to count all of the mappings between two rooted labeled trees beyond ordered trees, that is, cyclically ordered trees such as biordered trees, cyclic-ordered trees and cyclic-biordered trees, ...
Refinement of operator-valued reproducing kernels

This paper studies the construction of a refinement kernel for a given operator-valued reproducing kernel such that the vector-valued reproducing kernel Hilbert space of the refinement kernel contains that of the given kernel as a subspace. The study is ...
Refinement of operator-valued reproducing kernels

This paper studies the construction of a refinement kernel for a given operator-valued reproducing kernel such that the vector-valued reproducing kernel Hilbert space of the refinement kernel contains that of the given kernel as a subspace. The study is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '09: Proceedings of the 26th Annual International Conference on Machine Learning

June 2009

1331 pages

ISBN:9781605585161

DOI:10.1145/1553374

General Chair:
Andrea Danyluk
Williams College
,
Program Chairs:
Léon Bottou
NEC Laboratories America
,
Michael Littman
Rutgers University

Copyright © 2009 Copyright 2009 by the author(s)/owner(s).

Sponsors

NSF
Microsoft Research: Microsoft Research
MITACS

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 June 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Conference

ICML '09

Sponsor:

Microsoft Research

ICML '09: The 26th Annual International Conference on Machine Learning held in conjunction with the 2007 International Conference on Inductive Logic Programming

June 14 - 18, 2009

Quebec, Montreal, Canada

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
213
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 28 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Filice SCastellucci GDa San Martino GMoschitti ACroce DBasili R(2017)KeLPThe Journal of Machine Learning Research10.5555/3122009.324204818:1(6993-6997)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.5555/3122009.3242048
Da San Martino GNavarin NSperduti A(2016)Ordered Decompositional DAG kernels enhancementsNeurocomputing10.1016/j.neucom.2015.12.110192(92-103)Online publication date: Jun-2016
https://doi.org/10.1016/j.neucom.2015.12.110
Aiolli FDa San Martino GSperduti A(2015)An Efficient Topological Distance-Based Tree KernelIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2014.232933126:5(1115-1120)Online publication date: May-2015
https://doi.org/10.1109/TNNLS.2014.2329331
Ferrone LZanzotto FCarreras X(2015)Decoding Distributed Tree StructuresProceedings of the Third International Conference on Statistical Language and Speech Processing - Volume 944910.1007/978-3-319-25789-1_8(73-83)Online publication date: 24-Nov-2015
https://dl.acm.org/doi/10.1007/978-3-319-25789-1_8
Bacciu DMicheli ASperduti A(2014)Integrating bi-directional contexts in a generative kernel for trees2014 International Joint Conference on Neural Networks (IJCNN)10.1109/IJCNN.2014.6889768(4145-4151)Online publication date: Jul-2014
https://doi.org/10.1109/IJCNN.2014.6889768
Bacciu DMicheli ASperduti A(2014)Modeling Bi-directional Tree Contexts by Generative TransductionsNeural Information Processing10.1007/978-3-319-12637-1_68(543-550)Online publication date: 2014
https://doi.org/10.1007/978-3-319-12637-1_68
Costa GOrtale RRitacco E(2013)X-ClassACM Transactions on Information Systems10.1145/2414782.241478531:1(1-40)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1145/2414782.2414785
Gallicchio CMicheli A(2013)Tree Echo State NetworksNeurocomputing10.1016/j.neucom.2012.08.017101(319-337)Online publication date: Feb-2013
https://doi.org/10.1016/j.neucom.2012.08.017
Bacciu DMicheli ASperduti A(2012)Compositional Generative Mapping for Tree-Structured Data—Part I: Bottom-Up Probabilistic Modeling of TreesIEEE Transactions on Neural Networks and Learning Systems10.1109/TNNLS.2012.222204423:12(1987-2002)Online publication date: Dec-2012
https://doi.org/10.1109/TNNLS.2012.2222044
Lin ZWang HMcClean S(2012)A Multidimensional Sequence Approach to Measuring Tree SimilarityIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2010.23924:2(197-208)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1109/TKDE.2010.239
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents