Article

Weighted decomposition kernels

Authors:

Sauro Menchetti,

Fabrizio Costa,

Paolo FrasconiAuthors Info & Claims

ICML '05: Proceedings of the 22nd international conference on Machine learning

Pages 585 - 592

https://doi.org/10.1145/1102351.1102425

Published: 07 August 2005 Publication History

Abstract

We introduce a family of kernels on discrete data structures within the general class of decomposition kernels. A weighted decomposition kernel (WDK) is computed by dividing objects into substructures indexed by a selector. Two substructures are then matched if their selectors satisfy an equality predicate, while the importance of the match is determined by a probability kernel on local distributions fitted on the substructures. Under reasonable assumptions, a WDK can be computed efficiently and can avoid combinatorial explosion of the feature space. We report experimental evidence that the proposed kernel is highly competitive with respect to more complex state-of-the-art methods on a set of problems in bioinformatics.

References

[1]

Ben-David, S., Eiron, N., & Simon, H. U. (2002). Limitations of learning via embeddings in euclidean half spaces. J. of Mach. Learning Research, 3, 441--461.

Digital Library

[2]

Collins, M., & Duffy, N. (2001). Convolution kernels for natural language. NIPS 14 (pp. 625--632).

[3]

Cortes, C., Haffner, P., & Mohri, M. (2004). Rational kernels: Theory and algorithms. J. of Machine Learning Research, 5, 1035--1062.

Digital Library

[4]

Cumby, C. M., & Roth, D. (2003). On kernel methods for relational learning. Proceedings of ICML'03.

[5]

Deshpande, M., Kuramochi, M., & Karypis, G. (2003). Frequent Sub-Structure-Based Approaches for Classifying Chemical Compounds. Proceedings of ICDM 2003 (pp. 35--42).

Digital Library

[6]

Gärtner, T. (2003). A survey of kernels for structured data. SIGKDD Explor. Newsl., 5, 49--58.

Digital Library

[7]

Gärtner, T., Flach, P., & Wrobel, S. (2003). On graph kernels: Hardness results and efficient alternatives. Proc. of COLT/Kernel '03 (pp. 129--143).

[8]

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

[9]

Helma, C., King, R. D., Kramer, S., & Srinivasan, A. (2001). The Predictive Toxicology Challenge 2000--2001. Bioinformatics, 17, 107--108.

[10]

Horváth, T., Gärtner, T., & Wrobel, S. (2004). Cyclic pattern kernels for predictive graph mining. Proceedings of KDD'04 (pp. 158--167). ACM Press.

Digital Library

[11]

Hua, S., & Sun, Z. (2001). Support Vector Machine for Protein Subcellular Localization Prediction. Bioinformatics, 17, 721--728.

[12]

Jaakkola, T., Diekhans, M., & Haussler, D. (2000). A Discriminative Framework for Detecting Remote Protein Homologies. J. of Comp. Biology, 7, 95--114.

[13]

Jebara, T., Kondor, R., & Howard, A. (2004). Probability product kernels. J. Mach. Learn. Res., 5, 819--844.

Digital Library

[14]

Kashima, H., Tsuda, K., & Inokuchi, A. (2003). Marginalized kernels between labeled graphs. Proceedings of ICML'03 (pp. 321--328).

[15]

Kramer, S., Raedt, L. D., & Helma, C. (2001). Molecular feature mining in HIV data. Proc. of KDD-01 (pp. 136--143). ACM Press.

Digital Library

[16]

Leslie, C. S., Eskin, E., & Noble, W. S. (2002). The spectrum kernel: A string kernel for SVM protein classification. Pacific Symposium on Biocomputing (pp. 566--575).

[17]

Lodhi, H., Saunders, C., Shawe-Taylor, J., Cristianini, N., & Watkins, C. (2002). Text classification using string kernels. J. Mach. Learn. Res., 2, 419--444.

Digital Library

[18]

Mahé, P., Ueda, N., Akutsu, T., Perret, J.-L., & Vert, J.-P. (2004). Extensions of marginalized graph kernels. Proceedings of ICML'04 (pp. 552--559).

Digital Library

[19]

Nair, R., & Rost, B. (2003). Better Prediction of Sub-Cellular Localization by Combining Evolutionary and Structural Information. Proteins: Structure, Function, and Genetics, 53, 917--930.

[20]

Odone, F., Barla, A., & Verri, A. (2005). Building kernels from binary strings for image matching. IEEE Transactions on Image Processing, 14, 169--180.

Digital Library

[21]

Schölkopf, B., Weston, J., Eskin, E., Leslie, C. S., & Noble, W. S. (2002). A kernel approach for learning from almost orthogonal patterns. Proc. of ECML'02 (pp. 511--528).

Digital Library

[22]

Shawe-Taylor, J., & Cristianini, N. (2004). Kernel methods for pattern analysis. Cambridge University Press.

Digital Library

Cited By

Luperto MAmigoni F(2019)Predicting the global structure of indoor environmentsAutonomous Robots10.1007/s10514-018-9732-743:4(813-835)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s10514-018-9732-7
Ghosh SDas NGonçalves TQuaresma PKundu M(2018)The journey of graph kernels through two decadesComputer Science Review10.1016/j.cosrev.2017.11.00227(88-111)Online publication date: Feb-2018
https://doi.org/10.1016/j.cosrev.2017.11.002
Baskin I(2018)Machine Learning Methods in Computational ToxicologyComputational Toxicology10.1007/978-1-4939-7899-1_5(119-139)Online publication date: 23-Jun-2018
https://doi.org/10.1007/978-1-4939-7899-1_5
Show More Cited By

Recommendations

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 ...
Simultaneous learning of localized multiple kernels and classifier with weighted regularization
SSPR'12/SPR'12: Proceedings of the 2012 Joint IAPR international conference on Structural, Syntactic, and Statistical Pattern Recognition

Kernel classifiers have demonstrated their high performance for many classification problems. For the proper selection of kernel functions, multiple kernel learning (MKL) has been researched. Furthermore, the localized MKL (LMKL) enables to set the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ICML '05: Proceedings of the 22nd international conference on Machine learning

August 2005

1113 pages

ISBN:1595931805

DOI:10.1145/1102351

General Chair:
Saso Dzeroski
Jozef Stefan Institute, Slovenia
,
Program Chairs:
Luc De Raedt,
Stefan Wrobel

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 07 August 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

Overall Acceptance Rate 140 of 548 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

43
Total Citations
View Citations
296
Total Downloads

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

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Luperto MAmigoni F(2019)Predicting the global structure of indoor environmentsAutonomous Robots10.1007/s10514-018-9732-743:4(813-835)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s10514-018-9732-7
Ghosh SDas NGonçalves TQuaresma PKundu M(2018)The journey of graph kernels through two decadesComputer Science Review10.1016/j.cosrev.2017.11.00227(88-111)Online publication date: Feb-2018
https://doi.org/10.1016/j.cosrev.2017.11.002
Baskin I(2018)Machine Learning Methods in Computational ToxicologyComputational Toxicology10.1007/978-1-4939-7899-1_5(119-139)Online publication date: 23-Jun-2018
https://doi.org/10.1007/978-1-4939-7899-1_5
Kiran PSivadasan N(2015)Scalable graph similarity search in large graph databases2015 IEEE Recent Advances in Intelligent Computational Systems (RAICS)10.1109/RAICS.2015.7488415(207-211)Online publication date: Dec-2015
https://doi.org/10.1109/RAICS.2015.7488415
Yamashita HHiguchi TYoshida R(2014)Atom Environment Kernels on MoleculesJournal of Chemical Information and Modeling10.1021/ci400403w54:5(1289-1300)Online publication date: 6-May-2014
https://doi.org/10.1021/ci400403w
LUGO-MARTINEZ JRADIVOJAC P(2014)Generalized graphlet kernels for probabilistic inference in sparse graphsNetwork Science10.1017/nws.2014.142:2(254-276)Online publication date: 1-Aug-2014
https://doi.org/10.1017/nws.2014.14
GLAVAŠ GŠNAJDER J(2014)Construction and evaluation of event graphsNatural Language Engineering10.1017/S135132491400006021:4(607-652)Online publication date: 1-May-2014
https://doi.org/10.1017/S1351324914000060
Glavaš GŠnajder J(2014)Event graphs for information retrieval and multi-document summarizationExpert Systems with Applications: An International Journal10.1016/j.eswa.2014.04.00441:15(6904-6916)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1016/j.eswa.2014.04.004
Frasconi PCosta FDe Raedt LDe Grave K(2014)kLogArtificial Intelligence10.1016/j.artint.2014.08.003217:C(117-143)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.artint.2014.08.003
Seeland MKramer SPfahringer BShin SMaldonado J(2013)Model selection based product kernel learning for regression on graphsProceedings of the 28th Annual ACM Symposium on Applied Computing10.1145/2480362.2480391(136-143)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.1145/2480362.2480391
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