Approximate tree kernels

Research output: Journal contributionsJournal articlesResearchpeer-review

Standard

Approximate tree kernels. / Rieck, Konrad; Krueger, Tammo; Brefeld, Ulf et al.
In: Journal of Machine Learning Research, Vol. 11, 02.2010, p. 555-580.

Research output: Journal contributionsJournal articlesResearchpeer-review

Harvard

APA

Vancouver

Rieck K, Krueger T, Brefeld U, Müller KR. Approximate tree kernels. Journal of Machine Learning Research. 2010 Feb;11:555-580.

Bibtex

@article{80bc2fa980124112a63f3e3a8f3a70a1,
title = "Approximate tree kernels",
abstract = "Convolution kernels for trees provide simple means for learning with tree-structured data. The computation time of tree kernels is quadratic in the size of the trees, since all pairs of nodes need to be compared. Thus, large parse trees, obtained from HTML documents or structured network data, render convolution kernels inapplicable. In this article, we propose an effective approximation technique for parse tree kernels. The approximate tree kernels (ATKs) limit kernel computation to a sparse subset of relevant subtrees and discard redundant structures, such that training and testing of kernel-based learning methods are significantly accelerated. We devise linear programming approaches for identifying such subsets for supervised and unsupervised learning tasks, respectively. Empirically, the approximate tree kernels attain run-time improvements up to three orders of magnitude while preserving the predictive accuracy of regular tree kernels. For unsupervised tasks, the approximate tree kernels even lead to more accurate predictions by identifying relevant dimensions in feature space.",
keywords = "Approximation, Convolution kernels, Kernel methods, Tree kernels, Informatics, Business informatics",
author = "Konrad Rieck and Tammo Krueger and Ulf Brefeld and M{\"u}ller, {Klaus Robert}",
year = "2010",
month = feb,
language = "English",
volume = "11",
pages = "555--580",
journal = "Journal of Machine Learning Research",
issn = "1532-4435",
publisher = "Microtome Publishing",

}

RIS

TY - JOUR

T1 - Approximate tree kernels

AU - Rieck, Konrad

AU - Krueger, Tammo

AU - Brefeld, Ulf

AU - Müller, Klaus Robert

PY - 2010/2

Y1 - 2010/2

N2 - Convolution kernels for trees provide simple means for learning with tree-structured data. The computation time of tree kernels is quadratic in the size of the trees, since all pairs of nodes need to be compared. Thus, large parse trees, obtained from HTML documents or structured network data, render convolution kernels inapplicable. In this article, we propose an effective approximation technique for parse tree kernels. The approximate tree kernels (ATKs) limit kernel computation to a sparse subset of relevant subtrees and discard redundant structures, such that training and testing of kernel-based learning methods are significantly accelerated. We devise linear programming approaches for identifying such subsets for supervised and unsupervised learning tasks, respectively. Empirically, the approximate tree kernels attain run-time improvements up to three orders of magnitude while preserving the predictive accuracy of regular tree kernels. For unsupervised tasks, the approximate tree kernels even lead to more accurate predictions by identifying relevant dimensions in feature space.

AB - Convolution kernels for trees provide simple means for learning with tree-structured data. The computation time of tree kernels is quadratic in the size of the trees, since all pairs of nodes need to be compared. Thus, large parse trees, obtained from HTML documents or structured network data, render convolution kernels inapplicable. In this article, we propose an effective approximation technique for parse tree kernels. The approximate tree kernels (ATKs) limit kernel computation to a sparse subset of relevant subtrees and discard redundant structures, such that training and testing of kernel-based learning methods are significantly accelerated. We devise linear programming approaches for identifying such subsets for supervised and unsupervised learning tasks, respectively. Empirically, the approximate tree kernels attain run-time improvements up to three orders of magnitude while preserving the predictive accuracy of regular tree kernels. For unsupervised tasks, the approximate tree kernels even lead to more accurate predictions by identifying relevant dimensions in feature space.

KW - Approximation

KW - Convolution kernels

KW - Kernel methods

KW - Tree kernels

KW - Informatics

KW - Business informatics

UR - http://www.scopus.com/inward/record.url?scp=77949506401&partnerID=8YFLogxK

M3 - Journal articles

AN - SCOPUS:77949506401

VL - 11

SP - 555

EP - 580

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

SN - 1532-4435

ER -

Documents

Links

Recently viewed

Researchers

  1. Mathis Brinkmann

Activities

  1. Agile Portfolio Management Patterns - A Research Design
  2. Digital Transformation and Digital Business
  3. 17th Trends in Enterprise Architecture Research Workshop
  4. Benelux Conference on Artificial Intelligence 2017
  5. Implementing internet-based interventions for symptoms of depression and stress - results from a german routine care project
  6. Transparency in Research
  7. Stimmtraining - 2009
  8. Efficacy of an online- and smartphone-based Gratitude training for employees with elevated cognitive irritation - a secondary analysis of a randomized controlled trial
  9. Sub-Plenary: Partial Organization: Perspectives, Promises and Pitfalls after a Decade of Research
  10. 2023 Americas Conference on Information Systems
  11. European Conference on Information Systems 2023 (Veranstaltung)
  12. Changing ID Systems in West Africa and their Implications
  13. 12. Internationale Tagung Wirtschaftsinformatik 2015 - WI2015
  14. Undoing the ‘Migration Crisis’ Statistics. The Displacement Tracking Matrix by the International Organization for Migration and its Discontents in Niger
  15. The Sociotechnical Lives of Digital Identification: Intermediaries, Citizenship and Belonging
  16. African Migration Research Networks: Where Next?
  17. d3con - 2015
  18. A daily diary study on humor at work: Some preliminary findings
  19. Datenschutz (Organisation)
  20. Wo das Land zu Ende ist
  21. 82nd Annual Meeting of the Academy of Management - AOM 2022
  22. Video Case Studies in Online Teaching. Insights from an International Study Program
  23. Intersectionality as a lens to educational inequalities during and after the COVID-19 pandemic
  24. Die Adresse des Motivs. Oder: Das Schreiben der Ähnlichkeit
  25. Information Systems Journal (Fachzeitschrift)
  26. Wissensintegration und Wissenstransfer in der transdisziplinären Nachhaltigkeitsforschung: Das Beispiel Global TraPs.